董露露

(安徽廣播電視大學(xué) 安徽繼續(xù)教育網(wǎng)絡(luò)園區(qū)管理中心，安徽 合肥 230022)

科技革命的不斷深入、互聯(lián)網(wǎng)的迅速發(fā)展為人們提供了越來越多的傳播、獲取信息的渠道，但同時也帶來“信息爆炸”的巨大挑戰(zhàn)[1]。雖然信息形式多種多樣，但是80%的信息都是由文本組成的，因此文本成為高效地組織管理信息的關(guān)鍵，文本分類技術(shù)應(yīng)運(yùn)而生。文本分類是根據(jù)文檔的內(nèi)容及其屬性將其劃分到一個或多個預(yù)先定義的類別中的過程，作為文本信息挖掘領(lǐng)域的重要研究內(nèi)容，其目前已被廣泛應(yīng)用于搜索引擎、網(wǎng)頁分類、用戶意圖分析、抽取數(shù)據(jù)符號和郵件過濾等多個領(lǐng)域[2]。

文本分類中，通常采用VSM對文本信息進(jìn)行結(jié)構(gòu)化表示[3]。VSM將文本信息轉(zhuǎn)化成更有利于計算機(jī)理解和處理的詞條-文本矩陣，但該矩陣的高維稀疏性不僅增加了分類器計算開銷，而且影響分類精度。因此，需要使用特征選擇方法對文本集進(jìn)行降維[4-6]。

特征選擇是從原始特征集合中選出對分類最有效的一部分子集的過程，它能有效去除噪聲特征，減少特征空間[7-8]，從而提高分類精度。常用的特征選擇方法有：互信息(Mutual Information, MI)、信息增益(Information Divergence, IG)、期望交叉熵(Expected Cross Entropy, ECE)、χ2檢驗(yàn)(Chi-square, CHI)等[8-9]，這些方法分別從不同角度衡量特征項對分類的重要程度。其中，MI是一種常用的特征選擇方法，它將特征的存在與否給類別的正確判斷所帶來的信息量作為特征重要性的衡量標(biāo)準(zhǔn)，具有時間復(fù)雜度低、使用方便等優(yōu)點(diǎn)。但傳統(tǒng)互信息特征選擇方法僅考慮了文檔頻，沒有考慮詞頻因素，并且忽略了負(fù)相關(guān)特征的潛在影響，在平衡數(shù)據(jù)集上分類效果較好，但在不平衡數(shù)據(jù)集上的分類效果并不令人滿意[10-15]。

本文對傳統(tǒng)互信息特征選擇方法進(jìn)行深入分析，并提出一種改進(jìn)的互信息特征選擇方法，克服了傳統(tǒng)互信息傾向于低頻詞、忽視負(fù)相關(guān)特征的缺陷。在不平衡語料集上的實(shí)驗(yàn)表明，改進(jìn)的互信息特征選擇方法能夠有效改善分類性能，且明顯優(yōu)于目前主流的多數(shù)特征選擇方法。

1 相關(guān)工作

自機(jī)器學(xué)習(xí)技術(shù)被成功應(yīng)用于文本分類以來，自然語言處理領(lǐng)域的研究人員針對特征選擇方法在文本分類中的應(yīng)用進(jìn)行了一系列的研究，這些研究主要集中在以下三個方面。

首先，對現(xiàn)有較成熟的特征選擇方法進(jìn)行性能對比。比較有代表性的是Yang Y[16]和Mladenic D[17]的工作。前者使用LISF和KNN分類器，分析并比較了文檔頻(Document Frequency, DF)、IG、MI、文本證據(jù)權(quán)(Weight of evidence for text, WET)、CHI和ECE共6種方法在平面文本分類問題中的性能。后者針對等級文本分類問題，使用Navie Bayes分類器，分析并比較了DF，ECE、WET及優(yōu)勢率等方法。由于特征選擇算法對訓(xùn)練集和分類器的依賴性較大，因此不同研究者針對不同分類應(yīng)用采用不同的訓(xùn)練過程和分類器可能會導(dǎo)致各個特征選擇算法的性能評價結(jié)果差異較大。

其次，在傳統(tǒng)特征選擇方法的基礎(chǔ)上引入新的因子作為改進(jìn)。劉海峰等人[18]針對傳統(tǒng)互信息的不足，引入權(quán)重因子、詞頻因素、特征項位置權(quán)重，分別基于特征與類別相關(guān)度、詞頻、位置對互信息進(jìn)行改進(jìn)。廖莎莎等人[19]將概念特征引入，提出基于概念屏蔽層的特征選擇方法。樊小超等人[20]基于詞頻、文檔頻和類別相關(guān)度對傳統(tǒng)互信息進(jìn)行了改進(jìn)。

再者，直接提出新的特征選擇算法。徐燕等人[21]提出一種用概率分布刻畫的基于區(qū)分類別能力的特征選擇方法的表達(dá)形式。單曉麗等人[22]對ECE函數(shù)進(jìn)行修改后對每個類別分別進(jìn)行特征選擇，然后再將各類特征項按相同或不同比例合并用于分類。

以上研究在文本分類實(shí)驗(yàn)中都被證明是合理有效的，但它們并未沒有考慮數(shù)據(jù)集不平衡的情況。

在不均衡文本分類方面，針對特征選擇的研究很多，多數(shù)是在現(xiàn)有特征選擇方法的基礎(chǔ)上進(jìn)行改進(jìn)。Zheng Z等人[23]將特征選擇方法分為兩種：只選擇正例特征(單面方法)和正反例特征同時選擇(兩面方法)，發(fā)現(xiàn)在不均衡數(shù)據(jù)集下，兩面方法并不是最優(yōu)的，然后提出一種從正例、反例中合理選擇特征的方法，實(shí)驗(yàn)證明這種方法是有效的。陸玉昌等人[24]強(qiáng)調(diào)高頻詞的作用，即在特征選擇方法中加入p(w)因子，進(jìn)行特征權(quán)重的調(diào)整。

綜上所述，在不平衡數(shù)據(jù)集上進(jìn)行特征選擇時需要考慮兩方面因素，一個因素傾向于選擇高頻詞，另一方面不傾向于高頻詞，注重包含類別信息較多的特征。本文從這兩點(diǎn)出發(fā)，對傳統(tǒng)互信息特征選擇方法進(jìn)行改進(jìn)，強(qiáng)調(diào)詞頻作用的同時注重負(fù)相關(guān)特征的作用，選取包含類別信息較多的特征，從而提高不平衡語料集上的文本分類效果。

2 基于改進(jìn)互信息的文本分類算法

2.1 傳統(tǒng)互信息特征選擇方法

作為信息論中的重要概念，MI衡量的是特征之間互相依賴的程度[25]。將此概念引入到特征選擇，可用來度量特征項存在與否給類別的正確判斷帶來的信息量[26]。對于給定的特征項與類別c，它們之間的互信息計算公式如下：

(1)

其中，P(tj∩c)為特征項tj和類別c同時出現(xiàn)的概率，即類別c中包含tj的概率，P(tj)表示特征項tj在整個語料庫中出現(xiàn)的概率，P(c)表示類別c出現(xiàn)的概率?；バ畔⒅翟酱?，表明特征項所帶來的信息量也就越大，其和類別之間的共存關(guān)系就越強(qiáng)。當(dāng)特征項是判定類別歸屬的最佳特征時，互信息達(dá)到最大值，也就是說，當(dāng)且僅當(dāng)某篇文檔屬于當(dāng)前類別時，詞項出現(xiàn)在該文檔中。

設(shè)c1,c2,...,cr表示文檔集中類別的集合，則特征項與文檔集的互信息計算公式如下：

(2)

其中，k表示類別總數(shù)。特征選擇時，對每個特征計算其與文檔集的互信息值并進(jìn)行排序，可選取預(yù)定數(shù)目個度量值最高的特征項，或者設(shè)定閾值N，選取度量值大于N的特征項作為最終的特征子集，該子集可用來進(jìn)行下一步的文本表示。

從公式可以看出，傳統(tǒng)互信息特征選擇方法具有如下不足：

(1)僅考慮了特征項在某個具體的類別以及整個訓(xùn)練集中的文檔頻率，忽略了詞頻因素，從而傾向于選擇低頻詞，可能造成更具有代表性、與類別依存關(guān)系更強(qiáng)的特征項被過濾掉。

(2)特征項與某類別的互信息值為負(fù)數(shù)說明該特征項與當(dāng)前類別負(fù)相關(guān)，即其在當(dāng)前類別中很少或者不出現(xiàn)，而在其他類別中出現(xiàn)。這樣的特征項對類別的正確判斷具有重要作用，而公式卻將正相關(guān)和負(fù)相關(guān)的作用中和了，最終影響到特征子集的選擇。特別是在數(shù)據(jù)集不平衡的情況下，分類精度會受到很大影響。

(3)在文本分類中，文檔集不平衡是一種常見現(xiàn)象，而互信息度量特征項的信息量是在假定訓(xùn)練集類別分布相對均勻的情況下進(jìn)行的，因此，當(dāng)類別分布不均勻時，互信息取得的分類效果偏低。

2.2 改進(jìn)的互信息特征選擇方法

2.2.1 基于詞頻的互信息改進(jìn)

互信息特征選擇方法在度量特征項的信息量時僅考慮了文檔頻，造成大量特征項的互信息值相同，同時傾向于選擇低頻詞，使得對分類價值更大的特征項被過濾掉從而影響了分類效果。比如，分析公式(1)可知，當(dāng)P(tk|ci)=P(tj|ci)時，如果P(tk)>p(tj)，則MI(tk,ci)>MI(tj,ci)。但是，與低詞頻的特征項相比，具有高詞頻的特征項對于文本的正確分類而言具有更重要的作用，前者甚至可能是影響分類效果的噪聲特征；當(dāng)P(tk)=P(tj)時，若特征項tk在類ci的每篇文檔中都只出現(xiàn)一次，tj在類ci的90%的文檔中均出現(xiàn)了10次，則MI(tk,ci)>MI(tj,ci)。但很顯然，tk和tj相比，后者與類別ci的相互依存關(guān)系更大，更能代表ci類。為解決上述問題，改善不平衡數(shù)據(jù)集上的分類效果，本文引入“平均詞頻率”因子，其計算公式如下：

(3)

其中，tfci,m表示特征項在類ci的第m篇文本中出現(xiàn)的次數(shù)；nci表示類ci的文本數(shù)；k表示類別總數(shù)；N表示文本總數(shù)。α值越大，說明特征項在相應(yīng)類別中出現(xiàn)的頻率越大，與該類別的相互依存關(guān)系也就越強(qiáng)，也就越能代表該類別。

2.2.2 基于絕對值最大的互信息改進(jìn)

互信息忽視了負(fù)相關(guān)性特征項對分類的作用。若特征項在某類別上的互信息值為負(fù)，說明其與當(dāng)前類別的相互依存關(guān)系較弱，但這并不代表該特征項對其他類別的區(qū)分不起作用或者起反作用。實(shí)際上，互信息值為負(fù)的特征項對于類別的正確區(qū)分所起的作用是不可忽視的。為了避免公式對正、負(fù)相關(guān)特征作用的中和，改善互信息在不平衡數(shù)據(jù)集上的分類效果，采用如下方法：

對選定的特征項t，取它和各個類別的互信息值中絕對值最大的那個為其最終的互信息值，計算公式如下：

(4)

綜合考慮詞頻因素及正、負(fù)相關(guān)特征對文本分類的影響，引入平均詞頻率因子及絕對值最大，得到一種新型互信息特征選擇方法NMI(New Mutal Information , NMI)，其計算公式可以表示為：

(5)

(6)

2.3 基于改進(jìn)互信息的文本分類算法

文本分類的一般流程為：首先，對語料庫進(jìn)行預(yù)處理，分詞并去除對分類無用或作用較小的特征項；其次，使用特征選擇方法，選擇對分類最有價值的特征子集，對數(shù)據(jù)集進(jìn)行降維操作；再次，將文檔集向量化，得到文檔-特征項矩陣；最后，使用分類器對未知文本進(jìn)行類別預(yù)測。其中，特征選擇和分類算法是分類系統(tǒng)的核心部分。

本文研究和實(shí)現(xiàn)的是一種基于改進(jìn)互信息的文本分類方法，步驟如下：

步驟1文本預(yù)處理。

1.對文本進(jìn)行分詞。使用復(fù)旦大學(xué)的開源分詞系統(tǒng)對訓(xùn)練集和測試集進(jìn)行分詞處理；

2.去除停用詞。停用詞是指代詞和語氣助詞等常用詞，它們出現(xiàn)頻率很高但對分類而言作用不大甚至沒有作用。本文采用停用詞字典的方法將所有文檔中的停用詞去除；

3.刪除低頻詞。統(tǒng)計詞頻，去除詞頻低于3的特征項。

步驟2特征選擇。使用改進(jìn)的互信息特征選擇方法對訓(xùn)練集的每個特征進(jìn)行評估，對所有的特征按照其評估分的大小進(jìn)行排序，選取預(yù)定數(shù)目的最佳特征作為最終的特征子集。

步驟3文檔向量化表示。利用特征子集分別對訓(xùn)練集和測試集進(jìn)行向量表示，得到相應(yīng)的文檔-特征項矩陣。

步驟4訓(xùn)練分類器。使用訓(xùn)練集的文檔-特征項矩陣進(jìn)行分類訓(xùn)練，構(gòu)建SVM分類器。由于本實(shí)驗(yàn)中的文檔均用空間向量表示，本文選取基于向量空間模型的SVM分類器，具體使用的分類工具是LibSVM[27]。LibSVM是臺灣大學(xué)林智仁(Lin Chih-Jen)教授等開發(fā)設(shè)計的一個操作簡單、易于使用、快速有效的通用支持向量機(jī)軟件包。

步驟5預(yù)測未知文本的類別。利用步驟4得到的SVM分類器進(jìn)行類別預(yù)測，得到測試文本所屬類別。

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

3.1 數(shù)據(jù)集

本文實(shí)驗(yàn)數(shù)據(jù)選自復(fù)旦大學(xué)中文文本分類語料庫，該語料庫分為訓(xùn)練集和測試集兩個部分。從中選取8個類別共14265篇文檔組成不平衡語料集，其中訓(xùn)練文檔7190篇、測試文檔7075篇，文檔類別分布如下表所示：

表1 不平衡語料集分布

3.2 評估方法

本文選擇查準(zhǔn)率P、查全率R及F1值來衡量算法在每一個類別上的分類性能[28]，選擇宏平均查準(zhǔn)率、宏平均查全率值、宏平均F1來衡量算法在整個數(shù)據(jù)集上的分類性能。

查準(zhǔn)率P是分類器返回的結(jié)果中被正確分類的文本所占的比例，計算公式如下：

(7)

查全率是被分類器正確判為該類的文本在該類總文本中的比例，計算公式如下：

(8)

其中，A表示正確分類的文本數(shù)，B表示被判到該類的錯誤類別的文本數(shù)，C表示本屬于該類卻被分類器判為其它類的文本數(shù)。

F1值是對正確率和召回率的綜合：

(9)

宏平均指對于每一個類別的性能指標(biāo)的平均值，它將類別等同看待，避免了結(jié)果評測被大類支配的問題。

宏平均F1：

(10)

其中，Pi是分類器在類別i上的查準(zhǔn)率，Ri是分類器在類別i上的查全率，|c|是類別總數(shù)。

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

為了證明本文所提方法的有效性，在相同的實(shí)驗(yàn)環(huán)境下，本文分別對NIM、MI、IG、ECE、CHI進(jìn)行了文本分類實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2和圖1所示。

特征維數(shù)不同時，特征選擇方法所取得的分類效果也不同。從表2和圖1可以看出：當(dāng)特征維數(shù)僅為1000時，傳統(tǒng)互信息的效果最差，而改進(jìn)的互信息最好，這說明即使選擇的特征數(shù)目很少，本文所提方法也能夠取得相對較好的效果。隨著特征維數(shù)的增加，互信息、IG、CHI和ECE的宏平均F1值c呈緩慢上升趨勢，但均低于NMI。當(dāng)特征維數(shù)為7000時，NMI的宏平均F1值為90%，IG的宏平均F1值達(dá)到最大值88%，與NMI接近，ECE為83%，比NMI低7%。特征維數(shù)繼續(xù)增加時，IG和ECE的宏平均F1值呈下降趨勢，這是因?yàn)榇藭r越來越多的不相關(guān)特征項被用來表示文本。當(dāng)特征維數(shù)增至8000時，CHI的宏平均F1值取得最大值72%，但此時其與NMI仍有20%的差距。NMI在特征維數(shù)為10000時取得最大宏平均F1值95%，比MI高出27%。總體而言，本文提出的NMI的宏平均F1值呈上升趨勢，且在10000維之后趨于穩(wěn)定。

表2 不同特征選擇方法的宏平均F1值

圖1 NMI與傳統(tǒng)特征選擇方法宏平均F1值對比

表3列出了特征維數(shù)為1000時，傳統(tǒng)互信息和NMI在各個類別上的查準(zhǔn)率、查全率和F1值。其中，傳統(tǒng)互信息在“歷史”類別上的查準(zhǔn)率和查全率以及F1值均最低，分析原因主要是傳統(tǒng)互信息忽略了詞頻因素和負(fù)相關(guān)特征對分類的作用，導(dǎo)致其在數(shù)據(jù)集分布不平衡的情況下，在文本數(shù)最少的“歷史”類別上效果最差。改進(jìn)的互信息比傳統(tǒng)互信息在查準(zhǔn)率、查全率和F1值上都有非常大的提高，這說明本文對互信息的改進(jìn)是合理可行的。

表3 MI和NMI在各個類別上的分類效果

由上述實(shí)驗(yàn)結(jié)果可以得出如下結(jié)論：

(1)和傳統(tǒng)互信息相比，改進(jìn)的互信息能顯著提高分類性能；

(2)改進(jìn)的互信息不僅明顯優(yōu)于傳統(tǒng)互信息，而且能夠取得比傳統(tǒng)互信息、IG、CHI、ECE更好的分類結(jié)果，是一種有效的特征選擇方法。

4 結(jié)束語

特征選擇是文本分類的重要環(huán)節(jié)。作為一種常用的特征選擇方法，互信息存在未考慮詞頻因素、忽視負(fù)相關(guān)特征對分類的作用等缺陷。本文針對傳統(tǒng)互信息特征選擇方法的不足，引入平均詞頻率因子以加強(qiáng)特征項的詞頻的作用，采用絕對值最大準(zhǔn)則確定特征項的互信息值以加強(qiáng)負(fù)相關(guān)特征的作用。在不平衡數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，改進(jìn)的互信息能夠明顯改善分類效果。本文所提方法是基于統(tǒng)計的，下一步工作將研究如何從語義角度提取更有價值的特征項，并將其應(yīng)用于文本分類、搜索引擎等多個領(lǐng)域。

[1] 何力，丁兆云，賈焰，等. 大規(guī)模層次分類中的候選類別搜索[J]. 計算機(jī)學(xué)報，2014，37(1)：41-49.

[2] 劉露，彭濤，左萬利，等. 一種基于聚類的PU主動文本分類方法[J]. 軟件學(xué)報，2013，24(11)：2571-2583.

[3] 張嬌鵬，王峰，梁吉業(yè). 特征選擇：一種面向數(shù)據(jù)取值更新的批處理機(jī)制[J]. 小型微型計算機(jī)系統(tǒng)，2017, 38(2)：264-267.

[4] 張進(jìn)，丁勝，李波. 改進(jìn)的基于例子群優(yōu)化的支持向量機(jī)特征選擇和參數(shù)聯(lián)合優(yōu)化算法[J]. 計算機(jī)應(yīng)用，2016，36(5)：1330-1335.

[5] Yi Guo, Zhiqing Shao, Nan Hua. Automatic text categorization based on content analysis with congnitive situation models[J]. Information Sciences, 2010, 180(5): 613-630.

[6] 張延祥，潘海俠. 一種基于區(qū)分能力的多類不平衡文本分類特征選擇方法[J]. 中文信息學(xué)報，2015，29(4)：111-119.

[7] Zhang N, Ruan S, Lebonvallet S, et al.Kernel feature selection to fuse multi-spectral MRI images for brain tumor segmentation[J].Computer Vision and Image Understanding, 2011, 115(2): 256-269.

[8] Azar A T, Elshazly H I, Hassanien A E, et al. A random forest classifier for lymph diseases[J]. Computer Methods and Programs in Biomedicine, 2014, 113(2): 465-473.

[9] Christopher D.Manning, Prabhakar Raghavan, Hinrich Schutze. Introduction to Information Retrieval[M]. Beijing: Posts&Telecom Press, 2010: 188-193.

[10] 林琪，張宏，李千目. 一種基于MA-LSSVM的封裝式特征選擇算法[J]. 南京理工大學(xué)學(xué)報，2016，40(1)：10-16.

[11] Zhao Xi, Deng Wei, Shi Yong. Feature selection with attributes clustering by maximal information coefficient[J].Procedia Computer Science, 2013, 17: 70-79.

[12] Yamada M, Jitkrittum W, Sigal L, et al. High-dimensional feature selection by feature-wise kernelized lasso[J]. Neural computation, 2014, 26(1): 185-207.

[13] 段宏湘，張秋余，張墨逸. 基于歸一化互信息的FCBF特征選擇算法[J]. 華中科技大學(xué)學(xué)報：自然科學(xué)版，2017，45(1)：93-100.

[14] 董紅斌，滕旭陽，楊雪. 一種基于關(guān)聯(lián)信息熵度量的特征選擇方法[J]. 計算機(jī)研究與發(fā)展，2016，53(8)：1684-1695.

[16] Yang Y, Pedersen J. A comparative study on feature selection in text categorization[C]//Proceedings of the ICML. 1997, 97: 412-420.

[17] Mlademnic, D., Grobelnik, M. Feature Selection for unbalanced class distribution and Naive Bayees[A]. Proceedings of the Sixteenth International Conference on Machine Learning[C]. Bled: Morgan Kaufmann,1999: 258-267.

[18] 劉海峰，陳琦，張以皓. 一種基于互信息的改進(jìn)文本特征選擇[J]. 計算機(jī)工程與應(yīng)用，2012，48(25)：1-4.

[19] 廖莎莎，江銘虎. 中文文本分類中基于概念屏蔽層的特征提取方法[J]. 中文信息學(xué)報，2006，20(3)：22-28.

[20] 樊小超，張重陽，鄧雄偉. 基于互信息的文本特征加權(quán)方法[J]. 計算機(jī)工程與應(yīng)用，2015，51(13)：145-148.

[21] 徐燕，李錦濤，王斌，等. 基于區(qū)分類別能力的高性能特征選擇方法[J]. 軟件學(xué)報，2008，19(1)：191-201.

[22] 單麗莉，劉秉權(quán)，孫承杰. 文本分類中特征選擇方法的比較與改進(jìn)[J].哈爾濱工業(yè)大學(xué)學(xué)報，2011，43(1)：320-324.

[23] Zheng Z, Wu X, R Srihari. Feature selection for text categorization on imbalanced data. SIGKDD Explorations, 2004, 6(1): 80-89.

[24] 陸玉昌，魯明羽，李凡，等. 向量空間中單詞權(quán)重函數(shù)的分析和構(gòu)造[J]. 計算機(jī)研究與發(fā)展，2002，39(10)：1205-1210.

[25] Lin Y. , Hu X., Wu X. Quality of information-based source assessment and selection[J]. Neurocomputing, 2014, 133(8): 95-102.

[26] 徐峻嶺，周毓明，陳林，徐寶文. 基于互信息的無監(jiān)督特征選擇[J]. 計算機(jī)研究與發(fā)展，2012，49(2): 372-382.

[27] Chang C C, Lin C J. LIBSVM: a library for support vector machines[J]. ACM Trans on Intelligent Systems and Technology, 2011, 2(3): 27-65.

[28] 樊興華，孫茂松. 一種高性能的兩類中文文本分類方法[J]. 計算機(jī)學(xué)報，2006，29(1)：124-131.