基于粒子群優化的樸素貝葉斯改進算法

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

(長春理工大學 計算機科學技術學院,長春 130022)

0 概述

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

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

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

1 文本預處理

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

1.1 改進的互信息算法

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

(1)

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

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

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

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

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

(2)

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

(3)

一個特征詞的類間離散因子能夠量化該特征詞在各個類間的差異分布狀況。類間分布差異越大,特征詞就越具有類別代表性,其分類性能也就越強。將類間離散因子引入互信息公式,就能剔除在各個類中出現頻率相當的、沒有分類能力的冗余屬性,進而降低計算復雜度,提高分類精確度。

(4)

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

1.2 改進的CDMI特征評價函數

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

(5)

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

2 樸素貝葉斯優化算法

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

(6)

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

2.1 PSO算法

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

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

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

φ2rand()(gbesti-xis)

(7)

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

xis+1=vis+1+xis

(8)

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

算法1PSO優化算法

輸入微粒群體的規模N,迭代次數max,最高速度vmax,最低速度vmin

輸出最優解gbest

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

for each xi∈x

初始位置xi作為局部最優解pbesti

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

end for

gbest=min{pbesti}

while max>0

for i=1 to N

更新vi,xi

if fitness(xi)

當前位置xi設為局部最優解

if fitness(pbesti)

gbest=pbesti

end for

max=max-1

end while

2.2 PSO-NB算法

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

圖1 PSO-NB算法流程

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

算法2CDMI算法

輸入數據集,類別集C={c1,c2,…,ci,…,cn}

輸出特征集t′

預處理得到初始特征集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

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

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

(9)

(10)

則目標函數f(ω)可表示為:

(11)

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

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

算法3PSO-NB算法

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

輸出類別結果集classify

初始化權向量ω=?,結果集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

當前概率設為最大概率best

當前類別設為文本所屬類別classifyk

end for

end for

3 實驗與結果分析

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

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

3.1 互信息參數和粒子群參數的選取

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

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

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

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

圖2 4種算法精確率結果對比

圖3 4種算法特征詞數結果對比

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

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

圖4 CDMI算法準確率對比

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

表2 特征詞數量變化情況

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

3.2 評價指標

為有效地評估PSO-NB模型的分類效果,實驗采用以下3個評價指標:

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

(12)

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

(13)

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

(14)

3.3 PSO-NB算法驗證

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

表3 分類器的分類性能結果對比

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

4 結束語

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