除了开方检验(CHI)以外,信息增益(IG,Information Gain)也是很有效的特征选择方法。但凡是特征选择,总是在将特征的重要程度量化之后再进行选择,而如何量化特征的重要性,就成了各种方法间最大的不同。开方检验中使用特征与类别间的关联性来进行这个量化,关联性越强,特征得分越高,该特征越应该被保留。
在信息增益中,重要性的衡量标准就是看特征能够为分类系统带来多少信息,带来的信息越多,该特征越重要。
因此先回忆一下信息论中有关信息量(就是“熵”)的定义。说有这么一个变量X,它可能的取值有n多种,分别是x1,x2,……,xn,每一种取到的概率分别是P1,P2,……,Pn,那么X的熵就定义为:
意思就是一个变量可能的变化越多(反而跟变量具体的取值没有任何关系,只和值的种类多少以及发生概率有关),它携带的信息量就越大(因此我一直觉得我们的政策法规信息量非常大,因为它变化很多,基本朝令夕改,笑)。
对分类系统来说,类别C是变量,它可能的取值是C1,C2,……,Cn,而每一个类别出现的概率是P(C1),P(C2),……,P(Cn),因此n就是类别的总数。此时分类系统的熵就可以表示为:
有同学说不好理解呀,这样想就好了,文本分类系统的作用就是输出一个表示文本属于哪个类别的值,而这个值可能是C1,C2,……,Cn,因此这个值所携带的信息量就是上式中的这么多。
信息增益是针对一个一个的特征而言的,就是看一个特征t,系统有它和没它的时候信息量各是多少,两者的差值就是这个特征给系统带来的信息量,即增益。系统含有特征t的时候信息量很好计算,就是刚才的式子,它表示的是包含所有特征时系统的信息量。
问题是当系统不包含t时,信息量如何计算?我们换个角度想问题,把系统要做的事情想象成这样:说教室里有很多座位,学生们每次上课进来的时候可以随便坐,因而变化是很大的(无数种可能的座次情况);但是现在有一个座位,看黑板很清楚,听老师讲也很清楚,于是校长的小舅子的姐姐的女儿托关系(真辗转啊),把这个座位定下来了,每次只能给她坐,别人不行,此时情况怎样?对于座次的可能情况来说,我们很容易看出以下两种情况是等价的:(1)教室里没有这个座位;(2)教室里虽然有这个座位,但其他人不能坐(因为反正它也不能参与到变化中来,它是不变的)。
对应到我们的系统中,就是下面的等价:(1)系统不包含特征t;(2)系统虽然包含特征t,但是t已经固定了,不能变化。
我们计算分类系统不包含特征t的时候,就使用情况(2)来代替,就是计算当一个特征t不能变化时,系统的信息量是多少。这个信息量其实也有专门的名称,就叫做“条件熵”,条件嘛,自然就是指“t已经固定“这个条件。
但是问题接踵而至,例如一个特征X,它可能的取值有n多种(x1,x2,……,xn),当计算条件熵而需要把它固定的时候,要把它固定在哪一个值上呢?答案是每一种可能都要固定一下,计算n个值,然后取均值才是条件熵。而取均值也不是简单的加一加然后除以n,而是要用每个值出现的概率来算平均(简单理解,就是一个值出现的可能性比较大,固定在它上面时算出来的信息量占的比重就要多一些)。
因此有这样两个条件熵的表达式:
这是指特征X被固定为值xi时的条件熵,
这是指特征X被固定时的条件熵,注意与上式在意义上的区别。从刚才计算均值的讨论可以看出来,第二个式子与第一个式子的关系就是:
[img]
http://d.hiphotos.baidu.com/space/pic/item/2934349b033b5bb5fa2f366436d3d539b700bcab.jpg[/img]
具体到我们文本分类系统中的特征t,t有几个可能的值呢?注意t是指一个固定的特征,比如他就是指关键词“经济”或者“体育”,当我们说特征“经济”可能的取值时,实际上只有两个,“经济”要么出现,要么不出现。一般的,t的取值只有t(代表t出现)和(代表t不出现),注意系统包含t但t 不出现与系统根本不包含t可是两回事。
因此固定t时系统的条件熵就有了,为了区别t出现时的符号与特征t本身的符号,我们用T代表特征,而用t代表T出现,那么:
与刚才的式子对照一下,含义很清楚对吧,P(t)就是T出现的概率,就是T不出现的概率。这个式子可以进一步展开,其中的
另一半就可以展开为:
因此特征T给系统带来的信息增益就可以写成系统原本的熵与固定特征T后的条件熵之差:
公式中的东西看上去很多,其实也都很好计算。比如P(Ci),表示类别Ci出现的概率,其实只要用1除以类别总数就得到了(这是说你平等的看待每个类别而忽略它们的大小时这样算,如果考虑了大小就要把大小的影响加进去)。再比如P(t),就是特征T出现的概率,只要用出现过T的文档数除以总文档数就可以了,再比如P(Ci|t)表示出现T的时候,类别Ci出现的概率,只要用出现了T并且属于类别Ci的文档数除以出现了T的文档数就可以了。
从以上讨论中可以看出,信息增益也是考虑了特征出现和不出现两种情况,与开方检验一样,是比较全面的,因而效果不错。但信息增益最大的问题还在于它只能考察特征对整个系统的贡献,而不能具体到某个类别上,这就使得它只适合用来做所谓“全局”的特征选择(指所有的类都使用相同的特征集合),而无法做“本地”的特征选择(每个类别有自己的特征集合,因为有的词,对这个类别很有区分度,对另一个类别则无足轻重)。
分享到:
相关推荐
分析了传统信息增益(IG)特征选择方法忽略了特征项在类间、类内分布信息的缺点,引入类内分散度、类间集中度等因素,区分与类强相关的特征;针对传统信息增益(IG)特征选择方法没有很好组合正相关特征和负相关特征...
针对肿瘤基因数据因维度高和冗余基因较多而导致分类精度低的问题,提出一种基于PCA和信息增益的肿瘤特征基因选择方法.该方法首先使用PCA算法剔除冗余基因,获得预选特征基因子集;然后利用信息增益算法对预选特征基因子...
在传统的k-gram方法提取的特征的基础上,为了选出更加有效的特征,提出了一种新的特征选择方法——信息增益。由于针对信息增益方法中未对特征碎片的词频给予足够重视,从而导致特征分布不均的问题,将特征频率应用于...
比较了常用的CHI选择、互信息(MI)、信息增益(IG)和SVM 特征选择算法在垃圾邮件过滤中的效果,针对这些方法只排序而未消除特征间冗余的缺点,提出了利用特征词间条件概率和分类区分度消除冗余的混合邮件特征选择...
matlab版的信息增益算法实现
针对网络入侵检测所处理数据特征维数高、入侵检测系统负荷大、检测速度慢等问题,提出了一种将自适应遗传算法与信息增益相结合的特征选择方法,并采用基于支持向量机的分类器作为自适应遗传算法中适应度函数的计算与...
主要为大家详细介绍了python实现求特征选择的信息增益,可以同时适用于二值离散型和连续型的属性,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
在研究文本分类特征选择方法的基础上,分析了信息增益方法的不足,将频度、集中度、分散度应用到信息增益方法上,提出了一种基于信息增益的特征优化选择方法。实验表明,该方法在分类效果与性能上都优于传统方法。
通过分析特征词与类别间的相关性, 在原有卡方特征选择和信息增益特征选择的基础上提出了两个参数, 使得选出...通过实验对比传统的卡方特征选择、信息增益和CCIF方法, CCIF方法使得算法的微平均查准率得到了明显的提高。
电信设备-基于对称不确定性和信息交互增益的特征选择方法.zip
基于信息熵计算属性的信息增益,最终得到约简后的属性集,实现特征选择
三种常用的特征选择算法 卡方特征选择,互信息特征选择,信息增益特征选择(CHI,MI,IG) (Three kinds of commonly used feature selection algorithm, CHI, MI, IG)
现有的特征选择函数主要有文档频率(DF),信息增益(IG),互信息(MI)等。基于特征的基本约束条件以及高性能特征选择方法的设计步骤,提出了一种改进的特征选择方法SIG。该特征选择方法在保证分类效果的同时,...
ID3选择具有最高信息熵增益的属性作为分裂属性
该方法在融合输入图像的细节信息时,同时考虑了输入图像的多个分解层的小波系数。实验结果表明,无论是依据均方根误差、信噪比、灰度平均误差等客观评价标准,还是视觉的主观评价,所提出的融合方法都能取得较好的...
在机器学习中,信息增益是一种用于特征选择的常用技术。它可以帮助我们确定哪些特征对于分类任务是最有用的。在 Java 中实现信息增益的代码需要几个步骤。首先,我们需要导入必要的包和类。然后,我们需要定义数据集...
本文实例讲述了Python决策树之基于信息增益的特征选择。分享给大家供大家参考,具体如下: 基于信息增益的特征选取是一种广泛使用在决策树(decision tree)分类算法中用到的特征选取。该特征选择的方法是通过计算每个...
TPA3116D2 增益调节方法
信息增益Java代码,具体的代码实现以及数据库的链接