摘自:
http://www.blogjava.net/zhenandaci/archive/2009/03/24/261701.html
前文提到过,除了开方检验(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被固定时的条件熵,注意与上式在意义上的区别。从刚才计算均值的讨论可以看出来,第二个式子与第一个式子的关系就是:
具体到我们文本分类系统中的特征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)特征选择方法没有很好组合正相关特征和负相关特征的问题,引入比例因子来平衡特征出现和不出现时的信息量,降低在不平衡语料集上负相关特征的比例,提高分类效果。通过实验证明了改进的信息...
针对肿瘤基因数据因维度高和冗余基因较多而导致分类精度低的问题,提出一种基于PCA和信息增益的肿瘤特征基因选择方法.该方法首先使用PCA算法剔除冗余基因,获得预选特征基因子集;然后利用信息增益算法对预选特征基因子...
现有的特征选择函数主要有文档频率(DF),信息增益(IG),互信息(MI)等。基于特征的基本约束条件以及高性能特征选择方法的设计步骤,提出了一种改进的特征选择方法SIG。该特征选择方法在保证分类效果的同时,...
针对上述问题,提出了信息增益(IG)与主成分分析(PCA)相结合的特征选择方法。通过实验比较分析了不同特征选择方法与特征维度对分类性能的影响,证明了该特征选择方法在基于神经网络的中文文本分类中的优越性,并得出...
对四种特征选择方法: 互信息、信息增益、x 2 统计和期望交叉熵作了简要的介绍, 并 且结合 K NN分类算法 , 使用查全率、查准率、宏平均和微平均对四种特征选择方法分别进行评 估 , 提出并讨论了互信息修正的两种方法...
介绍文本分类中特征提取方法的比较与分析,信息增益、卡方等方法
考察了文档频率DF、信息增益IG、互信息MI、V2 分布CHI 四种不同的特征选取方法。采用支持向量机(SVM) 和KNN 两种不同的分类器以考察不同抽取方法的有效性。实验结果表明, 在英文文本分类中表现良好的特征抽取方法( ...
比较了常用的CHI选择、互信息(MI)、信息增益(IG)和SVM 特征选择算法在垃圾邮件过滤中的效果,针对这些方法只排序而未消除特征间冗余的缺点,提出了利用特征词间条件概率和分类区分度消除冗余的混合邮件特征选择...
是关于文本特征提取的新方法,很不错,在信息增益\积比率的基础上,做了改善
在传统的k-gram方法提取的特征的基础上,为了选出更加有效的特征,提出了一种新的特征选择方法——信息增益。由于针对信息增益方法中未对特征碎片的词频给予足够重视,从而导致特征分布不均的问题,将特征频率应用于...
文档频率(DF)、信息增益(IG)和互信息(MI)等特征选择方法在文本分类中广泛应用。已有的实验结果表明,IG是最有效的特征选择算法之一,该方法基于申农提出的信息论。本文基于粗糙集理论,提出了一种新的特征选择方法(KG...
在研究文本分类特征选择方法的基础上,分析了信息增益方法的不足,将频度、集中度、分散度应用到信息增益方法上,提出了一种基于信息增益的特征优化选择方法。实验表明,该方法在分类效果与性能上都优于传统方法。
基于信息增益与CHI卡方统计的情感文本特征选择.pdf
实现的功能 一、语料库处理 词频率(TF),文档频率(DF)的统计。...信息增益IG方法:衡量特征能够为分类系统带来多少信息,跟具体类别无关。 三、文本分类。 分类快速。 能对单个文件、目录、文件列表进行分类。
为了获得更好的文本分类准确率和更快的执行效率, 研究了多种Web文本的特征提取方法, 通过对互信息(MI)、文档频率(DF)、信息增益(IG)和χ2统计(CHI)算法的研究, 利用其各自的优势互补, 提出一种基于主成分分析(PCA)...
电信设备-一种基于信息增益率的属性加权方法及文本分类方法.zip
matlab版的信息增益算法实现
提出了结合情感词典的改进信息增益特征选择方法。首先,针对现有的信息增益特征选择存在注重特征词的文档频率而忽视语料均衡等问题,提出了改进方法。其次,考虑情感词对文本分类的影响,提出了基于情感词典的特征...
针对网络入侵检测所处理数据特征维数高、入侵检测系统负荷大、检测速度慢等问题,提出了一种将自适应遗传算法与信息增益相结合的特征选择方法,并采用基于支持向量机的分类器作为自适应遗传算法中适应度函数的计算与...
通过分析特征词与类别间的相关性, 在原有卡方特征选择和信息增益特征选择的基础上提出了两个参数, 使得选出...通过实验对比传统的卡方特征选择、信息增益和CCIF方法, CCIF方法使得算法的微平均查准率得到了明显的提高。