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

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

0 概述

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

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

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

1 文本預處理

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

1.1 改進的互信息算法

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

(1)

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

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

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

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

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

(2)

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

(3)

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

(4)

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

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

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

(5)

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

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

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

(6)

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

2.1 PSO算法

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

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

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

φ2rand()(gbesti-xis)

(7)

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

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

end for

gbest=min{pbesti}

while max>0

for i=1 to N

更新vi,xi

if fitness(xi)

當前位置xi設為局部最優(yōu)解

if fitness(pbesti)

gbest=pbesti

end for

max=max-1

end while

2.2 PSO-NB算法

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

圖1 PSO-NB算法流程

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

算法2CDMI算法

輸入數(shù)據(jù)集,類別集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優(yōu)化算法對權值進行優(yōu)化。而在權值優(yōu)化之前首先要確定目標函數(shù),下面就針對目標函數(shù)確定的問題進行形式化描述。按照樸素貝葉斯算法的思想,假設有類別C={c1,c2,…,cn},某一樣本X∈c1,那么根據(jù)樸素貝葉斯加權式(6)計算出的概率越接近于1,其他類別的概率越接近于0,則分類結果就越精確。因此,根據(jù)確定目標函數(shù)的含義,可將p(ci|X)與0或1之間的誤差和記為目標函數(shù),記準確值為γ,測量值為γi,那么具體的公式可描述如下:

(9)

(10)

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

(11)

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

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

算法3PSO-NB算法

輸入特征集t,類別集C,測試集X,迭代次數(shù)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部分是對加權模型中的權值進行優(yōu)化,其優(yōu)化方法采用PSO優(yōu)化算法,并以優(yōu)化后的權值作為條件屬性對分類影響的重要程度。為了驗證權值優(yōu)化前后算法的能力,設計實驗將PSO-NB算法與NB算法以及權值未優(yōu)化的WNB算法的性能進行對比。

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

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

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

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

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

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

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

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

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

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

圖4 CDMI算法準確率對比

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

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

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

3.2 評價指標

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

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

(12)

2)精確率(P)。指分類器判斷其類別為正的樣本集中,真正類別為正的樣本數(shù)有多少。將由分類器得到的類別為正的樣本集合記為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優(yōu)化算法對權值更新,每次更新都會使目標函數(shù)更小,一方面使得權值更加貼近特征詞的重要程度,因此精確率更高,大大降低了文本類別誤判的概率;另一方面所有特征詞的合適權值使得文本屬于某一類別的概率更加精確,因此召回率更高。

4 結束語

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