基于詞頻信息改進(jìn)的IG特征選擇算法在文本分類中的應(yīng)用研究

摘 要：IG算法是一種有效的特征選擇算法，在文本分類研究領(lǐng)域中得到了廣泛應(yīng)用。本文針對(duì)IG算法的不足，提出了一種基于詞頻信息的改進(jìn)方法，分別從類內(nèi)詞頻信息、類內(nèi)詞頻位置分布、類間詞頻信息等方面進(jìn)行了改進(jìn)。通過實(shí)驗(yàn)對(duì)改進(jìn)的算法進(jìn)行了測(cè)試，結(jié)果表明，改進(jìn)的算法相對(duì)傳統(tǒng)算法更有效。

關(guān)鍵詞：詞頻信息；IG算法；特征選擇；文本分類

中圖分類號(hào)：TP391.1 文獻(xiàn)標(biāo)識(shí)碼：A

Research on the Application of the IG Feature Selection Algorithm Based on Word

Frequency Information Improvement in Text Classification

NIU Yuxia

（Nantong Science and Technology Academy，Nantong 226007，China）

Abstract：As an effective feature selection algorithm，the IG algorithm has been widely used in the field of text classification.Aiming at the shortcomings of the IG algorithm，this paper proposes an improved method based on word frequency information，which improves the intra-class frequency information，the intra-class word frequency location distribution and the inter-class word frequency information.Experiments are carried out to test the improved algorithm，and the results show that the improved algorithm is more effective in comparison with the traditional one.

Keywords：word frequency information；IG algorithm；feature selection；text classification

1 引言（Introduction）

隨著信息技術(shù)的飛速發(fā)展，互聯(lián)網(wǎng)信息資源呈爆炸式增長(zhǎng)。面對(duì)海量信息，如何合理管理資源，使人們能夠快速、準(zhǔn)確地獲取有效信息，已經(jīng)成為IT行業(yè)的研究熱點(diǎn)之一[1]。

文本分類技術(shù)是文本信息處理的關(guān)鍵技術(shù)之一，能夠很好地解決上述問題，在文本分類中，通常用向量空間模型來表示結(jié)構(gòu)化文本，其中，文本特征的高維性和特征權(quán)值的稀疏性直接影響文本分類精度。因此，設(shè)計(jì)合理的特征降維方法可以提高文本自動(dòng)分類的效率。特征選擇模式是常用的文本特征降維方式。該模式計(jì)算復(fù)雜度低，容易理解。特征選擇的主要方法有：文檔頻度（Document Frequency，DF）、互信息（Mutual Information，MI）、文本證據(jù)權(quán)（Weight of Evidence，WE）、統(tǒng)計(jì)量（Chi-square，CHI）、期望交叉熵（Expected Cross Entropy，ECE）、信息增益（Information Gain，IG）等。相關(guān)研究表明[2，3]，在信息類別分布均衡的情況下，信息增益優(yōu)勢(shì)明顯，但在類偏斜條件下，信息增益的分類效果就會(huì)下降。就信息增益的不足，探索相應(yīng)的改進(jìn)方法，提高文本分類的性能，有重要的現(xiàn)實(shí)意義。

2 信息增益文本特征選擇算法（Information gain

text feature selection algorithm）

信息增益（Information Gain，IG）的評(píng)估方法是以熵為理論基礎(chǔ)的[4]。熵越大，表明體系分布不確定、混亂。設(shè)X是隨機(jī)變量，它可能有n個(gè)取值，，…，，每個(gè)取值取到的概率分別為，，…，，則X的信息熵為：

（1）

當(dāng)Y確定以后，則X的熵為

（2）

信息增益是熵的差值，表示在去掉變量的不確定性后得到的信息量，表示為：

（3）

IG是針對(duì)特征項(xiàng)而言的。設(shè)ω為特征項(xiàng)，C為文本類別，用ω在C類中是否出現(xiàn)所帶來的信息量來確定ω對(duì)C的信息增益值，如式（4）所示。

（4）

其中，n表示總的文檔類別數(shù)，表示在文檔集合中屬于類的文檔出現(xiàn)概率，表示含有特征項(xiàng)的文本在文檔集合中出現(xiàn)的概率，表示不含特征項(xiàng)在文檔集合中出現(xiàn)的概率，表示含特征項(xiàng)屬于類別的概率，表示含特征項(xiàng)不屬于類別的概率。

3 改進(jìn)信息增益算法（Improved information gain

algorithm）

3.1 基于類內(nèi)詞頻信息改進(jìn)IG算法

傳統(tǒng)信息增益算法中計(jì)算的概率P均是基于文檔數(shù)量的，沒有考慮特征項(xiàng)詞頻因素[5]。比如，特征項(xiàng)中的與在類別中的大部分文本中出現(xiàn)，在其他類別中基本不出現(xiàn)，那么，和可能是的特征項(xiàng)。由式（3）計(jì)算得到的兩個(gè)特征項(xiàng)與類別之間的IG值應(yīng)該基本接近。但是，如果特征項(xiàng)在類別中出現(xiàn)的次數(shù)遠(yuǎn)遠(yuǎn)大于特征項(xiàng)時(shí)，即特征項(xiàng)對(duì)的分類能力遠(yuǎn)遠(yuǎn)大于特征項(xiàng)，由式（3）計(jì)算得到的兩個(gè)特征項(xiàng)IG值仍然接近。因此，在評(píng)估特征項(xiàng)對(duì)文檔類別的分類能力時(shí)，傳統(tǒng)的信息增益算法考慮了在類別中出現(xiàn)特征項(xiàng)文檔的數(shù)量，而沒有考慮特征項(xiàng)在中各個(gè)文檔中出現(xiàn)的次數(shù)。endprint

由上述情況可知，某一個(gè)特征項(xiàng)在某一個(gè)文檔類別中出現(xiàn)的次數(shù)越多，則該特征項(xiàng)對(duì)文檔類別而言分類能力就越強(qiáng)，該特征項(xiàng)的IG應(yīng)該放大，因此，考慮為特征項(xiàng)增加權(quán)重參數(shù)，出現(xiàn)頻數(shù)越大，則分配較大的權(quán)重值。記特征項(xiàng)集合，文本類別中的文本有，其中，是類別中包含文檔的總數(shù)。設(shè)特征項(xiàng)在文檔（屬類別）出現(xiàn)的頻數(shù)為，那么權(quán)重參數(shù)為：

（5）

不同類別中的文檔數(shù)量也有所不同，因此，將式（5）進(jìn)一步做歸一化處理。

（6）

由改進(jìn)的模型可以看出，特征項(xiàng)在文檔中出現(xiàn)的頻數(shù)與其權(quán)重值呈正比關(guān)系，即某一特征項(xiàng)在某類別中出現(xiàn)越頻繁，則分類能力就越強(qiáng)。

3.2 基于類內(nèi)詞頻位置分布信息改進(jìn)IG算法

相關(guān)研究表明，在文本類別中分類能力越強(qiáng)的特征項(xiàng)，不僅出現(xiàn)頻數(shù)要大，而且在該類別中的分布位置應(yīng)該均勻[6，7]。比如，在類別中都出現(xiàn)了特征項(xiàng)和，特征項(xiàng)在每個(gè)文檔中都出現(xiàn)，而且出現(xiàn)頻數(shù)接近，分布均勻，特征項(xiàng)只在個(gè)別文檔中出現(xiàn)，而且出現(xiàn)頻數(shù)很高，在其他文檔中出現(xiàn)頻數(shù)很少，即特征項(xiàng)在類中呈偏斜分布。在這種情況下，我們認(rèn)為特征項(xiàng)對(duì)類別的分類能力更強(qiáng)。但是，公式（3）沒有考慮這一因素，計(jì)算得到的結(jié)論恰恰相反。

因此，基于特征項(xiàng)在類內(nèi)文本分布信息進(jìn)行改進(jìn)，在模型中引入樣本方差。樣本方差在統(tǒng)計(jì)學(xué)中用來表示樣本之間的離散程度，方差越大，表示樣本分布越不均勻，即越偏斜；方差越小，表示樣本與其均值之間的偏差越小，分布越均勻。在本文中，表示特征項(xiàng)在同一類別各個(gè)文檔中頻數(shù)的分布情況。

記特征項(xiàng)在類別的某一文檔中出現(xiàn)的頻數(shù)為，那么每個(gè)頻數(shù)之間的樣本方差可表示為

（7）

特征項(xiàng)在文檔類別中出現(xiàn)頻數(shù)的方差與其分類能力成反比，即方差越小，分類能力越強(qiáng)。所以，將式（7）表示的方差參數(shù)進(jìn)行進(jìn)一步修正，如式（8）所示。

（8）

在文檔類別中，特征項(xiàng)每個(gè)文本中分布越均勻，值就越大，相應(yīng)的分類能力也就越強(qiáng)。

3.3 基于類間詞頻信息改進(jìn)IG算法

特征項(xiàng)在不同的文本類別中出現(xiàn)的頻數(shù)也能反應(yīng)其相對(duì)文本類別的分類能力[8]。如果特征項(xiàng)在類別中出現(xiàn)頻繁，且分布均勻，在其他類別中出現(xiàn)很少，那么表現(xiàn)出對(duì)類別較強(qiáng)的分類能力；相反，如果特征項(xiàng)在所有文檔類別中都頻繁出現(xiàn)，那么表現(xiàn)出的分類能力就較差。仍然以特征項(xiàng)在類別中的詞頻方差作為權(quán)重參數(shù)，特征項(xiàng)在不同類別中的詞頻數(shù)方差越大，則分類能力越強(qiáng)。

設(shè)特征項(xiàng)在類別的所有文檔中出現(xiàn)的頻數(shù)為，則特征項(xiàng)在每個(gè)類別中的頻數(shù)間樣本方差可表示為

（9）

在此基礎(chǔ)上，將參數(shù)做歸一化處理，如式（10）所示。

（10）

參數(shù)體現(xiàn)了特征項(xiàng)在不同文本類別中出現(xiàn)頻數(shù)的分布情況，分布越偏斜，則分類能力更強(qiáng)，反之則弱。

綜上所述，通過引入、、三個(gè)權(quán)重參數(shù)，對(duì)傳統(tǒng)IG算法進(jìn)行了優(yōu)化，得到改進(jìn)的模型如式（11）所示。

（11）

改進(jìn)的算法綜合考慮了類內(nèi)詞頻信息、類內(nèi)詞頻位值分布信息、類間詞頻分布信息三個(gè)因素的影響，即特征項(xiàng)在類內(nèi)少數(shù)文檔類別中出現(xiàn)頻數(shù)越高，分類能力越強(qiáng)；特征項(xiàng)在類內(nèi)出現(xiàn)頻數(shù)高，且分布均勻，分類能力越強(qiáng)；特征項(xiàng)在類別間分布越偏斜，分類能力越強(qiáng)。實(shí)驗(yàn)表明，改進(jìn)的特征選擇算法IGimp相對(duì) IG效果更好。

4 實(shí)驗(yàn)過程與結(jié)果分析（Experiment process and

result analysis）

4.1 選取實(shí)驗(yàn)文本

本文對(duì)改進(jìn)的模型進(jìn)行了分本分類實(shí)驗(yàn)，實(shí)驗(yàn)數(shù)據(jù)來自復(fù)旦大學(xué)李榮陸教授提供的語料庫，包括教育、經(jīng)濟(jì)、環(huán)境、計(jì)算機(jī)、醫(yī)藥、藝術(shù)、交通、政治、體育、軍事10個(gè)主題類別，選取926篇作為測(cè)試集，1851篇文本作為訓(xùn)練集，具體分布情況如表1所示。

使用中科院ICTCLAS分詞系統(tǒng)進(jìn)行分詞處理，剔除無用詞和停用詞，使用文中改進(jìn)的模型進(jìn)行特征提取，使用KNN分類算法進(jìn)行測(cè)試。

4.2 確定實(shí)驗(yàn)K值

KNN分類算法中的K值是不確定的，需要通過實(shí)驗(yàn)，選擇準(zhǔn)確率最高K的取值。用傳統(tǒng)IG算法，特征提取維數(shù)1000，K分別取5、8、10、12、14、18。從圖1中可以看出，當(dāng)K取12時(shí)，分類器準(zhǔn)確率達(dá)到最高，所以，在對(duì)比實(shí)驗(yàn)中，K的值取12。

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

本文實(shí)驗(yàn)比較了改進(jìn)算法IGimp與傳統(tǒng)IG算法的分類效果，采用KNN分類算法、TF-IDF加權(quán)算法，使用查準(zhǔn)率P、查全率R和F1測(cè)試值作為分類效果的評(píng)估指標(biāo)。

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

查全率R=正確分類文本數(shù)/類內(nèi)文本數(shù)

F1=2×P×R/（P+R）

實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果如表2所示，其中，P、R和F1表示IG算法分類評(píng)估值，P-new、R-new和F1-new表示改進(jìn)算法IGimp的分類評(píng)估值。

為直觀比較，將表2中的數(shù)據(jù)用直方圖表示，查準(zhǔn)率P直方圖如圖2所示。從圖中可以看出，改進(jìn)的算法的查準(zhǔn)率在實(shí)驗(yàn)文本的十個(gè)類別中都有所提高，平均提高率為4.27%，尤其是在教育、交通類中，分別提高了10.84%和6.75%。

圖3為查全率R對(duì)比直方圖，改進(jìn)的算法在查全率方面平均提高率為3.04%，經(jīng)濟(jì)、醫(yī)藥、藝術(shù)類別的查全率高于平均提高率，分別為7.24%、6.96%、4.94%，教育類的查全率稍有下降。

圖4為F1評(píng)估值對(duì)比直方圖，改進(jìn)的算法F1值在十個(gè)種類中都有提高，平均提高率為3.8%，醫(yī)藥、經(jīng)濟(jì)、教育類有明顯提高，分別提高了5.96%、5.88%、5.24%。

筆者利用宏平均查準(zhǔn)率、宏平均查全率、宏平均F1三個(gè)評(píng)估指標(biāo)，對(duì)改進(jìn)算法IGimp與傳統(tǒng)IG算法F1做了比較，可以從整體上看出兩種算法的分類效果。具體數(shù)據(jù)如表3所示。endprint

從表3中可以看出，相比較IG算法，IGimp在宏平均查準(zhǔn)率、宏平均查全率和宏平均F1方面分別提高了3.12%、2%、2.24%。

綜合分析改進(jìn)IGimp算法的分類效果，在查準(zhǔn)率、查全率和F1方面比IG算法的效果要好，僅在個(gè)別類別的查全率略有下降。從整體上看，改進(jìn)IGimp算法的文本分類效果優(yōu)于傳統(tǒng)IG算法。

5 結(jié)論（Conclusion）

本文針對(duì)信息增益算法在特征項(xiàng)頻數(shù)分布方面的不足進(jìn)行了改進(jìn)，引入了三個(gè)權(quán)重參數(shù)，分別從類內(nèi)詞頻信息、類內(nèi)詞頻分布、類間詞頻分布三個(gè)方面進(jìn)行了改進(jìn)，使得優(yōu)化的信息增益模型IGimp有更強(qiáng)的類別特征選擇能力。通過對(duì)文本樣本分類實(shí)驗(yàn)對(duì)比，證明了改進(jìn)的IGimp算法有更強(qiáng)的文本分類能力。

參考文獻(xiàn)（References）

[1] Ghosh A K，Chaudhuri P，Murthy C A.Multiscale classi-fication using nearest neighbor density estimates[J].IEEETransactions on Systems，Man，and Cybernetics-part B：Cybernetics，

2006，36（5）：1139-1148.

[2] Liu L，Ren J Y，Zhou J，et al.Carrier frequency offset and I/Q imbalance compensation for MB-OFDM based UWB system[J].Wireless Personal Communications，2013，71（2）：1095-1107.

[3] Sharma R.Lalitha H.Kumar N.Design and development of nono data aided estimation algorithm for carrier frequency-offset and I/Q imbalancing in OFDM-based systems[C].Wireless and Optical Communications Networks，2013：1-4.

[4] 石慧.基于特征選擇和特征加權(quán)算法的文本分類研究[D].山東師范大學(xué)，2015.

[5] 劉海峰，劉守生，宋阿羚.基于詞頻分布信息的優(yōu)化IG特征選擇方法[J].計(jì)算機(jī)工程與應(yīng)用，2017，53（4）：113-116；122.

[6] 黃志艷.一種基于信息增益的特征選擇方法[J].山東農(nóng)業(yè)大學(xué)學(xué)報(bào)，2013，44（2）：252-256.

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

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

作者簡(jiǎn)介：

牛玉霞（1981-），女，碩士，講師.研究領(lǐng)域：計(jì)算機(jī)應(yīng)用技術(shù)，物聯(lián)網(wǎng)技術(shù).endprint