前文提到过,除了开方检验(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的文档数就可以了。
从以上讨论中可以看出,信息增益也是考虑了特征出现和不出现两种情况,与开方检验一样,是比较全面的,因而效果不错。但信息增益最大的问题还在于它只能考察特征对整个系统的贡献,而不能具体到某个类别上,这就使得它只适合用来做所谓“全局”的特征选择(指所有的类都使用相同的特征集合),而无法做“本地”的特征选择(每个类别有自己的特征集合,因为有的词,对这个类别很有区分度,对另一个类别则无足轻重)。
看看,导出的过程其实很简单,没有什么神秘的对不对。可有的学术论文里就喜欢把这种本来很直白的东西写得很晦涩,仿佛只有读者看不懂才是作者的真正成功。
咱们是新一代的学者,咱们没有知识不怕被别人看出来,咱们有知识也不怕教给别人。所以咱都把事情说简单点,说明白点,大家好,才是真的好。
该系列文章的来源:http://tech.ddvip.com/2009-03/1237883850112130_5.html
分享到:
相关推荐
### 文本分类入门知识点详解 #### 一、文本分类问题定义及应用范围 文本分类,作为自然语言处理(NLP)的重要组成部分,旨在通过计算机自动分析文档内容,并将其归类到预定义的类别中。这一过程涉及理解文本的语义...
《基于信息增益特征选取和覆盖的中文文本分类.pdf》和《基于最优互信息的特征选取.pdf》这两篇论文都关注特征选择。信息增益和最优互信息是衡量特征与类别间关联度的指标,用于减少冗余特征并提高模型效率。 《手机...
其中,ID3主要基于信息增益来选择特征,C4.5是对ID3的改进,采用了信息增益率来解决ID3在选择特征时偏向多值特征的问题,而CART则是一种基于基尼不纯度的决策树,它可以用于分类也可以用于回归任务。 在西电的数据...
`criterion`参数定义了评估节点分割的标准,如'gini'(基尼指数)或'entropy'(信息增益)。`max_depth`限制了树的最大深度,`min_samples_split`和`min_samples_leaf`分别控制了分裂子树的最小样本数和叶子节点的...
这可能涉及到单变量或多变量的选择方法,如卡方检验、信息增益等。 4. **建模与分类**:WEKA提供了各种机器学习算法,如决策树(C4.5, ID3)、随机森林、支持向量机、神经网络等。选择合适的算法后,可以训练模型并...
ID3(Iterative Dichotomiser 3)算法是最早用于构建决策树的算法之一,它基于信息熵和信息增益来选择最优特征进行分裂。本项目通过Python实现ID3算法并结合matplotlib库进行决策树的可视化展示,帮助理解决策树的...
这个过程包括模板的创建、匹配方法的选择(如灰度匹配、形状匹配等)和匹配结果的评估。 1D码和2D码识别则涉及到条形码和二维码的读取,这是现代工业中常见的数据交换方式。Halcon提供了强大的读码器,能适应各种...
- 使用信息增益比作为特征选择度量。 **应用场景:** - 客户分类。 - 信用评估。 - 医疗诊断系统。 ### 二、K-Means **简介:** K-Means是一种简单且高效的聚类算法,通过迭代的方式将数据集划分为k个簇。该算法...
书中解释了随机森林的工作原理,包括随机特征选择和随机样本抽取。 六、支持向量机(SVM) SVM是一种强大的分类和回归工具,利用最大间隔思想来构建决策边界。书中详细讲述了硬间隔与软间隔的概念,以及核函数的...
- **决策树构建**:介绍了一种基于信息增益或基尼指数的决策树构建方法。 - **剪枝技术**:讨论了避免过拟合问题的剪枝技术,包括预剪枝和后剪枝。 - **决策树的应用**:通过具体例子展示了决策树在实际场景中的应用...
1. **C4.5算法**:C4.5是ID3决策树算法的改进版本,通过信息增益率选择最佳分割属性,解决了ID3对属性数量多的偏好问题,并进行了剪枝以避免过拟合。适用于分类任务,尤其在处理离散和不完整数据时。优点是易于理解...
- **文语转换(Text-to-Speech)**:将文本信息转化为语音输出。 - **语音识别(Voice Recognition)**:识别语音命令或信息,并据此执行相应的操作。 - **电话呼出**:自动拨打预设的电话号码。 - **传真的存储...
### FEKO Suite 5.3 入门手册关键知识点 #### 一、矩形喇叭示例 ##### 1.1 示例概述 - **目的**:本示例旨在通过一个矩形喇叭模型,让初次接触FEKO软件的用户熟悉其基本工作流程及功能。 - **模型**:采用的是一个...
2017年最新机器学习入门与实战精品高清全套视频教程附讲义作业(anaconda2 4.3Pytyhon2.7 jupyter) 70课 课程介绍: 从基本的软件安装到必备的Python扩展讲起,然后对机器学习算法一一讲解,同时配合编程实操的实现...
课程可能涉及ID3、C4.5、CART算法,以及剪枝策略和信息增益等概念。 4. **07_SVMs.pdf** - 支持向量机(SVM) SVM是一种强大的分类和回归技术,通过构造最大间隔超平面来实现。内容可能涵盖硬间隔和软间隔、核函数...
### Multisim 10.0 快速入门指南 #### 一、Multisim 10.0 系统简介 Multisim是由National Instruments(NI)公司开发的一款强大的电子电路仿真软件,广泛应用于教育、研究以及工业设计等领域。Multisim 10.0作为该...
这两种方法都依赖于查询和文档中词汇的统计特征,无需复杂的模型训练,但可能受限于固定的公式和参数。 然而,随着机器学习技术的发展,学习排序(Learning to Rank)逐渐成为提升排序性能的有效手段。学习排序是一...
2.4.4可闻文本(Audiotex) 26 2.4.5按呼叫次数付费(pay-per-call) 26 2.4.6自动订购系统(Automated order entry) 26 2.4.7呼叫中心(Call center) 27 2.5通信基础术语 27 2.5.1电话线 27 2.5.2拨号音 27...
功率增益圆是评估和选择放大器设计的一种工具,它表示在不同负载条件下的增益性能。这有助于在设计中平衡增益和稳定性。 7. 有源器件的偏置网络(6.Biasnetworksofactivedevices) 放大器需要合适的直流偏置条件...
### FM355PID模块使用入门相关知识点 #### 一、概述 FM355PID模块是西门子公司推出的一款高性能闭环控制模块,主要用于压力、流量、温度等参数的闭环控制。该模块的设计旨在帮助工程师们更加高效地完成控制系统的...