王 振，邱曉暉

(南京郵電大學(xué) 通信與信息技術(shù)學(xué)院，江蘇 南京 210003)

0 引 言

隨著信息技術(shù)的迅猛發(fā)展，網(wǎng)絡(luò)上的數(shù)據(jù)呈現(xiàn)爆炸式的增長，而其中以文本數(shù)據(jù)居多。如何對眾多的文本進(jìn)行快速分類，成為了研究的熱點，文本分類也由此產(chǎn)生并不斷發(fā)展。文本分類是在給定類別的情況下，根據(jù)文本的內(nèi)容，將其自動劃分到一個或者幾個預(yù)先給定的類別中[1]。文本分類主要由分詞、預(yù)處理、特征選擇、特性降維、分類算法、分類性能評估等幾個步驟構(gòu)成[2]。在構(gòu)建特征向量時，如何降低向量的維數(shù)一直是需要解決的問題。因為一般大小的數(shù)據(jù)集經(jīng)過提取就有上萬個特征，大一點的數(shù)據(jù)集甚至能達(dá)到上百萬個特征，這么高的維數(shù)不僅對計算產(chǎn)生了很大的負(fù)擔(dān)，而且很多特征對分類而言都是無用的，還會降低分類的準(zhǔn)確度。因此，可以通過特征選擇方法，降低特征向量的維數(shù)，減少分類算法的運(yùn)行時間，從而最終提高分類準(zhǔn)確度。一直以來，特征選擇問題都是研究的重點問題[3-5]。

目前，文本分類中常用的特征選擇算法有文檔頻數(shù)(document frequency,DF)、卡方統(tǒng)計量(CHI-square statistic,CHI)、信息增益(information gain,IG)、互信息(mutual information,MI)、期望交叉熵(expected cross entropy,ECE)、文本證據(jù)權(quán)(weight of evidence for text,WET)等。美國卡內(nèi)基梅隆大學(xué)的Yang教授對以上幾種特征選擇方法進(jìn)行比較分析發(fā)現(xiàn)，CHI和IG方法的分類效果相對較好，但CHI方法相比IG方法的分類準(zhǔn)確度更高[6]。因此，針對CHI的優(yōu)缺點進(jìn)行深入研究，探索該模型的改進(jìn)途徑對提高文本的分類準(zhǔn)確度具有重要意義。近年來，很多研究者都對CHI進(jìn)行了研究改進(jìn)[7-9]。文中在分析傳統(tǒng)CHI和MI方法的優(yōu)缺點的基礎(chǔ)上，通過引入詞頻并綜合兩種算法提出一種新的混合特征選擇算法(CHMI)。

1 傳統(tǒng)特征選擇方法

1.1 傳統(tǒng)卡方統(tǒng)計方法

卡方統(tǒng)計量來自一種假設(shè)檢驗的方法，在文本分類的特征選擇問題中，用來表示特征t與所屬類別c之間的相關(guān)度。特征t與類別c之間的相關(guān)度越大，其卡方統(tǒng)計值越大，該特征對于分類就越重要。假設(shè)特征t與類別c符合一階自由度的卡方分布，t對于c的卡方統(tǒng)計量可由式(1)計算：

(1)

其中，A表示訓(xùn)練集中包含特征t且屬于類別c的文檔數(shù)；B表示訓(xùn)練集中包含特征t但是不屬于類別c的文檔數(shù)；C表示訓(xùn)練集中不包含特征t但是屬于類別c的文檔數(shù)；D表示不包含特征t且不屬于類別c的文檔數(shù)；N表示訓(xùn)練集中包含的文檔總數(shù)，通常N固定不變且N=A+B+C+D，A+C表示屬于類別c的文檔數(shù)，B+D表示不屬于類別c的文檔數(shù)，這兩個值對于確定的數(shù)據(jù)量來說都是常數(shù)，因此式(1)可以簡化為：

(2)

當(dāng)特征t與類別c相互獨立時，AD-BC=0，根據(jù)式2可知χ2(t,c)=0。當(dāng)AD-BC>0時，表示特征與類別正相關(guān)，相應(yīng)的卡方統(tǒng)計值也越大，說明該特征與類別之間的相關(guān)度越強(qiáng)。

特征t對于整個訓(xùn)練集的卡方統(tǒng)計值通常有兩種計算方式，加權(quán)平均和求最大值，計算公式分別如下：

(3)

(4)

其中，n為類別數(shù)。式(3)表示特征與所有類別的平均卡方值，式(4)表示特征與所有類別的卡方值的最大值。

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

互信息的概念出自信息論[10]中，原本互信息用來衡量兩個信號間的關(guān)聯(lián)程度。在文本分類中，表現(xiàn)為特征與類別之間的關(guān)聯(lián)程度?；バ畔⒌挠嬎愎綖椋?/p>

(5)

用t表示特征，用c表示文本類別，則文本分類中的特征與類別之間的互信息計算公式為：

(6)

其中，p(t,c)表示文檔包含特征t并且屬于類別c的概率；p(t)表示包含特征t的文檔在所有文檔中的概率；p(c)表示屬于類別c的文檔占所有文檔的概率。當(dāng)特征t與類別c獨立時，p(t,c)=p(t)p(c)，由式(6)可知特征與類別之間的互信息為0。p(t|c)值越大，特征與類別之間的關(guān)聯(lián)性就越強(qiáng)，這樣的特征就具有更多的分類信息；反之，特征與類別關(guān)聯(lián)性就越弱，特征含有的分類信息也就越少。

特征t對于整個類別的互信息主要有兩種計算方式，分別是互信息的最大值和各類別的互信息的平均值。通常，互信息的最大值比互信息的平均值的特征選擇效果好。兩種計算方式分別如下：

MImax(t)=maxiMI(t,ci)

(7)

(8)

2 改進(jìn)的特征選擇方法

2.1 傳統(tǒng)CHI方法的不足與改進(jìn)

傳統(tǒng)CHI統(tǒng)計方法只考慮了特征詞在所有文檔集中出現(xiàn)的文檔數(shù)量，而沒有考慮特征詞在某一篇文檔中出現(xiàn)的次數(shù)，從而夸大了低頻詞的作用[11]。例如，現(xiàn)在一共有100篇文檔，特征詞t1在其中的90篇文檔中均出現(xiàn)了一次，特征詞t2在其中的60篇文檔中均出現(xiàn)了50次，那么根據(jù)CHI公式計算得到CHI(t1,C)>CHI(t2,C)。CHI方法會傾向于選擇特征詞t1，但實際上特征詞t2比特征詞t1具有更多的分類信息，這是CHI方法的不足，會導(dǎo)致選擇的特征不夠準(zhǔn)確，影響最終分類效果。針對CHI方法的這一缺陷引入詞頻因子α進(jìn)行調(diào)節(jié)，α的計算公式為：

(9)

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

傳統(tǒng)的MI方法相比同樣是信息論為基礎(chǔ)的IG方法，更加直觀且易于理解，計算復(fù)雜度也較低。MI方法的一個顯著優(yōu)點是考慮類內(nèi)不同特征出現(xiàn)的頻率，度量的是含有特征t的文本數(shù)與類別內(nèi)總的文本數(shù)之間的比率，體現(xiàn)了不同類別內(nèi)特征對類別的表現(xiàn)能力，有效地利用了文本的類別信息。但是MI方法也存在一些不足之處，一個主要的缺陷是沒有考慮特征本身出現(xiàn)的頻度，這會造成MI方法在評估特征時會傾向于選擇一些低頻特征[12]。

從式(6)可以看出，當(dāng)兩個特征的p(t|c)相同時，p(t)的大小決定互信息的大小，p(t)小則互信息大，但實際這樣的特征含有的分類信息比較少，從而導(dǎo)致分類效果不理想。針對這個不足，提出在原有的公式中引入調(diào)節(jié)參數(shù)β，改進(jìn)后的公式如下：

(10)

其中，β=p(t,c)，通過引入β，添加詞頻信息，適當(dāng)增加中高頻特征所占比重，降低低頻特征的互信息值，避免互信息方法選擇過多的低頻特征，從而降低低頻詞對互信息方法的負(fù)效用。

不同類別之間，特征的詞頻也代表了不同的類別區(qū)分能力。一個區(qū)分能力強(qiáng)的特征詞，應(yīng)該集中分布在某些特定的類別中，也就是不同類別中的特征詞頻的方差應(yīng)該盡可能大，這樣的特征含有更多的類別區(qū)分信息[13]。為此，引入不同類別間特征的詞頻的方差對MI方法進(jìn)行優(yōu)化，記tfj(t)代表特征t在類別j中的頻數(shù)，則方差可表示為：

(11)

其中，m表示總類別的數(shù)量。

那么式(10)可改進(jìn)為：

(12)

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

文中提出混合CHI和MI兩種特征選擇方法，并對CHI和MI方法各自的不足進(jìn)行了分析和改進(jìn)，針對CHI方法不考慮詞頻的不足，引入詞頻調(diào)節(jié)因子α(t)。此外引入調(diào)節(jié)參數(shù)β減小MI方法對低頻詞的選擇權(quán)重，引入類別間特征詞頻的方差γ對MI方法進(jìn)一步優(yōu)化，使MI方法選擇那些集中分布在某些類別的特征，整合兩種改進(jìn)后的方法，得到一種混合的特征選擇方法(CHMI)。該方法基于CHI和MI方法，選擇那些集中出現(xiàn)在某些類別且在類別文本中分布均勻，出現(xiàn)次數(shù)較多的特征。

該方法的計算公式如下：

CHMI=χ2(t,c)×α×MI(t,c)×β×γ

(13)

3 實驗結(jié)果與分析

為了驗證該算法的有效性，將傳統(tǒng)的CHI選擇方法和傳統(tǒng)MI選擇方法與提出的混合方法進(jìn)行比較，分類器選擇實現(xiàn)簡單、分類效果良好的樸素貝葉斯(NB)和最有效的分類算法之一的支持向量機(jī)(SVM)[14]。

3.1 數(shù)據(jù)集

實驗數(shù)據(jù)集采用國際標(biāo)準(zhǔn)數(shù)據(jù)集20NewsGroup，共計20個類別，每個類別1 000篇文章，共計20 000篇文章。實驗將其中的80%用于訓(xùn)練，20%用于進(jìn)行分類準(zhǔn)確度測試。

3.2 分類效果評估

在文本分類領(lǐng)域，評價一個分類算法好壞的主要指標(biāo)有查準(zhǔn)率(precision)，又稱準(zhǔn)確率，和查全率(recall)，又稱召回率。除此之外，還有綜合了查準(zhǔn)率和查全率的Fβ值[15]。一篇文檔的歸屬情況分為四種，具體見表1。

表1 文本分類歸屬判斷

查準(zhǔn)率是指分類器劃分給某個類別的文本數(shù)量占真正屬于該類別的文本數(shù)量的比例，其計算公式為：

(14)

查全率是指真正屬于該類別的文本數(shù)量占分類器劃分給該類別的文本數(shù)量的比例，其計算公式為：

(15)

Fβ值綜合了查準(zhǔn)率和查全率，通常其β值取1，其計算公式為：

(16)

3.3 實驗步驟與結(jié)果

對數(shù)據(jù)集進(jìn)行預(yù)處理，包括去除停用詞、標(biāo)點符號等，得到預(yù)處理后的特征集合。使用CHI、MI和CHMI三種特征選擇方法對特征集合中的特征進(jìn)行分類重要性計算，并對特征的分類重要性進(jìn)行排序，得到排序后的特征集合。分類器采用樸素貝葉斯(NB)和支持向量機(jī)(SVM)。

圖1表示的是經(jīng)過改進(jìn)后的CHI方法和改進(jìn)后的MI方法與原CHI方法和原MI方法的分類準(zhǔn)確度對比。圖中CHI_2表示引入詞頻參數(shù)α(t)后的改進(jìn)CHI方法，MI_2表示引入調(diào)節(jié)參數(shù)β和γ后的改進(jìn)MI方法。從圖中可以看出，引入詞頻的CHI_2方法比原有的CHI方法在分類準(zhǔn)確度上有了一定提高，驗證了詞頻參數(shù)提高CHI方法分類準(zhǔn)確度的正確性。另外，引入調(diào)節(jié)參數(shù)后的MI_2方法比MI方法準(zhǔn)確度也有了提高。

圖1 改進(jìn)后的CHI_2和MI_2與原CHI和MI的性能比較

圖2顯示的是NB分類器分別采用CHI、MI和CHMI三種特征選擇方法在20GroupNews數(shù)據(jù)集上的分類準(zhǔn)確度曲線。從圖中可以看出，CHMI方法的分類準(zhǔn)確度比CHI和MI方法都要高。MI方法準(zhǔn)確度較低，但隨著特征數(shù)量增加而變大?；旌戏椒ㄟx擇那些集中分布在某一類中，在類別中分布均勻的特征進(jìn)行分類，最終分類效果比CHI和MI要好。

圖2 三種特征選擇方法的NB分類器性能比較

圖3顯示的是SVM分類器分別采用CHI、MI和CHMI三種特征選擇方法在20GroupNews數(shù)據(jù)集上的分類準(zhǔn)確度曲線。從圖中可以看出，當(dāng)特征數(shù)量為1 000時，CHMI方法的分類準(zhǔn)確度明顯高于CHI和MI方法。隨著特征數(shù)量的增加，MI方法的分類準(zhǔn)確度在增加，但依然低于CHMI方法。此外，SVM分類器的性能要優(yōu)于NB分類器。

此外，衡量分類效果的另一個指標(biāo)是F1值。采用貝葉斯分類器，三種方法的F1值具體情況如表2所示。從中可以看出，當(dāng)特征比較小時，CHI和CHMI方法的F1值一樣，當(dāng)特征數(shù)量增大時，CHMI方法的F1值比傳統(tǒng)的MI方法和CHI方法都要高。從查準(zhǔn)率和F1值的結(jié)果看，CHMI方法的分類效果要好于傳統(tǒng)的CHI和MI方法。

圖3 三種特征選擇方法的SVM分類器性能比較

表2 CHI方法、MI方法、CHMI方法的F1值比較

4 結(jié)束語

針對CHI方法不考慮詞頻的缺點，引入詞頻因子，考慮文檔頻的同時加入特征的詞頻，做特征選擇時，選擇在某個類別出現(xiàn)文檔數(shù)量和詞頻數(shù)量都比較多的特征。MI方法因為傾向于選擇低頻詞的缺點，特征數(shù)量小的時候效果較差。通過引入一個概率調(diào)節(jié)參數(shù)，降低選擇低頻詞帶來的負(fù)效用。另外考慮不同類別間特征的分布情況，引入類間詞頻方差，進(jìn)一步優(yōu)化MI方法。將兩種改進(jìn)后的方法結(jié)合，提出一種混合特征選擇方法CHMI，選擇集中出現(xiàn)在某一特定類并在該類中每篇文檔中出現(xiàn)次數(shù)多的特征。實驗結(jié)果證明，改進(jìn)后的混合方法在分類準(zhǔn)確度和F1值上相比傳統(tǒng)的兩種方法都有了提升。

參考文獻(xiàn)：

[1] 蘇金樹,張博鋒,徐 昕.基于機(jī)器學(xué)習(xí)的文本分類技術(shù)研究進(jìn)展[J].軟件學(xué)報,2006,17(9):1848-1859.

[2] 焦慶爭,蔚承建.一種可靠信任推薦文本分類特征權(quán)重算法[J].計算機(jī)應(yīng)用研究,2010,27(2):472-474.

[3] BIDI N,ELBERRICHI Z.Feature selection for text classification using genetic algorithms[C]//8th international conference on modelling,identification and control.[s.l.]:IEEE,2016:806-810.

[4] 林艷峰.中文文本分類特征選擇方法的研究與實現(xiàn)[D].西安:西安電子科技大學(xué),2014.

[5] 李軍懷,付靜飛,蔣文杰,等.基于MRMR的文本分類特征

選擇方法[J].計算機(jī)科學(xué),2016,43(10):225-228.

[6] YANG Y.An evaluation of statistical approaches to text categorization[J].Information Retrieval,1999,1(1-2):69-90.

[7] 樊存佳,汪友生,王雨婷.一種改進(jìn)的CHI文本特征選擇方法[J].計算機(jī)與現(xiàn)代化,2016(11):7-11.

[8] 裴英博,劉曉霞.文本分類中改進(jìn)型CHI特征選擇方法的研究[J].計算機(jī)工程與應(yīng)用,2011,47(4):128-130.

[9] 閆 屹,張燕平,耿筱媛.基于CHI值特征選取和覆蓋的文本分類方法[J].計算機(jī)技術(shù)與發(fā)展,2008,18(5):79-81.

[10] 呂 鋒，王 虹，劉皓春，等.信息理論與編碼[M].北京:人民郵電出版社,2004.

[11] 邱云飛,王 威,劉大有,等.基于方差的CHI特征選擇方法[J].計算機(jī)應(yīng)用研究,2012,29(4):1304-1306.

[12] JIANG X Y,JIN S.An improved mutual information-based feature selection algorithm for text classification[C]//5th international conference on intelligent human-machine systems and cybernetics.[s.l.]:IEEE,2013:126-129.

[13] DING X,TANG Y.Improved mutual information method for text feature selection[C]//8th international conference on computer science & education.[s.l.]:IEEE,2013:163-166.

[14] 熊志斌,劉 冬.樸素貝葉斯在文本分類中的應(yīng)用[J].軟件導(dǎo)刊,2013,12(2):49-51.

[15] 李榮陸.文本分類及其相關(guān)技術(shù)研究[D].上海：復(fù)旦大學(xué),2005.