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

1、第4章 分类：基本概念、决策树与模型评估分类：基本概念、决策树与模型评估 4.1预备知识 4.2解决分类问题的一般方法 4.3决策树归纳 4.4模型的过分拟合 4.5评估分类器的性质 4.6比较分类器的方法 分类任务：确定对象属于哪个预定义的目标类 例子： 1、根据电子邮件的标题和内容检查 出垃圾邮件。 2、根据星系的形状对它们分类。 螺旋状的星系 椭圆状的星系 一、预备知识一、预备知识 分类任务的输入数据是记录的集合。每条记录也称实例或者样例， 用元组（x, y）表示，其中x是属性的集合，而y是一个特殊的属性， 指出样例的类标号（也成为分类属性或目标属性）。 分类？回归？ 分类（classi

2、fication） 通过学习得到一个目标函数（target function） ， 也成为分类模 型（classification model），把每个属性集x映射到一个预先定义的类标 号y。 f 目的： 1、描述性建模 分类模型可以作为解释性的工具，用于区分不同类中的对象。 2、预测性建模 分类模型还可以用于预测未知记录的类标号。 名字名字体温体温表皮表皮 覆盖覆盖 胎生胎生水生水生 动物动物 飞行飞行 动物动物 有腿有腿冬眠冬眠类标类标 号号 毒蜥冷血鳞片否否否是是？ 输入属性集（x） 分类模型 输出类标号（y） 分类器的任务：根据输入属性集x确定类标号y 分类技术非常适合预测或描述二元或

3、标称类型的数据集，对序数分类不 太有效，因为分类技术不考虑隐含在目标类中的序关系。 分类技术是一种根据输入数据集建立分类模型的系统方法。 分类技术 决策树分类法决策树分类法 基于规则的分类法基于规则的分类法 神经网络神经网络 支持向量机支持向量机 这些技术都使用一种学习算法确定分类模型，修改这个模型能够很好地 拟合输入数据中类标号和属性集之间的联系。学习算法得到的模型不仅 要很好地拟合输入数据，还要能够正确地预测未知样本的类标号。 训练算法的目标：建立具有很好的泛化能力的模型。 二、解决分类问题的一般方法二、解决分类问题的一般方法 朴素贝叶斯分类法朴素贝叶斯分类法 训练集：由类标号已知的记录构

4、成 检验集：由类标号未知的记录构成 预测的类预测的类 类=1类=0 实际的类类=1 类=0 00 f 01 f 10 f 11 f 二类问题的混淆矩阵 ij f ij 表中每个表项 表示实际类标号为 但是被预测为类 的记 录数。被分类模型正确预测的样本总数是 ，而被错误 预测的样本总数是 。 0011 ff 0110 ff 虽然混淆矩阵提供衡量分类模型的信息，但是用一个数汇总这些信 息更便于比较不同模型的性能。为实现这一目的，可以使用性能度 量（performance metric），如准确率（accuracy），其定义如下： 同样，分类模型的性能也可以用错误率（error rate）来表示，

5、其定 义如下： 00011011 0110 ffff ff 预测总数 错误预测数 错误率 目标：寻求最高的准确率或者最低的错误率 00011011 0011 ffff ff 预测总数 正确预测数 准确率 1、什么是决策树？ 类似于流程图的树结构 每个内部节点表示在一个属性上的测试 每个分枝代表一个测试输出 每个叶节点代表类或类分布 三、决策树（三、决策树（decision tree）归纳）归纳 3、决策树的使用：对未知样本进行分类 通过将样本的属性值与决策树相比较 2、决策树的生成由两个阶段组成 决策树构建 开始时，所有的训练样本都在根节点 递归通过选定的属性，来划分样本 （必须是离散值） 树

6、剪枝 许多分枝反映的是训练数据中的噪声和孤立点，树剪枝试图检测和剪 去这种分枝 根结点（root node）：它没有入边，但是有零条或多条出边。 内部结点（internal node）：恰好有一条入边和两条或多条出边。 叶节点（leaf node）或终结点（terminal node）：恰好有一条入边， 但没有出边。 叶结点 根结点 内部结点 体温 胎生 非哺乳动 物 哺乳动物 非哺乳动 物 恒温 否 冷血 是 一旦构造了决策树，对检验记录进行分类就很容易。从树的根结点 开始，将测试条件用于检验记录，根据测试结果选择适当的分支。沿着该 分支或者到达另一个内部结点，使用新的测试条件，或者到达一个

7、叶结点。 到达叶结点之后，叶结点的类标号就被赋值给该检验记录。 名字名字体温体温胎生胎生类标号类标号 火烈鸟恒温否？ 体温 胎生 非哺乳 动物 哺乳动 物 非哺乳 动物 恒温 否 冷血 是 如何建立决策树 对于给定的属性集，可以构造的决策树的数目达指数级。 尽管某些决策树比其他决策树更准确，但是由于搜索空间是 指数规模的，找出最佳决策树在计算上是不可行的。 尽管如此，人们还是开发了一些有效的算法，能够在合 理的时间内构造出具有一定准确率的次最优决策树。这些算 法通常都采用贪心策略。 有许多决策树算法: （ID3ID3） （C4.5C4.5） (SLIQ(SLIQ， SPRINT)SPRINT)

8、 在Hunt算法中，通过将训练记录相继划分成较纯的子集，以递归方式 建立决策树。设 是与结点t相关联的训练记录集，而 是类标号，Hunt算法的递归定义如下。 t D , 21c yyyy （1）如果 中所有记录都属于同一个类 ，则t是叶结点，用 标记。 t y t D t y （2）如果 中包含属于多个类的记录，则选择一个属性测试条件， 将记录划分成较小的子集。对于测试条件的每个输出，创建一个子女 结点，并根据测试结果将 中的记录分布到子女结点中。然后，对于 每个子女结点，递归地调用该算法。 t D t D Hunt算法 Tid有房者有房者婚姻状况婚姻状况年收入年收入拖欠贷款者拖欠贷款者 1是

9、单身125k否 2否已婚100k否 3否单身70k否 4是已婚120k否 5否离异95k是 6否已婚60k否 7是离异220k否 8否单身85k是 9否已婚75k否 10否单身90k是 拖欠贷款者=否拖欠贷款者=否拖欠贷款者=否 有房者 拖欠贷款者=否 有房者 拖欠贷款者=否 婚姻状况 年收入 拖欠贷款者=是拖欠贷款者=否 (b) (c)(d) (a) 拖欠贷款者=否 有房者 拖欠贷款者=否 婚姻状况 拖欠贷款者=是 是 是 否 否 否 是 单身离异 单身离异 已婚 已婚 =80k Hunt算法构造决策树 如果属性值的每种组合都在训练数据中出现，并且每种组合都具有唯一的类 标号，则Hunt算法

10、是有效的。但是对于大多数实际情况，这些假设太苛刻了， 因此，需要附加的条件来处理以下的情况： （1）算法的第二步所创建的子女结点可能为空，即不存在与这些结点相关 联的记录。如果没有一个训练记录包含这样的结点相关联的属性值组合，这 种情形就可能发生。这时，该结点成为叶结点，类标号为其父结点上训练记 录中的多数类。 （2）在第二步，如果与 相关联的所有记录都具有相同的属性值（目标属 性除外），则不可能进一步划分这些记录。在这种情况下，该结点为叶结点， 其标号为与该结点相关联的训练记录中的多数类。 t D 决策树归纳的设计问题 （1）如何分裂训练记录？ （2）如何停止分裂过程？ 树增长过程的每个递归

11、步骤都必须选择一个属性测试条件，将 记录划分成较小的子集。为了实现这个步骤。算法必须提供为 不同类型的属性指定测试条件的方法，并且提供评估每种测试 条件的客观度量。 决策树需要有结束条件，以终止决策树的生长过程。一个可能 的策略是分裂结点，直到所有的记录都属于同一个类，或者所 有的记录都具有相同的属性值。 表示属性测试条件的方法 1、二元属性 二元属性的测试条件产生两个可能的输出。 体温 恒温冷血 二元属性的测试条件 2、标称属性 由于标称属性有多个属性值，它的测试条件可以用两种方法表示。 婚姻状 况 单身已婚离异 婚姻状 况 已婚单身，离异 婚姻状 况 离异单身，已婚 婚姻状 况 单身已婚，

12、离异 多路划分 二元划分（通过属性值分组） 3、序数属性 序数属性也可以产生二元或多路划分，只要不违背序数属性值的有序 性，就可以对属性值进行分组。 衬衣尺码 小号， 中号 大号， 加大号 衬衣尺码 小号中号， 加大号 衬衣尺码 小号， 大号 中号， 加大号 （a）（b）（c） 4、连续属性 对于连续属性来说，测试条件可以是具有二元输出的比较测试 或 也可以是具有形如 输出的范围查询。 )(vA )(vA ), 2 , 1( 1 kivAv ii 年收入 80k （a） （b） 年收入 是 否10k 10k,25k 10k 25k,50k50k,80k 连续属性的测试条件 有很多度量可以用来确

13、定划分记录的最佳方法，这些度量用划分前和划分 后的记录的类分布定义。 选择最佳划分的度量 设 表示给定结点t中属于类i的记录所占的比例，有时，我们省略结点t， 直接用 表示该比例。在两类问题中，任意结点的类分布都可以记作 其中 。 )|(tip ),( 10 pp 01 1pp i p 性别 男 女 车型 家用 运动 豪华 C0:6 C1:4 C0:4 C1:6 C0:1 C1:3 C0:8 C1:0 C0:1 C1:7 （b）（a） C0:1 C1:0 C0:1 C1:0 C0:0 C1:1 C0:0 C1:1 顾客ID v1 v10 v20 v11 （c） 选择最佳划分的度量通常是根据划分

14、后子女结点不纯性的度量。不纯的 程度越低，类分布就越倾斜。例如（0,1）的结点具有零不纯性，而均衡 分布（0.5, 0.5）的结点具有最高的不纯性。不纯性度量的例子包括： 1 0 2 )|(log)|()( c i tiptiptEntropy 1 0 2 )|(1)( c i tiptGini )|(max1)(_Ctipterrorionlassificat i 熵： 基尼指数： 分类误差： 其中c是类的个数，并且在计算熵时， 00log2O 结点结点N1计数计数 类=00 类=16 结点结点N3计数计数 类=03 类=13 结点结点N2计数计数 类=01 类=15 0)6/6()6/0(

15、1 22 Gini 0)6/6(log)6/6()6/0(log)6/0( 22 Entropy 06/6 , 6/0max1Error 278. 0)6/5()6/1 (1 22 Gini 650. 0)6/5(log)6/5()6/1 (log)6/1 ( 22 Entropy 167. 06/5 , 6/1max1Error 5 . 0)6/3()6/3(1 22 Gini 1)6/3(log)6/3()6/3(log)6/3( 22 Entropy 5 . 06/3 , 6/3max1Error 二元分类问题不纯性度量之间的比较 不同的不纯性度量是一致的，但是作为测试条件的属性选择仍然

16、 因不纯性度量的选择而异。 00.10.20.30.40.50.60.70.80.91 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1 p 熵 Gini 分 类 误 差 为确定测试条件的效果，我们需要比较父结点（划分前）的不纯性程度和 子女结点（划分后）的不纯性程度，它们的差越大，测试条件的效果就越 好。增益 是一种可以用来确定划分效果的标准： k j j j vI N vN parentI 1 )( )( )( )(I其中， 是给定结点的不纯性度量，N是父结点上的记录总数，k是 属性值的个数， 是与子女结点 相关联的记录个数。)( j vN j v 决策树算法

17、选择最大化增益的测试条件。 B 是否 结点 N1结点 N2 A 是否 结点 N1结点 N2 父结点父结点 C06 C16 Gini=0.500 N1N1N2N2 C042 C133 Gini=0.486 N1N1N2N2 C015 C142 Gini=0.371 1、二元属性的划分 2、标称属性的划分 车型车型 运动，豪华家用 C091 C173 Gini0.468 车型车型 运动家用，豪华 C082 C1010 Gini0.167 车型车型 家用运动豪华 C0181 C1307 Gini0.163 （a）二元划分 (b)多路划分 标称属性可以产生二元划分或者多路划分 3、连续属性的划分 1.

18、使用二元划分 2.划分点v选择 N个记录中所有属性值作为划分点 3.对每个划分进行类计数, A v 和 A v 4.计算每个候选点v的Gini指标，并从中选择具有最小值的候选划分点 5.时间复杂度为O(n2) 降低计算复杂性的方法: 1.将记录进行排序 2.从两个相邻的排过序的属性值之间选择中间值作为划分点 3.计算每个候选点的Gini值 4.时间复杂度为O（NlogN） 4、增益率 熵和Gini指标等不纯性度量趋向有利于具有大量不同值的属性。 性别 男 女 车型 家用 运动 豪华 C0:6 C1:4 C0:4 C1:6 C0:1 C1:3 C0:8 C1:0 C0:1 C1:7 （b）（a）

19、 测试条件“车型”要比测试条件“性别”要好，因为它产生了更纯的派生结点。 测试条件“顾客ID”相比前两个产生更纯的划分，但是它却不是一个有预测性的 属性，因为与每个划分相关联的记录太少，以致不能作出可靠的预测。 C0:1 C1:0 C0:1 C1:0 C0:0 C1:1 C0:0 C1:1 顾客ID v1 v10 v20 v11 （c） 如何解决？如何解决？ 第一种策略：限制测试条件只能是二元划分。 第二种策略：修改评估划分的标准，把属性测试条件产生的输出数也考虑 进去。 例如：CART就是采用这样的策略。 例如：决策树算法C4.5采用增益率（gain ratio）的划分标准来 评估划分。 I

20、nfoSplit ratioGain info 是划分的总数，而其中，划分信息k)()logP(v-InfoSplit 1i 2i k i vP 决策树归纳特点的总结 1、决策树归纳是一种构建分类模型的非参数方法。 2、找到最佳的决策树是NP完全问题。 3、已开发的构建决策树技术不需要昂贵的计算代价，即使训练集非常 大，也可以快速建立模型。 4、决策树相对容易解释，特别是小型的决策树。 5、决策树是学习离散值函数的典型代表。 6、决策树算法对于噪声的干扰具有相当好的鲁棒性。 7、冗余属性不会对决策树的准确率造成不利的影响。 8、由于大多数决策树算法都采用自顶向下的递归划分方法，因此沿着 树向下

21、，记录会越来越少。 9、子树可能在决策树中重复多次，这使得决策树过于复杂，并且可能 更难解释。 10、目前为止，本章介绍的测试条件每次都只涉及一个属性。 二维数据集的决策树及其边界示例 P QR S01 01 Q S0 01 使用仅涉及单个属性的测试条件不能有效划分的数据集的例子 斜决策树（oblique decision tree）可以克服以上的局限，因为它允许测试条 件涉及多个属性。上图中的数据集可以很容易地用斜决策树表示，该决策树 只有一个结点，其测试条件为： 1 yx 缺点：尽管这种技术有更强的表达能力，并且能够产生更紧凑的决策树， 但是为给定的结点找出最佳测试条件的计算可能是相当复杂

22、的。 x + y 1 Class = + Class = 构造归纳（constructive induction） 提供另一种将数据划分成齐次非矩形区域的方法，该方法创建复合 属性，代表已有属性的算术或逻辑组合。新属性提供了更好的类区分能 力，并在决策树归纳之前就增广到数据集中。 与决策树不同，构造归纳不需要昂贵的花费，因为在构造决策树之 前，它只需要一次性地确定属性的所有相关组合，相比之下，在扩展每 个内部结点时，斜决策树都需要动态地确定正确的属性组合。然而构造 归纳会产生冗余的属性，因为新创建的属性是已有属性的组合。 11、研究表明不纯性度量方法的选择对决策树算法的性能影响很小。 一个好的

23、分类模型必须具有低训练误差和低泛化误差。 四、模型的过分拟合四、模型的过分拟合 二维数据过分拟合的例子 下图所示的二维数据集中的数据点属于两个类，分别标记为类“o”和类 “+”，类“o”的数据点由三个高斯分布混合产生，而类“+”的数据点 用一个均匀分布产生。数据集中，总共有1200个数据点是属于类“o”， 1800个数据点属于类“+”，其中30%的点用于训练，剩下的70%用于检 验。对训练集使用以Gini指标作为不纯性度量的决策树方法。 具有两个类的数据集的例子 当决策树很小时，训练误差和检验误差都很大，这种情况称作模型拟合不 足（model underfitting）。出现拟合不足的原因是模

24、型尚未学习到数据的真实 结构，因此，模型在训练集和检验集上的性能都很差。 一旦树的规模变得太大，即使训练误差还在降低，但是检验误差开始增大， 这种现象称为模型过分拟合（model overfitting）。 训练误差和检验误差 为理解过分拟合现象，举个例子：可以扩展树的叶结点，直到它完全拟合训练 数据。虽然这样一颗复杂的树的训练误差为0，但是检验误差可能很大，因为该树 可能包含这样的结点，它们偶然地拟合训练数据中某些噪声。这些结点降低了决策 树的性能，因为他们不能很好的泛化到检验样本。 （a）包含11个叶结点的决策树（b）包含24个叶结点的决策树 过分拟合与拟合不足是两种与模型复杂度有关的异常

25、现象。 名称名称体温体温胎生胎生4条腿条腿冬眠冬眠类标号类标号 豪猪恒温是是是是 猫恒温是是否是 蝙蝠恒温是否是否* 鲸恒温是否否否* 蝾螈冷血否是是否 科莫多巨蜥冷血否是否否 蟒蛇冷血否否是否 鲑鱼冷血否否否否 鹰恒温否否否否 虹鳉冷血是否否否 哺乳动物分类的训练数据集样本。（“*”为错误标记记录） 十个训练记录中有两个被错误标记：蝙蝠和鲸被错误标记为非哺乳 动物，而不是哺乳动物。 噪声导致的过分拟合 名称名称体温体温胎生胎生4条腿条腿冬眠冬眠类标号类标号 人恒温是否否是 鸽子恒温否否否否 象恒温是是否是 豹纹鲨冷血是否否否 海龟冷血否是否否 企鹅冷血否否否否 鳗冷血否否否否 海豚恒温是否否

26、是 针鼹恒温否是是是 希拉毒蜥冷血否是是否 哺乳动物分类的检验数据集样本。 完全拟合训练数据的决策树显示在下图（a）中，虽然该树的训练误差 为0，但是它在检验数据集上的误差高达30%。 体温 恒温 冷血 胎生 4条腿 哺乳类 动物 非哺乳 类动物 非哺乳 类动物 非哺乳 类动物 是否 是否 体温 恒温 冷血 胎生 非哺乳 类动物 非哺乳 类动物 是否 哺乳类 动物 （a）模型M1 （b）模型M2 图（b）中决策树M2尽管训练误差较高（20%）， 但是它具有较低的检验误差。 缺乏代表性样本导致的过分拟合 名称名称体温体温胎生胎生4 4条腿条腿冬眠冬眠类标号类标号 蝾螈冷血否是是否 虹鳉冷血是否否

27、否 鹰恒温否否否否 弱夜鹰恒温否否是否 鸭嘴兽恒温否是是是 体温 恒温 冷血 冬眠 4条腿 哺乳类 动物 非哺乳 类动物 非哺乳 类动物 非哺乳 类动物 是否 是否 人、大象和海豚都被误分类，因为决策树 把恒温但不冬眠的脊柱动物划分为非哺乳动物。 决策树做出这样的分类决策是因为只有一个训 练记录（鹰）具有这些特性。 过分拟合与多重比较过程 1、在决策树增长过程中，可以进行多种测试，以确定哪个属性能够 最好的划分训练数据。 2、在这种情况下，算法实际上是使用多重比较过程来决定是否需要 扩展决策树。 3、当候选属性多，训练记录数少时，这种影响就变得更加明显。 多重比较过程与模型过分拟合有什么关系？

28、 1、过分拟合的主要原因一直是个争辩的话题，但大家还是普遍同意模型 的复杂度对模型的过分拟合有影响。 2、如何确定正确的模型复杂度？理想的复杂度是能产生最低泛化误差的 模型的复杂度。 3、估计泛化误差的方法 使用再代入估计。用训练误差提供对泛化误差的乐观估计 结合模型复杂度 估计统计上界 使用确定集 泛化误差估计 泛化误差估计 1、使用再代入估计 再代入估计方法假设训练数据集可以很好地代表整体数据，因而， 可以使用训练误差（又称再代入误差）提供泛化误差的乐观估计。 但是训练误差通常是泛化误差的一种很差的估计。 考虑下图中的二叉决策树。假设两颗决策树都由相同的训练数据产 生，并且都根据每个叶结点

29、多数类做出划分。注意，左边的树T1复 杂一些，它扩展了右边决策树T2的某些结点。左决策树的训练误差 是 ，而右决策树的训练误差是 。 根据再代入估计，左决策树要优于右决策树。 167. 024/4)( 1 Te25. 024/6)( 2 Te +：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、结合模型复杂度 如之前所述，模型越是复杂，出现过分拟合的几率就越高，因此，我们更喜欢采 用较为简单的模型。这种策略与应用众所周知的奥卡姆剃刀一致。 奥卡

30、姆剃刀：给定两个具有相同泛化误差的模型，较简单的模型比较复杂的模型 更可取。 悲观误差评估悲观误差评估：使用训练误差与模型复杂度罚项（penalty term）的和计算泛 化误差。结果泛化误差可以看作模型的悲观误差估计。设n(t)是结点t分类的 训练记录数，e(t)是被误分类的记录数。决策树T的悲观误差估计 可以用 下式计算： )(Teg t k i i k i ii g N TTe tn tte Te )()( )( )()( )( 1 1 其中，k是决策树的叶结点数，e(T)是决策树的总训练误差， 是训练记 录数， 是每个结点 对应的罚项。 t N )( i t i t +：3 -：0 +

31、：3 -：1 +：1 -：2 +：0 -：2 +：2 -：1 +：3 -：1 +：0 -：5 +：3 -：6 +：3 -：0 +：1 -：4 +：5 -：2 决策树T1 决策树T2 考虑上图的二叉决策树。如果罚项等于0.5，左边的决策树的悲观误差 估计为： 3125. 0 24 5 . 7 24 5 . 074 )( 1 Teg 右边的决策树的悲观误差估计为： 333. 0 24 8 24 5 . 046 )( 2 Teg 此时，左边的决策树比右边的决策树具有更好的悲观误差估计。 最小描述长度原则（最小描述长度原则（minimum description length, MDL） AB A?

32、B? C? 10 0 1 YesNo B1B2 C1C2 Xy X11 X20 X30 X41 Xn1 标记的未标记的 Cost 是传输总代价。目标：最小化Cost值。 其中Cost(Data|Model) 是误分类记录编码的开销。Cost(Model) 是模 型编码的开销 。 另一种可能是，A决定建立一个分类模型，概括X和y点之间的关系。 Cost(Model, Data) = Cost(Data|Model) + Cost(Model) 3、估计统计上界 泛化误差也可以用训练误差的统计修正来估计。因为泛化误差倾向 于比训练误差大，所以统计修正通常是计算训练误差的上界。 4、使用确认集 在该

33、方法中，不是用训练集估计泛化误差，而是把原始的训练数据 集分为两个较小的子集，一个子集用于训练，而另一个称为确认集， 用于估计泛化误差。 2/3训练集 建立模型建立模型 误差估计误差估计 1/3训练集 该方法通常用于通过参数控制获得具有不同复杂度模型的分类技术。 通过调整学习算法中的参数，直到学习算法产生的模型在确认集上 达到最低的错误率，可以估计最佳模型的复杂度。 处理决策树归纳中的过分拟合 先剪枝 (提前终止规则) 树增长算法在产生完全拟合整个训练数据集的之前就停止决策树的生长 为了做到这一点，需要采用更具限制性的结束条件: 当结点的记录数少于一定阈值，则停止生长 当不纯性度量的增益低于某

34、个确定的阈值时，则停止生长 (e.g., information gain). 缺点：很难为提前终止选取正确的阈值: （1）阈值太高，导致拟合不足 （2）阈值太低，导致不能充分解决过分拟合的问题。 后剪枝 在该方法中，初始决策树按照最大规模生长，然后进行剪枝的步骤，按照自 底向上的方式修剪完全增长的决策树。 修剪有两种做法: （1）用新的叶结点替换子树，该叶结点的类标号由子树下记录中的多数类定 （2）用子树中最常用的分支代替子树 五、评估分类器的性能五、评估分类器的性能 一、保持（Holdout）方法 将被标记的原始数据划分成两个不相交的集合，分别成为训练集和 检验集。在训练集上归纳分类模型，

35、在检验集上评估模型的性能。 局限性： 1、用于训练的被标记样本较少。 2、模型可能高度依赖于训练集和检验集的构成。 二、随机二次抽样（random subsampling） 随机二次抽样可以多次重复保持方法来改进分类器性能的估计。 k i isub kaccacc 1 / 由于它没有控制每个记录用于训练和检验的次数，因此，有些 用于训练的记录使用的频率可能比其他记录高得多。 三、交叉验证（cross-validation） 在该方法中，每个记录用于训练的次数相同，并且恰好检验一次。 例：假设把数据分为相同大小的两个子集，首先，我们选择一个子 集作训练集，而另一个作检验集，然后交换两个集合的角色

36、，原先 作训练集的现在作检验集，反之亦然，这种方法叫做二折交叉验证。 四、自助（bootstrap）法 在自助法中，训练记录采用有放回抽样使得它等几率地被重新抽取。如果原 始数据有N个记录，可以证明，平均来说，大小为N的自助样本大约包含原始 数据的63.2%的记录。 N N ) 1 1 (1至少一个记录被自助样本抽取的概率632. 0 1 1) 1 1 (1lim eN N N 它通过组合每个自助样本的准确率 和由包含所有标记样本的训练集计算的 准确率 计算总准确率 ： )( i )( s acc)( boot acc b i siboot acc b acc 1 )368. 0632. 0( 1 六、比较分类器的方法六、比较分类器的方法 考虑一对分类模型Model A和model