改進(jìn)的文本特征選取算法研究

朱世玲，鄭 彥

(南京郵電大學(xué) 計(jì)算機(jī)軟件學(xué)院，江蘇 南京 210023)

0 引 言

隨著計(jì)算機(jī)信息技術(shù)的快速發(fā)展，網(wǎng)絡(luò)上各種各樣的文本數(shù)據(jù)極速增長(zhǎng)。對(duì)這些文本數(shù)據(jù)的快速處理成為了重要的研究課題，文本分類也因此得到了快速發(fā)展。文本分類是在給定一些特定的文本類別下，根據(jù)文本的內(nèi)容將文本自動(dòng)劃分到一個(gè)或多個(gè)類別中[1-2]。在文本分類時(shí)，通常需要將文本信息用向量空間模型或詞頻矩陣來表示[3]。如果直接用文本向量來表示，則向量空間維數(shù)會(huì)很大，而且會(huì)包含很多無用的屬性，所以需要對(duì)文本數(shù)據(jù)進(jìn)行預(yù)處理，去除無關(guān)屬性，降低文本向量空間的維數(shù)以及排除一些無關(guān)信息對(duì)分類的干擾。預(yù)處理通常包括去除停用詞、特征選取等方法[4]，而特征選取是文本分類預(yù)處理中的重要一步，也是一直以來很多學(xué)者研究的重點(diǎn)問題[5-7]。目前，文本分類中常用的特征選取算法有文檔頻率(document frequency，DF)、卡方統(tǒng)計(jì)量(CHI-square statistic，CHI)、信息增益(information gain，IG)、互信息(mutual information，MI)[8]等。文檔頻率就是設(shè)置一個(gè)閾值，只要在訓(xùn)練集中包含該詞的文本數(shù)大于這個(gè)閾值就選取作為特征詞。在文本分類特征選取中，互信息衡量的是一個(gè)特征和類別之間的相關(guān)程度，互信息值越大，所包含的類別信息就越多，對(duì)分類影響就越大。近年來很多學(xué)者都對(duì)互信息進(jìn)行了改進(jìn)[9-12]。在此基礎(chǔ)上，文中分別討論了文檔頻率和互信息在進(jìn)行特征選取時(shí)的缺點(diǎn)，提出了一種混合文檔頻率和互信息的改進(jìn)算法，并通過實(shí)驗(yàn)對(duì)其有效性進(jìn)行驗(yàn)證。

1 傳統(tǒng)的特征選取算法

1.1 傳統(tǒng)的文檔頻率算法

文檔頻率算法是文本分類中最簡(jiǎn)單、復(fù)雜度最低的特征選取算法。它是指在訓(xùn)練集中包含某個(gè)詞條的文本數(shù)。將得到的每個(gè)詞條的DF值和預(yù)先設(shè)定的閾值進(jìn)行比較，如果大于這個(gè)閾值，就表示這個(gè)詞條屬于高頻詞對(duì)文本分類有價(jià)值，就保留作為特征詞，如果小于這個(gè)閾值，就認(rèn)為該詞條屬于低頻詞對(duì)分類沒有貢獻(xiàn)并刪除。這種方法簡(jiǎn)單，計(jì)算快速，能夠勝任大規(guī)模的文本分類任務(wù)。

1.2 傳統(tǒng)的互信息算法

在文本分類特征選取中，互信息衡量的是特征和類別之間的統(tǒng)計(jì)關(guān)聯(lián)程度。它的理論基礎(chǔ)是如果類別c中包含特征t的文檔數(shù)占類別文檔數(shù)的比重高，而包含特征t占文檔集總數(shù)的比重低，則表明特征t與類別具有強(qiáng)相關(guān)性，不是相互獨(dú)立關(guān)系，其互信息值大[13]。特征與類別之間的互信息計(jì)算公式如下：

(1)

其中，P(t,c)表示在類別c中文本包含特征t的概率；P(c)表示屬于類別c的文本占訓(xùn)練集文本的概率；P(t)表示在訓(xùn)練集中文本包含特征t的概率。當(dāng)特征t和類別c相互獨(dú)立時(shí)，P(t|c)=P(t)P(c)的值就等于0。P(t|c)值越大，P(t)值越小，互信息值就越大，特征與類別之間的關(guān)聯(lián)性就越強(qiáng)，特征就具有更多的分類信息。

特征t對(duì)于整個(gè)類別的互信息主要有兩種計(jì)算方式，分別是互信息的最大值和各類互信息的平均值。兩種計(jì)算公式如下：

采用平均值：

(2)

采用最大值：

MI(t)=maxMI(t,ci)

(3)

2 改進(jìn)的特征選取算法

2.1 傳統(tǒng)文檔頻率方法的不足與改進(jìn)

文檔頻率算法雖然簡(jiǎn)單直白，復(fù)雜度低，但是缺點(diǎn)也很明顯，即沒有確切的理論基礎(chǔ)，通常被認(rèn)為是一種經(jīng)驗(yàn)方法。而且考慮特征詞和類別之間的關(guān)系，有的詞條小于預(yù)先設(shè)定的閾值，被認(rèn)為低頻詞而刪除，但卻在某個(gè)類別中集中出現(xiàn)，能夠很好地反映該類別特征。有的詞條雖然大于預(yù)先設(shè)定的閾值，但卻在每個(gè)類別中均勻出現(xiàn)，這樣的特征詞對(duì)分類就沒有價(jià)值[14]?；谶@個(gè)缺點(diǎn)，文中為特征詞的文檔頻率加入類別間的方差權(quán)重，選擇詞條在每個(gè)類別中文檔頻率方差比較大的詞條。這樣可以降低在每個(gè)類別中均等出現(xiàn)詞的作用。

改進(jìn)后的文檔頻率公式如下：

DF(t)=β×logDF

(4)

其中，DF(t)表示改進(jìn)后的特征t的文檔頻率；β表示特征t在各個(gè)類別中的文檔頻率的方差權(quán)重；DF表示特征t的文檔頻率。

β的計(jì)算公式為：

(5)

其中，m表示類別總數(shù)；dfj(t)表示特征t在類別j中的文檔數(shù)。

2.2 傳統(tǒng)互信息方法的不足與改進(jìn)

根據(jù)式1可知，當(dāng)兩個(gè)特征的P(t|c)相同時(shí)，P(t)越小的特征的互信息值反而越大，所以會(huì)偏向選擇低頻詞[15]。而且對(duì)于特征t和類別c，當(dāng)互信息值大于零時(shí)，P(t|c)越大或P(t)越小時(shí)，互信息的值就越大，絕對(duì)值越大；當(dāng)互信息值小于零時(shí)，P(t|c)越大或P(t)越小時(shí)，互信息的值越小，絕對(duì)值反而越大。換句話說，當(dāng)P(t|c)和P(t)越接近時(shí)，特征t和類別c的相關(guān)聯(lián)度就越小，互信息的絕對(duì)值越小，反之，互信息的絕對(duì)值就越大。所以，互信息值的絕對(duì)值越大的特征越能反映特征和類別之間的關(guān)聯(lián)程度。改進(jìn)后的互信息公式如下：

(6)

其中互信息的值采用平均值。

2.3 改進(jìn)的混合算法

文中提出了混合DF和MI的特征選取算法，并對(duì)DF和MI各自的不足進(jìn)行了分析和改進(jìn)。針對(duì)DF方法偏向選擇高頻詞和MI方法偏向選擇低頻詞，考慮將兩種方法進(jìn)行混合來削弱它們的不足，使在特征選取時(shí)選擇的特征詞既不偏向低頻詞也不偏向高頻詞，也避免選取在類別中均等出現(xiàn)的特征詞?；旌螪F和MI的特征選取公式如下：

(7)

3 實(shí) 驗(yàn)

3.1 數(shù)據(jù)集及開發(fā)工具

實(shí)驗(yàn)數(shù)據(jù)集采用搜狗數(shù)據(jù)集，總共9個(gè)類別，分別為財(cái)經(jīng)、IT、健康、體育、旅游、教育、招聘、文化、軍事。每個(gè)類別300篇文章，共2 700篇文章，其中每個(gè)類別的200篇文章用于訓(xùn)練，100篇文章用于測(cè)試分類結(jié)果。為了驗(yàn)證該算法的有效性，將傳統(tǒng)的DF方法和傳統(tǒng)的MI方法與提出的混合DFMI方法進(jìn)行比較。分類器選擇實(shí)現(xiàn)簡(jiǎn)單，分類效果良好的樸素貝葉斯，用Java語言實(shí)現(xiàn)，開發(fā)工具為Eclipse。

3.2 分類效果評(píng)估

一篇文本的分類情況可以分為四種：真正例(true position)、假正例(false position)、真反例(true negative)、假反例(false negative)，如表1所示。

表1 文本分類結(jié)果

評(píng)價(jià)算法好壞的度量指標(biāo)采用精度(precision，又稱查準(zhǔn)率)、召回率(recall，又稱查全率)、F1度量。

精度(P)可以看作精確性的度量，即標(biāo)記為正類的元組實(shí)際為正類所占的百分比，公式如下：

(8)

召回率(R)是完全性度量，即正元組標(biāo)記為正的百分比，公式如下：

(9)

F1度量是把精度和召回率組合到一起的度量方法，公式如下：

(10)

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

在Eclipse上用Java語言實(shí)現(xiàn)樸素貝葉斯分類，來驗(yàn)證不同特征選取方法對(duì)分類結(jié)果的影響。先利用中科大ICTCLAS分詞系統(tǒng)對(duì)所有文本進(jìn)行分詞，根據(jù)分詞后的結(jié)果，再選取名詞性和既有名詞性和動(dòng)詞性的詞語，得到預(yù)處理后的特征集合。使用不同特征選取方法進(jìn)行特征選取，特征詞都是1 000個(gè)。將所有文本向量化，最后利用樸素貝葉斯分類器對(duì)文本進(jìn)行分類，實(shí)驗(yàn)結(jié)果如表2所示。

表2 DF、MI、DFMI方法在精度、召回率和F1上的比較 %

從表中可以看出，改進(jìn)的混合DFMI方法明顯比MI方法好很多，無論在精度、召回率還是F1度量上都明顯提高，和DF相比也均有提升，從而驗(yàn)證了混合DFMI方法的有效性。

4 結(jié)束語

MI方法簡(jiǎn)單，應(yīng)用廣泛，但傾向選擇低頻詞，忽略了互信息絕對(duì)值較大的特征也具有較好的類別區(qū)別能力，因此通過對(duì)互信息取絕對(duì)值后再取平均值排序進(jìn)行特征選擇。DF方法雖然簡(jiǎn)單直白，但有的特征雖然出現(xiàn)的頻率很好，但在類別中均等出現(xiàn)這樣的特征也沒有區(qū)別能力，所以考慮加入文檔頻率類別方差?；趦煞N改進(jìn)后的方法，提出一種混合的DFMI特征選取算法。實(shí)驗(yàn)結(jié)果表明，該算法在精度、召回率和F1度量上均有所提高。

現(xiàn)有的特征選取算法都是從不同的角度進(jìn)行特征選取，都有各自的優(yōu)缺點(diǎn)，因此將不同的特征選取算法進(jìn)行混合，使之從多個(gè)角度進(jìn)行考慮，兼顧多個(gè)方面，是一個(gè)值得研究的方向。