基于信息增益的文本特征選擇方法

王理冬

摘要：在類和特征分布不均時(shí)，傳統(tǒng)信息增益算法的分類性能急劇下降。針對(duì)此問題，提出一種改進(jìn)的基于信息增益的文本特征選擇方法。首先，降低了低頻詞對(duì)特征選擇的影響。其次，使用離散度分析特征詞在類間的文檔頻率，增加波動(dòng)性大的特征詞的權(quán)值。通過對(duì)比實(shí)驗(yàn)分析表明，選取的特征具有更好的分類性能，并且對(duì)于不平衡數(shù)據(jù)集表現(xiàn)也較好。

關(guān)鍵詞：文本分類；信息增益；特征選擇；不平衡數(shù)據(jù)集；離散度分析

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2017）25-0242-03

Abstract： Due to the highly skewed distributions of classes and features， the classification accuracy of algorithms Based on traditional information gain algorithm will decline sharply. This paper proposes a new feature selection method to improve the performance of traditional information gain method. Firstly， the proposed new feature selection method can decrease the interference of low frequency Words to feature selection. Secondly， it analyses the variances of inter-class document frequencies of feature Word that have large variances of inter-class document frequency. Because the feature Word have large variances is more representative than other features when the distributions of classed and features are highly skewed. The comparison experiment on some real data sets shows that the proposed method is more effective and has better classification performance in imbalanced data set as compared with the traditional information gain method.

Key words：Text Classification； Information Gain； Feature Selection； Imbalanced Data Set； Dispersion Analyse

文本分類是文本挖掘的一個(gè)重要部分，其內(nèi)容是按照預(yù)定義的類別將待分類文本進(jìn)行歸類。在這個(gè)過程中，特征選擇和特征提取是文本分類的首要任務(wù)和關(guān)鍵問題，其中文本向量化是基礎(chǔ)。文本向量化的過程中，特征詞的權(quán)重用來衡量該特征對(duì)描述文本內(nèi)容的重要程度。特征詞的權(quán)重計(jì)算的準(zhǔn)確度成為影響文本分類的重要因素。

因?yàn)槲谋緮?shù)據(jù)的半結(jié)構(gòu)化特點(diǎn)，使得文本表示的特征向量高達(dá)幾萬甚至幾十萬維。即使經(jīng)過簡(jiǎn)單的預(yù)處理，如去除停用詞、稀有詞、高頻詞，依舊會(huì)有很多高維數(shù)的特征向量留下。然而向量空間的高維性和文檔向量的稀疏性不僅增加了分類的時(shí)間復(fù)雜度和空間復(fù)雜度，還影響分類精度。因此在文本分類中，特征選擇就顯得尤為重要。

特征選擇主要用于排除特征空間中那些被認(rèn)為關(guān)聯(lián)性不大的特征，通過降低特征空間的維度以及去除噪音特征來提高分類效率和精度。目前常見的特征選擇方法有TFIDF、互信息（MI）、信息增益（IG）、卡方統(tǒng)計(jì)（CHI）等。其中信息增益是一種有效的特征選擇方法。在文獻(xiàn)[1]中作者提出了IG是最好的測(cè)度；在文獻(xiàn)[2]中作者比較了文檔評(píng)論，信息增益、互信息、卡方、特征權(quán)等5種特征選擇方法，其證明了卡方效果最好，文檔頻率，信息增益及卡方之間存在著一定的相關(guān)性；在文獻(xiàn)[3]中作者提出了三種基于特征信息增益權(quán)重的分類算法，通過添加權(quán)重系數(shù)來平衡特征項(xiàng)對(duì)分類的影響，但是由于權(quán)重系數(shù)的設(shè)置是根據(jù)人為的經(jīng)驗(yàn)設(shè)定，所以存在很大的偶然性。在文獻(xiàn)[4]中作者針對(duì)傳統(tǒng)IG 算法過分看重高頻特征項(xiàng)的缺點(diǎn)，提出一種強(qiáng)調(diào)中低頻特征項(xiàng)的改進(jìn)的算法，此算法在一定程度上提高了特征選擇的效率，但算法中沒有考慮到特征項(xiàng)在不同類別的分布差異對(duì)分類能力的影響。在文獻(xiàn)[5]中作者在以上改進(jìn)算法的基礎(chǔ)上，通過按類進(jìn)行特征選擇，利用特征頻率計(jì)算信息增益，再利用離散型分析去除相對(duì)冗余特征。實(shí)驗(yàn)表明該方法能有效的提取特征子集，此算法在一定程度上提高了特征選擇的效率，但算法沒有考慮到特征項(xiàng)在類內(nèi)位置上分布對(duì)算法的影響。信息增益算法在平衡語料的情況下，表現(xiàn)良好，但在處理不平衡語料時(shí)其性能急劇下降。本文針對(duì)以上不足，充分考慮了特征項(xiàng)在類間的頻數(shù)對(duì)分類能力的影響，提出了一種基于信息增益的詞頻改進(jìn)的特征選擇方法，實(shí)驗(yàn)表明該方法比傳統(tǒng)的方法有更好的效果。

1 信息增益簡(jiǎn)介

1.1 熵和信息熵

熵是信息論中一個(gè)非常重要的概念，表示一種能量在空間中分布的均勻程度，其能力分布越均勻，熵就越大。1948年，信息論創(chuàng)始人香農(nóng)將熵應(yīng)用于信息處理中，并提出了“信息熵”的概念。

1.2 信息增益的不足

通過上面的公式發(fā)現(xiàn)，傳統(tǒng)的信息增益方法是從整個(gè)訓(xùn)練集角度根據(jù)特征項(xiàng)的文檔頻數(shù)考察了特征項(xiàng)對(duì)整個(gè)系統(tǒng)的貢獻(xiàn)程度。在不同類中分布相同或相近的特征項(xiàng)信息增益最小，說明該方法適合用來做全局的特征選擇。但該方法過多地關(guān)注了文檔頻數(shù)，對(duì)詞頻的貢獻(xiàn)沒有給予足夠的重視。其次，由于考慮了特征項(xiàng)不出現(xiàn)的情況，當(dāng)每個(gè)類別中文檔數(shù)差別明顯時(shí)，即類別分布不平衡或特征項(xiàng)分布不均衡時(shí)，會(huì)使得在一個(gè)類別中出現(xiàn)次數(shù)不多而在其他類別中頻繁出現(xiàn)的特征項(xiàng)被選取出來，而不傾向于選取在一個(gè)類別中出現(xiàn)較多而在其他類別中出現(xiàn)較少的更具代表性的特征項(xiàng)。endprint

2 K最近鄰算法

KNN算法以其簡(jiǎn)單性、有效性而成為基于向量空間模型（VSM）的最好分類算法之一。

假定文本訓(xùn)練集為S，S 有M 個(gè)類別[c1]，[c2]，……，[cM]，S 的總文本數(shù)為N。在KNN算法的訓(xùn)練階段，首先對(duì)文本訓(xùn)練集S 進(jìn)行分詞，接著對(duì)特征維數(shù)進(jìn)行降維，最后把訓(xùn)練集文本表示為特征向量：[Di]= {[X1]，[X2]，……，[Xn]}T （0

（0

分類文本D 歸屬到隸屬度最大的類別。KNN算法的具體步驟如下：

步驟1 對(duì)文本訓(xùn)練集進(jìn)行中文分詞。

步驟2 對(duì)訓(xùn)練集文本進(jìn)行特征選擇。

步驟3 把訓(xùn)練集文本進(jìn)行向量化。

步驟4 對(duì)待分類文本進(jìn)行步驟1到步驟3的處理工作。

步驟5 利用向量夾角余弦公式來計(jì)算待分類文本D與訓(xùn)練集文本Di的相似度。

步驟6 選出與待分類文本D 最相似K 個(gè)文本作為文本D 的最近鄰。

步驟7 根據(jù)這K 個(gè)最近鄰，計(jì)算待分類文本D 在各個(gè)類別里的隸屬度。我們以所屬類別數(shù)作為其隸屬度。

步驟8 選出隸屬度最大的類別，并將待分類文本D歸入到該類別中。

2 傳統(tǒng)信息增益的改進(jìn)算法

2.1 降低低頻特征的影響

傳統(tǒng)的信息增益方法考慮了特征項(xiàng)出現(xiàn)和不出現(xiàn)兩種情況，但在類別分布不平衡或者特征項(xiàng)在類間分布不平衡的情況下，由于大多數(shù)特征項(xiàng)在某些類別中是不出現(xiàn)的，此時(shí)的信息增益值主要依賴于特征項(xiàng)不出現(xiàn)情況下所帶來的信息量的大小，即此時(shí)信息增益的值由公式的后半部分決定。然而這些不出現(xiàn)的詞對(duì)文檔分類的貢獻(xiàn)遠(yuǎn)小于對(duì)分類的干擾，其大大降低了信息增益方法提取特征的效果，因此我們應(yīng)該去除這些“無用詞”。

2.2 改進(jìn)類間不平衡的影響

通過分析易知，在所有類別中分布均勻的特征項(xiàng)對(duì)系統(tǒng)的分類貢獻(xiàn)最小，也就是說分布不均勻?qū)ο到y(tǒng)的貢獻(xiàn)反而大。

通過離散度分析，利用特征項(xiàng)在每個(gè)類中的文檔頻率，分析每個(gè)特征項(xiàng)在數(shù)據(jù)集中的波動(dòng)性。我們使用方差來做離散度度量。特征項(xiàng)在每個(gè)類間的分布的方差越大，說明該分布越不均勻，即該特征項(xiàng)越集中分布在某個(gè)類，越能代表該類特征，反之，方差越小，該分布越均勻，即該特征項(xiàng)越均勻分布在每個(gè)類中，越不能代表某個(gè)類。設(shè)m表示類別總數(shù)，訓(xùn)練集中特征項(xiàng)t在類別Cj中的文檔頻率為DFtj（在類別Cj中出現(xiàn)特征項(xiàng)t的文檔頻數(shù)除以類別Cj中的總文檔數(shù)），DFt表示特征項(xiàng)的平均文檔頻率，那么特征項(xiàng)t的文檔頻率的方差DVt就表示如下：

2.3 基于IGDV的分類算法流程

中文文本分類的對(duì)象是一篇篇文檔，為了使用機(jī)器學(xué)習(xí)的方法來進(jìn)行分類，首先需要將它進(jìn)行向量化表示。而這一過程，我們首先要進(jìn)行中文分詞，然后去除停用詞，進(jìn)行特征分析提取，選擇適合的特征詞，最后用特征詞向量，來對(duì)文檔進(jìn)行向量化，使用機(jī)器學(xué)習(xí)的分類方法對(duì)其進(jìn)行分類，其整個(gè)算法流程如下：

（1） 對(duì)文檔進(jìn)行中文分詞，去除停用詞，這里主要提取其中的名詞、形容詞等。這個(gè)階段也稱為預(yù)處理。

（2） 選用本文的IGDV算法對(duì)文本進(jìn)行特征選擇。

（3） 使用TFIDF方法構(gòu)建向量空間模型，這里的特征值取TFIDF*IGDV。

（4） 對(duì)訓(xùn)練文本使用前面的特征選擇結(jié)果，進(jìn)行向量化，使用KNN算法進(jìn)行文本分類。

（5） 根據(jù)分類結(jié)果，計(jì)算其評(píng)價(jià)。我們這里采用的評(píng)價(jià)指標(biāo)是MarcoP，MarcoR，MarcoF1。

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

3.1 評(píng)價(jià)指標(biāo)

評(píng)價(jià)文本分類系統(tǒng)好壞的指標(biāo)我們采用MarcoP，MarcoR，MarcoF1。各評(píng)價(jià)參數(shù)定義如下：

3.2 實(shí)驗(yàn)分析

為了驗(yàn)證IGDV特征選擇算法的有效性，本文對(duì)上述的特征選擇方法的分類效率進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)包括分詞、特征選擇和分類測(cè)試幾部分。其中分詞我們采用中科院的漢語詞法分析系統(tǒng)ICTCLAS2015，實(shí)驗(yàn)數(shù)據(jù)集我們選取了復(fù)旦大學(xué)中文語料庫，分類算法我們采用了KNN文本分類器對(duì)樣本進(jìn)行分類，使用java語言編程實(shí)現(xiàn)。

1） 對(duì)平衡數(shù)據(jù)集的實(shí)驗(yàn)

從語料庫中我們選取4000篇文本，包括農(nóng)業(yè)、環(huán)境、經(jīng)濟(jì)、政治、體育各800篇，其中每個(gè)類抽400篇作為訓(xùn)練集，剩下的400篇作為測(cè)試集。選取1000個(gè)特征詞進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)的結(jié)果數(shù)據(jù)如表1所示。

由表1可以看出，在平衡數(shù)據(jù)集下，改進(jìn)后的信息增益方法相比較傳統(tǒng)的信息增益方法在MacroP、MacroR、MacroF1 三個(gè)指標(biāo)上都有一定程度的提高。

2） 對(duì)不平衡數(shù)據(jù)集的實(shí)驗(yàn)

從語料庫中我們選取4000篇文本，包括農(nóng)業(yè)600篇、環(huán)境600篇、經(jīng)濟(jì)1200篇、政治800篇、體育800篇，其中農(nóng)業(yè)200篇、環(huán)境200篇、經(jīng)濟(jì)800篇、政治400篇、體育400篇作為訓(xùn)練集，剩下作為測(cè)試集。選取1000個(gè)特征詞進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)的結(jié)果數(shù)據(jù)如表2所示。

由表2可以看出，在不平衡數(shù)據(jù)集下，改進(jìn)后的信息增益方法相比較傳統(tǒng)的信息增益方法在MacroP、MacroR、MacroF1 三個(gè)指標(biāo)上都有很大的提高。

綜上，改進(jìn)后的信息增益方法不論在平衡數(shù)據(jù)集還是不平衡數(shù)據(jù)集下，相比傳統(tǒng)的信息增益特征選擇方法，都很有很好的表現(xiàn)。

4 結(jié)束語

本文針對(duì)傳統(tǒng)信息增益方法的不足進(jìn)行了改進(jìn)。通過分析，我們?nèi)コ斯街械皖l部分的影響；使用離散性分析，考慮了文檔頻率的波動(dòng)性，降低了類間不平衡的影響。實(shí)驗(yàn)表明，在數(shù)據(jù)集平衡和不平衡的條件下，改進(jìn)后的信息增益特征選擇算法的分類效果上都有很大程度的提高。下一步的工作是將此方法應(yīng)用到我們的系統(tǒng)中，來檢驗(yàn)它的適用性，并進(jìn)一步完善此方法，以進(jìn)一步提高分類效率和分類精度。

參考文獻(xiàn)：

[1] Yang Yiming，Pedersen J Q.A Comparative Study On Feature Selection In Text Categorization[C]//Proceedings of the 14th International Conference on Machine Learning（ICML97）. Nashvillr：Morgan Kaufmann Publisher，1997：412-420.

[2] Ng H， Goh W， Low K. Feature Selection，Perception Learning and A Usability Case Study For Text Categorization[C]//Proceedings of the 20th ACM International Conference on Research and Development in Information Retrieval（SIGIR-97）.1997：67-73.

[3] 李文斌， 劉椿年， 陳嶷瑛. 基于特征信息增益權(quán)重的文本分類算法[J]. 北京工業(yè)大學(xué)學(xué)報(bào)， 2006，32（5）：456-460.

[4] 黃秀麗， 王蔚. 一種改進(jìn)的文本分類特征選擇方法[J]. 計(jì)算機(jī)工程與應(yīng)用， 2009， 45（36）：129-130.

[5] 任永功， 楊榮杰， 尹明飛， 馬名威. 基于信息增益的文本特征選擇方法[J].計(jì)算機(jī)科學(xué)， 2012，39（11）：127-130.

[6] 周萌清. 信息理論基礎(chǔ)[M].北京： 北京航天航空大學(xué)出版社， 2002.

[7] Vapnik V. The nature of statistical learning theory[M].New York：Springer，1999.

[8] 劉慶和， 梁正友. 一種基于信息增益的特征優(yōu)化選擇方法[J]. 計(jì)算機(jī)工程與應(yīng)用，2011，47（11）：130-132.

[9] 裴英博. 中文文本分類中特征選擇方法的研究與實(shí)現(xiàn) [D]. 西北大學(xué)， 2010.

[10] 楊玉珍， 劉培玉， 朱振方等. 應(yīng)用特征項(xiàng)分布信息的信息增益改進(jìn)方法研究[J]. 山東大學(xué)學(xué)報(bào)：理學(xué)版， 2009， 44（11）：48-51.

[11] 郭亞維， 劉曉霞. 文本分類中信息增益特征選擇方法的研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2012， 48（27）：119-122.

[12] 任永功， 楊雪， 楊榮杰， 胡志東. 基于信息增益特征關(guān)聯(lián)樹的文本特征選擇算法[J]. 計(jì)算機(jī)科學(xué)， 2013， 40（10）：252-256.

[13] 張振海， 李士寧， 李志剛， 陳昊. 一類機(jī)遇與信息熵的多標(biāo)簽特征選擇算法[J]. 計(jì)算機(jī)研究與發(fā)展，2013， 50（6）：1177-1184.

[14] 李學(xué)明， 李海瑞， 薛亮， 何光軍. 基于信息增益與信息熵的TFIDF算法[J].計(jì)算機(jī)工程， 2012， 38（8）：37-40.

[15] 張玉芳， 陳小莉， 熊忠陽. 基于信息增益的特征詞權(quán)重調(diào)整算法研究[J]. 計(jì)算機(jī)工程與應(yīng)用， 2007， 43（35）：159-161.

[16] 石慧， 賈代平， 苗培. 基于詞頻信息的改進(jìn)信息增益文本特征選擇算法[J].計(jì)算機(jī)應(yīng)用， 2014， 34（11）：3279-3282.endprint