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

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)决策树怎么做？谁是父节点？谁是下一层子节点？为什么是它？头-肌肉-体温头-体温-肌肉肌肉-头-体温肌肉-体温-头体温-头-肌肉体温-肌肉-头333!6P三拍决策决策树基础……@）￥——JK)I*&^Fkl9*^&%*&UIDOFGJNo.天气气温湿度风类别1晴热高无N2晴热高有N3多云热高无P4雨适中高无P5雨冷正常无P6雨冷正常有N7多云冷正常有PNo.天气气温湿度风类别8晴适中高无N9晴冷正常无P10雨适中正常无P11晴适中正常有P12多云适中高有P13多云热正常无P14雨适中高有N怎么生成好的？哪个好？种决策树方案决策树基础N个分割属性的训练集(!)nnPn决策树基础好的决策树：（MDL准则下为例）MinimumDescriptionLength训练集中大多数数据符合这棵树例外的数据单独编码描述决策树用的bit描述例外数据用bitMin哪个好？决策树基础（选择掌握）•如何描述决策树体温头痛很高正常高YNYN否是流感决策树•深度优先遍历决策树•用1标注父子节点•用0标注叶节点•记录分割属性•1,体温,0,Y,1,头疼,0,Y,0,N,0,N层次少+分枝少•占用存储空间小•决策计算时间快决策树基础C4.5算法ID3算法决策树基础信息论基础选哪个？？怎么生成好的？NextOne!信息论基础2I(x)=-logP(x)ii辨析•先验概率•信息量P(x)i信息论基础—先验概率P(x)Xxii先验概率事件发生前，猜测结果为的可能性•对事件X的某一结果进行讨论：例：在没有任何帮助的情况下，奥/罗谁赢的概率P（x1=奥）=P（x2=罗）信息论基础—信息量I()I()I()习近平奥巴马薄熙来主席总统主席2XxP(x)XI(x)I(x)=-logP(x)iiiiii事件的可能结果出现的概率则可能结果的信息量为信息论基础2I(x)=-logP(x)ii2=1H(X)=-P(x)logP(x)NiiiP(x)i辨析•先验概率•信息量•先验熵信息论基础•先验熵——自信息量——熵H（X）原意：热力学中形容失序现象和复杂程度现意：一个事件X的平均信息量•熵越大，不确定性就越大，正确估计其值的可能性就越小。•XXX熵===XXX的信息量的加权2=1H(X)=-P(x)logP(x)Niii信息论基础22222222()=-P()logP()-P()logP()=-0.99log0.99-0.01log0.01=0.067()=-P()logP()-P()logP()=-0.5log0.5-0.5log0.5=1HH中习习薄薄美奥奥罗罗•先验熵——自信息量——熵H（X）原意：热力学中形容失序现象和复杂程度现意：通信中一个事件的平均信息量信息论基础22222222()=-P()logP()-P()logP()=-0.99log0.99-0.01log0.01=0.067()=-P()logP()-P()logP()=-0.5log0.5-0.5log0.5=1HH中习习薄薄美奥奥罗罗•熵H(X)——自信息量科学发展观指导下的和谐社会，失序现象和复杂程度远低于万恶的资本主义社会！事件的可能结果发生几率越相近，则熵越大信息论基础2I(x)=-logP(x)ii2=1H(X)=-P(x)logP(x)NiiiP(x)i辨析•先验概率•信息量•先验熵•后验概率jP(x)iy信息论基础jjP(x)xiiy后验概率在y的辅助条件下猜测事件结果为的可能•对事件X的某一结果进行讨论：例：已知民意调查结果，猜奥/罗谁赢的概率P（x1=奥|y1=奥领先）P（x2=罗|y1=奥领先）信息论基础2I(x)=-logP(x)ii2=1H(X)=-P(x)logP(x)NiiiP(x)i辨析•先验概率•信息量•先验熵•后验概率•后验熵jP(x)iyjj2j=1H(X)=-P(x)logP(x)Niiiyyy信息论基础•熵H(X)原意：热力学中形容失序现象和复杂程度现意：一个事件X的平均信息量•熵越大，不确定性就越大，正确估计其值的可能性就越小。•XXX熵===XXX的信息量的加权后验熵=后验概率的信息量的加权信息论基础jjH(X):Xyy后验熵后验概率的信息量的加权在得知的辅助条件后事件的平均信息量（不确定程度）jj2j=1H(X)=-P(x)logP(x)Niiiyyy•对事件X的全部结果在某一辅助条件下进行讨论：信息论基础jj2j=1H(X)=-P(x)logP(x)Niiiyyy•对事件X的全部结果在某一辅助条件下进行讨论：例：在民意调查的结果帮助下（y1）计算2012年谁是总统的不确定性H(谁当选|民调奥领先)=？信息论基础2I(x)=-logP(x)ii2=1H(X)=-P(x)logP(x)NiiiP(x)i辨析•先验概率•信息量•熵=自信息量•后验概率•后验墒•条件熵jP(x)iyjj2j=1H(X)=-P(x)logP(x)Niiiyyyj2j=1=1H(X)=(y)P(x)logP(x)MNjiijiYPyy信息论基础H(X)XYY条件熵：在得知的全部可能辅助条件后事件的平均信息量（不确定程度）•对事件X的全部结果在全部辅助条件下进行讨论：j2j=1=1H(X)=(y)P(x)logP(x)MNjiijiYPyy信息论基础•条件熵即对后验墒的所有可能辅助条件Yj累计jj2j=1H(X)=-P(x)logP(x)Niiiyyyj2j=1=1H(X)=(y)P(x)logP(x)MNjiijiYPyy信息论基础2I(x)=-logP(x)ii2=1H(X)=-P(x)logP(x)NiiiP(x)i辨析•先验概率•信息量•熵=自信息量•后验概率•后验墒•条件熵jP(x)iyjj2j=1H(X)=-P(x)logP(x)Niiiyyyj2j=1=1H(X)=(y)P(x)logP(x)MNjiijiYPyy信息论基础2I(x)=-logP(x)ii2=1H(X)=-P(x)logP(x)NiiiP(x)i辨析•信息量•熵=自信息量•先验概率•后验概率•后验墒•条件熵•互信息量jP(x)iyjj2j=1H(X)=-P(x)logP(x)Niiiyyy？？——ID3j2j=1=1H(X)=(y)P(x)logP(x)MNjiijiYPyy信息论基础对于条件墒H(X|Y)•由于辅助条件Y的存在•由熵——不确定程度——事件X的平均信息量•所以一般情况下H(X)=H(X|Y)I(X|Y)=H(X)-H(X|Y)信息论基础jj2j=1=12=1=12=1YXP(x,x)P(x)P(y)P(x)===P(x)(y)(x)H(X)=(y)P(x)logP(x)=(y)P(x)logP(x)=P(x)logP(x)=(X)ijijiijjMNjiijiMNjiijiNiiiyPPYPyyPH仅当辅助条件与事件无关时信息论基础因此定义互信息量I(X,Y)——信息增益•I(X,Y)信息增益才是接收端获得的信息量我没收到任何东西前，我不知道你发了是什么我收到了一些东西后，才有机会猜你到底发了什么H(X)(X)(X)-H(X)0I(X,)=(X)-H(X)YHHYYHY定义为信息增益信息论基础I(X,)=(X)-H(X)YHY互信息量I(X,Y)的物理含义•H(X)事件X的结果的不确定性•H(X|Y)事件X在辅助条件Y下的结果的不确定性•H(X)-H(X|Y)辅助条件Y对事件X的结果的不确定性的消除——信息增益ID3和C4.5算法就基于以上ID3算法互信息量I(X,Y)的物理含义•辅助条件Y消除了事件X多少的不确定性ID3算法•IterativeDichotomiser迭代二分器（为什么？）•使用互信息量作为度量标准•选择当前所有分割属性中，互信息量最大的作为内部节点ID3算法ID3算法•使用互信息量作为度量标准•选择当前所有分割属性中，互信息量最大的•作为内部节点——最能消除不确定性的分割属性生活工作中的决策（做？不做？）•总是优先选取最具有决定性意义的辅助条件进行判定如—打不打室外羽毛球？•刮风是最具有决定意义的因素ID3算法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)决策树怎么做？谁是父节点？谁是下一层子节点？为什么是它？头-肌肉-体温头-体温-肌肉肌肉-头-体温肌肉-体温-头体温-头-肌肉体温-肌肉-头333!6P•例题中各数据的属性及其取值分别为：–类别（事件X）：是、否；——x1，x2–分割属性Y1头痛：是、否；–分割属性Y2肌肉痛：是、否；–分割属性Y3体温：很高、高、正常•选择全部数据记录，求先验熵（对类别）：–P(x1)=4/7，P(x2)=3/7–H(X)=-∑i=1,2P(xi)log2P(xi)=0.985bit•后验熵（对Y1）：y1=是，y2=否–P(y1)=4/7，P(y2)=3/7–P(x1|y1)=3/4，P(x2|y1)=1/4–H(X|y1)=-∑i=1,2P(xi|y1)log2P(xi|y1)=0.811–同理，H(X|y2)=0.918ID3算法•条件熵（对Y1）：–H(X|Y1)=∑j=1,2,3P(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.592•I(X,Y3)值最大，所以选择“体温”作为决策树的根节点，将其三个取值分别作为三个分支，并划分原数据集合为三个子集•判断子集中各记录是否属于同一类别，若是则在树上作标记，否则对子集重复上述步骤ID3算法ID3算法（选择掌握）兴趣题~~使用ID3算法构建“天气-外出”决策树No.天气气温湿度风类别1晴热高无N2晴热高有N3多云热高无P4雨适中高无P5雨冷正常无P6雨冷正常有N7多云冷正常有PNo.天气气温湿度风类别8晴适中高无N9晴冷正常无P10雨适中正常无P11晴适中正常有P12多云适中高有P13多云热正常无P14雨适中高有N•例题中各数据的属性及其取值分别为：–类别：P、N；——u1、u2–天气A1：晴、多云、雨；气温A2：冷、适中、热；–湿度A3：高、正常；风A4：有、无•选择全部数据记录，求先验熵（对类别）：–P(u1)=9/14，P(u2)=5/14–H(U)=-∑i=1,2P(ui)log2P(ui)=0.94bit•后验熵（对A1）：v1=晴，v2=多云，v3=雨–P(v1)=5/14，P(v2)=4/14，P(v3)=5/14–P(u1|v1)=2/5，P(u2|v1)=3/5–H(U|v1)=-∑i=1,2P(ui|v1)log2P(ui|v