ID算法及优化spssPPT课件.ppt

ID3算法及优化 27 01 2020 1 ID3算法 设训练实例集为X 学习目的是将训练实例分为n类 记为C X1 X2 Xn 设第i类的训练实例个数是 Xi Ci X中总的训练实例个数为 X 若记一个实例属于第i类的概率为P Xi 则有 此时决策树对划分C的不确定程度为H X C 可简记为H X 1 2 27 01 2020 2 ID3算法 1 of 9 决策树学习过程就是使得决策树对划分的不确定程度逐渐减小的过程 若选择测试属性A进行测试 设属性A具有性质a1 a2 a3 ai 在A ai的情况下属于第i类的实例个数为Cij个 记 即P Xi A aj 为测试属性A的取值为aj时它属于第i类的概率 记Yj为A aj时的实例集 此时决策树对分类的不确定程度就是训练实例集对属性A的条件熵 3 4 27 01 2020 3 ID3算法 2 of 9 当选择测试属性A后伸出的每一个A aj叶节点Xj对于分类信息的信息熵为 属性A对于分类提供的信息量 即属性A的信息增益为 5 6 27 01 2020 4 3 of 9 ID3算法 显然 式 5 的值越小则式 6 的值越大 说明选择测试属性A对于分类提供的信息越大 选择A之后对分类的不确定程度越小 ID3算法即采取I X A 作为测试属性的选取标准分割训练实例集最终生成决策树 27 01 2020 5 4 of 9 ID3算法的不足 ID3算法往往偏向于选择取值较多的属性 因为加权和的方法使得实例集的分类趋向于抛弃小数据量的数据元组 然而属性较多的属性却不总是最优的属性 即按照使熵值最小和信息增益最大的原则被ID3算法列为应该首先选取的属性在现实情况中却并不那么重要 也就是说对这些属性进行测试不会提供太多的信息 27 01 2020 6 5 of 9 ID3算法改进 针对以上缺点 引入用户兴趣度 给定0 1 称为用户对不确定知识的兴趣度 其大小由决策者根据先验知识或领域知识来确定 它是一个模糊的概念 通常指关于某一事务的先验知识 包括领域知识和专家建议 具体到决策树学习中则是指在决策树训练过程中除了用于生成和修改决策树的实例集之外的所有影响决策树规则生成和选择的因素 27 01 2020 7 ID3算法优化 6 of 9 改进的ID3算法是针对规则生成方法即属性选择标准算法进行了改进 通过对式 5 中加权和增加用户兴趣度 加强了属性的标注 降低非重要属性的标注 把加权和转换为加权和加用户兴趣度 使生成决策树时数量少的数据元组不会被淹没 最终使决策树减少了对取值较多的属性的依赖性 从而尽可能地减少大数据掩盖小数据的现象发生 27 01 2020 8 ID3算法优化 7 of 9 利用用户兴趣度把 5 修改为 相应式 6 变为 式 7 中 用户兴趣度 取值在 0 1 之间 其大小由决策者根据先验知识或领域知识测试后给出 7 8 27 01 2020 9 ID3算法优化 8 of 9 改进ID3算法就是把式 7 和式 8 作为测试属性的选择标准来构造决策树 实际应用中可以首先用ID3算法构造决策树 如果结果中出现了取值少的重要属性比取值多的非重要属性离根结点的距离远的情况 则可设定用户兴趣度利用改进后ID3算法重新构造决策树进行规则提取 27 01 2020 10 算法举例 样本数据表1 27 01 2020 11 程序运行结果 27 01 2020 12 2020 1 27 13 ID3算法决策树 27 01 2020 14 9 of 9 DisseminationCo Ltd ID3算法结论 根据上图从根结点到叶结点的路径及数据集所包含记录的多少 可以得出如下分类规则 表格表示如表2 1 IF 穿衣 较多AND湿度 正常 THEN 类别 正 2 IF穿衣 较多AND湿度 很大THEN 类别 负 3 IF 温度 正常AND穿衣 较多 THEN 类别 负 4 IF 穿衣 较多AND温度 很高AND风力 很大 THEN 类别 负 27 01 2020 15 ID3算法结论 表2 27 01 2020 16 ID3算法 由分类规则表可以看到 实际生活中 人们穿衣的多少是一种主观的行为 与个人的实际情况有很大的关系 比如通常情况下老年人 病人 婴幼儿 孕妇等就会比健康的成年人穿衣多一点 所以穿衣指数能在一定程度上反映出天气的舒适度但并不能成为决定天气舒适与否的客观条件 即它不是一个很重要的分类属性 所以需要降低穿衣指数属性在分类中的重要性 相对地提高温度 湿度和风力在分类中的重要性 27 01 2020 17 ID3算法优化 通过测试指定穿衣指数属性的用户兴趣度 0 33 其它属性的用户兴趣度设为0 首先对根结点进行分类 由表1可知 初始时刻正例 舒适 类实例个数为9 反例 不舒适 类实例个数为11 所以开始时熵值为 27 01 2020 18 ID3算法优化 选择穿衣指数作为测试属性后 该属性的信息熵为 如果选取温度属性作为测试属性则此时的条件熵为 27 01 2020 19 ID3算法优化 如果选取湿度属性作为测试属性则此时的条件熵为 如果选取风力属性作为测试属性则此时的条件熵为 比较可知 H X 湿度 H X 温度 H X 穿衣指数 H X 风力 27 01 2020 20 ID3算法优化决策树 27 01 2020 21 ID3算法优化结论 可以得出以下分类规则 湿度很大且穿衣较多时 人们会感觉很不适 湿度正常或稍大点 穿衣也正常或稍多一点 人们会感觉舒适 穿衣较多而温度又很高人们会感觉不适 穿衣较多温度较高而又有大风时人们感觉不适 可以用表3表示 27 01 2020 22 ID3算法优化结论 其中 规则1至规则4比较符合实际情况可以用于实际中进行预测天气舒适度 表3 27 01 2020 23 结论 比较两种决策树算法的规则提取 可以发现改进算法与ID3算法所生成的决策树有很大的区别 得到的分类规则也有较大不同 但改进算法基