决策树.ppt

1 决策树 DecisionTree 2019 12 27 2 1 分类的意义 数据库 了解类别属性与特征 分类模型 决策树 分类模型 聚类 一 分类 Classification 2019 12 27 3 数据库 分类标记 2019 12 27 2 分类的技术 1 决策树 4 2 聚类 2019 12 27 3 分类的程序 5 模型建立 ModelBuilding 模型评估 ModelEvaluation 使用模型 UseModel 2019 12 27 决策树分类的步骤 6 数据库 2019 12 27 训练样本 trainingsamples 建立模型 测试样本 testingsamples 评估模型 例 7 错误率为66 67 2019 12 27 4 分类算法的评估 8 预测的准确度 指模型正确地预测新的或先前未见过的数据的类标号的能力 训练测试法 training and testing 交叉验证法 cross validation 例如 十折交叉验证 即是将数据集分成十分 轮流将其中9份做训练1份做测试 10次的结果的均值作为对算法精度的估计 一般还需要进行多次10倍交叉验证求均值 例如10次10倍交叉验证 更精确一点 2019 12 27 2019 12 27 9 速度 指产生和使用模型的计算花费 建模的速度 预测的速度强壮性 指给定噪声数据或具有缺失值的数据 模型正确预测的能力 可诠释性 指模型的解释能力 10 2019 12 27 决策树归纳的基本算法是贪心算法 它以自顶向下递归各个击破的方式构造决策树 贪心算法 在每一步选择中都采取在当前状态下最好 优的选择 在其生成过程中 分割方法即属性选择度量是关键 通过属性选择度量 选择出最好的将样本分类的属性 根据分割方法的不同 决策树可以分为两类 基于信息论的方法 较有代表性的是ID3 C4 5算法等 和最小GINI指标方法 常用的有CART SLIQ及SPRINT算法等 二 决策树 DecisionTree 信息增益 信息越明确 所包含的信息量越大 熵越小 信息增益越大 反正 熵越大比如明天太阳从东边出来 熵最小比如投硬币 谁都不知道下一次将会是那一面 熵最大决策树分裂的基本原则是数据集被分裂为若干个子集后 要使每个子集中的数据尽可能的纯 也就是说子集中的记录要尽可能属于同一个类别 即要使分裂后各子集的熵尽可能的小 要让树尽可能的简洁 不能太复杂 因此选择熵最小的属性作为分裂节点 2019 12 27 11 一 决策树的结构 12 根部节点 rootnode 中间节点 non leafnode 代表测试的条件 分支 branches 代表测试的结果 叶节点 leafnode 代表分类后所获得的分类标记 2019 12 27 2019 12 27 13 二 决策树的形成 例 14 根部节点中间节点停止分支 2019 12 27 三 ID3算法 C4 5 C5 0 15 2019 12 27 Quinlan 1979 提出 以Shannon 1949 的信息论为依据 ID3算法的属性选择度量就是使用信息增益 选择最高信息增益的属性作为当前节点的测试属性 信息论 若一事件有k种结果 对应的概率为Pi 则此事件发生后所得到的信息量I 熵 视为Entropy 为 I p1 log2 p1 p2 log2 p2 pk log2 pk Example1 设k 4 p1 0 25 p2 0 25 p3 0 25 p4 0 25I 25 log2 25 4 2Example2 设k 4 p1 0 p2 0 5 p3 0 p4 0 5I 5 log2 5 2 1Example3 设k 4 p1 1 p2 0 p3 0 p4 0I 1 log2 1 0 2019 12 27 16 2019 12 27 17 信息增益 18 Example Gain n 16n1 4 I 16 4 4 16 log2 4 16 12 16 log2 12 16 0 8113 E 年龄 6 16 I 6 1 10 16 I 10 3 0 7946Gain 年龄 I 16 4 E 年龄 0 0167 Gain 年龄 0 0167 Max 作为第一个分类依据 2019 12 27 Gain 性别 0 0972 Gain 家庭所得 0 0177 Example 续 19 Gain 家庭所得 0 688 I 7 3 3 7 log2 3 7 4 7 log2 4 7 0 9852 Gain 年龄 0 9852 Gain 年龄 0 2222 I 9 1 1 9 log2 1 9 8 9 log2 8 9 0 5032 Gain 家庭所得 0 5032 2019 12 27 Example end ID3算法 20 分类规则 IF性别 FemaleAND家庭所得 低所得THEN购买RV房车 否IF性别 FemaleAND家庭所得 小康THEN购买RV房车 否IF性别 FemaleAND家庭所得 高所得THEN购买RV房车 是IF性别 MaleAND年龄 35THEN购买RV房车 否IF性别 MaleAND年龄 35THEN购买RV房车 是 资料 DecisionTree 2019 12 27 决策树算法 第1步计算决策属性的熵 决策属性 买计算机 该属性分两类 买 不买S1 买 641S2 不买 383S S1 S2 1024P1 641 1024 0 6260P2 383 1024 0 3740I S1 S2 I 641 383 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9537 决策树算法 第2步计算条件属性的熵 条件属性共有4个 分别是年龄 收入 学生 信誉 分别计算不同属性的信息增益 决策树算法 第2 1步计算年龄的熵 年龄共分三个组 青年 中年 老年青年买与不买比例为128 256S1 买 128S2 不买 256S S1 S2 384P1 128 384P2 256 384I S1 S2 I 128 256 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9183 决策树算法 第2 2步计算年龄的熵 年龄共分三个组 青年 中年 老年中年买与不买比例为256 0S1 买 256S2 不买 0S S1 S2 256P1 256 256P2 0 256I S1 S2 I 256 0 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 决策树算法 第2 3步计算年龄的熵 年龄共分三个组 青年 中年 老年老年买与不买比例为125 127S1 买 125S2 不买 127S S1 S2 252P1 125 252P2 127 252I S1 S2 I 125 127 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9157 决策树算法 第2 4步计算年龄的熵 年龄共分三个组 青年 中年 老年所占比例青年组384 1025 0 375中年组256 1024 0 25老年组384 1024 0 375计算年龄的平均信息期望E 年龄 0 375 0 9183 0 25 0 0 375 0 9157 0 6877G 年龄信息增益 0 9537 0 6877 0 2660 1 决策树算法 第3步计算收入的熵 收入共分三个组 高 中 低E 收入 0 9361收入信息增益 0 9537 0 9361 0 0176 2 决策树算法 第4步计算学生的熵 学生共分二个组 学生 非学生E 学生 0 7811年龄信息增益 0 9537 0 7811 0 1726 3 决策树算法 第5步计算信誉的熵 信誉分二个组 良好 优秀E 信誉 0 9048信誉信息增益 0 9537 0 9048 0 0453 4 决策树算法 第6步计算选择节点 年龄信息增益 0 9537 0 6877 0 2660 1 收入信息增益 0 9537 0 9361 0 0176 2 年龄信息增益 0 9537 0 7811 0 1726 3 信誉信息增益 0 9537 0 9048 0 0453 4 决策树算法 年龄 青年 中年 老年 买 不买 买 买 不买 叶子 决策树算法 青年买与不买比例为128 256S1 买 128S2 不买 256S S1 S2 384P1 128 384P2 256 384I S1 S2 I 128 256 P1Log2P1 P2Log2P2 P1Log2P1 P2Log2P2 0 9183 决策树算法 如果选择收入作为节点分高 中 低 平均信息期望 加权总和 E 收入 0 3333 0 0 5 0 9183 0 1667 0 0 4592Gain 收入 I 128 256 E 收入 0 9183 0 4592 0 4591 I 0 128 0比例 128 384 0 3333I 64 128 0 9183比例 192 384 0 5I 64 0 0比例 64 384 0 1667 注意 决策树算法 年龄 青年 中年 老年 学生 买 信誉 叶子 否 是 优 良 买 不买 买 不买 买 叶子 叶子 叶子 决策树算法 ID3决策树建立算法1决定分类属性 2对目前的数据表 建立一个节点N3如果数据库中的数据都属于同一个类 N就是树叶 在树叶上标出所属的类4如果数据表中没有其他属性可以考虑 则N也是树叶 按照少数服从多数的原则在树叶上标出所属类别5否则 根据平均信息期望值E或GAIN值选出一个最佳属性作为节点N的测试属性6节点属性选定后 对于该属性中的每个值 从N生成一个分支 并将数据表中与该分支有关的数据收集形成分支节点的数据表 在表中删除节点属性那一栏如果分支数据表非空 则运用以上算法从该节点建立子树 决策树算法 四 DecisionTree的建立过程 37 1 决策树的停止决策树是通过递归分割 recursivepartitioning 建立而成 递归分割是一种把数据分割成不同小的部分的迭代过程 如果有以下情况发生 决策树将停止分割 该群数据的每一笔数据都已经归类到同一类别 该群数据已经没有办法再找到新的属性来进行节点分割 该群数据已经没有任何尚未处理的数据 2019 12 27 2 决策树的剪枝 pruning 38 决策树学习可能遭遇模型过度拟合 overfitting 的问题 过度拟合是指模型过度训练 导致模型记住的不是训练集的一般性 反而是训练集的局部特性 如何处理过度拟合呢 对决策树进行修剪 树的修剪有几种解决的方法 主要为先剪枝和后剪枝方法 2019 12 27 1 先剪枝方法 39 在先剪枝方法中 通过提前停止树的构造 例如 通过决定在给定的节点上不再分裂或划分训练样本的子集 而对树 剪枝 一旦停止 节点成为树叶 确定阀值法 在构造树时 可将信息增益用于评估岔的优良性 如果在一个节点划分样本将导致低于预定义阀值的分裂 则给定子集的进一步划分将停止 测试组修剪法 在使用训练组样本产生新的分岔时 就立刻使用测试组样本去测试这个分岔规则是否能够再现 如果不能 就被视作过度拟合而被修剪掉 如果能够再现 则该分岔予以保留而继续向下分岔 2019 12 27 2 后剪枝方法 40 后剪枝方法是由 完全生长 的树剪去分枝 通过删除节点的分枝 剪掉叶节点 案例数修剪是在产生完全生长的树后 根据最小案例数阀值 将案例数小于阀值的树节点剪掉 成本复杂性修剪法是当决策树成长完成后 演算法计算所有叶节点的总和错误率 然后计算去除某一叶节点后的总和错误率 当去除该叶节点的错误率降低或者不变时 则剪掉该节点 反之 保留 2019 12 27 应用案例 在农业中的应用 2019 12 27 41 第一步 属性离散化 2019 12 27 42 第二步 概化 泛化 2019 12 27 43 第三步 计算各属性的期望信息 2019 12 27 44 17 30 LOG 17 30 2 10 30 LOG 10 30 2 3 30 LOG 3 30