决策树--PPT.ppt

决策树 根据李峰等人的PPT改编课件主要依据李航编写的 统计学习方法 编制 清华大学出版社另一本参考书 数据挖掘与数学建模 国防工业出版社2010 决策树 1 1决策树模型与学习1 2特征选择1 3决策树的生成1 4决策树的剪枝1 5CART算法 1 1决策树模型与学习 1 1 1决策树模型1 1 2决策树与if then规则1 1 3决策树与条件概率分布1 1 4决策树学习 1 1 1决策树模型 什么是决策树 定义1 1 决策树 分类决策树模型是一种描述对实例进行分类的树形结构 决策树由结点和有向边组成 结点有两种类型 内部结点和叶节点 内部结点表示一个特征或属性 叶节点表示一个类 决策树学习算法的特点 决策树学习算法的最大优点是 它可以自学习 在学习的过程中 不需要使用者了解过多背景知识 只需要对训练实例进行较好的标注 就能够进行学习 显然 它属于有监督学习 从一类无序 无规则的事物 概念 中推理出决策树表示的分类规则 决策树学习的主要算法 建立决策树的关键 即在当前状态下选择哪个属性作为分类依据 根据不同的目标函数 建立决策树主要有一下三种算法 ID3 J RossQuinlan 1975 核心 信息熵C4 5 ID3的改进 核心 信息增益比CART Breiman 1984 核心 基尼指数 例1 找对象 决策树分类的思想类似于找对象 现想象一个女孩的母亲要给这个女孩介绍男朋友 于是有了下面的对话 女儿 多大年纪了 年龄 母亲 26 女儿 长的帅不帅 长相 母亲 挺帅的 女儿 收入高不 收入情况 母亲 不算很高 中等情况 女儿 是公务员不 是否公务员 母亲 是 在税务局上班呢 女儿 那好 我去见见 1 1 2决策树与if then规则 由决策树的根结点到叶结点的每一条路径构建一条规则 路径上内部结点的特征对应着规则的条件 而叶结点的类对应着规则的结论 If then规则集合的一重要性质 互斥并且完备 1 1 3决策树与条件概率分布 将特征空间划分为互不相交的单元或区域 并在每个单元定义一个类的概率分布就构成了一个条件概率分布 各叶结点 单元 上的条件概率往往偏向某一个类 即属于某一类的概率较大 决策树分类时将该结点的实例强行分到条件概率大的那一类去 1 1 4决策树学习 1 1 4决策树学习 目标 我们需要的是一个与训练数据矛盾较小的决策树 同时具有很好的泛化能力 决策树学习的损失函数 通常是 正则化的极大似然函数 但是基于损失函数找到全局最优决策树是NP 完全问题 现实中决策树学习通常采用启发式方法 即局部最优 具体做法 每次选择feature时 都挑选择当前条件下最优的那个feature作为划分规则 即局部最优的feature 1 2特征选择1 2 1特征选择问题 特征选择在于选取对训练数据具有分类能力的特征 如何判断一个特征对于当前数据集的分类效果 也即确定选择特征的准则 例1 2右表是一个由15个样本组成的贷款申请训练数据 数据包括贷款申请人的四个特征 表的最后一列是类别 是否同意贷款 取2个值 是 否 希望通过所给的训练数据学习一个贷款申请的决策树 用以对未来的贷款申请进行分类 特征选择是决定用哪个特征来划分特征空间 1 2 2信息增益 熵 就分类而言 所有成员都属于一类 熵为零 不同类别数目相等 则熵等于1 类别数目不等 则熵介于0 1之间 条件熵 信息增益 信息增益的具体公式 信息增益算法 例1 3对表1 1所给的训练数据集D 根据信息增益准则选择最优特征 1 2 3信息增益比 1 3决策树的生成1 3 1ID3算法 例1 4对表1 1的训练数据集 利用ID3算法建立决策树 有自己的房子 A3 是 否 表1 表2 有自己的房子 是 否 是 是 否 有工作 表3 表4 这里生成的决策树只用到两个特征 两个内节点 ID3算法容易存在过拟合问题 补充 如何解决决策树的过拟合问题 概念 原因 解决 什么是过度拟合数据 过度拟合数据是怎么产生的 怎么去解决这个问题 补充 如何解决决策树的过拟合问题 概念 过度拟合 overfitting 如果决策树对训练样本的特征描述得 过于精确 无法实现对新样本的合理分析 所以此时它不是一棵分析新数据的最佳决策树 一棵完全决策树能非常准确地反映训练集中数据的特征 但因失去了一般代表性而无法用于对新数据的分类或预测 这种现象一般称为 过拟合 定义 给定一个假设H 如果在假设空间上存在另一个假设H 使得在训练集上H的错误率差比H 小 而在测试集上H的错误率却比H 要大 那么称假设H过度拟合训练数据 二 产生过度拟合数据问题的原因有哪些 原因1 样本问题 1 样本里的噪音数据干扰过大 大到模型过分记住了噪音特征 反而忽略了真实的输入输出间的关系 什么是噪音数据 2 样本抽取错误 包括 但不限于 样本数量太少 抽样方法错误 抽样时没有足够正确考虑业务场景或业务特点 等等导致抽出的样本数据不能有效足够代表业务逻辑或业务场景 3 建模时使用了样本中太多无关的输入变量 原因2 构建决策树的方法问题在决策树模型搭建中 我们使用的算法对于决策树的生长没有合理的限制和修剪的话 决策树的自由生长有可能每片叶子里只包含单纯的事件数据或非事件数据 可以想象 这种决策树当然可以完美匹配 拟合 训练数据 但是一旦应用到新的业务真实数据时 效果是一塌糊涂 三 如何解决过度拟合数据问题 针对原因1的解决方法 合理 有效地抽样 用相对能够反映业务逻辑的训练集去产生决策树 针对原因2的主要解决方法 剪枝 提前停止树的增长或者对已经生成的树按照一定的规则进行后剪枝 1 3 2C4 5的生成算法 C4 5算法与ID3算法相似 C4 5算法对ID3算法进行了改进 C4 5在生成的过程中 用信息增益比来选择特征 1 4决策树的剪枝 算法1 4树的剪枝算法 关于剪枝的补充 先剪枝 剪枝是一个简化过拟合决策树的过程 有两种常用的剪枝方法 先剪枝 prepruning 通过提前停止树的构建而对树 剪枝 一旦停止 节点就成为树叶 该树叶可以持有子集元组中最频繁的类 有多种不同的方式可以让决策树停止生长 下面介绍几种停止决策树生长的方法 1 定义一个高度 当决策树达到该高度时就可以停止决策树的生长 这是一种最为简单的方法 2 达到某个结点的实例具有相同的特征向量 即使这些实例不属于同一类 也可以停止决策树的生长 这种方法对于处理数据中的数据冲突问题非常有效 补充 关于剪枝 先剪枝 3 定义一个阈值 当达到某个结点的实例个数小于该阈值时就可以停止决策树的生长 4 定义一个阈值 通过计算每次扩张对系统性能的增益 并比较增益值与该阈值的大小来决定是否停止决策树的生长 先剪枝方法不但相对简单 效率很高 而且不需要生成整个决策树 适合于解决大规模问题 该方法看起来很直接 但要精确地估计决策树生长的停止时间并不容易 即选取一个恰当的阈值是非常困难的 高阈值可能导致过分简化的树 而低阈值可能使得树的简化太少 关于剪枝的补充 后剪枝 后剪枝 postpruning 它首先构造完整的决策树 允许树过度拟合训练数据 然后对那些置信度不够的结点子树用叶子结点来代替 该叶子的类标号用该结点子树中最频繁的类标记 相比于先剪枝 这种方法更常用 正是因为在先剪枝方法中精确地估计何时停止树增长很困难 补充 关于剪枝的准则 无论是通过及早停止还是后修剪来得到正确规模的树 一个关键的问题是使用什么样的准则来确定最终正确树的规模 1 使用训练集合 TrainingSet 和验证集合 ValidationSet 来评估剪枝方法在修剪结点上的效用 2 使用所有的训练集合进行训练 但是用统计测试来估计修剪特定结点是否会改善训练集合外的数据的评估性能 测试来进一步扩展结点是否能改善整个分类数据的性能 还是仅仅改善了当前训练集合数据上的性能 3 使用明确的标准来衡量训练样例和决策树的复杂度 当编码长度最小时 停止树增长 如MDL MinimumDescriptionLength 准则 补充 关于剪枝的准则 Reduced ErrorPruning REP 错误率降低剪枝 REP方法是一种比较简单的后剪枝的方法 在该方法中 可用的数据被分成两个样例集合 一个训练集用来形成学习到的决策树 一个分离的验证集用来评估这个决策树在后续数据上的精度 确切地说是用来评估修剪这个决策树的影响 这个方法的动机是 即使学习器可能会被训练集中的随机错误和巧合规律所误导 但验证集合不大可能表现出同样的随机波动 所以验证集可以用来对过度拟合训练集中的虚假特征提供防护检验 REP 错误率降低剪枝 该剪枝方法考虑将树上的每个节点作为修剪的候选对象 决定是否修剪这个结点由如下步骤组成 1 删除以此结点为根的子树2 使其成为叶子结点3 赋予该结点关联的训练数据的最常见分类4 当修剪后的树对于验证集合的性能不会比原来的树差时 才真正删除该结点训练集合可能过拟合 使用验证集合数据能够对其进行修正 反复进行上面的操作 从底向上的处理结点 删除那些能够最大限度的提高验证集合的精度的结点 直到进一步修剪有害为止 有害是指修剪会减低验证集合的精度 Pesimistic ErrorPruning PEP 悲观错误剪枝 悲观错误剪枝法是根据剪枝前后的错误率来判定子树的修剪 该方法引入了统计学上连续修正的概念弥补REP中的缺陷 在评价子树的训练错误公式中添加了一个常数 假定每个叶子结点都自动对实例的某个部分进行错误的分类 把一棵子树 具有多个叶子节点 的分类用一个叶子节点来替代的话 在训练集上的误判率肯定是上升的 但是在新数据上不一定 于是我们需要把子树的误判计算加上一个经验性的惩罚因子 PEP 悲观错误剪枝 对于一个叶子节点 它覆盖了N个样本 其中有E个错误 那么该叶子节点的错误率为 E 0 5 N 这个0 5就是惩罚因子 那么一棵子树 它有L个叶子节点 那么该子树的误判率估计为这样的话 我们可以看到一棵子树虽然具有多个子节点 但由于加上了惩罚因子 所以子树的误判率计算未必占到便宜 剪枝后内部节点变成了叶子节点 其误判个数J也需要加上一个惩罚因子 变成J 0 5 那么子树是否可以被剪枝就取决于剪枝后的错误J 0 5在 PEP续的标准误差内 对于样本的误差率e 我们可以根据经验把它估计成各种各样的分布模型 比如是二项式分布 比如是正态分布 那么一棵树错误分类一个样本值为1 正确分类一个样本值为0 该树错误分类的概率 误判率 为e e为分布的固有属性 可以通过统计出来 那么树的误判次数就是伯努利分布 我们可以估计出该树的误判次数均值和标准差 PEP续把子树替换成叶子节点后 该叶子的误判次数也是一个伯努利分布 其概率误判率e为 E 0 5 N 因此叶子节点的误判次数均值为使用训练数据 子树总是比替换为一个叶节点后产生的误差小 但是使用校正后有误差计算方法却并非如此 当子树的误判个数大过对应叶节点的误判个数一个标准差之后 就决定剪枝 这个条件就是剪枝的标准 当然并不一定非要大一个标准差 可以给定任意的置信区间 我们设定一定的显著性因子 就可以估算出误判次数的上下界 PEP 小例题 T4这棵子树的误差率 子树误判次数的标准误差 子树替换为一个叶节点后 其误判个数为 7 0 5 7 5因为8 5 1 996 7 5 所以决定将子树T4替换这一个叶子节点 Cost ComplexityPruning CCP 代价复杂度剪枝 该算法为子树Tt定义了代价 cost 和复杂度 complexity 以及一个可由用户设置的衡量代价与复杂度之间关系的参数 其中 代价指在剪枝过程中因子树Tt被叶节点替代而增加的错分样本 复杂度表示剪枝后子树Tt减少的叶结点数 则表示剪枝后树的复杂度降低程度与代价间的关系 定义为其中 N1 子树Tt中的叶节点数 R t 结点t的错误代价 计算公式为R t r t p t r t 为结点t的错分样本率 p t 为落入结点t的样本占所有样本的比例 R Tt 子树Tt错误代价 计算公式为R Tt R i i为子树Tt的叶节点 例子 我们以非叶结点T4为例 假设已有的数据有60条 那么R t r t p t 7 16 16 60 7 60R Tt R i 2 5 5 60 0 2 2 60 3 9 9 60 5 60 R t R Tt N1 1 1 60 CCP续 CCP剪枝算法分为两个步骤 1 对于完全决策树T的每个非叶结点计算 值 循环剪掉具有最小 值的子树 直到剩下根节点 在该步可得到一系列的剪枝树 T0 T1 T2 Tm 其中T0为原有的完全决策树 Tm为根结点 Ti 1为对Ti进行剪枝的结果 2 从子树序列中 根据真实的误差估计选择最佳决策树 CCP续 通常使用1 SE 1standarderrorofminimumerror 规则从步骤1产生的一系列剪枝树中选择一棵最佳的剪枝决策树 方法为 假定一个含有N 个样本的剪枝集 分别用在步骤1中产生的剪枝树Ti对该剪枝集进行分类 记Ti所有叶结点上长生的错分样本数为Ei 令E min Ei 定义E 的标准错误为 所得的最佳剪枝树Tbest是满足条件Ei E SE E 且包含的接点数最少的那棵剪枝树Ti 几种后剪枝方法的比较 1 5CART 分类与回归树 算法 CART同样由特征选择 树的生成及剪枝组成 既可以用于分类也可以用于回归 CART假设决策树是二叉树 内部结点特征的取值为 是 和 否 这样的决策树等价于递归地二分每个特征 步骤 1 决策树生成 基于训练数据集生成决策树 生成的决策树要尽量大 2 决策树剪枝 用验证数据集对已生成的树进行剪枝并选择最优子树 这时用损失函数最小作为剪枝的标准 1 5 1CART生成 决策树的生成就是递归地构建二叉决策树的过程 对回归树用平方误差最小化准则 对分类树用基尼指数 Giniindex 最小化准则 进行特征选择 生成二叉树 最开始我们可以按 表面覆盖为毛发与非毛发表面覆盖为鳞片与非鳞片恒温与非恒温来产生当前结点的左右两个孩子 我们将Gini指数来作为准则判别哪种划分比较好 GINI指数 1 5 2CART剪枝 实验结果 解决决策树过拟合的另一种方法 随机森林 Bootstraping Bootstraping的名称来自成语 pullupbyyourownbootstraps 意思是依靠你自己的资源 称为自助法 它是一种有放回的抽样方法 注 Bootstrap本义是指高靴子口后面的悬挂物 小环 带子 是穿靴子时用手向上拉的工具 pullupbyyourownbootstraps 即 通过拉靴子让自己上升 意思是 不可能发生的事情 后来意思发生了转变 隐喻 不需要外界帮助 仅依靠自身力量让自己变得更好 解决决策树过拟合的另一种方法 随机森林 组合模型 Bagging的策略 三个臭皮匠顶个诸葛亮的意思 bootstrapaggregation 从样本集中重采样 有重复的 选出n个样本 在所有属性上 对这n个样本建立分类器 ID3 C4 5 CART SVM Logistic回归等 重复以上两步m次 即获得了m个分类器 将数据放在这m个分类器上 最后根据这m个分类器的投票结果 决定数据属于哪一类 解决决策树过拟合的另一种方法 随机森林 解决决策树过拟合的另一种方法 随机森林 随机森林应用非常广泛 根据目标变量的取值类型大致可分为两类一种是分类 当目标变量取值为离散型时 属性变量 种类变量 有序变量 多级变量等 采用该法可进行分类 当目标变量为连续型 则可做回归 对应的预测结果是目标变量的分布 优点 可以产生高准确度的分类器 解决决策树过拟合的另一种方法 随机森林 随机森林在bagging基础上做了修改 从样本集中用Bootstrap采样选出n个样本 从所有属性中随机选择k个属性 选择最佳分割属性作为节点建立CART决策树 重复以上两步m次 即建立了m棵CART决策树 这m个CART形成随机森林 通过投票表决结果 决定数据属于哪一类 解决决策树过拟合的另一种方法 随机森林 随