貝葉斯網在數據挖掘中的應用

李強徐捷

1.國防科技大學電子科學與工程學院，湖南 長沙 410073

2.國防科技大學信息工程研究所，湖南 長沙 410073

貝葉斯網在數據挖掘中的應用

李強1徐捷2

1.國防科技大學電子科學與工程學院，湖南 長沙 410073

2.國防科技大學信息工程研究所，湖南 長沙 410073

貝葉斯網用圖形的模式表示變量集合的聯合分布，應用于數據挖掘能夠將變量之間的潛在依賴關系反映出來。介紹了貝葉斯網，概括了構造貝葉斯網的方法，給出了建網的偽代碼，通過一個實例說明了貝葉斯網在數據挖掘中的應用。

貝葉斯網；數據挖掘；貝葉斯學習；貝葉斯推理

貝葉斯網（Bayesian Network），是一種對概率關系的有向圖描述，適用于概率性的和不確定性的事物。貝葉斯網的結構蘊含了某些規則，節點之間的依賴關系則蘊含了某些知識。數據挖掘中使用貝葉斯網方法，能夠發掘出多層次的、多點的關聯關系，具有處理不完整數據和噪聲數據的能力，能夠挖掘出隱含的知識而且具有良好的可理解性和邏輯性[1]。

1 貝葉斯網

N元隨機變量X={X1，X2,…,Xn}，其貝葉斯網絡模型是一個二元組B={Bs，Bp}，其中:

（1）Bs={X，E}表示貝葉斯網絡的結構。Bs是一個有向無環圖（Directed Acyclic Graph， DAG），X={X1，X2,…,Xn}是結點的集合，每個結點代表一個變量、狀態或者屬性等實體，記π(xi)為BS中結點的父結點的集合；E是圖中結點之間的有向弧的集合，反映結點之間的依賴關系。是貝葉斯網模型的概率分布集合，用于衡量結點之間的依賴關系，其中π(xi)表示結點xi的父節點集合，表示先驗知識。貝葉斯網約定任意結點的子節點與非子節點之間是條件獨立的，并且滿足d-分割[2]的結點都是條件獨立的，那么由貝葉斯概率的鏈規則（chain rule）有:

圖1 一個簡單的貝葉斯網

這種由條件獨立性得到的鏈規則可以將聯合分布分解為若干個復雜度較低的概率分布的乘機，使得模型的復雜度降低。例如，假設圖1中的變量都是布爾型的，，其中xi表示xi=true，表示xi=false。那么圖1中所有變量都取true的聯合分布概率可以這樣計算:

一般來說，描述圖1中8個點組成的聯合分布需要28-1=255個局部概率，而在貝葉斯網中，只需要計算21+23+22+21+1+22+1+1=23個局部概率，這就是所謂的條件概率表（CPT）。

2 貝葉斯網的學習

貝葉斯網的學習就是要尋找一種能夠按照某種測度最好地與給定實例數據集擬合的網絡結構，即尋找一個有向無環圖和一個與圖中每個結點相關的條件概率表。尋找有向無環圖稱為網絡結構學習，獲取條件概率表稱為網絡參數學習。由于通過網絡結構與數據集可以確定參數，故網絡結構學習是貝葉斯網絡學習的核心。貝葉斯網絡結構學習一般可分為兩類:基于獨立性檢測的方法和基于網絡質量衡量的方法。

基于獨立性檢測的方法假設存在一個網絡的結構能夠完全的表示變量之間的依賴或者獨立性關系[3]，使用給定的數據集進行統計測試每一個依賴或者獨立性關系，其基本步驟為:

基于網絡質量衡量的方法也稱為基于打分-搜索的方法，其基本思想是為可能的網絡結構打分，通過得分衡量網絡的質量，選擇質量最好的結構。這種方法需要為結構打分的標準和搜索網絡結構的方法。常用的打分標準有:貝葉斯標準[4]、MDL[5]（最小描述長度）標準、AIC標準和Entropy（熵）標準[6]等。使用窮舉法遍歷完全結構空間是一個NP難度的問題[7]，因此一般使用啟發式的搜索算法，常用的有K2算法、爬山法、模擬退火算法、禁忌搜索和遺傳算法等。基于網絡質量衡量的偽代碼如下:

3 貝葉斯網推理

貝葉斯網推理就是在給定一個貝葉斯網模型的情況下，根據已知條件，利用貝葉斯概率中的條件概率的計算方法，計算出查詢結點概率[8]。在理論上由聯合分布可以推斷出任何在貝葉斯網絡中人們想知道的概率，根據局部概率分布可以得到聯合概率分布。貝葉斯網推理主要有三類問題:由原因推結論的后驗概率問題、由結論推出原因的最大后驗假設問題（MAP）和提供解釋以支持現象的最大可能假設問題（MPE）。

4 貝葉斯網與數據挖掘

貝葉斯網不僅可以表達不確定知識，還能夠進行概率推理。其學習算法能夠從大量的數據中自動構建網絡，非常適合不確定知識的發現。貝葉斯網應用于數據挖掘獨特地優勢:能挖掘出隱含性的知識，具有良好的邏輯性和可理解性，極大地簡化了概率的運算，能夠進行因果雙向推理。圖2是貝葉斯網應用于數據挖掘的基本框架。

圖2 基于貝葉斯網的數據挖掘框架

使用貝葉斯網進行數據挖掘一般按照三步進行:首先確定變量集和變量域，這里要充分利用相關領域的專家知識；然后構建貝葉斯網，確定網絡結構和條件概率分布；最后計算查詢變量的概率。

為了說明貝葉斯網在數據挖掘中的計算方法，使用來自UCI 的Wisconsin BREAST_CANCER乳腺癌數據集[10]。數據集包含699個實例，每個實例有9個數值型的特征屬性和一個類屬性。使用這個數據集建立貝葉斯網，挖掘各屬性之間的關系，推斷腫瘤是良性的（class=0）還是惡性的（class=1）。

針對BREAST_CANCER數據集，李光，張鳳斌等使用樸素貝葉斯法和K-Means算法進行了分類挖掘[11]，得出的結果如表1中的第2、3行所示。本文在WEKA3.7智能分析環境[9]下使用C4.5決策樹算法得到的結果如表1中第4行所示。將以上三種方法作為對比，本文使用貝葉斯網方法進行挖掘。首先將數值型變量離散化，得到如表2所示的結果，接著使用基于MDL評分標準和局部衡量的K2搜索算法進行，得到如圖3所示的貝葉斯網結構，經過10重交叉驗證，該模型精確度為94.2%。將四種方法得出的結果匯總入表1，可以看出:貝葉斯網方法精度優于樸素貝葉斯算法和K-Means算法，與C4.5算法水平相當，其優勢是輸出了反映變量依賴關系的網絡結構。

表1 結果對比

表2 BREAST_CANCER數據集的屬性和值域

圖3 由數據集構建的貝葉斯網

從得到的貝葉斯網可以挖掘出一些有用的信息，如屬性clump_thickness、cell_ shape_uniformity、bland_chromatin與其他屬性依賴關系數量最多，可能是識別腫瘤細胞的重要特征，需要密切關注；沒有連線的屬性之間不存在依賴關系（如cell_size_ uniformity與bare_nuclei），它們的變化可能是由不同的因素引起的，需要區別研究等，這些信息將為腫瘤細胞狀態的推斷和病情研究提供輔助。

需要注意的是，同一個問題可能建立起不同的貝葉斯網，但描述的是來自于同一個聯合概率分布，這是由于聯合概率分布被分解為條件概率分布而產生的。通過機器學習得到的網絡中有向邊代表依賴關系，因果關系只是依賴關系中的一部分。

5 結語

貝葉斯網是結合概率、統計和圖論發展起來的，有堅實的數學基礎，是研究復雜系統的不確定性和數據分析的一種有效工具。貝葉斯網應用于數據挖掘，能夠發現出數據的內在本質，在許多領域應用并取得了很好地效果，將在數據挖掘領域發揮愈加重要的作用。

[1] 劉偉娜，霍利民，張立國.貝葉斯網絡精確推理算法的研究[J].微計算機信息，2006.3-2:92～94

[2] 張連文，郭海鵬.貝葉斯網引論.[M] 北京:科學出版社，2006:67～69

[3] Chen J, Bell D, Liu W.Learning Bayesian networks from data: An efficient approach based on information theory [J].Artificial Intelligence, 2002, 137(1-2), pp.43～90.

[4] David Heckerman.A tutorial on learning Bayesian networks.Technical ReportMSR-TR-95-06, Microsoft Research, 1996.

[5] Suzuki J.Learning Bayesian Belief networks Based on the Minimum Description Length Principle: Basic Properties.IEEE Transactions on fundamentals, 1999, E82-A (9), pp.2237～2245.

[6] Cooper G F, Herskovits E A.A Bayesian method for the induction of probabilistic networks from data[J].Machine Learning, 1992, 9(4), pp.309～347.

[7] Cooper G.Computational complexity of probabilistic inference using Bayesian belief networks.[J].Artificial Intelligence, 1990, 42(2-3), pp.393～405.

[8] 董立巖，苑森淼等.基于預測能力的連續貝葉斯網絡結構學習[J].計算機工程與應用，2007，43(9)，pp.23～24

[9] Ian H.Witten, Eibe Frank, Mark A.Hall.Data Mining Practical Machine Learning Tools and Techniques.[M] 3rd Edition.2010, pp.262～273

[10] K.P.Bennett, O.L.Mangasarian: "Robust linear programming discrimination of two linearly inseparable sets".[J].Optimization Methods and Software 1, 1992, 23～34 (Gordon & Breach Science Publishers).

[11] 李光，張鳳斌.基于樹突狀細胞算法的分類方法研究[M].電腦知識與技術，2010, 6(31), pp.8798～8800

A

TP391.4

10.3969/j.issn.1001-8972.2012.13.050

李強(1987－),男,碩士研究生 ,研究領域為數據挖掘,信息。