第4章分类基本概念、决策树与模型评估.ppt

第4章分类 基本概念 决策树与模型评估 4 1预备知识4 2解决分类问题的一般方法4 3决策树归纳4 4模型的过分拟合4 5评估分类器的性质4 6比较分类器的方法 分类任务 确定对象属于哪个预定义的目标类 例子 1 根据电子邮件的标题和内容检查出垃圾邮件 2 根据星系的形状对它们分类 螺旋状的星系 椭圆状的星系 一 预备知识 分类任务的输入数据是记录的集合 每条记录也称实例或者样例 用元组 x y 表示 其中x是属性的集合 而y是一个特殊的属性 指出样例的类标号 也成为分类属性或目标属性 分类 回归 分类 classification 通过学习得到一个目标函数 targetfunction 也成为分类模型 classificationmodel 把每个属性集x映射到一个预先定义的类标号y 目的 1 描述性建模分类模型可以作为解释性的工具 用于区分不同类中的对象 2 预测性建模分类模型还可以用于预测未知记录的类标号 输入属性集 x 分类模型 输出类标号 y 分类器的任务 根据输入属性集x确定类标号y 分类技术非常适合预测或描述二元或标称类型的数据集 对序数分类不太有效 因为分类技术不考虑隐含在目标类中的序关系 分类技术是一种根据输入数据集建立分类模型的系统方法 分类技术 决策树分类法 基于规则的分类法 神经网络 支持向量机 这些技术都使用一种学习算法确定分类模型 修改这个模型能够很好地拟合输入数据中类标号和属性集之间的联系 学习算法得到的模型不仅要很好地拟合输入数据 还要能够正确地预测未知样本的类标号 训练算法的目标 建立具有很好的泛化能力的模型 二 解决分类问题的一般方法 朴素贝叶斯分类法 训练集 由类标号已知的记录构成检验集 由类标号未知的记录构成 二类问题的混淆矩阵 表中每个表项表示实际类标号为但是被预测为类的记录数 被分类模型正确预测的样本总数是 而被错误预测的样本总数是 虽然混淆矩阵提供衡量分类模型的信息 但是用一个数汇总这些信息更便于比较不同模型的性能 为实现这一目的 可以使用性能度量 performancemetric 如准确率 accuracy 其定义如下 同样 分类模型的性能也可以用错误率 errorrate 来表示 其定义如下 目标 寻求最高的准确率或者最低的错误率 1 什么是决策树 类似于流程图的树结构每个内部节点表示在一个属性上的测试每个分枝代表一个测试输出每个叶节点代表类或类分布 三 决策树 decisiontree 归纳 3 决策树的使用 对未知样本进行分类通过将样本的属性值与决策树相比较 2 决策树的生成由两个阶段组成决策树构建开始时 所有的训练样本都在根节点递归通过选定的属性 来划分样本 必须是离散值 树剪枝许多分枝反映的是训练数据中的噪声和孤立点 树剪枝试图检测和剪去这种分枝 根结点 rootnode 它没有入边 但是有零条或多条出边 内部结点 internalnode 恰好有一条入边和两条或多条出边 叶节点 leafnode 或终结点 terminalnode 恰好有一条入边 但没有出边 叶结点 根结点 内部结点 一旦构造了决策树 对检验记录进行分类就很容易 从树的根结点开始 将测试条件用于检验记录 根据测试结果选择适当的分支 沿着该分支或者到达另一个内部结点 使用新的测试条件 或者到达一个叶结点 到达叶结点之后 叶结点的类标号就被赋值给该检验记录 恒温 否 冷血 是 如何建立决策树 对于给定的属性集 可以构造的决策树的数目达指数级 尽管某些决策树比其他决策树更准确 但是由于搜索空间是指数规模的 找出最佳决策树在计算上是不可行的 尽管如此 人们还是开发了一些有效的算法 能够在合理的时间内构造出具有一定准确率的次最优决策树 这些算法通常都采用贪心策略 有许多决策树算法 Hunt算法信息增益 Informationgain ID3 增益比率 Gainration C4 5 基尼指数 Giniindex SLIQ SPRINT 在Hunt算法中 通过将训练记录相继划分成较纯的子集 以递归方式建立决策树 设是与结点t相关联的训练记录集 而是类标号 Hunt算法的递归定义如下 1 如果中所有记录都属于同一个类 则t是叶结点 用标记 2 如果中包含属于多个类的记录 则选择一个属性测试条件 将记录划分成较小的子集 对于测试条件的每个输出 创建一个子女结点 并根据测试结果将中的记录分布到子女结点中 然后 对于每个子女结点 递归地调用该算法 Hunt算法 拖欠贷款者 否 拖欠贷款者 否 拖欠贷款者 否 有房者 拖欠贷款者 否 有房者 拖欠贷款者 否 婚姻状况 年收入 拖欠贷款者 是 拖欠贷款者 否 b c d a 拖欠贷款者 否 有房者 拖欠贷款者 否 婚姻状况 拖欠贷款者 是 是 是 否 否 否 是 单身离异 单身离异 已婚 已婚 80k 80k Hunt算法构造决策树 如果属性值的每种组合都在训练数据中出现 并且每种组合都具有唯一的类标号 则Hunt算法是有效的 但是对于大多数实际情况 这些假设太苛刻了 因此 需要附加的条件来处理以下的情况 1 算法的第二步所创建的子女结点可能为空 即不存在与这些结点相关联的记录 如果没有一个训练记录包含这样的结点相关联的属性值组合 这种情形就可能发生 这时 该结点成为叶结点 类标号为其父结点上训练记录中的多数类 2 在第二步 如果与相关联的所有记录都具有相同的属性值 目标属性除外 则不可能进一步划分这些记录 在这种情况下 该结点为叶结点 其标号为与该结点相关联的训练记录中的多数类 决策树归纳的设计问题 1 如何分裂训练记录 2 如何停止分裂过程 树增长过程的每个递归步骤都必须选择一个属性测试条件 将记录划分成较小的子集 为了实现这个步骤 算法必须提供为不同类型的属性指定测试条件的方法 并且提供评估每种测试条件的客观度量 决策树需要有结束条件 以终止决策树的生长过程 一个可能的策略是分裂结点 直到所有的记录都属于同一个类 或者所有的记录都具有相同的属性值 表示属性测试条件的方法 1 二元属性二元属性的测试条件产生两个可能的输出 体温 恒温 冷血 二元属性的测试条件 2 标称属性由于标称属性有多个属性值 它的测试条件可以用两种方法表示 婚姻状况 单身 已婚 离异 婚姻状况 已婚 单身 离异 婚姻状况 离异 单身 已婚 婚姻状况 单身 已婚 离异 多路划分 二元划分 通过属性值分组 3 序数属性序数属性也可以产生二元或多路划分 只要不违背序数属性值的有序性 就可以对属性值进行分组 衬衣尺码 小号 中号 大号 加大号 衬衣尺码 小号 中号 加大号 衬衣尺码 小号 大号 中号 加大号 a b c 4 连续属性对于连续属性来说 测试条件可以是具有二元输出的比较测试或也可以是具有形如输出的范围查询 年收入 80k a b 年收入 是 否 10k 10k 25k 10k 25k 50k 50k 80k 连续属性的测试条件 有很多度量可以用来确定划分记录的最佳方法 这些度量用划分前和划分后的记录的类分布定义 选择最佳划分的度量 设表示给定结点t中属于类i的记录所占的比例 有时 我们省略结点t 直接用表示该比例 在两类问题中 任意结点的类分布都可以记作其中 性别 男 女 车型 家用 运动 豪华 C0 6C1 4 C0 4C1 6 C0 1C1 3 C0 8C1 0 C0 1C1 7 b a C0 1C1 0 C0 1C1 0 C0 0C1 1 C0 0C1 1 顾客ID v1 v10 v20 v11 c 选择最佳划分的度量通常是根据划分后子女结点不纯性的度量 不纯的程度越低 类分布就越倾斜 例如 0 1 的结点具有零不纯性 而均衡分布 0 5 0 5 的结点具有最高的不纯性 不纯性度量的例子包括 熵 基尼指数 分类误差 其中c是类的个数 并且在计算熵时 二元分类问题不纯性度量之间的比较 不同的不纯性度量是一致的 但是作为测试条件的属性选择仍然因不纯性度量的选择而异 为确定测试条件的效果 我们需要比较父结点 划分前 的不纯性程度和子女结点 划分后 的不纯性程度 它们的差越大 测试条件的效果就越好 增益是一种可以用来确定划分效果的标准 其中 是给定结点的不纯性度量 N是父结点上的记录总数 k是属性值的个数 是与子女结点相关联的记录个数 决策树算法选择最大化增益的测试条件 B 是 否 结点N1 结点N2 A 是 否 结点N1 结点N2 1 二元属性的划分 2 标称属性的划分 a 二元划分 b 多路划分 标称属性可以产生二元划分或者多路划分 3 连续属性的划分 1 使用二元划分2 划分点v选择N个记录中所有属性值作为划分点3 对每个划分进行类计数 A v和A v4 计算每个候选点v的Gini指标 并从中选择具有最小值的候选划分点5 时间复杂度为O n2 降低计算复杂性的方法 1 将记录进行排序2 从两个相邻的排过序的属性值之间选择中间值作为划分点3 计算每个候选点的Gini值4 时间复杂度为O NlogN 4 增益率 熵和Gini指标等不纯性度量趋向有利于具有大量不同值的属性 性别 男 女 车型 家用 运动 豪华 C0 6C1 4 C0 4C1 6 C0 1C1 3 C0 8C1 0 C0 1C1 7 b a 测试条件 车型 要比测试条件 性别 要好 因为它产生了更纯的派生结点 测试条件 顾客ID 相比前两个产生更纯的划分 但是它却不是一个有预测性的属性 因为与每个划分相关联的记录太少 以致不能作出可靠的预测 C0 1C1 0 C0 1C1 0 C0 0C1 1 C0 0C1 1 顾客ID v1 v10 v20 v11 c 如何解决 第一种策略 限制测试条件只能是二元划分 第二种策略 修改评估划分的标准 把属性测试条件产生的输出数也考虑进去 例如 CART就是采用这样的策略 例如 决策树算法C4 5采用增益率 gainratio 的划分标准来评估划分 决策树归纳特点的总结 1 决策树归纳是一种构建分类模型的非参数方法 2 找到最佳的决策树是NP完全问题 3 已开发的构建决策树技术不需要昂贵的计算代价 即使训练集非常大 也可以快速建立模型 4 决策树相对容易解释 特别是小型的决策树 5 决策树是学习离散值函数的典型代表 6 决策树算法对于噪声的干扰具有相当好的鲁棒性 7 冗余属性不会对决策树的准确率造成不利的影响 8 由于大多数决策树算法都采用自顶向下的递归划分方法 因此沿着树向下 记录会越来越少 9 子树可能在决策树中重复多次 这使得决策树过于复杂 并且可能更难解释 10 目前为止 本章介绍的测试条件每次都只涉及一个属性 二维数据集的决策树及其边界示例 使用仅涉及单个属性的测试条件不能有效划分的数据集的例子 斜决策树 obliquedecisiontree 可以克服以上的局限 因为它允许测试条件涉及多个属性 上图中的数据集可以很容易地用斜决策树表示 该决策树只有一个结点 其测试条件为 缺点 尽管这种技术有更强的表达能力 并且能够产生更紧凑的决策树 但是为给定的结点找出最佳测试条件的计算可能是相当复杂的 构造归纳 constructiveinduction 提供另一种将数据划分成齐次非矩形区域的方法 该方法创建复合属性 代表已有属性的算术或逻辑组合 新属性提供了更好的类区分能力 并在决策树归纳之前就增广到数据集中 与决策树不同 构造归纳不需要昂贵的花费 因为在构造决策树之前 它只需要一次性地确定属性的所有相关组合 相比之下 在扩展每个内部结点时 斜决策树都需要动态地确定正确的属性组合 然而构造归纳会产生冗余的属性 因为新创建的属性是已有属性的组合 11 研究表明不纯性度量方法的选择对决策树算法的性能影响很小 一个好的分类模型必须具有低训练误差和低泛化误差 四 模型的过分拟合 二维数据过分拟合的例子 下图所示的二维数据集中的数据点属于两个类 分别标记为类 o 和类 类 o 的数据点由三个高斯分布混合产生 而类 的数据点用一个均匀分布产生 数据集中 总共有1200个数据点是属于类 o 1800个数据点属于类 其中30 的点用于训练 剩下的70 用于检验 对训练集使用以Gini指标作为不纯性度量的决策树方法 具有两个类的数据集的例子 当决策树很小时 训练误差和检验误差都很大 这种情况称作模型拟合不足 modelunderfitting 出现拟合不足的原因是模型尚未学习到数据的真实结构 因此 模型在训练集和检验集上的性能都很差 一旦树的规模变得太大 即使训练误差还在降低 但是检验误差开始增大 这种现象称为模型过分拟合 modeloverfitting 训练误差和检验误差 为理解过分拟合现象 举个例子 可以扩展树的叶结点 直到它完全拟合训练数据 虽然这样一颗复杂的树的训练误差为0 但是检验误差可能很大 因为该树可能包含这样的结点 它们偶然地拟合训练数据中某些噪声 这些结点降低了决策树的性能 因为他们不能很好的泛化到检验样本 a 包含11个叶结点的决策树 b 包含24个叶结点的决策树 过分拟合与拟合不足是两种与模型复杂度有关的异常现象 哺乳动物分类的训练数据集样本 为错误标记记录 十个训练记录中有两个被错误标记 蝙蝠和鲸被错误标记为非哺乳动物 而不是哺乳动物 噪声导致的过分拟合 哺乳动物分类的检验数据集样本 完全拟合训练数据的决策树显示在下图 a 中 虽然该树的训练误差为0 但是它在检验数据集上的误差高达30 体温 恒温 冷血 胎生 4条腿 哺乳类动物 非哺乳类动物 非哺乳类动物 非哺乳类动物 是 否 是 否 体温 恒温 冷血 胎生 非哺乳类动物 非哺乳类动物 是 否 哺乳类动物 a 模型M1 b 模型M2 图 b 中决策树M2尽管训练误差较高 20 但是它具有较低的检验误差 缺乏代表性样本导致的过分拟合 体温 恒温 冷血 冬眠 4条腿 哺乳类动物 非哺乳类动物 非哺乳类动物 非哺乳类动物 是 否 是 否 人 大象和海豚都被误分类 因为决策树把恒温但不冬眠的脊柱动物划分为非哺乳动物 决策树做出这样的分类决策是因为只有一个训练记录 鹰 具有这些特性 过分拟合与多重比较过程 1 在决策树增长过程中 可以进行多种测试 以确定哪个属性能够最好的划分训练数据 2 在这种情况下 算法实际上是使用多重比较过程来决定是否需要扩展决策树 3 当候选属性多 训练记录数少时 这种影响就变得更加明显 多重比较过程与模型过分拟合有什么关系 1 过分拟合的主要原因一直是个争辩的话题 但大家还是普遍同意模型的复杂度对模型的过分拟合有影响 2 如何确定正确的模型复杂度 理想的复杂度是能产生最低泛化误差的模型的复杂度 3 估计泛化误差的方法使用再代入估计 用训练误差提供对泛化误差的乐观估计结合模型复杂度估计统计上界使用确定集 泛化误差估计 泛化误差估计 1 使用再代入估计 再代入估计方法假设训练数据集可以很好地代表整体数据 因而 可以使用训练误差 又称再代入误差 提供泛化误差的乐观估计 但是训练误差通常是泛化误差的一种很差的估计 考虑下图中的二叉决策树 假设两颗决策树都由相同的训练数据产生 并且都根据每个叶结点多数类做出划分 注意 左边的树T1复杂一些 它扩展了右边决策树T2的某些结点 左决策树的训练误差是 而右决策树的训练误差是 根据再代入估计 左决策树要优于右决策树 3 0 3 1 1 2 0 2 2 1 3 1 0 5 3 6 3 0 1 4 5 2 决策树T1 决策树T2 2 结合模型复杂度 如之前所述 模型越是复杂 出现过分拟合的几率就越高 因此 我们更喜欢采用较为简单的模型 这种策略与应用众所周知的奥卡姆剃刀一致 奥卡姆剃刀 给定两个具有相同泛化误差的模型 较简单的模型比较复杂的模型更可取 悲观误差评估 使用训练误差与模型复杂度罚项 penaltyterm 的和计算泛化误差 结果泛化误差可以看作模型的悲观误差估计 设n t 是结点t分类的训练记录数 e t 是被误分类的记录数 决策树T的悲观误差估计可以用下式计算 其中 k是决策树的叶结点数 e T 是决策树的总训练误差 是训练记录数 是每个结点对应的罚项 3 0 3 1 1 2 0 2 2 1 3 1 0 5 3 6 3 0 1 4 5 2 决策树T1 决策树T2 考虑上图的二叉决策树 如果罚项等于0 5 左边的决策树的悲观误差估计为 右边的决策树的悲观误差估计为 此时 左边的决策树比右边的决策树具有更好的悲观误差估计 最小描述长度原则 minimumdescriptionlength MDL 标记的 未标记的 Cost是传输总代价 目标 最小化Cost值 其中Cost Data Model 是误分类记录编码的开销 Cost Model 是模型编码的开销 另一种可能是 A决定建立一个分类模型 概括X和y点之间的关系 Cost Model Data Cost Data Model Cost Model 3 估计统计上界 泛化误差也可以用训练误差的统计修正来估计 因为泛化误差倾向于比训练误差大 所以统计修正通常是计算训练误差的上界 4 使用确认集 在该方法中 不是用训练集估计泛化误差 而是把原始的训练数据集分为两个较小的子集 一个子集用于训练 而另一个称为确认集 用于估计泛化误差 2 3训练集 建立模型 误差估计 1 3训练集 该方法通常用于通过参数控制获得具有不同复杂度模型的分类技术 通过调整学习算法中的参数 直到学习算法产生的模型在确认集上达到最低的错误率 可以估计最佳模型的复杂度 处理决策树归纳中的过分拟合 先剪枝 提前终止规则 树增长算法在产生完全拟合整个训练数据集的之前就停止决策树的生长为了做到这一点 需要采用更具限制性的结束条件 当结点的记录数少于一定阈值 则停止生长当不纯性度量的增益低于某个确定的阈值时 则停止生长 e g informationgain 缺点 很难为提前终止选取正确的阈值 1 阈值太高 导致拟合不足 2 阈值太低 导致不能充分解决过分拟合的问题 后剪枝在该方法中 初始决策树按照最大规模生长 然后进行剪枝的步骤 按照自底向上的方式修剪完全增长的决策树 修剪有两种做法 1 用新的叶结点替换子树 该叶结点的类标号由子树下记录中的多数类定 2 用子树中最常用的分支代替子树 五 评估分类器的性能 一 保持 Holdout 方法 将被标记的原始数据划分成两个不相交的集合 分别成为训练集和检验集 在训练集上归纳分类模型 在检验集上评估模型的性能 局限性 1 用于训练的被标记样本较少 2 模型可能高度依赖于训练集和检验集的构成 二 随机二次抽样 randomsubsampling 随机二次抽样可以多次重复保持方法来改进分类器性能的估计 由于它没有控制每个记录用于训练和检验的次数 因此 有些用于训练的记录使用的频率可能比其他记录高得多 三 交叉验证 cross validation 在该方法中 每个记录用于训练的次数相同 并且恰好检验一次 例 假设把数据分为相同大小的两个子集 首先 我们选择一个子集作训练集 而另一个作检验集 然后交换两个集合的角色 原先作训练集的现在作检验集 反之亦然 这种方法叫做二折交叉验证 四 自助 bootstrap 法 在自助法中 训练记