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

張劍飛，劉克會，杜曉昕

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

?

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

張劍飛，劉克會，杜曉昕

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

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

[關鍵詞]貝葉斯網絡；KDB；依賴關系；Boosting；集成學習

0引言

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

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

1KDB模型及其構造算法

1.1KDB模型

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

圖1　樸素貝葉斯二階依賴擴展結構

1.2KDB的構造算法

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

(1)

1.2.1KDB分類器的模型

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

(2)

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

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

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

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

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

1.2.2KDB算法過程

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

(3)

(4)

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

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

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

(c) 將Xmax添加到S中.

(4)根據貝葉斯網絡G和數據Dataset計算概率和條件概率.

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

2KDB的集成方法

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

2.1LCKDB算法

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

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

輸出：KDB分類模型.

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

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

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

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

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

(c) 將Xmax添加到S中.

(4) 輸出KDB模型G.

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

2.2KDB集成

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

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

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

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

輸出：組合分類器H.

2:start←1

3：fort=1:T//構建弱分類器ht

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

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

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//結構學習結束

21:returnG//返回貝葉斯網絡結構G

22:L←L+1

23:constructhtbasedG//根據G進行參數學習得到分類器ht

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

25:ifet<0.5

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

29：else

30：goto 32

31：endif

32：start←start+1

33:endfor

3實驗與分析

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

表1　實驗數據集信息

表2　分類錯誤率的對比

根據表2中的實驗數據可以做如下分析：

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

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

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

4結束語

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

提出的BLCKBD算法的準確性一定程度的受閾值ε影響，因此如何合理選取有效閾值還需要進一步地研究.同時算法需要訓練不同的KDB分類器，花費時間較長，因此如何選取合適的訓練次數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]秦峰，任詩流，程澤凱，等. 基于屬性加權的樸素貝葉斯分類算法[J]. 計算機工程與應用，2008，44(6)：107-109.

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

[7]鄧偉斌，王國胤，王燕. 基于Rough Set的加權樸素貝葉斯分類模型[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].計算機研究與發展，2004，41(2)：340-345.

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

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

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

[14]汪春峰，張永紅. 基于無約束優化和遺傳算法的貝葉斯網絡結構學習方法[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