1、第25卷第2期2007年6月廣西師范大學學報:自然科學版Journal of GuangxiN o rm al U niversity:N atural Science Edition V o l .25N o.2Jun.2007收稿日期:2006212215基金項目:重慶市自然科學基金資助項目(CSTC 2006BB 2021作者簡介:張玉芳(1965,女,上海人,重慶大學副教授,碩導。一種改進的貝葉斯文本分類方法張玉芳,陳劍敏,熊忠陽(重慶大學計算機學院,重慶400030摘要:樸素貝葉斯分類(naive Bayes 有一個“獨立性假設”:給定一個實例的類標簽,實例中的每個屬性的出現都獨立于

2、實例中其他屬性的出現,而在實際應用中這種條件并不易滿足,另外由于文本的特殊性,相關的特征項可能會產生新的語義信息。因此在訓練文本時,對特征選擇后產生的特征集用一種可行的方法考察它們之間的相關性,然后對相關程度高的特征進行合并處理。實驗數據表明,這個改進的方法能提高樸素貝葉斯的算法精確度。關鍵詞:文本分類;獨立性假設;相關性中圖分類號:T P 392文獻標識碼:A 文章編號:100126600(2007022*文本分類的目標是在分析文本內容的基礎上給文本分配一個或者多個比較合適的類別,文本分類的過程是對訓練集中文檔的內容進行分析,構造一個分類器,用這些分類器對新文檔分類,對文本分類的研究大大縮小

3、信息檢索的范圍,增強檢索對象與檢索要求的相關性1。目前較為著名的文本分類方法有B ayes 方法、k 2NN 方法、神經網絡方法、決策樹方法、支持向量機算法等,其中樸素貝葉斯方法是目前公認的一種簡單有效的分類方法,它是一種基于概率的分類方法。1樸素貝葉斯分類目前大多數分類方法是基于向量空間模型的2,在該模型中,每個文檔可看作詞的序列,文檔中的詞稱為特征,在經過切分詞、去除停用詞、截取詞干等預處理后得到一個特征集合,還需要進行特征選擇,找出能最好地代表一個文檔或者類別的特征來參與分類計算,這樣文檔表示為由特征組成的特征矢量。1.1樸素貝葉斯分類器及獨立假設貝葉斯文本分類模型是一種典型的基于統計方

4、法的分類模型3,它利用先驗信息和樣本數據信息來確定事件的后驗概率。令論域U =(w 1,w 2,w 3,w n ,C 是離散隨機變量的有限集,其中w 1,w 2,w 3,w n 為特征項集,類變量C 的取值范圍為(c 1,c 2,c 3,c l ,一個文檔d i 表示為特征向量(w 1,w 2,w 3,w n ,則d i 屬于類c j 的概率可表示為:p (c j w 1,w 2,w 3,w n =p (w 1,w 2,w 3,w n c j p (c j p (w 1,w 2,w 3,w n 。(1根據概率的鏈規則:p (w 1,w 2,w 3,w n c j =7n i =1p (w i

5、w 1,w 2,w i -1,c j ,(2樸素貝葉斯分類模型中的屬性獨立假設假定所有的屬性都是相互條件獨立,即有:p (w i w 1,w 2,w i -1,c j =p (w i c j ,(3結合公式(2、(3,公式(1則變為:p (c j w 1,w 2,w 3,w n =7n i =1p (w i c j p (c j p (w 1,w 2,w 3,w n 。(4根據貝葉斯最大后驗準則,給定某一待分類文本d i =(w 1,w 2,w 3,w n ,貝葉斯分類器選擇使后驗概率p (c j w 1,w 2,w 3,w n 最大的類作為該文本的類標簽。樸素貝葉斯的獨立性假設提高了分類的效

6、率,但在實際應用中這種獨立性假設是不太可能滿足的,因此改進樸素貝葉斯文本分類器,使之在獨立性假設不能滿足的情況下具有較高的分類精度和分類效率,是值得研究的領域。Kononenko 的sem i 2naive 分類器4將屬性集分割成若干個不相交的屬性組,假設在不同組中的屬性之間是相互獨立的,而同一屬性組內的各屬性相互關聯,但這樣大大增加學習的開銷,對于特征項眾多的文本分類并不現實。1.2TAN 樹擴展樸素貝葉斯分類方法TAN (tree augm en t naive B ayes 是由F riedm an 等人提出的一種樹狀結構模型5,6,它將貝葉斯網絡的部分表示依賴關系的能力與樸素貝葉斯方法

7、的簡易性結合。在TAN 結構中,類變量C 是根,沒有父結點,特征項要不以類結點作為其父結點,要不以一個其他的特征項作為其父結點,這時這個其他的特征項只能以類結點作為父結點。因此p (w i w 1,w 2,w i -1,c j =p (w i c j (特征項w i 只有類結點作為父結點或者p (w i w 1,w 2,w i -1,c j =p (w i w p ,c j (特征項w i 以一個其他特征項w p 作為父結點,即特征項w i 對分類的影響依賴于特征項w p ,此時w p 只能以類變量作為父結點,w p w 1,w 2,w i -1,TAN 分類模型具有較好的綜合性能,體現了學習

8、效率與分類精度之間的一種適當的折衷。2本文的改進方法相對于樸素貝葉斯,sem i 2naive 分類器和TAN 方法在一定程度上克服了基于屬性獨立性假設的限制,但實現相對復雜并且學習的效率相對樸素貝葉斯方法大幅度下降,對于特征項眾多的文本分類而言計算量是相當巨大的,并且在文本分類中,相關聯的特征項除了存在一定的依賴關系外,他們一起出現還可能產生新的語義信息,因此對分類的性能有一定的影響,所以對相關的特征項進行歸一的計算對最終的分類可能會取到很好的效果。要對相關的特征項進行合并,首先要從特征項集中找出相關程度較高的特征項,對文本分類而言,特征項之間的聯系可能是錯綜復雜的,要衡量多個特征之間的相關

9、程度是不容易實現的。本文從簡易性的思想出發認為:一個特征項最多與一個其他的特征項關聯。先得出相關程度較高的兩兩特征項,然后對這些特征項進行適當的處理來提升貝葉斯方法的性能。為描述兩個特征項之間的相關程度,要給出一種數學方法來度量。準確度量高維的特征相關度是困難的,這樣做不僅問題復雜,而且得出相關的可能性并不可靠。本文用一種簡單可行的方法度量兩個特征項之間的相關程度。互信息7是一種廣泛用于建立詞關聯統計模型的標準,互信息量反映了兩個隨機事件的統計關聯程度,這里借用這個概念來表示兩個特征項間的關聯程度,在類別c j 中兩個特征w i ,w p 之間的互信息計算公式為:I (w i ,w p c j

10、 =log p (w i ,w p c j p (w p c j p (w i c j ,(5其近似計算公式為:I (w i ,w p c j =log A N (A +L (A +K 。(6再考慮兩個特征在該類別的訓練文本集的各個文檔中一起出現的詞頻數,可以采用下面的公式來計算兩個特征項在類別c j 之間的相關性:D (w i ,w p c j H Nlog A N (A +L (A +K ,(7其中N 為類別c j 中的文檔總數,H 為兩個特征項在類別c j 中一起出現的詞頻總數,A 為類別c j 中一起出現的文檔數量,K 為類別c j 中w i 出現w p 不出現的文檔數,L 為類別c

11、j 中w p 出現且w i 不出現的文檔數。若w i 、702第2期張玉芳等:一種改進的貝葉斯文本分類方法w p不相關,p(w i,w p c j=p(w p c jp(w i c j,即A N(A+L(A+K N2,此時D(w i,w p c j0。但在實際應用中,如果對所有D(w i,w p c j0的特征項都要考慮的話,計算量是十分驚人的,另外若所有D(w i,w p c j都是從實際訓練文本集得到,有可能D(w i,w p c j0并不代表兩者一定相關,這樣反而使精度下降。為了解決這個問題,可以采用一個統計上的閾值,當D(w i,w p c jc時,兩個特征項才相關。考察特征項相關性的

12、算法描述如下:B egin對所有的類別c j do;計算所有的特征項(w i,w p在類別c j中的相關性D(w i,w p c j;生成包含所有特征項對(w i,w p的集合S;Fo r(w i,w pSIf m ax(D(w i,w p c jc then在類別c j加入合并的特征項w ip;在S中刪除含有w i或者w p的特征項對;E lse ex itEnd fo rEnd。在得到相關性大的兩兩特征項后,本文采用以下的方法處理取得了較好的效果:在類別c j中如果w i,w p相關,則加入一個新的特征項w ip進行計算,相應地修改w i、w p的詞頻數。例如有一個文檔d i,w i的詞頻

13、數為a,w p的詞頻為b,ab,則計算p(c j d i時,w i的詞頻數為a-b,w p的詞頻為0,特征項w ip的詞頻為b。經過上述處理后,再采用樸素B ayes方法對文本分類,比較新文本屬于所有類的幾率,將文本分到幾率最大的那個類別中。3實驗及結果分析在實驗中采用了宏觀平均F1值和微觀平均F1值來評估分類的性能8。實驗利用在CNL P下載的一個小型語料庫作為測試數據。按照21的原則,把語料庫分為訓練文檔和測試文檔兩個部分。當衡量特征項相關程度的限值c取不同值時,會影響文本分類的效果(圖1,并且c值越小,考察特征的相關性時得出相關的特征項越多,算法的效率越低,從附圖中可以看出c=0.3時性

14、能最好,考慮到效率問題,實驗采用了效果較好的c=0.4。表1實驗結果Tab.1The result of exper i m en t方法宏平均F1值 %微平均F1值 % N aive Bayes方法75.8776.21改進的方法(c=0.477.6978. 01圖1參數c與精確度的關系F ig.1T he relati on of betw een Param eter c andthe p recisi on4結論本文介紹了一種改進的B ayes文本分類方法,它通過統計方法評估出特征項在類之間的相關性,然后802廣西師范大學學報:自然科學版第25卷將相關性高的特征項合并,根據實驗結果(表1

15、可以看出,改進后的方法在分類精度上略優于naive B ayes 方法,由于特征選取后全部特征項都參與了計算,所以訓練的時間很長。下一步將重點考慮如何只選取部分特征來考察相關性,在保證精確度的同時提高算法效率。參考文獻:1Fabrizi o Sebastiani .M ach ine learning in autom ated text catego rizati on J .A C M Computing Curveys ,2002,34(1:11212,32233.2王灝,黃厚寬,田盛豐.文本分類實現技術J .廣西師范大學學報:自然科學版,2003,21(S 1:1732179.3M c

16、CALLUM A ,N IGAM K .A comparison of event models fo r N aive Bayes text retrival J .Info r m ati on P rocessingand M anagem ent ,1998,24(5:5132523.4KONON EN KO I .Sem i 2N aive Bayesian classifiers C P roceedings of European Conference on A rtificial Intelli 2gence .Berlin :Sp ringer 2V erlag ,1991:

17、2062219.5FR IEDM AN N ,GE IGER D ,GOLD SZ M I D T M .Bayesian netw o rk classifiers J .M ach ine L earning ,1997,29(23:1312163.6石洪波,王志海,黃厚寬.一種基于TAN 的文本分類方法J .廣西師范大學學報:自然科學版,2003,21(1:81285.7魯晨光.廣義信息論研究M .合肥:中國科技大學出版社,1993.8YAN G Y i 2m ing .A n evaluati on of statistical app roach to text catego riz

18、ati on J .Info r m ati on R etrieval ,1999,1(12:69290.I m p roved N aive B ayes T ex t C lassificati on A lgo rithmZHANG Y u -fang ,CHEN J i an -m i n ,X I ONG Zhong -yang(Computer A cadem ic ,Chongqing U niversity ,Chongqing 400030,Ch ina Abstract :T here is an “independence hypo thesis ”in B ayesian classifier m ethod :exam p les of the em