一種改進(jìn)的互信息特征選擇方法

摘要:特征選擇是中文文本自動分類領(lǐng)域中極其重要的研究內(nèi)容，其目的是為了解決特征空間高維性和文檔表示向量稀疏性之間的矛盾。針對互信息(MI)特征選擇方法分類效果較差的現(xiàn)狀，提出了一種改進(jìn)的互信息特征選擇方法IMI。該方法考慮了特征項在當(dāng)前文本中出現(xiàn)的頻率以及互信息值為負(fù)數(shù)情況下的特征選取，從而能更有效地過濾低頻詞。通過在自動分類器KNN上的實驗表明，改進(jìn)后的方法極大地提高了分類精度。

關(guān)鍵詞:中文文本自動分類;特征選擇;互信息

中圖分類號:TP311文獻(xiàn)標(biāo)識碼:A 文章編號:1009-3044(2009)35-9889-02

An Improved Feature Selection Algorithm Based on Mutual Information

KANG Lan-lan，DONG Dan-dan

(Faculty ofApplied Science， Jiangxi University of Science and Technology， Ganzhou 341000， China)

Abstract: Feature selection is extremely important research of automatic categorization， and its purpose is to solve the contradiction between the high dimensional feature space and sparse vector of the document. For the less effective classification results of mutual information feature selection method， an improved mutual information feature selection method， IMI，was presented. This method not only takes into the current frequency of feature in text， but also takes into the case of mutual information value is negative. Low frequency words can be filtered more effective. Experiments of automatic categorization based KNN show that IMI improves the classification accuracy.

Key words: automatic categorization; feature selection; mutual information

分類是對信息的一種最基本的認(rèn)知形式。所謂中文文本自動分類[1]就是指在給定的分類體系下，根據(jù)文本的內(nèi)容用計算機(jī)程序確定文本所屬的類別，給文本分配一個或者多個合適的類別。即用計算機(jī)程序來確定指定文檔和預(yù)先定義類別之間的隸屬關(guān)系。文本自動分類問題的主要障礙之一就是特征空間的高維性。特征選擇是中文文本自動分類領(lǐng)域中極其重要的研究內(nèi)容，其目的是為了解決特征空間高維性和文檔表示向量稀疏性之間的矛盾[2]。常用的特征選擇方法有:文檔頻數(shù)， 信息增益，互信息， 期望交叉熵，卡方統(tǒng)計量，文本證據(jù)權(quán)等。

本文針對互信息(MI)特征選擇方法分類效果較差的現(xiàn)狀，提出了一種改進(jìn)的互信息特征選擇方法CMI。該方法考慮了特征項在當(dāng)前文本中出現(xiàn)的頻率以及互信息值為負(fù)數(shù)情況下的特征選取，從而能更有效地過濾低頻詞。在文本自動分類器KNN上的實驗表明該方法極大地提高了分類精度。

1 互信息特征選擇方法

文本集中的單詞、短語往往多達(dá)數(shù)萬甚至數(shù)十萬個，如果直接用來構(gòu)成文本特征向量，必將帶來所謂的“維數(shù)災(zāi)難”和計算復(fù)雜性太高，不能滿足實際的性能需求等問題。因此，很有必要對特征向量進(jìn)行降維處理。特征選擇的依據(jù)是特征對分類作用的大小，通常用一個統(tǒng)計量或者評價函數(shù)來度量，把度量值小于閾值T的那些特征過濾掉，剩下的即認(rèn)為是有效特征。選擇沒有改變原始特征空間的性質(zhì)，只是從原始特征空間中選擇了一部分重要的特征，組成一個新的低維空間[3]。

互信息(Mutual Information: MI)在統(tǒng)計語言學(xué)領(lǐng)域被廣泛使用[4]，它體現(xiàn)了特征與類型之間的相關(guān)程度。特征項t和類別之間的互信息定義[5]:

(1)

其中:P(t，c)為C中出現(xiàn)特征t的文本數(shù)除以訓(xùn)練集的大小;P(t)為訓(xùn)練集中出現(xiàn)t的文本數(shù)除以訓(xùn)練集的大小;P(c)為訓(xùn)練集中屬于類型C的文本所占的比例。

如果有m個類型，于是對每個特征項t都有m個值，通常取它們的平均，即平均互信息。平均值大的特征被選擇的可能性大。平均互信息如公式(2)所示:

(2)

2 改進(jìn)的互信息方法

互信息體現(xiàn)著特征與類型之間的相關(guān)程度，當(dāng)特征的出現(xiàn)只依賴于某一類型時，特征與該類型的互信息很大，當(dāng)特征與類型相互獨立時，互信息為0;在進(jìn)行特征選擇時，分別計算出各個特征項的MI值，從原始特征空間中刪除低于既定閾值的特征項，將高于該閾值的特征項構(gòu)成文本向量的特征子集?；バ畔⒃u估函數(shù)沒有考慮特征項在當(dāng)前文本中出現(xiàn)的頻率，在公式(2)中，不同特征項在訓(xùn)練集中出現(xiàn)的概率和在類ci中出現(xiàn)的概率相同時，低頻詞比高頻詞的MI值更高，即此種情況下低頻詞易被選入特征子集中，從而影響了分類的效果。在計算MI值時加上特征項頻率的條件限制，能有效地過濾低頻詞。

從公式(2)可以得出，P(t，ci)/P(ci)描述的是特征 出現(xiàn)在類ci中的概率，P(t)描述的是特征 在訓(xùn)練集中出現(xiàn)的概率。P(t)值越小，且P(t，ci)/P(ci)值越大，則計算出的互信息值就越大，該特征項就越有可能被選取;反之，P(t)值越大，且P(t，ci)/P(ci)值越小，則計算出的互信息值就越小，甚至為負(fù)數(shù)，該特征項被選取的可能性也就越小。但是互信息值是負(fù)數(shù)說明該特征項很少或不出現(xiàn)在當(dāng)前類別中，而是出現(xiàn)在其他類別中， 即負(fù)相關(guān)。進(jìn)行特征選擇時，通常會把負(fù)值大的特征項過濾掉，而實際上，這些特征項對正確分類也具有重要的意義。

綜合以上兩個因素，我們對公式(2 )進(jìn)行如下變換來改進(jìn)互信息方法，即帶限制條件的互信息方法(Constrained Mutual Information: CMI):

(3)

其中f(t)為特征項在當(dāng)前文本中出現(xiàn)的頻率，其它同公式(2 )。對于低頻詞，按公式(3)計算的CMI值將小于其MI值，從而有利于過濾掉低頻詞;對于負(fù)相關(guān)的特征詞，按公式(3)計算的CMI值為正數(shù)值，從而很可能選為特征子集。

3 實驗及其分析

3.1 語料集

實驗采用的訓(xùn)練集和測試集來源于中科院計算所譚博士整理的中文文本分類語料庫-TanCorpV1.0( 下載地址為: http//www.searchforum.org.cn/ tansongbo/corpus.htm )，我們把其中的數(shù)據(jù)平均分成兩半分別組成訓(xùn)練集TanCorpTrain和測試集TanCorpTest。

3.2 評價標(biāo)準(zhǔn)

文本分類中普遍使用的性能評估指標(biāo)有查全率R(Recall)、查準(zhǔn)率P(Precision)、F1測試指標(biāo)、宏平均F1和微平均F1等。查全率=被正確分類的文本數(shù)/被測試文本總數(shù);查準(zhǔn)率=正確分類的文本數(shù)/被分類器識別為該類的文本數(shù);對于一次測試，準(zhǔn)確率和查全率一般是成反比的。提高準(zhǔn)確率，查全率會下降;提高查全率，準(zhǔn)確率會下降。F1指標(biāo)綜合了P和R兩個指標(biāo)，可以對分類器進(jìn)行整體評價，如公式(4)所示:

F1=2 × P × R / (P + R)(4)

宏平均F1和微平均F1是以兩種不同的平均方式求得的全局F1指標(biāo)。

3.3 分類器及實驗

K最近鄰居算法(KNN)是文本分類中比較著名的經(jīng)典分類算法，我們應(yīng)用KNN分類器進(jìn)行了實驗，其中概率估算方法采用基于詞頻統(tǒng)計，特征選擇方式采用全局選取;

實驗比較結(jié)果如表1以及圖1、圖2所示。

從表1以及圖1、圖2的實驗數(shù)據(jù)可以看出，在相同的訓(xùn)練集和測試集條件下，改進(jìn)的互信息方法所取得的分類效果遠(yuǎn)高于未經(jīng)改進(jìn)的互信息方法。這說明了在計算MI值時加上特征項頻率的條件限制，能有效地過濾低頻詞，并且計算所得的那些互信息負(fù)值大的特征項，對文本分類同樣具有重要意義。

4 結(jié)束語

互信息是常用的一種特征評估函數(shù)，但在實際的中文文本分類中其分類精度一直較低。該文分析了其影響分類精確度的兩個因素，提出了一種改進(jìn)的特征選擇方法，該方法考慮了特征項在當(dāng)前文本中出現(xiàn)的頻率以及互信息值為負(fù)數(shù)情況下的特征選取，從而能更有效地過濾低頻詞，在文本自動分類器KNN上的實驗表明該方法極大地提高了分類精度。

參考文獻(xiàn):

[1] Lewis D D.An evaluation of phrasal and clustered representations on a text categorization task[C].Proceedings of 15th ACM International Conference on Research and Development in Information Retrieval (SIGIR-92)，1992:37-50.

[2] Kohavi R，John G H.Wrappers for feature subset selection[J].Artificial Intelligence Journal，1997，97(1-2):273-324.

[3] Aha D W，Bankert R L.A comparative evaluation of sequential feature selection algorithms[C].Proceedings of the 5th International Workshop on Artificial Intelligence and Statistics，1995:1-7.

[4] Church L W. Hanks P K.Word association norms，mutual information and lexicography[C].Vancouver，Canada:Proceedings of ACL27，1989:76-83.

[5] Yang Yiming，edersen J O.A comparative study on feature selection in text categorization[C].Proceedingsof the 14th International Conference on Machine Learning (ICML-97)，1997:412-420.