基于詞頻和文本類別的互信息改進(jìn)算法

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

基于詞頻和文本類別的互信息改進(jìn)算法

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

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

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

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

0 引言

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

本文針對(duì)互信息算法選擇特征后分類精度不高的不足，提出了一種基于詞頻和文本類別的互信息改進(jìn)算法。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法比原算法有更高的準(zhǔn)確性。

1 文本特征選擇相關(guān)技術(shù)

1.1 文本預(yù)處理

1.1.1 文本分詞

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

1.1.2 詞匯過濾

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

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

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

互信息(Mutual Information)是根據(jù)某個(gè)特征詞的出現(xiàn)情況來衡量它對(duì)某個(gè)文本類別的重要程度[7]。因?yàn)榛バ畔⑺惴ǘ攘苛颂卣髟~和文本類別之間的關(guān)聯(lián)信息，所以在統(tǒng)計(jì)語(yǔ)言模型中被廣泛采用。特征詞與類別的互信息MI(T,C)定義如下：

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

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

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

在計(jì)算相似度時(shí)，將同類別的相似度相加求和，然后對(duì)計(jì)算結(jié)果進(jìn)行排序，將待分類文本歸到相似度和最大的那個(gè)類中。計(jì)算公式如下：

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

2 互信息特征選擇算法的改進(jìn)

2.1 互信息算法的局限性

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

2.2 強(qiáng)信息特征標(biāo)準(zhǔn)

強(qiáng)信息特征是具有很強(qiáng)的文本分類能力和表述能力的詞語(yǔ)，一般受以下三個(gè)指標(biāo)影響[9]：

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

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

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

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

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

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

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

2.3 基于詞頻和文本類別的互信息改進(jìn)算法

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

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

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

MIFC算法相較于MI算法，主要有兩點(diǎn)改進(jìn)：

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

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

圖1 類別相關(guān)系數(shù)與類別個(gè)數(shù)的關(guān)系圖

3 實(shí)驗(yàn)設(shè)計(jì)及結(jié)果

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

本實(shí)驗(yàn)的訓(xùn)練文本、測(cè)試文本均采用復(fù)旦大學(xué)提供的語(yǔ)料庫(kù)，從計(jì)算機(jī)、環(huán)境、經(jīng)濟(jì)、體育和政治5個(gè)類別中分別選取100篇文本，總共500篇，構(gòu)成實(shí)驗(yàn)的訓(xùn)練文本集。此外，再?gòu)倪@5個(gè)類別中分別挑選另外的100篇文本，總共500篇，構(gòu)成實(shí)驗(yàn)的測(cè)試文本集。

本實(shí)驗(yàn)的分詞系統(tǒng)采用中科院的ICTCLAS 4j系統(tǒng)[10]。ICTCLAS系統(tǒng)功能強(qiáng)大，不僅有較高的分詞準(zhǔn)確性，還能對(duì)詞匯進(jìn)行詞性標(biāo)注，方便用戶進(jìn)行詞性統(tǒng)計(jì)。在ICTCLAS系統(tǒng)的基礎(chǔ)上，可以通過程序?qū)崿F(xiàn)特征選擇。

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

圖2 實(shí)驗(yàn)流程圖

3.2 實(shí)驗(yàn)結(jié)果及分析

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

圖3 當(dāng)K=40時(shí)，MI與MIFC分類的準(zhǔn)確率比較

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

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

4 結(jié)論

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

[1] 范小麗, 劉曉霞. 文本分類中互信息特征選擇方法的研究[J]. 計(jì)算機(jī)工程與應(yīng)用, 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] 盧新國(guó), 林亞平, 陳治平. 一種改進(jìn)的互信息特征選取預(yù)處理算法[J]. 湖南大學(xué)學(xué)報(bào): 自然科學(xué)版, 2005, 32(1): 104-107.

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

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

[6] 李英. 基于詞性選擇的文本預(yù)處理方法研究[J]. 情報(bào)科學(xué), 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].成都: 西南交通大學(xué), 2010.

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

[10] 劉群, 張華平, 俞鴻魁, 等. 基于層疊隱馬模型的漢語(yǔ)詞法分析[J].計(jì)算機(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

上海市科委國(guó)際合作基金項(xiàng)目(10510712500)

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

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

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