楊杰明，王 靜，曲朝陽(yáng)

(東北電力大學(xué)信息工程學(xué)院，吉林吉林132012)

1 引 言

隨著因特網(wǎng)技術(shù)的高速發(fā)展，各種類型的數(shù)據(jù)呈爆炸式的增長(zhǎng)，人們難以借助手工操作對(duì)海量數(shù)據(jù)進(jìn)行分析和管理［1］。目前，已有越來(lái)越多的基于統(tǒng)計(jì)理論和機(jī)器學(xué)習(xí)的方法用于信息的自動(dòng)處理［2］。其中，文本分類方法成為組織和處理大量文檔數(shù)據(jù)的關(guān)鍵技術(shù)。但是，在文本分類系統(tǒng)中，文本特征表示通常采用向量空間模型進(jìn)行描述［6］。然而原始特征向量空間的維數(shù)十分巨大，高維的特征集一方面造成文本表示的數(shù)據(jù)稀疏問(wèn)題，另一方面也造成了分類器過(guò)分?jǐn)M合的現(xiàn)象［7］。這兩個(gè)問(wèn)題直接影響文本分類的效率和精確度。有效的特征選擇方法可以降低文本的特征向量維數(shù)，去除冗余特征，保留具有較強(qiáng)類別區(qū)分能力的特征，從而提高分類的精度和防止過(guò)擬合［8］。因此，在文本分類過(guò)程中，如何進(jìn)行有效的特征選擇成為很多學(xué)者研究的熱點(diǎn)。目前已有很多特征選擇方法應(yīng)用在文本分類過(guò)程中，例如:信息增益［9］，互信息［10］，幾率比［11］和 DIA 相關(guān)因子［12］等。

本文提出一種新的特征選擇算法，該算法從相對(duì)貢獻(xiàn)率的角度度量一個(gè)特征對(duì)于分類的重要性，并在20-Newgroups數(shù)據(jù)集上與信息增益、互信息、幾率比和DIA相關(guān)因子等算法進(jìn)行了對(duì)比。實(shí)驗(yàn)結(jié)果表明，該算法能有效提高文本分類器的性能。

2 相關(guān)技術(shù)

2.1 信息增益

信息增益是機(jī)器學(xué)習(xí)領(lǐng)域常用的算法。如果一個(gè)特征的信息增益值越大，則表明該特征對(duì)分類所起的作用越大。特征tk相對(duì)于類別ci的信息增益可表示為:

其中:p(c)表示類別c的文檔總數(shù)在所有文檔中所占的比例，P(t，c)表示文檔c類中包含詞t的文檔在所有文檔中所占的比例。P(t)是文件包含特征詞t的文檔在所有文檔中所占的比例。

2.2 互信息

互信息是信息理論中的一個(gè)概念。互信息用來(lái)衡量特征tk和類別ci之間的相關(guān)性。一個(gè)特征tk擁有類ci的互信息越多，該特征包含更多的類ci信息就越多。計(jì)算互信息公式如下:

2.3 幾率比

幾率比是信息檢索的一個(gè)重要方法。它是計(jì)算特征tk在類別ci中出現(xiàn)的概率與在其它類別中出現(xiàn)的概率之比。如果特征tk在一個(gè)給定的類別ci中的幾率比較高，那么就認(rèn)為特征tk對(duì)類ci越重要。幾率比定義如下:

2.4 DIA相關(guān)因子

DIA相關(guān)因子方法用于衡量一個(gè)包含特征tk的文檔被分到類別ci中的概率，從而確定該特征對(duì)于類別ci的重要性，公式如下:

2.5 歧義值度量

Saket和Mengle等人提出了一種基于歧義值度量的特征選擇算法，該算法從特征集合中挑選出具有明確類別指示度的特征項(xiàng)。公式如下:

其中，tf(tk，ci)表示特征tk在類別ci中出現(xiàn)的概率，tf(tk)表示特征tk在整個(gè)數(shù)據(jù)集中出現(xiàn)的概率。

3 算法描述

表1是兩個(gè)特征在五個(gè)類中的特征－頻度矩陣。DIA相關(guān)因子和歧義值度量AM是常用的特征選擇方法。DIA相關(guān)因子是估計(jì)特征tk在類別ci中出現(xiàn)的概率，而歧義值度量AM是從特征集中挑選出具有明確類別指示度的特征項(xiàng)。分析DIA相關(guān)因子和歧義值度量方法，可以發(fā)現(xiàn)特征tk在某個(gè)類別ci中出現(xiàn)的頻度越高，特征tk在類別ci中就越重要。換言之，當(dāng)特征tk在類別ci出現(xiàn)的概率比其它特征在類別ci中出現(xiàn)的概率大，那么與其它特征相比特征tk就越能夠代表類別ci。據(jù)此本文推斷，當(dāng)特征tk在類別ci出現(xiàn)的概率與其它特征在類別ci中出現(xiàn)的概率之差的總和越大，特征tk對(duì)類別ci的貢獻(xiàn)就越大，越能夠代表類ci。由此本文引入一個(gè)基于相對(duì)貢獻(xiàn)率的特征選擇方法來(lái)判斷特征tk在類別ci中的重要性，即基于相對(duì)的特征頻度來(lái)衡量一個(gè)特征的重要性。

相對(duì)的特征頻度為一個(gè)特征tk在類別ci中的頻度與在其它類中的特征頻度的差值的總和，差值的總和越大證明這個(gè)特征在類別ci中越重要，說(shuō)明它的貢獻(xiàn)率越大?；谠撍枷?，可計(jì)算圖1中所示的兩個(gè)特征t1，t2在類別c1中的重要性，分別為:t1在c1中的相對(duì)特征頻度為t1在c1中的絕對(duì)特征頻度(216)減去t1在其它類中的絕對(duì)特征頻度的差值的總和，即(216－230)+(216－200)+(216－180)+(216－190)=64，t2在c1中的相對(duì)特征頻度為t2在c1中的絕對(duì)特征頻度(80)減去t2在其它類中的絕對(duì)特征頻度的差值的總和，即(80－16)+(80－50)+(80－20)+(80－10)=224，所以t2特征對(duì)類別c1的貢獻(xiàn)率大，其在類別c1中比t1重要。從圖1可以看出t2的相對(duì)特征頻度(所有綠色直線距離之和)比t1大的多。

觀察表1發(fā)現(xiàn)特征t1在數(shù)據(jù)集所有類別當(dāng)中所占的比例是很大的，特征t1在每個(gè)類別中的特征頻度都大于特征t2。由圖1也可以看出，t1曲線整體在t2曲線之上，但是這并不能證明特征t1在每個(gè)類別中都是重要的，為了削弱與類別相關(guān)的影響，本文使用每個(gè)類中的特征總頻度對(duì)特征tk在類別中的貢獻(xiàn)進(jìn)行了平衡。計(jì)算公式如下:

為了讓結(jié)果曲線較圓滑，防止特征頻率為0的情況，對(duì)上述算法進(jìn)行了進(jìn)一步的處理，如下:

表1 特征 ×類別矩陣

4 實(shí)驗(yàn)環(huán)境設(shè)置

4.1 分類器

本實(shí)驗(yàn)，采用了兩種常用的分類器，即:樸素貝葉斯(NB)和支持向量機(jī)(SVM)。其中，樸素貝葉斯［13］是建立在出現(xiàn)于一個(gè)文本中的特征與其他特征無(wú)關(guān)的假設(shè)基礎(chǔ)上的分類算法。常用貝葉斯分類器模型有兩種:一種是多項(xiàng)模型，另一種是多元的伯努利模型［14］。而多項(xiàng)式模型比多元伯努利模型的精度更高。因此，本文使用多項(xiàng)式模型。支持向量機(jī)是由Dluke等人提出來(lái)的，并且在垃圾分類和文本分類中的分類精度很高，是一種高效的分類器［15］。本文中使用了LIBSVM工具包，并選擇了線性核支持向量機(jī)。

圖1 兩個(gè)特征在不同類別中的特征頻率曲線圖

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

為了評(píng)估本文所提出的特征選擇算法的性能。在實(shí)驗(yàn)過(guò)程中，采用基準(zhǔn)數(shù)據(jù)集(20-Newgroups)進(jìn)行了驗(yàn)證，該數(shù)據(jù)集包含了19997個(gè)新聞組，所有的文件被均勻分配到20個(gè)不同類別之中［16］。在數(shù)據(jù)的預(yù)處理過(guò)程中，所有單詞轉(zhuǎn)換成小寫，并且刪除了標(biāo)點(diǎn)符號(hào)，使用了停詞表，詞根提取。最后，采用10折交叉驗(yàn)證的方法進(jìn)行了性能測(cè)試。

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

本文采用了三個(gè)評(píng)價(jià)標(biāo)準(zhǔn)，即:微平均F1micro宏平均F1macro和準(zhǔn)確率Accuracy對(duì)RC算法進(jìn)行了評(píng)價(jià)。在文本分類領(lǐng)域中常用精度P、召回率R結(jié)果進(jìn)行度量［17］。精度P為正確分類的樣本數(shù)量與測(cè)試樣本總數(shù)之比。召回率R是正確分類的樣本數(shù)量與預(yù)先標(biāo)記的樣本數(shù)量之比。而F1micro和F1macro度量是結(jié)合了精度和召回率［18］進(jìn)行的評(píng)價(jià)的指標(biāo)，計(jì)算公式如下:

準(zhǔn)確率為正確分類的百分比，常被用來(lái)衡量分類器的性能，計(jì)算公式如下:

5 數(shù)據(jù)分析

表2和表3顯示了在五種不同的特征選擇算法在20－Newgroups數(shù)據(jù)集上，分別使用貝葉斯和支持向量機(jī)分類器得到的微平均F1micro性能。表2表明了使用貝葉斯分類器時(shí)基于RC算法的微平均性能優(yōu)于其它幾個(gè)特征選擇算法，并且隨著特征數(shù)的增多性能越來(lái)越好。當(dāng)特征數(shù)量為達(dá)到2000時(shí)，性能最好。表3表明使用支持向量機(jī)上的RC算法的微平均性能優(yōu)于其它特征選擇算法，并且當(dāng)特征數(shù)量為2000時(shí)性能最好。圖2顯示五種特征選擇算法應(yīng)用在20-Newgroups數(shù)據(jù)集時(shí)貝葉斯分類器的微平均精度，RC曲線在其它算法曲線之上，精度優(yōu)于其它特征算法的。圖3顯示五種特征選擇算法應(yīng)用在20-Newgroups數(shù)據(jù)集時(shí)支持向量機(jī)分類器的微平均精度，RC曲線在其它算法曲線之上，但增加比較平緩，但精度也優(yōu)于其它特征算法。

圖2 不同特征選擇算法應(yīng)用在20N數(shù)據(jù)集時(shí)貝葉斯分類器的微平均曲線圖

圖3 不同特征選擇算法應(yīng)用在20N數(shù)據(jù)集時(shí)支持向量機(jī)分類器的微平均曲線圖

表2 不同特征選擇算法應(yīng)用在20N數(shù)據(jù)集時(shí)貝葉斯分類器的微平均性能比較(%)

表3 不同特征選擇算法應(yīng)用在20N數(shù)據(jù)集時(shí)支持向量機(jī)分類器的微平均性能比較(%)

表4和表5顯示了五種不同的特征選擇算法在20-Newgroups數(shù)據(jù)集上，分別使用貝葉斯和支持向量機(jī)分類器得到的宏平均結(jié)果。表2表明使用貝葉斯分類器時(shí)，基于RC算法的宏平均性能優(yōu)于其它特征選擇算法，并且隨著特征的增多性能越來(lái)越好，并且當(dāng)特征數(shù)量為2000時(shí)性能最好。表3表明使用支持向量機(jī)分類器時(shí)，基于RC算法的微平均性能優(yōu)于其它特征選擇算法，并且當(dāng)特征數(shù)量為2000時(shí)達(dá)到最好。圖4顯示了五種特征選擇算法在20-Newgroups數(shù)據(jù)集上使用貝葉斯分類器時(shí)的宏平均精度，RC曲線在其它算法曲線之上，優(yōu)于其它特征選擇算法。圖5顯示五種特征選擇算法在20-Newgroups數(shù)據(jù)集上使用支持向量機(jī)分類器時(shí)的宏平均精度，RC曲線在其它算法曲線之上，但增加比較平緩，但也優(yōu)于其它特征選擇算法。

圖4 不同特征選擇算法使用20N數(shù)據(jù)集時(shí)的貝葉斯分類器的宏平均曲線圖

圖5 不同特征選擇算法使用20N數(shù)據(jù)集時(shí)的支持向量機(jī)分類器的宏平均

表4 不同特征選擇算法應(yīng)用在20N數(shù)據(jù)集時(shí)貝葉斯分類器的宏平均性能比較(%)

表5 不同特征選擇算法應(yīng)用在20N數(shù)據(jù)集時(shí)支持向量機(jī)分類器的宏平均性能比較(%)

表6和表7顯示了五種不同的特征選擇算法在20-Newgroups數(shù)據(jù)集上分別使用貝葉斯和支持向量機(jī)分類器時(shí)的準(zhǔn)確率測(cè)試結(jié)果。表6表明使用貝葉斯分類器時(shí)，基于RC算法的準(zhǔn)確率優(yōu)于其它特征選擇算法，并且隨著特征數(shù)量的增加準(zhǔn)確率越來(lái)越高，當(dāng)特征數(shù)量為2000時(shí)達(dá)到最高。表7表明使用支持向量機(jī)分類器時(shí)，基于RC算法的準(zhǔn)確率優(yōu)于其它特征選擇算法，當(dāng)特征數(shù)量為2000時(shí)達(dá)到最高。圖6顯示五種特征選擇算法使用20-Newgroups數(shù)據(jù)集時(shí)，貝葉斯分類器的準(zhǔn)確率，RC曲線在其它算法曲線之上，精度優(yōu)于其它算法。圖7顯示五種特征選擇算法使用20-Newgroups數(shù)據(jù)集時(shí)，支持向量機(jī)分類器的準(zhǔn)確率，RC曲線在其它算法曲線之上，準(zhǔn)確率也優(yōu)于其它算法。

圖6 不同特征選擇算法應(yīng)用在20N數(shù)據(jù)集時(shí)貝葉斯分類器的準(zhǔn)確率曲線圖

圖7 不同特征選擇算法應(yīng)用在20N數(shù)據(jù)集時(shí)支持向量機(jī)分類器的準(zhǔn)確率曲線圖

表6 不同特征選擇算法應(yīng)用在20N數(shù)據(jù)集時(shí)貝葉斯分類器的準(zhǔn)確率性能比較(%)

表7 不同特征選擇算法應(yīng)用在20N數(shù)據(jù)集時(shí)支持向量機(jī)分類器的準(zhǔn)確率性能比較(%)

6 結(jié)束語(yǔ)

本文提出了一種新的特征選擇算法，即基于相對(duì)貢獻(xiàn)率的特征選擇方法(RC算法)。文中基于20N數(shù)據(jù)集，使用了NB和SVM分類器進(jìn)行了實(shí)驗(yàn)驗(yàn)證，實(shí)驗(yàn)結(jié)果表明RC算法的性能優(yōu)于其它幾個(gè)流行的特征選擇算法，即:信息增益(IG)，互信息(MI)，幾率比(OR)，DIA相關(guān)因子(DIA)。但是本文所選的數(shù)據(jù)集是相對(duì)數(shù)據(jù)比較平衡的數(shù)據(jù)集，未來(lái)的研究工作將選擇不平衡的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證。

［1］Blum，A.L.，＆ Langley，P.Selection of relevant features and examples in machine learning［J］.Artificial Intelligence，1997:97:245-271.

［2］Shang，W.，Huang，H.，＆ Zhu，H.A novel feature selection algorithm for text categorization［J］.Expert Systems with Applications，2007，33:1-5.

［3］Chen，J.，Huang，H.，Tian，S.，＆ Qu，Y.Feature selection for text classification with Na?ve Bayes［J］.Expert Systems with Applications，2009，36:5432-5435.

［4］Chen，Z.，＆ Lü，K.A preprocess algorithm of filtering irrelevant information based on the minimum class difference［J］.Knowledge-Based Systems，2006，19:422-429.

［5］Cover，T.，＆ Hart，P.Nearest neighbor pattern classification［J］.Information Theory，IEEE Transactions on，1967，13:21-27.

［6］Drucker，H.，Wu，D.，＆ Vapnik，V.N.Support Vector Machines for Spam Categorization［J］.IEEE TRANSACTIONS ON NEURAL NETWORKS，1999，10:1048-1054.

［7］Fragoudis，D.，Meretakis，D.，＆ Likothanassis，S.Best terms:an efficient feature-selection algorithm for text categorization［J］.Knowledge and Information Systems，2005，8:16-33.

［8］郭新辰，李成龍，樊秀玲.基于主成分分析和KNN混合方法的文本分類研究［J］.東北電力大學(xué)學(xué)報(bào)，2013，33(6):60-65

［9］He，H.，＆ Garcia，E.A.Learning from Imbalanced Data［J］.IEEE Trans.on Knowl.and Data Eng.，2009，21:1263-1284.

［10］Iman，R.L.，＆ Davenport，J.M.Approximations of the critical region of the Friedman statistic［J］.Communications in Statistics，1980，18:571-579.

［11］John，G.H.，Kohavi，R.，＆ Pfleger，K.Irrelevant Features and the Subset Selection Problem［C］.Proceedings of the Machine Learning:Proceedings of the Eleventh International Conference，San Francisco，CA:Morgan Kaufmann Publishers，1994:121-129.

［12］Yang，J.，Liu，Y.，Liu，Z.，Zhu，X.，＆ Zhang，X.A new feature selection algorithm based on binomial hypothesis testing for spam filtering.Knowledge-Based Systems，2011，24:904-914.

［13］Yan，J.，Liu，N.，Zhang，B.，Yan，S.，Chen，Z.，Cheng，Q.，F(xiàn)an，W.，＆ Ma，W.-Y.OCFS:optimal orthogonal centroid feature selection for text categorization.Proceedings of the Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval，Salvador Brazil:ACM，2005:122-129.

［14］Mladenic，D.，＆ Grobelnik，M.Feature selection on hierarchy of web documents［J］.Decision Support Systems，2003，35:45-87.

［15］Ogura，H.，Amano，H.，＆ Kondo，M.Feature selection with a measure of deviations from Poisson in text categorization［J］.Expert Systems with Applications，2009，36:6826-6832.

［16］Schneider，K.-M.A Comparison of Event Models for Naive Bayes Anti-Spam E-Mail Filtering［C］.ACM Transactions on Asian Language Information Processing(TALIP)，2004，3:243-269.

［17］Shang，W.，Huang，H.，＆ Zhu，H.A novel feature selection algorithm for text categorization［J］.Expert Systems with Applications，2007，33:1-5.

［18］Forman G，An Extensive Empirical Study of Feature Selection Metrics for Text Classification［J］.Journal of Machine Learning Research，2003，3:1289-1305.