焦 鵬，王新政謝鵬遠

（1.海軍航空工程學院，山東煙臺264001；2.解放軍91055部隊，浙江臺州318050）

基于屬性選擇法的樸素貝葉斯分類器性能改進?

焦 鵬1，??，王新政1，謝鵬遠2

（1.海軍航空工程學院，山東煙臺264001；2.解放軍91055部隊，浙江臺州318050）

為提高樸素貝葉斯（Naive Bayesian）分類器的分類準確率，對樸素貝葉斯屬性選擇算法及假設屬性概率值先驗分布中的參數(shù)設置問題進行分析，提出將屬性先驗分布的參數(shù)設置加入到屬性選擇的過程中，并研究當先驗分布服從Dirichlet分布及廣義Dirichlet分布情況下的具體調(diào)整步驟。以UCI數(shù)據(jù)庫為例進行仿真實驗，結果表明當先驗分布服從廣義Dirichlet分布時，該方法可提高分類的準確率，如Parkinsons數(shù)據(jù)集，效率可提升13.32％。

樸素貝葉斯分類器；先驗分布；屬性選擇法；廣義Dirichlet分布

1 引 言

在數(shù)據(jù)挖掘領域，樸素貝葉斯分類器（Naive Bayesian Classifier，NBC）由于運算速度快、分類準確率較高，得到了廣泛的應用。NBC假設一個屬性值對給定類的影響獨立于其他屬性值，這樣的假設有助于提高運算效率，然而現(xiàn)實中往往不能滿足。研究者提出各種方法對NBC的分類性能進行改進，如樹增強樸素貝葉斯（Tree Augmented Naive Bayes，

TAN）［1］、惰性貝葉斯規(guī)則（Lazy Bayesian Rules）［2］、特征加權（Weighted Naive Bayes，WNB）［3］等方法。這些方法與NBC相比通常具有較好的分類精度，在一定程度上改進了NBC的性能。研究顯示，當數(shù)據(jù)樣本屬性之間相關程度很高時會降低分類準確率，因此希望NBC使用的屬性集合盡可能地服從條件獨立，即需要一個屬性選擇機制［4］。在眾多的屬性選擇方法中，樸素貝葉斯屬性選擇算法（Selective Naive Bayesian Algorithm，SNB）能有效剔除多余或影響分類結果的屬性，因此常被用于NBC中［5］。另外，為了改善NBC的分類效果，通常假設屬性的可能值服從某種先驗分布，一般是Dirichlet分布或廣義Dirichlet分布。針對先驗分布的參數(shù)設置已有很多學者提出各種設定方法［1］。在以往的研究中，屬性選擇結束后一般會直接進行分類而不考慮先驗分布。本文將各屬性先驗分布的參數(shù)調(diào)整加入到屬性選擇的過程中使之成為一個整體，即首先運用SNB算法對樣本數(shù)據(jù)集合進行屬性選擇，再根據(jù)其得出的屬性選擇順序?qū)x出的屬性群進行參數(shù)的個別調(diào)整。通過對UCI數(shù)據(jù)庫中的10個樣本數(shù)據(jù)集合進行分析，仿真實驗結果表明與以往的方法相比，本文提出的方法可提高分類準確性。

2 基礎理論分析

2.1 樸素貝葉斯分類器

NBC利用貝葉斯準則（Bayesian Decision Rule）以及屬性間條件獨立假設作為分類的依據(jù)［6］。根據(jù)貝葉斯定理，假設有n個屬性X1，X2，…，Xn，其中一筆數(shù)據(jù)x＝（x1，x2，…，xn）屬于第j個類別值的概率為Cj：

其中，p（Cj｜x）表示在給定某項樣本數(shù)據(jù)下分類到類別值Cj的概率，稱為后驗概率（Posterior Probability）；p（x）表示數(shù)據(jù)x出現(xiàn)的概率。比較不同類別值的后驗概率時，式（1）可以簡化為

根據(jù)NBC的屬性條件獨立假設，將式（2）展開：

因此，若某一類別值Cj的后驗概率最大，NBC可預測該筆數(shù)據(jù)x的類別值為Cj。

2.2 樸素貝葉斯屬性選擇算法

文獻［7］將屬性選擇法分成Filter和Wrapper兩種。Filter方法根據(jù)統(tǒng)計測度分析屬性之間的關系選擇屬性，不考慮選擇的屬性是否影響特定分類器的表現(xiàn)。而Wrapper方法在選擇過程中使用分類器的表現(xiàn)評估屬性的重要性。由于Wrapper方法考慮分類器的表現(xiàn)來篩選屬性，對未知的數(shù)據(jù)有較好的分類準確率，而Filter方法不需要反復地求得分類結果，因此執(zhí)行速度較快。

SNB算法是由文獻［5］提出，屬于Wrapper方法，其運行流程如圖1所示。初始階段設定S為空集合，從樣本數(shù)據(jù)中選取一個屬性到樸素貝葉斯分類器中做分類并計算分類準確率。重復這個過程直到樣本數(shù)據(jù)中所有屬性各自對應的分類準確率都已知，選擇使分類準確率最高的屬性Xi加入S中，此時Xi就是NBC選擇的第一個屬性。從樣本數(shù)據(jù)中計算未被選擇的屬性配合Xi得到的分類準確率，選出與之配合能使分類準確率最高的屬性Xj，Xj即為第二個選擇的屬性，重復以上步驟直到分類準確率不再提升。SNB算法的特點是采用前向搜索屬性的方法，即初始的屬性集合不包含任何屬性，一次選擇一個屬性直到分類準確率不再提升為止。經(jīng)過實驗發(fā)現(xiàn)，SNB算法使用較少的屬性但分類準確率較高，說明該分類方法有過濾冗余屬性的功能。

圖1 SNB算法流程圖

3 先驗分布的參數(shù)設定

3.1 先驗分布的參數(shù)設定

使用NBC進行分類時使用數(shù)據(jù)樣本集合中的所有屬性，并通過調(diào)整先驗分布中的參數(shù)來提高分類準確率。而SNB算法則是通過選擇對分類準確率真正有幫助的屬性供NBC使用。由于篩選的過程耗費時間，因此先驗分布的參數(shù)常使用Laplace Estimator用以滿足無信息性，使得屬性可能值的出現(xiàn)概率期望值相同。

文獻［8］在實驗研究中針對Dirichlet部分依序測試αi，發(fā)現(xiàn)αi＝60后分類準確率與αi成反比。因此對每個屬性做參數(shù)設定時，將參數(shù)αi的范圍設定為［1，60］，并取其中的整數(shù)。除了限定范圍外，調(diào)整參數(shù)時需滿足無信息性的限制，即在此條件下評估各事件的發(fā)生概率，都應給定相同的估計值且總和為1。此時各個變量對應的期望值應相同，但是不同的先驗分布推導出的期望值公式不同，參數(shù)的限制也有所差異。對Dirichlet分布而言，推導出的結果為各參數(shù)需設定相同的值（α1＝α2，…，＝αk＋1），以此限制在［1，60］作調(diào)整滿足無信息性。廣義Dirichlet分布在無信息性的限制滿足所有參數(shù)必須滿足式（4）：

由此可知，只要αi已知，便可通過式（4）求得βi的值，因此無論是Dirichlet分布還是廣義Dirichlet分布都只需調(diào)整參數(shù)αi。對于整個樣本數(shù)據(jù)的所有屬性做參數(shù)設定時，先選擇的屬性對接下來其他屬性的最優(yōu)參數(shù)設定有很大的影響。因此首先判斷各屬性對分類的重要性，重要性最高的屬性優(yōu)先調(diào)整參數(shù)和決定先驗分布。而SNB算法在挑選屬性的過程可看作屬性重要性的排序過程，根據(jù)SNB算法選擇的順序作為屬性參數(shù)調(diào)整的順序。

3.2 Dirichlet分布

定義1：隨機向量θ＝（θ1，θ2，…，θk）滿足θ1＋θ2＋…＋θk≤1且θj＞0（j＝1，2，…，k），如果其概率密度函數(shù)為

其中，αj＞0（j＝1，2，…，k＋1）且α＝α1＋α2＋…＋αk＋1，則隨機向量θ服從k維Dirichlet分布，記作θ～DK（α1，α2，…，αK；αK＋1）。

假設數(shù)據(jù)樣本中某個屬性有k＋1個可能值，令隨機向量θ＝（θ1，θ2，…，θk）為該屬性前k個可能值對應的出現(xiàn)概率，且θ～DK（α1，α2，…，αK；αK＋1）。令隨機向量y＝（y1，y2，…，yk＋1）代表此屬性k＋1個可能值分別的發(fā)生次數(shù)，yj表示此屬性第j個可能值出現(xiàn)的次數(shù)，如果yθ服從多項分配，根據(jù)Dirichlet分布的共軛性質(zhì)可推得后驗概率分布y～DK（α′1，α′2，…，α′K；α′K＋1），其中α′j＝αj＋yj，j＝1，2，…，k＋1表示根據(jù)收集樣本數(shù)據(jù)推導出屬性可能值的出現(xiàn)概率同樣服從Dirichlet分布，不過參數(shù)值有所改變。如果θm為θ的一個變量，則θm在給定y的條件下，期望值為

其中y＝y(tǒng)1＋y2＋…＋yk＋1。與NBC使用后驗概率進行分類相比，此處將后驗分布的期望值作為后驗概率進行計算。當一項新的樣本數(shù)據(jù)出現(xiàn)時，就可利用式（6）計算在給定類別下屬性的某個可能值發(fā)生的概率E（θm｜y），再利用式（3）找出使后驗概率最大的類別值，作為此項樣本數(shù)據(jù)的預估類別值。

調(diào)整步驟如下：

（1）將所有屬性的參數(shù)值設定為Laplace Estimator，利用SNB算法選擇一組屬性，假設共選擇m個屬性；

（2）針對選擇屬性中的第一個屬性參數(shù)，計算α1＝α2，…，＝αk在［1，60］之間各整數(shù)的分類準確率，選擇使分類準確率最高的參數(shù)值為，表示第一個屬性的最優(yōu)參數(shù)值；

（3）設定第一個屬性的α1＝α2，…，＝αk＋1＝，再針對第二個選擇的屬性參數(shù)計算在［1，60］之間整數(shù)的分類準確率，選擇使分類準確率最高的參數(shù)值設定為，使用同樣的方法找出。

3.3 廣義Dirichlet分布

定義2：隨機向量θ＝（θ1，θ2，…，θk）滿足θ1＋θ2＋…＋θk≤1且θj＞0（j＝1，2，…，k），如果其概率密度函數(shù)為

其中，參數(shù)αj，βj，λj滿足αj＞0（j＝1，2，…，k），βj＞0（j＝1，2，…，k），λk＝βk－1及λj＝βj－αj＋1－βj＋1（j＝1，2，…，k－1），則隨機變量θ服從k維廣義Dirichlet分布。記作θ～GDK（α1，α2，…，αK；β1，β2，…，βK）。

與Dirichlet分布在樸素貝葉斯分類器的作用一樣，當假設樣本數(shù)據(jù)中某屬性服從廣義Dirichlet分布，如果該屬性有k＋1個可能值，令隨機向量θ＝（θ1，θ2，…，θk）為該屬性前k個可能值的概率，且θ～GDK（α1，α2，…，αK；β1，β2，…，βK）。令隨機向量y＝（y1，y2，…，yk＋1）表示該屬性的k＋1個可能值分別發(fā)生的次數(shù)，yj表示此屬性第j個可能值出現(xiàn)的次數(shù)。如果y｜θ服從多項分配，由于廣義Dirichlet分布也具有共軛性質(zhì)，可知后驗概率分布

θ｜y～GDK（α′1，α′2，…，α′K；β′1，β′2，…，β′K）。如果θm是θ的一個變量，則θm在給定y的條件下，期望值為

其中，j＝1，2，…，k，m＝1，2，…，k。

由式（8）和式（9）可知，在給定類別值下，除了估計某屬性的最后一個可能值的發(fā)生概率使用式（9）之外，估算其他可能值的發(fā)生概率都可采用式（8）計算。最后再利用式（3）找出具有最大后驗概率的類別值，作為此項樣本數(shù)據(jù)的預估類別值。

調(diào)整步驟如下：

（1）將所有屬性的參數(shù)值設定為Laplace Estimator后由SNB算法挑選出m個屬性；

（2）針對第一個屬性的首個參數(shù)α1計算在［1，60］之間整數(shù)的分類準確率，挑選使分類準確率最高的參數(shù)值為，表示第一個屬性的最優(yōu)參數(shù)值；

（3）假設α1＝，針對α2計算在［1，60］之間整數(shù)的分類準確率，選擇使分類準確率最高的參數(shù)值設定為，用同樣的方法找出，并通過式（4）計算相應的βi；

（4）針對SNB挑選的第二個屬性，以步驟1～2的方式調(diào)整其參數(shù)，并采用相同的方式找出第3～m個屬性的最優(yōu)參數(shù)值。

4 實驗驗證

4.1 模式評估

［9］，整理得出以下兩個指標。

（1）分類準確率：采用K-fold交互認證，將樣本數(shù)據(jù)中的數(shù)據(jù)分成K個集合，一個集合稱為一個fold。當其中一個fold作為測試的集合時，其他K-1個fold結合成一個訓練數(shù)據(jù)，之后重復進行K次，直到K個fold都作為測試的集合，最后取K次分類準確率的平均值作為指標。

（2）屬性個數(shù)：比較選擇的屬性和通過屬性選擇法減少的屬性個數(shù)，如果只需少量屬性即可獲得良好的分類準確率，表示該屬性選擇法確實能有效地過濾冗余屬性。

4.2 實例驗證

本節(jié)針對UCI［10］上的10個樣本數(shù)據(jù)集合進行計算并評估其性能。

表1為樣本數(shù)據(jù)集合的相關屬性。將K-fold交互式認證法的K值設定為5，使得樣本數(shù)據(jù)集合最小的tae集合在每個fold平均有30項，因此不會因為測試項數(shù)量過小導致結果無統(tǒng)計意義。另外，如果樣本數(shù)據(jù)集合中某些屬性出現(xiàn)遺漏值則忽略，只使用其他沒有遺漏值的屬性作運算。由于NBC無法直接使用連續(xù)型屬性，應將數(shù)據(jù)離散化。在離散化的方法中，ten-bin是將連續(xù)型屬性分成10個等區(qū)間，并按照屬性值大小放入這10個區(qū)間，即變成有10個可能值的離散屬性。本文選用的資料文件包含連續(xù)屬性和離散屬性，樣本數(shù)量從151～8 124不等，目的就是研究本文提出的方法在各種情況下的分類準確率，得出較為客觀的結論。

表1 實驗樣本數(shù)據(jù)屬性及屬性選擇結果Table 1 List of sample attributes and selected results

4.3 測試結果及分析

表2列出各模式下選擇的屬性群及個數(shù)，其中NBC表示樸素貝葉斯分類器使用的屬性個數(shù)，即所有屬性個數(shù)，SNB表示本文方法使用的屬性個數(shù)。

表2 屬性選擇結果Table 2 List of attribute selection results

表3為所有樣本數(shù)據(jù)集合在各模式下的分類準確率，其中的粗體數(shù)值表示各樣本數(shù)據(jù)集合最高的分類準確率。NBC表示樸素貝葉斯分類器，使用Laplace Estimator。SNB表示使用SNB選出的屬性做預測的分類準確率，使用Laplace Estimator。MD表示先驗分布為Dirichlet分布，調(diào)整出最優(yōu)參數(shù)的分類準確率。MG表示先驗分布為廣義Dirichlet分布，調(diào)整最優(yōu)參數(shù)的分類準確率。分類效果如圖2所示。

表3 分類準確率匯總表Table 3 List of classification accuracy

圖2 分類結果對比圖

分析以上結果可知，在各個樣本數(shù)據(jù)集合中，SNB的準確率要優(yōu)于NBC。例如Parkinsons數(shù)據(jù)集，NBC使用22個屬性的分類準確率為73.91％，而SNB篩選出3個屬性的準確率為87.23％，效率提升13.32％。這說明在實際樣本數(shù)據(jù)集合中并非每個屬性都具有分類價值，屬性間也不完全服從條件獨立的假設，以上兩點都會影響NBC的分類準確率。

SNB算法篩選出的屬性數(shù)量與原始屬性數(shù)量無關，這說明分類準確率不再提升時SNB算法即終止，因此選擇的屬性數(shù)量只與各階段已選入的屬性群計算的分類準確率有關，與原始屬性無關。

當先驗分布服從廣義Dirichlet分布時，準確率在多數(shù)樣本數(shù)據(jù)集合中最高。一般而言，廣義Dirichlet分布比Dirichlet分布更能提升NBC的準確率，但受樣本數(shù)據(jù)集合內(nèi)噪聲的影響，有可能使得服從Dirichlet分布時準確率更高。本文研究的屬性集合經(jīng)過SNB算法選擇，可基本濾除干擾屬性的影響，在這樣的屬性集合下可使廣義Dirichlet充分發(fā)揮其效用。

5 小結

本文運用SNB算法對樣本數(shù)據(jù)集合進行屬性選擇，在屬性選擇的過程中針對已選出的屬性，分析各個屬性的特點加入最適合該屬性的先驗分布后再做選擇，并根據(jù)選擇過程中的分類準確率調(diào)整先驗分布的參數(shù)，最終產(chǎn)生的一組具有適合先驗分布的屬性集合以提高分類準確率。仿真實驗結果表明該方法可在保證分類效率的前提下提高分類準確率。在分析SNB算法的分類結果時，發(fā)現(xiàn)準確率不再上升即停止選擇的準則過于嚴格，即使目前的準確率下降，繼續(xù)選擇若干個屬性后仍有可能進一步提高分類準確率。在下一步研究中考慮設置一個緩沖區(qū)間，當準確率下降在某個范圍內(nèi)時仍可以進行選擇。這樣可避免由于選擇屬性過少對分類準確率的影響，使得分類效果得到進一步的改善。

參考文獻：

［1］Friedman N，Geiger D，GoldszmidtM.Bayesian network classifiiers［J］.Machine Learning，1997，29（2/3）：131－163.

［2］Zheng Zijian，Webb G I，Ting Kaiming.Bayesina rules：A lazy semi－semi－Na?ve Baesian learning technique competitive to boosting decision trees［C］//Proceeding of the 16th International Conference on Machine Learning.Bled，USA：IEEE，1999：493－502.

［3］Webb G I，JPazzaniM J.Adjusted probability na?ve Bayesian induction［C］//Proceeding of the 11th Australian jiont Conference on Artificial Intelligence.Adelaide，Australia：IEEE，1998：285－295.

［4］Ioan Pop.An approach of the naive Bayesian classifier for the document classification［J］.General Mathematics，2006，14（4）：135－138.

［5］Langley P，Sage S，Induction of selective bayesian classifiers［C］//Proceedings of UAI-94 10th International Conference on Uncertainty in Artificial Intelligence.Seattle，WA：IEEE，1994：399－406.

［6］John G H，Kohavi R，Pfleger K.Irrelevant features and the subset selection problem［C］//Proceedings of the 11th International Conference on Machine Learning.New Brunswick，NJ：IEEE，1994：121－129.

［7］Kim Chanju，Hwang Kyu-Baek.Naive Bayes classifier learningwith feature selection for spam detection in social bookmarking［C］//Proceeding of Europe Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases.Antwerp，Belgium：IEEE，2008：184－198.

［8］余芳，姜云飛.一種基于樸素貝葉斯分類的特征選擇方法［J］.中山大學學報（自然科學版），2004，43（5）：118－120.YU Fang，JIANG Yun-fei.Selection method based on the characteristics of the naive Bayesian classifier［J］.Zhongshan University University（Natural Science Edition），2004，43（5）：118－120.（in Chinese）

［9］秦鋒，任詩流，程澤凱，等.基于屬性加權的樸素貝葉斯分類算法［J］.計算機工程與應用，2008，44（6）：107－109.QIN Feng，RENShi-liu，CHENGZe-kai，etal.Naive Bayes classification algorithm based on attribute weighting［J］.Computer Engineering and Applications，2008，44（6）：107－109.（in Chinese）

［10］Frank A，Asuncion A.UCIMachine Learning Repository［EB/OL］.（2010）［2012－07－15］.http：//archive.ics.uci.edu/ml.

焦鵬（1980—），男，陜西西安人，2009年獲碩士學位，現(xiàn)為博士研究生，主要從事智能信息處理、復雜設備故障預測及診斷研究；

JIAO Peng was born in Xi′an，Shaanxi Province，in 1980.He received the M.S.degree in 2009.He is currently working toward the Ph.D.degree.His research concerns intelligent information processing and prognosticsand diagnosisof complex equipment.

Email：Jiaopeng－NEAU＠hotmail.com

王新政（1949—），男，陜西漢中人，海軍航空工程學院教授、博士生導師，主要從事信息對抗技術、智能設備檢測研究；

WANG Xin-zheng was born in Hanzhong，Shaanxi Province，in 1949.He isnow a professor and also the Ph.D.supervisor.His research concerns information warfare and intelligent test technology.

謝鵬遠（1980—），男，陜西安康人，2009年獲碩士學位，現(xiàn)為工程師，主要研究方向為智能信息處理及電子對抗。

XIE Peng-yuan was born in Ankang，Shaanxi Province，in 1980.He received the M.S.degree in 2009.He is now an engineer.His research interests include intelligent information processing and electronic countermeasures.

Performance Improvement of Naive Bayesian Classifier Based on Feature Selection

JIAO Peng1，WANG Xin-zheng1，XIE Peng-yuan2
（1.Naval Aeronautical Engineering University，Yantai264001，China；2.Uint91055 of PLA，Taizhou 318050，China）

In order to improve the accuracy of the naive Bayesian classifier（NBC），the selective naive Bayesian（SNB）method and the attributes′prior distribution are studied.Amethod for combining prior distribution and feature selection together is proposed，which finds out the best prior for each attribute after all attributes have been determined by the SNB algorithm.The experimental result on 10 data sets form UCIdata repository shows that thismethod with the general Dirichletprior generally achieves higher classification accuracy，such as the the efficiency of the data sets of Parkinson's can be enhanced by 13.32％.

naive Bayesian classifier；prior distribution；feature selection algorithm；generalized Dirichlet distribution

TP181

A

1001－893X（2013）03－0329－06

10.3969/j.issn.1001－893x.2013.03.020

2012－08－02；

2012－11－12 Received date：2012－08－02；Revised date：2012－11－12

??通訊作者：Jiaopeng－NEAU＠hotmail.com Corresponding author：Jiaopeng－NEAU＠hotmail.com