一种面向不均衡数据集的IG特征选择改进算法

骆魁永

(信阳农林学院 信息工程学院，河南 信阳 464000)

随着网络技术的迅速发展，当前社会已步入大数据时代，文本内容分析已成为实现大数据价值发现的有效手段，文本分类[1-2]作为大数据价值挖掘的关键技术，广泛应用于信息检索、内容信息过滤、自然语言处理和信息组织与管理等多个领域。然而，在对海量电子文档的分类中，发现数据不均衡分布的情况普遍存在，数据集中不同类别之间的文本数量可能存在数量级的差距，这给文本分类带来了新的挑战。特征选择作为文本分类的重要一环，选择算法的优良也直接影响分类模型的构建以及分类的准确性。目前，文本分类研究中常用的特征选择方法有：互信息、文档频率、信息增益、期望交叉熵、开方拟合检验、特征权等。Ng[3]比较了互信息(MI)、开方拟合检验(CHI)、特征权(TS)、文档频率(DF)和信息增益(IG)五种特征选择算法，得出IG、CHI和DF比MI和TS效果好的结论。Yang等[4]研究得出IG是最有效的特征选择算法之一。目前IG算法已成为文本分类研究中常用的特征选择算法，因此，在不均衡数据集中，寻找该方法不足，并做出有效改进，进而提高特征提取的效率具有非常重要的现实意义。

传统的IG特征选择方法在特征项选择的过程中往往会出现类别不平衡问题，导致分类器对小类别的分类效果较差。目前，一些学者指出了IG特征选择算法存在的缺点，并提出了相应的改进措施。文献[5-6]指出在不均衡的数据集中，由于不同类别样本数目相差很大，那些对于小类分布影响较大的特征项其信息熵变化值不如大类影响大的特征项显著，针对这一问题，通过对条件熵部分增加了权重系数，来改进IG算法；文献[7]提出改进的信息增益算法，通过添加权重值来平衡正、负相关特征，由于权重值需要人为根据经验设定，设定的细微不同可能导致较大的分类差异，而且简单设定权重值并不适用于多种应用场景；文献[8-9]在以上改进算法的基础上，通过引入特征分布差异因子、类内和类间加权因子，提出一种加权的IG-C改进算法，该方法比较全面地考虑到了词频对特征提取的作用；但该算法没有考虑数据集的不均衡性和特征项频数在类内分布情况对分类的影响。本文针对上述改进算法的不足，引入了类内词频加权因子、类内词频分散度加权因子和类间词频集中度加权因子对传统IG算法进行改进，提出了一种改进的IG特征选择方法。通过选取复旦大学计算机信息与技术系整理的语料库中部分文档[10]，采用SVM和KNN两种分类算法进行实验，实验结果表明，本文改进的特征选择方法相较于其它已改进的算法在不均衡数据集上有较好的的分类效果。

1 改进的IG特征选择算法

1.1 引入类内词频加权因子

传统的IG算法只考虑了特征项在所有文档出现的次数，而没有考虑特征项在指定类中出现的次数，即IG算法只考虑了特征项的文档频数，没有考虑特征项在指定类中的词频，从而放大了低频词对指定类别的分类价值。

例如：假设在类别Ci中，特征项tp和tq在类别Ci中大多数文本出现且在其它类别中很少出现甚至不出现，那么这两个特征项都有可能是类别Ci的特征项，根据IG公式计算出的两个特征项与类别之间的IG值应该基本相近。然而在Ci类文本内部当tp出现的频数远大于tq出现的频数，也就是说特征项tp对Ci类的分类价值远大于特征项tq时，利用IG算法计算的IG值仍相近。因此可以得出影响特征项t对C类文档分类能力有两个因素：包含特征项t的文档在类别C中的频数与特征项t在C类内各个文档的词频数，传统的IG算法只考虑了第一个因素，却没有考虑第二个因素。

由于在不均衡数据集中，各类别之间文档频数差异比较大，仅仅通过词频数来度量特征项的频繁程度，算法往往会更倾向于选择大类的特征项，这对小类别的特征项选择是不公平的，影响了小类别的分类效果。为了避免对大类的特征项的这种选择倾向性，本文引入类内词频加权因子来度量特征项在不平衡数据集的频繁程度，表示如公式(1)所示：

(1)

考虑到在不均衡数据集中，不同类别的文档数量的差异性将式(1)做归一化处理：

(2)

其中：m是特征向量的纬度阈值；tf(Ci,wj)表示特征项wj在类别Ci中出现的次数。类内词频加权因子α度量了在不平衡数据集下特征项w在某一类别C中出现的频繁程度，显然，频数越高的特征项w其对应的权重α越大，即式(1)反映了类内出现频数越大的特征项其具有的分类价值越大。

1.2 引入类内词频分散度加权因子

传统的IG模型没有考虑特征项在类内各文档的分布情况。根据先前学者的研究可知，具有分类价值越大的特征项，其在指定类别中不仅出现的频数大，而且在该类各文档中要均匀地出现，若只出现在该类的个别文档而在其它文档中很少出现，则表明该特征项具有的分类价值就比较低。

例如：特征项tp在类别Ci的文本中均匀出现，特征项tq仅在类别Ci的个别文本中出现，且出现的频数比tp大。在这种情况下，由于特征项tp在类内均匀出现，特征项tp对类别Ci的分类价值更高些，但是通过传统的IG算法却得到相反的结果。为了解决上述问题，本文引入类内词频分散度加权因子β，由样本方差的思想可知，特征项在某一类别文档中分布越均匀，总体方差就越小，其分类能力越强，反之，样本方差值越大，其分类能力越弱。记tf(tk,dij)表示特征词tk在类别Ci中的文档dij中出现的次数，Mi表示类别Ci中的文档数，那么各个频数之间的样本方差可以表示为：

(3)

由于特征项在类内分布越均匀其出现的频数方差越小，即特征项的分类能力与方差值成反比关系。因此需对上述参数归一化后还应修正：

(4)

其中：m是特征向量的纬度阈值。类内词频分散度加权因子β度量了在不平衡数据集下特征项tk在类内分布情况，显然，特征项tk在类别Ci中各文档之间分布越均匀，β的值就越大，该特征项对该类的分类价值就越高。

1.3 引入类间词频集中度加权因子

除了特征项的频数和特征项在类内分布情况之外，特征项的频数在类间的分布差异也能体现特征项对类别的分类能力。假设一个特征项在每一个类别都出现很多次，而另外一个特征项只在某一个类中均匀出现且在其它类别中出现很少或则几乎不出现，显然后一个特征项要比前一个特征项具有更高的分类价值，即类别间特征项的频数方差与特征项的分类能力成正比。记n是类别总数；tf(Ci,wj)表示特征项wj在类别Ci中出现的次数，那么特征项wj在各个类别Ci中出现频数之间的样本方差可以表示为：

(5)

考虑到在不均衡数据集中，不同类别的文档数量的差异性将式(5)做归一化处理：

(6)

其中：m是特征向量的纬度阈值。类间词频集中度加权因子λ度量了在不平衡数据集下特征项tk在类间的频数分布情况，显然，特征项tk在类间的频数分布越集中，λ的值就越大，该特征项对分类价值就越高。

在Im-IG特征选择算法基础上，引入上述所得权重参数α、β、λ进行修正，得到改进算法：

(7)

式(7)综合考虑了数据集的不均衡性与特征项频数对分类的影响，对传统IG算法优化得到改进的特征选择算法。

2 实验结果与分析

2.1 实验数据

为了验证本文所提方法的合理性，选用复旦大学计算机信息与技术系国际数据库中心自然语言处理小组整理的语料库。在语料库的20个类别当中，选取了计算机、艺术、经济、政治、体育、环境和历史这7个类别，选取类别中文本分布呈现较大差异性，其中最大类中包含1600个文本，最小类中只包含123个文本，具体文本分布如表1所示。

表1 不同类别文档数选取情况

2.2 评价指标

目前对分类器性能评价指标通常选取查全率、准确率、F1三项指标。由于在不均衡数据集的分类中，分类结果极易偏向大类，如果仍然采取传统评价指标，则无法真实评价分类器的实际性能。本文采用宏平均查全率、宏平均准确率以及宏平均F1指标对分类结果进行评价。

(1)宏平均查全率为：

(8)

式(8)中，ri表示第i个类别的查全率；|K|表示类别总数。

(2)宏平均准确率为：

(9)

式(9)中，pi表示第i个类别的准确率。

(3)宏平均F1为：

(10)

式(10)中，F1i表示第i个类别的F1值。

2.3 实验流程

(1)文档预处理过程的分词选用jieba分词工具。

(2)对文档集中的每一个待求特征，分别使用文献[5]改进的Im-IG算法、文献[8]提出的IG-C算法以及本文改进的IG算法计算其信息增益值。

(3)每一种算法均分别选取信息增益值最大的前50、100、200、400、800、1600个特征词构成50、100、200、400、800、1600维的特征向量空间。

(4)使用文本分类中常用的TF-IDF权重算法计算向量空间中各特征值的权重值。

(5)本文采用Weak[11]数据挖掘开源平台进行文本分类实验，输入各分档的特征权重值，分别使用两种经典的算法SVM(选用线性核函数)和KNN算法进行分类实验。将文档集平均分成10份，采用十折交叉验证方法，分别选取50、100、200、400、800、1600个特征值进行实验。

2.4 结果分析

表2、3列出了使用Im-IG算法、IG-C算法以及本文算法在实验数据上进行特征选择，并分别使用SVM和KNN进行分类的实验结果。可以看出，当特征数目小于800时，使用本算法进行特征选择获得的宏平均值比其它两种方法提高了5%左右，特征数量为800时获得M_F1值最大，特征数超过800时其M_F1值趋于稳定；当选择的特征数为400时，采用本文算法优势比较明显，已经达到了其它两种算法特征数为800时的宏平均准确率和宏平均查全率，表明本文方法能够更早地获得较好的分类效果。

表2 基于SVM分类算法对比实验结果

表3 基于KNN分类算法对比实验结果

改进算法在传统算法基础上，充分考虑了数据集不均衡、特征项频数在类内、类内分布情况以及类间分布情况对算法的影响，对传统IG算法的参数进行了修正。综合上述实验结果来看，本文提出的改进的IG特征选择算法在不均衡数据集上文本分类上效果比较理想。

3 结束语

数据集的不均衡在文本分类中是一个普遍存在的问题。本文针对传统的IG特征选择算法的缺陷，以及对已有改进算法深入分析的基础上，充分考虑了数据集的不均衡与特征项频数对分类的影响，引入类内词频加权因子、类内词频分散度加权因子和类间词频集中度加权因子，提出了一种改进的IG特征选择方法，降低了类别分布不均匀和特征分布不均匀在分类中所带来的干扰。实验结果表明，改进后的特征选择效果相对于传统算法和其它改进算法在不均衡数据集上的分类效果明显提高。