胡 強(qiáng)

(川渝中煙工業(yè)公司長(zhǎng)城雪茄煙廠工程部,中國(guó) 什邡 618400)

文本自動(dòng)分類是文本挖掘中一個(gè)核心研究?jī)?nèi)容，它根據(jù)文檔內(nèi)容及其屬性給文檔自動(dòng)分配一個(gè)或多個(gè)類別[1]．目前，在絕大多數(shù)的文本分類模型中常用空間向量模型來對(duì)文檔進(jìn)行表示[2]．在這個(gè)表示模型中，文檔通常被看作是特征詞的無序序列，因而特征向量空間可能由出現(xiàn)在文檔中的全部詞條構(gòu)成，這就使得文本特征空間具有較大的維數(shù)，從而大大限制了分類算法的選擇、降低了分類算法的性能．因此，在實(shí)行文本自動(dòng)分類之前必須對(duì)文本向量空間進(jìn)行降維以減少運(yùn)算開銷、提高分類的效率和精度[3]．

特征選擇是一種比較有效的降維方法，它從原始特征集中選擇出一部分有代表性的、對(duì)分類類別貢獻(xiàn)比較大的詞條組成特征子集．在諸多現(xiàn)存特征選擇方法中，互信息是一種比較有效的方法[4]．論文首先對(duì)互信息進(jìn)行分析，總結(jié)其不足，然后定義了一個(gè)新型文檔頻并把它引入互信息以期對(duì)互信息進(jìn)行優(yōu)化．實(shí)驗(yàn)結(jié)果表明，在同種條件下，優(yōu)化的互信息方法能夠提高分類整體性能．

1 信息(Mutual Information, MI)分析

互信息是統(tǒng)計(jì)學(xué)中一種用于表征兩個(gè)變量相關(guān)性的方法，常被用于文本特征相關(guān)的統(tǒng)計(jì)模型及其相關(guān)應(yīng)用標(biāo)準(zhǔn)[4-7]．對(duì)于給定的特征f和c類文檔，它們之間的互信息可由下式來表示[8]：

(1)

式中p(f)表示特征f在全部文檔中出現(xiàn)的概率，p(f|c)表示特征f在c類文檔中出現(xiàn)的概率．互信息最大的不足就是對(duì)臨界特征的概率比較敏感．分析公式(1)可知：當(dāng)兩個(gè)特征的條件概率p(f|c)值相等時(shí)，p(f)較小的詞 (也即稀有詞)比p(f)大的詞 (也即普通詞)的互信息分值要高，因此，對(duì)于概率相差太大的兩特征來說，它們的互信息值不具有可比性．互信息另一個(gè)很大的缺點(diǎn)在于它沒有考慮特征在文本中發(fā)生的頻度，因而造成了互信息特征選擇方法經(jīng)常傾向于選擇稀有特征．在一些文本特征詞選擇算法的研究中發(fā)現(xiàn)[6-7]，如果僅僅使用互信息進(jìn)行特征選擇，它的精度極低，其主要原因在于它濾掉了很多高頻的有用特征．

2 新型文檔頻

論文所提的新型文檔頻就是把文檔頻方法和詞頻方法[5-7]結(jié)合起來，以便既考慮特征的文檔頻又考慮特征的詞頻．

定義1新型文檔頻.特征f關(guān)于類別C的新型文檔頻是指在類別C的文本集中出現(xiàn)特征f次數(shù)達(dá)到事先給定的閾值的文檔數(shù)，可用New-DFmin(f,C) ，其中min為事先給定的一個(gè)閾值，表示特征詞在文檔中出現(xiàn)的最少次數(shù)．如果用該新型文檔頻New-DFmin(f,C)計(jì)算特征評(píng)估函數(shù)中的概率，則評(píng)估函數(shù)中用到的概率公式計(jì)算方法為:

3 優(yōu)化的互信息方法

通過第1節(jié)對(duì)互信息的分析可知，它僅考慮特征發(fā)生的文檔頻而沒有考慮它發(fā)生的詞頻，從而導(dǎo)致互信息評(píng)估函數(shù)經(jīng)常傾向于選擇稀有詞．通常情況下，稀有詞也即出現(xiàn)頻率較低的詞通常對(duì)分類貢獻(xiàn)較小，為了避免對(duì)分類系統(tǒng)帶來干擾，需要對(duì)這類詞加以過濾．為此，本文把第2節(jié)所提的文檔頻引入互信息，以期對(duì)互信息的缺點(diǎn)進(jìn)行彌補(bǔ)． 此時(shí)特征f與c類文檔之間優(yōu)化的互信息Optimized-MI(f,c)的定義如下：

(2)

其中p(f)min和p(f|c)min為上述第二節(jié)所定義．從公式(2)可以看出，引入新型文檔頻后可以在一定程度上彌補(bǔ)傳統(tǒng)互信息傾向于選擇詞頻較低的特征的缺陷．

4 優(yōu)化的互信息方法實(shí)驗(yàn)驗(yàn)證

4.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)選用語料庫(kù)Reuters-21578作為實(shí)驗(yàn)數(shù)據(jù)．目前，這個(gè)語料庫(kù)已經(jīng)被廣泛應(yīng)用于文本分類實(shí)驗(yàn)之中，并成為了一種標(biāo)準(zhǔn)的分類語料庫(kù)，已有大量基于該語料庫(kù)的實(shí)驗(yàn)結(jié)果公開發(fā)表，其下載網(wǎng)址為：http://kdd.ics.uci.edu/databases/reuters21578/reuters21578.htm．Reuters-21578語料庫(kù)中共包含了22個(gè)SGML格式的數(shù)據(jù)文件夾，其中從reut2-000.sgm到reut2-020.sgm這21個(gè)文件夾中，每個(gè)文件夾由1 000篇文章組成，而reut2-021.sgm中則只包含578篇文章，因此整個(gè)語料庫(kù)總共有21 578篇文章，這些文章都來源于路透社1987年的新聞．該語料庫(kù)共有135個(gè)類別，一篇文章最多時(shí)同時(shí)屬于14個(gè)類別，平均一篇文章屬于1.24個(gè)類別．該語料庫(kù)類別文檔數(shù)分布極其不均勻，其中一個(gè)最大的類別由2 877篇正例訓(xùn)練文檔組成， 有75個(gè)類別的正例訓(xùn)練文檔數(shù)不足10篇，甚至還有一些類別根本就沒有正例訓(xùn)練文檔．本實(shí)驗(yàn)保留了90個(gè)類別，這些類別在訓(xùn)練集和測(cè)試集中都至少有一篇正例文檔．實(shí)驗(yàn)中使用“ModApte”劃分方法根據(jù)LEWISSPLIT、TOPIS、CGIPLIT等屬性對(duì)這90個(gè)類別的文檔進(jìn)行不同的劃分．經(jīng)過劃分和刪去分類信息缺失的文檔后，共得到訓(xùn)練文檔8 237篇、測(cè)試文檔3 186篇．本實(shí)驗(yàn)僅考慮〈TITLE〉和〈BODY〉之間的內(nèi)容，使用N-gram方法抽取詞干并刪去停詞后獲得20 993個(gè)不同的詞．

4.2 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

實(shí)驗(yàn)設(shè)備為一臺(tái)普通計(jì)算機(jī)．實(shí)驗(yàn)中，使用的計(jì)算工具為MATLAB 7.0，采用的分類軟件工具是Weka，這是紐西蘭的Waikato大學(xué)開發(fā)的與數(shù)據(jù)挖掘相關(guān)的一系列數(shù)據(jù)預(yù)處理、分類、回歸分析、聚類、關(guān)聯(lián)規(guī)則、可視化等工具，它對(duì)學(xué)習(xí)研究數(shù)據(jù)挖掘和機(jī)器有很大益處，其下載網(wǎng)址為：http://www.cs.waikato.ac.nz/ml/weka/．經(jīng)反復(fù)試驗(yàn)，本文算法中最小詞頻閾值設(shè)置如下：min=4．

4.3 實(shí)驗(yàn)所用分類器及其評(píng)價(jià)標(biāo)準(zhǔn)

實(shí)驗(yàn)主要用于比較Optimized-MI與MI對(duì)后續(xù)文本分類性能的影響，因此本實(shí)驗(yàn)在這兩特征選擇方法后采用相同的分類器來比較這兩種特征選擇方法．KNN分類器因簡(jiǎn)單、易理解而被廣泛使用，本實(shí)驗(yàn)就選擇該分類器來比較Optimized-MI與MI(實(shí)驗(yàn)中，KNN分類器中向量間的夾角余弦值作為文本間的距離，K設(shè)置為10)．為了檢測(cè)這兩個(gè)方法在特征個(gè)數(shù)變化情況下的KNN分類性能，選取了不同的特征個(gè)數(shù)，將微平均F1值和宏平均F1值[8]的變化情況作了比較．

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

在Reuter-21578語料庫(kù)上，為了檢測(cè)KNN分類器在不同的特征數(shù)目下的性能，分別對(duì)所選擇的90個(gè)類別的微平均F1值和宏平均F1值進(jìn)行了計(jì)算，具體結(jié)果如表1所示．

表1 特征維數(shù)變化下的微平均F1值和宏平均F1值

在特征數(shù)目變化的情況下，考察分類器的性能變化情況，可以很好地反映一個(gè)分類器對(duì)數(shù)據(jù)樣本變化的敏感程度．從表1中可以看出，隨著特征個(gè)數(shù)的增加，分類器的宏平均F1值隨著特征個(gè)數(shù)的增加而升高，但是波動(dòng)相對(duì)微平均較大，這是因?yàn)楹昶骄饕鞘艿叫☆悇e精度的影響；分類器的微平均F1值也隨著特征個(gè)數(shù)的增加而升高，并將到達(dá)一個(gè)相對(duì)穩(wěn)定的水平．從表1還可以看出，在同樣的條件下，在宏平均F1值和微平均F1值方面，Optimized-MI都要優(yōu)于MI．在50到1 500這個(gè)特征個(gè)數(shù)范圍內(nèi)，Optimized-MI的宏平均F1值比MI的宏平均F1值平均提高了近9%， Optimized-MI的微平均F1值比MI的微平均F1值平均提高了近20%．Optimized-MI的宏平均F1值和微平均F1值在特征個(gè)數(shù)為1 500的時(shí)候達(dá)到最高，分別為0.669 2和0.889 4，以后分別基本維持在0.66 0和0.88左右，這說明Optimized-MI選出的特征集中前1 500個(gè)特征是比較優(yōu)的．MI的宏平均F1值和微平均F1值在特征個(gè)數(shù)為2 500的時(shí)候達(dá)到最高，分別為0.768 3和0.579 7，以后分別基本維持在0.57和0.76左右，這說明MI選出的特征集中前2 500個(gè)特征是比較優(yōu)的．對(duì)比可知在MI選擇的前2 500個(gè)特征中包含了許多對(duì)分類貢獻(xiàn)較小甚至對(duì)分類貢獻(xiàn)起副作用的低頻特征詞；在Optimized-MI中由于引進(jìn)了一個(gè)新的文檔頻，從而能夠把那些低頻詞過濾掉，進(jìn)而提高了后續(xù)分類器的宏平均F1值和微平均F1值，這說明Optimized-MI是比較有效的．

5 結(jié)束語

論文分析了傳統(tǒng)互信息方法，針對(duì)其傾向于選擇對(duì)分類貢獻(xiàn)較小的低頻詞的缺點(diǎn)，引入一個(gè)新型文檔頻，以此對(duì)傳統(tǒng)互信息進(jìn)行優(yōu)化．通過在國(guó)際通用語料庫(kù)—Reuter-21578語料庫(kù)上的對(duì)比實(shí)驗(yàn)表明，優(yōu)化的互信息能夠克服傳統(tǒng)互信息的不足，從而獲得較為優(yōu)秀的特征集．

參考文獻(xiàn)：

[1] YAN X. A formal study of feature selection in text categorization [J]. American Journal of Communication and Computer, 2009, 6(4):32-41.

[2] ZHU H D，ZHAO X H, ZHONG Y. Feature selection method combined optimized document frequency with improved RBF NetWork[C]//Proc. of 5thInternational Cnference,ADMA 2009,Beijing:China,August 2009,796-803.

[3] 朱顥東,鐘 勇. 基于優(yōu)化的文檔頻和粗糙集的特征選擇方法[J]. 湖南師范大學(xué)自然科學(xué)學(xué)報(bào),2009,32(3):27-31.

[4] DESTRERO A, MOSCI S, MOL C D. Feature selection for high dimensional data [J]. Computational management science, 2009,6(1):25-40.

[5] 毛 勇,周曉波,夏 錚．特征選擇算法研究綜述[J]. 模式識(shí)別與人工智能,2007,20(2):211-218．

[6] CUI Z F, XU B W, ZHANG W F. A new approach of feature selection for text categorization [J].Wuhan University Journal of Natural Sciences (English version), 2006, 11(5):1 335-1 339.

[7] 寇蘇玲,蔡慶生. 中文文本分類中的特征選擇研究[J].計(jì)算機(jī)仿真,2007,24(3):289-291.

[8] LIU H W, SUN J G, LIU L. Feature selection with dynamic mutual information [J]. Pattern Recognition,2009,42(7):1 330-1 339.