新的文本分類特征選擇方法研究

張玉芳，王 勇，劉 明，熊忠陽

重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044

新的文本分類特征選擇方法研究

張玉芳，王 勇，劉 明，熊忠陽

重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044

隨著計(jì)算機(jī)技術(shù)和因特網(wǎng)的飛速發(fā)展，互聯(lián)網(wǎng)上的電子文檔急劇增加，文本分類成為組織和處理大量文檔數(shù)據(jù)的關(guān)鍵技術(shù)。文本分類（Text Categorization）是指依據(jù)文本的內(nèi)容，由計(jì)算機(jī)根據(jù)某種自動(dòng)分類算法，把文本判分為預(yù)先定義好的類別[1]，是信息存儲(chǔ)、信息檢索和信息推送等領(lǐng)域的重要課題。近年來，基于統(tǒng)計(jì)理論和機(jī)器學(xué)習(xí)的方法被應(yīng)用到文本分類中來，取得了較好的效果，但在面向?qū)嶋H應(yīng)用時(shí)文本分類技術(shù)仍存在許多挑戰(zhàn)[2]。

文本分類可以大致分為數(shù)據(jù)預(yù)處理、文本特征表示、特征降維和訓(xùn)練分類模型4個(gè)階段。在文本分類系統(tǒng)中，文本特征表示通常采用向量空間模型進(jìn)行描述。然而原始向量空間的特征維數(shù)十分巨大，高維的特征集一方面造成文本表示的數(shù)據(jù)稀疏問題，另一方面也包含了很多噪音特征。這兩個(gè)問題對文本分類的時(shí)間和精確度有著直接的影響，而且許多分類算法在計(jì)算上是無法處理這種高維特征向量的。有效的特征選擇方法可以降低文本的特征向量維數(shù)，去除冗余特征，保留具有較強(qiáng)類別區(qū)分能力的特征，從而提高分類的精度和防止過擬合[3]。因此，尋求一種有效的特征選擇方法，成為文本分類極為關(guān)鍵的環(huán)節(jié)。

1 常見的特征選擇方法研究

特征選擇對于文本分類的特征降維具有較優(yōu)的效果[4]，一直以來它都是文本分類領(lǐng)域研究的熱點(diǎn)之一。常用的特征選擇方法有文檔頻率（Document Frequency，DF）、互信息（Mutual Information，MI）、信息增益（Information Gain，IG）、期望交叉熵（Expected Cross Entropy，CE）、X2統(tǒng)計(jì)（Chi-square Statistic，CHI）和文本證據(jù)權(quán)（Weight of Evidence for Text，WET）等。它們是通過構(gòu)造某種特征評價(jià)函數(shù)，來統(tǒng)計(jì)文本特征空間各維的特征值，將各個(gè)特征按其特征值排序，并根據(jù)設(shè)置的閾值選擇出合適規(guī)模的特征子集，進(jìn)而選取出對文本分類貢獻(xiàn)較大的特征，以達(dá)到降低特征空間維數(shù)的目的。YANG Y等人在英文文本分類上的實(shí)驗(yàn)表明信息增益，期望交叉熵、CHI和文本證據(jù)權(quán)較好，而文檔頻率和互信息稍差[5]。QIU LIQING等人在中文文本分類上的實(shí)驗(yàn)表明CHI統(tǒng)計(jì)方法和信息增益方法的效果最好，文檔頻率的性能與它們大致相當(dāng)，而互信息的性能最差[6]。熊忠陽等人提出CDF特征選擇方法，并通過對比實(shí)驗(yàn)證明了其方法的有效性和優(yōu)勢[7]。

下面分別介紹幾種文本分類中普遍認(rèn)為較優(yōu)的特征選擇方法：

（1）信息增益（Information Gain，IG）。它表示了某一特征項(xiàng)的存在與否對類別預(yù)測的影響。公式如下：

信息增益的不足之處在于它考慮了特征未出現(xiàn)的情況。雖然考慮某個(gè)特征不出現(xiàn)的情況也可能對判斷文本類別有貢獻(xiàn)，但實(shí)驗(yàn)表明，這種貢獻(xiàn)往往小于其所帶來的干擾[6]。

（2）χ2統(tǒng)計(jì)量（Chi-square Statistic，CHI）。它度量了特征t和文檔類別c之間的相關(guān)程度。公式如下：

它的不足在于考慮了特征與類別的負(fù)相關(guān)，可能會(huì)選擇到在指定類中出現(xiàn)頻率較低而普遍存在于其他類的特征，這種特征對分類的貢獻(xiàn)不大，應(yīng)該刪除。此外CHI方法是基于卡方分布。如果特征和類別間的這種分布假設(shè)被打破，那么該方法傾向于選擇低頻特征[8]。

（3）文本證據(jù)權(quán)（WET）。文本證據(jù)權(quán)比較了在給定某特征的類別出現(xiàn)的條件概率和原類別出現(xiàn)的概率之間的差別。公式如下：

文本證據(jù)權(quán)傾向于選擇與類別強(qiáng)相關(guān)的特征，它放大了這類特征對分類的作用，增強(qiáng)了各個(gè)特征之間的區(qū)分度。

（4）CDF方法[7]。該方法綜合考慮特征項(xiàng)的類間集中度、類內(nèi)分散度和類內(nèi)平均頻度三項(xiàng)指標(biāo)提出來。公式如下：

CDF特征選擇方法的優(yōu)點(diǎn)在于：只考慮了特征與文本類別正相關(guān)的情況，避免了負(fù)相關(guān)情況所帶來的干擾；類間集中度和類內(nèi)分散度考慮了特征與類別之間分布的關(guān)系；類內(nèi)平均頻度考慮了特征的頻度，避免了現(xiàn)有部分特征提取方法傾向于選擇稀有特征的問題；計(jì)算復(fù)雜度小。

2 CR特征選擇方法

本文將數(shù)據(jù)集分為正類和負(fù)類，當(dāng)前類別命名為正類，數(shù)據(jù)集中當(dāng)前類別以外的其他類別命名為負(fù)類，所有的信息元素如表1所示。

表1 數(shù)據(jù)集中的信息元素

Ci表示正類，表示負(fù)類，負(fù)類里面包含了整個(gè)數(shù)據(jù)集中除Ci類別以外的所有類別的文檔；A表示正類中包含特征詞t的文檔頻；B表示正類中不包含特征詞t的文檔頻；C表示負(fù)類中包含特征詞的文檔頻；D表示負(fù)類中不包含特征詞t的文檔頻[9]。

該方法基于以下四條假設(shè)：（1）如果特征詞在正類的大部分文檔中出現(xiàn)，即在正類中分布的越均勻，那么該特征詞就具有較強(qiáng)的類別區(qū)分能力，越能代表正類；（2）如果包含特征詞的文檔在正負(fù)類間（即整個(gè)數(shù)據(jù)集中）越分散，那么該特征詞就具有較小的類別區(qū)分能力，更趨向于代表負(fù)類而非正類；（3）如果正類的大多數(shù)文檔均包含特征詞，且負(fù)類的大多數(shù)文檔也均包含該特征詞，這樣的特征詞對于正類來說具有較小的類別區(qū)分能力，本文把這樣的特征叫作鑒別性特征；（4）從詞頻的角度出發(fā)，如果特征詞在正類中平均出現(xiàn)的次數(shù)越多，而在負(fù)類中出現(xiàn)的平均次數(shù)越少，那么該特征越能代表正類。

構(gòu)造基于以上四種假設(shè)的評估函數(shù)來衡量特征與類別的相關(guān)性，得到本文方法的最終公式，表示如下：

（1）公式的第一部分用正類中包含特征t的文檔頻在整個(gè)正類所有文檔中所占比例A/(A+B)來衡量特征項(xiàng)的類別代表能力，該值越大，表示特征t的正類代表能力越強(qiáng)。

（2）公式的第二部分用正類中包含特征t的文檔頻在整個(gè)數(shù)據(jù)集中包含特征t的文檔頻的比例A/(A+C)來衡量特征詞的類別區(qū)分能力，該值越大，表明其類別區(qū)分能力越強(qiáng)，越能代表正類。

（3）公式的第三部分A/(A+B)-C/(C+D)表示特征的鑒別能力，值越大，該特征的鑒別性就越強(qiáng)，就越能代表正類。

（4）公式的第四部分用特征項(xiàng)在正-類中出現(xiàn)的平-均詞頻TCi和在負(fù)類中出現(xiàn)的平均詞頻TCi的比值TCi/TCi來衡量特征的類別的相關(guān)性，該值越大表明特征t與正類的相關(guān)性越強(qiáng)。

為了在全局特征空間中衡量特征t對分類的貢獻(xiàn)，可以按公式（6）計(jì)算特征t的分值：

CR特征選擇方法的算法如下：

（1）對訓(xùn)練語料庫中的文檔進(jìn)行分詞、去停用詞。

（2）計(jì)算每個(gè)特征t和類別C的CR(t，ci)。

（3）計(jì)算每個(gè)類別特征t的分值CRmax(t)。

（4）按照CR值降序排列，選擇前M個(gè)作為特征空間，其中，M為特征空間的維數(shù)。

CR算法的時(shí)間復(fù)雜度和空間復(fù)雜度均為O(V×M)。其中，V表示訓(xùn)練語料經(jīng)過分詞后得到的特征數(shù)量，M為特征空間的維數(shù)。而V又是由數(shù)據(jù)集的大小決定的，即文檔集越多，V值越大，計(jì)算的時(shí)間復(fù)雜度就越高，因此CR算法時(shí)間復(fù)雜度與文檔集數(shù)目成正比；M參數(shù)是人為設(shè)定的。

由于CR方法的公式構(gòu)造是基于以上幾個(gè)比值的，每一部分都可以用條件概率表示，比如A/(A+B)這個(gè)指標(biāo)的每一部分分別除以總的文檔數(shù)N，就表示成了正類中包含特征t的條件概率，其他三個(gè)指標(biāo)也可以用相同的方法進(jìn)行表示。因此，本文將該方法命名為綜合概率比（Composite Ratio，CR）

表3 不同特征選擇方法取得的分類結(jié)果 （%）

3 實(shí)驗(yàn)及其分析

3.1 數(shù)據(jù)集及實(shí)驗(yàn)設(shè)置

本文所采用的語料庫來自復(fù)旦大學(xué)計(jì)算機(jī)信息與技術(shù)系國際數(shù)據(jù)庫中心自然語言處理小組。該數(shù)據(jù)集是中文文本分類領(lǐng)域具有代表性并被普遍認(rèn)可和采用的數(shù)據(jù)集，不失一般性的同時(shí)，比較適合本文提出的基于四條假設(shè)的CR方法可行性的驗(yàn)證。文中抽取了10個(gè)類別的文檔，包括計(jì)算機(jī)、環(huán)境、交通、教育、經(jīng)濟(jì)、軍事、體育、醫(yī)藥、藝術(shù)、政治等，其中1 834篇文檔作為訓(xùn)練集，914篇作為測試集。各個(gè)類中，訓(xùn)練文檔和測試文檔的比例在2∶1左右。

實(shí)驗(yàn)主要包括三個(gè)部分：（1）KNN算法中K值的確定；（2）在維度為1 000維時(shí)，將本文的CR方法與傳統(tǒng)較好的信息增益（IG）、CHI和文本證據(jù)權(quán)（WET）以及CDF方法進(jìn)行實(shí)驗(yàn)對比，來驗(yàn)證本文方法的有效性；（3）分別在不同維度下進(jìn)行CR方法的對比實(shí)驗(yàn)，來驗(yàn)證CR方法在不同維度下的分類性能及復(fù)雜度。

3.2 KNN算法及其K值的確定

K-最近鄰算法（K-Nearest Neighbor，KNN），是基于實(shí)例的學(xué)習(xí)方法，其實(shí)現(xiàn)也是基于向量空間模型的。在訓(xùn)練過程中，KNN只是簡單地將所有訓(xùn)練樣本表示成向量空間上的權(quán)重向量并保存。分類時(shí)，首先將待分類文本表示成向量空間上的權(quán)重向量；然后，將該向量與保存的所有訓(xùn)練樣本的權(quán)重向量進(jìn)行計(jì)算，計(jì)算該文本與每一個(gè)樣本間的相似度，記錄相似度最高的前K個(gè)樣本；最后，根據(jù)這K個(gè)最“鄰近”的樣本的類別屬性裁定該文本的類別屬性[7]。

KNN算法中K值的選定目前仍沒有很好的方法，一般都是先定一個(gè)初始值，根據(jù)實(shí)驗(yàn)測試的結(jié)果來調(diào)整確定K值。本文先設(shè)定特征提取方法為CHI，通過一組實(shí)驗(yàn)確定K值，實(shí)驗(yàn)結(jié)果的好壞用準(zhǔn)確率（Accuracy）來衡量。準(zhǔn)確率的定義如下所示：

K取不同值的情況下，分類器的總體準(zhǔn)確率Accuracy結(jié)果如表2所示。

觀察表2可以發(fā)現(xiàn)，在K值為13時(shí)，分類系統(tǒng)的總體準(zhǔn)確率最高，達(dá)到最佳效果，故本文實(shí)驗(yàn)中K值均取13。通過此實(shí)驗(yàn)也在此驗(yàn)證了KNN算法中K值對于分類結(jié)果會(huì)產(chǎn)生一定的影響，K值過大或者過小都將對分類算法的分類結(jié)果產(chǎn)生負(fù)面的影響。

表2 在不同K值情況下的分類效果

3.3 多種方法的對比實(shí)驗(yàn)

維度M為1 000時(shí)，將CR方法和其他幾種特征選擇方法進(jìn)行對比實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表3、表4所示。

表4 不同特征選擇方法的宏平均實(shí)驗(yàn)結(jié)果比較 （%）

分析以上實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，綜合效果CR方法的最佳，CDF其次，IG最差，本文的CR方法比傳統(tǒng)的特征選擇方法均有一個(gè)明顯的提升，效果比CDF方法在經(jīng)濟(jì)、醫(yī)藥、軍事這三個(gè)類別也有一個(gè)大幅度的提升。分析原因，CR方法綜合考慮特征在正類和負(fù)類中的分布，而CDF方法更傾向于選擇那些在類別中分布均勻的特征，會(huì)忽略一些在正類中平均出現(xiàn)次數(shù)不多但在負(fù)類中很少出現(xiàn)的這些特征項(xiàng)，但是這類特征往往具有較強(qiáng)的類別區(qū)分能力；IG方法考慮了特征不出現(xiàn)的情況，而這種貢獻(xiàn)往往小于其所帶來的干擾；CHI方法會(huì)選擇到在指定類中出現(xiàn)頻率較低而普遍存在于其他類的特征，這種特征對分類的貢獻(xiàn)不大，應(yīng)該刪除；WET傾向于選擇與類別強(qiáng)相關(guān)的特征，它放大了這類特征對分類的作用，也是忽略了在正類中出現(xiàn)相對不多但在其他類別中很少出現(xiàn)的特征項(xiàng)。

3.4 CR方法在不同維度下的實(shí)驗(yàn)對比

為了進(jìn)一步驗(yàn)證CR方法的性能，本文分別在不同維度下進(jìn)行實(shí)驗(yàn)，綜合比較不同維度下的宏平均R、宏平均P、宏平均F1和微平均F1，實(shí)驗(yàn)結(jié)果如表5所示。同時(shí)也列出了CR方法在不同維度下特征選擇階段的耗時(shí)，如表6所示。

表5 不同維度下CR方法的宏平均比較（%）

表6 不同維度M時(shí)CR方法特征選擇耗時(shí)

觀察表5，發(fā)現(xiàn)CR方法在維度為500的時(shí)候，分類效果相對較低；維度為1 000時(shí)分類效果有明顯的提升；當(dāng)維度達(dá)到1 500時(shí)較1 000維分類效果有微小的降低，但在1 500以后各種評價(jià)指標(biāo)均達(dá)到一個(gè)相對穩(wěn)定的值。 這一結(jié)果也證明了特征選擇維度M的取值也對分類效果有一定的影響。

觀察表6，可以看出CR方法在不同維度值M時(shí)，特征選擇階段的耗時(shí)是隨著M的增大耗時(shí)大幅度增長。這也足以說明，CR方法的時(shí)間復(fù)雜度跟特征選擇維度M有關(guān)，隨著M值的增大，時(shí)間復(fù)雜度也增大。

4 結(jié)語

本文通過分析常見的特征選擇方法的優(yōu)缺點(diǎn)，把文本集分成正類和負(fù)類，綜合考慮特征項(xiàng)在正類和負(fù)類中的分布，結(jié)合四種衡量特征類別區(qū)分能力的指標(biāo)，構(gòu)造了CR特征選擇方法。經(jīng)過文本分類系統(tǒng)的實(shí)驗(yàn)驗(yàn)證，CR方法的效果要明顯優(yōu)于其他特征選擇方法。數(shù)據(jù)集的不平衡問題已成為文本分類所面臨的一大難題，特征選擇也是提高不平衡數(shù)據(jù)集中文本分類效果的重要途徑[10]。本文的CR方法在平衡數(shù)據(jù)集上表現(xiàn)出了較好的性能，不平衡數(shù)據(jù)集上表現(xiàn)如何，還有待進(jìn)一步的實(shí)驗(yàn)驗(yàn)證。同時(shí)，如何在這四項(xiàng)指標(biāo)中尋找一個(gè)平衡點(diǎn)，用一種更為合理的函數(shù)表現(xiàn)形式來表達(dá)，使該方法的效果達(dá)到更優(yōu)，將是下一步的主要工作。

[1]旺建華.中文文本分類技術(shù)研究[D].長春：吉林大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，2007.

[2]蘇金樹，張博鋒，徐昕.基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J].軟件學(xué)報(bào)，2006，17（9）：1848-1860.

[3]Yang Y，Liu X.A re-examination of text categorization methods[C]//Proceedings of 22nd Annual InternationalACM SI-GIR Conference on Research and Development in Information Retrieval.New York：ACM，1999：42-49.

[4]Novovicova J，Malik A.Information theoretic feature selection algorithms for text classification[C]//Proceedings of IEEE International Joint Conference on Neural Networks. Washington：IEEE Computer Society，2005：3272-3277.

[5]Yang Y，Pedersen J Q.A comparative study on feature selection in text categorization[C]//Proceedings of the 14th International Conference on Machine Learning.Nashville：Morgan Kaufmann Publishers，1997：412-420.

[6]Qiu Liqing，Zhao Ruyi，Zhou Gang，et a1.An extensive empirical study of feature selection for text categorization[C]// Proceedingsofthe 7th IEEE/ACIS InternationalConference on Computer and Information Science.Washington，DC：IEEE Computer Society，2008：312-315.

[7]熊忠陽，蔣健，張玉芳.新的CDF文本分類特征提取方法[J].計(jì)算機(jī)應(yīng)用，2009，29（7）：1755-1757.

[8]申紅，呂寶糧，內(nèi)山將夫，等.文本分類的特征提取方法比較與改進(jìn)[J].計(jì)算機(jī)仿真，2006，23（3）：222-225.

[9]Lan M，Tan C L，Su J，et al.Supervised and traditional term weighting methods for automatic text categorization[J].IEEE Trans on Pattern Anal and Machine Intel，2009，31（4）：721-735.

[10]Wasikowski M，Chen Xuewen.Combating the small sample class imbalance problem using feature selection[J].IEEE Trans on Knowledge and Data Engineering，2010，22（10）：1388-1400.

ZHANG Yufang,WANG Yong,LIU Ming,XIONG Zhongyang

College of Computer,Chongqing University,Chongqing 400044,China

Feature reduction is an important part in text categorization.On the basis of existing approaches of feature selection, considering the distribution property of feature between the positive class and negative class,combining four measure indicators for feature with categories distinguishing ability,a new approach named Composite Ratio（CR）for feature selection is proposed. Experiment using K-Nearest Neighbor（KNN）algorithm to examine the effectiveness of CR,the result shows that approach has better performance in dimension reduction.

feature reduction;text categorization;feature selection;Composite Ratio（CR）;K-Nearest Neighbor（KNN）algorithm

特征降維是文本分類過程中的一個(gè)重要環(huán)節(jié)。在現(xiàn)有特征選擇方法的基礎(chǔ)上，綜合考慮特征詞在正類和負(fù)類中的分布性質(zhì)，綜合四種衡量特征類別區(qū)分能力的指標(biāo)，提出了一個(gè)新的特征選擇方法，即綜合比率（CR）方法。實(shí)驗(yàn)采用K-最近鄰分類算法（KNN）來考查CR方法的有效性，實(shí)驗(yàn)結(jié)果表明該方法能夠取得比現(xiàn)有特征選擇方法更優(yōu)的降維效果。

特征降維；文本分類；特征選擇；綜合比率；K-最近鄰分類算法

A

TP391

10.3778/j.issn.1002-8331.1107-0512

ZHANG Yufang,WANG Yong,LIU Ming,et al.New feature selection approach for text categorization.Computer Engineering and Applications,2013,49（5）：132-135.

重慶市科委自然科學(xué)基金計(jì)劃資助項(xiàng)目（No.2007BB2372）；中央高校研究生創(chuàng)新基金（No.CDJXS11180013）。

張玉芳（1965—），女，教授，主要研究方向：數(shù)據(jù)挖掘、網(wǎng)絡(luò)入侵檢測、并行計(jì)算；王勇（1986—），男，碩士研究生，主要研究方向：文本分類、自然語言處理；劉明（1986—），男，研究生，主要研究方向：數(shù)據(jù)挖掘、推薦系統(tǒng)；熊忠陽（1962—），男，博導(dǎo)，主要研究方向：數(shù)據(jù)挖掘與應(yīng)用、網(wǎng)格技術(shù)、并行計(jì)算。E-mail：zonewm@cqu.edu.cn

2011-07-25

2011-09-13

1002-8331（2013）05-0132-04

CNKI出版日期：2011-11-14 http://www.cnki.net/kcms/detail/11.2127.TP.20111114.0939.022.html