文本分类中信息增益算法的改进

杨敬妹　王学军

摘 要： 分析了信息增益方法的不足，并将类内离散度、类间离散度和权重协调因子应用到信息增益算法上，提出了一种改进的信息增益算法。实验表明，该方法在分类效果上与经典算法相比有一定的提高。

关键词： 特征选择； 信息增益； 类内离散度； 类间离散度； 权重协调因子

中图分类号：TP312 文献标志码：A 文章编号：1006-8228（2013）09-45-02

0 引言

信息科学技术和互联网技术每天都在更新，人们通过网络获得的信息资源越来越多，与此同时，就需要更多的人力和时间来整理网络里的各种信息，因此产生了文本分类技术。文本数据的特点就是高维性和稀疏性[1-2]。文本分类算法在分类的时间上，带来大量时间开销；特征过多又往往会出现“维数灾难”的问题，特征选择就此产生。常用的特征选择方法是：信息增益、互信息、χ2统计量、特征词频-文档频率等。很多人倾向于信息增益方法，因为它考虑了特征词条未发生的情况。实验证明这种贡献在多数情况下远远小于它带来的干扰。本文提出了一种新的特征选择方法，并通过实验证明了该方法能有效提高文本分类的精度。

1 信息增益特征选择方法

信息增益（Information Gain）[3]在机器学习领域被广泛使用，在信息论中，样本属性的信息增益越大，其包含的信息量也越大。对分类系统来说，计算信息增益是针对一个一个的特征项而言的，它通过统计某一个特征项t在类别ci中出现与否的文档数来计算特征项t对类别ci的信息增益，定义为考虑出现前后的信息熵之差，定义如公式⑴：

⑴

式⑴中，P（ci）表示ci类文档在语料中出现的概率，P（t）表示语料中包含t的文档的概率，P（ci|t）表示文档包含t时属于ci类文档的条件概率，表示语料中不包含特征词条t的文档概率，表示文档不包含特征词条t时属于ci类的条件概率，m表示文档类别数。

显然，某个特征项的信息增益值越大，表示其贡献越大，对分类也越重要。因此，在进行特征选择时，通常选取信息增益值大的若干个单词构造文本的特征向量。信息增益的优点在于，它考虑了词条未发生的情况，即虽然某个单词不出现也又可能对判断文本类别有贡献。但是实验证明，这种贡献往往远远小于考虑单词不出现情况所带来的干扰。

2 信息增益特征选择算法的改进

信息增益特征选择方法的不足之处是：忽视了类间、类内分布不平衡的问题[4]；对特征项出现的频率考虑不全面。近些年，不少学者都在改进信息增益算法，来减小它带来的干扰，如利用语义联系改进信息增益算法[5]；利用最大值与次大值之间的差作为最终的评价函数值[6]；把频度、集中度、分散度都考虑上的算法[7]；通过构造隶属度函数来改进[8]。本文引入类间集中度DIac（t）、类内分散度DIic（t）和权重协调因子ω来对原始的算法进行改进。

2.1 类间离散度

一般情况下，如果一个特征项在一个类别中大量出现，而在其他类别中较少出现，那么这个特征项对于类别判定的贡献度应该是比较大的，这种特征项相对于类别的倾斜特性使用类间离散度来衡量，即权衡一个特征相对于所有预定类别的分布均衡程度，分布越不均衡，那么这个特征对于类别判定的贡献度越大。类间离散度用来描述特征在类间的分布情况，特征项的类间离散度计算如公式⑵：

从公式⑵中可以看出，那些集中分布在个别类或者几个类别的特征项，其类间离散度的值比较大，这些特征项一般具有较强的类别区分能力，当特征词条t仅在一个类别中出现的时候，DIac取最大值1，此时的分类能力最强；当特征词条t在每个类别中都出现的时候，DIac取最小值0，其分类能力最弱。

2.2 类内离散度

在衡量了特征相对于类别的均衡程度后，还应该考虑特征在一个类别内的分布情况。如果一个特征在一个类别内的某个文本中大量出现，而其他文本出现很少或不出现，那么这个特征对于文本的分类贡献较少；反之，则特征对于类别区分的贡献度是比较大的。对于类别内的特征分布情况，我们可以使用类内离散度来衡量，即权衡一个特征相对于一个类别的分布均匀程度，分布越均衡，那么这个特征对于类别判定的贡献程度越大。类内离散度描述了特征项在某个类中的分布情况，特征项t在类ci中的类内离散度计算如公式⑶：

⑶

式⑶中，n代表ci类中的文档个数，fj（t）表示词条t在ci类的第j篇文档中的词频，表示词条t在类ci文档中的平均词频。其中的计算公式为：。

类内离散度越小，说明该词条越集中分布在该类中，其区分类别的能力越强。由公式⑶可以看出，当特征向量t在本类别中所有文档中都出现的时候，DIic取最小值0，此时的分类能力最强，可见DIic的值与其分类能力是成反比的。

2.3 权重协调因子

根据很多实例判断，特征词在语料库中出现次数多少并不能完全表征该特征词在分类中的重要程度，频率相同的特征词对分类的重要程度也是不同的，在各类别中分布越均匀，其对分类的重要性就越小，反之就越大。考虑到方差这一数学指标能够较好地体现数据分布是否均匀这一特征，进而通过方差除以该特征词在各类中的词频之和来得到权重协调因子的定义如公式⑷：

⑷

式⑷中，P（ci|t）表示文档包含t时属于ci类文档的条件概率，m表示文档类别数。

2.4 信息增益算法的改进

对于分类而言，如果一个特征项在某个类别中大量出现，在其他类别中较少出现，且该特征在大量出现的类别中分布比较均匀，那么显然这个特征对于分类是有利的，在类间、类内离散度上的表现为类间离散度较大，类内离散度较小。所以在衡量分类贡献度时，应将类间离散度和类内离散度综合考虑，另外加入了权重协调因子，来对信息增益的方法可以更进一步的提高它的计算精度。

利用公式⑷计算出特证词条t的权重协调因子ω，然后再对文档里所有的特征词出现的概率进行求和处理，利用公式⑵求出类间离散度DIac（t），利用公式⑶得出类内离散度DIic（t），加入到改进算法之内，使得新算法可以进一步提高计算精度。具体算法如公式⑸：

⑸

3 实验结果及分析

文本预处理阶段采用了汉语词法分析系统ICTCLAS对文本集合中的数据进行分词，用Lucene建立全文索引；在测试数据时，实验采用KNN（k-Nearest Neighbor）分类器（KNN算法是一种常用的，效果较好的文本分类算法）。

3.1 语料集

为了验证改进算法的有效性，尽可能地消除语料选取不当所带来的干扰。本实验搜集了中文文本分类语料库，选用了3000篇文本，其中包括计算机、军事、教育、经济、政治、体育6大类，其中采用1800篇文本作为训练集，其余1200篇文本作为测试集。

3.2 评估指标

⑴ 查全率

定义为正确分类的正例个数占实际正例个数的比例，表示为公式⑹：

⑵ 查准率

定义为正确分类的正例个数占分类为正例的实例个数的比例，表示为公式⑺：

⑶ F1评估值

在信息检索领域，查全率与查率是一对相互制约的指标。查准率和查全率反映了分类质量的两个不同方面，两者必须综合考虑。因此，列入了F1测试值作为评价指标，它是查全率与查准率的调和平均数，表示为公式⑻：

⑻

3.3 实验结果及分析

经典算法的分类结果如表1所示。

根据表1中的数据，得出平均的F1测试值为85.533%。

改进算法的分类结果如表2所示。

从表2中可以看出，各种类别的分类效果都很好，平均的F1测试值为86.786%，相比原来的算法，提高了信息增益的精度，效果还是令人满意的。

4 结束语

本文仔细分析了传统的信息增益算法的不足， 并针对其进行了广泛的研究，最终提出了一种改进的信息增益算法。实验证明，改进后的算法与传统算法相比，在分类准度和精度上都有了更好的表现。但是改进的算法增大了计算的难度，将会导致分析的时间变长。下一步工作将从缩短时间的角度来继续研究，深入分析对分类性能有影响的因素，完善新算法。

参考文献：

[1] Y. Li， D.F. Hsu， S.M. Chung， Combining multiple feature selection methods for text categorization by using rank-score characteristics[C]. IEEE 21st International Conference on Tools with Artificial Intelligence， Newark，NJ，USA，Nov.2009：508-517

[2] B. Yu， Z. Xu， C. Li.Latent semantic analysis for text categorization using neural network[J].Knowledge-Based Systems，2008.21（8）：900-904

[3] 苗夺谦，卫志华.中文文本信息处理的原理与应用[M].清华大学出版社，2007.

[4] Harun Uguz.A two-stage feature selection method for text categorization by using information gain， principal component analysis and genetic algorithm[J]. Knowledge-Based Systems，2011.24（7）：1024-1032

[5] 张浩.基于语义关联的文本分类研究[J].舍肥工业大学学报，2011.

[6] 张玉芳，万斌候，熊忠阳.文本分类中的特征降维方法研究[J].计算机应用研究，2012.29（7）：2541-2543

[7] 刘庆和，梁正友.一种基于信息增益的特征优化选择方法[J].计算机工程与应用，2011.12.