一種改進的互信息特征選擇方法

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

關鍵詞:中文文本自動分類;特征選擇;互信息

中圖分類號:TP311文獻標識碼: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

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

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

1 互信息特征選擇方法

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

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

(1)

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

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

(2)

2 改進的互信息方法

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

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

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

(3)

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

3 實驗及其分析

3.1 語料集

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

3.2 評價標準

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

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

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

3.3 分類器及實驗

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

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

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

4 結束語

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

參考文獻:

[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.