决策树信息论c45算法

《决策树信息论c45算法》由会员分享，可在线阅读，更多相关《决策树信息论c45算法（76页珍藏版）》请在金锄头文库上搜索。

1、C4.5算法讲解,2012.11.29,C4.5算法,ID3算法,知识结构,决策树基础,信息论基础,决策树基础,女孩家长 安排相亲 女孩 不厌其烦 女孩 提出决策树 父母筛选 候选男士,决策树基础,有向无环 二叉/多叉树 父节点：没有子节点的节点 内部节点：有父节点、子节点的节点 叶节点：有父节点没有子节点的节点,父节点 内部节点,叶节点,分割属性+判断规则,类别标识,决策树基础,父节点 内部节点,叶节点 （类别标识）,（分割属性+判断规则）,决策树基础,训练集：数据的集合，用于生成树（模型） 测试集：用于测试树（模型）的性能 决策树作用： 通过训练集 算法指导下 生成决策树 新数据进行划分

2、否则是“三拍”决策,训练集,算法,决策树,新数据,决策,决策树基础,实例,决策树怎么做？谁是父节点？ 谁是下一层子节点？为什么是它？,头-肌肉-体温 头-体温-肌肉 肌肉-头-体温 肌肉-体温-头 体温-头-肌肉 体温-肌肉-头,三 拍 决 策,决策树基础,）￥JK)I*&Fkl9*&%*&UIDOFGJ,怎么生成好的？,哪个好？,种决策树方案,决策树基础,N个分割属性的训练集,决策树基础,好的决策树：（MDL准则下为例） Minimum Description Length 训练集中大多数数据符合这棵树 例外的数据单独编码,哪个好？,决策树基础（选择掌握）,如何描述决策树,深度优先遍历决策树

3、 用1标注父子节点 用0标注叶节点 记录分割属性 1,体温,0,Y,1,头疼,0,Y,0,N,0,N 层次少+分枝少 占用存储空间小 决策计算时间快,决策树基础,C4.5算法,ID3算法,决策树基础,信息论基础,选哪个？,怎么生成好的？,Next One!,信息论基础,辨析 先验概率 信息量,信息论基础先验概率,对事件X的某一结果进行讨论： 例：在没有任何帮助的情况下，奥/罗谁赢的概率 P（x1=奥）= P（x2=罗）,信息论基础信息量,信息论基础,辨析 先验概率 信息量 先验熵,信息论基础,先验熵自信息量熵H（X） 原意：热力学中形容失序现象和复杂程度 现意：一个事件X的平均信息量 熵越大，

4、不确定性就越大，正确估计其值的可能性就越小。 XXX熵=XXX的信息量的加权,信息论基础,先验熵自信息量熵H（X） 原意：热力学中形容失序现象和复杂程度 现意：通信中一个事件的平均信息量,信息论基础,熵H(X)自信息量 科学发展观指导下的和谐社会，失序现象和复杂程度远低于万恶的资本主义社会！ 事件的可能结果发生几率越相近，则熵越大,信息论基础,辨析 先验概率 信息量 先验熵 后验概率,信息论基础,对事件X的某一结果进行讨论： 例：已知民意调查结果，猜奥/罗谁赢的概率 P（x1=奥|y1=奥领先） P（x2=罗|y1=奥领先）,信息论基础,辨析 先验概率 信息量 先验熵 后验概率 后验熵,信息论

5、基础,熵H(X) 原意：热力学中形容失序现象和复杂程度 现意：一个事件X的平均信息量 熵越大，不确定性就越大，正确估计其值的可能性就越小。 XXX熵=XXX的信息量的加权 后验熵=后验概率的信息量的加权,信息论基础,对事件X的全部结果在某一辅助条件下进行讨论：,信息论基础,对事件X的全部结果在某一辅助条件下进行讨论： 例：在民意调查的结果帮助下（y1） 计算2012年谁是总统的不确定性 H(谁当选|民调奥领先)=？,信息论基础,辨析 先验概率 信息量 熵=自信息量 后验概率 后验墒 条件熵,信息论基础,对事件X的全部结果在全部辅助条件下进行讨论：,信息论基础,条件熵 即对后验墒的所有可能辅助条

6、件Yj累计,信息论基础,辨析 先验概率 信息量 熵=自信息量 后验概率 后验墒 条件熵,信息论基础,辨析 信息量 熵=自信息量 先验概率 后验概率 后验墒 条件熵 互信息量,信息论基础,对于条件墒H(X|Y) 由于辅助条件Y的存在 由熵不确定程度事件X的平均信息量 所以一般情况下 H(X)=H(X|Y) I(X|Y)=H(X)-H(X|Y),信息论基础,信息论基础,因此定义互信息量I(X,Y)信息增益 I(X,Y)信息增益才是接收端获得的信息量 我没收到任何东西前，我不知道你发了是什么 我收到了一些东西后，才有机会猜你到底发了什么,信息论基础,互信息量I(X,Y)的物理含义 H(X) 事件X的

7、结果的不确定性 H(X|Y) 事件X在辅助条件Y下的结果的不确定性 H(X)- H(X|Y) 辅助条件Y对事件X的结果的不确定性的消除信息增益,ID3和C4.5算法就基于以上,ID3算法,互信息量I(X,Y)的物理含义 辅助条件Y消除了事件X多少的不确定性 ID3算法 Iterative Dichotomiser 迭代二分器（为什么？） 使用互信息量作为度量标准 选择当前所有分割属性中，互信息量最大的 作为内部节点,ID3算法,ID3算法 使用互信息量作为度量标准 选择当前所有分割属性中，互信息量最大的 作为内部节点最能消除不确定性的分割属性,生活工作中的决策 （做？不做？） 总是优先选取最具

8、有决定性意义的 辅助条件进行判定 如打不打室外羽毛球？ 刮风是最具有决定意义的因素,ID3算法,ID3算法 互信息量最大,决策树怎么做？谁是父节点？ 谁是下一层子节点？为什么是它？,头-肌肉-体温 头-体温-肌肉 肌肉-头-体温 肌肉-体温-头 体温-头-肌肉 体温-肌肉-头,例题中各数据的属性及其取值分别为： 类别（事件X）：是、否；x1，x2 分割属性Y1 头痛：是、否； 分割属性Y2 肌肉痛：是、否； 分割属性Y3 体温 ：很高、高、正常 选择全部数据记录，求先验熵（对类别）： P(x1)=4/7，P(x2)=3/7 H(X)= - i=1,2P(xi) log2 P(xi)=0.985

9、 bit 后验熵（对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.918,ID3算法,条件熵（对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.592 I (X,Y3)值最大，所以选

10、择“体温”作为决策树的根节点，将其三个取值分别作为三个分支，并划分原数据集合为三个子集 判断子集中各记录是否属于同一类别，若是则在树上作标记，否则对子集重复上述步骤,ID3算法,ID3算法（选择掌握）,兴趣题 使用ID3算法构建“天气-外出”决策树,例题中各数据的属性及其取值分别为： 类别：P、N；u1、u2 天气A1：晴、多云、雨；气温A2：冷、适中、热； 湿度A3 ：高、正常； 风A4 ：有、无 选择全部数据记录，求先验熵（对类别）： P(u1)=9/14，P(u2)=5/14 H(U)=- i=1,2P(ui) log2 P(ui)=0.94 bit 后验熵（对A1）：v1 =晴，v2=

11、多云，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 | v1) =0.97 同理， H(U|v2 )=0，H(U|v3 )=0.97,ID3算法（选择掌握）,条件熵（对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.05 I (

12、A1)值最大，所以选择“天气”作为决策树的根节点，将其三个取值分别作为三个分支，并划分原数据集合为三个子集 判断子集中各记录是否属于同一类别，若是则在树上作标记，否则对子集重复上述步骤,ID3算法（选择掌握）,ID3算法,每个名字都有它的意义 御手洗！#！#￥&￥# Fox电影公司 = 狐狸电影公司 Paramount电影公司 = 最牛的电影公司 美国总统Bush = 美国总统灌木丛 ID3为什么是 Iterative Dichotomiser迭代二分器,ID3算法,Iterative（迭代） 当前的输出结果会返回到程序开始作自变量。 Dichotomiser（二分器） ID3算出的决策树的“

13、类别”只有“是”、“否” 如“流感”决策树,ID3算法:主算法,从训练集中随机选择一个既含正例(Y)又含反例(N)的子集（称为“窗口”）； 用“建树算法”对当前窗口形成一棵决策树； 对训练集（窗口除外）中例子用所得决策树进行类别判定，找出错判的例子； 若存在错判的例子，把它们插入窗口，重复步骤（2），否则结束。,ID3算法:建树算法,自顶向下： 从父节点开始，逐层向下 贪心： 例如“100个数，挑出5个很小的数” 贪心法 在每层总取互信息量最小的属性 但不保证整个决策树是最优的 如果各属性彼此独立则最优 如果有相关性，可能非最优 递归： 一个程序在过程中有调用自身 将大型复杂的问题层层转化为一

14、个与原问题相似的规模较小的问题来求解,ID3算法:建树算法,对窗口的所有分割属性，计算各自的互信息量； 选择互信息最大的特征Ak，作为内部节点 把在Ak处取值相同的属性归于同一子集，将当前表格的行划分成不同的子集； 判断子集，若各子集中类别属性相同，则在决策树上作相应类别标记，并返回 否则将子集作为1)中的窗口，进行迭代计算。 当全部子集类别属性均为相同时，则停止建树。 此时形成二分的决策树，即只有两个可能结果,ID3算法（选择掌握）,ID3算法用编程语言的实现 网络链接： http:/ 本机文件： 数据挖掘中ID3算法实现.txt,ID3算法,优点 算法简单 易于理解,缺点 偏向分割属性中取

15、值多的一个 只能处理离散属性 ID3不包括树剪枝，易受噪声和波动影响 不宜对变化的数据集进行学习,C4.5算法,ID3缺点1：偏向分割属性中取值较多的一个 原因：分割属性取值越多，每个值对应的子集规模越小。 极限情况下，每个子集内如只有一个单元（表格中的行），则它的信息增益必然最高（对不确定性的消除达到最大）。 例如用“身份证号”区分“相亲”，显然没有任何意义，但是确实符合ID3算法。 解决方法：引入增益比例,C4.5算法,对分割属性Y计算熵 此熵与样本类别无关（公式中没有X） 此公式衡量了分割属性Y的均匀性 回忆（习薄）和（奥罗）例子 分布越均匀H(Y)越大，反之越小 4份2、2分，4份1、

16、1、1、1分 4份1、3分，4份1、1、2分 的H（Y）,C4.5算法（不科学的证明）,4份不分 H(Y)=0 4份1、3分 H(Y)=0.41 4份2、2分 H(Y)=1 4份1、1、2分 H（Y）=1.5 4份1、1、1、1分 H(Y)=2 份数越多，H(Y)月大 份数一样的前提下，越平均H(Y)越大,C4.5算法,增益比例G(X,Y) 对类别X和分裂属性Y计算G(X,Y) ID3用信息增量I（X|Y）选择节点分割属性 C4.5用增益比例选择节点分裂属性,C4.5通过引入分母H(Y)，解决了ID3的最大问题， 即 偏向分割属性中取值较多的一个属性的问题,C4.5算法,考虑“相亲”中的身份证例子 在ID3中，分割属性取值越多，每个值对应的子集规模越小。信息增益极大几率增高。所以ID3产