1、第7章 信息论方法,7.1 信息论原理7.2 决策树方法,7.1 信息论原理 信息论是C.E.Shannon为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。1.信道模型一个传递信息的系统是由发送端（信源）和接收端（信宿）以及连接两者的通道（信道）三者组成。,在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。这种情形就称为信宿对于信源状态具有不确定性。而且这种不确定性是存在于通信之前的。因而又叫做先验不确定性，表示成 信息熵 H（U）,在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少
2、。如果干扰很小，不会对传递的信息产生任何可察觉的影响，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。,一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。先验不确定性不能全部被消除，只能部分地消除。通信结束之后，信宿仍然具有一定程度的不确定性。这就是后验不确定性，用条件熵表示H（U/V）。后验不确定性总要小于先验不确定性:H（U/V）H（U）,如果后验不确定性的大小正好等于先验不确定性的大小，这就表示信宿根本没有收到信息。如果后验不确定性等于零，这就表示信宿收到了全部信息。可见，信息是用来消除（随机）不确定性的度量。信息量用互信息来表示
3、，即：I（U，V）H（U）H（U/V）,互信息的计算,1定义（1）设S为训练集，有n个特征（属性），表示为（A1，A2，.，An）。S表示例子总数。（2）S中有U1，U2两类。Ui表示Ui类例子数。（3）特征Ak处有m个取值，分别为（V1，V2，.，Vm）。2Ui类出现概率为:P（Ui）=Ui/S,3Ui类中在特征Ak处取值Vj的例子集合Vij的条件概率为:P（VjUi）=Vij/Ui4在特征Ak处，取Vj值的例子集合的概率为:P（Vj）=Vj/S,5在特征Ak处取Vj值的例子，属于Ui类的例子集合Uij的条件概率为:P（UiVj）=Uij/Vj,6信息熵（1）消息传递系统由消息的发送端（信源
4、）和接收端（信宿）以及连接两者的通道（信道）三者组成。（2）消息（符号）Ui（i=1，2，.，q）的发生概率P（Ui）组成信源数学模型（样本空间或概率空间）,（7.2）,（3）自信息:消息Ui发出后所含有的信息量。它反映了消息Ui发出前的不确定性（随机性）。定义为：以2为底，所得的信息量单位为bit。（4）信息熵:自信息的数学期望。即信源输出后，每个消息所提供的信息量，也反映了信源输出前的平均不确定性。定义为:,例如:两个信源，其概率空间分别为:则信息熵分别为:H（X）=-0.99 log0.99-0.01 log0.01=0.08 bitH（Y）=-0.5 log0.5-0.5 log0.5
5、=1bit 可见 H（Y）H（X）故信源Y比信源X的平均不确定性要大。,信息熵H（U）是信源输出前的平均不确定性，也称先验熵。H（U）的性质:（1）H（U）=0时，说明只存在着唯一的可能性，不存在不确定性。（2）如果n种可能的发生都有相同的概率，即所有的Ui有P（Ui）=1/n，H（U）达到最大值log n，系统的不确定性最大。P（Ui）互相接近，H（U）就大。P（Ui）相差大，则H（U）就小。,7互信息(1)后验熵当信宿没有接收到输出符号V时，已知输入符号U的概率分布为P（U），而当接收到输出符号V=Vj 后，输入符号的概率分布发生了变化,变成后验概率分布P（U|Vj）。其后验熵为：后验熵是
6、接收到单个输出符号Vj后关于信息源U的不确定性(信息度量)。,7互信息(2)条件熵后验熵对输出符合V(全部符号)求平均值(数学期望)，得到条件熵,这个条件熵称为信道疑义度。它表示在输出端收到全部输出符号V后，对于输入端的符号集U尚存在的不确定性（存在疑义）。从上面分析可知：条件熵小于无条件熵，即H（U|V）H（U）。说明接收到符号集V的所有符号后，关于输入符号U的平均不确定性减少了。即总能消除一些关于输入端X的不确定性，从而获得了一些信息。,（3）互信息定义:I（U,V）=H（U）H（U|V）I（U,V）称为U和V之间的互信息。它代表接收到符号集V后获得的关于U的信息量。可见，熵（H（U）、H
7、（U|V）只是平均不确定性的描述。熵差（H（U）H（U|V）是不确定性的消除，即互信息才是接收端所获得的信息量。,对输入端U只有U1，U2两类，互信息的计算公式为:,7.2 决策树方法,7.2.1决策树概念决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。,决策树是一种知识表示形式，它是对所有样本数据的高度概括。决策树能准确地识别所有样本的类别，也能有效地识别新样本的类别。,7.2.2 ID3方法基本思想,最有影响的决策树方法首推J.R.Quin
8、lan的ID3。首先找出最有判别力的特征，把数据分成多个子集，每个子集又选择最有判别力的特征进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。J.R.Quinlan的工作主要是引进了信息论中的互信息，他将其称为信息增益（information gain），作为特征判别能力的度量，并且将建树的方法嵌在一个迭代的外壳之中。,一、ID3基本思想 例如：关于气候的类型，特征为:天气 取值为：晴，多云，雨 气温 取值为：冷，适中，热 湿度 取值为：高，正常 风 取值为：有风，无风,每个实体在世界中属于不同的类别，为简单起见，假定仅有两个类别，分别为P，N。在这种两个类别的归纳任务
9、中，P类和N类的实体分别称为概念的正例和反例。将一些已知的正例和反例放在一起便得到训练集。表3.1给出一个训练集。由ID3算法得出一棵正确分类训练集中每个实体的决策树，见下图。,ID3决策树,决策树叶子为类别名，即P 或者N。其它结点由实体的特征组成，每个特征的不同取值对应一分枝。若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。,现用来判一个具体例子，某天早晨气候描述为:天气：多云 气温：冷 湿度：正常 风：无风 它属于哪类气候呢?从图中可判别该实体的类别为P类。,ID3就是要从表的训练集构造出
10、这样的决策树。实际上，能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。,二、ID3算法（一）主算法 从训练集中随机选择一个既含正例又含反例的子集（称为窗口）；用“建树算法”对当前窗口形成一棵决策树；对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；若存在错判的例子，把它们插入窗口，转2，否则结束。,主算法流程用下图表示。其中PE、NE分别表示正例集和反例集，它们共同组成训练集。PE，PE和NE，NE分别表示正例集和反例集的子集。主算法中每迭代循环一次，生成的决策树将会不相同。,ID3主算法流程,（二）建树算法 对当前例子集合，计算各特征的互
11、信息；选择互信息最大的特征Ak；把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；对既含正例又含反例的子集，递归调用建树算法；若子集仅含正例或反例，对应分枝标上P或N，返回调用处。,实例计算,对于气候分类问题进行具体计算有：信息熵的计算对9个正例和5个反例有：P（u1）=9/14 P（u2）=5/14H（U）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit,条件熵计算条件熵：A1=天气取值 v1=晴，v2=多云，v3=雨在A1处取值晴的例子5个，取值多云的例子4 个，取值雨的例子5 个，故：P（v1）=5/14 P（v2）=4/14 P（v3）=5
12、/14取值为晴的5 个例子中有2 个正例、3个反例，故：P（u1/v1）=2/5，P（u2/v1）=3/5同理有：P（u1/v2）=4/4，P（u2/v2）=0 P（u1/v3）=2/5，P（u2/v3）=3/5H(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/14)(4/4)log(4/4)+0)+(5/14)(2/5)log(5/2)+(3/5)log(5/3)=0.694bit,互信息计算 对 A1=天气 处有：I（天气）=H（U）-H（U|V）=0.94-0.694=0.246 bit 类似可得：I（气温）=0.029 bit I（湿度）=0.15
13、1 bit I（风）=0.048 bit 建决策树的树根和分枝 ID3算法将选择互信息最大的特征天气作为树根，在14个例子中对天气的3个取值进行分枝，3 个分枝对应3 个子集，分别是:F1=1，2，8，9，11，F2=3，7，12，13，F3=4，5，6，10，14 其中F2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用建树算法。,天 气,1,2,8,9,11,4,5,6,10,14,晴,雨,多云,P,递归建树 分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征）求互信息.（1）F1中的天气全取晴值，则H（U）=H（U|V），有I（U
14、|V）=0，在余下三个特征中求出湿度互信息最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标记N。取值正常的例子全为P类，该分枝标记P。（2）在F3中，对四个特征求互信息，得到风特征互信息最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。这样就得到图8.5的决策树,对ID3的讨论,优点 ID3在选择重要特征时利用了互信息的概念，算法的基础理论清晰，使得算法较简单，是一个很有实用价值的示例学习算法。该算法的计算时间是例子个数、特征个数、结点个数之积的线性函数。用4761个关于苯的质谱例子作了试验。其中正例2361个，反
15、例2400个，每个例子由500个特征描述，每个特征取值数目为6，得到一棵1514个结点的决策树。对正、反例各100个测试例作了测试，正例判对82个，反例判对80个，总预测正确率81%，效果是令人满意的。,缺点（1）互信息的计算依赖于特征取值的数目较多的特征，这样不太合理。,（2）用互信息作为特征选择量存在一个假设，即训练例子集中的正，反例的比例应与实际问题领域里正、反例比例相同。一般情况不能保证相同，这样计算训练集的互信息就有偏差。（3）ID3在建树时，每个节点仅含一个特征，是一种单变元的算法，特征间的相关性强调不够。虽然它将多个特征用一棵树连在一起，但联系还是松散的。,（4）ID3对噪声较为
16、敏感。关于什么是噪声，Quinlan的定义是训练例子中的错误就是噪声。它包含两方面，一是特征值取错，二是类别给错。（5）当训练集增加时，ID3的决策树会随之变化。在建树过程中，各特征的互信息会随例子的增加而改变，从而使决策树也变化。这对渐近学习（即训练例子不断增加）是不方便的。,C4.5算法,ID3算法在数据挖掘中占有非常重要的地位。但是，在应用中，ID3算法不能处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。C4.5是在ID3基础上发展起来的决策树生成算法，由J.R.Quinlan在1993年提出。,C4.5克服了ID3在应用中存在的不足，主要体现在以下几个方面：（1）用信息增益
17、率来选择属性，它克服了用信息增益选择属性时偏向选择取值多的属性的不足；（2）在树构造过程中或者构造完成之后，进行剪枝；（3）能够完成对连续属性的离散化处理；（4）能够对于不完整数据的处理，例如未知的属性 值；（5）C4.5采用的知识表示形式为决策树，并最终可以 形成产生式规则。,C4.5克服了ID3在应用中存在的不足，主要体现在以下几个方面：（1）用信息增益率来选择属性，它克服了用信息增益选择属性时偏向选择取值多的属性的不足；（2）在树构造过程中或者构造完成之后，进行剪枝；（3）能够完成对连续属性的离散化处理；（4）能够对于不完整数据的处理；（5）可以形成规则。,C4.5构造决策树的算法,1、
18、用信息增益率来选择属性一般来说率就是用来取平衡用的，就像方差。比如有两个跑步的人，一个起点是10m/s的人、其10s后为20m/s；另一个人起速是1m/s、其1s后为2m/s。如果仅仅算差值那么两个差距就很大了，如果使用速度增加率(加速度，即都是为1m/s2)来衡量，2个人就是一样的加速度。因此，C4.5克服了ID3用信息增益选择属性时偏向选择取值多的属性的不足。,2、连续属性的处理C4.5是如何处理连续属性的呢？实际上它先把连续属性转换为离散属性再进行处理。虽然本质上属性的取值是连续的，但对于有限的采样数据它是离散的，如果有N条样本，那么我们有N-1种离散化的方法：vj的分到右子树。计算这N
19、-1种情况下最大的信息增益率。,2、连续属性的处理在C4.5中，对连续属性的处理如下：1.对属性的取值进行排序2.两个属性取值之间的中点作为可能的分裂点，将数据集分成两部分，计算每个可能的分裂点的信息增益3.对每个分裂点的信息增益(InforGain)进行修正：减去log2(N-1)/|D|4.选择修正后信息增益(InforGain)最大的，分裂点作为该属性的最佳分裂点5.计算最佳分裂点的信息增益率（Gain Ratio）作为属性的Gain Ratio6.选择Gain Ratio最大的属性作为分裂属性,2、连续属性的处理在离散属性上只需要计算1次信息增益率，而在连续属性上却需要计算N-1次，计
20、算量是相当大的。有办法可以减少计算量。对于连续属性先进行排序，只有在决策属性发生改变的地方才需要切开。,3、决策树剪枝 由于噪声和随机因素的影响，决策树一般会很复杂。因此需要进行剪枝操作。(1)什么时候剪枝？有两种剪枝策略：（1）在树生成过程中判断是否还继续扩展决策树。若停止扩展，则相当于剪去该结点以下的分枝。（2）对于生成好的树剪去某些结点和分枝。C4.5采用第二种方法。剪枝之后的决策树的叶结点不再只包含一类实例。结点有一个类分布描述，即该叶结点属于某类的概率。,(2)基于误差的剪枝 决策树的剪枝通常是用叶结点替代一个或者多个子树，然后选择出现概率最高的类作为该结点的类别。在C4.5中，还允
21、许用其中的树枝来替代子树。如果使用叶结点或者树枝代替原来的子树之后，误差率若能够下降，则使用此叶结点或者树枝代替原来的子树。,4、从决策树抽取规则在C4.5中，从决策树抽取规则需要两个步骤：获得简单规则、精简规则属性。对于生成好的决策树，我们可以直接从获得规则。从根到叶的每一条路经都可以是一条规则。例如，从下面的决策树中我们可以得到规则：,决策树：,规则：IF F=1,G=0,J=1,K=1 THEN class1,C4.5算法有如下优点：产生的分类规则易于理解，准确率较高。其缺点是：在构造树的过程中，需要对数据集进行多次的顺序扫描和排序，因而导致算法的低效。此外，C4.5只适合于能够驻留于内存的数据集，当训练集大得无法在内存容纳时程序无法运行。,作业,全纹静、王洪佳、刘剑 结合例子的C4.5连续属性的离散化王瑞新、陈光、王斐 结合例子的C4.5剪枝张彬、周南、郭俊平 结合例子的IBLE方法李丹、刘晓帅、高立明 结合例子的IBLE方法高军、苑聪、佀称称 结合例子的IBLE方法,
