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

李欣倩，楊 哲，任 佳

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

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

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

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

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

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

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

1 樸素貝葉斯

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

(1)

P(Y=cm)

(2)

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

(3)

(4)

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

(5)

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

(6)

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

2.1 互信息

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

(7)

當(dāng)變量X和Y互信息為0時，表示X與Y相互獨立，兩者沒有任何相關(guān)性。對比皮爾遜相關(guān)系數(shù)[10]，互信息系數(shù)衡量相關(guān)性的范圍更廣。所以，選擇互信息來度量特征與類別之間的相關(guān)性強(qiáng)度?；バ畔⒅翟酱?，表示該特征與類別之間的相關(guān)性越強(qiáng)，即包含的信息量越多。

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

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

圖1 層次聚類法示意圖

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

2.3 基于雙重特征選擇的改進(jìn)樸素貝葉斯算法

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

表1 MIHC_NB算法偽代碼

圖2 MIHC_NB算法框圖

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

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

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

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

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

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

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集與實驗環(huán)境

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

表2 實驗數(shù)據(jù)

本實驗的測試平臺為Windows 10，算法實現(xiàn)為Python 3.6。

3.2 算法驗證與分析

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

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

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

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

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

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

4 結(jié)論與工作展望

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