文本分類中一種基于互信息改進(jìn)的特征選擇方法

田 野，鄭 偉

（河北北方學(xué)院理學(xué)院，河北 張家口 075000）

1 引 言

文本自動分類的任務(wù)就是對未知類別的文檔進(jìn)行自動判斷，把它歸屬到已有類別集中，目前文本自動分類技術(shù)已經(jīng)廣泛地應(yīng)用到信息檢索和數(shù)字化圖書館等領(lǐng)域，具有很強(qiáng)的應(yīng)用價值。在基于向量空間模型的文本自動分類系統(tǒng)中，文本分類面臨的難題之一是如何從高維的特征空間中選取對文本分類有效的特征，特征選擇就是解決上述問題的辦法之一。目前常用的特征選擇方法有互信息 （MI）、文檔頻率方法（DF）、信息增益 （IG）、期望交叉熵 （ECE）、χ2統(tǒng)計(jì) （CHI）、文本證據(jù)權(quán) （WET）等［1，2］。

互信息是信息論和統(tǒng)計(jì)學(xué)中一種經(jīng)典的統(tǒng)計(jì)算法，常用來計(jì)算樣本和類別的相關(guān)性，互信息作特征選擇方法也廣泛地用在特征選擇中，但是其在理論上還有一定的不完善性，在實(shí)踐中，特征選擇時特征的提取效果也不是十分理想，尤其在中文文本分類中。本文針對互信息 （MI）特征選擇方法在特征提取時分類效果不理想的狀況，提出了一種改進(jìn)的互信息特征選擇方法。該方法改進(jìn)了互信息方法中的不足點(diǎn)，應(yīng)用在SVM與KNN實(shí)驗(yàn)上，極大地提高了分類精度。

2 互信息選擇算法

特征選擇方法是使用某種特征評估函數(shù)對每個特征進(jìn)行評估打分，按照評估分?jǐn)?shù)的高低進(jìn)行特征排序，再選取一定預(yù)設(shè)數(shù)目評分高的特征作為文本分類的特征集。詞條和類別的互信息 （mutual information，MI）體現(xiàn)了詞條與類別的相關(guān)程度，詞條對于類別的互信息越大，它們之間的共現(xiàn)概率也越大。它作為一種標(biāo)準(zhǔn)被廣泛用于關(guān)聯(lián)統(tǒng)計(jì)建模。

特征t如果以較高的概率在某個類別ci中出現(xiàn)，而低概率在其它類別中出現(xiàn)，那么稱特征t與類別ci的互信息值較高，t可被選取為類別的ci的特征。特征t與類ci的互信息計(jì)算公式如下：

其中，P（t｜c(diǎn)i）為特征項(xiàng)t出現(xiàn)在類ci中的概率，P（t）定義為t出現(xiàn)的概率，P（ci）定義為類別ci的概率。

如果有m個類別，于是對每個特征項(xiàng)t都有m個類別值，通常取它們的平均互信息。平均值大的特征被選擇的可能性大。平均互信息如公式 （2）所示：

如果一個詞條能夠帶有只代表某一類的豐富類別信息，同時在其他類別中很少出現(xiàn)，那么該詞條可選取作為對應(yīng)類別的類別特征。為了最大效率的選取出能夠代表各類類別信息的典型特征，我們可以采用對每個類訓(xùn)練文本集中分別選取代表此類的關(guān)鍵詞條作為特征。

3 互信息方法的不足與改進(jìn)

使用互信息 （MI）方法進(jìn)行特征選擇時，計(jì)算所得到的特征互信息值的大小能夠直接體現(xiàn)該特征與類別相關(guān)性的大小，研究發(fā)現(xiàn)公式還具有以下2點(diǎn)不足：

1）MI公式由于互信息沒有考慮詞頻，所以經(jīng)常會傾向于選擇低頻詞，低頻詞的作用被放大，甚至是噪音的低頻次被選中用于文本表示，因此使用MI的效果并不是很好。

2）在互信息公式中，會出現(xiàn)特征t與類別的互信息為負(fù)數(shù)的情況，當(dāng)特征t很少在類別ci文本中出現(xiàn)，但特征t的文檔頻率又很大，即P（t）很大而P（t｜c(diǎn)i）很小，計(jì)算后就會出現(xiàn)負(fù)數(shù)［3］。

為了使特征選擇方法能夠更有效地提取具有類別信息的特征，結(jié)合上述對互信息選擇方法的分析，對互信息選擇方法進(jìn)行了改進(jìn)，用于類內(nèi)特征的提取，改進(jìn)后的互信息算法為：

公式 （3）中引入因子tf（t，ci）用來彌補(bǔ)原算法中對低頻詞的倚重，去掉對數(shù)中的log可以避免負(fù)互信息值的出現(xiàn)，改進(jìn)后的方法可用于類別內(nèi)部特征的選擇。

4 實(shí)驗(yàn)及其分析

4.1 實(shí)驗(yàn)設(shè)置

本實(shí)驗(yàn)?zāi)康氖峭ㄟ^分類實(shí)驗(yàn)，探討在SVM和KNN分類算法下測試互信息和改進(jìn)之后的互信息特征選擇方法對應(yīng)的特征選擇效果。

實(shí)驗(yàn)采用復(fù)旦大學(xué)收集的中文語料庫，選用其中的5個類別：環(huán)境、交通、計(jì)算機(jī)、教育、醫(yī)藥，其中訓(xùn)練樣本694篇，測試樣本345篇，每個類別的訓(xùn)練語料與測試語料分布均勻。

4.2 分類器和性能評價

實(shí)驗(yàn)采用目前性能最好的分類器SVM和KNN用于分類［4］，實(shí)驗(yàn)采用宏平均準(zhǔn)確率MacroP，宏平均召回率MacroR，宏平均MacroF1值作為評估指標(biāo)，其中F1測試值綜合考慮了文本分類的查準(zhǔn)率與查全率，其具體計(jì)算公式如下：

4.3 實(shí)驗(yàn)結(jié)果及分析

圖1是在采用復(fù)旦大學(xué)5個類別的語料下，采用互信息和改進(jìn)的互信息方法在選擇不同數(shù)目的類內(nèi)特征值時，對應(yīng)分類的F1均值曲線。表1中數(shù)據(jù)展示了當(dāng)選擇不同的類內(nèi)特征值時，互信息和改進(jìn)的互信息方法在SVM和KNN分類器下的F1值比較。

圖1 改進(jìn)后的不同特征選擇方法分類結(jié)果

從圖1曲線可以看出改進(jìn)后的互信息方法在SVM和KNN分類器下特征提取效果明顯好于原互信息方法，在類內(nèi)特征數(shù)目增加時，分類效果均較為穩(wěn)定，而原互信息方法在兩類分類器下對應(yīng)的分類效果依賴特征數(shù)目，F(xiàn)1值會隨著特征數(shù)目的增加而增加。

表1 改進(jìn)后的互信息和互信息方法分類效果對比

從表1中可以看出改進(jìn)后的互信息法在每類抽取800維特征時，使用SVM分類器分類效果達(dá)到最佳值，其F1值為94.455%，分類效果好于互信息在不同數(shù)目特征值時的分類F1值；在使用KNN分類器時，改進(jìn)后的互信息算法對應(yīng)的分類F1值一直比較穩(wěn)定，都是在85%左右，并且明顯高于原互信息方法的分類F1值。綜合看，改進(jìn)后的互信息算法用在特征選擇時能夠提高不同分類器的分類準(zhǔn)確率。

5 結(jié) 論

互信息方法是一種常用的特征選擇方法，但還存在理論需進(jìn)一步完善、實(shí)踐中特征提 取效果差的不足。本文分析了互信息算法，找出了其存在的不足，對互信息算法進(jìn)行了改進(jìn)，提出了一種改進(jìn)的互信息特征選擇方法。實(shí)驗(yàn)結(jié)果證明，改進(jìn)后的算法在特征選擇效果方面明顯優(yōu)于原算法，用于分類時能夠有效地提高分類準(zhǔn)確率。下一步的工作將繼續(xù)研究特征選擇方法約束條件，根據(jù)約束條件構(gòu)造出更好的類內(nèi)特征選擇方法。

［1］鄭偉，王銳.文本分類中特征提取方法的比較與研究［J］.河北北方學(xué)院學(xué)報：自然科學(xué)版，2007，23（06）：51-54.

［2］Yang Y，Pederson J O.A comparative study on feature selection in text categorization［A］.Proceedings of the 14th International Conference on Machine Learning［C］.Nashville：Morgan Kaufmann，1997：412-420.

［3］裴志利，李志剛，王建，等.一種基于改進(jìn)互信息的文本分類方法［J］.內(nèi)蒙古民族大學(xué)學(xué)報：自然科學(xué)版，2007，22（04）：377-380.

［4］Yang Y M，Liu X.A re-examination of text categorization methods［A］.Proceedings of ACM SIGIR Conference on Research and Development in Information Retrieval（SIGIR）［C］.1999：42-49.