一種面向不均衡數(shù)據(jù)集的IG特征選擇改進算法

駱魁永

(信陽農(nóng)林學院 信息工程學院，河南 信陽 464000)

隨著網(wǎng)絡(luò)技術(shù)的迅速發(fā)展，當前社會已步入大數(shù)據(jù)時代，文本內(nèi)容分析已成為實現(xiàn)大數(shù)據(jù)價值發(fā)現(xiàn)的有效手段，文本分類[1-2]作為大數(shù)據(jù)價值挖掘的關(guān)鍵技術(shù)，廣泛應(yīng)用于信息檢索、內(nèi)容信息過濾、自然語言處理和信息組織與管理等多個領(lǐng)域。然而，在對海量電子文檔的分類中，發(fā)現(xiàn)數(shù)據(jù)不均衡分布的情況普遍存在，數(shù)據(jù)集中不同類別之間的文本數(shù)量可能存在數(shù)量級的差距，這給文本分類帶來了新的挑戰(zhàn)。特征選擇作為文本分類的重要一環(huán)，選擇算法的優(yōu)良也直接影響分類模型的構(gòu)建以及分類的準確性。目前，文本分類研究中常用的特征選擇方法有：互信息、文檔頻率、信息增益、期望交叉熵、開方擬合檢驗、特征權(quán)等。Ng[3]比較了互信息(MI)、開方擬合檢驗(CHI)、特征權(quán)(TS)、文檔頻率(DF)和信息增益(IG)五種特征選擇算法，得出IG、CHI和DF比MI和TS效果好的結(jié)論。Yang等[4]研究得出IG是最有效的特征選擇算法之一。目前IG算法已成為文本分類研究中常用的特征選擇算法，因此，在不均衡數(shù)據(jù)集中，尋找該方法不足，并做出有效改進，進而提高特征提取的效率具有非常重要的現(xiàn)實意義。

傳統(tǒng)的IG特征選擇方法在特征項選擇的過程中往往會出現(xiàn)類別不平衡問題，導(dǎo)致分類器對小類別的分類效果較差。目前，一些學者指出了IG特征選擇算法存在的缺點，并提出了相應(yīng)的改進措施。文獻[5-6]指出在不均衡的數(shù)據(jù)集中，由于不同類別樣本數(shù)目相差很大，那些對于小類分布影響較大的特征項其信息熵變化值不如大類影響大的特征項顯著，針對這一問題，通過對條件熵部分增加了權(quán)重系數(shù)，來改進IG算法；文獻[7]提出改進的信息增益算法，通過添加權(quán)重值來平衡正、負相關(guān)特征，由于權(quán)重值需要人為根據(jù)經(jīng)驗設(shè)定，設(shè)定的細微不同可能導(dǎo)致較大的分類差異，而且簡單設(shè)定權(quán)重值并不適用于多種應(yīng)用場景；文獻[8-9]在以上改進算法的基礎(chǔ)上，通過引入特征分布差異因子、類內(nèi)和類間加權(quán)因子，提出一種加權(quán)的IG-C改進算法，該方法比較全面地考慮到了詞頻對特征提取的作用；但該算法沒有考慮數(shù)據(jù)集的不均衡性和特征項頻數(shù)在類內(nèi)分布情況對分類的影響。本文針對上述改進算法的不足，引入了類內(nèi)詞頻加權(quán)因子、類內(nèi)詞頻分散度加權(quán)因子和類間詞頻集中度加權(quán)因子對傳統(tǒng)IG算法進行改進，提出了一種改進的IG特征選擇方法。通過選取復(fù)旦大學計算機信息與技術(shù)系整理的語料庫中部分文檔[10]，采用SVM和KNN兩種分類算法進行實驗，實驗結(jié)果表明，本文改進的特征選擇方法相較于其它已改進的算法在不均衡數(shù)據(jù)集上有較好的的分類效果。

1 改進的IG特征選擇算法

1.1 引入類內(nèi)詞頻加權(quán)因子

傳統(tǒng)的IG算法只考慮了特征項在所有文檔出現(xiàn)的次數(shù)，而沒有考慮特征項在指定類中出現(xiàn)的次數(shù)，即IG算法只考慮了特征項的文檔頻數(shù)，沒有考慮特征項在指定類中的詞頻，從而放大了低頻詞對指定類別的分類價值。

例如：假設(shè)在類別Ci中，特征項tp和tq在類別Ci中大多數(shù)文本出現(xiàn)且在其它類別中很少出現(xiàn)甚至不出現(xiàn)，那么這兩個特征項都有可能是類別Ci的特征項，根據(jù)IG公式計算出的兩個特征項與類別之間的IG值應(yīng)該基本相近。然而在Ci類文本內(nèi)部當tp出現(xiàn)的頻數(shù)遠大于tq出現(xiàn)的頻數(shù)，也就是說特征項tp對Ci類的分類價值遠大于特征項tq時，利用IG算法計算的IG值仍相近。因此可以得出影響特征項t對C類文檔分類能力有兩個因素：包含特征項t的文檔在類別C中的頻數(shù)與特征項t在C類內(nèi)各個文檔的詞頻數(shù)，傳統(tǒng)的IG算法只考慮了第一個因素，卻沒有考慮第二個因素。

由于在不均衡數(shù)據(jù)集中，各類別之間文檔頻數(shù)差異比較大，僅僅通過詞頻數(shù)來度量特征項的頻繁程度，算法往往會更傾向于選擇大類的特征項，這對小類別的特征項選擇是不公平的，影響了小類別的分類效果。為了避免對大類的特征項的這種選擇傾向性，本文引入類內(nèi)詞頻加權(quán)因子來度量特征項在不平衡數(shù)據(jù)集的頻繁程度，表示如公式(1)所示：

(1)

考慮到在不均衡數(shù)據(jù)集中，不同類別的文檔數(shù)量的差異性將式(1)做歸一化處理：

(2)

其中：m是特征向量的緯度閾值；tf(Ci,wj)表示特征項wj在類別Ci中出現(xiàn)的次數(shù)。類內(nèi)詞頻加權(quán)因子α度量了在不平衡數(shù)據(jù)集下特征項w在某一類別C中出現(xiàn)的頻繁程度，顯然，頻數(shù)越高的特征項w其對應(yīng)的權(quán)重α越大，即式(1)反映了類內(nèi)出現(xiàn)頻數(shù)越大的特征項其具有的分類價值越大。

1.2 引入類內(nèi)詞頻分散度加權(quán)因子

傳統(tǒng)的IG模型沒有考慮特征項在類內(nèi)各文檔的分布情況。根據(jù)先前學者的研究可知，具有分類價值越大的特征項，其在指定類別中不僅出現(xiàn)的頻數(shù)大，而且在該類各文檔中要均勻地出現(xiàn)，若只出現(xiàn)在該類的個別文檔而在其它文檔中很少出現(xiàn)，則表明該特征項具有的分類價值就比較低。

例如：特征項tp在類別Ci的文本中均勻出現(xiàn)，特征項tq僅在類別Ci的個別文本中出現(xiàn)，且出現(xiàn)的頻數(shù)比tp大。在這種情況下，由于特征項tp在類內(nèi)均勻出現(xiàn)，特征項tp對類別Ci的分類價值更高些，但是通過傳統(tǒng)的IG算法卻得到相反的結(jié)果。為了解決上述問題，本文引入類內(nèi)詞頻分散度加權(quán)因子β，由樣本方差的思想可知，特征項在某一類別文檔中分布越均勻，總體方差就越小，其分類能力越強，反之，樣本方差值越大，其分類能力越弱。記tf(tk,dij)表示特征詞tk在類別Ci中的文檔dij中出現(xiàn)的次數(shù)，Mi表示類別Ci中的文檔數(shù)，那么各個頻數(shù)之間的樣本方差可以表示為：

(3)

由于特征項在類內(nèi)分布越均勻其出現(xiàn)的頻數(shù)方差越小，即特征項的分類能力與方差值成反比關(guān)系。因此需對上述參數(shù)歸一化后還應(yīng)修正：

(4)

其中：m是特征向量的緯度閾值。類內(nèi)詞頻分散度加權(quán)因子β度量了在不平衡數(shù)據(jù)集下特征項tk在類內(nèi)分布情況，顯然，特征項tk在類別Ci中各文檔之間分布越均勻，β的值就越大，該特征項對該類的分類價值就越高。

1.3 引入類間詞頻集中度加權(quán)因子

除了特征項的頻數(shù)和特征項在類內(nèi)分布情況之外，特征項的頻數(shù)在類間的分布差異也能體現(xiàn)特征項對類別的分類能力。假設(shè)一個特征項在每一個類別都出現(xiàn)很多次，而另外一個特征項只在某一個類中均勻出現(xiàn)且在其它類別中出現(xiàn)很少或則幾乎不出現(xiàn)，顯然后一個特征項要比前一個特征項具有更高的分類價值，即類別間特征項的頻數(shù)方差與特征項的分類能力成正比。記n是類別總數(shù)；tf(Ci,wj)表示特征項wj在類別Ci中出現(xiàn)的次數(shù)，那么特征項wj在各個類別Ci中出現(xiàn)頻數(shù)之間的樣本方差可以表示為：

(5)

考慮到在不均衡數(shù)據(jù)集中，不同類別的文檔數(shù)量的差異性將式(5)做歸一化處理：

(6)

其中：m是特征向量的緯度閾值。類間詞頻集中度加權(quán)因子λ度量了在不平衡數(shù)據(jù)集下特征項tk在類間的頻數(shù)分布情況，顯然，特征項tk在類間的頻數(shù)分布越集中，λ的值就越大，該特征項對分類價值就越高。

在Im-IG特征選擇算法基礎(chǔ)上，引入上述所得權(quán)重參數(shù)α、β、λ進行修正，得到改進算法：

(7)

式(7)綜合考慮了數(shù)據(jù)集的不均衡性與特征項頻數(shù)對分類的影響，對傳統(tǒng)IG算法優(yōu)化得到改進的特征選擇算法。

2 實驗結(jié)果與分析

2.1 實驗數(shù)據(jù)

為了驗證本文所提方法的合理性，選用復(fù)旦大學計算機信息與技術(shù)系國際數(shù)據(jù)庫中心自然語言處理小組整理的語料庫。在語料庫的20個類別當中，選取了計算機、藝術(shù)、經(jīng)濟、政治、體育、環(huán)境和歷史這7個類別，選取類別中文本分布呈現(xiàn)較大差異性，其中最大類中包含1600個文本，最小類中只包含123個文本，具體文本分布如表1所示。

表1 不同類別文檔數(shù)選取情況

2.2 評價指標

目前對分類器性能評價指標通常選取查全率、準確率、F1三項指標。由于在不均衡數(shù)據(jù)集的分類中，分類結(jié)果極易偏向大類，如果仍然采取傳統(tǒng)評價指標，則無法真實評價分類器的實際性能。本文采用宏平均查全率、宏平均準確率以及宏平均F1指標對分類結(jié)果進行評價。

(1)宏平均查全率為：

(8)

式(8)中，ri表示第i個類別的查全率；|K|表示類別總數(shù)。

(2)宏平均準確率為：

(9)

式(9)中，pi表示第i個類別的準確率。

(3)宏平均F1為：

(10)

式(10)中，F(xiàn)1i表示第i個類別的F1值。

2.3 實驗流程

(1)文檔預(yù)處理過程的分詞選用jieba分詞工具。

(2)對文檔集中的每一個待求特征，分別使用文獻[5]改進的Im-IG算法、文獻[8]提出的IG-C算法以及本文改進的IG算法計算其信息增益值。

(3)每一種算法均分別選取信息增益值最大的前50、100、200、400、800、1600個特征詞構(gòu)成50、100、200、400、800、1600維的特征向量空間。

(4)使用文本分類中常用的TF-IDF權(quán)重算法計算向量空間中各特征值的權(quán)重值。

(5)本文采用Weak[11]數(shù)據(jù)挖掘開源平臺進行文本分類實驗，輸入各分檔的特征權(quán)重值，分別使用兩種經(jīng)典的算法SVM(選用線性核函數(shù))和KNN算法進行分類實驗。將文檔集平均分成10份，采用十折交叉驗證方法，分別選取50、100、200、400、800、1600個特征值進行實驗。

2.4 結(jié)果分析

表2、3列出了使用Im-IG算法、IG-C算法以及本文算法在實驗數(shù)據(jù)上進行特征選擇，并分別使用SVM和KNN進行分類的實驗結(jié)果?？梢钥闯觯斕卣鲾?shù)目小于800時，使用本算法進行特征選擇獲得的宏平均值比其它兩種方法提高了5%左右，特征數(shù)量為800時獲得M_F1值最大，特征數(shù)超過800時其M_F1值趨于穩(wěn)定；當選擇的特征數(shù)為400時，采用本文算法優(yōu)勢比較明顯，已經(jīng)達到了其它兩種算法特征數(shù)為800時的宏平均準確率和宏平均查全率，表明本文方法能夠更早地獲得較好的分類效果。

表2 基于SVM分類算法對比實驗結(jié)果

表3 基于KNN分類算法對比實驗結(jié)果

改進算法在傳統(tǒng)算法基礎(chǔ)上，充分考慮了數(shù)據(jù)集不均衡、特征項頻數(shù)在類內(nèi)、類內(nèi)分布情況以及類間分布情況對算法的影響，對傳統(tǒng)IG算法的參數(shù)進行了修正。綜合上述實驗結(jié)果來看，本文提出的改進的IG特征選擇算法在不均衡數(shù)據(jù)集上文本分類上效果比較理想。

3 結(jié)束語

數(shù)據(jù)集的不均衡在文本分類中是一個普遍存在的問題。本文針對傳統(tǒng)的IG特征選擇算法的缺陷，以及對已有改進算法深入分析的基礎(chǔ)上，充分考慮了數(shù)據(jù)集的不均衡與特征項頻數(shù)對分類的影響，引入類內(nèi)詞頻加權(quán)因子、類內(nèi)詞頻分散度加權(quán)因子和類間詞頻集中度加權(quán)因子，提出了一種改進的IG特征選擇方法，降低了類別分布不均勻和特征分布不均勻在分類中所帶來的干擾。實驗結(jié)果表明，改進后的特征選擇效果相對于傳統(tǒng)算法和其它改進算法在不均衡數(shù)據(jù)集上的分類效果明顯提高。