條件互信息度量ＢＳＮＢＣ分類學習算法

摘要：在綜合考慮算法效率與效用性的基礎上提出了一種新的有界半樸素貝葉斯分類（bounded semi－naive Bayesian classifier，BSNBC）算法。傳統的SNBC僅能將兩個屬性構成一個組合屬性，大大制約了SNBC的分類性能。BSNBC在一定程度上克服了SNBC的上述弱點，它能將最多K個屬性組合成一個組合屬性節點。IP算法與LP算法可用于學習BSNBC，但是它們的搜索過程帶有一定的盲目性。提出的算法利用條件互信息將關聯性大的屬性組合在一起。實驗證明了其有效性。

關鍵詞：機器學習； 貝葉斯分類器； 半樸素貝葉斯； 條件互信息

中圖分類號：TP18文獻標志碼：A

文章編號：1001-3695(2007)11-0052-03

分類是數據分析與機器學習領域中的一個基本問題。近年來，從數據中學習可靠的分類器逐漸成為一個熱門研究課題。人們提出了不同的方法以從數據集中學習分類器。常見的方法有概率神經網絡、決策樹、支持向量機、貝葉斯網絡等。

貝葉斯網絡建立在統計理論基礎上，是用于描述不確定性知識的有力工具。從20世紀80年代開始就有很多人研究它在分類領域的應用。由于理論證明學習完全貝葉斯網絡分類模型是NP難題，人們提出了樸素貝葉斯分類器（NBC）。NBC假設各屬性之間在給定類別屬性的條件下相互獨立，這使得貝葉斯理論用于實際分類成為可能。在

某些領域，該模型具有良好的分類性能。但是許多實際問題中屬性間有很大的關聯性，獨立性假設使得NBC不能充分表達這些屬性之間的相關性，從而不能取得良好的分類效果。為此，Kononenko提出了semi－naive[1]貝葉斯分類（SNBC）模型。該模型的基本思想是將相關聯的屬性組合在一起，構成所謂的組合屬性節點（有時也被稱做大屬性節點）。在邏輯上這種組合屬性與NBC中的基本屬性無異，即各個組合屬性節點之間相對于類別屬性條件獨立，SNBC的分類思想以及分類過程類似于NBC。

傳統的SNBC只能將兩個屬性組合成組合屬性。最大似然理論[2]揭示了這種模型的局限性，從而出現了有界半樸素貝葉斯分類模型。它能將最多K個屬性組合起來。其中K是事先制訂的界限值。

本文在研究屬性間依賴關系的基礎上提出了一種新的屬性組合算法思想。在這一問題上人們已經做了大量工作，但是已經出現的許多算法的搜索過程帶有一定的盲目性，算法效率不高。筆者對此作了較深入的探討，所提出的分類器的分類效率較高。

從表2可以看出，當k=2，θ=0.02時，分類精度遠小于k=2，θ=0.03的情形，前者包含四個組合屬性，后者包含三個，這說明部分組合對分類未必有益；當k=4，θ=0.02時，分類精度低于k=2，3的情形，這顯示了組合屬性所含基本屬性個數過大也無益于提高性能；當k=3，θ=0．02時，所得組合屬性所含基本屬性的個數皆為3，這說明本算法可以用于建立K－規范BSNBC。表4中k=2， θ=0．01及k=3，θ=0.01的實驗結果也說明了同樣的問題。從表3可以看出，該數據庫的六個基本屬性大部分是相互獨立的。這說明了該算法在判定屬性間關聯程度方面的有效性。

5結束語

在對條件互信息進行概念延伸的基礎上，本文提出了一種有效的借助于條件互信息學習BSNBC分類器的算法。算法過程中建立的BSNBC模型的組合節點所包含的基本屬性個數不超過事先給定的界限值K，并且，基本屬性個數少于K的組合屬性的各基本屬性間相對于類別屬性的條件互信息值不小于閾值θ。當K與θ的取值適當時，能有效地將相互關聯的基本屬性組合為一個大屬性，同時避免將依賴關系小或相互獨立的屬性組合起來，從而提高分類性能。實驗也證明了這一點。

筆者下一步的工作是研究數據庫與K及θ間的關系，以期對于給定的數據庫找到最佳的界限值與條件互信息閾值組合。

參考文獻：

［1］KONONENKO I. Seminaive bayesian classifier[C]//KODROTOFF Y. Proc of the 6th European Working Session on Learning. NewYork:Springer－Verlag，1991:206-219.

［2］HUANG Kai－zhu，KING I， LYU M R. Finite mixture model of boun￣ded semi－naive Bayesian networks classifier[C]//Proc of ICANN/ICONIP.2003:115－122.

［3］HUANG Kai－zhu，KING I， LYU M R. Learning maximum likelihood semi－naive Bayesian network classifier[C]//Proc of the 2nd IEEE International Conference on Systems Man and Cybernetics.Hammanet. Tunisia:[s.n.]，2002.

［4］FRIEDMAN N， GEIGER D， GOLDSZMIDT M. Bayesian network classifiers[J]. Machine Learning，1997，29(2-3):131－163.

［5］邢永康，沈一棟.基于互信息和測度學習信度網結構[J].重慶大學學報:自然科學版，2001，24(1):78-83.

“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”