文本分類中信息增益算法的改進

楊敬妹　王學軍

摘 要： 分析了信息增益方法的不足，并將類內離散度、類間離散度和權重協調因子應用到信息增益算法上，提出了一種改進的信息增益算法。實驗表明，該方法在分類效果上與經典算法相比有一定的提高。

關鍵詞： 特征選擇； 信息增益； 類內離散度； 類間離散度； 權重協調因子

中圖分類號：TP312 文獻標志碼：A 文章編號：1006-8228（2013）09-45-02

0 引言

信息科學技術和互聯網技術每天都在更新，人們通過網絡獲得的信息資源越來越多，與此同時，就需要更多的人力和時間來整理網絡里的各種信息，因此產生了文本分類技術。文本數據的特點就是高維性和稀疏性[1-2]。文本分類算法在分類的時間上，帶來大量時間開銷；特征過多又往往會出現“維數災難”的問題，特征選擇就此產生。常用的特征選擇方法是：信息增益、互信息、χ2統計量、特征詞頻-文檔頻率等。很多人傾向于信息增益方法，因為它考慮了特征詞條未發生的情況。實驗證明這種貢獻在多數情況下遠遠小于它帶來的干擾。本文提出了一種新的特征選擇方法，并通過實驗證明了該方法能有效提高文本分類的精度。

1 信息增益特征選擇方法

信息增益（Information Gain）[3]在機器學習領域被廣泛使用，在信息論中，樣本屬性的信息增益越大，其包含的信息量也越大。對分類系統來說，計算信息增益是針對一個一個的特征項而言的，它通過統計某一個特征項t在類別ci中出現與否的文檔數來計算特征項t對類別ci的信息增益，定義為考慮出現前后的信息熵之差，定義如公式⑴：

⑴

式⑴中，P（ci）表示ci類文檔在語料中出現的概率，P（t）表示語料中包含t的文檔的概率，P（ci|t）表示文檔包含t時屬于ci類文檔的條件概率，表示語料中不包含特征詞條t的文檔概率，表示文檔不包含特征詞條t時屬于ci類的條件概率，m表示文檔類別數。

顯然，某個特征項的信息增益值越大，表示其貢獻越大，對分類也越重要。因此，在進行特征選擇時，通常選取信息增益值大的若干個單詞構造文本的特征向量。信息增益的優點在于，它考慮了詞條未發生的情況，即雖然某個單詞不出現也又可能對判斷文本類別有貢獻。但是實驗證明，這種貢獻往往遠遠小于考慮單詞不出現情況所帶來的干擾。

2 信息增益特征選擇算法的改進

信息增益特征選擇方法的不足之處是：忽視了類間、類內分布不平衡的問題[4]；對特征項出現的頻率考慮不全面。近些年，不少學者都在改進信息增益算法，來減小它帶來的干擾，如利用語義聯系改進信息增益算法[5]；利用最大值與次大值之間的差作為最終的評價函數值[6]；把頻度、集中度、分散度都考慮上的算法[7]；通過構造隸屬度函數來改進[8]。本文引入類間集中度DIac（t）、類內分散度DIic（t）和權重協調因子ω來對原始的算法進行改進。

2.1 類間離散度

一般情況下，如果一個特征項在一個類別中大量出現，而在其他類別中較少出現，那么這個特征項對于類別判定的貢獻度應該是比較大的，這種特征項相對于類別的傾斜特性使用類間離散度來衡量，即權衡一個特征相對于所有預定類別的分布均衡程度，分布越不均衡，那么這個特征對于類別判定的貢獻度越大。類間離散度用來描述特征在類間的分布情況，特征項的類間離散度計算如公式⑵：

從公式⑵中可以看出，那些集中分布在個別類或者幾個類別的特征項，其類間離散度的值比較大，這些特征項一般具有較強的類別區分能力，當特征詞條t僅在一個類別中出現的時候，DIac取最大值1，此時的分類能力最強；當特征詞條t在每個類別中都出現的時候，DIac取最小值0，其分類能力最弱。

2.2 類內離散度

在衡量了特征相對于類別的均衡程度后，還應該考慮特征在一個類別內的分布情況。如果一個特征在一個類別內的某個文本中大量出現，而其他文本出現很少或不出現，那么這個特征對于文本的分類貢獻較少；反之，則特征對于類別區分的貢獻度是比較大的。對于類別內的特征分布情況，我們可以使用類內離散度來衡量，即權衡一個特征相對于一個類別的分布均勻程度，分布越均衡，那么這個特征對于類別判定的貢獻程度越大。類內離散度描述了特征項在某個類中的分布情況，特征項t在類ci中的類內離散度計算如公式⑶：

⑶

式⑶中，n代表ci類中的文檔個數，fj（t）表示詞條t在ci類的第j篇文檔中的詞頻，表示詞條t在類ci文檔中的平均詞頻。其中的計算公式為：。

類內離散度越小，說明該詞條越集中分布在該類中，其區分類別的能力越強。由公式⑶可以看出，當特征向量t在本類別中所有文檔中都出現的時候，DIic取最小值0，此時的分類能力最強，可見DIic的值與其分類能力是成反比的。

2.3 權重協調因子

根據很多實例判斷，特征詞在語料庫中出現次數多少并不能完全表征該特征詞在分類中的重要程度，頻率相同的特征詞對分類的重要程度也是不同的，在各類別中分布越均勻，其對分類的重要性就越小，反之就越大。考慮到方差這一數學指標能夠較好地體現數據分布是否均勻這一特征，進而通過方差除以該特征詞在各類中的詞頻之和來得到權重協調因子的定義如公式⑷：

⑷

式⑷中，P（ci|t）表示文檔包含t時屬于ci類文檔的條件概率，m表示文檔類別數。

2.4 信息增益算法的改進

對于分類而言，如果一個特征項在某個類別中大量出現，在其他類別中較少出現，且該特征在大量出現的類別中分布比較均勻，那么顯然這個特征對于分類是有利的，在類間、類內離散度上的表現為類間離散度較大，類內離散度較小。所以在衡量分類貢獻度時，應將類間離散度和類內離散度綜合考慮，另外加入了權重協調因子，來對信息增益的方法可以更進一步的提高它的計算精度。

利用公式⑷計算出特證詞條t的權重協調因子ω，然后再對文檔里所有的特征詞出現的概率進行求和處理，利用公式⑵求出類間離散度DIac（t），利用公式⑶得出類內離散度DIic（t），加入到改進算法之內，使得新算法可以進一步提高計算精度。具體算法如公式⑸：

⑸

3 實驗結果及分析

文本預處理階段采用了漢語詞法分析系統ICTCLAS對文本集合中的數據進行分詞，用Lucene建立全文索引；在測試數據時，實驗采用KNN（k-Nearest Neighbor）分類器（KNN算法是一種常用的，效果較好的文本分類算法）。

3.1 語料集

為了驗證改進算法的有效性，盡可能地消除語料選取不當所帶來的干擾。本實驗搜集了中文文本分類語料庫，選用了3000篇文本，其中包括計算機、軍事、教育、經濟、政治、體育6大類，其中采用1800篇文本作為訓練集，其余1200篇文本作為測試集。

3.2 評估指標

⑴ 查全率

定義為正確分類的正例個數占實際正例個數的比例，表示為公式⑹：

⑵ 查準率

定義為正確分類的正例個數占分類為正例的實例個數的比例，表示為公式⑺：

⑶ F1評估值

在信息檢索領域，查全率與查率是一對相互制約的指標。查準率和查全率反映了分類質量的兩個不同方面，兩者必須綜合考慮。因此，列入了F1測試值作為評價指標，它是查全率與查準率的調和平均數，表示為公式⑻：

⑻

3.3 實驗結果及分析

經典算法的分類結果如表1所示。

根據表1中的數據，得出平均的F1測試值為85.533%。

改進算法的分類結果如表2所示。

從表2中可以看出，各種類別的分類效果都很好，平均的F1測試值為86.786%，相比原來的算法，提高了信息增益的精度，效果還是令人滿意的。

4 結束語

本文仔細分析了傳統的信息增益算法的不足， 并針對其進行了廣泛的研究，最終提出了一種改進的信息增益算法。實驗證明，改進后的算法與傳統算法相比，在分類準度和精度上都有了更好的表現。但是改進的算法增大了計算的難度，將會導致分析的時間變長。下一步工作將從縮短時間的角度來繼續研究，深入分析對分類性能有影響的因素，完善新算法。

參考文獻：

[1] Y. Li， D.F. Hsu， S.M. Chung， Combining multiple feature selection methods for text categorization by using rank-score characteristics[C]. IEEE 21st International Conference on Tools with Artificial Intelligence， Newark，NJ，USA，Nov.2009：508-517

[2] B. Yu， Z. Xu， C. Li.Latent semantic analysis for text categorization using neural network[J].Knowledge-Based Systems，2008.21（8）：900-904

[3] 苗奪謙，衛志華.中文文本信息處理的原理與應用[M].清華大學出版社，2007.

[4] Harun Uguz.A two-stage feature selection method for text categorization by using information gain， principal component analysis and genetic algorithm[J]. Knowledge-Based Systems，2011.24（7）：1024-1032

[5] 張浩.基于語義關聯的文本分類研究[J].舍肥工業大學學報，2011.

[6] 張玉芳，萬斌候，熊忠陽.文本分類中的特征降維方法研究[J].計算機應用研究，2012.29（7）：2541-2543

[7] 劉慶和，梁正友.一種基于信息增益的特征優化選擇方法[J].計算機工程與應用，2011.12.