基于粒子群優(yōu)化的樸素貝葉斯改進(jìn)算法

邱寧佳,李 娜,胡小娟,王 鵬,孫爽滋

(長春理工大學(xué) 計算機(jī)科學(xué)技術(shù)學(xué)院,長春 130022)

0 概述

樸素貝葉斯(Native Bayes,NB)算法是一種簡潔而高效的分類算法,在很多情況下達(dá)到的分類效果可以與一些復(fù)雜分類算法相媲美。但其以假設(shè)條件屬性變量之間相互獨(dú)立為前提,而在現(xiàn)實(shí)應(yīng)用中,事務(wù)的各屬性之間大都有著一定的聯(lián)系。因此,樸素貝葉斯算法的這種理想式假設(shè)是不合理的,這也使得分類性能受到很大的影響。為解決該問題,相關(guān)學(xué)者提出了不同的方法來彌補(bǔ)樸素貝葉斯分類器的不足之處,提高其分類精度。

文獻(xiàn)[1]以Hall所提出的加權(quán)方法為目標(biāo)函數(shù),采用差分進(jìn)化算法取得屬性的最優(yōu)權(quán)值,建立樸素貝葉斯加權(quán)模型,使其準(zhǔn)確性有所提高。文獻(xiàn)[2]提出一種局部加權(quán)方法,為經(jīng)典NB模型中的每個屬性分配權(quán)重,并使用基于對數(shù)的簡單假設(shè)將其轉(zhuǎn)換成線性形式,利用最小二乘法確定方程中的最優(yōu)權(quán)向量,以該權(quán)向量建立加權(quán)模型,使算法的復(fù)雜度有所簡化。文獻(xiàn)[3]提出一種局部加權(quán)的學(xué)習(xí)方法來削弱樸素貝葉斯分類器的條件獨(dú)立性假設(shè),使算法的分類性能明顯提高。文獻(xiàn)[4]采用最優(yōu)帶寬選擇來估計類條件概率密度函數(shù)的方法降低特征間的依賴性,實(shí)驗(yàn)結(jié)果表明,當(dāng)特征之間存在依賴時該模型明顯優(yōu)于傳統(tǒng)模型。文獻(xiàn)[5]采用基于準(zhǔn)割線法的局部優(yōu)化方法確定目標(biāo)函數(shù)中的最優(yōu)權(quán)值,使模型的分類精度明顯優(yōu)于原有NB分類模型。文獻(xiàn)[6]采用粗糙集對數(shù)據(jù)集進(jìn)行屬性約簡,使用對數(shù)條件似然估計法對條件屬性求取全局最優(yōu)權(quán)值,明顯提高使算法的性能。文獻(xiàn)[7]首先采用無標(biāo)簽訓(xùn)練集求得置信度比較高的樣本,再結(jié)合有標(biāo)簽訓(xùn)練樣本不斷迭代,使傳統(tǒng)的半監(jiān)督樸素貝葉斯算法的性能明顯提高。文獻(xiàn)[8]利用主成分分析法提取獨(dú)立屬性的性質(zhì),構(gòu)造新的屬性,達(dá)到提高分類效果的目的。文獻(xiàn)[9]采用最小二乘法確定目標(biāo)函數(shù),以FOA算法優(yōu)化權(quán)值,明顯提高分類器的性能。文獻(xiàn)[10]利用支持向量機(jī)構(gòu)造一個最優(yōu)分類超平面降低樣本空間規(guī)模,并使用樸素貝葉斯算法訓(xùn)練樣本集生成分類模型。上述樸素貝葉斯模型均在不同程度上提高了樸素貝葉斯算法的分類性能,然而這些研究存在沒有屬性約簡、權(quán)值優(yōu)化以及設(shè)定初始權(quán)值的問題。

上述方法在一定程度上降低了算法分類性能,本文針對其存在的問題,提出一種改進(jìn)的PSO-NB算法。通過引入權(quán)重因子、類內(nèi)和類間離散因子對互信息進(jìn)行改進(jìn),以改進(jìn)的互信息方法進(jìn)行屬性約簡,獲得彼此相對獨(dú)立的核心屬性,將屬性的詞頻比率作為其初始權(quán)值,利用PSO算法迭代求得最終的特征權(quán)向量生成分類器,以提高算法分類性能。

1 文本預(yù)處理

在文本分類中,特征選擇方法能從高維的特征空間中選取對分類有效的特征,降低特征的冗余,提高分類準(zhǔn)確度。文獻(xiàn)[11]對特征選擇的各個方法進(jìn)行了簡述。互信息算法是文本分類中常用的特征選擇方法之一,但其在理論以及現(xiàn)實(shí)應(yīng)用中分類精確度較低。文獻(xiàn)[12]采用一種綜合考慮相關(guān)度和冗余度的特征選擇標(biāo)準(zhǔn)UmRMR來評價特征重要性的方法,提出一種基于互信息的無監(jiān)督特征選擇方法使模型的性能有所提高。文獻(xiàn)[13]分別從特征項(xiàng)在類內(nèi)出現(xiàn)的頻數(shù)、類內(nèi)分布等方面對傳統(tǒng)互信息算法的參數(shù)進(jìn)行了修正,提高了算法的分類精度。文獻(xiàn)[14]結(jié)合功能特征互信息和特征類互信息,提出了一種基于互信息的貪心特征選擇方法以找到最佳的特征子集,提高分類精確度。文獻(xiàn)[15]采用歸一化互信息代替對稱不確定性作為FCBF算法的相關(guān)性評價標(biāo)準(zhǔn),并進(jìn)行相關(guān)性分析以獲得最優(yōu)特征子集,提高了平均分類正確率。本文基于上述互信息理論,提出一種改進(jìn)的特征評價函數(shù),減少冗余屬性,提高分類精確度。

1.1 改進(jìn)的互信息算法

傳統(tǒng)的互信息算法按照特征詞和類別一起出現(xiàn)的概率來衡量特征詞與類別的相關(guān)性,特征詞t和類別ci的互信息公式如下:

(1)

其中,p(t,ci)表示在訓(xùn)練集中類別為ci且包含特征詞t的文本的概率,p(t)表示在訓(xùn)練集中包含特征t的文本的概率,p(ci)表示訓(xùn)練集中屬于類別ci的文本的概率。

由于計算各個概率時使用的頻數(shù)都是包含特征詞的文本數(shù)量,因此并沒有考慮到特征詞在各個文本中出現(xiàn)的詞頻因素。

當(dāng)類別cq中包含特征詞ti和tj的文本數(shù)目一致,并且2個特征詞在其他類別中都甚少出現(xiàn),那么由MI公式計算出的2個特征詞與類別之間的互信息值基本接近。

然而,當(dāng)文本中包含的特征詞ti的頻數(shù)遠(yuǎn)大于tj時(如特征詞ti在文本出現(xiàn)的平均頻數(shù)為10,而特征詞tj在文本中出現(xiàn)的頻數(shù)為1,顯然,特征詞ti更具有代表性,分類能力也越好),利用MI公式計算的互信息值仍相近。因此,可以得出特征在某類別各個文本中出現(xiàn)的頻數(shù)是體現(xiàn)特征詞分類能力的重要因素,本文根據(jù)這個因素提出了權(quán)重因子、類間和類內(nèi)離散因子3個定義,具體的描述如下所示。

定義1設(shè)特征集T={t1,t2,…,tm},訓(xùn)練集類別集C={c1,c2,…,cn},記fij為特征詞tj在類別ci出現(xiàn)的總頻數(shù),Fj為特征詞tj在訓(xùn)練集中出現(xiàn)的總頻數(shù)。特征tj在類別ci中的權(quán)重因子定義如下:

(2)

一個特征詞的權(quán)重因子就是該特征詞在某一類別中出現(xiàn)的頻率。特征的權(quán)重因子越大,分類性能就越強(qiáng)。在互信息公式中引入權(quán)重因子,削弱互信息對低詞頻的倚重,增強(qiáng)高詞頻屬性的影響力,提高分類準(zhǔn)確性。

(3)

一個特征詞的類間離散因子能夠量化該特征詞在各個類間的差異分布狀況。類間分布差異越大,特征詞就越具有類別代表性,其分類性能也就越強(qiáng)。將類間離散因子引入互信息公式,就能剔除在各個類中出現(xiàn)頻率相當(dāng)?shù)摹]有分類能力的冗余屬性,進(jìn)而降低計算復(fù)雜度,提高分類精確度。

(4)

一個特征詞的類內(nèi)離散因子能夠量化該特征在某一個類中的差異分布狀況。類內(nèi)差異分布越小,特征詞就越有類別代表性,分類性能也就越好。將類內(nèi)離散因子引入互信息方法中,就能夠篩選出在某一類別各個文檔中均勻出現(xiàn)的特征詞,提高分類性能。

1.2 改進(jìn)的CDMI特征評價函數(shù)

本文針對互信息方法中對低頻詞的倚重,導(dǎo)致冗余屬性成為特征詞,而有用的條件屬性會漏選等不足,引入上文所定義的權(quán)重因子、類間離散因子和類內(nèi)離散因子,提出一種改進(jìn)的CDMI特征選擇算法,其公式如下:

(5)

其中,t為特征詞,訓(xùn)練集類別集C={c1,c2,…,cn},α表示特征t的類間離散因子,βi表示特征t在ci類內(nèi)的類內(nèi)離散因子,ωi表示特征t的權(quán)重因子,p(t)表示訓(xùn)練集中包含特征t的文檔數(shù)和總文檔數(shù)的比值,p(t|ci)是訓(xùn)練文本集中含有特征t的ci類文檔數(shù)與ci類文檔數(shù)的比值。使用CDMI算法進(jìn)行屬性約簡,獲得彼此相對相互獨(dú)立的核心屬性,為樸素貝葉斯模型分類做準(zhǔn)備。

2 樸素貝葉斯優(yōu)化算法

針對樸素貝葉斯分類器的條件獨(dú)立性假設(shè)在眾多現(xiàn)實(shí)應(yīng)用中并不成立的缺陷,許多的學(xué)者提出可以根據(jù)不同特征詞對分類的重要程度,給予不同的權(quán)值,放大決策屬性的影響,從而將樸素貝葉斯模型擴(kuò)展為樸素貝葉斯加權(quán)模型,如式(6)所示。

(6)

其中,p(ci)表示在現(xiàn)有數(shù)據(jù)集中p(X)類的先驗(yàn)概率,p(X)表示對象X出現(xiàn)的先驗(yàn)概率,p(xj|ci) 表示特征詞xj的條件概率,ωj表示為對應(yīng)于每一個特征值的權(quán)重。

2.1 PSO算法

加權(quán)貝葉斯模型中權(quán)值的選取直接影響分類的效果。為了提高分類的準(zhǔn)確性,本文引入了PSO優(yōu)化算法對初始權(quán)值進(jìn)行全局尋優(yōu),獲取最優(yōu)權(quán)值。

在PSO優(yōu)化算法中依照速度與位置公式來調(diào)整微粒的速度與位置,求得全局最優(yōu)解。由于本文設(shè)定了合適的初始權(quán)值,其大小只需微調(diào),因此在迭代尋優(yōu)中速度不宜過大,以免得不到精確解。為避免這種情況,設(shè)定了最低速度vmin和最高速度vmax,保證其收斂性,改善局部最優(yōu)的狀況。其速度公式和位置公式分別如式(7)、式(8)所示。

vis+1=ωvis+φ1rand()(pbesti-xis)+

φ2rand()(gbesti-xis)

(7)

其中,ω表示慣性因子,φ1和φ2為學(xué)習(xí)因子,vis表示第s次更新時微粒i的速度,xis表示第s次更新時微粒i的位置,rand()為隨機(jī)函數(shù)。

xis+1=vis+1+xis

(8)

其中,vis+1為第s+1次更新時微粒i的速度,xis為第s次更新時微粒i的位置。根據(jù)PSO優(yōu)化算法的思想,可以得出算法1。

算法1PSO優(yōu)化算法

輸入微粒群體的規(guī)模N,迭代次數(shù)max,最高速度vmax,最低速度vmin

輸出最優(yōu)解gbest

初始化位置集合x=(x1,x2,…,xi,…,xN)和速度集合v=(v1,v2,…,vi,…,vN)

for each xi∈x

初始位置xi作為局部最優(yōu)解pbesti

微粒自適應(yīng)度計算fitness(xi)

end for

gbest=min{pbesti}

while max>0

for i=1 to N

更新vi,xi

if fitness(xi)

當(dāng)前位置xi設(shè)為局部最優(yōu)解

if fitness(pbesti)

gbest=pbesti

end for

max=max-1

end while

2.2 PSO-NB算法

為了達(dá)到提高樸素貝葉斯模型的分類準(zhǔn)確性和降低計算復(fù)雜度的目的,本文首先使用改進(jìn)的CDMI算法對屬性進(jìn)行約簡,然后利用PSO優(yōu)化算法對樸素貝葉斯加權(quán)模型中的初始權(quán)值進(jìn)行優(yōu)化,生成分類器。為能清晰地闡述整個算法流程,下面將該算法劃分為CDMI特征選擇算法和PSO-NB分類算法來進(jìn)行具體描述,完整流程如圖1所示。

圖1 PSO-NB算法流程

在特征選擇過程中,針對原有互信息計算中忽略詞頻因素的不足,通過引入權(quán)重因子,放大高詞頻的影響,引入類內(nèi)離散因子和類間離散因子篩選出具有類別代表性的特征詞,具體的算法描述如算法2所示。

算法2CDMI算法

輸入數(shù)據(jù)集,類別集C={c1,c2,…,ci,…,cn}

輸出特征集t′

預(yù)處理得到初始特征集t={t1,t2,…,tj,…},t′=?

for each tj∈t

計算ωij,αj,βij

end for

for each tj∈t

計算CDMI(tj)

if CDMI(tj)>ε

t′=t′∪tj

end for

特征選擇屬性約簡算法的計算復(fù)雜度為O(|t|),|t|為初始特征集的大小。相較于計算復(fù)雜度為O(|t|×loga|t|)的粗糙集約簡算法和計算復(fù)雜度為O(|t|×|t|)的TSVM-NB約簡算法,本文約簡算法計算復(fù)雜度明顯降低。

在分類算法中,首先將各個屬性的詞頻比率作為其初始權(quán)值,然后利用PSO優(yōu)化算法對權(quán)值進(jìn)行優(yōu)化。而在權(quán)值優(yōu)化之前首先要確定目標(biāo)函數(shù),下面就針對目標(biāo)函數(shù)確定的問題進(jìn)行形式化描述。按照樸素貝葉斯算法的思想,假設(shè)有類別C={c1,c2,…,cn},某一樣本X∈c1,那么根據(jù)樸素貝葉斯加權(quán)式(6)計算出的概率越接近于1,其他類別的概率越接近于0,則分類結(jié)果就越精確。因此,根據(jù)確定目標(biāo)函數(shù)的含義,可將p(ci|X)與0或1之間的誤差和記為目標(biāo)函數(shù),記準(zhǔn)確值為γ,測量值為γi,那么具體的公式可描述如下:

(9)

(10)

則目標(biāo)函數(shù)f(ω)可表示為:

(11)

在目標(biāo)函數(shù)確定之后,就可以利用PSO優(yōu)化算法根據(jù)已知的條件對權(quán)值迭代優(yōu)化,每次更新優(yōu)化都要使目標(biāo)函數(shù)更小,直至目標(biāo)函數(shù)收斂。將最優(yōu)權(quán)值作為樸素貝葉斯加權(quán)模型中屬性的權(quán)值,生成分類器,計算測試文本集的分類結(jié)果。

為了在算法3中能簡單清晰的描述,將算法2中提取出的特征集t′記為特征集t,具體的算法描述如算法3所示。

算法3PSO-NB算法

輸入特征集t,類別集C,測試集X,迭代次數(shù)max

輸出類別結(jié)果集classify

初始化權(quán)向量ω=?,結(jié)果集classify=?

for each tj∈t

計算p(ci),p(tj|ci),ωj

ω=ω∪ωj

end for

ω= PSO(ω,max)

for each Xk∈X

best=0

for each ci∈C

ifp(ci|Xk)>best

當(dāng)前概率設(shè)為最大概率best

當(dāng)前類別設(shè)為文本所屬類別classifyk

end for

end for

3 實(shí)驗(yàn)與結(jié)果分析

本文將樸素貝葉斯分類模型的改進(jìn)分為2個部分。第1部分是對特征選擇方法中的互信息方法進(jìn)行改進(jìn),去除冗余特征詞,降低維度,減少算法計算的復(fù)雜度,同時也改善了算法的分類精度,為了驗(yàn)證改進(jìn)前后算法的性能,以分類效果作為標(biāo)準(zhǔn),設(shè)計實(shí)驗(yàn)對其進(jìn)行驗(yàn)證。第2部分是對加權(quán)模型中的權(quán)值進(jìn)行優(yōu)化,其優(yōu)化方法采用PSO優(yōu)化算法,并以優(yōu)化后的權(quán)值作為條件屬性對分類影響的重要程度。為了驗(yàn)證權(quán)值優(yōu)化前后算法的能力,設(shè)計實(shí)驗(yàn)將PSO-NB算法與NB算法以及權(quán)值未優(yōu)化的WNB算法的性能進(jìn)行對比。

本文采用Newsgroups-18828中的10個類別新聞組作為數(shù)據(jù)文本集,對算法進(jìn)行了實(shí)驗(yàn)測評,使用五折交叉驗(yàn)證法,將樣本集隨機(jī)地分割成大小相等但互不相交的5份,并分別進(jìn)行5次樣本訓(xùn)練和驗(yàn)證,計算得出每次分類的召回率與精確率,為了使分類的結(jié)果更具科學(xué)性,防止實(shí)驗(yàn)的隨機(jī)性和偶然性,本文采取5次實(shí)驗(yàn)結(jié)果的平均值作為最終的衡量標(biāo)準(zhǔn)。

3.1 互信息參數(shù)和粒子群參數(shù)的選取

本文引入權(quán)重因子的MI算法為WMI算法,引入類間離散因子和類內(nèi)離散因子的MI算法為CMI算法,然后將改進(jìn)的CDMI算法與WMI算法、CMI算法以及MI算法進(jìn)行實(shí)驗(yàn)對比,確定要篩選的特征詞個數(shù)。下文進(jìn)行的對比主要是在不限定總的單詞個數(shù)情況下,4種算法能達(dá)到的分類結(jié)果的最高精確率,以及在相同的單詞個數(shù)下4種算法的精確率和特征詞個數(shù)。

4種算法最高精確率對比結(jié)果如表1所示。

表1 算法最高精確率對比 %

在相同單詞總數(shù)情況下,4種算法的精確率和特征詞數(shù)對比如圖2、圖3所示。

圖2 4種算法精確率結(jié)果對比

圖3 4種算法特征詞數(shù)結(jié)果對比

從圖2可以看出,在數(shù)據(jù)集的單詞由10 000下降到5 000時,MI特征選擇算法的分類結(jié)果呈急速的下降趨勢;而改進(jìn)后的CDMI算法的分類結(jié)果一直都穩(wěn)定在0.9附近,這就說明了改進(jìn)后的CDMI算法其分類性能比較穩(wěn)定,不會因?yàn)閿?shù)據(jù)集單詞總量的變動而發(fā)生急劇的變化,并且CDMI算法的分類精確度明顯優(yōu)于MI算法。結(jié)合圖2、圖3可以看出,當(dāng)數(shù)據(jù)集單詞數(shù)目相同時,CDMI算法所選取的特征詞數(shù)量明顯少于MI算法,而分類精確度卻明顯優(yōu)于MI算法,這就說明改進(jìn)后的CDMI算法可以降低屬性冗余,篩選出具有高分類能力的核心屬性,這也在一定程度上降低了算法的計算復(fù)雜度。因此,可以得出,CDMI算法無論是在分類性能上面還是計算精度上面都明顯優(yōu)于MI算法。

對于CDMI算法而言,在數(shù)據(jù)集的總單詞數(shù)為7 000時,分類結(jié)果的精確率最高,為了更加直觀地說明這一因素,本文對5次實(shí)驗(yàn)得到的精確率的平均值進(jìn)行了描述,如圖4所示。

圖4 CDMI算法準(zhǔn)確率對比

對于CDMI算法,在數(shù)據(jù)集的總單詞數(shù)變化的過程中,特征詞的數(shù)量變化如表2所示。

表2 特征詞數(shù)量變化情況

由表2可知,在數(shù)據(jù)集的單詞總數(shù)為7 000時,特征詞的個數(shù)為130,本文將特征詞的個數(shù)設(shè)置為130。因此,將PSO-NB算法中粒子的規(guī)模設(shè)為n=130,粒子群其他參數(shù)的選取分別為φ1=2.05,φ2=2.05,ω=0.729,rand()為(0,1)區(qū)間上均勻分布的隨機(jī)數(shù)。

3.2 評價指標(biāo)

為有效地評估PSO-NB模型的分類效果,實(shí)驗(yàn)采用以下3個評價指標(biāo):

1)召回率(R)。指所有類別為正的樣本集有多少被分類器判別為正類別樣本,即召回。將由分類器得到的類別為正的樣本集合記為A,真正的類別為正的樣本集合記為B,則有:

(12)

2)精確率(P)。指分類器判斷其類別為正的樣本集中,真正類別為正的樣本數(shù)有多少。將由分類器得到的類別為正的樣本集合記為A,真正的類別為正的樣本集合記為B,則有:

(13)

3)F-Measure。一個綜合考慮指標(biāo),其綜合考慮了召回率與精確率2個因素。

(14)

3.3 PSO-NB算法驗(yàn)證

為驗(yàn)證本文所提出PSO-NB算法的效果,設(shè)計實(shí)驗(yàn)分別測試使用改進(jìn)互信息的NB、WNB、PSO-NB、文獻(xiàn)[6]提出的NWRNB、文獻(xiàn)[9]提出的FOA-NB以及文獻(xiàn)[10]提出的TSVM-NB這6種不同的算法,為避免實(shí)驗(yàn)的隨機(jī)性和偶然性,選取互不相交的5個測試集進(jìn)行5次實(shí)驗(yàn),取5次結(jié)果的平均值為最終結(jié)果,得到3種分類模型的召回率、精確率以及F-Measure的值,進(jìn)而分析分類器的分類性能,其結(jié)果對比如表3所示。

表3 分類器的分類性能結(jié)果對比

由表3可以看出,PSO-NB算法的召回率和精確率均高于其他5個算法。其中,NWRNB算法和TSVM-NB算法分別使用粗糙集技術(shù)和支持向量機(jī)進(jìn)行了屬性約簡,WNB算法和FOA-NB算法使用不同的加權(quán)方法來評估特征詞的重要程度,以提高分類性能,PSO-NB算法首先使用改進(jìn)的CDMI算法進(jìn)行了屬性約簡,然后將特征詞的詞頻比率作為初始權(quán)值,利用PSO優(yōu)化算法對權(quán)值更新,每次更新都會使目標(biāo)函數(shù)更小,一方面使得權(quán)值更加貼近特征詞的重要程度,因此精確率更高,大大降低了文本類別誤判的概率;另一方面所有特征詞的合適權(quán)值使得文本屬于某一類別的概率更加精確,因此召回率更高。

4 結(jié)束語

為提高樸素貝葉斯算法文本分類準(zhǔn)確率并降低計算復(fù)雜度,本文提出一種改進(jìn)的PSO-NB算法。首先利用改進(jìn)的CDMI方法進(jìn)行屬性約簡,然后以特征詞的詞頻比率作為初始權(quán)值,使用絕對誤差方法確定目標(biāo)函數(shù),設(shè)定速度更新中的最低和最高速度,通過PSO優(yōu)化算法對初始權(quán)值進(jìn)行優(yōu)化,直至目標(biāo)函數(shù)收斂,生成分類器。通過在Newsgroups語料集上的分析結(jié)果表明,該算法具有更高的分類精度以及更低的計算復(fù)雜度。