文本分類算法中詞語權重計算方法的改進

摘要:在自動文本分類中，TFIDF公式是常用的詞語權重計算公式。該方法簡單易行，但僅僅考慮了特征詞出現的頻率，而忽略了特征詞對區分每個類的貢獻。針對這個不足，該文提出了TFIDF-CHI，來修正各個特征詞的權重，重新調整每個特征詞對各個類別的區分度，并用KNN分類器來驗證其有效性。實驗證明該方法優于原來的TFIDF算法，表明了改進的策略是可行的。

關鍵詞:文本分類;特征權值;TFIDF;TFIDF-CHI

中圖分類號:TP312 文獻標識碼:A文章編號:1009-3044(2009)36-10626-03

Modify the Method of Feature's Weight in Text Classfication

ZHAO Xiao-hua， MA Jian-fen

(Dept. of Computer and Software College， Taiyuan University of Techonology， Taiyuan 030024， China)

Abstract: In auto text classification， TFIDF is often used when the weight of a term is calculated.The method is easy， only considers the frequency of the feature and ignores the feature's contribution to each class. Aiming at this shortage， we put forward the TFIDF-CHI and use it to modify each feature's weight， read just each feature's differentiation to each class. Then the KNN classifier is used to check its validity. The method is better than traditional TFIDF and proves that the TFIDF-CHI method is feasible.

Key words: text classification; feature weight; TFIDF; TFIDF-CHI

現在，政府、工業、商業和其他機構的大部分信息都以文本數據庫的形式電子地存儲，同時電子出版物、各種電子文檔、電子郵件和萬維網等文本數據庫也正在快速的增長。隨著各種電子形式的文本文檔以指數級的速度增長，有效的信息檢索、內容管理及信息過濾等應用變得越來越重要和困難。文本自動分類是一個有效的解決辦法，已成為一項具有實用價值的關鍵技術。文本分類的主要步驟為:文本預處理、訓練分類模型、測試分類模型。近年來，多種統計理論和機器學習方法被用來進行文本的自動分類，掀起了文本自動分類研究和應用的熱潮。

本文通過研究發現傳統的文本特征權值表示方法 TFIDF的不足:它忽略了特征詞和類別之間的相關性。本文認為特征詞和類別之間沒有絕對的獨立性，針對這個不足，提出了TFIDF-CHI算法，并用實驗加以證明。

1 TFIDF算法及其改進

1.1 ?字2統計量

?字2統計量(chi-square statistic， CHI)特征選擇方法又被稱作開方擬合檢驗，這個概念來自列表檢驗，它可以用來衡量特征x與類別c之間的統計相關性。 ?字2方法認為特征t與文本類別之間的沒有獨立性，它們之間的關系類似于具有一維自由度的 ?字2分布， ?字2統計量的值越高，詞匯和類別之間的獨立性就越小。它基于如下假設:在指定類別Ci的文本中出現頻率高的詞語和在其它類的文本中出現頻率高的詞語，對判斷文章是否屬于類別Ci都有幫助。其計算公式如下:

(1)

式中，A是特征t和第i類文檔共同出現的頻度;B是特征t出現而第i類文檔不出現的頻度;C是第i類文檔出現而特征t不出現的頻度;D是第i類文檔和特征都不出現的頻度;N為總共的文本數，且N=A+B+C+D，同時要求滿足A*D>B*C。文獻[1]中指出，CHI算法綜合考慮了特征與類別出現的各種可能性，在文本數量逐漸增多的過程中，穩定性很好;與其他方法相比，CHI大約減少50%的詞匯，分類效果好。

1.2 傳統TFIDF計算方法

傳統的TFIDF權重計算方法是由Salton在1988年提出的。指導思想是:在同一個文本中出現的頻率較高，在不同文本中出現的頻率較小的詞應該賦予較高的權值。它主要考慮兩個方面:詞語在文本中出現的頻率(TF)，用于計算該詞描述文檔內容的能力;反文檔頻率(IDF)，用于計算該詞區分文檔的能力。特征詞條的權值與詞條頻率成正比，與文檔頻率成反比。

傳統TFIDF權值計算公式:

(2)

其中tf(t，d)為特征t在文本d中的頻數，n為文本集中含有t的文本的數量，a是一個常量(一般取0.01)，log2(N/ntk+a)是逆文本頻率函數，即n越大此值越小。分母是歸一化因子。

但是傳統TFIDF權值計算方法也有其不可避免的不足，IDF的簡單結構并不能有效地反映單詞的重要程度和特征詞的分布情況，使其無法很好地完成對權值調整的功能，所以TFIDF法的精度并不是很高。其權重計算的有效性和詞條的分類能力就存在嚴重不足。而CHI算法卻能夠很好的彌補TFIDF算法的不足。

1.3 TFIDF-CHI算法

因此，我們將TFIDF算法和CHI算法加以綜合，用CHI算法的優點來彌補TFIDF的不足，提出了新的權值計算方法，TFIDF-CHI算法。TFIDF-CHI 的計算公式為:

(3)

2 試驗過程

2.1 實驗環境與實驗數據集

我們用Visual C++ 6.0實現本文的算法，在Windows XP的環境下進行試驗。實驗數據是是從中文自然語言處理開放平臺網站獲取李榮陸收集的新華社的新聞樣本語料庫。其中訓練樣本2000個，測試樣本 815個，共 2815個樣本。樣本有10個類別，分別為 政治、藝術、醫藥、體育、軍事、經濟、教育、交通、計算機、環境;

2.2 評估方法

因為文本分類本質上是一個映射過程，所以評估文本分類系統的標志是映射的準確程度和映射的速度。映射的速度取決于映射規則的復雜程度，而評估映射準確程度的參照物是通過專家思考判斷后對文本的分類結果(這里假設人工分類完全正確并且排除個人思維差異的因素)，與人工分類結果越相近，分類的準確程度就越高。 本文中文本分類的評價方法主要有查準率(也稱為準確度)、查全率(也稱為召回率)。

準確率是所有判斷的文本中與人工分類結果吻合的文本所占的比率。其數學公式為:

準確率(precision)=分類的正確文本數/實際分類的文本數

召回率是人工分類結果應有的文本中分類系統吻合文本所占的比率，其數學公式為:

召回率(recall)=分類的正確文本數/應有文本數

2.3 試驗分析

本文的試驗使用KNN分類器，其中K取35。本文隨機抽取了“收入”、“亞軍”、“武器”和“青年”四個特征詞，其中“亞軍”和“武器”是在體育和軍事類中常見的，而在其他類中則不常見，所以它們對類的貢獻比較大。而“青年”可在多個類別中多次出現，所以其對類的貢獻相對較小。通過我們對公式的改進，可猜想改進后的“亞軍”和“武器”的權值應該增大，而“青年”的權值則應減小。

表1 特征詞權重

表2 各個類別的分類準確率及召回率

表1列出了針對四個不同的特征詞，分別采用TFIDF和TFIDF-CHI兩種不同的計算方法所得到的權值和的分類準確率。實驗中具有代表性的詞使用TFIDF-CHI算法后的權值明顯比用TFIDF算法所得的權值大。從表中可看出計算結果與我們所猜想的結果基本一致。表2通過列出常用的度量標準，準確率和召回率對兩個算法進行對比。由表2可知通過對TFIDF的改進，重置特征詞的權重，使文本分類的準確率和召回率都明顯得到改善，凸顯了特征詞與類別之間的關系。

3 試驗總結

綜上所述，從實驗的圖表中我們可以看出不同的權值計算方法對分類的準確率有著一定的影響。與TFIDF相比，改進后的TFIDF 更能夠反映特征詞與類別之間的關系，進一步提高了文本分類的準確率。近年來，一些研究者針對TFIDF權重函數提出了大量的改進算法。文獻[2-4] 在TFIDF的基礎上結合了文本語義、頻率等多方面信息，提出了新的改進算法。文獻[5-11] 針對TFIDF沒有考慮特征向在文本集上的分布比例，而對其改進，將TFIDF和互信息，信息增益等方法進行了融合。文獻[12-13]將Gini index與TFIDF相結合，提出了新的改進算法。文獻[14]在TFIDF的基礎上引入了遺傳算法。文獻[15]考慮了當訓練文本屬于同一類別時，文本特征的權值計算。文獻[16]通過對TFIDF的改進考慮到了特征項在類間的分布情況。

本文將TFIDF和互信息綜合，各取其優點，將分類的準確率和召回率進一步提高。同時由于CHI算法綜合考慮了特征與類別出現的各種可能性，在文本數量逐漸增多的過程中，穩定性很好;與前面其他各種改進方法相比，CHI大約減少50%的詞匯，分類效果好。

4 結束語

特征權重計算方法的選擇對文檔分類的精確度有很大的影響。本文研究了傳統的TFIDF算法，并在其基礎上提出了新的改進方法TFIDF-CHI。由于CHI方法考慮了特征詞對類別的貢獻，所以理論上改進后的TFIDF-CHI方法能夠通過重置權值，更好的優化分類效果。實驗證明，新的改進方法TFIDF-CHI在分類的精確度上確實有更好的表現，因此，實驗說明了，改進后的TFIDF算法——TFIDF-CHI是一種高效可行的特征權重計算方法。雖然TFIDF是很經典的算法，但是TFIDF還有很多方面值得我們研究，例如雖然TFIDF權值計算方法可以和很多的特征選擇方法進行綜合，更改權值的計算方法，以提高分類效率，但是他TFIDF和哪種選擇方法綜合后，分類效率最高，適用的場合也最廣則還有待研究。

參考文獻:

[1] 張俊麗，趙乃瑄，馮君.基于統計頻率的文本分類特征選擇算法研究[J].現代圖書情報技術，2008(11):44-48.

[2] 沈志斌，白清源. 一種基于多重因子加權的文本特征項權值計算方法[J].南京師范大學學報:工程技術版，2008，8(4):80-83.

[3] 龔靜，田小梅.基于文本表示的特征項權值計算方法[J].電腦開發與應用(總133)，21(2):46-48.

[4] 龔靜，周經野.一種基于多重因子加權的文本特征項權值計算方法[J].計算技術與自動化，2007，26(1):80-83.

[5] 姚興山.基于統計的中文文本分類研究[J].信息系統，2009，32(5):95-98.

[6] 陳國松，黃大榮.基于信息熵TF IDF文本分類特征選擇算法研究[J].湖北民族學院學報:自然科學版，2008，26(4):402-404.

[7] 廖浩，李志蜀，王秋野，等.基于詞語關聯的文本特征詞提取方法[J].計算機應用，2007，27(12):3009-3012.

[8] 白碩，王實.文檔中詞語權重計算方法的改進[J].中文信息學報，2007，14(6):8-13.

[9] 馮長遠，普杰信.Web文本特征選擇算法的研究[J].計算機應用研究，2005，(7):36-38.

[10] 初建崇，劉培玉，王衛玲.Web 文檔中詞語權重計算方法的改進[J].計算機工程與應用，2007，43(19):192-198.

[11] 沈志斌，白清源.文本分類中特征權重算法的改進[J].南京師范大學學報:工程技術版，2008，8(4):95-98.

[12] Shang Wenqian，Qu Youli，Zhu Haibin，et al.An Adaptive Fuzzy kNN Text Classifier Based on Gini Index Weight[C].Proceedings of the 11th IEEE Symposium on Computers and Communications(ISCC'06)0-7695-2588-1/06，2006.

[13] Shang Wenqian，Huang Houkuan，Zhu Haibin，et al.An Adaptive Fuzzy kNN Text Classifier[M]//Alexandrov V N.ICCS 2006，Part III，LNCS 3993，2006:216-223.Springer-Verlag Berlin Heidelberg.2006.

[14] 張玉芳，彭時名，呂佳.基于文本分類TFIDF方法的改進與應用[J].計算機工程，2006，32(19):76-78.

[15] 寇莎莎，魏振軍.自動文本分類中權值公式的改進[J].計算機工程與設計，2005，26(6):1616-1618.

[16] 熊忠陽，黎剛，陳小莉，等偉.文本分類中詞語權重計算方法的改進與應用[J].計算機工程與應用，2008，44(5):187-189.