决策树信息论C45算法.pptx
C4.5算法讲解算法讲解2012.11.29C4.5算法算法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)N(1)7是(1)否(0)高(1)Y(1)决策树怎么做？谁是父节点？决策树怎么做？谁是父节点？谁是下一层子节点？为什么是它？谁是下一层子节点？为什么是它？l头-肌肉-体温l头-体温-肌肉l肌肉-头-体温l肌肉-体温-头l体温-头-肌肉l体温-肌肉-头三三 拍拍 决决 策策决策树基础决策树基础）￥）￥JK)I*&Fkl9*&%*&UIDOFGJNo.天气气温湿度风类别1晴热高无N2晴热高有N3多云热高无P4雨适中高无P5雨冷正常无P6雨冷正常有N7多云冷正常有PNo.天气气温湿度风类别8晴适中高无N9晴冷正常无P10雨适中正常无P11晴适中正常有P12多云适中高有P13多云热正常无P14雨适中高有N怎么生成好的？怎么生成好的？哪个好？哪个好？种决策树方案种决策树方案决策树基础决策树基础N个分割属性的训练集个分割属性的训练集决策树基础决策树基础好的决策树好的决策树：（MDL准则下为例）准则下为例）Minimum Description Lengthn训练集中大多数数据符合这棵树n例外的数据单独编码描述决策树用的描述决策树用的bit描述例外数据用描述例外数据用bit哪个好？哪个好？决策树基础（选择掌握）决策树基础（选择掌握）如何描述决策树体温体温头痛头痛很高很高正常正常高高YNYN否否是是流感决策树流感决策树 深度优先遍历决策树深度优先遍历决策树 用用1 1标注父子节点标注父子节点 用用0 0标注叶节点标注叶节点 记录分割属性记录分割属性 1,1,体温体温,0,Y,1,0,Y,1,头疼头疼,0,Y,0,N,0,N,0,Y,0,N,0,N层次少层次少+分枝少分枝少 占用存储空间小占用存储空间小 决策计算时间快决策计算时间快决策树基础决策树基础C4.5算法算法ID3算法算法决策树基础决策树基础信息论基础信息论基础选哪个？选哪个？怎么生成好的？怎么生成好的？Next One!信息论基础信息论基础辨析辨析先验概率先验概率信息量信息量信息论基础信息论基础先验概率先验概率对事件对事件X的某一结果进行讨论：的某一结果进行讨论：例：在没有任何帮助的情况下，奥例：在没有任何帮助的情况下，奥/罗谁赢的概率罗谁赢的概率P（x1=奥）奥）=P（x2=罗）罗）信息论基础信息论基础信息量信息量信息论基础信息论基础辨析辨析先验概率先验概率信息量信息量先验熵先验熵信息论基础信息论基础先验熵先验熵自信息量自信息量熵熵H（X）原意：热力学中形容失序现象和复杂程度原意：热力学中形容失序现象和复杂程度 现意：一个事件现意：一个事件X的平均信息量的平均信息量熵越大，不确定性就越大，正确估计其值的可能熵越大，不确定性就越大，正确估计其值的可能性就越小。性就越小。XXXXXX熵熵=XXX=XXX的信息量的加权的信息量的加权信息论基础信息论基础先验熵先验熵自信息量自信息量熵熵H（X）原意：热力学中形容失序现象和复杂程度原意：热力学中形容失序现象和复杂程度 现意：通信中一个事件的平均信息量现意：通信中一个事件的平均信息量信息论基础信息论基础熵熵H(X)自信息量自信息量科学发展观指导下的和谐社会，失序现象和复杂科学发展观指导下的和谐社会，失序现象和复杂程度远低于万恶的资本主义社会！程度远低于万恶的资本主义社会！事件的可能结果发生几率越相近，则熵越大事件的可能结果发生几率越相近，则熵越大信息论基础信息论基础辨析辨析先验概率先验概率信息量信息量先验熵先验熵后验概率后验概率信息论基础信息论基础对事件对事件X的某一结果进行讨论：的某一结果进行讨论：例：已知民意调查结果，猜奥例：已知民意调查结果，猜奥/罗谁赢的概率罗谁赢的概率P（x1=奥奥|y1=奥领先）奥领先）P（x2=罗罗|y1=奥领先）奥领先）信息论基础信息论基础辨析辨析先验概率先验概率信息量信息量先验熵先验熵后验概率后验概率后验熵后验熵信息论基础信息论基础熵熵H(X)原意：热力学中形容失序现象和复杂程度原意：热力学中形容失序现象和复杂程度 现意：一个事件现意：一个事件X的平均信息量的平均信息量熵越大，不确定性就越大，正确估计其值的可能熵越大，不确定性就越大，正确估计其值的可能性就越小。性就越小。XXXXXX熵熵=XXX=XXX的信息量的加权的信息量的加权 后验熵后验熵=后验概率的信息量的加权后验概率的信息量的加权信息论基础信息论基础对事件对事件X的全部结果在某一辅助条件下进行讨论：的全部结果在某一辅助条件下进行讨论：信息论基础信息论基础对事件对事件X的全部结果在某一辅助条件下进行讨论：的全部结果在某一辅助条件下进行讨论：例：在民意调查的结果帮助下（例：在民意调查的结果帮助下（y1）计算计算2012年谁是总统的不确定性年谁是总统的不确定性H(谁当选谁当选|民调奥领先民调奥领先)=？信息论基础信息论基础辨析辨析先验概率先验概率信息量信息量熵熵=自信息量自信息量后验概率后验概率后验墒后验墒条件熵条件熵信息论基础信息论基础对事件对事件X的全部结果在全部辅助条件下进行讨论：的全部结果在全部辅助条件下进行讨论：信息论基础信息论基础条件熵即对后验墒的所有可能辅助条件Yj累计信息论基础信息论基础辨析辨析先验概率先验概率信息量信息量熵熵=自信息量自信息量后验概率后验概率后验墒后验墒条件熵条件熵信息论基础信息论基础辨析辨析信息量信息量熵熵=自信息量自信息量先验概率先验概率后验概率后验概率后验墒后验墒条件熵条件熵互信息量互信息量信息论基础信息论基础对于条件墒对于条件墒H(X|Y)由于辅助条件由于辅助条件Y的存在的存在由熵由熵不确定程度不确定程度事件事件X的平均信息量的平均信息量所以一般情况下所以一般情况下 H(X)=30 THEN 不见不见IF 年龄年龄=30 AND 长相长相=丑丑 THEN 不见不见IF年龄年龄=30 AND 长相长相=帅帅or中等中等 AND 收收入入=高高 THEN 见见IF年龄年龄=30 AND 长相长相=帅帅or中等中等 AND 收收入入=中等中等 AND 公务员公务员=是是 THEN 见见IF年龄年龄=30 AND 长相长相=帅帅or中等中等 AND 收收入入=中等中等 AND 公务员公务员=不是不是 THEN 不见不见IF年龄年龄=30 AND 长相长相=帅帅or中等中等 AND 收收入入=低低 THEN 不见不见C4.5算法算法ID3缺点缺点3：无树剪枝，易受噪声和波动影响无树剪枝，易受噪声和波动影响解决方法：解决方法：K阶交叉验证阶交叉验证C4.5算法算法数据集数据集(一组一组表格表格)子集子集1子集子集2子集子集3子集子集4子集子集5子集子集6子集子集7子集子集8C4.5决策树决策树1用用于于生生成成树树用于验证用于验证K=8的的8阶交叉验证阶交叉验证错误数错误数1C4.5算法算法数据集数据集(一组一组表格表格)子集子集2子集子集1子集子集3子集子集4子集子集5子集子集6子集子集7子集子集8C4.5决策树决策树2用用于于生生成成树树用于验证用于验证K=8的的8阶交叉验证阶交叉验证错误数错误数2C4.5算法算法数据集数据集(一组一组表格表格)子集子集3子集子集1子集子集2子集子集4子集子集5子集子集6子集子集7子集子集8C4.5决策树决策树3用用于于生生成成树树用于验证用于验证K=8的的8阶交叉验证阶交叉验证错误数错误数3C4.5算法算法数据集数据集(一组一组表格表格)子集子集4子集子集1子集子集2子集子集3子集子集5子集子集6子集子集7子集子集8C4.5决策树决策树4用用于于生生成成树树用于验证用于验证K=8的的8阶交叉验证阶交叉验证错误数错误数4C4.5算法算法数据集数据集(一组一组表格表格)子集子集5子集子集1子集子集2子集子集3子集子集4子集子集6子集子集7子集子集8C4.5决策树决策树5用用于于生生成成树树用于验证用于验证K=8的的8阶交叉验证阶交叉验证错误数错误数5C4.5算法算法数据集数据集(一组一组表格表格)子集子集6子集子集1子集子集2子集子集3子集子集4子集子集5子集子集7子集子集8C4.5决策树决策树6用用于于生生成成树树用于验证用于验证K=8的的8阶交叉验证阶交叉验证错误数错误数6C4.5算法算法数据集数据集(一组一组表格表格)子集子集7子集子集1子集子集2子集子集3子集子集4子集子集5子集子集6子集子集8C4.5决策树决策树7用用于于生生成成树树用于验证用于验证K=8的的8阶交叉验证阶交叉验证错误数错误数7C4.5算法算法数据集数据集(一组一组表格表格)子集子集8子集子集1子集子集2子集子集3子集子集4子集子集5子集子集6子集子集7C4.5决策树决策树8用用于于生生成成树树用于验证用于验证K=8的的8阶交叉验证阶交叉验证错误数错误数8C4.5算法算法树树1错错1树树2错错2树树3错错3树树4错错4树树5错错5树树6错错6树树7错错7树树8错错8决决 策策 树树 最最 终终 版版仅用于小规模数据仅用于小规模数据C4.5算法（选择掌握）算法（选择掌握）C4.5算法用算法用C语言的实现语言的实现网络链接：网络链接：http:/ 邵峰晶等编著；数据挖掘算法与应用北京大学出版社 梁循编著现代通信原理清华大学出版社 曹志刚等编著
