李強徐捷

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

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

貝葉斯網(wǎng)在數(shù)據(jù)挖掘中的應(yīng)用

李強1徐捷2

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

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

貝葉斯網(wǎng)用圖形的模式表示變量集合的聯(lián)合分布，應(yīng)用于數(shù)據(jù)挖掘能夠?qū)⒆兞恐g的潛在依賴關(guān)系反映出來。介紹了貝葉斯網(wǎng)，概括了構(gòu)造貝葉斯網(wǎng)的方法，給出了建網(wǎng)的偽代碼，通過一個實例說明了貝葉斯網(wǎng)在數(shù)據(jù)挖掘中的應(yīng)用。

貝葉斯網(wǎng)；數(shù)據(jù)挖掘；貝葉斯學(xué)習(xí)；貝葉斯推理

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

1 貝葉斯網(wǎng)

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

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

圖1 一個簡單的貝葉斯網(wǎng)

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

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

2 貝葉斯網(wǎng)的學(xué)習(xí)

貝葉斯網(wǎng)的學(xué)習(xí)就是要尋找一種能夠按照某種測度最好地與給定實例數(shù)據(jù)集擬合的網(wǎng)絡(luò)結(jié)構(gòu)，即尋找一個有向無環(huán)圖和一個與圖中每個結(jié)點相關(guān)的條件概率表。尋找有向無環(huán)圖稱為網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)，獲取條件概率表稱為網(wǎng)絡(luò)參數(shù)學(xué)習(xí)。由于通過網(wǎng)絡(luò)結(jié)構(gòu)與數(shù)據(jù)集可以確定參數(shù)，故網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)是貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的核心。貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)一般可分為兩類:基于獨立性檢測的方法和基于網(wǎng)絡(luò)質(zhì)量衡量的方法。

基于獨立性檢測的方法假設(shè)存在一個網(wǎng)絡(luò)的結(jié)構(gòu)能夠完全的表示變量之間的依賴或者獨立性關(guān)系[3]，使用給定的數(shù)據(jù)集進行統(tǒng)計測試每一個依賴或者獨立性關(guān)系，其基本步驟為:

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

3 貝葉斯網(wǎng)推理

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

4 貝葉斯網(wǎng)與數(shù)據(jù)挖掘

貝葉斯網(wǎng)不僅可以表達不確定知識，還能夠進行概率推理。其學(xué)習(xí)算法能夠從大量的數(shù)據(jù)中自動構(gòu)建網(wǎng)絡(luò)，非常適合不確定知識的發(fā)現(xiàn)。貝葉斯網(wǎng)應(yīng)用于數(shù)據(jù)挖掘獨特地優(yōu)勢:能挖掘出隱含性的知識，具有良好的邏輯性和可理解性，極大地簡化了概率的運算，能夠進行因果雙向推理。圖2是貝葉斯網(wǎng)應(yīng)用于數(shù)據(jù)挖掘的基本框架。

圖2 基于貝葉斯網(wǎng)的數(shù)據(jù)挖掘框架

使用貝葉斯網(wǎng)進行數(shù)據(jù)挖掘一般按照三步進行:首先確定變量集和變量域，這里要充分利用相關(guān)領(lǐng)域的專家知識；然后構(gòu)建貝葉斯網(wǎng)，確定網(wǎng)絡(luò)結(jié)構(gòu)和條件概率分布；最后計算查詢變量的概率。

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

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

表1 結(jié)果對比

表2 BREAST_CANCER數(shù)據(jù)集的屬性和值域

圖3 由數(shù)據(jù)集構(gòu)建的貝葉斯網(wǎng)

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

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

5 結(jié)語

貝葉斯網(wǎng)是結(jié)合概率、統(tǒng)計和圖論發(fā)展起來的，有堅實的數(shù)學(xué)基礎(chǔ)，是研究復(fù)雜系統(tǒng)的不確定性和數(shù)據(jù)分析的一種有效工具。貝葉斯網(wǎng)應(yīng)用于數(shù)據(jù)挖掘，能夠發(fā)現(xiàn)出數(shù)據(jù)的內(nèi)在本質(zhì)，在許多領(lǐng)域應(yīng)用并取得了很好地效果，將在數(shù)據(jù)挖掘領(lǐng)域發(fā)揮愈加重要的作用。

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

[2] 張連文，郭海鵬.貝葉斯網(wǎng)引論.[M] 北京:科學(xué)出版社，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] 董立巖，苑森淼等.基于預(yù)測能力的連續(xù)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)[J].計算機工程與應(yīng)用，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].電腦知識與技術(shù)，2010, 6(31), pp.8798～8800

A

TP391.4

10.3969/j.issn.1001-8972.2012.13.050

李強(1987－),男,碩士研究生 ,研究領(lǐng)域為數(shù)據(jù)挖掘,信息。