-
随着信息时代的迅速发展，信息数据呈指数级增长，面对如此巨大的信息资源，如何有效地管理，使人们更加方便快捷地获得目标信息成为研究热点.文本信息挖掘中的文本分类技术有效解决了这一问题，文本分类是指未知类别的文本根据其内容信息，自动分类为一个或多个预先定义的类别[1].文本分类的核心问题是通过一种算法构建分类器，文本分类方法有很多，常见算法有Rocchio算法、朴素贝叶斯分类算法、KNN算法[2]、神经网络算法、SVM算法[3]等.近年来，最大熵模型对未知事件尽可能使其分布均匀的特性，使得该算法在文本分类中得到研究与应用.
文本分类系统常采用向量空间模型(VSM)来实现文本信息描述，VSM的特征项涉及整个文本的词条，导致了VSM的高维性[4-5]，这对分类训练时间及准确性造成了很大影响.特征选择实现了对VSM文本特征的降维处理，在文本分类时能够保留携带信息量大、对分类贡献大的词，在降低文本特征空间维数的同时提高分类性能[6].特征选择常用方法有互信息、开方检验、特征权(TS)、信息增益(IG)等.互信息(Mutual Information, MI)表示2个变量之间的相关性，可以看成是一个随机变量中包含的关于另一个随机变量的信息量.信息IG算法考虑特征词条未发生情况的优点使得其得到更多应用，常用于图像相关性处理和文本分类.
文献[7]针对传统IG算法的缺陷提出了一种改进IG算法，该算法引入特征分布差异因子、类内和类间加权因子，分类准确度优于传统算法，但是改进算法增大了算法计算复杂度，使得分类时间变长.文献[8]通过引入比例因子提出了自适应IG算法，该算法自动调节比例因子，使得改进IG算法适用于平衡数据集和非平衡数据集等不同的语料库，同时解决了信息增益特征选择方法等比例地组合正、负相关特征导致文本分类中分类精度下降的问题.文献[9]根据特征对IG贡献大小及在新文本中出现的次数，设计了3种基于IG特征权重的分类算法，能够在保证分类精度的同时提高训练速度，算法具有较低的时间复杂度.文献[10]针对传统IG算法的缺点，对IG算法进行改进，该算法首先对数据集类别选择特征，然后优化合并不同类别特征，通过合并特征的出现概率来计算IG权重，并引入类内和类间分布因子，改进IG算法优于传统算法.
通过对传统IG算法及已有的改进算法进行分析研究，本文提出了一种新的改进IG算法.该算法通过引入均衡比和类内词频位置参数，解决了传统IG算法忽略词频分布对分类的弱化问题和局部特征选择缺陷，修正传统类内词频位置参数，提高特征选择算法对分类精度的影响，并将该改进IG特征选择算法用于最大熵模型对文本进行分类，性能优于传统IG算法及其他分类算法.
HTML
-
信息增益(IG)是基于熵理论的评估方法，亦是一种很有效的特征选择方法，具有考虑特征词条未发生情况的优点.对于特征选择，就是将特征的重要程度量化之后再进行选择，而如何量化特征的重要性，就成为各种特征选择算法间最大的不同.开方检验量化方法的特点是关联性越强的特征越重要，其方法是使用特征与类别间的关联性来量化特征重要性. IG特征选择算法的特点是特征携带信息越多，特征越重要，IG是根据特征能够为分类系统带来多少信息来量化特征重要性.
IG被定义为通过减少变量的不确定性而获得的信息量：IG(X，Y)=E(X)-E(X|Y). IG计算的是词条特征，由信息理论可知，一个术语贡献的信息量越大就越重要.术语f用于确定C类的信息增益值，定义如下
式中C代表语料库中的文档集合；P(Ci)表示属于文档集中出现类别Ci的概率；P(f)表示特征f出现在文件中的概率；P(f)表示文件中没有出现f的概率；P(Ci|f)表示包含f的文档属于类别Ci的概率；P(Ci|)表示包含f的文档不属于类别Ci的概率.
通过上述分析，可以得知IG算法是一种非常典型的监督特征提取算法，具有很好的降低特征维数的作用，并被广泛应用于文本分类研究.然而，传统IG算法存在一些问题，导致IG算法在文本分类中精度还有提升空间.针对IG算法中存在的问题，本文提出了改进IG特征选择算法，并将该算法与最大熵模型结合，使得本文算法在文本分类时性能达到最优.
-
IG算法中存在的问题主要有2个：
1) IG算法只考虑特征对整个系统的贡献，不能具体到一个特定的类别，这使得IG特征选择算法仅适合于进行所谓的“全局”特征选择(所有类别使用相同的特征集)，并且不能进行“本地”功能选择(因为每个类别都有自己的功能集，一些类别中的部分词出现次数很少).
2) 传统IG算法并没有考虑词频对文本分类的影响，2个特征项A和B分布在同一个文档中，即使A词频是B词频的10倍，仍然得到相同的IG值.当忽略词频分布时，只考虑文档频率可能会导致特征预测能力弱化，不能选择最有效的特征.
针对以上2个问题，本文对IG特征选择算法进行改进，引入了均衡比因子和类内词频位置参数来提高IG算法的性能.
-
均衡比因子是用来解决一个词在文档中出现多次与出现一次的IG值相同这个问题，IG算法中均衡比α表示词频在类别中分布均衡的程度.对于训练集中类别Ci(1≤i≤n)，特征fi在Ci类文本中出现的频数为tf(fi)，设λi=tf(fi)/∑tf(fi)，tf(fi)表示在类别Ci中词频f的频率数，则词频均衡比α可以定义为
其中，
$\bar \lambda = \left( {1/\mathit{n}} \right)\sum\limits_{i = 1}^m {{\lambda _i}} $ .假设有3个类别，每个类别包含5个文档，有2个特征项F1和F2，其分布见表 1.从表 1可以看出，F1较F2更频繁出现在类别1，因此判断F1具有较强的分类能力.但是用公式(1)计算时，2个特征值具有相同的IG值，如果引入词频平衡因子α，则可以得到不同的IG值，表 1中αF1＞αF2，表明词频均衡比因子可以有效地纠正IG限制.
-
在同一类别中每个文本的特征分布越均匀，特征分类能力就越强.因此，本文引入类内词频位置参数，该参数由样本方差反映，统计样本方差的本质是反映样本间的分散程度.假定在类别Ci(1≤i≤n)的文本dik(1≤i≤Ni)中，特征fi出现的频数为tf(fi)，则每个频率之间的样本方差为
类别中每个文本的频率方差变化越小，分类能力越强，两者之间的反比关系越大.因此，上述参数应归一化为
类别Ci文本的分布越均匀，则β越大，分类能力越强.
基于传统的IG算法引入了上述均衡比α和类内词频位置参数β，则改进了算法可表示为
-
最大熵模型是一种概率估计，该模型原理表明预测一个随机事件的概率分布时，应当满足全部已知的约束，而未知的情况下不做任何主观假设，这样使得概率分布最均匀，预测风险最小，能够得到概率分布的最大熵.
在本文中，将需要分类的一个文本作为一个事件，则待分类文本集合可表示为{(r1，s1)，(r2，s2)…(rN，sN)}，其中ri(1≤i≤N)为具体文本，表示文本分类结果.根据最大熵模型，模型的概率分布必须与获得最大熵的训练集一致，通过拉格朗日乘数算法，最大熵的概率分布为
其中，fi表示特征函数，f(r，s)→(0，1)，满足一定约束条件下取值为1，其他情况下取值为0；wi表示特征函数fi的权值，反映了特征对模型的重要程度，本文使用改进迭代算法计算权值；Zw(r)表示归一化因子，有
${Z_w}\left( r \right) = \sum\limits_s {{\rm{exp}}\left( {\sum\limits_i {{w_i}{f_i}\left( {r, s} \right)} } \right)} $ ，保证对所有可能的文本r则有$\sum\limits_r {p\left( {s\left| r \right.} \right) = 1} $ .改进IG算法解决了传统IG算法的缺陷，在特征选择将特征项在类间和类内分布的均匀程度考虑进来.另一方面，ME模型是比较成熟的模型，对比其他常用分类模型如SVM和KNN等，其分类性能优于其他分类模型.
2.1. 均衡比因子
2.2. 类内词频位置参数
2.3. 最大熵模型
-
通常我们评估文本分类的结果主要有3个方面：简单性、复杂性和算法的有效性.本文仅考虑评价指标的有效性，主要有准确度P、召回率R和F1值3个指标(表 2).
准确率是Ci中样本数与Ci类中实际样本数之间的比例，定义为
召回率是正确分类的样本数和样本数应按类别Ci正确分类的比例，定义为
准确率和召回率从2个方面反映了分类结果，一个是对完整性的研究，另一个是对正确性的研究.两者是成反比的，往往提高前者的表现会导致后者的表现下降.因此，对于两者的价值评估将综合考虑使用F1值，定义为
-
本文选取军事，金融，艺术，体育4个大类文件进行实验(表 3).
首先采用中国科学院开发的中文分词系统处理单词分割和去除停止词，然后使用改进的特征选择算法进行特征提取，最后采用最大熵模型及KNN算法用于分类测试.本文进行3次实验，第1次实验是验证本文特征选择算法的维数与分类性能的比较；第2次实验是改进IG特征与不同分类算法的性能比较；第3次实验是在搜狗实验室文本分类语料库上，对本文方法与传统IG方法进行比较实验.上述实验都是采用经典的十折交叉验证方法，实验文本平均分为10份，其中9份作为训练集，1份作为测试集，取10次分类结果的平均值作为测试结果.
分类方法采用最大熵模型算法，改进IG算法作为特征选择算法，特征维数对分类性能的影响见图 1.
从图 1可以看出，当特征维数为1 000时，F1值最好，本文后2项实验中特征维数都采用1 000.
在本文实验中，采用改进IG特征选择算法用于最大熵进行分类，并与KNN分类方法进行比较，特征选择的维数为1 000，分类结果见表 4.
从上述数据可以看出，基于改进的IG特征选择的ME分类方法F1值比KNN分类方法在体育文本的分类提高9.09%，在艺术方面分类提高最多为12.06%，说明本文提出的改进IG算法ME分类性能优于KNN算法.另外，选择搜狗实验室文本分类语料库作为实验对象，对本文算法进行验证，将本文算法与SVM和KNN分类算法进行比较，采用经典的十折交叉验证，得到F1值见表 5.
从表 5中可以得出，本文算法性能优于SVM和KNN算法.
改进IG算法下2种分类的F1值直观比较见图 2.
分类方法采用最大熵模型算法，将文本方法与传统IG算法进行对比实验，本次实验结果采用十折交叉方法，实验结果见表 6.
分析表 6和图 3内容，可以得出以下结论：基于改进的IG特征选择算法较传统IG算法，F1值军事文本分类提高最小，为6.97%，金融文本分类提高最多，达到9.27%，说明使用改进的IG算法用于ME分类方法在准确率、召回率和F1值3个方面都有提高，总体分类结果优于传统IG算法.
另外，在搜狗实验室文本分类语料库中将本文算法与传统IG算法进行比较，采用经典的十折交叉验证，得到F1值见图 4.
由图 4中数据可以看出，本文方法比传统IG算法的F1值高，即本文算法在本文分类的性能高于传统IG算法.
3.1. 实验分类评价指标
3.2. 实验结果
-
作为文本分类的关键技术，特征选择算法对分类性能有直接影响.本文研究了传统IG特征选择算法，针对传统IG算法的不足，引入均衡比和类内词频位置参数，提出一种新的信息增益(IG)特征选择算法，该算法解决了传统IG算法忽略词频分布对分类的弱化问题，修正传统类内词频位置参数，提高了分类精度，并将该改进IG特征选择算法用于最大熵模型对文本进行分类，实验结果表明本文方法优于传统IG特征选择算法.把本文方法用于ME分类时性能优于KNN分类算法，说明本文方法可行、有效.
DownLoad: