基于差異度量和互信息的文本特征選擇算法

潘曉英, 陳 柳, 王 昊, 趙逸喆, 孫 俊

(1. 西安郵電大學(xué) 計(jì)算機(jī)學(xué)院, 陜西 西安710121；2. 西安郵電大學(xué) 陜西省網(wǎng)絡(luò)數(shù)據(jù)分析與智能處理重點(diǎn)實(shí)驗(yàn)室， 陜西 西安 710121；3. 廈門優(yōu)萊柏網(wǎng)絡(luò)科技有限公司, 福建 廈門 361008)

文本分類技術(shù)[1]是處理文本信息的關(guān)鍵技術(shù)，已被廣泛應(yīng)用在垃圾郵件檢測(cè)和電子郵件分類等日常生活中。在文本分類過程中，文檔通常被建模為向量空間，每個(gè)詞被視為特征。過多的特征不但會(huì)增加計(jì)算時(shí)間，而且會(huì)降低分類準(zhǔn)確性。通過特征選擇去除冗余特征，選擇具有代表性的特征，可降低文本特征空間的高維度。

文本分類中主要的特征選擇方法有過濾式、封裝式和嵌入式。其中過濾式特征選擇計(jì)算時(shí)間復(fù)雜度低、操作簡(jiǎn)便，應(yīng)用較為廣泛。利用改進(jìn)的卡方檢驗(yàn)(chi-square statistics，CHI)[2]和互信息結(jié)合的方法對(duì)特征集進(jìn)行初步篩選，并載入MapReduce模型，可增加文本分類的準(zhǔn)確度且縮短數(shù)據(jù)處理時(shí)間[3]；CHI通過添加類內(nèi)和類間分布因子，可降低低頻詞以及特征詞對(duì)類間均勻分布的干擾[4]；段落類別特征選擇(feature selection paragraph category，F(xiàn)SPC)[5-6]將特征詞的段落頻率與特征詞類別的分布程度進(jìn)行融合，該度量標(biāo)準(zhǔn)能夠描述特征詞在文檔中的均勻分布程度；CHI優(yōu)化算法針對(duì)分布不均勻的特征數(shù)據(jù)集，適當(dāng)改善了集中在少量文檔中的單詞的權(quán)重[7-8]；基于文檔頻率的歸一化差異度量 (normalized difference measure，NDM)通過對(duì)真正類率和假正類率之間的絕對(duì)差異與兩者之間最小值的比值進(jìn)行研究，優(yōu)化了類別之間不平衡問題[9]。但是，上述方法均未考慮詞頻以及如何定義準(zhǔn)確的特征。

針對(duì)忽略詞頻以及類別與特征詞關(guān)系等問題，本文提出一種基于差異度量和互信息的文本特征選擇算法。充分考慮文檔頻率、特征詞頻率、文檔類別與特征詞之間的關(guān)聯(lián)度等方面，引入詞頻信息和特征分布系數(shù)，以期提高文本分類的準(zhǔn)確率。

1 基本原理

1.1 歸一化差異度量

NDM算法[9]通過使用真正類率rt和假正類率rf之間的絕對(duì)差異與兩者之間最小值的比值表示特征詞t排序的優(yōu)先級(jí)。將rt和rf最小值引入算法中，不僅克服了數(shù)據(jù)集類別之間數(shù)據(jù)不平衡的問題且有效提高了分類的準(zhǔn)確性。NDM算法表達(dá)式為

(1)

其中：A表示包含特征詞t且屬于正類的文檔數(shù)；B表示不包含特征詞t且屬于正類的文檔數(shù)；C表示包含特征詞t且不屬于正類的文檔數(shù)；D表示不包含征詞t且不屬于正類的文檔數(shù)。

NDM算法進(jìn)行特征選擇時(shí)，在考慮文檔數(shù)量的同時(shí)引入類別信息，計(jì)算時(shí)間復(fù)雜度較低且操作簡(jiǎn)單，對(duì)理解數(shù)據(jù)方面也占有優(yōu)勢(shì)，但忽略了特征與類別之間的關(guān)聯(lián)度。

1.2 互信息

互信息[10](mutual information，MI)在信息論中用于判斷兩個(gè)信號(hào)之間的相關(guān)性，在文本分類中作為特征選擇算法，主要表示特征詞和類別之間的相關(guān)程度。特征詞t與文本類別c之間的關(guān)聯(lián)度公式為

(2)

其中：P(c)表示屬于類別c的文檔占所有文檔的概率；P(t)表示包含特征詞t的文檔占所有文檔的頻率；P(t,c)表示文檔包含特征詞t并且屬于類別c的概率；P(t|c)表示文檔在屬于類別c的條件下包含特征詞t的概率。

MI特征選擇算法考慮了類內(nèi)不同特征出現(xiàn)的頻度，充分體現(xiàn)了特征對(duì)類別的表現(xiàn)能力，及文本類別與特征詞的關(guān)聯(lián)度。由式(2)可以看出，若特征詞頻率較低，則互信息明顯偏高，傾向低頻特征詞，特征分類不準(zhǔn)確。

2 文本特征提取算法的改進(jìn)

NDM特征選擇算法考慮了文檔頻率，但忽略了詞頻以及特征詞和類別之間的關(guān)聯(lián)度；MI特征選擇算法考慮了文本類別與特征詞的關(guān)聯(lián)度，但傾向低頻特征詞，即特征詞頻率較低，則互信息偏高。因此，本文充分考慮文檔頻率、特征詞頻率、文檔類別與特征詞之間的關(guān)聯(lián)以及準(zhǔn)確的特征詞只出現(xiàn)在固定類別等4個(gè)方面，提出一種基于差異度量和互信息文本特征選擇算法 (normalized difference measure plus，NDMP)。融合歸一化差異度量和互信息概念，引入詞頻信息和特征分布系數(shù)，對(duì)特征選擇過程進(jìn)一步優(yōu)化。

設(shè)特征詞為t，文檔為d，文本類別為c，N為總類別數(shù)。詞頻信息和特征分布系數(shù)的計(jì)算表達(dá)式分別為

(3)

(4)

其中：ft(t,c)表示t在類別c出現(xiàn)的次數(shù)；fd(t,c)表示文檔d包含t且屬于類別c的文檔數(shù)；fd(t)表示所有文檔d包含t的文檔數(shù)。若fd(t,c)接近fd(t)，C趨近于1時(shí)，則說明特征詞t對(duì)類別c表征效果較好，反之亦然。Ft適當(dāng)?shù)卦黾恿烁哳l特征所占的比重，C衡量了特征詞在一個(gè)類別的權(quán)重。

在歸一化度量NDM的基礎(chǔ)上融合MI并增添詞頻信息和特征分布系數(shù)，得到改進(jìn)的文本特征選擇算法表達(dá)式為

DMNP=DMN×I(t,c)×Ft×C。

(5)

根據(jù)式(5)對(duì)特征詞進(jìn)行優(yōu)先級(jí)排序，完成文本特征選擇。通過引入Ft和C，特征詞t對(duì)類別c表征效果越好，區(qū)分類別能力就越強(qiáng)。

NDMP算法具體步驟如下。

輸入數(shù)據(jù)集Q，其中文檔類別為c且c∈Q，文檔中特征詞為t且t∈c。

輸出特征詞優(yōu)先級(jí)排序

步驟1判斷數(shù)據(jù)集Q中是否包含特征詞t及是否屬于正類的文檔數(shù)。

步驟2根據(jù)式(1)計(jì)算數(shù)據(jù)集Q的rt和rf，得出DMN，式(2)計(jì)算得出I(t,c)。

步驟3根據(jù)式(3)和式(4)分別計(jì)算詞頻信息Ft和特征分布系數(shù)C。

步驟4根據(jù)式(5)對(duì)特征詞進(jìn)行優(yōu)先級(jí)排序，得到新的特征排名。

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

3.1 實(shí)驗(yàn)環(huán)境與語料庫

實(shí)驗(yàn)環(huán)境為i5處理器、4G內(nèi)存和Windows 10 64位操作系統(tǒng)，基于Python 3版本的Pycharm編譯器。選用20 News-groups 語料庫[11]作為實(shí)驗(yàn)數(shù)據(jù)集，并將數(shù)據(jù)集隨機(jī)分為70%的訓(xùn)練集和30%的測(cè)試集，使用K折交叉[12]驗(yàn)證方法。

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

對(duì)數(shù)據(jù)集進(jìn)行去除停用詞、標(biāo)點(diǎn)和詞干化等操作。采用支持向量機(jī)和樸素貝葉斯對(duì)數(shù)據(jù)集進(jìn)行分類，分別對(duì)比ACC2[13]、MI、NDM和NDMP等4種算法在不同特征維數(shù)下的分類效果，及精確度、召回率、準(zhǔn)確率和F1分?jǐn)?shù)等4種評(píng)價(jià)指標(biāo)。分類效果分別如圖1和圖2所示；評(píng)價(jià)指標(biāo)對(duì)比結(jié)果分別如表1和表2所示。

圖1 不同特征維數(shù)下的支持向量機(jī)分類效果

圖2 不同特征維數(shù)下的樸素貝葉斯分類效果

由圖1可以看出，使用支持向量機(jī)進(jìn)行特征分類時(shí)，隨著特征維數(shù)的增加，準(zhǔn)確度也隨之增加，且NDMP明顯優(yōu)于其他3種特征選擇算法。由圖2可以看出，使用樸素貝葉斯進(jìn)行特征分類時(shí)，隨著特征維數(shù)的增加，NDMP的準(zhǔn)確率明顯增加。當(dāng)特征維數(shù)達(dá)到900時(shí)，NDMP準(zhǔn)確度隨之增加，但此時(shí)ACC2在降低；當(dāng)特征維數(shù)達(dá)到1 500之后，分類準(zhǔn)確率接近78%，說明NDMP方法更加穩(wěn)定，綜合性能更好。

表1 4種算法評(píng)價(jià)指標(biāo)對(duì)比(支持向量機(jī))

表2 4種算法評(píng)價(jià)指標(biāo)對(duì)比(樸素貝葉斯)

從表1和表2的結(jié)果可以看出，隨著特征維數(shù)的變化，在不同分類器下NDMP在特征選擇過程中精確度、召回率、準(zhǔn)確率和F1分?jǐn)?shù)，相比其他特征選擇算法均有一定的提升。

4 結(jié)語

NDMP算法融合歸一化差異度量和互信息，引入詞頻信息和特征分布系數(shù)，彌補(bǔ)了歸一化差異度量在特征選擇過程中忽略詞頻以及特征詞和類別之間關(guān)系的不足，選擇出了更多信息的特征，從而提高了分類器的性能。實(shí)驗(yàn)結(jié)果表明， 該算法提高了文本分類的準(zhǔn)確率，且在特征選擇相同的情況下，樸素貝葉斯訓(xùn)練出的分類準(zhǔn)確率效果最顯著。