謝 力，李光耀，譚云蘭,2

基于詞頻和文本類別的互信息改進算法

*謝 力1，李光耀1，譚云蘭1,2

（1.同濟大學電子與信息工程學院，上海201804；2. 井岡山大學電子與信息工程學院，江西，吉安 343009）

分析了傳統(tǒng)的互信息特征選擇算法的不足，針對可能賦予低頻特征詞過高權重的問題，利用詞頻、集中度這兩個強信息特征指標對算法進行改進，提出了一種基于詞頻和文本類別的互信息改進算法(Improved Mutual Information Algorithm based on Word Frequency and Text Category，簡稱改進的MIFC)。實驗結果表明，改進的MIFC算法提取的特征空間比傳統(tǒng)的互信息算法有更高的精確度。

互信息；特征選擇；詞頻；文本類別；MIFC

0 引言

文本特征選擇是指從高維的特征空間中選擇出最能代表文本內容的特征項，是文本分類過程中一個至關重要的技術環(huán)節(jié)。好的特征選擇算法不僅能夠降低文本特征空間的維數(shù)，提高文本分類器分類的效率，還能去除對文本分類無效的特征，提高分類的精度[1]。目前文本分類有很多種特征選擇算法，常用的有文檔頻率法、互信息法、信息增益法、期望交叉熵法和χ2統(tǒng)計法等。在研究互信息特征選擇算法方面，國內外很多學者從不同角度提出了改進方案。Battiti在互信息法提取特征空間的基礎上，計算特征項兩兩之間的關聯(lián)度，對關聯(lián)度大的特征項組二者取其一[2]。盧新國等提出了一種基于互信息特征選取的改進算法(IMI)，加強了互信息為負值的特征項在分類中的作用[3]。劉海峰等從權重因子、修正因子和位置差異三個方面入手，重新調整了特征項的權重，提高了互信息法的特征選擇效率[4]。

本文針對互信息算法選擇特征后分類精度不高的不足，提出了一種基于詞頻和文本類別的互信息改進算法。實驗結果表明，改進后的算法比原算法有更高的準確性。

1 文本特征選擇相關技術

1.1 文本預處理

1.1.1 文本分詞

在中文文本預處理過程中，一般可以選擇字、詞語或詞組作為文本的特征項。用單個字作為特征項容易導致特征空間龐大，影響分類效率；用詞組作為特征項容易導致特征空間稀少，損失很多重要信息。相比而言，用詞語作為特征項比字具有更強的表達能力，而且在切分時要比詞組更容易實現(xiàn)。因此，一般選用詞語來提取中文文本的特征項，這個操作稱為文本分詞[5]。

1.1.2 詞匯過濾

詞匯過濾是指去掉對區(qū)分文本類別影響較弱的特征詞（又稱“弱信息詞”），保留對區(qū)分文本類別影響較強的特征詞（又稱“強信息詞”）。弱信息詞包括介詞、連詞和助詞等虛詞，比如：“是”、“的”、“能”、“所”、“在”、“從而”、“并且”等。它們出現(xiàn)頻率很高，但對于區(qū)分文本類別沒有參考價值。強信息詞主要包括名詞和動詞，是具有代表性的關鍵詞匯，可以表達出文本的主題。

一個原始特征空間可能包含數(shù)十萬個不同特征詞，如果不對這些原始特征詞進行過濾，不僅會增加特征提取算法的處理時間，而且對算法的精確度也會產(chǎn)生不利的影響。為了對原始特征空間進行降維，就必須去除弱信息詞[6]。

1.2 互信息(MI)特征選擇算法

互信息(Mutual Information)是根據(jù)某個特征詞的出現(xiàn)情況來衡量它對某個文本類別的重要程度[7]。因為互信息算法度量了特征詞和文本類別之間的關聯(lián)信息，所以在統(tǒng)計語言模型中被廣泛采用。特征詞與類別的互信息MI(T,C)定義如下：

其中，(,)表示包含且屬于的文本在訓練文本集中出現(xiàn)的概率，()為包含的文本出現(xiàn)的概率，()為屬于類文本的概率。如果用表示包含特征詞T且屬于類別的文本頻數(shù)，為包含但是不屬于的文本頻數(shù)，表示不包含但是屬于的文本頻數(shù)，表示訓練文本集中的文本總數(shù)，那么特征詞和類別的互信息可由下式計算：

1.3 K近鄰(KNN)文本分類算法

K近鄰法(K Nearest Neighbor)是一種基于實例的機器學習方法，相關研究證明該算法是向量空間模型下最好的分類算法之一。KNN的分類過程可以理解成：先將訓練文本集中的所有文本表示成向量空間。當一個待分類文本到達時，計算該文本與向量空間中每個文本的相似度，并將相似度值按降序排列，取出排在最前面的K篇文本。最后按這K篇文本的類別權重對待分類文本進行歸類[8]。

在計算相似度時，將同類別的相似度相加求和，然后對計算結果進行排序，將待分類文本歸到相似度和最大的那個類中。計算公式如下：

其中，表示選取的文本數(shù)，j(d)表示文本是否屬于類(是為1，否為0)，sim(,d)可以由向量夾角余弦(公式2.4)求得。其中，1i，2i分別表示文本1，2的特征空間中相應特征項的權重。兩個向量夾角的余弦值越大，相似度越高。

2 互信息特征選擇算法的改進

2.1 互信息算法的局限性

互信息算法主要研究的是含有特征詞的文本出現(xiàn)在類別內的概率以及整個訓練文本集里和出現(xiàn)的概率，并沒有考慮的詞頻因素。這樣，低頻特征詞的作用可能會被放大，導致對分類沒有明顯效果的詞語獲得了更高的互信息值而成為特征項，影響特征空間對文本的表示能力。

2.2 強信息特征標準

強信息特征是具有很強的文本分類能力和表述能力的詞語，一般受以下三個指標影響[9]：

（1）頻數(shù)：某個特征詞在某類文本中出現(xiàn)次數(shù)越多，就越能代表這類文本。因此，應該選擇在同類文本中出現(xiàn)頻數(shù)最高的若干詞語作為該類文本的特征項。

（2）分散度：對于某個類別有標引價值的特征，應該均勻地分布在該類別的各個文本中，而不是集中出現(xiàn)在某幾個文本中。分散度表示某個特征詞與某個類別之間的關聯(lián)程度，可以通過互信息法公式(1.1)或(1.2)計算。若在類文本中分布地越分散，則(,)越高，對的分類價值越高。

（3）集中度：對于某個類別有標引價值的特征，應該集中出現(xiàn)在這個類文本中，而不是均勻地分布在各個類別的文本中。集中度表示特征項與所有類別之間的關聯(lián)程度。與類別之間的關系會有以下三種情況：

①只出現(xiàn)在一個類別的文本中，則對這個類別的區(qū)分很有價值。

②出現(xiàn)在兩個或多個類別的文本中，則對沒有其出現(xiàn)的類別很有分類價值。

③出現(xiàn)在所有類別中，則對分類幾乎沒有價值。

從強信息特征的三個指標可以看出，對于某個特征詞，其頻數(shù)、分散度、集中度越大，則它對文本分類能力就越強。

2.3 基于詞頻和文本類別的互信息改進算法

根據(jù)強信息特征的特點，本文綜合考慮了詞頻和集中度兩個指標，提出了基于詞頻和文本類別的互信息改進算法MIFC，公式如下：

(T,C)(() ×R)/100 (2.1)

其中，表示出現(xiàn)在類文本中出現(xiàn)的頻數(shù)， R表示的類別相關系數(shù)，表達式如(3.2)所示。為訓練文本集中的類別總數(shù)， C為包含的文本所屬類別的個數(shù)。

MIFC算法相較于MI算法，主要有兩點改進：

（1）引入頻數(shù)指標。統(tǒng)計在中出現(xiàn)的次數(shù)。若出現(xiàn)的次數(shù)越多，就越大，對的分類價值越大。

（2）引入集中度指標。根據(jù)集中度指標中特征項與類別之間的關系可知，若出現(xiàn)在測試文本集中的類別個數(shù)越少，則集中度越大，分類能力越強，應該給予更大的類別相關系數(shù)。同時，的類別相關系數(shù)與其出現(xiàn)的類別個數(shù)之間是一個非線性的關系，隨著出現(xiàn)的類別個數(shù)增多，其類別相關系數(shù)減小地越快（如圖1所示）。

圖1 類別相關系數(shù)與類別個數(shù)的關系圖

3 實驗設計及結果

3.1 實驗設計

本實驗的設計思路：首先對訓練文本進行預處理并建立特征空間，其中技術環(huán)節(jié)包括文本分詞和詞匯過濾。然后，利用MI或者MIFC算法計算各個特征項的權重，從高到低排序，取前面N個形成特征空間。接著，基于特征空間和KNN算法實現(xiàn)分類器。最后，將預處理過后的測試文本導入分類器分類，得到實驗結果。實驗的流程如圖2所示。

本實驗的訓練文本、測試文本均采用復旦大學提供的語料庫，從計算機、環(huán)境、經(jīng)濟、體育和政治5個類別中分別選取100篇文本，總共500篇，構成實驗的訓練文本集。此外，再從這5個類別中分別挑選另外的100篇文本，總共500篇，構成實驗的測試文本集。

本實驗的分詞系統(tǒng)采用中科院的ICTCLAS 4j系統(tǒng)[10]。ICTCLAS系統(tǒng)功能強大，不僅有較高的分詞準確性，還能對詞匯進行詞性標注，方便用戶進行詞性統(tǒng)計。在ICTCLAS系統(tǒng)的基礎上，可以通過程序實現(xiàn)特征選擇。

本實驗分別使用MI和MIFC兩種特征選擇算法提取100維的特征空間，并通過KNN算法實現(xiàn)分類器，比較兩個特征空間的分類能力。通過不斷調試參數(shù)，發(fā)現(xiàn)K=40時，分類的準確率最高。

圖2 實驗流程圖

3.2 實驗結果及分析

利用MI與MIFC提取的兩個不同的特征空間，分別對測試文本集中的500篇文本進行分類，并與文本原來所屬的類別進行比較，統(tǒng)計兩種算法下各個類別分類的準確率。統(tǒng)計結果如圖3所示。

圖3 當K=40時，MI與MIFC分類的準確率比較

對于計算機、環(huán)境、經(jīng)濟、體育、政治5個類別，每個類別各100篇文本的測試集，使用MIFC算法查準的文本數(shù)分別為97、94、86、95、89篇，使用MI算法查準的文本數(shù)分別為96、90、83、95、85篇。

從實驗結果可以看出，除了體育類文本（兩者準確率相同），MIFC算法的分類準確率都要高于MI算法。因此，以MIFC作為特征選擇算法得到的分類結果較MI算法具有更高的準確性，同時也驗證了使用MIFC算法提取的特征空間比MI算法提取的特征空間具有更強的文本分類能力。

4 結論

本文重點研究了在中文文本分類中的互信息特征選擇算法，針對互信息算法可能賦予低頻特征詞過高權重的問題，引入了特征詞頻數(shù)和文本類別權重對互信息算法做了進一步的改進。實驗結果表明，改進的MIFC算法確實提高了特征選擇的精確度和文本分類的準確率。

[1] 范小麗, 劉曉霞. 文本分類中互信息特征選擇方法的研究[J]. 計算機工程與應用, 2010, 46(34): 123-125.

[2] Battiti R. Using Mutual Information for Selecting Features in Supervised Neural Net Learning[J]. IEEE Transactions on Neural Networks, 1994, 5(4): 537-550.

[3] 盧新國, 林亞平, 陳治平. 一種改進的互信息特征選取預處理算法[J]. 湖南大學學報: 自然科學版, 2005, 32(1): 104-107.

[4] 劉海峰, 陳琦, 張以皓. 一種基于互信息的改進文本特征選擇[J]. 計算機工程與應用, 2012, 48(25): 1-4.

[5] 劉依璐. 基于機器學習的中文文本分類方法研究[D].西安: 西安電子科技大學, 2009.

[6] 李英. 基于詞性選擇的文本預處理方法研究[J]. 情報科學, 2009, 27(5): 717- 719.

[7] Estévez P A., Tesmer M, Perez C A. Normalized Mutual Information Feature Selection[J]. IEEE Transactions on Neural Networks, 2009, 20(2): 189-200.

[8] 劉慧. 基于KNN的中文文本分類算法研究[D].成都: 西南交通大學, 2010.

[9] 陳平, 劉曉霞, 李亞軍. 文本分類中改進型互信息特征選擇的研究[J]. 微電子學與計算機, 2008, 25(6): 194-196.

[10] 劉群, 張華平, 俞鴻魁, 等. 基于層疊隱馬模型的漢語詞法分析[J].計算機研究與發(fā)展,2004,41(8): 1421-1428.

An Improved Mutual Information Algorithm based on Word Frequency and text Category

*XIE Li，LI Guang-yao，TAN Yun-lan

(1.School of Electronics and Information, Tongji University, Shanghai 201804, China)(2.School of Electronics and Information Engineering, Jinggangshan University, Ji’an, Jiangxi 343009, China)

This paper analyzes the shortages of Mutual Information (MI) algorithm. Aiming at the problem that low frequency features may have higher weights, we take advantage of two indexes of strong informational features–word frequency and concentration ratio and propose an improved MI algorithm based on word frequency and text category (MIFC). The result of the experiment shows that MIFC algorithm has greater accuracy than traditional MI algorithm.

mutual information; feature selection; word frequency; text category; MIFC

TP391

A

10.3969/j.issn.1674-8085.2013.03.010

1674-8085(2013)03-0041-04

2013-03-17；

2013-03-24

上海市科委國際合作基金項目(10510712500)

*謝 力(1989-)，男，浙江臺州人，碩士生，主要從事數(shù)據(jù)挖掘、虛擬現(xiàn)實研究 (E-mail: Robert3443@126.com)；

李光耀(1965-)，男，安徽安慶人，教授，博導，主要從事大規(guī)模城市建模與仿真、數(shù)據(jù)挖掘研究(E-mail:lgy@#edu.cn)；

譚云蘭(1972-)，女，江西新干人，副教授，同濟大學博士生，主要從事圖像處理，數(shù)據(jù)挖掘研究(E-mail: tanyunlan@163.com).