基奇PCA的貝葉斯網絡分糞器研究

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

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

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

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

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

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

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

用經PCA降維的數據和未經降維的數據集分別進行貝葉斯網絡結構的學習，所用時間如表2所示。

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

用圖1中的結點V4、圖2中的結點F13及圖3中的結點F8是類別標簽結點，其余結點為原數據結點的線性變換，無實際意義。實驗2用經過PCA降維后數據構造的貝葉斯網絡器(BN)與樸素貝葉斯(NB)分類器、TAN分類器分類對以上3組數據進行分類。分類準確率的比較如表3所示。

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

5 結束語
基于貝葉斯網絡結構學習中依賴分析方法需進行指數級的CI測試因而存在結點集較大時計算效率低的缺點，提出了將數據集先經過PCA主元分析的方法降維。減少結點數，再用降維后的數據進行貝葉斯網絡結構學習的方法，提高了網絡結構學習的效率，并通過提高學習到的網絡結構的正確性保證了較好的分類結果。此外。構建的網絡還具有結點少、結構簡單的特點，減少了網絡的復雜性。