基于互信息與層次聚類雙重特征選擇的改進樸素貝葉斯算法

李欣倩，楊 哲，任 佳

(浙江理工大學 機械與自動控制學院，浙江 杭州 310018)

樸素貝葉斯(Naive Bayes)[1-2]結構簡單、運算效率高，具有數學理論支撐，因此常用于解決二分類及多分類問題。在實際場景中，由于存在不確定因素，特征獨立性假設往往難以達成，因此樸素貝葉斯算法雖然容易實現，卻犧牲了部分分類性能。所以，研究人員從不同角度對算法進行了相應的改進。

一些學者從結構擴展的角度出發，提出了改進樸素貝葉斯算法結構的想法，不再視所有特征之間都相互獨立，而是針對具體問題去尋找特征之間的相關性或部分相關性。Friedman等[3]提出了Tan模型，每個特征屬性在類別變量的基礎上，能夠選擇一個其他特征進行關聯，其結構與樹狀圖相似，又稱樹擴展樸素貝葉斯。

基于屬性加權對樸素貝葉斯算法進行改進則提供了另一種思路，其賦予每個屬性一個權值，權值的大小可由不同的方法確定，相較于前一種改進方法，該方法可以有效保留樸素貝葉斯算法原來的結構。Zhang等[4]提出了一種加權樸素貝葉斯算法，給出了Markov Monte Carlo法、爬山法、信息增益法以及相應的組合方法等5種選擇屬性的權值方法。魏會建[5]在結合粗糙集理論和信息論的基礎上，提出了一種基于屬性約簡和屬性加權的樸素貝葉斯算法，該方法能約簡冗余屬性，同時計算約簡后的各條件屬性相對于決策屬性的權重，并融入到樸素貝葉斯算法中，從而達到改善算法應用場景和提高分類精確度的目的。

此外，一些學者從特征選擇的角度出發進行改進研究，在原始數據集中刪除無關或冗余的特征，用篩選后的特征子集進行算法的訓練。特征選擇是一種數據降維方法，其主要目的是在提高模型準確率或不降低準確率的前提下，盡可能地減少特征。常用的方法有Filter、Wrapper和Embedded。Filter方法使用某種距離或相似性度量準則計算特征和類別的相關性大小并進行排序，根據排序選擇值最高的特征。Wrapper方法考慮了后續學習器的性能，并將其作為評價指標。相較于前者，其計算量雖有增大，但能獲得更小、更優的特征子集。Embedded方法為一種嵌入式的特征選擇方法，將特征選擇嵌入于整個算法中，如ID3、C4.5、CART等一系列樹類算法。為了改善使用信息增益進行屬性選擇時需要設定閾值的問題，Abellan和Castellano[6]提出了一種基于最大熵的快速屬性選擇方法，該方法使用不精確概率和最大熵準則來選擇最具信息量的屬性，且無須設定閾值。

最后，局部學習也是改進樸素貝葉斯算法的方法，通過改變訓練數據的數量來改變模型的構造過程，使部分數據能滿足特征獨立性的要求。該方法在訓練階段選取一部分數據來構造分類器，這樣可以有效降低整個數據集對特征屬性獨立性假設的限制。Frank等[7]提出了一種局部加權貝葉斯算法，通過學習局部模型來放寬獨立性假設，對比其他的樸素貝葉斯算法，該方法計算簡單，能夠有效提高分類性能。

為了降低特征子集規模和提升分類性能，筆者提出了一種基于互信息與層次聚類雙重特征選擇的改進樸素貝葉斯算法。通過互信息方法剔除不相關特征，利用歐氏距離對特征進行層次聚類，之后從每個簇中選擇信息量最大的特征并用粒子群優化(Particle Swarm Optimization,PSO)算法優化聚類簇的個數。在計算特征子集的先驗概率和后驗概率后，根據樸素貝葉斯算法得到特征所屬類別。結果表明，該方法不僅能放寬特征屬性獨立性的假設，同時能提高分類的精準度。

1 樸素貝葉斯

樸素貝葉斯算法[1-2]為一種基于概率統計的分類方法，常作為文本分類的評估標準[8]。該算法在得到樣本數據的先驗概率與條件概率后，可根據貝葉斯公式求得后驗概率，即樣本對應不同類別的概率。后驗概率最大的類別即為算法對應的樣本預測類別，其中貝葉斯公式為

(1)

P(Y=cm)

(2)

P(X(1)=x(1),…,X(n)=x(n)|Y=cm)

(3)

(4)

該假設是指在輸出類別確定的情況下，特征之間相互獨立。該假設雖然存在降低算法分類準確率的情況，但是它能夠簡化模型、提高算法的可實現性。此時，模型計算公式為

(5)

因式(5)的分母對輸出類別并無影響，故該算法僅需最大化式(5)的分子，即可確定樣本所屬類別，即

(6)

2 基于互信息與層次聚類雙重特征選擇的改進樸素貝葉斯算法

2.1 互信息

互信息(Mutual Information)[9]是一種度量信息量的方法，在給定隨機變量X和Y后，互信息可以用于確定X中所含Y的信息量，或在X已知時Y所減少的不確定性。當X和Y均為離散的情況時，X的邊緣分布為p(x)，Y的邊緣分布為p(y)，兩者之間的聯合概率分布為p(x,y)。此時，X和Y之間的互信息為

(7)

當變量X和Y互信息為0時，表示X與Y相互獨立，兩者沒有任何相關性。對比皮爾遜相關系數[10]，互信息系數衡量相關性的范圍更廣。所以，選擇互信息來度量特征與類別之間的相關性強度?；バ畔⒅翟酱螅硎驹撎卣髋c類別之間的相關性越強，即包含的信息量越多。

2.2 基于歐氏層次聚類與互信息雙重特征選擇的改進樸素貝葉斯算法

層次聚類[11]，即樹聚類，是一種高效的聚類算法[12]。層次聚類法根據簇與簇之間的相似度或者距離度量方式(如最大距離、歐氏距離、馬哈拉比諾比斯距離)，構建一棵由簇與子簇組成的聚類樹。重復此操作，并在符合停止條件時結束，如聚集到所設置的簇的個數。層次聚類算法包括凝聚法[13](Agglomerative)和分裂法[14](Divisive)，如圖1所示。

圖1 層次聚類法示意圖

在圖1中，從左向右為凝聚法，該方法為一種由下而上的聚類方式，選定相似性或距離度量準則，將每個對象看作一個單獨的簇,合并符合準則的簇，在滿足停止條件或所有的簇聚為一類時合并結束。從右向左看即為分裂法，該方法在初始階段將所有的對象處于同一簇中，再根據所選的度量準則，迭代分裂，符合停止條件或所有對象自成一簇時，結束分裂。

2.3 基于雙重特征選擇的改進樸素貝葉斯算法

樸素貝葉斯算法的假設在實際分類問題中較為嚴格且不易滿足，所以將互信息與凝聚分層聚類方法結合，提出一種特征選擇改進算法(MIHC_NB)，以便在采用樸素貝葉斯算法進行分類時，盡可能滿足所需的假設條件，提升算法分類性能。MIHC_NB算法的框圖和偽代碼見圖2、表1。

表1 MIHC_NB算法偽代碼

圖2 MIHC_NB算法框圖

① 基于互信息算法的第一重特征選擇。根據式(7)，得到所有特征對應不同類別的值，其中包含部分互信息值為0的特征。該部分特征不僅對算法性能的提升毫無幫助，而且還會增加模型的計算成本，因此剔除該部分特征。

② 基于凝聚層次聚類法的特征之間第二重特征選擇。首先將每個特征(列向量)作為聚類對象進行轉置，再根據歐氏距離，由下向上，將特征聚集成類。此處選用3種方式實現簇的合并，即最小離差平方和法(Ward-Linkage)、最遠點法(Complete-Linkage)和平均距離法(Average-Linkage)。最小離差平方法首先計算兩簇中所有對象距離兩簇中心點的和，再合并距離最小的兩個簇；最遠點法則是合并最遠點距離最小的兩個簇；平均距離法在計算簇與簇之間所有對象距離的平均值后，合并值最小的兩個簇。將特征聚集成簇的數量設置為Q，達到該設置時，迭代結束。

③ 計算Q個簇中所有特征和輸出類別之間的互信息值，并將每個簇中數值最大的特征添加到所選的特征子集中，即所選的特征數量與聚類簇的個數Q相同。

④ 拆分數據集。采用留一交叉驗證法評估特征子集的分類性能。每次取單個樣本進行測試，將其他的樣本用于訓練。重復多次，直到所有樣本經過測試后，使用平均值來衡量算法的分類準確率。該驗證法能夠降低個別噪聲點造成的偏差影響，提高算法的魯棒性。

⑤ 建立樸素貝葉斯算法的模型。根據式(1)～式(6)，依據上述步驟中得到的特征子集，建立樸素貝葉斯算法的模型。

⑥ 采用粒子群算法優化凝聚層次聚類法中簇的數量Q。因凝聚層次聚類法中簇的個數將直接影響所選特征的數量，所以本文選用粒子群算法[15]自動優化簇的選取數目Q，取值為[1,G]，以最優準確率Accuracymax作為優化目標。G為剔除步驟①中互信息為0的特征后余下的特征數量。在迭代次數達到Stepmax= 5000后，結束尋優過程，得到最優準確率Accuracymax及對應的最小特征數Featuremin。

3 實驗結果與分析

3.1 數據集與實驗環境

由表2可知，不同于傳統數據集，醫學數據集具有較多的特征，因此測試采用了6組高維醫學數據集。表2中所用數據集能在www.gems-system.org.和ligarto.org/rdiaz/Papers/rfVS/randomForestVarSel.html上得到。前4個數據集均為二元分類問題，類別取值為0或1，用于檢測是否患病。而后2組數據集則是多元類別，用來判別患者患病的程度(處于第幾期)。在6組數據中，Prostate數據集所含樣本數(102)和特征數(6033)最多。

表2 實驗數據

本實驗的測試平臺為Windows 10，算法實現為Python 3.6。

3.2 算法驗證與分析

分層聚類算法由3種不同的歐式距離準則得到，因此本實驗所用的雙層特征選擇算法有3種，即MIHC_NB-ward(基于互信息和最小離差平方和的分層聚類的樸素貝葉斯算法)、MIHC_NB-complete(基于互信息和最遠點的分層聚類的樸素貝葉斯算法)和MIHC_NB-average(基于互信息和平均距離的分層聚類的樸素貝葉斯算法)。對比算法為MI ranking(基于互信息排序特征選擇算法)，采用樸素貝葉斯算法衡量分類準確率，測試結果由留一交叉驗證法得到。本實驗與對比實驗的最優準確率和最小特征數目如表3所示。

表3 實驗算法在測試集上所得的分類性能對比

采用最大信息系數(Maximal Information Coefficient,MIC)[16]進一步驗證本方法的性能。MIC與互信息[9]、皮爾遜相關系數[10]相同，也是一種度量特征間關聯程度的方法，該方法在線性、非線性相關的情況中均適用。MIC將所得的互信息值進行了網格歸一化處理，使互信息值分布于[0,1]范圍內，能夠增強相關性的可觀程度。MIC數值越大，相關性就越強。通過MIC求得所選特征子集中兩兩特征間的相關性強度，并將結果相加后取均值。4種算法所得結果如表4所示。

表4 實驗所得特征子集的平均MIC系數

由表4可知，在DLBCL和Colon數據集上，所提出的3種算法所得的MIC值均低于MI ranking算法，尤其是MIHC_NB-average算法得到的MIC值最小。該結果表明，改進算法不僅可以提高分類性能，而且能夠有效減小特征的相關強度。雖然4種算法在Leukemia數據集上的分類性能相同，但提出的算法能夠減小MIC值，尤其是MIHC_NB-average算法的MIC值相較于MI ranking算法降低了0.1807。在Prostate數據集上，改進算法同樣可以達到減小特征間相關性的效果。在Glioma數據集上，3種算法的MIC值均低于MI ranking，且MIHC_NB-complete算法在3種評估方式中均取得最優的結果。在Lung-discrete數據集上，實驗所得準確率雖然相同，但是3種改進算法均在一定程度上降低了相關性，尤其是MIHC_NB-average算法的MIC值僅為0.0765。最后，根據表4中數據及上述分析結果可知，MIHC_NB-average算法在除Glioma數據集外的5個數據集上特征間的相關性均為最低，為4種算法中最接近樸素貝葉斯算法假設的方法。由于特征與類別間的相關性也是影響算法分類性能的一個重要原因，所以單一的簇間聚類準則不一定會得到信息量最高的特征子集。所以對于不同數據集，選用的簇間聚類準則不同并采用粒子群算法優化聚類簇個數。

上述表3與表4中數據表明，采用基于互信息與層次聚類雙重特征選擇方法后可以明顯降低特征之間的相關性，可見該方法作為樸素貝葉斯算法的前置算法，確實能夠最大限度地滿足其特征屬性獨立性假設，從而有效提高該算法的預測準確率。

4 結論與工作展望

為了進一步放寬樸素貝葉斯的假設，提出了一種基于互信息與層次聚類雙重特征選擇的改進樸素貝葉斯算法。該算法根據互信息方法剔除不相關特征，再利用凝聚層次聚類法將相關性強的特征進行聚類，最后將每簇之中互信息值最大的特征合并為最終的特征子集，盡可能地消除特征間的相關性。實驗結果表明，所提出的算法可以減少特征間的相關性強度，并且優化特征選取、提升分類性能。同時，更快地確定聚類簇的個數、加快優化算法的速度是下一步的主要研究內容。