《信息论方法.ppt》由会员分享，可在线阅读，更多相关《信息论方法.ppt（55页珍藏版）》请在三一办公上搜索。
1、第7章 信息论方法（一）,7.1 信息论原理7.2 决策树方法,7.1 信息论原理 信息论是C.E.Shannon为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。1.信道模型一个传递信息的系统是由发送端（信源）和接收端（信宿）以及连接两者的通道（信道）三者组成。,信道,u1,u2.ur,信源U,v1,v2.vr,P(V|U),信宿V,在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。这种情形就称为信宿对于信源状态具有不确定性。而且这种不确定性是存在于通信之前的。因而又叫做先验不确定性，表示成 信息熵 H（U）,在
2、进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。如果干扰很小，不会对传递的信息产生任何可察觉的影响，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。,在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。先验不确定性不能全部被消除，只能部分地消除。通信结束之后，信宿仍然具有一定程度的不确定性。这就是后验不确定性，用条件熵表示H（U/V）。后验不确定性总要小于先验不确定性:H（U/V）H（U）,如果后验不确定性的大小正好等于先验不确定性的大小，这就表示信宿根本没有收到信息。如果后验不确定性的大小等于零，这就表
3、示信宿收到了全部信息。可见，信息是用来消除（随机）不确定性的度量。信息量用互信息来表示，即：I（U，V）H（U）H（U/V）,6信息熵（1）消息传递系统由消息的发送端（信源）和接收端（信宿）以及连接两者的通道（信道）三者组成。（2）消息（符号）Ui（i=1，2，.，q）的发生概率P（Ui）组成信源数学模型（样本空间或概率空间）,（3.5）,（3）自信息:消息Ui发生后所含有的信息量。它反映了消息Ui发生前的不确定性（随机性）。定义为：以2为底，所得的信息量单位为bit。以e为底，所得的信息量单位为nat.（4）信息熵:自信息的数学期望。即信源输出后，每个消息所提供的信息量，也反映了信源输出前的
4、平均不确定性。定义为:,（3.6）,（3.7）,例如:两个信源，其概率空间分别为:则信息熵分别为:H（X）=-0.99 log0.99-0.01 log0.01=0.08 bitH（Y）=-0.5 log0.5-0.5 log0.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（
5、Ui）相差大，则H（U）就小。,(1)后验熵和条件熵当没有接收到输出符号V时，已知输入符号U的概率分布为P（U），而当接收到输出符号V=Vj 后，输入符号的概率分布发生了变化，变成后验概率分布P（U|Vj）。其后验熵为：,7互信息(增益),当没有接收到输出符号V时，已知输入符号U的概率分布为P（U），而当接收到输出符号V=Vj 后，输入符号的概率分布发生了变化，变成后验概率分布P（U|Vj）。那么接收到输出符号V=Vj后，关于U的平均不确定性为：这是接收到输出符号Vj后关于U的条件熵,7互信息（增益）,这个条件熵称为信道疑义度。它表示在输出端收到全部输出符号V后，对于输入端的符号集U尚存在的不
6、确定性（存在疑义）。从上面分析可知：条件熵小于无条件熵，即H（U|V）H（U）。说明接收到符号集V的所有符号后，关于输入符号U的平均不确定性减少了。即总能消除一些关于输入端X的不确定性，从而获得了一些信息。,（2）平均互信息（信息增益）定义:I（U,V）=H（U）H（U|V）（3.10）I（U,V）称为U和V之间的平均互信息（信息增益），它代表接收到符号集V后获得的关于U的信息量。可见，熵（H（U）、H（U|V）只是平均不确定性的描述。熵差（H（U）H（U|V）是不确定性的消除，即互信息（信息增益）才是接收端所获得的信息量。,（2）平均互信息（信息增益）对输入端U只有U1，U2两类，互信息（信
7、息增益）的计算公式为:,7.2 决策树方法,7.2.1决策树概念决策树是对数据进行分类，以此达到预测的目的。决策树方法先根据训练集数据形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。,7.2 决策树方法,7.2.1决策树概念决策树由决策结点、分支和叶子组成。决策树中最上面的结点为根结点，每个分支是一个新的决策结点，或者是树的叶子。每个决策结点代表一个问题或决策，通常对应于待分类对象的属性。每一个叶子结点代表一种可能的分类结果。,7.2 决策树方法,7.2.1决策树概念决策树的根结点是所有样本中
8、信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。,决策树是一种知识表示形式，它是对所有样本数据的高度概括。决策树能准确地识别所有样本的类别，也能有效地识别新样本的类别。,7.2.2 ID3方法基本思想,当前国际上最有影响的CLS(Concept Learning System)是ID3（Interative Discremiser versions3）.ID3算法是由Quinlan首先提出的，该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。,7.2.2 ID3方法基本思想,CLS原理：首先找出最
9、有判别力的特征，把数据分成多个子集，每个子集又选择最有判别力的特征进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。如：有关气候类型的研究，特征（属性）天气（晴、雨、多云），气温（冷、热、适中），风（有风、无风）等,7.2.2 ID3方法基本思想,CLS原理：怎么来确定哪个是有判断力的属性呢？J.R.Quinlan的工作主要是引进了信息论中的互信息，他将其称为信息增益（information gain），作为特征判别能力的度量。,例如：关于气候的类型，特征为:天气 取值为：晴，多云，雨 气温 取值为：冷，适中，热 湿度 取值为：高，正常 风 取值为：有风，无风,一、ID
10、3基本思想,为简单起见，假定仅有两个类别，分别为P，N。在这种两个类别的归纳任务中，P类和N类的实体分别称为概念的正例和反例。将一些已知的正例和反例放在一起便得到训练集。,ID3决策树,对上表给出的训练集，由ID3算法得出一棵正确分类训练集中每个实体的决策树,决策树叶子为类别名，即P 或者N。其它结点由实体的特征组成，每个特征的不同取值对应一分枝。若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。,现用图来判一个具体例子，某天早晨气候描述为:天气：多云 气温：冷 湿度：正常 风：无风 它属于哪类气
11、候呢?从图中可判别该实体的类别为P类。,ID3就是要从表的训练集来构造上图这样的决策树。实际上，能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。,（一）主算法 从训练集中随机选择一个既含正例又含反例的子集（称为窗口）；用“建树算法”对当前窗口形成一棵决策树；对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；若存在错判的例子，把它们插入窗口，转2，否则结束。,二、ID3算法,ID3主算法流程,PE、NE分别表示正例集和反例集，它们共同组成训练集,PE，PE和NE，NE分别表示正例集和反例集的子集。,主算法流程用下图表示,对当前例子集合，计算各
12、特征的互信息（信息增益）；选择互信息（信息增益）最大的特征Ak；把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；对既含正例又含反例的子集，递归调用建树算法；若子集仅含正例或反例，对应分枝标上P或N，返回调用处。,（二）建树算法,实例计算,对于气候分类问题进行具体计算（找出根节点）信息熵的计算信息熵：类别出现概率：|S|表示例子集S的总数（14），|ui|表示类别ui的例子数。u1代表正例P共9个和u2代表反例N共5个，有：P（u1）=9/14 P（u2）=5/14H(U)=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit,条件熵计算条件熵：属性A1
13、取值vj时，类别ui的条件概率：A1=天气 取值 v1=晴，v2=多云，v3=雨在A1处取值晴的例子5个，取值多云的例子4 个，取值雨的例子5 个，故：P（v1）=5/14 P（v2）=4/14 P（v3）=5/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)
14、log(5/3)=0.694bit,互信息（信息增益）计算 对 A1=天气 处有：I（天气）=H（U）-H（U|V）=0.94-0.694=0.246 bit 类似可得：I（气温）=0.94-0.911=0.029 bit I（湿度）=0.94-0.788=0.151 bit I（风）=0.94-0.892=0.048 bit,条件熵计算A2=气温 取值 v1=热，v2=适中，v3=冷在A2处取值热的例子4个，取值适中的例子6 个，取值冷的例子4 个，故：P（v1）=4/14 P（v2）=6/14 P（v3）=4/14取值为热的4个例子中有2个正例、2个反例，故：P（u1/v1）=2/4，P（
15、u2/v1）=2/4同理有：P（u1/v2）=4/6，P（u2/v2）=2/6 P（u1/v3）=3/4，P（u2/v3）=1/4H(U/V)=(4/14)(2/4)log(4/2)+(2/4)log(4/2)+(6/14)(2/3)log(3/2)+(1/3)log(3/1)+(4/14)(3/4)log(4/3)+(1/4)log(4/1)=2/7+3/7(2/3)log3-2/3log2+(1/3)log3)+2/7(3/4)log4-(3/4)log3+1/2)=2/7+2/7log3-2/7+4/7+3/14log3=4/7+3/14log3=0.911bit,条件熵计算A3=湿度
16、取值 v1=高，v2=正常在湿度A3处取值高的例子7个，取值正常的例子7个，故：P（v1）=7/14=1/2 P（v2）=7/14=1/2取值为高的7个例子中有3个正例、4个反例，故：P（u1/v1）=3/7，P（u2/v1）=4/7同理有：P（u1/v2）=6/7，P（u2/v2）=1/7H(U/V)=(1/2)(3/7)log(7/3)+(4/7)log(7/4)+(1/2)(6/7)log(7/6)+(1/7)log(7/1)=1/2(3/7log7-3/7log3+4/7log7-4/7log4+6/7log7-6/7log6+1/7log7-0)=1/2(2log7-9/7log3-
17、2log2)=1/2(5.614-2.038-2)=0.7881bit,条件熵计算A4=风 取值 v1=有风，v2=无风在风A4处取值有风的例子6个，取值无风的例子8个，故：P（v1）=6/14=3/7 P（v2）=8/14=4/7取值为有风的6个例子中有3个正例、3个反例，故：P（u1/v1）=3/6=1/2，P（u2/v1）=3/6=1/2同理有：P（u1/v2）=6/8=3/4，P（u2/v2）=2/8=1/4H(U/V)=(3/7)(1/2)log2+(1/2)log2)+(4/7)(3/4)log(4/3)+(1/4)log4)=3/7+4/7(3/4log4-3/4log3+1/2
18、)=3/7+8/7-3/7log3=11/7-4.755/7=0.892bit,建决策树的树根和分枝 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，其余两个子集既含有正例又含有反例，将递归调用建树算法。,递归建树 分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征天气、气温、湿度、风）求互信息.（1）F1中的示例数S=5，天气全取晴值，则H（U）=H（U
19、|V），有I（U，V）=0取确定值；F1中正例2，反例3，P(u1)=2/5，P(u2)=3/5；H(U)=P(u1)logP(u1)+P(u2)logP(u2)=2/5log5/2+3/5log5/3=log5-2/5log2-3/5log3=2.322-0.4-0.951=0.971求气温的条件熵:热v1=2，适中v2=2，冷v3=1，P(v1)=2/5，P（v2）=3/5，P（u1/v1）=0，P（u2/v1）=1，P（u1/v2）=，P（u2/v2）=1/2,H(U/V)=0+3/5(1/2log2+1/2log2)=0.6I(U,V)=H(U)-H(U/V)=0.971-0.6=0.
20、371。,递归建树 分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征天气、气温、湿度、风）求互信息.（1）F1中的示例数S=5，F1中的正例2，反例3，P(u1)=2/5，P(u2)=3/5；H(U)=P(u1)logP(u1)+P(u2)logP(u2)=2/5log5/2+3/5log5/3=log5-2/5log2-3/5log3=2.322-0.4-0.951=0.971求湿度的条件熵，高v1=3，正常v2=2，P(v1)=3/5，P（v2）=2/5，P（u1/v1）=0，P（u2/v1）=1，P（u1/v2）=1,P（u2/v2）=0,H(U/V)=0取确定值熵
21、为零I(U,V)=H(U)-H(U/V)=0.971-0=0.971。,递归建树 分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征天气、气温、湿度、风）求互信息.（1）F1中的示例数S=5，F1中的正例2，反例3，P(u1)=2/5，P(u2)=3/5；H(U)=P(u1)logP(u1)+P(u2)logP(u2)=2/5log5/2+3/5log5/3=log5-2/5log2-3/5log3=2.322-0.4-0.951=0.971求风的条件熵：无风v1=3，有风v2=2，P(v1)=3/5，P（v2）=2/5，P（u1/v1）=1，P（u2/v1）=0，P（u1
22、/v2）=1/2,P（u2/v2）=1/2,H(U/V)=0+3/5(1/2log2+1/2log2)=0.6I(U,V)=H(U)-H(U/V)=0.971-0.6=0.371。,递归建树 分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征雨）求互信息.（1）F1中的天气全取晴值，则H（U）=H（U|V），有I（U|V）=0，气温的I（U|V）=0.371，湿度的I（U|V）=0.971，风的I（U|V）=0.371，在四个特征中求出湿度互信息（信息增益）最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标记N。取值正常的例子全为P类，该分枝标记P。（
23、2）在F3中，对四个特征求互信息，得到风特征互信息最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。这样就得到图示的决策树,对ID3的讨论,优点 ID3在选择重要特征时利用了互信息的概念，算法的基础理论清晰，使得算法较简单，是一个很有实用价值的示例学习算法。该算法的计算时间是例子个数、特征个数、结点个数之积的线性函数。总预测正确率比较高，效果是令人满意的。,缺点（1）互信息的计算依赖于特征取值的数目较多的特征，这样不太合理。一种简单的办法是对特征进行分解，如上节例中，特征取值数目不一样，可以把它们统统化为二值特征，如天气取值晴，多云，雨，
24、可以分解为三个特征；天气晴，天气多云，天气雨。取值都为“是”或“否”，对气温也可做类似的工作。这样就不存在偏向问题了。,（2）用互信息作为特征选择量存在一个假设，即训练例子集中的正、反例的比例应与实际问题领域里正、反例比例相同。一般情况不能保证相同，这样计算训练集的互信息就有偏差。（3）ID3在建树时，每个节点仅含一个特征，是一种单变元的算法，特征间的相关性强调不够。虽然它将多个特征用一棵树连在一起，但联系还是松散的。,（4）ID3对噪声较为敏感。关于什么是噪声，Quinlan的定义是训练例子中的错误就是噪声。它包含两方面，一是特征值取错，二是类别给错。（5）当训练集增加时，ID3的决策树会随
25、之变化。在建树过程中，各特征的互信息会随例子的增加而改变，从而使决策树也变化。这对渐近学习（即训练例子不断增加）是不方便的。,总的来说，ID3由于其理论的清晰，方法简单，学习能力较强，适于处理大规模的学习问题，在世界上广为流传，得到极大的关注，是数据挖掘和机器学习领域中的一个极好范例，也不失为一种知识获取的有用工具。,习题,某市高中一年级（共六个班）学生上学期期末考试成绩在学生成绩数据库中，学生人数为161人。其中学生考试成绩属性有：学籍号、语文、数学、英语、物理、化学，如下表所示，本例子的目的是利用决策树技术研究学生物理成绩的及格与否可以由哪些属性决定：,习题,原数据库成绩如下学号 语文 数
26、学 英语 物理 化学 1 76 71 68 71 81 2 71 65 63 72 74 3 60 81 67 87 80 4 73 80 66 58 67,习题,第一步：对数据进行规范化处理。分析相关性不需要具体成绩，将上表中的数据规范化，用0表示成绩小于60分，1表示成绩大于或等于60分，得到下表：学号 语文 数学 英语 物理 化学 1 1 1 1 1 1 2 1 1 1 1 1 3 1 1 1 1 1 4 1 1 1 0 1,习题,对规范化的单科成绩及格人数和不及格人数统计如下：语文 数学 英语 物理 化学 及格 82 57 34 32 39 不及格 79 104 127 129 122 用ID3求影响物理成绩最大的学科。,结束,
