基于特征貢獻(xiàn)度的特征選擇方法在文本分類中應(yīng)用

孟佳娜， 林鴻飛， 李彥鵬

（1.大連理工大學(xué)計(jì)算機(jī)科學(xué)與工程系，遼寧大連 116024；2.大連民族學(xué)院理學(xué)院，遼寧大連 116600）

0 引 言

文本分類是信息檢索與數(shù)據(jù)挖掘領(lǐng)域的研究熱點(diǎn)問(wèn)題，其核心任務(wù)為根據(jù)給定的訓(xùn)練數(shù)據(jù)，構(gòu)造高性能的分類器，實(shí)現(xiàn)對(duì)新文本的自動(dòng)分類.在實(shí)際應(yīng)用中，根據(jù)預(yù)定義類別的數(shù)量不同，分類系統(tǒng)可分為兩類分類器和多類分類器兩種.從文本所屬類別的個(gè)數(shù)來(lái)看，文本分類技術(shù)又可以分為單標(biāo)簽和多標(biāo)簽兩種.

文本分類的主要算法包括樸素貝葉斯方法［1、2］、KNN［3］、最大熵方法［4］、神經(jīng)網(wǎng)絡(luò)［5］、支持向量機(jī)［6］方法等.最常用的文本特征表示模型是向量空間模型（vector space model，VSM），這種方法將分類文檔中出現(xiàn)的全部詞條作為特征，將分類空間視為一組正交詞條向量所張成的向量空間，原始空間的維數(shù)十分巨大，因此，找到一種有效的特征選擇方法顯得至關(guān)重要.文本分類中常用的特征選擇方法有文檔頻率（document frequency，DF）［7］、互信息（mutual information，MI）［7］、χ2統(tǒng)計(jì)（chi－square statistic，CHI）［7］及幾率比（odds ratio，OR）［8］等.文獻(xiàn)［7］比較了一些常用的特征選擇方法，并指出χ2統(tǒng)計(jì)和信息增益方法是最有效的，其次是文檔頻率和互信息.文獻(xiàn)［8］提出了幾率比的特征選擇方法，僅使用了多分類的樸素貝葉斯分類器在reuters－21578語(yǔ)料集上進(jìn)行了實(shí)驗(yàn)，并與其他方法進(jìn)行了比較，同時(shí)提出該方法是效果最好的特征選擇方法.人們利用這些特征評(píng)價(jià)函數(shù)從不同的知識(shí)角度對(duì)特征項(xiàng)與文本之間的相關(guān)程度進(jìn)行了研究［9、10］，文獻(xiàn)［9］使用SVM分類器分析了不同特征選擇方法的效果，并提出了一種新的特征選擇方法BNS，該方法在一些特定的情況下分類結(jié)果優(yōu)于常用的方法.文獻(xiàn)［10］給出了一組特征選擇函數(shù)需滿足的基本約束條件，并基于該約束條件提出了一個(gè)構(gòu)造高性能特征選擇方法的通用方法.

上述方法從不同的角度改進(jìn)了特征選擇方法，提高了分類效果，但忽略了特征詞在各個(gè)類中的分布情況，而特征詞在各個(gè)類的分布情況會(huì)反映特征對(duì)區(qū)分每個(gè)類的貢獻(xiàn).本文提出基于特征詞在各個(gè)類的分布情況的統(tǒng)計(jì)信息，即特征貢獻(xiàn)度的一種特征選擇方法，這種方法通過(guò)計(jì)算特征的貢獻(xiàn)度值對(duì)特征進(jìn)行選擇，傾向于選擇出在某一類文檔中頻繁出現(xiàn)同時(shí)在其他類中出現(xiàn)次數(shù)少的特征，認(rèn)為這種特征能夠?yàn)槲谋痉诸愄峁└袃r(jià)值的信息.

1 基于特征貢獻(xiàn)度（FCD）的特征選擇方法

1.1 FCD特征選擇方法

為了選擇出對(duì)分類貢獻(xiàn)度大的特征，本文首先用下面的公式計(jì)算每個(gè)特征的貢獻(xiàn)度值：

特征t的最終的FCD值計(jì)算公式定義為

由上式計(jì)算的FCD值越大，說(shuō)明特征對(duì)于某一類區(qū)別于其他類的區(qū)分貢獻(xiàn)程度越大，對(duì)于分類的指導(dǎo)意義越大；該值越小，說(shuō)明其對(duì)于類別區(qū)分的貢獻(xiàn)程度越弱，對(duì)于分類的指導(dǎo)性越小.本文算法在提取特征時(shí)，是按FCD值從大到小的次序依次提取，因此FCD值越高的特征將有更大的機(jī)會(huì)被選擇.

綜上所述，本文考慮到特征詞在各個(gè)類別中的分布情況不同，而特征在各個(gè)類的分布情況的統(tǒng)計(jì)信息對(duì)分類具有指導(dǎo)意義，從而提出了基于特征貢獻(xiàn)度的一種特征選擇方法，這種方法通過(guò)計(jì)算特征的貢獻(xiàn)度值對(duì)特征進(jìn)行選擇，而特征貢獻(xiàn)度值能夠很好地反映出類別分布情況的統(tǒng)計(jì)信息.該方法傾向于選擇出在某一類文檔中出現(xiàn)次數(shù)多同時(shí)在其他類中出現(xiàn)次數(shù)少的特征，認(rèn)為這種特征能夠?yàn)槲谋痉诸愄峁└袃r(jià)值的信息.

1.2 舉 例

為說(shuō)明本文方法進(jìn)行特征選擇的具體情況，下面舉一個(gè)例子進(jìn)行說(shuō)明.表1列出了在一個(gè)簡(jiǎn)單的文本語(yǔ)料集中特征的FCD值比較.其中，第1列表示語(yǔ)料集中出現(xiàn)的幾個(gè)特征，第2、3、4列分別表示該特征在三類文檔中出現(xiàn)的文檔數(shù)，第5列為特征在數(shù)據(jù)集中出現(xiàn)的總文檔數(shù)，最后一列為特征的FCD值.對(duì)于特征“corn”來(lái)說(shuō)，它在所有文檔中只在corn類中出現(xiàn)過(guò)，此時(shí)，F(xiàn)CD（corn，corn）＝（50－0）／（50＋0）＝1，同時(shí)，F(xiàn)CD（corn，｛interest，trade｝）＝（0－50）／（0＋50）＝－1，所以FCD（corn）＝max｛1，－1，－1｝＝1；對(duì)于特征“engineer”來(lái)說(shuō)，它在所有文檔中的每一類中出現(xiàn)的次數(shù)相同，F(xiàn)CD（engineer，｛corn，interest，trade｝）＝（20－40）／（20＋40）＝－0.33，所以FCD（engineer）＝－0.33；最后，考慮特征“database”，F(xiàn)CD（database，corn）＝－30／40＝－0.75，F(xiàn)CD（database，interest）＝10／40＝0.25，F(xiàn)CD（database，trade）＝－20／40＝－0.5，所以FCD（database）＝0.25.

從以上例子可以看出，特征“corn”的FCD值最高，此特征對(duì)于類別區(qū)分的貢獻(xiàn)度最大；特征“engineer”的FCD值最低，此特征對(duì)于類別區(qū)分的貢獻(xiàn)度最小.本文方法正是依據(jù)選擇那些對(duì)于分類貢獻(xiàn)度大的特征來(lái)達(dá)到提高分類效果的目的的.

表1 在一個(gè)簡(jiǎn)單的語(yǔ)料集上特征的FCD值比較Tab.1 Comparison between features FCD value in a simple corpus

2 實(shí)驗(yàn)結(jié)果

本文選擇支持向量機(jī)（SVM）算法作為分類器，SVM是Vapnik提出的一種在缺乏先驗(yàn)知識(shí)的條件下，以最小化結(jié)構(gòu)風(fēng)險(xiǎn)為目標(biāo)，對(duì)有限樣本進(jìn)行學(xué)習(xí)的統(tǒng)計(jì)學(xué)習(xí)方法.Joachims于1998年將其引入自動(dòng)文本分類研究領(lǐng)域，取得了非常理想的文本分類效果［11、12］.為了說(shuō)明本文方法的有效性，將其和一些常用的特征選擇方法進(jìn)行了比較.主要包括χ2統(tǒng)計(jì)法、文檔頻率、幾率比及互信息選擇方法，實(shí)驗(yàn)對(duì)比結(jié)果在后文給出.

2.1 語(yǔ)料集

實(shí)驗(yàn)中使用了20Newsgroups［13］和reuters－21578［11］兩個(gè)語(yǔ)料集.20Newsgroups語(yǔ)料集是由互聯(lián)網(wǎng)用戶在Usenet上張貼的19 997條消息組成的.這些消息分布在20個(gè)不同的新聞組中，每個(gè)新聞組對(duì)應(yīng)一個(gè)文本類別.實(shí)驗(yàn)中使用了其20news－bydate－matlab語(yǔ)料集，該語(yǔ)料集詳細(xì)的數(shù)據(jù)統(tǒng)計(jì)見(jiàn)表2.取其中的10個(gè)類別作為實(shí)驗(yàn)語(yǔ)料集，5 633篇文檔作為訓(xùn)練集，3 742篇文檔作為測(cè)試集.實(shí)驗(yàn)所采用的第2個(gè)語(yǔ)料集是reuters－21578，使用由David Lewis搜集的Mod Apte子集，包含reuters－21578最大的10個(gè)類，分別是acq、corn、crude、earn、grain、interest、money－fx、ship、trade、wheat.實(shí)驗(yàn)中隨機(jī)選擇訓(xùn)練文檔7 193篇，測(cè)試文檔2 787篇.訓(xùn)練集中類的分布是不均衡的，最大類有文檔2 877篇，最小類只有181篇.

表2 20Newsgroups的bydate－matlab版本的語(yǔ)料集的數(shù)據(jù)統(tǒng)計(jì)Tab.2 Data statistics of 20Newsgroups corpus in bydate－matlab version

2.2 評(píng)價(jià)方法

文本分類的評(píng)價(jià)方法和準(zhǔn)則不盡相同，本文使用宏平均F1（macro－averagingF1）和微平均F1（micro－averagingF1）［14］的評(píng)價(jià)方法.首先介紹查全率、查準(zhǔn)率和F－Measure.查全率r和查準(zhǔn)率p分別定義為

其中a表示分類器認(rèn)為屬于這個(gè)類而實(shí)際也屬于該類的文檔數(shù)，b表示分類器認(rèn)為屬于這個(gè)類而實(shí)際不屬于該類的文檔數(shù)，c表示分類器認(rèn)為不屬于這個(gè)類而實(shí)際屬于該類的文檔數(shù).

其中β是一個(gè)調(diào)整參數(shù)，用于以不同的權(quán)重綜合查全率和查準(zhǔn)率.當(dāng)β＝1時(shí)，查全率和查準(zhǔn)率被平等對(duì)待，如下式所示，這時(shí)F－Measure又被稱為

上面提出的查全率、查準(zhǔn)率及F1－Measure都是針對(duì)單個(gè)類的分類情況而言的，當(dāng)需要評(píng)價(jià)某個(gè)分類算法時(shí)，還需要將所有類上的結(jié)果綜合起來(lái)得到平均的結(jié)果.綜合的方法通常有兩種，分別為宏平均F1和微平均F1，即

2.3 實(shí)驗(yàn)結(jié)果和分析

圖1和2分別列出了在20Newsgroups語(yǔ)料集上使用各種特征選擇方法的宏平均F1和微平均F1分類結(jié)果，從分類結(jié)果中可以看出，在選擇10 000個(gè)特征時(shí)，F(xiàn)CD方法在所有列出的特征選擇方法中分類效果最不好，其次是互信息方法；此時(shí)文檔頻率方法效果最好，其次是χ2統(tǒng)計(jì)方法，這可能與FCD方法和互信息方法選擇了大量的低頻詞有關(guān)，而文檔頻率方法選擇的都是出現(xiàn)頻率最高的特征；在特征數(shù)逐步增大的過(guò)程中，F(xiàn)CD方法分類效果提高得非常明顯，在特征數(shù)達(dá)到35 000時(shí)，分類效果最好，而文檔頻率方法在特征數(shù)增加時(shí)，其分類效果提高得很小，而互信息方法在特征數(shù)增大時(shí)，分類效果提高得比較明顯.在特征數(shù)增大到一定程度時(shí)，F(xiàn)CD方法分類效果下降，這與其他的特征選擇方法的結(jié)果相同.圖3和4列出了在reuters－21578語(yǔ)料集上使用各種特征選擇方法在SVM分類器上的宏平均F1和微平均F分類結(jié)果，從分類結(jié)果中可以看出，F(xiàn)CD方法在特征數(shù)增大時(shí)，分類效果提高得比較緩慢，而OR和MI方法則提高得最為顯著.表3列出了所有特征選擇方法在語(yǔ)料集上的宏平均F1和微平均F1的最大值，綜合兩個(gè)語(yǔ)料集上的分類結(jié)果來(lái)看，F(xiàn)CD方法在所列出的幾種特征選擇方法中為所有分類器效果最好的，這也驗(yàn)證了該方法的分類有效性.

圖1 有關(guān)的特征選擇方法在20Newsgroups語(yǔ)料集上的宏平均F1值Fig.1 Macro－F1 values of relative feature selection methods in 20Newsgroups corpus

圖2 有關(guān)的特征選擇方法在20Newsgroups語(yǔ)料集上的微平均F1Fig.2 Micro－F1 values of relative feature selection methods in 20Newsgroups corpus

圖3 有關(guān)的特征選擇方法在reuters－21578語(yǔ)料集上的宏平均F1Fig.3 Macro－F1 values of relative feature selection methods in reuters 21578 corpus

圖4 有關(guān)的特征選擇方法在reuters－21578語(yǔ)料集上的微平均F1Fig.4 Micro－F1 values of relative feature selection methods in reuters－21578 corpus

表3 有關(guān)的特征選擇方法在兩個(gè)語(yǔ)料集上的效果統(tǒng)計(jì)Tab.3 Performance statistic using relative feature selection methods in two text corpuses

3 結(jié) 語(yǔ)

文本分類是信息檢索、信息過(guò)濾和搜索引擎工作的技術(shù)基礎(chǔ).文本特征的高維性是影響各種分類器分類精度和效率的一個(gè)重要因素，如何進(jìn)行有效的特征降維成為文本分類的一個(gè)研究熱點(diǎn).因?yàn)槲谋痉诸愂且粋€(gè)分類問(wèn)題，所以類別信息對(duì)于特征選擇是很重要的.本文提出了一種稱之為FCD的特征選擇方法，該方法利用特征的統(tǒng)計(jì)結(jié)果將對(duì)于類別區(qū)分具有高貢獻(xiàn)度的特征過(guò)濾出來(lái)，實(shí)驗(yàn)結(jié)果表明該方法與其他幾種常用的特征選擇方法相比簡(jiǎn)單、有效，該結(jié)果在20Newsgroups和reuters－21578語(yǔ)料集上得到了驗(yàn)證.

未來(lái)的工作將集中在將該方法用于具有更多特征和文檔的大語(yǔ)料集上，同時(shí)FCD方法沒(méi)有考慮何時(shí)特征和類別共現(xiàn)，何時(shí)特征和類別不共現(xiàn)，如果將該統(tǒng)計(jì)結(jié)果加入到特征選擇方法中，可能分類效果會(huì)得到提高.

［1］MITEHELL T.Machine Learning［M］.New York：McGraw－Hill，1997

［2］MCCALLUM A，NIGAM K.A comparison of event models for Nave Bayes text classification［C］／／Proceedings of the AAAI－98 Workshop on Learning for Text Categorization.Wisconsin：AAAI Press，1998

［3］COVER T M，HART P E.Nearest neighbor pattern classification［J］.IEEE Transactions on Information Theory，1967，13（1）：21－27

［4］ADWAIT R.Maximum entropy models for natural language ambiguity resolution［D］.Pennsylvania：University of Pennsylvania，1998

［5］NG Hwee－tou，GOH Wei－boon，LOW Kok－leong.Feature selection，perceptron learning，and a usability case study for text categorization［C］／／Proceedings of the 20th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval.New York：ACM Press 1997

［6］VAPNIK V.The Nature of Statistical Leaning Theory［M］.New York：Springer－Verlag，1995

［7］YANG Y，PEDERSEN J.A comparative study on feature selection in text categorization［C］／／Proceedings of the 14thInternational Conference on Machine Learning（ICML′97）.Nashville：Morgan Kaufmann Publishers，1997

［8］MLADENIC D，GROBELNIK M.Features selection for unbalanced class distribution and Nave Bayes［C］／／Proceedings of the 16thInternational Conference on Machine Learning.Slovenia：Morgan Kaufmann Publishers，1999

［9］FORMAN G.An extensive empirical study of feature selection metrics for text classification［J］.Journal of Machine Learning Research，2003，3（7－8）：1289－1305

［10］徐 燕，李錦濤，王 斌，等.基于區(qū)分類別能力的高性能特征選擇方法［J］.軟件學(xué)報(bào)，2008，19（1）：82－89

［11］JOACHIMS T.Text categorization with support vector machines：Leaning with many relevant features［C］／／Machine Learning：ECML－98.Chemnitz：Springer，1998

［12］JOACHIMS T.Making large－scale SVM learning practical［M］／／Advances in Kernel Methods：Support Vector Learning.Cambridge：MIT Press，1999

［13］LANG K.NewsWeeder：Learning to filter netnews［C］／／Proceedings of the 12th International Conference on Machine Learning.San Francisco：Morgan Kaufmann Publisher，1995

［14］YANG Yi－ming.An evaluation of statistical approaches to text categorization［J］.Journal of Information Retrieval，1999，1（1－2）：67－88