董 微，劉 學(xué)，倪 宏（1.中國(guó)科學(xué)院大學(xué)，北京100049；.中國(guó)科學(xué)院 聲學(xué)研究所 國(guó)家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心，北京100190）

0 引 言

目前基于統(tǒng)計(jì)理論和機(jī)器學(xué)習(xí)的分類方法成為了文本自動(dòng)分類的主流技術(shù)，典型的算法有支持向量機(jī)模型（SVM）［1］、貝葉斯（Bayes） 決策模型［2］、K近鄰分類（KNN）模型［1，3］、決策樹 （decision tree）分類模型等。上述方法主要采用向量空間模型，而文本自動(dòng)分類的主要困難之一是向量空間模型中特征向量的維度很高，若不加篩選地采用全部分詞作為特征向量，將導(dǎo)致特征向量稀疏，而其中很大一部分的分詞所攜帶的詞義較少，給分類引入了較大的噪聲，不僅降低了分類的速度，也嚴(yán)重影響了分類的精度。因此，提高文本分類的精度和速度，去除特征向量中的噪聲，降低特征向量的維度，是文本分類中需要解決的主要問(wèn)題之一?，F(xiàn)比較成熟的特征選擇方法主要有：文檔 頻 數(shù) （DF）［4］、 信 息增益（IG）［5，6］、 期望交叉熵（ECE）、互信息 （MI）［7］、文本證據(jù)權(quán) （WET）、χ2統(tǒng)計(jì)量（CHI）［4］等。根據(jù) Yang Yiming等分析，信息增益是在特征選擇過(guò)程中表現(xiàn)出較好性能的方法之一。信息增益同時(shí)考慮了正相關(guān)特征和負(fù)相關(guān)特征，正相關(guān)特征與負(fù)相關(guān)特征對(duì)文本分類的貢獻(xiàn)按等比例進(jìn)行分配。實(shí)驗(yàn)結(jié)果表明：正相特征相比負(fù)相關(guān)特征對(duì)文本分類的作用大；負(fù)相關(guān)特征的出現(xiàn)對(duì)文本分類有一定的貢獻(xiàn)，同時(shí)也對(duì)分類有很大干擾；完全不考慮負(fù)相關(guān)特征又會(huì)導(dǎo)致分類精度下降。李文斌等通過(guò)添加比例因子來(lái)調(diào)節(jié)正相關(guān)特征和負(fù)相關(guān)特征帶來(lái)的信息量。但是，簡(jiǎn)單的添加比例因子帶來(lái)了一些問(wèn)題：首先，比例因子往往通過(guò)經(jīng)驗(yàn)選擇，算法對(duì)參數(shù)值非常敏感，設(shè)置的細(xì)微差別可能會(huì)導(dǎo)致分類效果差別很大；其次，不同維度的特征空間選用的比例因子也各不相同；最后，不同的文本庫(kù)中文本分布不同，選擇的比例因子也不相同，若將選擇的比例因子用于各種文本庫(kù)，反而會(huì)導(dǎo)致原算法分類精度的下降。因此，本文提出了一種方法，該方法能夠確定信息增益的比例因子。

1 信息增益的分析及改進(jìn)

1.1 信息增益的分析

信息增益定義參見文獻(xiàn) ［8］。信息增益的特點(diǎn)在于考慮了特征詞的負(fù)相關(guān)性，特征詞的負(fù)相關(guān)性對(duì)特征選擇做出貢獻(xiàn)的同時(shí)，也對(duì)特征的選擇有著很大的干擾［9］。如圖1所示，文本集包含類別為C（c1，c2，……，cn）（其中，n為文本類別數(shù)），陰影部分表示包含特征詞的文檔數(shù)。在圖1（a）中，c1中的文檔均包含特征詞t，c2，……，cn的文檔中均不包含特征詞t；在圖1（b）中，c1中的文檔均不包含特征詞t，c2，……，cn的文檔中均包含特征詞t。在這2種情況下，計(jì)算所得的信息增益值相同，這種情況的產(chǎn)生是由于信息增益中特征正相關(guān)性和特征負(fù)相關(guān)性等比例分配造成的。然而，圖1（a）的情況是我們所期望的，而圖1（b）的情況是我們希望盡量避免。

圖1 信息增益存在的問(wèn)題

為了增強(qiáng)特征正相關(guān)性對(duì)信息增益的貢獻(xiàn)，減小特征詞負(fù)相關(guān)性對(duì)信息增益的干擾，設(shè)信息增益為式 （1）所示，其中α，β是為正相關(guān)特征和負(fù)相關(guān)特征添加的比例因子，α＋β＝1，α＞β，因此0.5＜α＜1，0＜β＜0.5

式中：P（t）——特征詞t在文本中出現(xiàn)的概率，P（ci｜t）——文本包含t時(shí)屬于ci類的條件概率，P（ci）——ci類文本在文本集中出現(xiàn)的概率，P——文本中不包含特征詞t的概率，P（ci｜——文本不包含詞條t時(shí)屬于ci類的條件概率，｜C｜——類別總數(shù)。

然而通過(guò)簡(jiǎn)單的添加比例因子，往往需要人為的經(jīng)驗(yàn)，而且設(shè)置的比例因子并不通用，并不是所有維度的特征空間和所有的分類集都可以使用相同的比例因子。因此，如何設(shè)置合適的比例因子是一個(gè)亟待解決的問(wèn)題。

1.2 信息增益的改進(jìn)

以經(jīng)驗(yàn)對(duì)信息增益的特征正相關(guān)性和特征負(fù)相關(guān)性添加比例因子使得分類效果并不理想，取得的比例因子也并不通用［10］，因此需要確定一種添加比例因子的方法，使添加比例因子的信息增益能夠適用于各種維度的特征空間和各種文本分布的語(yǔ)料庫(kù)。

對(duì)原始信息增益公式分析可知，當(dāng)只有ci類包含特征詞t，而在 （～ci）的類中均不包含特征詞t時(shí)，此種特征分布下，P（ci｜為1，而 ～P（ci｜t）的值均為0，如圖1（a）所示，此時(shí)特征正相關(guān)性取值能夠達(dá)到最大，有利于提高分類器在c1上的查全率；當(dāng)只有ci類不包含特征詞t，而在 （～ci）的類中均包含特征詞t時(shí)，P（ci｜）為1，而～P （ci｜）的值均為0，如圖1（b）所示的情況，此時(shí)特征負(fù)相關(guān)性取值能夠達(dá)到最大，此種特征分布有利于提高分類器在c1上的查全率。測(cè)量結(jié)果中為平衡分類器在c1上的查全率和查準(zhǔn)率，本文選用F1作為計(jì)算分類結(jié)果的度量，來(lái)調(diào)節(jié)比例因子。F1的定義參見文獻(xiàn) ［11］。如表1所示，Postitve表示分類為該類別的文本數(shù)，Negative表示分類為非該類別的文本數(shù)，表1顯示了實(shí)際分類的文本數(shù)與測(cè)量分類的文本數(shù)。

表1 實(shí)際與測(cè)量結(jié)果

實(shí)驗(yàn)結(jié)果表明：比例因子在最優(yōu)組合的鄰域范圍外進(jìn)行改變時(shí)會(huì)導(dǎo)致分類結(jié)果的巨大改變，只有當(dāng)比例因子在最優(yōu)組合的鄰域內(nèi)進(jìn)行微調(diào)時(shí)對(duì)分類結(jié)果的影響較小。因此本文提出一種方法，通過(guò)改變信息增益的比例因子，將改進(jìn)的信息增益作為文本分類預(yù)處理算法，對(duì)文本進(jìn)行分類，根據(jù)分類結(jié)果的好壞，自動(dòng)調(diào)節(jié)比例因子，直至2次分類結(jié)果的F1差值小于設(shè)置的閾值。

在計(jì)算合適的比例因子前，需要做的準(zhǔn)備工作如下：首先，選取語(yǔ)料庫(kù)，將其中2／3的文本集作為訓(xùn)練集，將其中1／3的文本集作為測(cè)試集；第二，將語(yǔ)料庫(kù)中的文本集進(jìn)行中文分詞，去掉其中的停等詞以及頻率過(guò)高和過(guò)低的詞，構(gòu)建訓(xùn)練集的特征空間；第三，設(shè)置前后2次分類結(jié)果的度量差值的最大閾值，以及比例因子增長(zhǎng)的步長(zhǎng)；第四，選取合適的分類算法。通過(guò)以上分析可知，α＞β，且0.5＜α＜1，0＜β＜0.5，對(duì)α，β進(jìn)行初始化，選取α＝β＝0.5。計(jì)算比例因子的算法描述如下：

算法描述：

Input：

（1）D｛d1，d2，……dN）為文本集；

（2）C｛c1，c2，……cm）為預(yù)定義的分類；

（3）T（t1，t2，……tn）為特征集；

（4）ξ為F1變化差值的閾值，δ為α變化的增量；

（5）Train （T，α，β）為分類文本的算法；

Output：合適的比例因子α，β。

Steps：

1 令F1＝0，α＝0.5，β＝0.5

2 loop：F1′ ＝ Train （T，α，β）

3 ΔF1＝｜F1′－F1｜

4 ifΔF1＜ξ

5 returnα，β

6 else

7 α＝α＋δ，β＝β－δ

8 F1＝F1′

9 go loop

算法分析：

本算法按照最壞情況計(jì)算時(shí)間復(fù)雜度。步驟1的時(shí)間復(fù)雜度為時(shí)間常量，即為Ο （1）。設(shè)步驟2中采用的分類算法的時(shí)間復(fù)雜度為Ο（T），在最壞情況下步驟2的循環(huán)次數(shù)為因此步驟2的時(shí)間復(fù)雜度為在每次循環(huán)過(guò)程中，步驟3～9的時(shí)間復(fù)雜度為Ο （1），因此該算法的時(shí)間復(fù)雜度為因此，采用本算法選取合適比例因子的同時(shí)，也給算法增加了復(fù)雜度，但由于δ只是線性增加，只是在原有算法復(fù)雜度的基礎(chǔ)上增加了一個(gè)比例系數(shù)，算法復(fù)雜度沒(méi)有很大增加。

2 實(shí)驗(yàn)及分析

由于貝葉斯算法在統(tǒng)計(jì)算法中計(jì)算速度較快，本文選取貝葉斯算法作為文本分類算法。

本文針對(duì)中文文本進(jìn)行分類，分析比較DF、χ2、IG以及改進(jìn)的IG分別作為預(yù)處理算法，測(cè)試在平衡數(shù)據(jù)集和非平衡數(shù)據(jù)集上的分類效果，見表2和表3。每種類別的文本集中選取其中2／3的文本集作為訓(xùn)練集，選取其中1／3的文本集作為測(cè)試集。

利用中國(guó)科學(xué)院計(jì)算技術(shù)研究所研發(fā)的中文分詞工具ICTCLAS3.0對(duì)文本集進(jìn)行中文文本分詞，獲得特征集以及特征詞的詞性，去掉一些低頻詞、高頻詞以及一些攜帶詞義不大的詞性的特征詞，包括時(shí)間詞、處所詞、方位詞、區(qū)別詞、狀態(tài)詞、代詞、數(shù)詞、量詞、副詞、介詞、連詞、助詞、嘆詞、語(yǔ)氣詞、擬聲詞、前綴、后綴、字符串、標(biāo)點(diǎn)符號(hào)；僅保留名詞、動(dòng)詞、形容詞、成語(yǔ)等。實(shí)驗(yàn)結(jié)果如下所示。

表2 平衡數(shù)據(jù)集語(yǔ)料庫(kù)

表3 非平衡數(shù)據(jù)集語(yǔ)料庫(kù)

表4 顯示在平衡數(shù)據(jù)集，選取不同數(shù)目的特征向量時(shí)獲取的最佳比例因子，以及采用改進(jìn)的信息增益作為預(yù)處理算法時(shí)計(jì)算得到分類結(jié)果的F1值。表5表示在非平衡數(shù)據(jù)集上，顯示結(jié)果見表4。

表4 平衡數(shù)據(jù)集比例因子

表5 非平衡數(shù)據(jù)集比例因子

圖2 顯示了在平衡數(shù)據(jù)集上，分別采用DF、χ2、IG以及改進(jìn)的IG作為預(yù)處理算法，在不同維度的向量空間上，對(duì)文本進(jìn)行分類，計(jì)算所得的F1值。圖3顯示了在非平衡數(shù)據(jù)集上的測(cè)試結(jié)果。

由實(shí)驗(yàn)結(jié)果分析：

從表4和表5中可以看出：①特征詞數(shù)目的多少對(duì)選取比例因子有一定的影響；②特征詞多比特征詞少分類的精度度要高；③改進(jìn)的信息增益在平衡數(shù)據(jù)集上測(cè)試結(jié)果比在非平衡數(shù)據(jù)集上的測(cè)試結(jié)果要好。

從圖2和圖3中可以看出：①在平衡數(shù)據(jù)集和非平衡數(shù)據(jù)集上，改進(jìn)的IG在分類效果上比DF、IG、CHI表現(xiàn)得好；②在平衡數(shù)據(jù)集上，IG、CHI和改進(jìn)的IG表現(xiàn)出來(lái)的性能相近；③在非平衡數(shù)據(jù)集上，IG、CHI的性能有所下降，改進(jìn)的IG性能比較好；④在平衡數(shù)據(jù)集和非平衡數(shù)據(jù)集上，α，β取值并不相同。

3 結(jié)束語(yǔ)

信息增益是一種比較成熟的特征選擇方法，且其在文本分類效果上有較好的表現(xiàn)，本文對(duì)其優(yōu)點(diǎn)以及不足進(jìn)行了分析。信息增益的特點(diǎn)在于考慮到了特征不出現(xiàn)的情況，特征不出現(xiàn)對(duì)文本分類做出了貢獻(xiàn)，然而也對(duì)特征選擇有很大的干擾，因此，信息增益添加合適的比例因子，對(duì)文本分類有很好的改進(jìn)效果。本文對(duì)如何選擇合適的比例因子進(jìn)行了研究，提出了一種基于信息增益的自適應(yīng)方法，通過(guò)實(shí)驗(yàn)結(jié)果表明，該方法不僅能夠適用于不同數(shù)目的特征空間也能適用于多種文本集合，選用改進(jìn)的信息增益作為預(yù)處理算法，可以大大提高了分類的準(zhǔn)確性。

［1］Gayathri K，Marimuthu A.Text document preprocessing with the KNN for classification using the SVM ［C］／／Coimbatore，Tamil Nadu，India：7th International Conference on Intelligent Systems and Control，2013：453－457.

［2］Zheng Gong，Tian Yu.Chinese Web text classification system model based on naive bayes［C］／／Henan：International Conference on E－Product E－Service and E－Entertainment，2010：1－4.

［3］Yao Bin，Li Feifei，Kumar P.K nearest neighbor queries and kNN－Joins in large relational databases （almost）for free［C］／／Long Beach，CA：26th IEEE International Conference on Data Engineering，2010：4－15.

［4］Li Yujian，Zhou Lanzhen，Cao Weiping.Joint feature selection method of document frequency and CHI with application to Web pages categorization ［J］.Journal of Beijing University of Technology，2008，34 （9）：995－1000.

［5］Lei Shang.A feature selection method based on Information gain and genetic algorithm ［C］／／Hangzhou：Proceedings of the International Conference on Computer Science and Electronic Engineering，2012：255－358.

［6］Fan Dongmei，Zhang Rubo，Lu Zhimao，et al.Chinese word sense disambiguation based on Bayesian model improved by information gain ［J］.Journal of Electronics and Information Technology，2008，30 （12）：2926－2929.

［7］Lu Zhimao，Shi Hong，Zhang Qi，et al.Automatic Chinese text categorization system based on mutual information ［C］／／Changchun：Mechatronics and Automation，ICMA，2009：4986－4990.

［8］Xu Yan，Li Jintao，Wang Bin，et al.A study on constraints for feature selection in text categorization ［J］.Journal of Computer Research and Development，2008，45 （4）：596－602.

［9］Tanmay Basu，Murthy CA.Effective text classification by a supervised feature selection approach ［C］／／Brussels：the 12th IEEE International Conference on Data Mining Workshops，2012：918－925.

［10］Guo Yawei，Liu Xiaoxia.Study on information gain－based feature selection in Chinese text categorization ［J］.Computer Engineering and Applications，2012，48 （27）：119－127.

［11］Liu He，Liu Dayou，Pei Zhili，et al.A feature weighting scheme for text categorization based on feature importance［J］.Journal of Computer Research and Development，2009，46 （10）：1693－1703.