决策树、信息论、ID3、C45算法课件

C4.5算法讲解2012.11.29C4.5算法讲解2012.11.291C4.5算法ID3算法知识结构决策树基础信息论基础C4.5算法ID3算法知识结构决策树基础信息论基础2决策树基础女孩家长安排相亲女孩不厌其烦女孩提出决策树父母筛选候选男士决策树基础女孩家长3决策树基础有向无环二叉/多叉树父节点：没有子节点的节点内部节点：有父节点、子节点的节点叶节点：有父节点没有子节点的节点父节点内部节点叶节点分割属性+判断规则类别标识决策树基础有向无环二叉/多叉树父节点叶节点分割属性+判断4决策树基础父节点内部节点叶节点（类别标识）（分割属性+判断规则）决策树基础父节点叶节点（分割属性+判断规则）5决策树基础训练集：数据的集合，用于生成树（模型）测试集：用于测试树（模型）的性能决策树作用：通过训练集算法指导下生成决策树新数据进行划分否则是“三拍”决策训练集算法决策树新数据决策决策树基础训练集：数据的集合，用于生成树（模型）训练集算法决6决策树基础实例No.头痛肌肉痛体温患流感1是(1)是(1)正常(0)N(0)2是(1)是(1)高(1)Y(1)3是(1)是(1)很高(2)Y(1)4否(0)是(1)正常(0)N(0)5否(0)否(0)高(1)N(0)6否(0)是(1)很高(2)N(1)7是(1)否(0)高(1)Y(1)决策树怎么做？谁是父节点？谁是下一层子节点？为什么是它？头-肌肉-体温头-体温-肌肉肌肉-头-体温肌肉-体温-头体温-头-肌肉体温-肌肉-头三拍决策决策树基础实例No.头痛肌肉痛体温患流感1是(1)是(1)7决策树基础……@）￥——JK)I*&^Fkl9*^&%*&UIDOFGJNo.天气气温湿度风类别1晴热高无N2晴热高有N3多云热高无P4雨适中高无P5雨冷正常无P6雨冷正常有N7多云冷正常有PNo.天气气温湿度风类别8晴适中高无N9晴冷正常无P10雨适中正常无P11晴适中正常有P12多云适中高有P13多云热正常无P14雨适中高有N决策树基础……@）￥——JK)I*&^Fkl9*^&%*&8怎么生成好的？哪个好？种决策树方案决策树基础N个分割属性的训练集怎么生成好的？哪个好？种决策9决策树基础好的决策树：（MDL准则下为例）MinimumDescriptionLength训练集中大多数数据符合这棵树例外的数据单独编码描述决策树用的bit描述例外数据用bit哪个好？决策树基础描述决策树用的bit描述例外数据用bit哪个好？10决策树基础（选择掌握）如何描述决策树体温头痛很高正常高YNYN否是流感决策树深度优先遍历决策树用1标注父子节点用0标注叶节点记录分割属性1,体温,0,Y,1,头疼,0,Y,0,N,0,N层次少+分枝少占用存储空间小决策计算时间快决策树基础（选择掌握）如何描述决策树体温头痛很高正常高YNY11决策树基础C4.5算法ID3算法决策树基础信息论基础选哪个？？怎么生成好的？NextOne!决策树基础C4.5算法ID3算法决策树基础信息论基础选哪个？12信息论基础辨析先验概率信息量信息论基础辨析13信息论基础—先验概率对事件X的某一结果进行讨论：例：在没有任何帮助的情况下，奥/罗谁赢的概率P（x1=奥）=P（x2=罗）信息论基础—先验概率对事件X的某一结果进行讨论：14信息论基础—信息量信息论基础—信息量15信息论基础辨析先验概率信息量先验熵信息论基础辨析16信息论基础先验熵——自信息量——熵H（X）原意：热力学中形容失序现象和复杂程度现意：一个事件X的平均信息量熵越大，不确定性就越大，正确估计其值的可能性就越小。XXX熵===XXX的信息量的加权信息论基础先验熵——自信息量——熵H（X）17信息论基础先验熵——自信息量——熵H（X）原意：热力学中形容失序现象和复杂程度现意：通信中一个事件的平均信息量信息论基础先验熵——自信息量——熵H（X）18信息论基础熵H(X)——自信息量科学发展观指导下的和谐社会，失序现象和复杂程度远低于万恶的资本主义社会！事件的可能结果发生几率越相近，则熵越大信息论基础熵H(X)——自信息量19信息论基础辨析先验概率信息量先验熵后验概率信息论基础辨析20信息论基础对事件X的某一结果进行讨论：例：已知民意调查结果，猜奥/罗谁赢的概率P（x1=奥|y1=奥领先）>P（x2=罗|y1=奥领先）信息论基础对事件X的某一结果进行讨论：21信息论基础辨析先验概率信息量先验熵后验概率后验熵信息论基础辨析22信息论基础熵H(X)原意：热力学中形容失序现象和复杂程度现意：一个事件X的平均信息量熵越大，不确定性就越大，正确估计其值的可能性就越小。XXX熵===XXX的信息量的加权后验熵=后验概率的信息量的加权信息论基础熵H(X)23信息论基础对事件X的全部结果在某一辅助条件下进行讨论：信息论基础对事件X的全部结果在某一辅助条件下进行讨论：24信息论基础对事件X的全部结果在某一辅助条件下进行讨论：例：在民意调查的结果帮助下（y1）计算2012年谁是总统的不确定性H(谁当选|民调奥领先)=？信息论基础对事件X的全部结果在某一辅助条件下进行讨论：25信息论基础辨析先验概率信息量熵=自信息量后验概率后验墒条件熵信息论基础辨析26信息论基础对事件X的全部结果在全部辅助条件下进行讨论：信息论基础对事件X的全部结果在全部辅助条件下进行讨论：27信息论基础条件熵即对后验墒的所有可能辅助条件Yj累计信息论基础条件熵28信息论基础辨析先验概率信息量熵=自信息量后验概率后验墒条件熵信息论基础辨析29信息论基础辨析信息量熵=自信息量先验概率后验概率后验墒条件熵互信息量信息论基础辨析30信息论基础对于条件墒H(X|Y)由于辅助条件Y的存在由熵——不确定程度——事件X的平均信息量所以一般情况下H(X)=<H(X|Y)I(X|Y)=H(X)-H(X|Y)信息论基础对于条件墒H(X|Y)31信息论基础信息论基础32信息论基础因此定义互信息量I(X,Y)——信息增益I(X,Y)信息增益才是接收端获得的信息量我没收到任何东西前，我不知道你发了是什么我收到了一些东西后，才有机会猜你到底发了什么信息论基础因此定义互信息量I(X,Y)——信息增益33信息论基础互信息量I(X,Y)的物理含义H(X)事件X的结果的不确定性H(X|Y)事件X在辅助条件Y下的结果的不确定性H(X)-H(X|Y)辅助条件Y对事件X的结果的不确定性的消除——信息增益ID3和C4.5算法就基于以上信息论基础互信息量I(X,Y)的物理含义ID3和C4.5算法34ID3算法互信息量I(X,Y)的物理含义辅助条件Y消除了事件X多少的不确定性ID3算法IterativeDichotomiser迭代二分器（为什么？）使用互信息量作为度量标准选择当前所有分割属性中，互信息量最大的作为内部节点ID3算法互信息量I(X,Y)的物理含义35ID3算法ID3算法使用互信息量作为度量标准选择当前所有分割属性中，互信息量最大的作为内部节点——最能消除不确定性的分割属性生活工作中的决策（做？不做？）总是优先选取最具有决定性意义的辅助条件进行判定如—打不打室外羽毛球？刮风是最具有决定意义的因素ID3算法ID3算法生活工作中的决策（做？不做？）36ID3算法ID3算法互信息量最大No.头痛肌肉痛体温患流感1是(1)是(1)正常(0)N(0)2是(1)是(1)高(1)Y(1)3是(1)是(1)很高(2)Y(1)4否(0)是(1)正常(0)N(0)5否(0)否(0)高(1)N(0)6否(0)是(1)很高(2)Y(1)7是(1)否(0)高(1)Y(1)决策树怎么做？谁是父节点？谁是下一层子节点？为什么是它？头-肌肉-体温头-体温-肌肉肌肉-头-体温肌肉-体温-头体温-头-肌肉体温-肌肉-头ID3算法ID3算法No.头痛肌肉痛体温患流感1是(1)是37例题中各数据的属性及其取值分别为：类别（事件X）：是、否；——x1，x2分割属性Y1头痛：是、否；分割属性Y2肌肉痛：是、否；分割属性Y3体温：很高、高、正常选择全部数据记录，求先验熵（对类别）：P(x1)=4/7，P(x2)=3/7H(X)=-∑i=1,2P(xi)log2P(xi)=0.985bit后验熵（对Y1）：y1=是，y2=否P(y1)=4/7，P(y2)=3/7P(x1|y1)=3/4，P(x2|y1)=1/4H(X|y1)=-∑i=1,2P(xi|y1)log2P(xi|y1)=0.811同理，H(X|y2)=0.918ID3算法例题中各数据的属性及其取值分别为：ID3算法38条件熵（对Y1）：H(X|Y1)=∑j=1,2,3

P(yj)H(X|yj)=0.857互信息（对Y1）：I(X,Y1)=H(X)-H(X|Y1)=0.128同理，有：I(X,Y2)=0.006，I(X,Y3)=0.592I(X,Y3)值最大，所以选择“体温”作为决策树的根节点，将其三个取值分别作为三个分支，并划分原数据集合为三个子集判断子集中各记录是否属于同一类别，若是则在树上作标记，否则对子集重复上述步骤ID3算法条件熵（对Y1）：ID3算法39ID3算法（选择掌握）兴趣题~~使用ID3算法构建“天气-外出”决策树

No.天气气温湿度风类别1晴热高无N2晴热高有N3多云热高无P4雨适中高无P5雨冷正常无P6雨冷正常有N7多云冷正常有PNo.天气气温湿度风类别8晴适中高无N9晴冷正常无P10雨适中正常无P11晴适中正常有P12多云适中高有P13多云热正常无P14雨适中高有NID3算法（选择掌握）兴趣题~~使用ID3算法构建“天气40例题中各数据的属性及其取值分别为：类别：P、N；——u1、u2天气A1：晴、多云、雨；气温A2：冷、适中、热；湿度A3

：高、正常；风A4

：有、无选择全部数据记录，求先验熵（对类别）：P(u1)=9/14，P(u2)=5/14H(U)=-∑i=1,2P(ui)log2P(ui)=0.94bit后验熵（对A1）：v1=晴，v2=多云，v3=雨P(v1)=5/14，P(v2)=4/14，P(v3)=5/14P(u1|v1)=2/5，P(u2|v1)=3/5H(U|v1)=-∑i=1,2P(ui|v1)log2P(ui|v1)=0.97同理，H(U|v2)=0，H(U|v3)=0.97ID3算法（选择掌握）例题中各数据的属性及其取值分别为：ID3算法（选择掌握）41条件熵（对A1）：H(U|V)=∑j=1,2,3

P(vj)H(U|vj)=0.69互信息（对A1）：I(A1)=H(U)-H(U|V)=0.25同理，有：I(A2)=0.03，I(A3)=0.15，I(A4)=0.05I(A1)值最大，所以选择“天气”作为决策树的根节点，将其三个取值分别作为三个分支，并划分原数据集合为三个子集判断子集中各记录是否属于同一类别，若是则在树上作标记，否则对子集重复上述步骤ID3算法（选择掌握）条件熵（对A1）：ID3算法（选择掌握）42ID3算法每个名字都有它的意义御手洗！@#@！#￥&&￥#……Fox电影公司=狐狸电影公司Paramount电影公司=最牛的电影公司美国总统Bush=美国总统灌木丛ID3为什么是IterativeDichotomiser迭代二分器ID3算法每个名字都有它的意义43ID3算法Iterative（迭代）当前的输出结果会返回到程序开始作自变量。

Dichotomiser（二分器）ID3算出的决策树的“类别”只有“是”、“否”如“流感”决策树W=F(X,Y,Z)XYZWID3算法Iterative（迭代）W=F(X,Y,Z)XY44ID3算法:主算法从训练集中随机选择一个既含正例(Y)又含反例(N)的子集（称为“窗口”）；用“建树算法”对当前窗口形成一棵决策树；对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；若存在错判的例子，把它们插入窗口，重复步骤（2），否则结束。ID3算法:主算法45ID3算法:建树算法自顶向下：从父节点开始，逐层向下贪心：例如“100个数，挑出5个很小的数”贪心法在每层总取互信息量最小的属性但不保证整个决策树是最优的如果各属性彼此独立则最优如果有相关性，可能非最优递归：一个程序在过程中有调用自身将大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解ID3算法:建树算法自顶向下：46ID3算法:建树算法对窗口的所有分割属性，计算各自的互信息量；选择互信息最大的特征Ak，作为内部节点把在Ak处取值相同的属性归于同一子集，将当前表格的行划分成不同的子集；判断子集，若各子集中类别属性相同，则在决策树上作相应类别标记，并返回否则将子集作为1)中的窗口，进行迭代计算。当全部子集类别属性均为相同时，则停止建树。此时形成二分的决策树，即只有两个可能结果ID3算法:建树算法47ID3算法（选择掌握）ID3算法用编程语言的实现网络链接：/view/66ac453a376baf1ffc4fad66.html本机文件：数据挖掘中ID3算法实现.txtID3算法（选择掌握）ID3算法用编程语言的实现48ID3算法优点算法简单易于理解缺点偏向分割属性中取值多的一个只能处理离散属性ID3不包括树剪枝，易受噪声和波动影响不宜对变化的数据集进行学习ID3算法优点缺点49C4.5算法ID3缺点1：偏向分割属性中取值较多的一个原因：分割属性取值越多，每个值对应的子集规模越小。极限情况下，每个子集内如只有一个单元（表格中的行），则它的信息增益必然最高（对不确定性的消除达到最大）。例如用“身份证号”区分“相亲”，显然没有任何意义，但是确实符合ID3算法。解决方法：引入增益比例C4.5算法ID3缺点1：偏向分割属性中取值较多的一个50C4.5算法对分割属性Y计算熵此熵与样本类别无关（公式中没有X）此公式衡量了分割属性Y的均匀性回忆（习薄）和（奥罗）例子分布越均匀H(Y)越大，反之越小4份2、2分，4份1、1、1、1分4份1、3分，4份1、1、2分的H（Y）C4.5算法对分割属性Y计算熵51C4.5算法（不科学的证明）4份不分H(Y)=04份1、3分H(Y)=0.414份2、2分H(Y)=14份1、1、2分H（Y）=1.54份1、1、1、1分H(Y)=2份数越多，H(Y)月大份数一样的前提下，越平均H(Y)越大C4.5算法（不科学的证明）4份不分H(Y)=052C4.5算法增益比例G(X,Y)对类别X和分裂属性Y计算G(X,Y)ID3用信息增量I（X|Y）选择节点分割属性C4.5用增益比例选择节点分裂属性C4.5通过引入分母H(Y)，解决了ID3的最大问题，即偏向分割属性中取值较多的一个属性的问题C4.5算法增益比例G(X,Y)C4.5通过引入分母H(Y)53C4.5算法考虑“相亲”中的身份证例子在ID3中，分割属性取值越多，每个值对应的子集规模越小。信息增益极大几率增高。所以ID3产生了偏向性。在C4.5中，如果分割属性取值很大，则C4.5算法考虑“相亲”中的身份证例子54C4.5算法还有缺陷：C4.5算法还有缺陷：55C4.5算法解决方法：先计算所有的信息增益I（X|Y）对于超过I(X|Y)均值，进一步考量H（Y），选取H（Y）最大的这样保证相对大C4.5算法解决方法：56排除H(Yi)=0的可能因为H(Yi)=0时Yi分布及其不均匀则I(X|Y)=0排除H(Yi)为身份证可能此时H(Yi)很大G(X|Y)很小排除H(Yi)=0的可能排除H(Yi)为身份证可能57C4.5算法ID3缺点2：只能处理离散分割属性原因：对于连续属性，和缺点1类似。如果把连续值看成离散值，则会产生分割属性的偏向问题。解决方法：引入“阈值”。将分割属性化为C4.5算法ID3缺点2：只能处理离散分割属性58C4.5算法问题：对于连续取值的分割属性，阈值=？方法：在表格中连续值分割属性取值对每个计算增益比例，找到最大值即可C4.5算法问题：对于连续取值的分割属性，阈值=？59C4.5算法ID3缺点3：无法对未知分割属性进行处理原因：某分割属性Y的一个取值由于一些原因未被计入解决方法：平均值代替 概率法代替C4.5算法ID3缺点3：无法对未知分割属性进行处理60C4.5算法决策树IF-THEN规则编程IF年龄>30THEN不见IF年龄<=30AND长相=丑THEN不见IF年龄<=30AND长相=帅or中等AND收入=高THEN见IF年龄<=30AND长相=帅or中等AND收入=中等AND公务员=是THEN见IF年龄<=30AND长相=帅or中等AND收入=中等AND公务员=不是THEN不见IF年龄<=30AND长相=帅or中等AND收入=低THEN不见C4.5算法决策树IF-THEN61C4.5算法ID3缺点3：无树剪枝，易受噪声和波动影响解决方法：K阶交叉验证C4.5算法ID3缺点3：无树剪枝，易受噪声和波动影响62C4.5算法数据集(一组表格)子集1子集2子集3子集4子集5子集6子集7子集8C4.5决策树1用于生成树用于验证K=8的8阶交叉验证错误数1C4.5算法数据集子集1子集2子集3子集4子集5子集6子集763C4.5算法数据集(一组表格)子集2子集1子集3子集4子集5子集6子集7子集8C4.5决策树2用于生成树用于验证K=8的8阶交叉验证错误数2C4.5算法数据集子集2子集1子集3子集4子集5子集6子集764C4.5算法数据集(一组表格)子集3子集1子集2子集4子集5子集6子集7子集8C4.5决策树3用于生成树用于验证K=8的8阶交叉验证错误数3C4.5算法数据集子集3子集1子集2子集4子集5子集6子集765C4.5算法数据集(一组表格)子集4子集1子集2子集3子集5子集6子集7子集8C4.5决策树4用于生成树用于验证K=8的8阶交叉验证错误数4C4.5算法数据集子集4子集1子集2子集3子集5子集6子集766C4.5算法数据集(一组表格)子集5子集1子集2子集3子集4子集6子集7子集8C4.5决策树5用于生成树用于验证K=8的8阶交叉验证错误数5C4.5算法数据集子集5子集1子集2子集3子集4子集6子集767C4.5算法数据集(一组表格)子集6子集1子集2子集3子集4子集5子集7子集8C4.5决策树6用于生成树用于验证K=8的8阶交叉验证错误数6C4.5算法数据集子集6子集1子集2子集3子集4子集5子集768C4.5算法数据集(一组表格)子集7子集1子集2子集3子集4子集5子集6子集8C4.5决策树7用于生成树用于验证K=8的8阶交叉验证错误数7C4.5算法数据集子集7子集1子集2子集3子集4子集5子集669C4.5算法数据集(一组表格)子集8子集1子集2子集3子集4子集5子集6子集7C4.5决策树8用于生成树用于验证K=8的8阶交叉验证错误数8C4.5算法数据集子集8子集1子集2子集3子集4子集5子集670C4.5算法树1错1树2错2树3错3树4错4树5错5树6错6树7错7树8错8决策树最终版仅用于小规模数据…C4.5算法树1错1树2错2树3错3树4错4树5错5树6错671C4.5算法（选择掌握）C4.5算法用C语言的实现网络链接：/view/4c7d8f82e53a580216fcfe61.html本机文件：C4.5算法的实现.docC4.5算法（选择掌握）C4.5算法用C语言的实现72参考文献/guoqiangma/article/details/7188639/view/298415.htm/view/96473.htm/view/8be6aa18c5da50e2524d7fb2.html/view/589872.htm/yaoyaozii/article/details/5278576参考文献/guoqi73参考文献参考文献74参考文献/view/66ac453a376baf1ffc4fad66.html参考文献/vie75参考文献《数据挖掘原理与算法》科学出版社邵峰晶等编著；《数据挖掘算法与应用》北京大学出版社梁循编著《现代通信原理》清华大学出版社曹志刚等编著参考文献《数据挖掘原理与算法》科学出版社邵峰晶等编著；76C4.5算法讲解2012.11.29C4.5算法讲解2012.11.2977C4.5算法ID3算法知识结构决策树基础信息论基础C4.5算法ID3算法知识结构决策树基础信息论基础78决策树基础女孩家长安排相亲女孩不厌其烦女孩提出决策树父母筛选候选男士决策树基础女孩家长79决策树基础有向无环二叉/多叉树父节点：没有子节点的节点内部节点：有父节点、子节点的节点叶节点：有父节点没有子节点的节点父节点内部节点叶节点分割属性+判断规则类别标识决策树基础有向无环二叉/多叉树父节点叶节点分割属性+判断80决策树基础父节点内部节点叶节点（类别标识）（分割属性+判断规则）决策树基础父节点叶节点（分割属性+判断规则）81决策树基础训练集：数据的集合，用于生成树（模型）测试集：用于测试树（模型）的性能决策树作用：通过训练集算法指导下生成决策树新数据进行划分否则是“三拍”决策训练集算法决策树新数据决策决策树基础训练集：数据的集合，用于生成树（模型）训练集算法决82决策树基础实例No.头痛肌肉痛体温患流感1是(1)是(1)正常(0)N(0)2是(1)是(1)高(1)Y(1)3是(1)是(1)很高(2)Y(1)4否(0)是(1)正常(0)N(0)5否(0)否(0)高(1)N(0)6否(0)是(1)很高(2)N(1)7是(1)否(0)高(1)Y(1)决策树怎么做？谁是父节点？谁是下一层子节点？为什么是它？头-肌肉-体温头-体温-肌肉肌肉-头-体温肌肉-体温-头体温-头-肌肉体温-肌肉-头三拍决策决策树基础实例No.头痛肌肉痛体温患流感1是(1)是(1)83决策树基础……@）￥——JK)I*&^Fkl9*^&%*&UIDOFGJNo.天气气温湿度风类别1晴热高无N2晴热高有N3多云热高无P4雨适中高无P5雨冷正常无P6雨冷正常有N7多云冷正常有PNo.天气气温湿度风类别8晴适中高无N9晴冷正常无P10雨适中正常无P11晴适中正常有P12多云适中高有P13多云热正常无P14雨适中高有N决策树基础……@）￥——JK)I*&^Fkl9*^&%*&84怎么生成好的？哪个好？种决策树方案决策树基础N个分割属性的训练集怎么生成好的？哪个好？种决策85决策树基础好的决策树：（MDL准则下为例）MinimumDescriptionLength训练集中大多数数据符合这棵树例外的数据单独编码描述决策树用的bit描述例外数据用bit哪个好？决策树基础描述决策树用的bit描述例外数据用bit哪个好？86决策树基础（选择掌握）如何描述决策树体温头痛很高正常高YNYN否是流感决策树深度优先遍历决策树用1标注父子节点用0标注叶节点记录分割属性1,体温,0,Y,1,头疼,0,Y,0,N,0,N层次少+分枝少占用存储空间小决策计算时间快决策树基础（选择掌握）如何描述决策树体温头痛很高正常高YNY87决策树基础C4.5算法ID3算法决策树基础信息论基础选哪个？？怎么生成好的？NextOne!决策树基础C4.5算法ID3算法决策树基础信息论基础选哪个？88信息论基础辨析先验概率信息量信息论基础辨析89信息论基础—先验概率对事件X的某一结果进行讨论：例：在没有任何帮助的情况下，奥/罗谁赢的概率P（x1=奥）=P（x2=罗）信息论基础—先验概率对事件X的某一结果进行讨论：90信息论基础—信息量信息论基础—信息量91信息论基础辨析先验概率信息量先验熵信息论基础辨析92信息论基础先验熵——自信息量——熵H（X）原意：热力学中形容失序现象和复杂程度现意：一个事件X的平均信息量熵越大，不确定性就越大，正确估计其值的可能性就越小。XXX熵===XXX的信息量的加权信息论基础先验熵——自信息量——熵H（X）93信息论基础先验熵——自信息量——熵H（X）原意：热力学中形容失序现象和复杂程度现意：通信中一个事件的平均信息量信息论基础先验熵——自信息量——熵H（X）94信息论基础熵H(X)——自信息量科学发展观指导下的和谐社会，失序现象和复杂程度远低于万恶的资本主义社会！事件的可能结果发生几率越相近，则熵越大信息论基础熵H(X)——自信息量95信息论基础辨析先验概率信息量先验熵后验概率信息论基础辨析96信息论基础对事件X的某一结果进行讨论：例：已知民意调查结果，猜奥/罗谁赢的概率P（x1=奥|y1=奥领先）>P（x2=罗|y1=奥领先）信息论基础对事件X的某一结果进行讨论：97信息论基础辨析先验概率信息量先验熵后验概率后验熵信息论基础辨析98信息论基础熵H(X)原意：热力学中形容失序现象和复杂程度现意：一个事件X的平均信息量熵越大，不确定性就越大，正确估计其值的可能性就越小。XXX熵===XXX的信息量的加权后验熵=后验概率的信息量的加权信息论基础熵H(X)99信息论基础对事件X的全部结果在某一辅助条件下进行讨论：信息论基础对事件X的全部结果在某一辅助条件下进行讨论：100信息论基础对事件X的全部结果在某一辅助条件下进行讨论：例：在民意调查的结果帮助下（y1）计算2012年谁是总统的不确定性H(谁当选|民调奥领先)=？信息论基础对事件X的全部结果在某一辅助条件下进行讨论：101信息论基础辨析先验概率信息量熵=自信息量后验概率后验墒条件熵信息论基础辨析102信息论基础对事件X的全部结果在全部辅助条件下进行讨论：信息论基础对事件X的全部结果在全部辅助条件下进行讨论：103信息论基础条件熵即对后验墒的所有可能辅助条件Yj累计信息论基础条件熵104信息论基础辨析先验概率信息量熵=自信息量后验概率后验墒条件熵信息论基础辨析105信息论基础辨析信息量熵=自信息量先验概率后验概率后验墒条件熵互信息量信息论基础辨析106信息论基础对于条件墒H(X|Y)由于辅助条件Y的存在由熵——不确定程度——事件X的平均信息量所以一般情况下H(X)=<H(X|Y)I(X|Y)=H(X)-H(X|Y)信息论基础对于条件墒H(X|Y)107信息论基础信息论基础108信息论基础因此定义互信息量I(X,Y)——信息增益I(X,Y)信息增益才是接收端获得的信息量我没收到任何东西前，我不知道你发了是什么我收到了一些东西后，才有机会猜你到底发了什么信息论基础因此定义互信息量I(X,Y)——信息增益109信息论基础互信息量I(X,Y)的物理含义H(X)事件X的结果的不确定性H(X|Y)事件X在辅助条件Y下的结果的不确定性H(X)-H(X|Y)辅助条件Y对事件X的结果的不确定性的消除——信息增益ID3和C4.5算法就基于以上信息论基础互信息量I(X,Y)的物理含义ID3和C4.5算法110ID3算法互信息量I(X,Y)的物理含义辅助条件Y消除了事件X多少的不确定性ID3算法IterativeDichotomiser迭代二分器（为什么？）使用互信息量作为度量标准选择当前所有分割属性中，互信息量最大的作为内部节点ID3算法互信息量I(X,Y)的物理含义111ID3算法ID3算法使用互信息量作为度量标准选择当前所有分割属性中，互信息量最大的作为内部节点——最能消除不确定性的分割属性生活工作中的决策（做？不做？）总是优先选取最具有决定性意义的辅助条件进行判定如—打不打室外羽毛球？刮风是最具有决定意义的因素ID3算法ID3算法生活工作中的决策（做？不做？）112ID3算法ID3算法互信息量最大No.头痛肌肉痛体温患流感1是(1)是(1)正常(0)N(0)2是(1)是(1)高(1)Y(1)3是(1)是(1)很高(2)Y(1)4否(0)是(1)正常(0)N(0)5否(0)否(0)高(1)N(0)6否(0)是(1)很高(2)Y(1)7是(1)否(0)高(1)Y(1)决策树怎么做？谁是父节点？谁是下一层子节点？为什么是它？头-肌肉-体温头-体温-肌肉肌肉-头-体温肌肉-体温-头体温-头-肌肉体温-肌肉-头ID3算法ID3算法No.头痛肌肉痛体温患流感1是(1)是113例题中各数据的属性及其取值分别为：类别（事件X）：是、否；——x1，x2分割属性Y1头痛：是、否；分割属性Y2肌肉痛：是、否；分割属性Y3体温：很高、高、正常选择全部数据记录，求先验熵（对类别）：P(x1)=4/7，P(x2)=3/7H(X)=-∑i=1,2P(xi)log2P(xi)=0.985bit后验熵（对Y1）：y1=是，y2=否P(y1)=4/7，P(y2)=3/7P(x1|y1)=3/4，P(x2|y1)=1/4H(X|y1)=-∑i=1,2P(xi|y1)log2P(xi|y1)=0.811同理，H(X|y2)=0.918ID3算法例题中各数据的属性及其取值分别为：ID3算法114条件熵（对Y1）：H(X|Y1)=∑j=1,2,3

P(yj)H(X|yj)=0.857互信息（对Y1）：I(X,Y1)=H(X)-H(X|Y1)=0.128同理，有：I(X,Y2)=0.006，I(X,Y3)=0.592I(X,Y3)值最大，所以选择“体温”作为决策树的根节点，将其三个取值分别作为三个分支，并划分原数据集合为三个子集判断子集中各记录是否属于同一类别，若是则在树上作标记，否则对子集重复上述步骤ID3算法条件熵（对Y1）：ID3算法115ID3算法（选择掌握）兴趣题~~使用ID3算法构建“天气-外出”决策树

No.天气气温湿度风类别1晴热高无N2晴热高有N3多云热高无P4雨适中高无P5雨冷正常无P6雨冷正常有N7多云冷正常有PNo.天气气温湿度风类别8晴适中高无N9晴冷正常无P10雨适中正常无P11晴适中正常有P12多云适中高有P13多云热正常无P14雨适中高有NID3算法（选择掌握）兴趣题~~使用ID3算法构建“天气116例题中各数据的属性及其取值分别为：类别：P、N；——u1、u2天气A1：晴、多云、雨；气温A2：冷、适中、热；湿度A3

：高、正常；风A4

：有、无选择全部数据记录，求先验熵（对类别）：P(u1)=9/14，P(u2)=5/14H(U)=-∑i=1,2P(ui)log2P(ui)=0.94bit后验熵（对A1）：v1=晴，v2=多云，v3=雨P(v1)=5/14，P(v2)=4/14，P(v3)=5/14P(u1|v1)=2/5，P(u2|v1)=3/5H(U|v1)=-∑i=1,2P(ui|v1)log2P(ui|v1)=0.97同理，H(U|v2)=0，H(U|v3)=0.97ID3算法（选择掌握）例题中各数据的属性及其取值分别为：ID3算法（选择掌握）117条件熵（对A1）：H(U|V)=∑j=1,2,3

P(vj)H(U|vj)=0.69互信息（对A1）：I(A1)=H(U)-H(U|V)=0.25同理，有：I(A2)=0.03，I(A3)=0.15，I(A4)=0.05I(A1)值最大，所以选择“天气”作为决策树的根节点，将其三个取值分别作为三个分支，并划分原数据集合为三个子集判断子集中各记录是否属于同一类别，若是则在树上作标记，否则对子集重复上述步骤ID3算法（选择掌握）条件熵（对A1）：ID3算法（选择掌握）118ID3算法每个名字都有它的意义御手洗！@#@！#￥&&￥#……Fox电影公司=狐狸电影公司Paramount电影公司=最牛的电影公司美国总统Bush=美国总统灌木丛ID3为什么是IterativeDichotomiser迭代二分器ID3算法每个名字都有它的意义119ID3算法Iterative（迭代）当前的输出结果会返回到程序开始作自变量。

Dichotomiser（二分器）ID3算出的决策树的“类别”只有“是”、“否”如“流感”决策树W=F(X,Y,Z)XYZWID3算法Iterative（迭代）W=F(X,Y,Z)XY120ID3算法:主算法从训练集中随机选择一个既含正例(Y)又含反例(N)的子集（称为“窗口”）；用“建树算法”对当前窗口形成一棵决策树；对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子；若存在错判的例子，把它们插入窗口，重复步骤（2），否则结束。ID3算法:主算法121ID3算法:建树算法自顶向下：从父节点开始，逐层向下贪心：例如“100个数，挑出5个很小的数”贪心法在每层总取互信息量最小的属性但不保证整个决策树是最优的如果各属性彼此独立则最优如果有相关性，可能非最优递归：一个程序在过程中有调用自身将大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解ID3算法:建树算法自顶向下：122ID3算法:建树算法对窗口的所有分割属性，计算各自的互信息量；选择互信息最大的特征Ak，作为内部节点把在Ak处取值相同的属性归于同一子集，将当前表格的行划分成不同的子集；判断子集，若各子集中类别属性相同，则在决策树上作相应类别标记，并返回否则将子集作为1)中的窗口，进行迭代计算。当全部子集类别属性均为相同时，则停止建树。此时形成二分的决策树，即只有两个可能结果ID3算法:建树算法123ID3算法（选择掌握）ID3算法用编程语言的实现网络链接：/view/66ac453a376baf1ffc4fad66.html本机文件：数据挖掘中ID3算法实现.txtID3算法（选择掌握）ID3算法用编程语言的实现124ID3算法优点算法简单易于理解缺点偏向分割属性中取值多的一个只能处理离散属性ID3不包括树剪枝，易受噪声和波动影响不宜对变化的数据集进行学习ID3算法优点缺点125C4.5算法ID3缺点1：偏向分割属性中取值较多的一个原因：分割属性取值越多，每个值对应的子集规模越小。极限情况下，每个子集内如只有一个单元（表格中的行），则它的信息增益必然最高（对不确定性的消除达到最大）。例如用“身份证号”区分“相亲”，显然没有任何意义，但是确实符合ID3算法。解决方法：引入增益比例C4.5算法ID3缺点1：偏向分割属性中取值较多的一个126C4.5算法对分割属性Y计算熵此熵与样本类别无关（公式中没有X）此公式衡量了分割属性Y的均匀性回忆（习薄）和（奥罗）例子分布越均匀H(Y)越大，反之越小4份2、2分，4份1、1、1、1分4份1、3分，4份1、1、2分的H（Y）C4.5算法对分割属性Y计算熵127C4.5算法（不科学的证明）4份不分H(Y)=04份1、3分H(Y)=0.414份2、2分H(Y)=14份1、1、2分H（Y）=1.54份1、1、1、1分H(Y)=2份数越多，H(Y)月大份数一样的前提下，越平均H(Y)越大C4.5算法（不科学的证明）4份不分H(Y)=0128C4.5算法增益比例G(X,Y)对类别X和分裂属性Y计算G(X,Y)ID3用信息增量I（X|Y）选择节点分割属性C4.5用增益比例选择节点分裂属性C4.5通过引入分母H(Y)，解决了ID3的最大问题，即偏向分割属性中取值较多的一个属性的问题C4.5算法增益比例G(X,Y)C4.5通过引入分母H(Y)129C4.5算法考虑“相亲”中的身份证例子在ID3中，分割属性取值越多，每个值对应的子集规模越小。信息增益极大几率增高。所以ID3产生了偏向性。在C4.5中，如果分割属性取值很大，则C4.5算法考虑“相亲”中的身份证例子130C4.5算法还有缺陷：C4.5算法还有缺陷：131C4.5算法解决方法：先计算所有的信息增益I（X|Y）对于超过I(X|Y)均值，进一步考量H（Y），选取H（Y）最大的这样保证相对大C4.5算法解决方法：132排除H(Yi)=0的可能因为H(Yi)=0时Yi分布及其不均匀则I(X|Y)=0排除H(Yi)为身份证可能此时H(Yi)很大G(X|Y)很小排除H(Yi)=0的可能排除H(Yi)为身份证可能133C4.5算法ID3缺点2：只能处理离散分割属性原因：对于连续属性，和缺点1类似。如果把连续值看成离散值，则会产生分割属性的偏向问题。解决方法：引入“阈值”。将分割属性化为C4.5算法ID3缺点2：只能处理离散分割属性134C4.5算法问题：对于连续取值的分割属性，阈值=？方法：在表格中连续值分割属性取值对每个计算增益比例，找到最大值即可C4.5算法问题：对于连续取值的分割属性，阈值=？135C4.5算法ID3缺点3：无法对未知分割属性进行处理原因：某分割属性Y的一个取值由于一些原因未被计入解决方法