《信息论方法》PPT课件.ppt

《《信息论方法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《信息论方法》PPT课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第7章 信息论方法（一）n7.1 信息论原理n7.2 决策树方法n n7.1 信息论原理信息论原理 信息论是信息论是C.E.ShannonC.E.Shannon为解决信息传递（通信）过程问题而为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。建立的理论，也称为统计通信理论。1.1.信道模型信道模型信道模型信道模型n n一个传递信息的系统是由发送端（信源）和接收端（信宿）一个传递信息的系统是由发送端（信源）和接收端（信宿）以及连接两者的通道（信道）三者组成。以及连接两者的通道（信道）三者组成。信道u1,u2.ur信源Uv1,v2.vrP(V|U)信宿Vn n在进行实际的通信之前，收

2、信者（信宿）不可在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。不可能判断信源会处于什么样的状态。n n这种情形就称为信宿对于信源状态具有不确定这种情形就称为信宿对于信源状态具有不确定性。而且这种不确定性是存在于通信之前的。因性。而且这种不确定性是存在于通信之前的。因而又叫做而又叫做先验不确定性先验不确定性，表示成，表示成 信息熵信息熵信息熵信息熵 HH（U U）n n在进行了通信之后，信宿收到了信源发来的信息，在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者

3、被减少。这种先验不确定性才会被消除或者被减少。n n如果干扰很小，不会对传递的信息产生任何可察如果干扰很小，不会对传递的信息产生任何可察觉的影响，信源发出的信息能够被信宿全部收到，觉的影响，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全在这种情况下，信宿的先验不确定性就会被完全消除。消除。n n在一般情况下，干扰总会对信源发出的信息造成某种在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。破坏，使信宿收到的信息不完全。n n先验不确定性不能全部被消除，只能部分地消除。先验不确定性不能全部被消除，只能部分地消除。n n通信结束之后，信宿仍然

4、具有一定程度的不确定性。通信结束之后，信宿仍然具有一定程度的不确定性。这就是这就是后验不确定性后验不确定性，用，用条件熵表示条件熵表示HH（U/VU/V）。n n后验不确定性总要小于先验不确定性后验不确定性总要小于先验不确定性:HH（U/VU/V）H H H（X X）故信源故信源Y Y比信源比信源X X的平均不确定性要大。的平均不确定性要大。信信息息熵熵H H（U U）是是信信源源输输出出前前的的平平均均不不确确定定性性，也称先也称先验熵验熵。HH（U U）的性）的性）的性）的性质质质质:（1 1）H H（U U）=0=0时时，说说明明只只存存在在着着唯唯一一的的可可能能性性，不存在不确定性。

5、不存在不确定性。（2 2）如如果果n n种种可可能能的的发发生生都都有有相相同同的的概概率率，即即所所有有的的U Ui i有有P P（U Ui i）=1/=1/n n，H H（U U）达达到到最最大大值值log log n n，系系统统的不确定性最大。的不确定性最大。P P（U Ui i）互互相相接接近近，H H（U U）就就大大。P P（U Ui i）相相差差大，大，则则H H（U U）就小。）就小。(1)(1)后后后后验熵验熵验熵验熵和条件和条件和条件和条件熵熵熵熵当没有接收到输出符号V时，已知输入符号U的概率分布为P（U），而当接收到输出符号V=Vj 后，输入符号的概率分布发生了变化，变

6、成后验概率分布P（U|Vj）。其后验熵为：7互信息(增益)当没有接收到输出符号V时，已知输入符号U的概率分布为P（U），而当接收到输出符号V=Vj 后，输入符号的概率分布发生了变化，变成后验概率分布P（U|Vj）。那么接收到输出符号V=Vj后，关于U的平均不确定性为：这这是接收到是接收到输输出符号出符号V Vj j后关于后关于U U的条件的条件熵熵 7互信息（增益）这这个个条条件件熵熵称称为为信信道道疑疑义义度度。它它表表示示在在输输出出端端收收到到全全部部输输出出符符号号V V后后，对对于于输输入入端端的的符符号号集集U U尚尚存存在的不确定性（存在疑在的不确定性（存在疑义义）。）。从上面分

7、析可知：条件从上面分析可知：条件熵熵小于无条件小于无条件熵熵，即，即HH（U U|V V）HH（U U）。说说明明接接收收到到符符号号集集V V的的所所有有符符号号后后，关关于于输输入入符符号号U U的的平平均均不不确确定定性性减减少少了了。即即总总能能消消除除一一些些关关于于输输入入端端X X的不确定性，从而的不确定性，从而获获得了一些信息。得了一些信息。（2）平均互信息（信息增益）平均互信息（信息增益）定义:I（U,V）=H（U）H（U|V）（3.10）I（U,V）称为U和V之间的平均互信息（信息增益），它代表接收到符号集V后获得的关于U的信息量。可见，熵（H（U）、H（U|V）只是平均

8、不 确 定 性 的 描 述。熵 差（H（U）H（U|V）是不确定性的消除，即互信息（信息增益）才是接收端所获得的信息量。（2）平均互信息（信息增益）平均互信息（信息增益）对输入端U只有U1，U2两类，互信息（信息增益）的计算公式为:7.2 7.2 决策树方法决策树方法n n7.2.17.2.1决策树概念决策树概念n n决策树是对数据进行分类，以此达到预测的目的。决策树方法先根据训练集数据形成决策树，如果该树不能对所有对象给出正确的分类，那么选择一些例外加入到训练集数据中，重复该过程一直到形成正确的决策集。决策树代表着决策集的树形结构。7.2 7.2 决策树方法决策树方法n n7.2.17.2.

9、1决策树概念决策树概念n n决策树由决策结点、分支和决策树由决策结点、分支和叶子组成。决策树中最上面叶子组成。决策树中最上面的结点为根结点，每个分支的结点为根结点，每个分支是一个新的决策结点，或者是一个新的决策结点，或者是树的叶子。每个决策结点是树的叶子。每个决策结点代表一个问题或决策，通常代表一个问题或决策，通常对应于待分类对象的属性。对应于待分类对象的属性。每一个叶子结点代表一种可每一个叶子结点代表一种可能的分类结果。能的分类结果。天气湿度风晴雨多云高正常有风无风PNNPP7.2 7.2 决策树方法决策树方法n n7.2.17.2.1决策树概念决策树概念n n决策树的根结点是所有样本中信息

10、量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的属性。决策树的叶结点是样本的类别值。天 气湿 度风晴雨多云高正常有风无风PNNPPn n决策树是一种知识表示形式，它是对所有样本数决策树是一种知识表示形式，它是对所有样本数据的高度概括。据的高度概括。n n决策树能准确地识别所有样本的类别，也能有效决策树能准确地识别所有样本的类别，也能有效地识别新样本的类别。地识别新样本的类别。7.2.2 ID37.2.2 ID3方法基本思想方法基本思想n n当前国际上最有影响的CLS(Concept Learning System)是ID3（Interative Discremiser

11、 versions3）.n nID3算法是由Quinlan首先提出的，该算法是以信息论为基础，以信息熵和信息增益度为衡量标准，从而实现对数据的归纳分类。7.2.2 ID37.2.2 ID3方法基本思想方法基本思想n nCLS原理：n n首先找出首先找出最有判别力的特征最有判别力的特征，把数据分成，把数据分成多个子集，每个多个子集，每个子集又选择最有判别力的子集又选择最有判别力的特征特征进行划分，一直进行到进行划分，一直进行到所有子集仅包所有子集仅包含同一类型含同一类型的数据为止。最后得到一棵决的数据为止。最后得到一棵决策树。策树。n n如：有关气候类型的研究，特征（属性）如：有关气候类型的研究

12、，特征（属性）天气（晴、雨、多云），气温（冷、热、天气（晴、雨、多云），气温（冷、热、适中），风（有风、无风）等适中），风（有风、无风）等7.2.2 ID37.2.2 ID3方法基本思想方法基本思想n nCLS原理：原理：n n怎么来确定哪个是有判断力的属性呢怎么来确定哪个是有判断力的属性呢？n nJ.R.Quinlan的工作主要是引进了信息的工作主要是引进了信息论中的互信息，他将其称为信息增益论中的互信息，他将其称为信息增益（information gain），作为特征判别），作为特征判别能力的度量。能力的度量。例如：关于气候的类型，特征为:天气 取值为：晴，多云，雨 气温 取值为：冷，适中

13、，热 湿度 取值为：高，正常 风 取值为：有风，无风 一、一、ID3ID3基本思想基本思想n n为简单起见，假定仅有两个类别，分为简单起见，假定仅有两个类别，分别为别为P，N。在这种两个类别的归纳任。在这种两个类别的归纳任务中，务中，P类和类和N类的实体分别称为概念类的实体分别称为概念的正例和反例。将一些已知的正例和的正例和反例。将一些已知的正例和反例放在一起便得到训练集。反例放在一起便得到训练集。NO.属性类别天气气温湿度风1晴热高无风N2晴热高有风N3多云热高无风P4雨适中高无风P5雨冷正常无风P6雨冷正常有风N7多云冷正常有风P8晴适中高无风N9晴冷正常无风P10雨适中正常无风P11晴适

14、中正常有风P12多云适中高有风P13多云热正常无风P14雨适中高有风N天 气湿 度风晴雨多云高正常有风无风PNNPPID3决策树对上表给出的训练集，由对上表给出的训练集，由ID3算法得出一棵算法得出一棵正确分类训练集中每个实体的决策树正确分类训练集中每个实体的决策树n n决策树叶子为类别名，即决策树叶子为类别名，即P P 或者或者NN。其它结点由实。其它结点由实体的特征组成，每个特征的不同取值对应一分枝。体的特征组成，每个特征的不同取值对应一分枝。n n若要对一实体分类，从树根开始进行测试，按特若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点，对该结点进行征的取值分枝向下

15、进入下层结点，对该结点进行测试，过程一直进行到叶结点，实体被判为属于测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。该叶结点所标记的类别。天气湿度风晴雨多云高正常有风无风PNNPPn n现用图来判一个具体例子，现用图来判一个具体例子，某天早晨气候描述为某天早晨气候描述为:天气天气：多云：多云 气温气温：冷：冷 湿度湿度：正常：正常 风风：无风无风 它属于哪类气候呢它属于哪类气候呢?n n从图中可判别该实体从图中可判别该实体的类别为的类别为P P类。类。天 气湿 度风晴雨多云高正常有风无风PNNPPID3ID3就是要从表的训练集来构造上图这样的决策树。就是要从表的训练集来构造上图

16、这样的决策树。实际上，能正确分类训练集的决策树不止一棵。实际上，能正确分类训练集的决策树不止一棵。QuinlanQuinlan的的ID3ID3算法能得出结点最少的决策树。算法能得出结点最少的决策树。（一）主算法（一）主算法 从训练集中随机选择一个既含正例又含反例的子集（称为窗口）；用“建树算法”对当前窗口形成一棵决策树；对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；若存在错判的例子，把它们插入窗口，转2，否则结束。二、二、ID3ID3算法算法训练集PE、NE取子集建窗口窗口PE、NE生成决策树测试PE、NE扩展窗口PE=PE+PENE=NE+NE此决策树为最后结果存在错判

17、的PE，NE吗是否ID3主算法流程PE、NE分别表示正例集和反例集，它们共同组成训练集PE，PE和NE，NE分别表示正例集和反例集的子集。主算法流程用下图表示主算法流程用下图表示 对当前例子集合，计算各特征的互信息（信息对当前例子集合，计算各特征的互信息（信息增益）；增益）；选择互信息（信息增益）最大的特征选择互信息（信息增益）最大的特征A Ak k；把在把在A Ak k处取值相同的例子归于同一子集，处取值相同的例子归于同一子集，A Ak k取取几个值就得几个子集；几个值就得几个子集；对既含正例又含反例的子集，递归调用建树算对既含正例又含反例的子集，递归调用建树算法；法；若子集仅含正例或反例，

18、对应分枝标上若子集仅含正例或反例，对应分枝标上P P或或NN，返回调用处。返回调用处。（二）建树算法（二）建树算法实例计算实例计算 对于气候分类问题进行具体计算对于气候分类问题进行具体计算（找出（找出根节点根节点）信息熵的计算信息熵的计算信息熵的计算信息熵的计算信息熵：信息熵：类别出现概率：类别出现概率：|S|S|表示例子集表示例子集S S的总数（的总数（1414），），|u|ui i|表示类别表示类别u ui i的例子数。的例子数。u u1 1代表正例代表正例P P共共9 9个和个和u u2 2代表反例代表反例NN共共5 5个，有：个，有：P P（u u1 1）=9/14=9/14 P P（

19、u u2 2）=5/14=5/14H(U)=H(U)=（9/149/14）loglog（14/914/9）+（5/145/14）loglog（14/514/5）=0.94bit=0.94bitNO.属性类别天气气温湿度风1晴热高无风N2晴热高有风N3多云热高无风P4雨适中高无风P5雨冷正常无风P6雨冷正常有风N7多云冷正常有风P8晴适中高无风N9晴冷正常无风P10雨适中正常无风P11晴适中正常有风P12多云适中高有风P13多云热正常无风P14雨适中高有风N 条件条件熵计熵计算算条件条件熵熵：属性属性A A1 1取取值值v vj j时时，类别类别u ui i的条件概率：的条件概率：A A1 1=

20、天气天气 取取值值 v v1 1=晴，晴，v v2 2=多云，多云，v v3 3=雨雨在在A A1 1处处取取值值晴晴的的例例子子5 5个个，取取值值多多云云的的例例子子4 4 个个，取取值值雨雨的的例例子子5 5 个，故：个，故：P P（v v1 1）=5/14 P=5/14 P（v v2 2）=4/14 P=4/14 P（v v3 3）=5/14=5/14取取值为值为晴的晴的5 5 个例子中有个例子中有2 2 个正例、个正例、3 3个反例，故：个反例，故：P P（u u1 1/v/v1 1）=2/5=2/5，P P（u u2 2/v/v1 1）=3/5=3/5同理有：同理有：P P（u u

21、1 1/v/v2 2）=4/4=4/4，P P（u u2 2/v/v2 2）=0=0 P P（u u1 1/v/v3 3）=2/5=2/5，P P（u u2 2/v/v3 3）=3/5=3/5H(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/14)(4/4)log(4/4)H(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+0)+(5/14)(2/5)log(5/2)+(3/5)log(5/3)=

22、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 条件条件熵计熵计算算A A2 2=气温气温 取取值值 v v1 1=热热，v v2 2=适中，适中，v v3 3=冷冷在在A A2 2处处取取值值热热的的例例子子4 4个个，取取值值适适中中的的例例子子6 6 个个，取取值值冷冷的的例例子子4 4 个，故：个，故：P

23、 P（v v1 1）=4/14 P=4/14 P（v v2 2）=6/14 P=6/14 P（v v3 3）=4/14=4/14取取值为热值为热的的4 4个例子中有个例子中有2 2个正例、个正例、2 2个反例，故：个反例，故：P P（u u1 1/v/v1 1）=2/4=2/4，P P（u u2 2/v/v1 1）=2/4=2/4同理有：同理有：P P（u u1 1/v/v2 2）=4/6=4/6，P P（u u2 2/v/v2 2）=2/6=2/6 P P（u u1 1/v/v3 3）=3/4=3/4，P P（u u2 2/v/v3 3）=1/4=1/4H(U/V)=(4/14)(2/4)l

24、og(4/2)+(2/4)log(4/2)+(6/14)(2/3)log(3/2)H(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)+(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+2/7+3/7(2/3)log3-2/3log2+(1/3)log3)+2/7(3/4)log4-(1/3)log3)+2/7(3/4)log4-(3/4

25、)log3+1/2)=2/7+2/7log3-(3/4)log3+1/2)=2/7+2/7log3-2/7+4/7+3/14log3=4/7+3/14log3=0.911bit2/7+4/7+3/14log3=4/7+3/14log3=0.911bit 条件条件熵计熵计算算A A3 3=湿度湿度 取取值值 v v1 1=高，高，v v2 2=正常正常在湿度在湿度A A3 3处处取取值值高的例子高的例子7 7个，取个，取值值正常的例子正常的例子7 7个，故：个，故：P P（v v1 1）=7/14=1/2 P=7/14=1/2 P（v v2 2）=7/14=1/2=7/14=1/2取取值为值为高

26、的高的7 7个例子中有个例子中有3 3个正例、个正例、4 4个反例，故：个反例，故：P P（u u1 1/v/v1 1）=3/7=3/7，P P（u u2 2/v/v1 1）=4/7=4/7同理有：同理有：P P（u u1 1/v/v2 2）=6/7=6/7，P P（u u2 2/v/v2 2）=1/7=1/7H(U/V)=(1/2)(3/7)log(7/3)+(4/7)log(7/4)+(1/2)(6/7)log(7/6)H(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/7)log(7/1)

27、=1/2(=1/2(3/7log73/7log7-3/7log3+-3/7log3+4/7log74/7log7-4/7log4+-4/7log4+6/7log76/7log7-6/7log6+6/7log6+1/7log71/7log7-0)=1/2(2log7-9/7log3-2log2)=1/2(5.614-2.038-0)=1/2(2log7-9/7log3-2log2)=1/2(5.614-2.038-2)=0.7881bit2)=0.7881bit 条件条件熵计熵计算算A A4 4=风风 取取值值 v v1 1=有有风风，v v2 2=无无风风在在风风A A4 4处处取取值值有有风

28、风的例子的例子6 6个，取个，取值值无无风风的例子的例子8 8个，故：个，故：P P（v v1 1）=6/14=3/7 P=6/14=3/7 P（v v2 2）=8/14=4/7=8/14=4/7取取值为值为有有风风的的6 6个例子中有个例子中有3 3个正例、个正例、3 3个反例，故：个反例，故：P P（u u1 1/v/v1 1）=3/6=1/2=3/6=1/2，P P（u u2 2/v/v1 1）=3/6=1/2=3/6=1/2同理有：同理有：P P（u u1 1/v/v2 2）=6/8=3/4=6/8=3/4，P P（u u2 2/v/v2 2）=2/8=1/4=2/8=1/4H(U/V

29、)=(3/7)(1/2)log2+(1/2)log2)+(4/7)(3/4)log(4/3)H(U/V)=(3/7)(1/2)log2+(1/2)log2)+(4/7)(3/4)log(4/3)+(1/4)log4)+(1/4)log4)=3/7+4/7(=3/7+4/7(3/4log43/4log4-3/4log3+1/2)=3/7+8/7-3/7log3=11/7-3/4log3+1/2)=3/7+8/7-3/7log3=11/7-4.755/7=0.892bit4.755/7=0.892bit 建决策树的树根和分枝建决策树的树根和分枝 ID3算法将选择互信息最大的特征天气算法将选择互信息

30、最大的特征天气作为树根，在作为树根，在14个例子中对天气的个例子中对天气的3个取值个取值(晴晴雨多云雨多云)进行分枝，进行分枝，3 个分枝对应个分枝对应3 个子集是个子集是:晴晴F1=1，2，8，9，11，多云多云 F2=3，7，12，13，雨雨F3=4，5，6，10，14 其中其中F2中的例子全属于中的例子全属于P类，因此对应类，因此对应分枝标记为分枝标记为P，其余两个子集既含有正例又含，其余两个子集既含有正例又含有反例，将递归调用建树算法。有反例，将递归调用建树算法。递归建树递归建树递归建树递归建树 分别对分别对F1F1和和F3F3子集利用子集利用ID3ID3算法，在每个子集中对各特算法，

31、在每个子集中对各特征（仍为四个特征天气、气温、湿度、风）求互信息征（仍为四个特征天气、气温、湿度、风）求互信息.（1 1）F1F1中的示例数中的示例数S=5S=5，天气全取晴值，则，天气全取晴值，则HH（U U）=H=H（U|VU|V），有），有I I（U U，V V）=0=0取确定值取确定值；F1F1中中正例正例2 2，反例，反例3 3，P(uP(u1 1)=2/5)=2/5，P(uP(u2 2)=3/5)=3/5；H(U)=P(uH(U)=P(u1 1)logP(u)logP(u1 1)+P(u)+P(u2 2)logP)logP(u(u2 2)=2/5log5/2+3/5log5/3=l

32、og5-2/5log2-3/5log3=2.322-0.4-)=2/5log5/2+3/5log5/3=log5-2/5log2-3/5log3=2.322-0.4-0.951=0.9710.951=0.971求气温的条件熵求气温的条件熵:热热v v1 1=2=2，适中适中v v2 2=2=2，冷冷v v3 3=1=1，P(vP(v1 1)=2/5)=2/5，P P（v v2 2）=3/5=3/5，P P（u u1 1/v/v1 1）=0=0，P P（u u2 2/v/v1 1）=1=1，P P（u u1 1/v/v2 2）=，P P（u u2 2/v/v2 2）=1/2,=1/2,H(U/V

33、)=0+3/5(1/2log2+1/2log2)=0.6H(U/V)=0+3/5(1/2log2+1/2log2)=0.6I(U,V)=H(U)-H(U/V)=0.971-0.6=0.371I(U,V)=H(U)-H(U/V)=0.971-0.6=0.371。递归建树递归建树递归建树递归建树 分别对分别对F1F1和和F3F3子集利用子集利用ID3ID3算法，在每个子集中对各特算法，在每个子集中对各特征（仍为四个特征天气、气温、湿度、风）求互信息征（仍为四个特征天气、气温、湿度、风）求互信息.（1 1）F1F1中的示例数中的示例数S=5S=5，F1F1中的中的正例正例2 2，反例，反例3 3，P

34、(uP(u1 1)=2/5)=2/5，P(uP(u2 2)=3/5)=3/5；H(U)=P(uH(U)=P(u1 1)logP(u)logP(u1 1)+P(u)+P(u2 2)logP(u)logP(u2 2)=2/5log5/2+3/5log5/3=log5-)=2/5log5/2+3/5log5/3=log5-2/5log2-3/5log3=2.322-0.4-0.951=0.9712/5log2-3/5log3=2.322-0.4-0.951=0.971求湿度的条件熵，求湿度的条件熵，高高v v1 1=3=3，正常正常v v2 2=2=2，P(vP(v1 1)=3/5)=3/5，P P

35、（v v2 2）=2/5=2/5，P P（u u1 1/v/v1 1）=0=0，P P（u u2 2/v/v1 1）=1=1，P P（u u1 1/v/v2 2）=1,1,P P（u u2 2/v/v2 2）=0,=0,H(U/V)=0H(U/V)=0取确定取确定值熵为值熵为零零I(U,V)=H(U)-H(U/V)=0.971-0=0.971I(U,V)=H(U)-H(U/V)=0.971-0=0.971。递归建树递归建树递归建树递归建树 分别对分别对F1F1和和F3F3子集利用子集利用ID3ID3算法，在每个子集中对各特算法，在每个子集中对各特征（仍为四个特征天气、气温、湿度、风）求互信息征

36、（仍为四个特征天气、气温、湿度、风）求互信息.（1 1）F1F1中的示例数中的示例数S=5S=5，F1F1中的中的正例正例2 2，反例，反例3 3，P(uP(u1 1)=2/5)=2/5，P(uP(u2 2)=3/5)=3/5；H(U)=P(uH(U)=P(u1 1)logP(u)logP(u1 1)+P(u)+P(u2 2)logP(u)logP(u2 2)=2/5log5/2+3/5log5/3=log5-)=2/5log5/2+3/5log5/3=log5-2/5log2-3/5log3=2.322-0.4-0.951=0.9712/5log2-3/5log3=2.322-0.4-0.9

37、51=0.971求风的条件熵：无风求风的条件熵：无风v v1 1=3=3，有有风风v v2 2=2=2，P(vP(v1 1)=3/5)=3/5，P P（v v2 2）=2/5=2/5，P P（u u1 1/v/v1 1）=1=1，P P（u u2 2/v/v1 1）=0=0，P P（u u1 1/v/v2 2）=1/2,=1/2,P P（u u2 2/v/v2 2）=1/2,=1/2,H(U/V)=0+3/5(1/2log2+1/2log2)=0.6H(U/V)=0+3/5(1/2log2+1/2log2)=0.6I(U,V)=H(U)-H(U/V)=0.971-0.6=0.371I(U,V)

38、=H(U)-H(U/V)=0.971-0.6=0.371。递归建树递归建树递归建树递归建树 分别对分别对F1F1和和F3F3子集利用子集利用ID3ID3算法，在每个子集中对各特算法，在每个子集中对各特征（仍为四个特征雨）求互信息征（仍为四个特征雨）求互信息.（1 1）F1F1中的天气全取晴值，则中的天气全取晴值，则HH（U U）=H=H（U|VU|V），有），有I I（U|VU|V）=0=0，气温的，气温的I I（U|VU|V）=0.371=0.371，湿度的，湿度的I I（U|VU|V）=0.971=0.971，风的，风的I I（U|VU|V）=0.371=0.371，在四个特征中求出，在四

39、个特征中求出湿度互信息（信息增益）最大，以它为该分枝的根结点，再湿度互信息（信息增益）最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为向下分枝。湿度取高的例子全为NN类，该分枝标记类，该分枝标记NN。取值。取值正常的例子全为正常的例子全为P P类，该分枝标记类，该分枝标记P P。（2 2）在在F3F3中，对四个特征求互信息，得到风特征互信息中，对四个特征求互信息，得到风特征互信息最大，则以它为该分枝根结点。再向下分枝，风取有风时全最大，则以它为该分枝根结点。再向下分枝，风取有风时全为为NN类，该分枝标记类，该分枝标记NN。取无风时全为。取无风时全为P P类，该分枝标记类，该分枝标记P

40、 P。这样就得到图示的决策树这样就得到图示的决策树 对ID3的讨论 优点优点优点优点 ID3ID3在选择重要特征时利用了互信息的概念，算在选择重要特征时利用了互信息的概念，算法的基础理论清晰，使得算法较简单，是一个很有法的基础理论清晰，使得算法较简单，是一个很有实用价值的示例学习算法。实用价值的示例学习算法。该算法的计算时间是例子个数、特征个数、结该算法的计算时间是例子个数、特征个数、结点个数之积的线性函数。总预测正确率比较高，效点个数之积的线性函数。总预测正确率比较高，效果是令人满意的。果是令人满意的。缺点缺点 （1 1）互信息的计算依赖于特征取值的数目较多的互信息的计算依赖于特征取值的数目

41、较多的特征，这样不太合理。一种简单的办法是对特征进特征，这样不太合理。一种简单的办法是对特征进行分解，如上节例中，特征取值数目不一样，可以行分解，如上节例中，特征取值数目不一样，可以把它们统统化为二值特征，如天气取值晴，多云，把它们统统化为二值特征，如天气取值晴，多云，雨，可以分解为三个特征；天气雨，可以分解为三个特征；天气晴，天气晴，天气多云，多云，天气天气雨。取值都为雨。取值都为“是是”或或“否否”，对气温也可，对气温也可做类似的工作。这样就不存在偏向问题了。做类似的工作。这样就不存在偏向问题了。（2）用互信息作为特征选择量存在一个假设，即训练例子集中的正、反例的比例应与实际问题领域里正、

42、反例比例相同。一般情况不能保证相同，这样计算训练集的互信息就有偏差。（3）ID3在建树时，每个节点仅含一个特征，是一种单变元的算法，特征间的相关性强调不够。虽然它将多个特征用一棵树连在一起，但联系还是松散的。（4）ID3对噪声较为敏感。关于什么是噪声，Quinlan的定义是训练例子中的错误就是噪声。它包含两方面，一是特征值取错，二是类别给错。（5）当训练集增加时，ID3的决策树会随之变化。在建树过程中，各特征的互信息会随例子的增加而改变，从而使决策树也变化。这对渐近学习（即训练例子不断增加）是不方便的。总的来说，总的来说，ID3ID3由于其理论的清晰，方法简由于其理论的清晰，方法简单，学习能力

43、较强，适于处理大规模的学习问题单，学习能力较强，适于处理大规模的学习问题 ，在世界上广为流传，得到极大的关注，是数据，在世界上广为流传，得到极大的关注，是数据挖掘和机器学习领域中的一个极好范例，也不失挖掘和机器学习领域中的一个极好范例，也不失为一种知识获取的有用工具。为一种知识获取的有用工具。习题习题n n某市高中一年级（共六个班）学生上学期期末考试成绩在学生成绩数据库中，学生人数为161人。其中学生考试成绩属性有：学籍号、语文、数学、英语、物理、化学，如下表所示，本例子的目的是利用决策树技术研究学生物理成绩的及格与否可以由哪些属性决定：习题习题n n原数据库成绩如下n n学号 语文 数学 英

44、语 物理 化学 1 76 71 68 71 81 2 71 65 63 72 74 3 60 81 67 87 80 4 73 80 66 58 67n n习题习题n n第一步：对数据进行规范化处理。分析相关性不需要具体成绩，将上表中的数据规范化，用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 n n 习题习题n n对规范化的单科成绩及格人数和不及格人数统计如下：语文 数学 英语 物理 化学 及格 82 57 34 32 39 不及格 79 104 127 129 122 n n用ID3求影响物理成绩最大的学科。结束