文本分類算法中詞語(yǔ)權(quán)重計(jì)算方法的改進(jìn)

摘要:在自動(dòng)文本分類中，TFIDF公式是常用的詞語(yǔ)權(quán)重計(jì)算公式。該方法簡(jiǎn)單易行，但僅僅考慮了特征詞出現(xiàn)的頻率，而忽略了特征詞對(duì)區(qū)分每個(gè)類的貢獻(xiàn)。針對(duì)這個(gè)不足，該文提出了TFIDF-CHI，來(lái)修正各個(gè)特征詞的權(quán)重，重新調(diào)整每個(gè)特征詞對(duì)各個(gè)類別的區(qū)分度，并用KNN分類器來(lái)驗(yàn)證其有效性。實(shí)驗(yàn)證明該方法優(yōu)于原來(lái)的TFIDF算法，表明了改進(jìn)的策略是可行的。

關(guān)鍵詞:文本分類;特征權(quán)值;TFIDF;TFIDF-CHI

中圖分類號(hào):TP312 文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):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

現(xiàn)在，政府、工業(yè)、商業(yè)和其他機(jī)構(gòu)的大部分信息都以文本數(shù)據(jù)庫(kù)的形式電子地存儲(chǔ)，同時(shí)電子出版物、各種電子文檔、電子郵件和萬(wàn)維網(wǎng)等文本數(shù)據(jù)庫(kù)也正在快速的增長(zhǎng)。隨著各種電子形式的文本文檔以指數(shù)級(jí)的速度增長(zhǎng)，有效的信息檢索、內(nèi)容管理及信息過(guò)濾等應(yīng)用變得越來(lái)越重要和困難。文本自動(dòng)分類是一個(gè)有效的解決辦法，已成為一項(xiàng)具有實(shí)用價(jià)值的關(guān)鍵技術(shù)。文本分類的主要步驟為:文本預(yù)處理、訓(xùn)練分類模型、測(cè)試分類模型。近年來(lái)，多種統(tǒng)計(jì)理論和機(jī)器學(xué)習(xí)方法被用來(lái)進(jìn)行文本的自動(dòng)分類，掀起了文本自動(dòng)分類研究和應(yīng)用的熱潮。

本文通過(guò)研究發(fā)現(xiàn)傳統(tǒng)的文本特征權(quán)值表示方法 TFIDF的不足:它忽略了特征詞和類別之間的相關(guān)性。本文認(rèn)為特征詞和類別之間沒(méi)有絕對(duì)的獨(dú)立性，針對(duì)這個(gè)不足，提出了TFIDF-CHI算法，并用實(shí)驗(yàn)加以證明。

1 TFIDF算法及其改進(jìn)

1.1 ?字2統(tǒng)計(jì)量

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

(1)

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

1.2 傳統(tǒng)TFIDF計(jì)算方法

傳統(tǒng)的TFIDF權(quán)重計(jì)算方法是由Salton在1988年提出的。指導(dǎo)思想是:在同一個(gè)文本中出現(xiàn)的頻率較高，在不同文本中出現(xiàn)的頻率較小的詞應(yīng)該賦予較高的權(quán)值。它主要考慮兩個(gè)方面:詞語(yǔ)在文本中出現(xiàn)的頻率(TF)，用于計(jì)算該詞描述文檔內(nèi)容的能力;反文檔頻率(IDF)，用于計(jì)算該詞區(qū)分文檔的能力。特征詞條的權(quán)值與詞條頻率成正比，與文檔頻率成反比。

傳統(tǒng)TFIDF權(quán)值計(jì)算公式:

(2)

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

但是傳統(tǒng)TFIDF權(quán)值計(jì)算方法也有其不可避免的不足，IDF的簡(jiǎn)單結(jié)構(gòu)并不能有效地反映單詞的重要程度和特征詞的分布情況，使其無(wú)法很好地完成對(duì)權(quán)值調(diào)整的功能，所以TFIDF法的精度并不是很高。其權(quán)重計(jì)算的有效性和詞條的分類能力就存在嚴(yán)重不足。而CHI算法卻能夠很好的彌補(bǔ)TFIDF算法的不足。

1.3 TFIDF-CHI算法

因此，我們將TFIDF算法和CHI算法加以綜合，用CHI算法的優(yōu)點(diǎn)來(lái)彌補(bǔ)TFIDF的不足，提出了新的權(quán)值計(jì)算方法，TFIDF-CHI算法。TFIDF-CHI 的計(jì)算公式為:

(3)

2 試驗(yàn)過(guò)程

2.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)集

我們用Visual C++ 6.0實(shí)現(xiàn)本文的算法，在Windows XP的環(huán)境下進(jìn)行試驗(yàn)。實(shí)驗(yàn)數(shù)據(jù)是是從中文自然語(yǔ)言處理開放平臺(tái)網(wǎng)站獲取李榮陸收集的新華社的新聞樣本語(yǔ)料庫(kù)。其中訓(xùn)練樣本2000個(gè)，測(cè)試樣本 815個(gè)，共 2815個(gè)樣本。樣本有10個(gè)類別，分別為 政治、藝術(shù)、醫(yī)藥、體育、軍事、經(jīng)濟(jì)、教育、交通、計(jì)算機(jī)、環(huán)境;

2.2 評(píng)估方法

因?yàn)槲谋痉诸惐举|(zhì)上是一個(gè)映射過(guò)程，所以評(píng)估文本分類系統(tǒng)的標(biāo)志是映射的準(zhǔn)確程度和映射的速度。映射的速度取決于映射規(guī)則的復(fù)雜程度，而評(píng)估映射準(zhǔn)確程度的參照物是通過(guò)專家思考判斷后對(duì)文本的分類結(jié)果(這里假設(shè)人工分類完全正確并且排除個(gè)人思維差異的因素)，與人工分類結(jié)果越相近，分類的準(zhǔn)確程度就越高。 本文中文本分類的評(píng)價(jià)方法主要有查準(zhǔn)率(也稱為準(zhǔn)確度)、查全率(也稱為召回率)。

準(zhǔn)確率是所有判斷的文本中與人工分類結(jié)果吻合的文本所占的比率。其數(shù)學(xué)公式為:

準(zhǔn)確率(precision)=分類的正確文本數(shù)/實(shí)際分類的文本數(shù)

召回率是人工分類結(jié)果應(yīng)有的文本中分類系統(tǒng)吻合文本所占的比率，其數(shù)學(xué)公式為:

召回率(recall)=分類的正確文本數(shù)/應(yīng)有文本數(shù)

2.3 試驗(yàn)分析

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

表1 特征詞權(quán)重

表2 各個(gè)類別的分類準(zhǔn)確率及召回率

表1列出了針對(duì)四個(gè)不同的特征詞，分別采用TFIDF和TFIDF-CHI兩種不同的計(jì)算方法所得到的權(quán)值和的分類準(zhǔn)確率。實(shí)驗(yàn)中具有代表性的詞使用TFIDF-CHI算法后的權(quán)值明顯比用TFIDF算法所得的權(quán)值大。從表中可看出計(jì)算結(jié)果與我們所猜想的結(jié)果基本一致。表2通過(guò)列出常用的度量標(biāo)準(zhǔn)，準(zhǔn)確率和召回率對(duì)兩個(gè)算法進(jìn)行對(duì)比。由表2可知通過(guò)對(duì)TFIDF的改進(jìn)，重置特征詞的權(quán)重，使文本分類的準(zhǔn)確率和召回率都明顯得到改善，凸顯了特征詞與類別之間的關(guān)系。

3 試驗(yàn)總結(jié)

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

本文將TFIDF和互信息綜合，各取其優(yōu)點(diǎn)，將分類的準(zhǔn)確率和召回率進(jìn)一步提高。同時(shí)由于CHI算法綜合考慮了特征與類別出現(xiàn)的各種可能性，在文本數(shù)量逐漸增多的過(guò)程中，穩(wěn)定性很好;與前面其他各種改進(jìn)方法相比，CHI大約減少50%的詞匯，分類效果好。

4 結(jié)束語(yǔ)

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

參考文獻(xiàn):

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

[2] 沈志斌，白清源. 一種基于多重因子加權(quán)的文本特征項(xiàng)權(quán)值計(jì)算方法[J].南京師范大學(xué)學(xué)報(bào):工程技術(shù)版，2008，8(4):80-83.

[3] 龔靜，田小梅.基于文本表示的特征項(xiàng)權(quán)值計(jì)算方法[J].電腦開發(fā)與應(yīng)用(總133)，21(2):46-48.

[4] 龔靜，周經(jīng)野.一種基于多重因子加權(quán)的文本特征項(xiàng)權(quán)值計(jì)算方法[J].計(jì)算技術(shù)與自動(dòng)化，2007，26(1):80-83.

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

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

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

[8] 白碩，王實(shí).文檔中詞語(yǔ)權(quán)重計(jì)算方法的改進(jìn)[J].中文信息學(xué)報(bào)，2007，14(6):8-13.

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

[10] 初建崇，劉培玉，王衛(wèi)玲.Web 文檔中詞語(yǔ)權(quán)重計(jì)算方法的改進(jìn)[J].計(jì)算機(jī)工程與應(yīng)用，2007，43(19):192-198.

[11] 沈志斌，白清源.文本分類中特征權(quán)重算法的改進(jìn)[J].南京師范大學(xué)學(xué)報(bào):工程技術(shù)版，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] 張玉芳，彭時(shí)名，呂佳.基于文本分類TFIDF方法的改進(jìn)與應(yīng)用[J].計(jì)算機(jī)工程，2006，32(19):76-78.

[15] 寇莎莎，魏振軍.自動(dòng)文本分類中權(quán)值公式的改進(jìn)[J].計(jì)算機(jī)工程與設(shè)計(jì)，2005，26(6):1616-1618.

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