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

C4 5算法讲解 2012 11 29 C4 5算法 ID3算法 知识结构 决策树基础 信息论基础 决策树基础 女孩家长安排相亲女孩不厌其烦女孩提出决策树父母筛选候选男士 决策树基础 有向无环二叉 多叉树父节点 没有子节点的节点内部节点 有父节点 子节点的节点叶节点 有父节点没有子节点的节点 父节点内部节点 叶节点 分割属性 判断规则 类别标识 决策树基础 父节点内部节点 叶节点 类别标识 分割属性 判断规则 决策树基础 训练集 数据的集合 用于生成树 模型 测试集 用于测试树 模型 的性能决策树作用 通过训练集算法指导下生成决策树新数据进行划分否则是 三拍 决策 训练集 算法 决策树 新数据 决策 决策树基础 实例 决策树怎么做 谁是父节点 谁是下一层子节点 为什么是它 头 肌肉 体温头 体温 肌肉肌肉 头 体温肌肉 体温 头体温 头 肌肉体温 肌肉 头 三拍决策 决策树基础 JK I Fkl9 UIDOFGJ 怎么生成好的 哪个好 种决策树方案 决策树基础 N个分割属性的训练集 决策树基础 好的决策树 MDL准则下为例 MinimumDescriptionLength训练集中大多数数据符合这棵树例外的数据单独编码 哪个好 决策树基础 选择掌握 如何描述决策树 深度优先遍历决策树用1标注父子节点用0标注叶节点记录分割属性1 体温 0 Y 1 头疼 0 Y 0 N 0 N层次少 分枝少占用存储空间小决策计算时间快 决策树基础 C4 5算法 ID3算法 决策树基础 信息论基础 选哪个 怎么生成好的 NextOne 信息论基础 辨析先验概率信息量 信息论基础 先验概率 对事件X的某一结果进行讨论 例 在没有任何帮助的情况下 奥 罗谁赢的概率P x1 奥 P x2 罗 信息论基础 信息量 信息论基础 辨析先验概率信息量先验熵 信息论基础 先验熵 自信息量 熵H X 原意 热力学中形容失序现象和复杂程度现意 一个事件X的平均信息量熵越大 不确定性就越大 正确估计其值的可能性就越小 XXX熵 XXX的信息量的加权 信息论基础 先验熵 自信息量 熵H X 原意 热力学中形容失序现象和复杂程度现意 通信中一个事件的平均信息量 信息论基础 熵H X 自信息量科学发展观指导下的和谐社会 失序现象和复杂程度远低于万恶的资本主义社会 事件的可能结果发生几率越相近 则熵越大 信息论基础 辨析先验概率信息量先验熵后验概率 信息论基础 对事件X的某一结果进行讨论 例 已知民意调查结果 猜奥 罗谁赢的概率P x1 奥 y1 奥领先 P x2 罗 y1 奥领先 信息论基础 辨析先验概率信息量先验熵后验概率后验熵 信息论基础 熵H X 原意 热力学中形容失序现象和复杂程度现意 一个事件X的平均信息量熵越大 不确定性就越大 正确估计其值的可能性就越小 XXX熵 XXX的信息量的加权后验熵 后验概率的信息量的加权 信息论基础 对事件X的全部结果在某一辅助条件下进行讨论 信息论基础 对事件X的全部结果在某一辅助条件下进行讨论 例 在民意调查的结果帮助下 y1 计算2012年谁是总统的不确定性H 谁当选 民调奥领先 信息论基础 辨析先验概率信息量熵 自信息量后验概率后验墒条件熵 信息论基础 对事件X的全部结果在全部辅助条件下进行讨论 信息论基础 条件熵即对后验墒的所有可能辅助条件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的结果的不确定性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算法互信息量最大 决策树怎么做 谁是父节点 谁是下一层子节点 为什么是它 头 肌肉 体温头 体温 肌肉肌肉 头 体温肌肉 体温 头体温 头 肌肉体温 肌肉 头 例题中各数据的属性及其取值分别为 类别 事件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 918 ID3算法 条件熵 对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 592I X Y3 值最大 所以选择 体温 作为决策树的根节点 将其三个取值分别作为三个分支 并划分原数据集合为三个子集判断子集中各记录是否属于同一类别 若是则在树上作标记 否则对子集重复上述步骤 ID3算法 ID3算法 选择掌握 兴趣题 使用ID3算法构建 天气 外出 决策树 例题中各数据的属性及其取值分别为 类别 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 97 ID3算法 选择掌握 条件熵 对A1 H U V j 1 2 3P 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算法 选择掌握 ID3算法 每个名字都有它的意义御手洗 Fox电影公司 狐狸电影公司Paramount电影公司 最牛的电影公司美国总统Bush 美国总统灌木丛ID3为什么是IterativeDichotomiser迭代二分器 ID3算法 Iterative 迭代 当前的输出结果会返回到程序开始作自变量 Dichotomiser 二分器 ID3算出的决策树的 类别 只有 是 否 如 流感 决策树 ID3算法 主算法 从训练集中随机选择一个既含正例 Y 又含反例 N 的子集 称为 窗口 用 建树算法 对当前窗口形成一棵决策树 对训练集 窗口除外 中例子用所得决策树进行类别判定 找出错判的例子 若存在错判的例子 把它们插入窗口 重复步骤 2 否则结束 ID3算法 建树算法 自顶向下 从父节点开始 逐层向下贪心 例如 100个数 挑出5个很小的数 贪心法在每层总取互信息量最小的属性但不保证整个决策树是最优的如果各属性彼此独立则最优如果有相关性 可能非最优递归 一个程序在过程中有调用自身将大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解 ID3算法 建树算法 对窗口的所有分割属性 计算各自的互信息量 选择互信息最大的特征Ak 作为内部节点把在Ak处取值相同的属性归于同一子集 将当前表格的行划分成不同的子集 判断子集 若各子集中类别属性相同 则在决策树上作相应类别标记 并返回否则将子集作为1 中的窗口 进行迭代计算 当全部子集类别属性均为相同时 则停止建树 此时形成二分的决策树 即只有两个可能结果 ID3算法 选择掌握 ID3算法用编程语言的实现网络链接 ID3算法 优点算法简单易于理解 缺点偏向分割属性中取值多的一个只能处理离散属性ID3不包括树剪枝 易受噪声和波动影响不宜对变化的数据集进行学习 C4 5算法 ID3缺点1 偏向分割属性中取值较多的一个原因 分割属性取值越多 每个值对应的子集规模越小 极限情况下 每个子集内如只有一个单元 表格中的行 则它的信息增益必然最高 对不确定性的消除达到最大 例如用 身份证号 区分 相亲 显然没有任何意义 但是确实符合ID3算法 解决方法 引入增益比例 C4 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算法 不科学的证明 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算法 增益比例G X Y 对类别X和分裂属性Y计算G X Y ID3用信息增量I X Y 选择节点分割属性C4 5用增益比例选择节点分裂属性 C4 5通过引入分母H Y 解决了ID3的最大问题 即偏向分割属性中取值较多的一个属性的问题 C4 5算法 考虑 相亲 中的身份证例子在ID3中 分割属性取值越多 每个值对应的子集规模越小 信息增益极大几率增高 所以ID3产生了偏向性 在C4 5中 如果分割属性取值很大 则 C4 5算法 还有缺陷 C4 5算法 解决方法 先计算所有的信息增益I X Y 对于超过I X Y 均值 进一步考量H Y 选取H Y 最大的这样保证相对大 排除H Yi 0的可能因为H Yi 0时Yi分布及其不均匀则I X Y 0 排除H Yi 为身份证可能此时H Yi 很大G X Y 很小 C4 5算法 ID3缺点2 只能处理离散分割属性原因 对于连续属性 和缺点1类似 如果把连续值看成离散值 则会产生分割属性的偏向问题 解决方法 引入 阈值 将分割属性化为 C4 5算法 问题 对于连续取值的分割属性 阈值 方法 在表格中连续值分割属性取值对每个计算增益比例 找到最大值即可 C4 5算法 ID3缺点3 无法对未知分割属性进行处理原因 某分割属性Y的一个取值由于一些原因未被计入解决方法 平均值代替概率法代替 C4 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算法 ID3缺点3 无树剪枝 易受噪声和波动影响解决方法 K阶交叉验证 C4 5算法 数据集 一组表格 子集1 子集2 子集3 子集4 子集5 子集6 子集7 子集8 C4 5 决策树1 用于生成树 用于验证 K 8的8阶交叉验证 错误数1 C4 5算法 数据集 一组表格 子集2 子集1 子集3 子集4 子集5 子集6 子集7 子集8 C4 5 决策树2 用于生成树 用于验证 K 8的8阶交叉验证 错误数2 C4 5算法 数据集 一组表格 子集3 子集1 子集2 子集4 子集5 子集6 子集7 子集8 C4 5 决策树3 用于生成树 用于验证 K 8的8阶交叉验证 错误数3 C4 5算法 数据集 一组表格 子集4 子集1 子集2 子集3 子集5 子集6 子集7 子集8 C4 5 决策树4 用于生成树 用于验证 K 8的8阶交叉验证 错误数4 C4 5算法 数据集 一组表格 子集5 子集1 子集2 子集3 子集4 子集6 子集7 子集8 C4 5 决策树5 用于生成树 用于验证 K 8的8阶交叉验证 错误数5 C4 5算法 数据集 一组表格 子集6 子集1 子集2 子集3 子集4 子集5 子集7 子集8 C4 5 决策树6 用于生成树 用于验证 K 8的8阶交叉验证 错误数6 C4 5算法 数据集 一组表格 子