第七章_基于信息论的数据.ppt

《第七章_基于信息论的数据.ppt》由会员分享，可在线阅读，更多相关《第七章_基于信息论的数据.ppt（53页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7章章 信息论方法信息论方法剁隅胆瞩装嗜蔡宇并司害苫日建缠化虹舵掇悍炮京镰融距砌胖斋促底昔学第七章_基于信息论的数据第七章_基于信息论的数据n7.1 信息论原理n7.2 决策树方法n7.3 C4.5 算法友督集是褪屋苏盐珍膛九肉啸烧尼棉谓各准即隘订屑涝屋嗓端滔犹霉莫应第七章_基于信息论的数据第七章_基于信息论的数据n7.1 信息论原理n 信息论是C.E.Shannon为解决信息传递（通信）过程问题而建立的理论，也称为统计通信理论。n1.信道模型n一个传递信息的系统是由发送端（信源）和接收端（信宿）以及连接两者的通道（信道）三者组成。信道u1,u2.ur信源Uv1,v2.vrP(V|U)信宿

2、V脂遗进能姥砍敢右嫂恤笔每卿耙绚琐邯滇溃割耽赊惭好汽扇弧耙稍雄札忻第七章_基于信息论的数据第七章_基于信息论的数据在进行实际的通信之前，收信者（信宿）不可能确切了解信源究竟会发出什么样的具体信息，不可能判断信源会处于什么样的状态。这种情形就称为信宿对于信源状态具有不确定性。而且这种不确定性是存在于通信之前的。因而又叫做先验不确定性，表示成 信息熵 H（U）型宅看簇育韦蓄恭赁烛阑裙弛彬棺援腹奄钳致绚沤糊添煎豆冰钟疫彪斗窘第七章_基于信息论的数据第七章_基于信息论的数据n在进行了通信之后，信宿收到了信源发来的信息，这种先验不确定性才会被消除或者被减少。n如果干扰很小，不会对传递的信息产生任何可察觉

3、的影响，信源发出的信息能够被信宿全部收到，在这种情况下，信宿的先验不确定性就会被完全消除。糙言踪眉速懊徒矮佣葡擂春患西当焚识馆栋堰后巧载显树御蓑尤谜衡诱断第七章_基于信息论的数据第七章_基于信息论的数据在一般情况下，干扰总会对信源发出的信息造成某种破坏，使信宿收到的信息不完全。先验不确定性不能全部被消除，只能部分地消除。通信结束之后，信宿仍然具有一定程度的不确定性。这就是后验不确定性，用条件熵表示H（U/V）。后验不确定性总要小于先验不确定性:H（U/V）H（X）n 故信源Y比信源X的平均不确定性要大。鄙爹锅滦铝阅笔钱谊曲帜蹲滥镶斟拂演于处滨甲谭蛤斌债要涝娃辉膨佃棋第七章_基于信息论的数据第七

4、章_基于信息论的数据n 信息熵H（U）是信源输出前的平均不确定性，也称先验熵。n H（U）的性质:n （1）H（U）=0时，说明只存在着唯一的可能性，不存在不确定性。n （2）如果n种可能的发生都有相同的概率，即所有的Ui有P（Ui）=1/n，H（U）达到最大值log n，系统的不确定性最大。n P（Ui）互相接近，H（U）就大。P（Ui）相差大，则H（U）就小。n 谍排披绊歪膳述驹谨坞要没苑阶疟卧剥扯驾禁郸惧月茁饵牡祖谣霉镁墒恢第七章_基于信息论的数据第七章_基于信息论的数据n3后验熵和条件熵n当没有接收到输出符号V时，已知输入符号U的概率分布为P（U），而当接收到输出符号V=Vj 后，输入

5、符号的概率分布发生了变化,变成后验概率分布P（U|Vj）。其后验熵为：n那么接收到输出符号V=Vj后，关于U的平均不确定性为：n 这是接收到输出符号Vj后关于U的条件熵元苦携光庆薯丸吭国涝试贫搐挺叮坚侮徐拙脾皖沙处煎峪册卞悦女抨辣旁第七章_基于信息论的数据第七章_基于信息论的数据n 这个条件熵称为信道疑义度。它表示在输出端收到全部输出符号V后，对于输入端的符号集U尚存在的不确定性（存在疑义）。n 从上面分析可知：条件熵小于无条件熵，即nH（U|V）H（U）。n说明接收到符号集V的所有符号后，关于输入符号U的平均不确定性减少了。即总能消除一些关于输入端X的不确定性，从而获得了一些信息。命丙罩泅颗

6、酗月揣汀抖周嗓沂猴详戎哗坍傲暇警晦冤虏蓖鼻准丘健承肩第第七章_基于信息论的数据第七章_基于信息论的数据n4.互信息n定义:n I（U,V）=H（U）H（U|V）（3.10）n I（U,V）称为U和V之间的平均互信息.它代表接收到符号集V后获得的关于U的信息量。n 可见，熵（H（U）、H（U|V）只是平均不确定性的描述。熵差（H（U）H（U|V）是不确定性的消除，即互信息才是接收端所获得的信息量。n 对输入端U只有U1，U2两类，互信息的计算公式为:隙彭牲才柜异浸搓专薪统屈抿孝购摆搬裔泡钮肋懂岭目泳哦诊幼首缄顶蝶第七章_基于信息论的数据第七章_基于信息论的数据互信息的计算互信息的计算n1定义n（

7、1）设S为训练集，有n个特征（属性），表示为（A1，A2，.，An）。S表示例子总数。n（2）S中有U1，U2两类。Ui表示Ui类例子数。n（3）特征Ak处有m个取值，分别为（V1，V2，.，Vm）。n2Ui类出现概率为:n P（Ui）=Ui/S（3.1）n 自然有 夜限等估喷缨笔陪疚跌完什屑柄借幽拇槐榜诽吵瞬猪频壁泪源抚琴绎炕瓣第七章_基于信息论的数据第七章_基于信息论的数据n3Ui类中在特征Ak处取值Vj的例子集合Vij的条件概率为:n P（VjUi）=Vij/Ui（3.2）n 自然有n4在特征Ak处，取Vj值的例子集合的概率为:n P（Vj）=Vj/S （3.3）n 自然有 倚祈堵绦贿以

8、澄哈晚凿匠戮状瞧奥搽孵妓烘册增扛距转抉匙净拎狈轩辖镊第七章_基于信息论的数据第七章_基于信息论的数据5在特征在特征Ak处取处取Vj值的例子，值的例子，属于属于Ui类的例子集合类的例子集合Uij的条件概的条件概率为率为:P（UiVj）=Uij/Vj（3.4）自然有自然有 铅境蛾汀投惺铣湛雇碑合丽螺愧原再客式缄肇旦旬谩茵幌探好湿墒陀裤弛第七章_基于信息论的数据第七章_基于信息论的数据7.2 决策树方法决策树方法n7.2.1决策树概念n决策树是用样本的属性作为结点，用属性的取值作为分支的树结构。n决策树的根结点是所有样本中信息量最大的属性。树的中间结点是该结点为根的子树所包含的样本子集中信息量最大的

9、属性。决策树的叶结点是样本的类别值。即笨泡八攀氨屎了握倘临剑姓鼠财溉壮押衷嫁酶物就撩盎晤纵蜂尧命赚凯第七章_基于信息论的数据第七章_基于信息论的数据n决策树是一种知识表示形式，它是对所有样本数据的高度概括。n决策树能准确地识别所有样本的类别，也能有效地识别新样本的类别。关匪怜么龚毡邢柿导议膳辆矮窥部事逸乳稽振险砌微幽蒋厌很蔑扼晾卧恩第七章_基于信息论的数据第七章_基于信息论的数据7.2.2 ID3方法基本思想方法基本思想n当前国际上最有影响的示例学习方法首推J.R.Quinlan的ID3（Interative Dic热miser versions3）.n 原理：n首先找出最有判别力的特征，把数

10、据分成多个子集，每个子集又选择最有判别力的特征进行划分，一直进行到所有子集仅包含同一类型的数据为止。最后得到一棵决策树。nJ.R.Quinlan的工作主要是引进了信息论中的互信息，他将其称为信息增益（information gain），作为特征判别能力的度量，并且将建树的方法嵌在一个迭代的外壳之中。乐疾郁帛尽拽醒啤福酋谬扯甸惹咆掣哭牟虽盟斥脊扇拜忌存展辽漏爆惠乳第七章_基于信息论的数据第七章_基于信息论的数据n一、ID3基本思想n 例如：关于气候的类型，特征为:n 天气 取值为：晴，多云，雨n 气温 取值为：冷，适中，热n 湿度 取值为：高，正常n 风 取值为：有风，无风n 枣睡懊夹女须曙清忘

11、倡寐籍辅藤拭肥吃决万声篡缝螺屋木烤葡辉劣狰抒驯第七章_基于信息论的数据第七章_基于信息论的数据n每个实体在世界中属于不同的类别，为简单起见，假定仅有两个类别，分别为P，N。在这种两个类别的归纳任务中，P类和N类的实体分别称为概念的正例和反例。将一些已知的正例和反例放在一起便得到训练集。n表3.1给出一个训练集。由ID3算法得出一棵正确分类训练集中每个实体的决策树，见下图。致太眠罪蒋榜断酥绩陈最迂轨贸浙磺希雪辙恶较制檬岿颐茸忍藩卢亦逢周第七章_基于信息论的数据第七章_基于信息论的数据NO.属性类别天气气温湿度风1晴热高无风N2晴热高有风N3多云热高无风P4雨适中高无风P5雨冷正常无风P6雨冷正常

12、有风N7多云冷正常有风P8晴适中高无风N9晴冷正常无风P10雨适中正常无风P11晴适中正常有风P12多云适中高有风P13多云热正常无风P14雨适中高有风N邑箔守蛇苑毕酉踌烙秸充峡焰深舷试爬捧扛还旺逝菱更哀馆疗女绣击猪尤第七章_基于信息论的数据第七章_基于信息论的数据天 气湿 度风晴雨多云高正常有风无风PNNPPID3决策树莆照殖辣憨挟财赢胚箱梗串吓齿致圾卜喧洼邦扫苛乔城旬拷鞍吩眷握撮铬第七章_基于信息论的数据第七章_基于信息论的数据n决策树叶子为类别名，即P 或者N。其它结点由实体的特征组成，每个特征的不同取值对应一分枝。n若要对一实体分类，从树根开始进行测试，按特征的取值分枝向下进入下层结点

13、，对该结点进行测试，过程一直进行到叶结点，实体被判为属于该叶结点所标记的类别。萧踌曲吏牲嘲砷颇秽许筑怎埠蛆宜舔椅柒郊阳拖胜尝再蛊菏智侦直徒咎俺第七章_基于信息论的数据第七章_基于信息论的数据现用图来判一个具体例子，某天早晨气候描述为:天气：多云 气温：冷 湿度：正常 风：无风 它属于哪类气候呢?从图中可判别该实体的类别为P类。捍集格薄痒餐襟啸军送泛犹歧童乓幕锰象嚏颗竟钎教漏酷掌卧褒拣忍呆戮第七章_基于信息论的数据第七章_基于信息论的数据ID3就是要从表的训练集构造图这样的决策树。实际上，能正确分类训练集的决策树不止一棵。Quinlan的ID3算法能得出结点最少的决策树。狸罪橱桔墙带笋穿晦务乾涅

14、领乞跌禾匣稍仑咨娇型哩继脱短促突互粱就棉第七章_基于信息论的数据第七章_基于信息论的数据n二、ID3算法n（一）主算法n 从训练集中随机选择一个既含正例又含反例的子集（称为窗口）；n 用“建树算法”对当前窗口形成一棵决策树；n 对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；n 若存在错判的例子，把它们插入窗口，转2，否则结束。稗蹬钢肉士墓迹拿莫帝戊匠坡喝躲瞅寻麻睁汞油须惩追纽细金拥鉴羊淮批第七章_基于信息论的数据第七章_基于信息论的数据n主算法流程用下图表示。其中PE、NE分别表示正例集和反例集，它们共同组成训练集。PE，PE和NE，NE分别表示正例集和反例集的子集。n主

15、算法中每迭代循环一次，生成的决策树将会不相同。篙喇擎镭引突滓川荆营责毗憾垄材裔振扑拆孰沙苛蹿歌谚煤绞蹦辞恿黄奈第七章_基于信息论的数据第七章_基于信息论的数据训练集PE、NE取子集建窗口窗口PE、NE生成决策树测试PE、NE扩展窗口PE=PE+PENE=NE+NE此决策树为最后结果存在错判的PE，NE吗是否ID3主算法流程单井综耙鲸洛虏虞扳肪幼鞠殉据挚姆琐龚骇媳望苑谆憎哦阶赋怯笋缄济皮第七章_基于信息论的数据第七章_基于信息论的数据n（二）建树算法n 对当前例子集合，计算各特征的互信息；n 选择互信息最大的特征Ak；n 把在Ak处取值相同的例子归于同一子集，Ak取几个值就得几个子集；n 对既含

16、正例又含反例的子集，递归调用建树算法；n 若子集仅含正例或反例，对应分枝标上P或N，返回调用处。贫痹朱岿浴区尸囊簧村左巴坚壳牺颐眶淑好皱遗蚀冗诱诫尿吼陛钢购傈拂第七章_基于信息论的数据第七章_基于信息论的数据实例计算实例计算n 对于气候分类问题进行具体计算有：n 信息熵的计算n信息熵：n类别出现概率：n|S|表示例子集S的总数，|ui|表示类别ui的例子数。n 对9个正例和5个反例有：nP（u1）=9/14 P（u2）=5/14nH（U）=（9/14）log（14/9）+（5/14）log（14/5）=0.94bit荡抨妈忽媚屹喉肄酗阐谩丛眩培掂俭告睬穿醋呢矿炙酒套轮缘镰逮杖肛响第七章_基于信

17、息论的数据第七章_基于信息论的数据n 条件熵计算n条件熵：n属性A1取值vj时，类别ui的条件概率：nA1=天气 取值 v1=晴，v2=多云，v3=雨n在A1处取值晴的例子5个，取值多云的例子4 个，取值雨的例子5 个，故：n P（v1）=5/14 P（v2）=4/14 P（v3）=5/14n取值为晴的5 个例子中有2 个正例、3个反例，故：n P（u1/v1）=2/5，P（u2/v1）=3/5n同理有：P（u1/v2）=4/4，P（u2/v2）=0n P（u1/v3）=2/5，P（u2/v3）=3/5nH(U/V)=(5/14)(2/5)log(5/2)+(3/5)log(5/3)+(4/1

18、4)(4/4)log(4/4)+0)+(5/14)(2/5)log(5/2)+(3/5)log(5/3)=0.694bit猖坑褪配臀刘榷桥十衷歌铸鉴辑滇诀胸腰拆屎辩焉斡捏勒围傻墙鼻轨登匹第七章_基于信息论的数据第七章_基于信息论的数据n 互信息计算n 对 A1=天气 处有：n I（天气）=H（U）-H（U|V）=0.94-0.694=0.246 bitn 类似可得：n I（气温）=0.029 bitn I（湿度）=0.151 bitn I（风）=0.048 bitn 建决策树的树根和分枝n ID3算法将选择互信息最大的特征天气作为树根，在14个例子中对天气的3个取值进行分枝，3 个分枝对应3

19、个子集，分别是:n F1=1，2，8，9，11，F2=3，7，12，13，F3=4，5，6，10，14n 其中F2中的例子全属于P类，因此对应分枝标记为P，其余两个子集既含有正例又含有反例，将递归调用建树算法。匆常口巾免奶砸搁郎特约毁紫蛰锐递冯挤孪渺跟区汰啃匪裤它达刮斌殊杠第七章_基于信息论的数据第七章_基于信息论的数据n 递归建树n 分别对F1和F3子集利用ID3算法，在每个子集中对各特征（仍为四个特征）求互信息.n （1）F1中的天气全取晴值，则H（U）=H（U|V），有I（U|V）=0，在余下三个特征中求出湿度互信息最大，以它为该分枝的根结点，再向下分枝。湿度取高的例子全为N类，该分枝标

20、记N。取值正常的例子全为P类，该分枝标记P。n （2）在F3中，对四个特征求互信息，得到风特征互信息最大，则以它为该分枝根结点。再向下分枝，风取有风时全为N类，该分枝标记N。取无风时全为P类，该分枝标记P。n 这样就得到图8.5的决策树 乞涵更荐睁军搪域凳涟氯值饰包纶狄旺抉腋欢滴侮钳刁券潭工樊驭洛致晾第七章_基于信息论的数据第七章_基于信息论的数据对对ID3的讨论的讨论n 优点n ID3在选择重要特征时利用了互信息的概念，算法的基础理论清晰，使得算法较简单，是一个很有实用价值的示例学习算法。n 该算法的计算时间是例子个数、特征个数、结点个数之积的线性函数。我们曾用4761个关于苯的质谱例子作了

21、试验。其中正例2361个，反例2400个，每个例子由500个特征描述，每个特征取值数目为6，得到一棵1514个结点的决策树。对正、反例各100个测试例作了测试，正例判对82个，反例判对80个，总预测正确率81%，效果是令人满意的。勿圭祝磅兜秉时妊粳揪遇汇戏侦险宏采扮张幼殿玻按面龙攫撰埋蒲昼炒蒂第七章_基于信息论的数据第七章_基于信息论的数据n 缺点n （1）互信息的计算依赖于特征取值的数目较多的特征，这样不太合理。一种简单的办法是对特征进行分解，如上节例中，特征取值数目不一样，可以把它们统统化为二值特征，如天气取值晴，多云，雨，可以分解为三个特征；天气晴，天气多云，天气雨。取值都为“是”或“否

22、”，对气温也可做类似的工作。这样就不存在偏向问题了。指远厄屈鸽鼎迅讨纬绢非哮之非蜡螟送茶桓侵酒瘸峙熬衅尊呀涝慢孩吮僻第七章_基于信息论的数据第七章_基于信息论的数据（2）用互信息作为特征选择量存在一个假设，即训练例子集中的正，反例的比例应与实际问题领域里正、反例比例相同。一般情况不能保证相同，这样计算训练集的互信息就有偏差。（3）ID3在建树时，每个节点仅含一个特征，是一种单变元的算法，特征间的相关性强调不够。虽然它将多个特征用一棵树连在一起，但联系还是松散的。挤韭幅幌入玛腺自打牵敦称惭冀子硬言愉斑打聪互衍务班禹且凿迭秽牲磨第七章_基于信息论的数据第七章_基于信息论的数据n （4）ID3对噪声

23、较为敏感。关于什么是噪声，Quinlan的定义是训练例子中的错误就是噪声。它包含两方面，一是特征值取错，二是类别给错。n （5）当训练集增加时，ID3的决策树会随之变化。在建树过程中，各特征的互信息会随例子的增加而改变，从而使决策树也变化。这对渐近学习（即训练例子不断增加）是不方便的。n 院崭毯铺弯赞激粕嗡伎帅染砂匹舅巩锥抵绦垫瓷柴裙阔莉圆什撅授仍诵辰第七章_基于信息论的数据第七章_基于信息论的数据 总的来说，ID3由于其理论的清晰，方法简单，学习能力较强，适于处理大规模的学习问题，在世界上广为流传，得到极大的关注，是数据挖掘和机器学习领域中的一个极好范例，也不失为一种知识获取的有用工具。描师

24、育透贾父版四吞尚钮马揖萤迂壁介抉锹干颠营撰养苑蟹幼问火纷齿句第七章_基于信息论的数据第七章_基于信息论的数据C4.5算法算法n ID3算法在数据挖掘中占有非常重要的地位。但是，在应用中，ID3算法不能够处理连续属性、计算信息增益时偏向于选择取值较多的属性等不足。C4.5是在ID3基础上发展起来的决策树生成算法，由J.R.Quinlan在1993年提出。咆苑撅吓钩掘赌宴名掇响丸左歧盾较集婆肛譬氯纵个祸笆喘裸斟爷故海岗第七章_基于信息论的数据第七章_基于信息论的数据 C4.5克服了克服了ID3在应用中存在的在应用中存在的不足，主要体现在以下几个方面：不足，主要体现在以下几个方面：（1）用信息增益率

25、来选择属性，）用信息增益率来选择属性，它克服了用信息增益它克服了用信息增益 选择属性时偏向选择取值多选择属性时偏向选择取值多的属性的不足；的属性的不足；（2）在树构造过程中或者构造完）在树构造过程中或者构造完成之后，进行剪枝；成之后，进行剪枝；（3）能够完成对连续属性的离散）能够完成对连续属性的离散化处理；化处理；（4）能够对于不完整数据的处理，）能够对于不完整数据的处理，例如未知的属性例如未知的属性 值；值；（5）C4.5采用的知识表示形式为采用的知识表示形式为决策树，并最终可以决策树，并最终可以 形成产生式规则。形成产生式规则。因脾惺鹏括仿笑农兽湾糯百革纽浆惺概辛竟粗哟推呢噪犬馅晃齿漾悬晕

26、呕第七章_基于信息论的数据第七章_基于信息论的数据C4.5构造决策树的算法构造决策树的算法n 设T为数据集，类别集合为C1,C2,Ck，选择一个属性V把T分为多个子集。设V有互不重合的n个取值v1,v2,vn，则T被分为n个子集T1,T2,Tn，这里Ti中的所有实例的取值均为vi。n 令：|T|为数据集T的例子数，|Ti|为v=vi的例子数，|Cj|=freq(Cj,T)，为Cj类的例子数，|Cjv|是V=vi例子中，具有Cj类别例子数。虹瞪钩团票芽蜜驰枣鲁酱跺急那卢嗜适佃料魄榔勃社兜冶帛绷证乔揣死丈第七章_基于信息论的数据第七章_基于信息论的数据则有：（1）类别Cj的发生概率：p(Cj)=|

27、Cj|/|T|=freq(Cj,T)/|T|（2）属性V=vi的发生概率：p(vi)=|Ti|/|T|（3）属性V=vi的例子中，具有类别Cj的条件概率：p(Cj|vi)=|Cjv|/|Ti|Quinlan在ID3中使用信息论中的信息增益（gain）来选择属性，而C4.5采用属性的信息增益率（gain ratio）来选择属性。娜圣每啡筏削顶痴盎萍残烤锚叮鞠台密嵌超鸵踪坐皮佑秸睬陷尽绷颇动册第七章_基于信息论的数据第七章_基于信息论的数据n(1)类别的信息熵n(2)类别条件熵n按照属性V把集合T分割，分割后的类别条件熵为：笺裂埋卖牛簧徘嗡杠隧辆伙贺风泼撅腔署敲惩嘲诣进论仟兑路骸磊跪输讲第七章_基

28、于信息论的数据第七章_基于信息论的数据n(3)信息增益（gain），即互信息n(4)属性V的信息熵n(5)信息增益率nC4.5对ID3改进是用信息增益率来选择属性。n理论和实验表明，采用“信息增益率”（C4.5方法）比采用“信息增益”（ID3方法）更好，主要是克服了ID3方法选择偏向取值多的属性。侍迅亡茵哦毯掠昧醋端革苛边笼吹心燕大扯舆咕椎凝膨歹通企组承抚卖炭第七章_基于信息论的数据第七章_基于信息论的数据n2、连续属性的处理n 在ID3 中没有处理连续属性的功能。在C4.5中，设在集合T中，连续属性A的取值为v1,v2,vm，则任何在vi和vi+1之间的任意取值都可以把实例集合分为两部分T1

29、=t|A vi，可以看到一共有m-1种分割情况。n 对属性A的m-1种分割的任意一种情况，作为该属性的两个离散取值，重新构造该属性的离散值，再按照上述公式计算每种分割所对应的信息增益率gain_ratio(vi)，在m-1中分割中，选择最大增益率的分割作为属性A的分枝：懒灵邻呼诵隔爷啸粗业洛宣思献绊仿寝斜砰料神喀施柱税挣靶意耐帛燕芋第七章_基于信息论的数据第七章_基于信息论的数据n Threshold(V)=vk n 其中，gain_ratio(vk)=max gain_ratio(vi)n 则连续属性A可以分割为：AA Threshold(V)捡汲捷牧得勤借稼捡羽壹僵汐师嘶墅盅挽祥扦寿无愿捐

30、诽腰悉阿牡慷兹黍第七章_基于信息论的数据第七章_基于信息论的数据n3、决策树剪枝n 由于噪声和随机因素的影响，上述树一般会很复杂。因此需要进行剪枝操作。n(1)什么时候剪枝？n 有两种剪枝策略：（1）在树生成过程中判断是否还继续扩展决策树。若停止扩展，则相当于剪去该结点以下的分枝。（2）对于生成好的树剪去某些结点和分枝。C4.5采用第二种方法。n 剪枝之后的决策树的叶结点不再只包含一类实例。结点有一个类分布描述，即该叶结点属于某类的概率。僳深跋言厚泛裴对熙臃骡幅腻恢久泊蒸纸纫袜珊眺彦蔑拆篓迫俐零技腹肤第七章_基于信息论的数据第七章_基于信息论的数据(2)基于误差的剪枝 决策树的剪枝通常是用叶结

31、点替代一个或者多个子树，然后选择出现概率最高的类作为该结点的类别。在C4.5中，还允许用其中的树枝来替代子树。如果使用叶结点或者树枝代替原来的子树之后，误差率若能够下降，则使用此叶结点或者树枝代替原来的子树。玄捷恬斩洞缺赘搓顾囊狱梢蔓阴杆旅愁答匡闯痈月蟹氨纫辫无钻眷惰抓颁第七章_基于信息论的数据第七章_基于信息论的数据n4、从决策树抽取规则n在C4.5中，从决策树抽取规则需要两个步骤：获得简单规则、精简规则属性。n对于生成好的决策树，我们可以直接从获得规则。从根到叶的每一条路经都可以是一条规则。例如，从下面的决策树中我们可以得到规则：头朝倒壳骄奢布潭这会楞仁鸭秘事葛勾茸厄绷弟郎绷夕躇屑慰迹容捡坞锡第七章_基于信息论的数据第七章_基于信息论的数据F=0J=0:Class0J=1K=0:Class0K=1:Class1F=1G=1:Class1G=0J=0:Class0J=1K=0:Class0K=1:Class1决策树：规则：IF F=1,G=0,J=1,K=1 THEN class1搓鲤虱钵竖抨槐劳纳匿碰橱幼盅疟屏邮几狰窥隅入斡褪桂嚼护麓讼蜘吩畔第七章_基于信息论的数据第七章_基于信息论的数据结束砍责野抛闭央患得蜒烩逊诧转剖谆慰脯雷甚千艰绘愤耘矩哼侯十郸溢签孺第七章_基于信息论的数据第七章_基于信息论的数据