駱魁永

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

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

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

1 改進(jìn)的IG特征選擇算法

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

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

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

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

(1)

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

(2)

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

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

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

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

(3)

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

(4)

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

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

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

(5)

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

(6)

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

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

(7)

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

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

2.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

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

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

(1)宏平均查全率為：

(8)

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

(2)宏平均準(zhǔn)確率為：

(9)

式(9)中，pi表示第i個(gè)類別的準(zhǔn)確率。

(3)宏平均F1為：

(10)

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

2.3 實(shí)驗(yàn)流程

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

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

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

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

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

2.4 結(jié)果分析

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

表2 基于SVM分類算法對比實(shí)驗(yàn)結(jié)果

表3 基于KNN分類算法對比實(shí)驗(yàn)結(jié)果

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

3 結(jié)束語

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