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

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

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

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

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

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

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

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

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

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

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

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

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