混合CHI和MI的改進文本特征選擇方法

王 振，邱曉暉

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

0 引 言

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

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

1 傳統特征選擇方法

1.1 傳統卡方統計方法

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

(1)

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

(2)

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

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

(3)

(4)

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

1.2 傳統的互信息方法

互信息的概念出自信息論[10]中，原本互信息用來衡量兩個信號間的關聯程度。在文本分類中，表現為特征與類別之間的關聯程度。互信息的計算公式為：

(5)

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

(6)

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

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

MImax(t)=maxiMI(t,ci)

(7)

(8)

2 改進的特征選擇方法

2.1 傳統CHI方法的不足與改進

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

(9)

2.2 傳統MI方法的不足與改進

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

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

(10)

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

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

(11)

其中，m表示總類別的數量。

那么式(10)可改進為：

(12)

2.3 改進的混合方法

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

該方法的計算公式如下：

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

(13)

3 實驗結果與分析

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

3.1 數據集

實驗數據集采用國際標準數據集20NewsGroup，共計20個類別，每個類別1 000篇文章，共計20 000篇文章。實驗將其中的80%用于訓練，20%用于進行分類準確度測試。

3.2 分類效果評估

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

表1 文本分類歸屬判斷

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

(14)

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

(15)

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

(16)

3.3 實驗步驟與結果

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

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

圖1 改進后的CHI_2和MI_2與原CHI和MI的性能比較

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

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

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

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

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

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

4 結束語

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

參考文獻：

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

[2] 焦慶爭,蔚承建.一種可靠信任推薦文本分類特征權重算法[J].計算機應用研究,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] 林艷峰.中文文本分類特征選擇方法的研究與實現[D].西安:西安電子科技大學,2014.

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

選擇方法[J].計算機科學,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] 樊存佳,汪友生,王雨婷.一種改進的CHI文本特征選擇方法[J].計算機與現代化,2016(11):7-11.

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

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

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

[11] 邱云飛,王 威,劉大有,等.基于方差的CHI特征選擇方法[J].計算機應用研究,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] 熊志斌,劉 冬.樸素貝葉斯在文本分類中的應用[J].軟件導刊,2013,12(2):49-51.

[15] 李榮陸.文本分類及其相關技術研究[D].上海：復旦大學,2005.