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

重慶大學 計算機學院，重慶 400044

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

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

重慶大學 計算機學院，重慶 400044

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

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

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

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

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

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

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

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

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

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

文本證據權傾向于選擇與類別強相關的特征，它放大了這類特征對分類的作用，增強了各個特征之間的區(qū)分度。

（4）CDF方法[7]。該方法綜合考慮特征項的類間集中度、類內分散度和類內平均頻度三項指標提出來。公式如下：

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

2 CR特征選擇方法

本文將數據集分為正類和負類，當前類別命名為正類，數據集中當前類別以外的其他類別命名為負類，所有的信息元素如表1所示。

表1 數據集中的信息元素

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

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

構造基于以上四種假設的評估函數來衡量特征與類別的相關性，得到本文方法的最終公式，表示如下：

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

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

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

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

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

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

（1）對訓練語料庫中的文檔進行分詞、去停用詞。

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

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

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

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

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

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

3 實驗及其分析

3.1 數據集及實驗設置

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

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

3.2 KNN算法及其K值的確定

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

KNN算法中K值的選定目前仍沒有很好的方法，一般都是先定一個初始值，根據實驗測試的結果來調整確定K值。本文先設定特征提取方法為CHI，通過一組實驗確定K值，實驗結果的好壞用準確率（Accuracy）來衡量。準確率的定義如下所示：

K取不同值的情況下，分類器的總體準確率Accuracy結果如表2所示。

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

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

3.3 多種方法的對比實驗

維度M為1 000時，將CR方法和其他幾種特征選擇方法進行對比實驗，實驗結果如表3、表4所示。

表4 不同特征選擇方法的宏平均實驗結果比較 （%）

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

3.4 CR方法在不同維度下的實驗對比

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

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

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

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

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

4 結語

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

[1]旺建華.中文文本分類技術研究[D].長春：吉林大學計算機科學與技術學院，2007.

[2]蘇金樹，張博鋒，徐昕.基于機器學習的文本分類技術研究進展[J].軟件學報，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].計算機應用，2009，29（7）：1755-1757.

[8]申紅，呂寶糧，內山將夫，等.文本分類的特征提取方法比較與改進[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

特征降維是文本分類過程中的一個重要環(huán)節(jié)。在現有特征選擇方法的基礎上，綜合考慮特征詞在正類和負類中的分布性質，綜合四種衡量特征類別區(qū)分能力的指標，提出了一個新的特征選擇方法，即綜合比率（CR）方法。實驗采用K-最近鄰分類算法（KNN）來考查CR方法的有效性，實驗結果表明該方法能夠取得比現有特征選擇方法更優(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.

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

張玉芳（1965—），女，教授，主要研究方向：數據挖掘、網絡入侵檢測、并行計算；王勇（1986—），男，碩士研究生，主要研究方向：文本分類、自然語言處理；劉明（1986—），男，研究生，主要研究方向：數據挖掘、推薦系統(tǒng)；熊忠陽（1962—），男，博導，主要研究方向：數據挖掘與應用、網格技術、并行計算。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