文本分類中信息增益算法的改進(jìn)

楊敬妹　王學(xué)軍

摘 要： 分析了信息增益方法的不足，并將類內(nèi)離散度、類間離散度和權(quán)重協(xié)調(diào)因子應(yīng)用到信息增益算法上，提出了一種改進(jìn)的信息增益算法。實(shí)驗(yàn)表明，該方法在分類效果上與經(jīng)典算法相比有一定的提高。

關(guān)鍵詞： 特征選擇； 信息增益； 類內(nèi)離散度； 類間離散度； 權(quán)重協(xié)調(diào)因子

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2013）09-45-02

0 引言

信息科學(xué)技術(shù)和互聯(lián)網(wǎng)技術(shù)每天都在更新，人們通過(guò)網(wǎng)絡(luò)獲得的信息資源越來(lái)越多，與此同時(shí)，就需要更多的人力和時(shí)間來(lái)整理網(wǎng)絡(luò)里的各種信息，因此產(chǎn)生了文本分類技術(shù)。文本數(shù)據(jù)的特點(diǎn)就是高維性和稀疏性[1-2]。文本分類算法在分類的時(shí)間上，帶來(lái)大量時(shí)間開(kāi)銷；特征過(guò)多又往往會(huì)出現(xiàn)“維數(shù)災(zāi)難”的問(wèn)題，特征選擇就此產(chǎn)生。常用的特征選擇方法是：信息增益、互信息、χ2統(tǒng)計(jì)量、特征詞頻-文檔頻率等。很多人傾向于信息增益方法，因?yàn)樗紤]了特征詞條未發(fā)生的情況。實(shí)驗(yàn)證明這種貢獻(xiàn)在多數(shù)情況下遠(yuǎn)遠(yuǎn)小于它帶來(lái)的干擾。本文提出了一種新的特征選擇方法，并通過(guò)實(shí)驗(yàn)證明了該方法能有效提高文本分類的精度。

1 信息增益特征選擇方法

信息增益（Information Gain）[3]在機(jī)器學(xué)習(xí)領(lǐng)域被廣泛使用，在信息論中，樣本屬性的信息增益越大，其包含的信息量也越大。對(duì)分類系統(tǒng)來(lái)說(shuō)，計(jì)算信息增益是針對(duì)一個(gè)一個(gè)的特征項(xiàng)而言的，它通過(guò)統(tǒng)計(jì)某一個(gè)特征項(xiàng)t在類別ci中出現(xiàn)與否的文檔數(shù)來(lái)計(jì)算特征項(xiàng)t對(duì)類別ci的信息增益，定義為考慮出現(xiàn)前后的信息熵之差，定義如公式⑴：

⑴

式⑴中，P（ci）表示ci類文檔在語(yǔ)料中出現(xiàn)的概率，P（t）表示語(yǔ)料中包含t的文檔的概率，P（ci|t）表示文檔包含t時(shí)屬于ci類文檔的條件概率，表示語(yǔ)料中不包含特征詞條t的文檔概率，表示文檔不包含特征詞條t時(shí)屬于ci類的條件概率，m表示文檔類別數(shù)。

顯然，某個(gè)特征項(xiàng)的信息增益值越大，表示其貢獻(xiàn)越大，對(duì)分類也越重要。因此，在進(jìn)行特征選擇時(shí)，通常選取信息增益值大的若干個(gè)單詞構(gòu)造文本的特征向量。信息增益的優(yōu)點(diǎn)在于，它考慮了詞條未發(fā)生的情況，即雖然某個(gè)單詞不出現(xiàn)也又可能對(duì)判斷文本類別有貢獻(xiàn)。但是實(shí)驗(yàn)證明，這種貢獻(xiàn)往往遠(yuǎn)遠(yuǎn)小于考慮單詞不出現(xiàn)情況所帶來(lái)的干擾。

2 信息增益特征選擇算法的改進(jìn)

信息增益特征選擇方法的不足之處是：忽視了類間、類內(nèi)分布不平衡的問(wèn)題[4]；對(duì)特征項(xiàng)出現(xiàn)的頻率考慮不全面。近些年，不少學(xué)者都在改進(jìn)信息增益算法，來(lái)減小它帶來(lái)的干擾，如利用語(yǔ)義聯(lián)系改進(jìn)信息增益算法[5]；利用最大值與次大值之間的差作為最終的評(píng)價(jià)函數(shù)值[6]；把頻度、集中度、分散度都考慮上的算法[7]；通過(guò)構(gòu)造隸屬度函數(shù)來(lái)改進(jìn)[8]。本文引入類間集中度DIac（t）、類內(nèi)分散度DIic（t）和權(quán)重協(xié)調(diào)因子ω來(lái)對(duì)原始的算法進(jìn)行改進(jìn)。

2.1 類間離散度

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

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

2.2 類內(nèi)離散度

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

⑶

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

類內(nèi)離散度越小，說(shuō)明該詞條越集中分布在該類中，其區(qū)分類別的能力越強(qiáng)。由公式⑶可以看出，當(dāng)特征向量t在本類別中所有文檔中都出現(xiàn)的時(shí)候，DIic取最小值0，此時(shí)的分類能力最強(qiáng)，可見(jiàn)DIic的值與其分類能力是成反比的。

2.3 權(quán)重協(xié)調(diào)因子

根據(jù)很多實(shí)例判斷，特征詞在語(yǔ)料庫(kù)中出現(xiàn)次數(shù)多少并不能完全表征該特征詞在分類中的重要程度，頻率相同的特征詞對(duì)分類的重要程度也是不同的，在各類別中分布越均勻，其對(duì)分類的重要性就越小，反之就越大?？紤]到方差這一數(shù)學(xué)指標(biāo)能夠較好地體現(xiàn)數(shù)據(jù)分布是否均勻這一特征，進(jìn)而通過(guò)方差除以該特征詞在各類中的詞頻之和來(lái)得到權(quán)重協(xié)調(diào)因子的定義如公式⑷：

⑷

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

2.4 信息增益算法的改進(jìn)

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

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

⑸

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

文本預(yù)處理階段采用了漢語(yǔ)詞法分析系統(tǒng)ICTCLAS對(duì)文本集合中的數(shù)據(jù)進(jìn)行分詞，用Lucene建立全文索引；在測(cè)試數(shù)據(jù)時(shí)，實(shí)驗(yàn)采用KNN（k-Nearest Neighbor）分類器（KNN算法是一種常用的，效果較好的文本分類算法）。

3.1 語(yǔ)料集

為了驗(yàn)證改進(jìn)算法的有效性，盡可能地消除語(yǔ)料選取不當(dāng)所帶來(lái)的干擾。本實(shí)驗(yàn)搜集了中文文本分類語(yǔ)料庫(kù)，選用了3000篇文本，其中包括計(jì)算機(jī)、軍事、教育、經(jīng)濟(jì)、政治、體育6大類，其中采用1800篇文本作為訓(xùn)練集，其余1200篇文本作為測(cè)試集。

3.2 評(píng)估指標(biāo)

⑴ 查全率

定義為正確分類的正例個(gè)數(shù)占實(shí)際正例個(gè)數(shù)的比例，表示為公式⑹：

⑵ 查準(zhǔn)率

定義為正確分類的正例個(gè)數(shù)占分類為正例的實(shí)例個(gè)數(shù)的比例，表示為公式⑺：

⑶ F1評(píng)估值

在信息檢索領(lǐng)域，查全率與查率是一對(duì)相互制約的指標(biāo)。查準(zhǔn)率和查全率反映了分類質(zhì)量的兩個(gè)不同方面，兩者必須綜合考慮。因此，列入了F1測(cè)試值作為評(píng)價(jià)指標(biāo)，它是查全率與查準(zhǔn)率的調(diào)和平均數(shù)，表示為公式⑻：

⑻

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

經(jīng)典算法的分類結(jié)果如表1所示。

根據(jù)表1中的數(shù)據(jù)，得出平均的F1測(cè)試值為85.533%。

改進(jìn)算法的分類結(jié)果如表2所示。

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

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

本文仔細(xì)分析了傳統(tǒng)的信息增益算法的不足， 并針對(duì)其進(jìn)行了廣泛的研究，最終提出了一種改進(jìn)的信息增益算法。實(shí)驗(yàn)證明，改進(jìn)后的算法與傳統(tǒng)算法相比，在分類準(zhǔn)度和精度上都有了更好的表現(xiàn)。但是改進(jìn)的算法增大了計(jì)算的難度，將會(huì)導(dǎo)致分析的時(shí)間變長(zhǎng)。下一步工作將從縮短時(shí)間的角度來(lái)繼續(xù)研究，深入分析對(duì)分類性能有影響的因素，完善新算法。

參考文獻(xiàn)：

[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] 苗奪謙，衛(wèi)志華.中文文本信息處理的原理與應(yīng)用[M].清華大學(xué)出版社，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] 張浩.基于語(yǔ)義關(guān)聯(lián)的文本分類研究[J].舍肥工業(yè)大學(xué)學(xué)報(bào)，2011.

[6] 張玉芳，萬(wàn)斌候，熊忠陽(yáng).文本分類中的特征降維方法研究[J].計(jì)算機(jī)應(yīng)用研究，2012.29（7）：2541-2543

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