基于分布估計算法的樸素貝葉斯分類問題研究

摘要:隨著基礎理論研究所取得的一系列進展，分布估計算法逐漸成為進化計算研究領域的一個新的研究方向，并成為當今國際進化算法研究的新熱點。采用機器學習的方法分析數據、指導搜索已經成為設計新算法的趨勢。將分布估計算法引入到樸素貝葉斯分類器系統中，設計基于基尼指數的適應度函數，從而進一步提高樸素貝葉斯分類器的性能。

關鍵詞:分布估計算法;樸素貝葉斯;分類;基尼指數

中圖分類號:TP18文獻標識碼:A文章編號:1009-3044(2010)11-2704-02

Study of Bayesian Classification Based on Estimation of Distribution Algorithm

YANG Xia1， DONG Hong-bin1，2， ZHANG Hai-yu3

(1.School of Computer Science and Information Engineering， Harbin Normal University， Harbin 150025， China; 2.National Science Park，Harbin Engineering University， Harbin 150001，China; 3.Department of Engineering， Heilongjiang August First Land Reclamation University， Daqing 163319， China)

Abstract: Estimation of distribution algorithmsh has gradually become a new research direction in the evolutionary computation researc with a series of progress made in fundamental research.，and become a new hot spot on international evolutionary algorithm. Analysis of data and to guide the search has become a trend in the design of new algorithms by the methods of machine learning. Estimation of distribution algorithms is introduced to the naive Bayesian classifier system and fitness function is designed based on the Gini index， which will further enhance the performance of Naive Bayes classifier.

Key words: estimation of distribution algorithm; naive bayes; classification; Gini index

近幾年，在進化計算領域興起了一類新型的優化算法，稱為分布估計算法，并迅速成為進化計算領域的研究熱點和解決工程問題的有效方法。分布估計算法的概念最初在1996 年提出，在2000年前后迅速發展，成為當前進化計算領域前沿的研究內容。2005年在進化計算領域權威的國際期刊出版了分布估計算法的專刊。近年來國際上進化計算領域的各大學術會議都將分布估計算法作為重要專題予以討論。貝葉斯分類器以其高準確率和高速度引起了越來越多的關注。而樸素貝葉斯由于其樸素假設在現實世界中很難滿足，因此需要通過各種方法提高分類器的性能。

1 基于分布估計算法的樸素貝葉斯分類器

1.1 分布估計算法

隨著基礎理論研究所取得的一系列進展，分布估計算法(estimation of distribution algorithms)以其較強的理論基礎逐漸成為進化計算研究領域的一個新的研究方向，并成為當今國際進化算法研究的新熱點。分布估計算法的基本思想就是使用概率的方法描述和表示每一代群體，并從個體中學習基因之間關系以及個體的適應度信息，利用學習到的信息生成性能更好的下一代群體[1-2]。

分布估計算法是遺傳算法和統計學習的結合，通過統計學習的手段建立解空間內個體分布的概率模型，然后對概率模型隨機采樣產生新的群體，如此反復進行，實現群體的進化。分布估計算法中沒有傳統的交叉、變異等遺傳操作，是一種全新的進化模式。這種優化技術能夠通過概率圖模型對變量之間的關系進行建模，從而能有效的解決多變量相關的優化問題[3]。周樹德等全面系統的介紹分布估計算法這一新技術[4]，并總結該算法的研究現狀和未來的研究方向。文獻[5]提出了一種自適應實值分布估計算法，借鑒遺傳算法中關于種群多樣性的性能指標，并根據該指標相應改變采樣時方差的值，從而擴大搜索空間，提高種群多樣性。文獻[6]提出一種新的基于最大熵的分布估計算法，主要用基于最大熵估計種群中的模式概率分布，取代貝葉斯網絡分布估計算法中的貝葉斯概率圖模型。該算法無需進行貝葉斯網絡學習，大大減少了計算量，而且還能獲取更準確的概率分布估計。

分布估計算法在算法設計、理論研究和實際應用方面仍需要做很多工作。作為一種新型的優化技術，分布估計算法的核心是解空間的概率模型。針對特定的優化問題，綜合考慮搜索空間的結構、概率模型的學習算法、樣本產生算法等。選擇合適的概率模型，是發揮分布估計算法性能的關鍵所在。分布估計算法的本質是統計學習與進化算法的結合，通過統計學習手段對群體中的數據進行分析和建模，以挖掘搜索空間結構的相關知識。采用機器學習的方法分析數據、指導搜索已經成為設計新算法的趨勢。

1.2 基尼指數

基尼指數是一種非純度的屬性分裂方法，適用于類別、二進制、連續數值等類型的字段，是Breiman等人于1984年提出的，被廣泛應用在CART算法、SLIQ算法、SPRINT算法和Intelligent Miner的決策樹算法中。Gini指數度量數據劃分或訓練數據集的不純度。尚文倩在[7]中提到改進的基尼指數算法，采用測量屬性對于分類來說的“純度” 的形式，即數值越大，“純度”越大，信息量越豐富，屬性越好.并提出了一種新型的文本分類模型(IGIC)，取得了良好的分類效果。

1.3 貝葉斯分類器

近年來，數據挖掘成為一個新的研究熱點。分類作為一種重要的數據分析形式，由于其具有大量的應用，也引起了研究者越來越多的關注。用于大型數據庫，貝葉斯分類已表現出高準確率和高速度。貝葉斯分類法是一種統計學分類方法，是機器學習和數據挖掘中最有效地學習方法之一[8]。通過分類算法的比較研究發現，一種稱作樸素貝葉斯分類法(Na?觙ve Bayesian classifier)的簡單貝葉斯分類算法可以與決策樹和經過挑選的神經網絡分類算法相媲美[9]。樸素貝葉斯分類法的“樸素” 是指它的條件獨立性假設，而實際的問題中這種樸素假設往往不能夠成立，雖然在某些不滿足獨立性假設的情況下它仍然可能獲得較好的分類性能，但是，仍然需要通過各種方法來提高樸素貝葉斯分類器的性能[4，9-10]。

文獻[11]提出一種改進的樸素貝葉斯模型，它對樣本空間中那些可能有助于提高分類準確率的子集給予更多的關注，從而達到提高模型分類準確率的目的。文獻[12]介紹了一種使用貝葉斯假設選擇子集概率的方法。文獻[12]提出了一種提高樸素貝葉斯分類器準確率的新算法—BoostFSNB，并與相關算法進行了對比，結果表明該算法的應用能夠提高分類器的準確率。文獻[14]通過分析比較得出10折交叉驗證能夠獲得更好的無偏性。董立巖等為了降低樸素貝葉斯分類模型的獨立性假設約束， 提出一種混合式樸素貝葉斯分類模型[15]。通過分析貝葉斯定理， 該模型把條件屬性集合劃分成若干個獨立的屬性子集， 然后用樹增廣樸素貝葉斯分類對屬性子集分別進行分類學習， 最后通過公式進行整合。張明衛等提出了一種基于相關系數的加權樸素貝葉斯分類模型[16]，通過計算條件屬性和決策屬性之間的相關系數，對不同的條件屬性賦予不同的權重，從而在保持簡單性的基礎上有效地提高了樸素貝葉斯算法的分類性能。文獻[17]提出了一種屬性加權樸素貝葉斯算法， 該算法通過屬性加權來提高樸素貝葉斯分類器性能，從訓練數據中直接學習得到加權參數。權值可以看作是計算某個類的后驗概率時某屬性取值對該類別的影響程度。對各屬性的每個取值采取不同的加權值， 從而體現出各個屬性的不同取值對分類的影響。文獻[18]對分類方法的新發展進行了較詳細的歸納，并總結了分類方法發展的趨勢。

文獻[19]提出學習近似模糊規則的混合遺傳算法來生成模糊分類器。它使用一種新的方法來促進種群間的共同進化，即通過個體運行的混合進化機制來發現多個規則。為了提高學習規則的質量，它提出一種通過每一代的遺傳操作產生性能優良的后代的局部搜索方法，最后從最后一代生成的種群中抽取規則集形成模糊分類器。文獻[20]對8種離散化方法進行了對比研究，并將其分別應用到NB/FNB，LBR和AODE三種分類器上進行對比實驗。文獻[21]歸納總結了現有的改進貝葉斯算法，并提出了一個新的貝葉斯模型即隱式樸素貝葉斯。它由每個屬性產生的父母來使其與其他屬性結合在一起產生權重，并通過大量實驗以不同的評價方法分別驗證了該算法的有效性。文獻[22]介紹了利用ROC曲線評價分類器性能的方法。文獻[23]介紹了一種比分類精度更能準確反應分類器性能的新方法AUC評價。

1.4 貝葉斯與進化算法的結合

文獻[24]首次將分布估計算法引入到分類器系統中，并與遺傳算法進行了對比，結果顯示分布估計算法要優于遺傳算法。文獻[25]提出了一個在基于概率的優化問題中使用貝葉斯推理技術的框架。基于這個框架，描述了一個簡單的連續貝葉斯分布估計算法。文獻[26]介紹了一個基于貝葉斯分類器在每一代進化中進行學習和模擬的新的進化計算方法。朱允剛提出了用遺傳算法簡化搜索空間然后進行貝葉斯結構學習算法[27]，該算法的搜索空間小于目前多數算法的搜索空間。金哲提出了一種基于遺傳算法的BAN分類器算法[28]。該算法對TAN分類器的結構進行了擴展，得到了一種受限制的BAN分類器。針對這種分類器的結構學習，設計了結合對數似然的適應度函數，并給出了網絡結構的編碼方案，設計了相應的遺傳算子，使得該算法能夠收斂到全局最優。文獻[29]提出一種新的算法，該算法為避免數據預處理時，訓練集的噪聲及數據規模使屬性約簡的效果不太理想，并進而影響分類效果，在訓練集上通過隨機屬性選取生成若干屬性子集，并以這些子集構建相應的貝葉斯分類器，然后采用遺傳算法進行優選。

2 結論

樸素貝葉斯分類器基于條件獨立性的樸素貝葉斯假設，而實際的問題中這種樸素假設往往不能夠成立，因此需要通過各種方法來提高樸素貝葉斯分類器的性能。分布估計算法是一種基于概率統計的優化算法，因此可以將分布估計算法用來強化樸素貝葉斯分類器的性能，并在實際問題中加以應用。

參考文獻:

[1] 閻平凡，張長水.人工神經網絡與模擬進化計算[M].北京:清華大學出版社，2005:610-614.

[2] Larranaga P，Lozano J A.Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation[M].Boston:Kluwer Academic Publishers，2002.

[3] Zhang Qing-fu， Muhlenbein H. On the Convergence of a Class of Estimation of Distribution Algorithms[J]. Evolutionary Comprtation，APRIL， 2004，8(2).

[4] 周樹德，孫增圻.分布估計算法綜述[J].自動化學報，2007，33(2).

[5] 張慶彬，吳惕華，劉波. 自適應實值分布估計算法[J].清華大學學報:自然科學版，2008，48(10).

[6] 姜群，王越. 基于最大熵的分布估計算法[J].微電子學與計算機，2007，24(11

[7] 尚文倩.文本分類及其相關技術研究[D].北京:北京交通大學博士論文，2007.

[8] Zhang H.The optimality of Na?ve Bayes[C].Proc. of the Seventeenth International Florida Artificial Intelligence Research Society Conference，2004.

[9] Han Jia-wei， Kamber M. 數據挖掘:概念與技術[M].北京機械工業出版社，2007.

[10] 程克非，張聰.基于特征加權的樸素貝葉斯分類器[J].計算機仿真，2006(10).

[11] Martinez Otzeta J M， Sierra B， Lazkano E， et al. Edited Naive Bayes[J].Ibero-American Journal of Artificial Intelligence，2006:63-69.

[12] Boulle M. Compression-Based Averaging of Selective Naive Bayes Classifiers[J].Journal of Machine Learning Research， 2007(8):1659-1685.

[13] Kotsiantis S， Pintelas P. Increasing the Classification Accuracy of Simple Bayesian Classifier[J]. Lecture Notes in Artificial Intelligence， Springer-Verlag， 2004(3192):198-207.

[14] Kohavi R. A study of cross-validation and bootstrap for accuracy estimation and model selection[C].Mellish C. Proccedings of IJCAI95， San Mateo: Morgan Kaufmann，1995:1137-1143.

[15] 董立巖，劉光遠，苑森淼，等.混合式樸素貝葉斯分類模型[J].吉林大學學報，2007(1):57-61.

[16] 張明衛，王波，張斌，等.基于相關系數的加權樸素貝葉斯分類算法[J].東北大學學報，2008(7).

[17] 秦鋒，任詩流，程澤凱，等.基于屬性加權的樸素貝葉斯分類算法[J].計算機工程與應用，2008，44(6):104-109.

[18] 張麗娟，李舟軍.分類方法的新發展:研究綜述[J].計算機科學，2006(10):11-15.

[19] Li Min-qiang， Wang Zhi-chun.A hybrid coevolutionary algorithm for designing fuzzy classifiers[J].Information Sciences，2009(179).

[20] Mizianty M， Kurgan L， Ogiela M. Comparative analysis of the impact of discretization on the classification with aive bayes and semiaive bayes classifiers[C].2008 Seventh International Conference on Machine Learning and Applications，2008.

[21] Jiang Liang-xiao， Zhang Harry， Cai Zhi-hua.A Novel Bayes Model:Hidden Naive Bayes[J].Knowledge and Data Engineering，2009.

[22] Bradley A P. The Use of the Area Under the ROC Curve in the Evaluation of Machine Learning Algorithms[J].Pattern Recognition，1997(30):1145-1159.

[23] Ling C X， Huang J， Zhang H. AUC: A Statistically Consistent and More Discriminating Measure than Accuracy[C].Proc. Int'l Joint Conf. Artificial Intelligence (IJCAI '03)， 2003:329-341.

[24] Rivera J， Santana R.Improving the Discovery Component of Classifier Systems by the application of Estimation of Distribution Algorithms[C].Proceedings of Student Sessions， ACAI'99， Chania， Greece， 1999:43-44.

[25] Gallagher M， Wood I， Keith J， et al.Bayesian inference in estimation of distribution algorithms[C].CEC2007，2007:127-133， .

[26] Miquelez T， Bengoetxea E， Larranaga P.Evolutionary Computation Based on Bayesian Classifiers[J].Int. J. Appl. Math. Comput. Sci.，2004，14(3):335-349.

[27] 朱允剛.基于進化算法的網結構學習研究[D].吉林:吉林大學博士論文，2007.

[28] 金哲.基于遺傳算法的貝葉斯增廣樸素貝葉斯分類器的研究與實現[D].吉林:吉林大學碩士論文，2006.

[29] 胡為成，胡學鋼.基于遺傳算法的樸素貝葉斯分類[J].計算機技術與發展，2007，17(1):30-32.