基于信息增益的文本特征选择方法

王理冬

摘要：在类和特征分布不均时，传统信息增益算法的分类性能急剧下降。针对此问题，提出一种改进的基于信息增益的文本特征选择方法。首先，降低了低频词对特征选择的影响。其次，使用离散度分析特征词在类间的文档频率，增加波动性大的特征词的权值。通过对比实验分析表明，选取的特征具有更好的分类性能，并且对于不平衡数据集表现也较好。

关键词：文本分类；信息增益；特征选择；不平衡数据集；离散度分析

中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2017）25-0242-03

Abstract： Due to the highly skewed distributions of classes and features， the classification accuracy of algorithms Based on traditional information gain algorithm will decline sharply. This paper proposes a new feature selection method to improve the performance of traditional information gain method. Firstly， the proposed new feature selection method can decrease the interference of low frequency Words to feature selection. Secondly， it analyses the variances of inter-class document frequencies of feature Word that have large variances of inter-class document frequency. Because the feature Word have large variances is more representative than other features when the distributions of classed and features are highly skewed. The comparison experiment on some real data sets shows that the proposed method is more effective and has better classification performance in imbalanced data set as compared with the traditional information gain method.

Key words：Text Classification； Information Gain； Feature Selection； Imbalanced Data Set； Dispersion Analyse

文本分類是文本挖掘的一个重要部分，其内容是按照预定义的类别将待分类文本进行归类。在这个过程中，特征选择和特征提取是文本分类的首要任务和关键问题，其中文本向量化是基础。文本向量化的过程中，特征词的权重用来衡量该特征对描述文本内容的重要程度。特征词的权重计算的准确度成为影响文本分类的重要因素。

因为文本数据的半结构化特点，使得文本表示的特征向量高达几万甚至几十万维。即使经过简单的预处理，如去除停用词、稀有词、高频词，依旧会有很多高维数的特征向量留下。然而向量空间的高维性和文档向量的稀疏性不仅增加了分类的时间复杂度和空间复杂度，还影响分类精度。因此在文本分类中，特征选择就显得尤为重要。

特征选择主要用于排除特征空间中那些被认为关联性不大的特征，通过降低特征空间的维度以及去除噪音特征来提高分类效率和精度。目前常见的特征选择方法有TFIDF、互信息（MI）、信息增益（IG）、卡方统计（CHI）等。其中信息增益是一种有效的特征选择方法。在文献[1]中作者提出了IG是最好的测度；在文献[2]中作者比较了文档评论，信息增益、互信息、卡方、特征权等5种特征选择方法，其证明了卡方效果最好，文档频率，信息增益及卡方之间存在着一定的相关性；在文献[3]中作者提出了三种基于特征信息增益权重的分类算法，通过添加权重系数来平衡特征项对分类的影响，但是由于权重系数的设置是根据人为的经验设定，所以存在很大的偶然性。在文献[4]中作者针对传统IG 算法过分看重高频特征项的缺点，提出一种强调中低频特征项的改进的算法，此算法在一定程度上提高了特征选择的效率，但算法中没有考虑到特征项在不同类别的分布差异对分类能力的影响。在文献[5]中作者在以上改进算法的基础上，通过按类进行特征选择，利用特征频率计算信息增益，再利用离散型分析去除相对冗余特征。实验表明该方法能有效的提取特征子集，此算法在一定程度上提高了特征选择的效率，但算法没有考虑到特征项在类内位置上分布对算法的影响。信息增益算法在平衡语料的情况下，表现良好，但在处理不平衡语料时其性能急剧下降。本文针对以上不足，充分考虑了特征项在类间的频数对分类能力的影响，提出了一种基于信息增益的词频改进的特征选择方法，实验表明该方法比传统的方法有更好的效果。

1 信息增益简介

1.1 熵和信息熵

熵是信息论中一个非常重要的概念，表示一种能量在空间中分布的均匀程度，其能力分布越均匀，熵就越大。1948年，信息论创始人香农将熵应用于信息处理中，并提出了“信息熵”的概念。

1.2 信息增益的不足

通过上面的公式发现，传统的信息增益方法是从整个训练集角度根据特征项的文档频数考察了特征项对整个系统的贡献程度。在不同类中分布相同或相近的特征项信息增益最小，说明该方法适合用来做全局的特征选择。但该方法过多地关注了文档频数，对词频的贡献没有给予足够的重视。其次，由于考虑了特征项不出现的情况，当每个类别中文档数差别明显时，即类别分布不平衡或特征项分布不均衡时，会使得在一个类别中出现次数不多而在其他类别中频繁出现的特征项被选取出来，而不倾向于选取在一个类别中出现较多而在其他类别中出现较少的更具代表性的特征项。endprint

2 K最近邻算法

KNN算法以其简单性、有效性而成为基于向量空间模型（VSM）的最好分类算法之一。

假定文本训练集为S，S 有M 个类别[c1]，[c2]，……，[cM]，S 的总文本数为N。在KNN算法的训练阶段，首先对文本训练集S 进行分词，接着对特征维数进行降维，最后把训练集文本表示为特征向量：[Di]= {[X1]，[X2]，……，[Xn]}T （0

（0

分类文本D 归属到隶属度最大的类别。KNN算法的具体步骤如下：

步骤1 对文本训练集进行中文分词。

步骤2 对训练集文本进行特征选择。

步骤3 把训练集文本进行向量化。

步骤4 对待分类文本进行步骤1到步骤3的处理工作。

步骤5 利用向量夹角余弦公式来计算待分类文本D与训练集文本Di的相似度。

步骤6 选出与待分类文本D 最相似K 个文本作为文本D 的最近邻。

步骤7 根据这K 个最近邻，计算待分类文本D 在各个类别里的隶属度。我们以所属类别数作为其隶属度。

步骤8 选出隶属度最大的类别，并将待分类文本D归入到该类别中。

2 传统信息增益的改进算法

2.1 降低低频特征的影响

传统的信息增益方法考虑了特征项出现和不出现两种情况，但在类别分布不平衡或者特征项在类间分布不平衡的情况下，由于大多数特征项在某些类别中是不出现的，此时的信息增益值主要依赖于特征项不出现情况下所带来的信息量的大小，即此时信息增益的值由公式的后半部分决定。然而这些不出现的词对文档分类的贡献远小于对分类的干扰，其大大降低了信息增益方法提取特征的效果，因此我们应该去除这些“无用词”。

2.2 改进类间不平衡的影响

通过分析易知，在所有类别中分布均匀的特征项对系统的分类贡献最小，也就是说分布不均匀对系统的贡献反而大。

通过离散度分析，利用特征项在每个类中的文档频率，分析每个特征项在数据集中的波动性。我们使用方差来做离散度度量。特征项在每个类间的分布的方差越大，说明该分布越不均匀，即该特征项越集中分布在某个类，越能代表该类特征，反之，方差越小，该分布越均匀，即该特征项越均匀分布在每个类中，越不能代表某个类。设m表示类别总数，训练集中特征项t在类别Cj中的文档频率为DFtj（在类别Cj中出现特征项t的文档频数除以类别Cj中的总文档数），DFt表示特征项的平均文档频率，那么特征項t的文档频率的方差DVt就表示如下：

2.3 基于IGDV的分类算法流程

中文文本分类的对象是一篇篇文档，为了使用机器学习的方法来进行分类，首先需要将它进行向量化表示。而这一过程，我们首先要进行中文分词，然后去除停用词，进行特征分析提取，选择适合的特征词，最后用特征词向量，来对文档进行向量化，使用机器学习的分类方法对其进行分类，其整个算法流程如下：

（1） 对文档进行中文分词，去除停用词，这里主要提取其中的名词、形容词等。这个阶段也称为预处理。

（2） 选用本文的IGDV算法对文本进行特征选择。

（3） 使用TFIDF方法构建向量空间模型，这里的特征值取TFIDF*IGDV。

（4） 对训练文本使用前面的特征选择结果，进行向量化，使用KNN算法进行文本分类。

（5） 根据分类结果，计算其评价。我们这里采用的评价指标是MarcoP，MarcoR，MarcoF1。

3 实验结果及分析

3.1 评价指标

评价文本分类系统好坏的指标我们采用MarcoP，MarcoR，MarcoF1。各评价参数定义如下：

3.2 实验分析

为了验证IGDV特征选择算法的有效性，本文对上述的特征选择方法的分类效率进行实验。实验包括分词、特征选择和分类测试几部分。其中分词我们采用中科院的汉语词法分析系统ICTCLAS2015，实验数据集我们选取了复旦大学中文语料库，分类算法我们采用了KNN文本分类器对样本进行分类，使用java语言编程实现。

1） 对平衡数据集的实验

从语料库中我们选取4000篇文本，包括农业、环境、经济、政治、体育各800篇，其中每个类抽400篇作为训练集，剩下的400篇作为测试集。选取1000个特征词进行实验，实验的结果数据如表1所示。

由表1可以看出，在平衡数据集下，改进后的信息增益方法相比较传统的信息增益方法在MacroP、MacroR、MacroF1 三个指标上都有一定程度的提高。

2） 对不平衡数据集的实验

从语料库中我们选取4000篇文本，包括农业600篇、环境600篇、经济1200篇、政治800篇、体育800篇，其中农业200篇、环境200篇、经济800篇、政治400篇、体育400篇作为训练集，剩下作为测试集。选取1000个特征词进行实验，实验的结果数据如表2所示。

由表2可以看出，在不平衡数据集下，改进后的信息增益方法相比较传统的信息增益方法在MacroP、MacroR、MacroF1 三个指标上都有很大的提高。

综上，改进后的信息增益方法不论在平衡数据集还是不平衡数据集下，相比传统的信息增益特征选择方法，都很有很好的表现。

4 结束语

本文针对传统信息增益方法的不足进行了改进。通过分析，我们去除了公式中低频部分的影响；使用离散性分析，考虑了文档频率的波动性，降低了类间不平衡的影响。实验表明，在数据集平衡和不平衡的条件下，改进后的信息增益特征选择算法的分类效果上都有很大程度的提高。下一步的工作是将此方法应用到我们的系统中，来检验它的适用性，并进一步完善此方法，以进一步提高分类效率和分类精度。

参考文献：

[1] Yang Yiming，Pedersen J Q.A Comparative Study On Feature Selection In Text Categorization[C]//Proceedings of the 14th International Conference on Machine Learning（ICML97）. Nashvillr：Morgan Kaufmann Publisher，1997：412-420.

[2] Ng H， Goh W， Low K. Feature Selection，Perception Learning and A Usability Case Study For Text Categorization[C]//Proceedings of the 20th ACM International Conference on Research and Development in Information Retrieval（SIGIR-97）.1997：67-73.

[3] 李文斌， 劉椿年， 陈嶷瑛. 基于特征信息增益权重的文本分类算法[J]. 北京工业大学学报， 2006，32（5）：456-460.

[4] 黄秀丽， 王蔚. 一种改进的文本分类特征选择方法[J]. 计算机工程与应用， 2009， 45（36）：129-130.

[5] 任永功， 杨荣杰， 尹明飞， 马名威. 基于信息增益的文本特征选择方法[J].计算机科学， 2012，39（11）：127-130.

[6] 周萌清. 信息理论基础[M].北京： 北京航天航空大学出版社， 2002.

[7] Vapnik V. The nature of statistical learning theory[M].New York：Springer，1999.

[8] 刘庆和， 梁正友. 一种基于信息增益的特征优化选择方法[J]. 计算机工程与应用，2011，47（11）：130-132.

[9] 裴英博. 中文文本分类中特征选择方法的研究与实现 [D]. 西北大学， 2010.

[10] 杨玉珍， 刘培玉， 朱振方等. 应用特征项分布信息的信息增益改进方法研究[J]. 山东大学学报：理学版， 2009， 44（11）：48-51.

[11] 郭亚维， 刘晓霞. 文本分类中信息增益特征选择方法的研究[J]. 计算机工程与应用， 2012， 48（27）：119-122.

[12] 任永功， 杨雪， 杨荣杰， 胡志东. 基于信息增益特征关联树的文本特征选择算法[J]. 计算机科学， 2013， 40（10）：252-256.

[13] 张振海， 李士宁， 李志刚， 陈昊. 一类机遇与信息熵的多标签特征选择算法[J]. 计算机研究与发展，2013， 50（6）：1177-1184.

[14] 李学明， 李海瑞， 薛亮， 何光军. 基于信息增益与信息熵的TFIDF算法[J].计算机工程， 2012， 38（8）：37-40.

[15] 张玉芳， 陈小莉， 熊忠阳. 基于信息增益的特征词权重调整算法研究[J]. 计算机工程与应用， 2007， 43（35）：159-161.

[16] 石慧， 贾代平， 苗培. 基于词频信息的改进信息增益文本特征选择算法[J].计算机应用， 2014， 34（11）：3279-3282.endprint