基于k階依賴擴展的貝葉斯網(wǎng)絡分類器集成學習算法

張劍飛，劉克會，杜曉昕

(齊齊哈爾大學計算機與控制工程學院，黑龍江 齊齊哈爾 161006)

?

基于k階依賴擴展的貝葉斯網(wǎng)絡分類器集成學習算法

張劍飛，劉克會，杜曉昕

(齊齊哈爾大學計算機與控制工程學院，黑龍江 齊齊哈爾 161006)

[摘要]針對傳統(tǒng)的KDB(k-dependence Bayesian network classifiers)算法不能用Boosting技術(shù)集成進行性能提升的不足，提出了一種放松依賴條件的KDB集成分類器學習算法(BLCKDB).首先放松傳統(tǒng)KDB選擇最強依賴關(guān)系的條件限制，通過參數(shù)調(diào)節(jié)產(chǎn)生不同KDB分類器，然后用Boosting對產(chǎn)生的KDB分類器進行集成，實現(xiàn)集成分類器的構(gòu)造.實驗結(jié)果表明，該分類器分類準確性比KDB算法有較大的提升，尤其是對多屬性數(shù)據(jù)集更加明顯.

[關(guān)鍵詞]貝葉斯網(wǎng)絡；KDB；依賴關(guān)系；Boosting；集成學習

0引言

分類是模式識別和機器學習的基本內(nèi)容，其目的是利用樣本數(shù)據(jù)構(gòu)建一個分類模型，并利用這個模型對未知類別樣本進行預測.通過訓練樣本構(gòu)造分類器的方法有多種，比較著名的分類器包括決策樹分類器、神經(jīng)網(wǎng)絡分類器、支持向量機分類器和貝葉斯分類器等.其中樸素貝葉斯分類器是最簡單的貝葉斯網(wǎng)絡分類器，以簡單高效而著稱，被應用于各個領域.人們在樸素貝葉斯分類器的基礎上進行改進，得到了許多性能優(yōu)良的貝葉斯分類器.樸素貝葉斯分類器的改進方法主要有屬性依賴擴展、屬性選擇和整體集成.在屬性依賴擴展方面，N.Friedman[1]放寬樸素貝葉斯屬性獨立性假設，提出了一種樹狀貝葉斯網(wǎng)絡(Tree Augmented Na?ve Bayesian，TAN)，允許每個屬性至多有一個屬性父節(jié)點；M.Sahami等[2]將樸素貝葉斯和貝葉斯網(wǎng)絡結(jié)合起來提出了k依賴擴展的樸素貝葉斯分類器(KDB)；J.Cheng等[3]在TAN基礎上提出了BAN(Bayesian Network Augmented Na?ve Bayesian classifier)，它假設屬性間存在有向無環(huán)的網(wǎng)狀依賴關(guān)系；石洪波等[4]提出了一種限定性的雙層貝葉斯分類模型，通過選擇對分類影響較大的屬性來建立依賴關(guān)系，然后使用關(guān)鍵屬性將屬性間重要的依賴關(guān)系表達出來.在屬性選擇方面按照其對分類影響的大小對不同的屬性進行加權(quán)，將貝葉斯分類器構(gòu)造的重點放在關(guān)鍵屬性上，從而使分類器的性能得到提升.秦峰等[5]通過訓練樣本學習得到屬性加權(quán)參數(shù)，然后對每個屬性賦予權(quán)值，從而構(gòu)建出分類性能更好的加權(quán)樸素貝葉斯分類器；李方等[6]基于卡方擬合構(gòu)造思想提出了一種新的屬性間相關(guān)性度量方法，改進了屬性加權(quán)的貝葉斯分類模型；鄧維彬等[7]從粗糙集理論屬性的重要性出發(fā)，提出了以屬性的重要性作為權(quán)值的加權(quán)樸素貝葉斯分類方法.從整體集成分類角度可以將貝葉斯分類器作為基分類器，采用分類器集成技術(shù)將其分類性能進行提升.Boosting是一種重要的集成技術(shù)，它能夠提升不穩(wěn)定分類算法性能，但是樸素貝葉斯是穩(wěn)定分類器，不能直接使用Boosting技術(shù)進行集成，因此如何改變貝葉斯分類器的穩(wěn)定性成為貝葉斯分類器集成的一大難題.K.M.Ting等[8]提出了一種將決策樹和樸素貝葉斯相結(jié)合的算法，提升了樸素貝葉斯分類器的性能；K.M.Ting[9]又對樹狀的分層貝葉斯分類器進行集成，取得了良好的分類效果；石洪波等[10]通過放松TAN最大權(quán)重樹的構(gòu)造條件，提出了GTAN方法，構(gòu)造多個TAN分類器，最后對這些分類器進行集成，證明集成后的分類器有較高的分類準確性；李凱等[11]利用Oracle選擇機制破壞樸素貝葉斯分類器穩(wěn)定性，提出了一種基于Oracle的選擇樸素貝葉斯集成算法；張雯等[12]提出了基于屬性加權(quán)的貝葉斯集成方法(WEBNC)，這種分類方法不僅具有較高的分類準確性還有較高的泛化能力.對于比較復雜的貝葉斯分類器，人們主要使用啟發(fā)式的方法來獲得最優(yōu)的網(wǎng)絡結(jié)構(gòu)[13].

近年來，貝葉斯網(wǎng)絡學習方面的研究主要集中在使用各種智能算法來減小候選網(wǎng)絡的搜索空間，以達到更快找到最優(yōu)網(wǎng)絡結(jié)構(gòu)的目的.常用于貝葉斯網(wǎng)絡學習的智能算法有遺傳算法[14]、蟻群算法[15]、進化算法[16]等.目前，貝葉斯分類器的集成主要是通過對屬性空間進行劃分和選擇，然后根據(jù)選擇的結(jié)果訓練不同的貝葉斯分類器，而在通過結(jié)構(gòu)學習方法上實現(xiàn)分類器集成方面的研究相對較少.樸素貝葉斯分類器的k階依賴擴展(KDB)允許每個屬性節(jié)點和其他屬性節(jié)點最多有k條依賴邊，能夠比TAN和樸素貝葉斯更好地利用屬性間的依賴信息，使之分類準確性更高.但是使用傳統(tǒng)方法構(gòu)造的KDB分類器是不穩(wěn)定的，需要采取有效方法來改變其穩(wěn)定性，才能使用Boosting技術(shù)對其進行性能提升.本文通過放松KDB構(gòu)建條件，產(chǎn)生不同的KDB分類器，并采用Boosting技術(shù)對其集成，達到提高傳統(tǒng)KDB算法的分類性能目的.

1KDB模型及其構(gòu)造算法

1.1KDB模型

樸素貝葉斯分類器是一種簡單高效的貝葉斯分類方法，但其屬性獨立性假設使其不能利用屬性間依賴信息，限制了它的分類性能.Friedman提出的TAN算法，假設每個屬性至多有一個屬性父節(jié)點，能夠較好的利用屬性間的依賴信息，但也只能較少部分利用依賴信息.為了更進一步利用屬性間的依賴信息，Sahami提出了KDB方法，將屬性父節(jié)點的個數(shù)增加到k.依賴屬性的個數(shù)k可以根據(jù)需要設定，因此可以通過k值來調(diào)節(jié)分類器和數(shù)據(jù)擬合程度，從而獲得更好的分類性能.當k=1時，樸素貝葉斯的k依賴擴展就是TAN分類模型.但是隨著k值的增大，在分類器準確率提高的同時，分類效率也會隨之下降，因此綜合考慮分類正確率和分類效率問題，將樸素貝葉斯進行二階擴展比較合適，本文中k取為2.

圖1　樸素貝葉斯二階依賴擴展結(jié)構(gòu)

1.2KDB的構(gòu)造算法

對于給定訓練集Dataset={(x1，y1)，(x2，y2)，…，(xi，yi)，…，(xn，yn)}，其中xi是訓練數(shù)據(jù)中第i個實例，yi是該實例的類別.分類的目的是使用特定方法對數(shù)據(jù)集Dataset進行分析，形成一個能對未知類別樣本進行預測的分類模型.根據(jù)貝葉斯最大后驗準則，對于任意給定的實例(xi1，xi2，…，xiN)，貝葉斯分類器將其歸入到后驗概率P(c|xi1，xi2，…，xiN)，則最大的類C*為

(1)

1.2.1KDB分類器的模型

在KDB模型中，由于每個節(jié)點最多有k個屬性節(jié)點，所以KDB分類器的模型表述為

(2)

對于2階依賴擴展的KDB，∏xik有3種形式：

(1) ∏xik={ci}，即xik僅有類似其父節(jié)點，而沒有屬性父節(jié)點；

(2) ∏xik={ci，xjl}，即xik有1個屬性父節(jié)點和類父節(jié)點；

(3) ∏xik={ci，xjl，xjk}，即xik具有2個屬性父節(jié)點和1個類父節(jié)點.

因此，構(gòu)造KDB分類模型的主要問題就是確定每個節(jié)點的屬性父節(jié)點.Sahami提出的KDB構(gòu)造算法的主要思想是根據(jù)屬性和類間的互信息I(X；C)來指定依賴弧的方向，根據(jù)類條件互信息來判斷屬性間是否存在依賴關(guān)系.

1.2.2KDB算法過程

(1) 計算每個屬性和類的互信息I(Xi；C)以及不同屬性間的類條件互信息I(Xi；Xj|C)，計算方法為：

(3)

(4)

(2) 初始化貝葉斯網(wǎng)絡結(jié)構(gòu)G，G初始化時僅有一個類節(jié)點C，用S表示添加到G中的屬性節(jié)點集，初始化時S置為空.

(3) 重復以下過程至S中包含所有的屬性節(jié)點.

(a) 選擇不在S中并且I(Xi；C)值最大的屬性為Xmax，在G上添加一個節(jié)點表示Xmax，并添加一條從類節(jié)點指向Xmax的弧.

(c) 將Xmax添加到S中.

(4)根據(jù)貝葉斯網(wǎng)絡G和數(shù)據(jù)Dataset計算概率和條件概率.

算法使用互信息作為衡量屬性間是否存在依賴關(guān)系的標準，但是某一屬性和其他屬性依賴關(guān)系較弱時，它們間的依賴關(guān)系對分類結(jié)果影響不大，因此又提出了一種改進算法KDB-θ，該算法為類條件互信息I(Xi；Xj|C)設置一個閾值θ，只有條件互信息大于θ時才會添加屬性節(jié)點之間的弧.因此，可以通過調(diào)整閾值θ來控制屬性的依賴關(guān)系.

2KDB的集成方法

KDB利用條件互信息來表征屬性間的依賴關(guān)系，條件互信息越大依賴關(guān)系越強.我們放松對依賴弧的選擇條件，選取符合一定條件的依賴關(guān)系來添加相應弧.這樣構(gòu)造出來的KDB分類器雖然分類能力不是最好，但是它能從不同方面反映屬性間關(guān)系.在此基礎上進行分類器集成學習可以有效地提高分類器準確率和泛化能力.

2.1LCKDB算法

下面為放松約束條件的KDB算法(Loosing Constraint k-dependence Bayesian network classifiers，LCKDB).

輸入：數(shù)據(jù)集Dataset={(x1，y1)，(x2，y2)，…，(xi，yi)，…，(xn，yn)}，閾值ε；

輸出：KDB分類模型.

(1) 計算每個屬性和類的互信息I(Xi；C)以及屬性間的類條件互信息I(Xi；Xj|C).

(2) 初始化貝葉斯網(wǎng)絡結(jié)構(gòu)G，初始化時G中僅有一個類節(jié)點C，用S表示添加到G中的屬性節(jié)點，初始時S置為空.

(3) 重復以下過程至S中包含所有的屬性節(jié)點.

(a) 選擇不在S中并且有最大的I(Xi；C)的屬性Xmax，在G上添加一個節(jié)點表示Xmax，并添加一條從類節(jié)點指向Xmax的弧；

(b) 在S中選擇I(Xi；Xj|C)≥ε不同變量Xj，將Xj放入一個集合Xc，選取符合條件的start≤|Xc|，L+start<|Xc|(|Xc|為滿足條件屬性的個數(shù))的2個屬性Xc(start)和Xc(start+L)作為Xmax的父節(jié)點，在G上添加從Xc(start)和Xc(start+L)這2個節(jié)點指向Xmax的弧(如果Xc中只有一個元素，則增加一條該元素指向Xmax的弧，沒有元素就不添加)；

(c) 將Xmax添加到S中.

(4) 輸出KDB模型G.

在上述算法中，通過參數(shù)ε可以對屬性間依賴關(guān)系存在與否進行控制，如果ε選擇過小，就可能使任意2個屬性間都存在依賴關(guān)系，但是這種依賴關(guān)系十分微弱，在KDB結(jié)構(gòu)中添加弧會造成分類精度的下降.如果ε選擇過大，可能導致屬性間不存在依賴關(guān)系，從而退化到樸素貝葉斯分類模型.start和L+start對應的是符合條件屬性集合Xc中的2個屬性，通過改變start和L的值可以改變一個屬性的2個父節(jié)點，因此可以構(gòu)造反映不同依賴關(guān)系的KDB分類器.

2.2KDB集成

Boosting算法能夠提升不穩(wěn)定分類器的分類性能，其原因是用于集成的基分類器之間存在差異，這些差異的存在使得最后形成的組合分類器能夠綜合多個基分類器的優(yōu)點，具有更高的分類準確性和泛化能力.

LCKDB算法通過調(diào)整參數(shù)start和L構(gòu)建的KDB分類器能反映不同的依賴關(guān)系.在分類過程中每個KDB分類器的側(cè)重點有所不同，在一些分類器中被錯誤分類的樣本在另一個分類器中就可能被正確分類.為此，可以將這些不同的KDB分類器作為集成基分類器.在原始數(shù)據(jù)集上用LCKDB方法訓練分類器，然后根據(jù)其分類結(jié)果調(diào)整樣本分布，將其作為新的數(shù)據(jù)集訓練分類器，最后根據(jù)這些分類器的表現(xiàn)，按照加權(quán)的方式將其組合起來形成一個強分類器，其具體算法如下.

BLCKBD集成算法(Boosting LCKBD algorithm，BLCKBD)

輸入：數(shù)據(jù)集Dataset={(x1，y1)，(x2，y2)，…，(xi，yi)，…，(xn，yn)}，弱分類器數(shù)T，閾值ε；

輸出：組合分類器H.

2:start←1

3：fort=1:T//構(gòu)建弱分類器ht

4：ComputeI(Xi；C)，I(Xi；Xj|C) //計算互信息和條件互信息

5：G={C}，S=φ，L←1//G是貝葉斯網(wǎng)絡，S是添加到G的屬性節(jié)點

6：while (length(S)

7:ifI(Xmax；Xj|C)≥εthen

8:AddXjtoXc//選取條件互信息大于ε的屬性加入集合Xc

9:endif

10:iflength(Xc)<2

11:add an arc fromXctoXmax//在G中添加Xc指向Xmax的弧

12:else

13：if (start+L

14:add two arcs fromXc(start)，Xc(start+L) toXmax

15:else

16:choose two attributes fromXcand add corresponding arcs

//隨機選擇Xc中的2個屬性并添加指向Xmax的弧

17:endif

18:endif

19:AddXmaxtoS//將Xmax加入S

20:endwhile//結(jié)構(gòu)學習結(jié)束

21:returnG//返回貝葉斯網(wǎng)絡結(jié)構(gòu)G

22:L←L+1

23:constructhtbasedG//根據(jù)G進行參數(shù)學習得到分類器ht

24:computeet//計算分類錯誤率

25:ifet<0.5

26:αt←0.5*log((1-et)/et)//計算第t個分類器權(quán)重αt

29：else

30：goto 32

31：endif

32：start←start+1

33:endfor

3實驗與分析

從UCI機器學習數(shù)據(jù)集中選取12個用于實驗，數(shù)據(jù)集信息如表1所示.本文提出的算法是針對離散數(shù)據(jù)進行分類的，因此需要對連續(xù)數(shù)據(jù)進行離散化處理，對不完整數(shù)據(jù)集的屬性值丟失的樣本剔除.所有實驗是使用Matlab來實現(xiàn)的，實驗中基分類器個數(shù)T=20，ε根據(jù)實際情況選取0.01~0.03間數(shù)值.實驗對KDB和BLCKDB算法在分類錯誤率方面進行比較.對不同的數(shù)據(jù)集采用十折交叉驗證方法來估計分類錯誤率(見表2).

表1　實驗數(shù)據(jù)集信息

表2　分類錯誤率的對比

根據(jù)表2中的實驗數(shù)據(jù)可以做如下分析：

(1) 整體上BLCKDB算法比KDB具有更高的分類準確率.KDB算法的平均分類錯誤率為17.58%，明顯高于BLCKDB的12.75%.這是因為傳統(tǒng)的KDB分類器僅僅依靠屬性間的強依賴關(guān)系進行分類，而BLCKDB算法將反映不同數(shù)據(jù)信息的KDB分類器通過加權(quán)的方式組合起來，從而使最終形成的強分類器能夠更好地表達數(shù)據(jù)間依賴關(guān)系.

(2) 從分類錯誤率變化可以看出，對屬性較多的數(shù)據(jù)集BLCKDB方法的錯誤率下降更多.例如在Lung cancer，Lymphography，Promoters和Tic_tac_toe數(shù)據(jù)集上分類錯誤率下降達到30%以上.這是因為屬性較多的數(shù)據(jù)集屬性間可供選擇依賴關(guān)系較多，利用BLCKBD方法構(gòu)造出來的分類器差異較大，使最終形成的分類器與數(shù)據(jù)擬合程度更高.

(3) 從實驗數(shù)據(jù)可以看出BLCKDB比KDB具有更好的分類性能，這充分說明了利用Boosting技術(shù)對存在差異性分類器進行集成能夠大幅度地提高其分類準確性和泛化能力.

4結(jié)束語

在傳統(tǒng)KDB結(jié)構(gòu)學習中，選取與新添加屬性節(jié)點具有最大條件互信息的k個屬性作為該屬性節(jié)點的父節(jié)點，構(gòu)造出來的KDB具有較好的分類性能，但由于其是穩(wěn)定分類器，不能使用Boosting技術(shù)對其集成.本文提出的BLCKDB算法通過放松選取最大條件互信息的k個屬性節(jié)點作為其屬性父節(jié)點的條件限制，選取滿足一定條件的k個屬性，然后通過調(diào)整參數(shù)L和start的值來構(gòu)造不同的KDB分類器，最后使用Booting技術(shù)對構(gòu)造的KDB分類器作為基分類器進行集成，從而形成分類精度更高的組合分類器.

提出的BLCKBD算法的準確性一定程度的受閾值ε影響，因此如何合理選取有效閾值還需要進一步地研究.同時算法需要訓練不同的KDB分類器，花費時間較長，因此如何選取合適的訓練次數(shù)T以達到分類準確性和分類效率的平衡，仍需進一步深入研究.

[參考文獻]

[1]FRIEDMAN N，GEIGER D，GOLDSZMIDT M. Bayesian network classifiers [J]. Machine Learning，1997，29(2/3)：131-163.

[2]SAHAMI M. Learning limited dependence Bayesian classifiers[C]. //Proceedings of the Second International Conference on Knowledge Discovery and Data Mining，Menlo Park：ACM，1996，335-338.

[3]CHENG J，GREINER R. Comparing Bayesian network classifiers[C].// Proceedings of the Fifteenth International Conference on Uncertainty in Artificial Intelligence，Sweden：Stockholm，1999，101-108.

[4]石洪波，王志海，黃厚寬，等. 一種基于限定性的雙層貝葉斯分類模型[J]. 軟件學報，2004，1(2)：193-199.

[5]秦峰，任詩流，程澤凱，等. 基于屬性加權(quán)的樸素貝葉斯分類算法[J]. 計算機工程與應用，2008，44(6)：107-109.

[6]李方，劉瓊蓀. 基于改進屬性加權(quán)的樸素貝葉斯分類模型[J]. 計算機工程與應用，2010，46(4)：132-133.

[7]鄧偉斌，王國胤，王燕. 基于Rough Set的加權(quán)樸素貝葉斯分類模型[J]. 計算機科學，2007，34(2)：204-206.

[8]TING K M，ZHENG Z J. Improving the performance of boosting for naive Bayesian classification[C]. //Proceedings of the third Pacific-Asia Conference on Knowledge Discovery and Data Mining，Beijing：Pacific-Asia Conference commitee，1999：296-305.

[9]TING K M，ZHENG Z J. A study of adaboost with na?ve Bayesian classifier：weakness and improvement [J]. Computational Intelligence，2003，19(2)：186-200.

[10]石洪波，黃厚寬，王志海. 基于Boosting的TAN組合分類器[J].計算機研究與發(fā)展，2004，41(2)：340-345.

[11]李凱，郝麗鋒. 基于Oracle選擇的樸素貝葉斯集成算法[J]. 計算機工程，2009，35(5)：183-185.

[12]張雯，張華祥. 屬性加權(quán)的樸素貝葉斯集成分類器[J]. 計算機工程與應用，2010，46(29)：144-146.

[13]曾安，李曉兵，楊海東，等. 基于最小描述長度和K2的貝葉斯網(wǎng)絡結(jié)構(gòu)學習算法[J]. 東北師大學報(自然科學版)，2014，46(3)：53-58.

[14]汪春峰，張永紅. 基于無約束優(yōu)化和遺傳算法的貝葉斯網(wǎng)絡結(jié)構(gòu)學習方法[J].控制與決策，2013，28(4)：618-622.

[15]JI J Z，HU R B，ZhANG H X，et al. A hybrid method for learning Bayesian networks based on ant colony optimization [J]. Applied Soft Computing，2011，11(4)：3373-3384.

[16]LARRANAGAA R，KARSHENAS H，BIELZA R，et al. A review on evolutionary algorithms in Bayesian network learning and inference tasks [J]. Information Sciences，2013，233(1)：109-125.

(責任編輯：石紹慶)

Ensemble learning basedk-dependence Bayesian network classifiers

ZHANG Jian-fei，LIU Ke-hui，DU Xiao-xin

(College of Computer and Control Engineering，Qiqihar University，Qiqihar 161006，China)

Abstract:For the performance of traditional KDB (k-dependence Bayesian network classifier) can not be enhanced by singly using Boosting technology，this paper proposed a classifier ensemble algorithm called RLCKDB by loosing the dependent condition of KDB. First it relaxes the he constraints of KDB-choosing the strongest dependences and adjusts the parameter to generate different KDB，then asset these different KDBs through Boosting algorithm to construct the ensemble classifier. Experimental results show that the classification accuracy of BKDB is higher than that of KDB，especially in the dataset with more attributes.

Keywords:Bayesian networks；KDB；dependence relationship；Boosting；ensemble learning

[中圖分類號]TP 181[學科代碼]510·80

[文獻標志碼]A

[作者簡介]張劍飛(1974—)，男，博士，教授，主要從事智能算法研究.

[基金項目]黑龍江省自然科學基金資助項目(F201333)；教育部人文社會科學研究青年基金項目(14YJC630188).

[收稿日期]2014-12-16

[文章編號]1000-1832(2016)01-0065-07

[DOI]10.16163/j.cnki.22-1123/n.2016.01.015