基奇PCA的貝葉斯網(wǎng)絡(luò)分糞器研究

1 引言
近幾年來，貝葉斯網(wǎng)絡(luò)已成為數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)中的一個(gè)主要工具，在分類、聚類、預(yù)測(cè)和規(guī)則推導(dǎo)等方面取得了良好的應(yīng)用效果。從歷史數(shù)據(jù)中學(xué)習(xí)貝葉斯網(wǎng)絡(luò)可采用基于依賴分析的方法。
常用的有：用Polytree表示概率網(wǎng)的方法、從完全圖刪除邊的方法等。這種方法需要進(jìn)行指數(shù)級(jí)的CI測(cè)試以發(fā)現(xiàn)依賴關(guān)系，當(dāng)結(jié)點(diǎn)集較大時(shí)，其計(jì)算效率低，所以大多數(shù)此類算法都假設(shè)結(jié)點(diǎn)有序；但這種假設(shè)可能會(huì)影響最后學(xué)習(xí)到的網(wǎng)絡(luò)結(jié)構(gòu)的正確性。對(duì)于稀疏網(wǎng)絡(luò)和具有較大樣本數(shù)據(jù)集的系統(tǒng)，這種方法非常有效。
針對(duì)基于依賴分析方法的這一缺點(diǎn)，在網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)之前應(yīng)用主元分析方法將數(shù)據(jù)降維，減少網(wǎng)絡(luò)結(jié)點(diǎn)數(shù)目，可提高算法效率、簡化網(wǎng)絡(luò)結(jié)構(gòu)。

2 數(shù)據(jù)處理及離散化
現(xiàn)實(shí)數(shù)據(jù)庫中的數(shù)據(jù)常存在數(shù)據(jù)不一致、數(shù)據(jù)丟失等現(xiàn)象，所以在運(yùn)用數(shù)據(jù)學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)前要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。此外，對(duì)于連續(xù)性數(shù)據(jù)(如溫度、濕度、長度等)，直接建立貝葉斯網(wǎng)絡(luò)模型計(jì)算復(fù)雜度大，從連續(xù)數(shù)據(jù)中很難正確學(xué)習(xí)到變量間的關(guān)系。因此首先將數(shù)據(jù)標(biāo)準(zhǔn)化，再將標(biāo)準(zhǔn)化后的連續(xù)變量離散化，用離散化后的數(shù)據(jù)進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的學(xué)習(xí)。這里采用模糊離散化方法，對(duì)數(shù)據(jù)集的每個(gè)屬性分別進(jìn)行離散化，每個(gè)屬性都有3個(gè)標(biāo)度：5標(biāo)度、7標(biāo)度、9標(biāo)度可以選擇。算法步驟如下：
(1)隨機(jī)初始化隸屬度矩陣：

3 基于PCA的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法
主元分析PCA(Principal Component Analysis)是通過可逆線性變換，將數(shù)據(jù)集轉(zhuǎn)換為由維數(shù)較少的特征成分表示的、包含原數(shù)據(jù)集所有信息或大部分信息的技術(shù)。通過PCA技術(shù)，可以將復(fù)雜數(shù)據(jù)簡化，因此它現(xiàn)已被廣泛應(yīng)用于數(shù)據(jù)挖掘、模式識(shí)別、信號(hào)評(píng)估、信號(hào)探測(cè)、圖像編碼等領(lǐng)域。主元分析的原理如下：
令x為表示環(huán)境的m維隨機(jī)向量。假設(shè)x均值為零，即

E[x]=0 (4)
令w表示m維單位向量，x在ω上投影。該投影被定義為向量x和ω的內(nèi)積，表示為：

主元分析的目的就是尋找一個(gè)權(quán)值向量w，使得表達(dá)式的值最大化：

即使得式(7)值最大化的w是矩陣的最大特征值所對(duì)應(yīng)的特征向量。
鑒于主元分析的優(yōu)點(diǎn)，這里引入主元分析技術(shù)給數(shù)據(jù)集降維，然后用降維后的數(shù)據(jù)構(gòu)建網(wǎng)絡(luò)，提高學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)算法的效率、簡化網(wǎng)絡(luò)結(jié)構(gòu)。構(gòu)造貝葉斯網(wǎng)絡(luò)的算法步驟如下：
(1)用普瑞姆算法生成最大似然樹構(gòu)造初始貝葉斯網(wǎng)絡(luò)；
(2)對(duì)所有互信息大于閾值且在當(dāng)前圖中無邊的結(jié)點(diǎn)對(duì)n1、n2：①找出它們鄰接路徑上的鄰居結(jié)點(diǎn)，設(shè)n1、n2的鄰居結(jié)點(diǎn)的結(jié)點(diǎn)集分別為S1和S2；② 令集合S1和S2中較小的一個(gè)作為條件集合C；③計(jì)算條件互信息v=I(n1，n2|c)，如果vε，則返回分離；否則，如果C只包含一個(gè)結(jié)點(diǎn)，那么轉(zhuǎn)去步驟⑤，否則，對(duì)每一個(gè)i，令Ci=c{C中的第i個(gè)結(jié)點(diǎn)}，vi=I(n1，n2|Ci)；④如果vminε，則返回分離，否則返回步驟③；⑤如果S2沒有用過，那么用S2作為條件集C，返回步驟③；否則，返回失敗。⑥如果這對(duì)結(jié)點(diǎn)在當(dāng)前圖中能夠被分離，則檢測(cè)下一對(duì)結(jié)點(diǎn)，否則，向網(wǎng)中添加連接這對(duì)結(jié)點(diǎn)的邊。
(3)對(duì)每一條圖中存在邊的結(jié)點(diǎn)對(duì)，如果除這條邊外它們之間還存在其他路徑，那么暫時(shí)從圖中移掉這條邊，然后對(duì)這對(duì)結(jié)點(diǎn)進(jìn)行步驟①～⑥的檢驗(yàn)；如果這對(duì)結(jié)點(diǎn)不能被分離，則仍將前面移掉的邊加入圖中，否則永久移除這條邊；
(4)用碰撞識(shí)別V結(jié)構(gòu)的方法定向網(wǎng)絡(luò)中的邊，對(duì)不能構(gòu)成V結(jié)構(gòu)的邊用打分的方法對(duì)其進(jìn)行定向。

4 實(shí)驗(yàn)
用IRIS實(shí)際數(shù)據(jù)、Zoo Data、Glass Identification Data作為網(wǎng)絡(luò)學(xué)習(xí)的數(shù)據(jù)集，這3組數(shù)據(jù)是UCI數(shù)據(jù)集中3個(gè)用于分類的數(shù)據(jù)集。
其中IRIS數(shù)據(jù)和Glass Identification Data是連續(xù)的，所以在用數(shù)據(jù)學(xué)習(xí)貝葉斯網(wǎng)絡(luò)前需要對(duì)數(shù)據(jù)進(jìn)行模糊離散化處理。以下實(shí)驗(yàn)中的每個(gè)屬性的離散化標(biāo)度是任意選擇的。實(shí)驗(yàn)1，比較經(jīng)PCA降維的數(shù)據(jù)構(gòu)造貝葉斯網(wǎng)絡(luò)并進(jìn)行分類的結(jié)果與未經(jīng)PCA降維的數(shù)據(jù)分類結(jié)果的準(zhǔn)確率，如表1所示。

用經(jīng)PCA降維的數(shù)據(jù)和未經(jīng)降維的數(shù)據(jù)集分別進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的學(xué)習(xí)，所用時(shí)間如表2所示。

對(duì)所用的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)算法進(jìn)行CI測(cè)試，最壞情況下的時(shí)間復(fù)雜度為O(N4)。由表2可知，采用PCA降維后，算法所用時(shí)間約占原構(gòu)造算法時(shí)間的34．58％，貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的學(xué)習(xí)效率有所提高。
經(jīng)PCA降維，IRIS數(shù)據(jù)集的屬性由4個(gè)減少為3個(gè)；ZooData的屬性由18個(gè)減少到12個(gè)；Glass Identification Data的屬性由11個(gè)減少為8個(gè)。屬性數(shù)量的減少使得網(wǎng)絡(luò)結(jié)構(gòu)更為簡單，并且由表2可以看出，經(jīng)PCA降維后進(jìn)行分類的結(jié)果準(zhǔn)確率不低于不經(jīng)過降維直接由數(shù)據(jù)集學(xué)習(xí)得到的貝葉斯網(wǎng)絡(luò)分類結(jié)果的準(zhǔn)確率。
經(jīng)PCA降維后的網(wǎng)絡(luò)結(jié)構(gòu)如圖1～圖3所示。

用圖1中的結(jié)點(diǎn)V4、圖2中的結(jié)點(diǎn)F13及圖3中的結(jié)點(diǎn)F8是類別標(biāo)簽結(jié)點(diǎn)，其余結(jié)點(diǎn)為原數(shù)據(jù)結(jié)點(diǎn)的線性變換，無實(shí)際意義。實(shí)驗(yàn)2用經(jīng)過PCA降維后數(shù)據(jù)構(gòu)造的貝葉斯網(wǎng)絡(luò)器(BN)與樸素貝葉斯(NB)分類器、TAN分類器分類對(duì)以上3組數(shù)據(jù)進(jìn)行分類。分類準(zhǔn)確率的比較如表3所示。

由實(shí)驗(yàn)1可知，使用PCA降維后構(gòu)造的貝葉斯網(wǎng)絡(luò)與未使用降維數(shù)據(jù)學(xué)習(xí)得到的網(wǎng)絡(luò)分類結(jié)果正確率相差不大，而這樣構(gòu)造的網(wǎng)絡(luò)分類結(jié)果比其他分類器正確率高很多，同時(shí)使用降維后數(shù)據(jù)構(gòu)造的網(wǎng)絡(luò)還具有結(jié)點(diǎn)少、結(jié)構(gòu)簡單、學(xué)習(xí)效率高等優(yōu)點(diǎn)。

5 結(jié)束語
基于貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)中依賴分析方法需進(jìn)行指數(shù)級(jí)的CI測(cè)試因而存在結(jié)點(diǎn)集較大時(shí)計(jì)算效率低的缺點(diǎn)，提出了將數(shù)據(jù)集先經(jīng)過PCA主元分析的方法降維。減少結(jié)點(diǎn)數(shù)，再用降維后的數(shù)據(jù)進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的方法，提高了網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的效率，并通過提高學(xué)習(xí)到的網(wǎng)絡(luò)結(jié)構(gòu)的正確性保證了較好的分類結(jié)果。此外。構(gòu)建的網(wǎng)絡(luò)還具有結(jié)點(diǎn)少、結(jié)構(gòu)簡單的特點(diǎn)，減少了網(wǎng)絡(luò)的復(fù)雜性。