丁 瓊

（華東交通大學(xué) 軟件學(xué)院，江西 南昌 330013）

文本分類指將文本按照其內(nèi)容含義劃分到不同的類型中去.自動(dòng)分類的一般做法是，預(yù)先確定好文本的類別，并且對(duì)每個(gè)文本類別提供一批預(yù)先分好類的文本（稱為訓(xùn)練文本集），分類系統(tǒng)通過(guò)訓(xùn)練文本集學(xué)習(xí)分類知識(shí)，在實(shí)際分類時(shí)，再根據(jù)學(xué)習(xí)到的分類知識(shí)為需要分類的文本確定一個(gè)或者多個(gè)文檔類別.國(guó)外的自動(dòng)分類研究大體上可以分為三個(gè)階段：第一階段（1958年－1964年）主要進(jìn)行了自動(dòng)分類可行性研究；第二階段（1965年－1974年），自動(dòng)分類的實(shí)驗(yàn)研究；第三階段（1975年－至今），自動(dòng)分類的實(shí)用化階段.國(guó)內(nèi)自動(dòng)分類研究起步較晚，始于20世紀(jì)80年代初期.國(guó)內(nèi)的研究基本上是在英文文本分類研究的基礎(chǔ)上采取相應(yīng)策略，結(jié)合中文文本的特定知識(shí)，然后應(yīng)用于中文之上，繼而形成中文文本自動(dòng)分類研究體系.[1]

1 特征提取算法

在文本處理中，一些常用特征提取評(píng)估函數(shù)有文檔頻數(shù)（document frequency）、信息增益（information gain）、期望交叉熵（expected cross entropy）、互信息（mutual information）、χ2統(tǒng)計(jì)（CHI）、文本證據(jù)權(quán)（the weight of evidence for text）等.[2,3,4]

1.1 文檔頻數(shù)DF

它是最簡(jiǎn)單的評(píng)估函數(shù)，值為訓(xùn)練集合中該單詞發(fā)生的文本數(shù).DF評(píng)估函數(shù)理論假設(shè)稀有單詞可能不包含有用信息，也可能太少而不足以對(duì)分類產(chǎn)生影響，也可能是噪音，因此可以刪去.顯然它在計(jì)算量上比其他評(píng)估函數(shù)小很多，但是實(shí)踐運(yùn)用中它的效果卻很好.DF的缺點(diǎn)是稀有單詞可能在某一類文本中并不稀有，也可能包含著重要的判斷信息，錯(cuò)誤的舍棄，可能影響分類器的精度.因此，在實(shí)際運(yùn)用中一般并不直接使用DF.

1.2 信息增益（Information Gain）

信息增益表示文檔中包含某一特征值時(shí)文檔類的平均信息量.它定義為某一特征在文檔中出現(xiàn)前后的信息熵之差.

1.3 互信息（Mutual Information）[5]

MI是信息論中的概念，用于衡量一個(gè)消息中兩個(gè)信號(hào)之間的相互依賴程度.在特征選擇領(lǐng)域中，文檔類別c和特征f的互信息體現(xiàn)了特征和類別的相關(guān)程度，在某個(gè)類別中出現(xiàn)的概率高，而在其他類別中出現(xiàn)概率低的特征f將獲得較高的互信息.

1.4 χ2統(tǒng)計(jì)[6]

統(tǒng)計(jì)也是表征兩個(gè)變量間的相互關(guān)性，但是它比互信息更強(qiáng)，因?yàn)樗瑫r(shí)考慮了特征存在和不存在時(shí)的情況.

1.5 交叉熵(Cross Entropy)[7]

交叉熵和信息增量相似，不同之處在于信息增量中同時(shí)考慮到了特征在文本中發(fā)生與不發(fā)生時(shí)的兩種情況，而交叉熵只考慮特征在文本中發(fā)生一種情況.

1.6 證據(jù)權(quán)值(Weight of Evidence)

證據(jù)權(quán)值反映的是類概率與在給定某一特征值下的類概率的差.

2 KNN分類方法簡(jiǎn)介

KNN分類方法把文本表示為D(T1,W1;T2,W2;…TN,WN)形式的加權(quán)向量.對(duì)于測(cè)試文本，計(jì)算該文本向量和訓(xùn)練樣本集中每個(gè)樣本的相似度，找出K個(gè)最相似的文本，在這K個(gè)近鄰中，依次計(jì)算每類的權(quán)重，最后把測(cè)試文本分到權(quán)重最大的類中.

3 特征提取在KNN中的性能比較

實(shí)驗(yàn)?zāi)康模何覀冇肒NN分類器比較常用的文本特征提取方法：IG、CE、MI、χ2、WE及 DF特征提取方法.訓(xùn)練集樣本數(shù)為1882.我們采用開放性測(cè)試，即訓(xùn)練數(shù)據(jù)不同的測(cè)試集進(jìn)行測(cè)試，測(cè)試集樣本數(shù)為934.

實(shí)驗(yàn)環(huán)境：分類算法KNN，特征預(yù)處理采用禁用詞表，權(quán)重計(jì)算公式TF*IDF，K值取35，特征數(shù)目從50到10000.為評(píng)價(jià)分類效果我們采用最通用的性能評(píng)價(jià)方法：準(zhǔn)確率(Precision)來(lái)對(duì)各種提取方法進(jìn)行比較.

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

表1 特征提取方法在KNN中的比較

圖1 特征提取方法在KNN中的比較

用KNN分類器比較常用的文本特征提取方法，比較結(jié)果見表1和圖1.各種方法的分類準(zhǔn)確率表現(xiàn)出隨特征數(shù)的增加先增加后降低的變化曲線.對(duì)于中文文本分類來(lái)說(shuō)，特征向量空間過(guò)大或過(guò)小時(shí)，分類準(zhǔn)確度都不高.選用的特征詞過(guò)少時(shí)，不能反映各個(gè)類別的特征，不能準(zhǔn)確地區(qū)分各個(gè)類別的文檔；而選用的特征詞過(guò)多時(shí)，一些區(qū)分度很低的冗余詞匯也被加了進(jìn)來(lái)，這樣那些區(qū)分度較高的詞在其中被“稀釋”了，不能有效地為區(qū)分文檔做貢獻(xiàn).IG、CE、χ2、WE、DF五種特征提取方法在 KNN分類器中性能接近，并且在特征空間維度為1000時(shí)，分類正確率達(dá)到最大.互信息(MI)特征提取方法隨著特征數(shù)的提高分類性能提高得較快，當(dāng)特征數(shù)目較小時(shí)分類性能極差.原因可能是互信息沒有考慮特征詞出現(xiàn)的頻度，導(dǎo)致互信息評(píng)價(jià)函數(shù)不選擇高頻的有用詞而有可能選擇稀有詞做文本的最佳特征.此外MI是基于類別信息的特征提取方法.當(dāng)訓(xùn)練語(yǔ)料庫(kù)未達(dá)一定規(guī)模時(shí)，特征空間中必然存在相當(dāng)數(shù)量的出現(xiàn)頻率很低（如低于三次）的特征.而因它們較低的出現(xiàn)頻率，必然只屬于較少的類別.而使用類別信息的統(tǒng)計(jì)方法認(rèn)為這些低頻詞攜帶較為強(qiáng)烈類別信息，從而對(duì)他們有不同程度的倚重.但是研究發(fā)現(xiàn)，這些低頻詞中只有不到20%的詞確實(shí)帶有較強(qiáng)的類別信息，大多數(shù)都是噪音詞，不應(yīng)成為特征.當(dāng)選擇較少數(shù)目的特征時(shí)，選取的大多是低頻詞，這些詞對(duì)分類并無(wú)很大作用，所以當(dāng)特征數(shù)目較少時(shí)分類的正確率很低，隨著特征數(shù)目的增加性能一步一步的提高.最后因我們訓(xùn)練集的文本都不太長(zhǎng)，故當(dāng)特征數(shù)目達(dá)到100000時(shí)，基本上所有特征都包含進(jìn)去，故最后分類效果趨于相同.

〔1〕李榮陸.文本分類若干關(guān)鍵技術(shù)研究[D].上海：復(fù)旦大學(xué)，2005.20-25.

〔2〕龐劍鋒，卜東波，白碩.基于向量空間模型的文本自動(dòng)分類系統(tǒng)的研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用研究，2001，21（9）：23-26.

〔3〕朱華宇，孫正興，張福炎.一個(gè)基于向量空間模型的中文文本自動(dòng)分類系統(tǒng) [J].計(jì)算機(jī)工程，2001，27（2）：36-40.

〔4〕孫健，等.基于K一最近距離的自動(dòng)文本分類研究[J].北京郵電大學(xué)學(xué)報(bào)，2001，24(1)：41-44.

〔5〕田文穎.文本特征提取方法研究.http://blog.csdn.net/tvetve/archive/2008/04/14/2292111.aspx.

〔6〕于瑞萍，張明.中文文本自動(dòng)分類中特征詞選擇算法研究[J].硅谷,2009（12）：61.