第3章 分类：基本概念和技术
人类具有分类事物的天赋，例如过滤垃圾邮件信息之类的日常任务，或者在望远镜图像中识别天体这类更为特殊的任务（参见图3.1）。虽然对于只有少数几个属性的小而简单的数据集，通常通过手动分类就足以解决，但对更大和更复杂的数据集，仍然需要自动化解决方案。
本章介绍了分类的基本概念，并描述了其中的一些关键问题，如模型过拟合、模型选择和模型评估等。虽然使用到了称为决策树归纳的分类技术来说明这些主题，但本章中的大部分内容也适用于其他分类技术，第4章会进行介绍。
3.1 基本概念
图3.2显示了分类的总体思路。分类任务的数据由一组实例（记录）组成。每个这样的实例都以元组（x，y）为特征，其中x是描述实例的属性值集合，y是实例的类别标签。属性集x可以包含任何类型的属性，而类别标签y必须是可分类的。
分类模型（classification model）是属性集和类别标签之间关系的抽象表示。正如在接下来的两章中将会看到的那样，该模型可以用许多方式来表示，例如树、概率表，或简单地用一个实值参数的向量表示。形式上，我们可以在数学表达上把它作为一个目标函数f，它将输入属性集x并产生一个对应于预测类别标签的输出。说明如果f（x)=y，则该模型可正确地对实例（x，y）进行分类。
表3.1显示了分类任务的属性集和类别标签的各种例子。垃圾邮件过滤和肿瘤鉴定是二分类问题的例子，其中每个数据实例可以分为两类之一。如果类的数量大于2，如在星系分类示例中那样，那么它被称为多分类问题。
我们用以下两个例子来说明分类的基本概念。
例3.1 脊椎动物分类 表3.2显示了将脊椎动物分为哺乳动物、爬行动物、鸟类、鱼类和两栖动物的样本数据集。属性集包括脊椎动物的特征，如体温、表皮覆盖和飞行能力。该数据集也可用于二分类任务，如哺乳动物分类，可将爬行动物、鸟类、鱼类和两栖类分为一类，称为非哺乳动物。
例3.2 贷款借款人分类 预测贷款人是否可以偿还贷款或拖欠贷款的问题。表3.3展示了用于建立分类模型的数据集。属性集包括借款人的个人信息，如婚姻状况和年收入，而类别标签则表明借款人是否拖欠了贷款。
分类模型在数据挖掘中担当两个重要角色。首先，它被用作预测模型（predictive model）来对先前未标记的实例进行分类。一个好的分类模型必须以快速的响应时间提供准确的预测。其次，它作为一个描述性模型（descriptive model）来识别区分不同类别实例的特征。这对于诸如医疗诊断的关键应用特别有用，因为如果无法证明如何做出这样的决定，就称不上是一个预测模型。
例如，由表3.2所示的脊椎动物数据集显示的分类模型可用于预测以下脊椎动物的类别标签：
此外，它可以用作描述性模型来帮助确定将脊椎动物定义为哺乳动物、爬行动物、鸟类、鱼类或两栖动物的特征。例如，该模型可能会将生育后代的哺乳动物确定为恒温脊椎动物。
关于前面的例子有几点值得注意。首先，虽然表3.2中显示的所有属性都是定性的，但对于可用作预测变量的属性类型没有限制。另一方面，类别标签必须是标称类型。这将分类与其他预测建模任务（如回归）区分开来，其中预测值通常是定量的。有关回归的更多信息可以在附录D中找到。
另一点值得注意的是，可能并非所有属性都与分类任务相关。例如，脊椎动物的平均长度或重量可能不适用于哺乳动物分类，116因为这些属性对于哺乳动物和非哺乳动物都可以体现相同的值。这种属性通常在预处理期间被丢弃。其余属性可能无法自行分类，因此必须与其他属性一起使用。例如，体温属性不足以区分哺乳动物和其他脊椎动物。当它与“胎生”一起使用时，哺乳动物的分类显著改善。但是，如果包含附加属性（例如表皮覆盖），则该模型变得过于具体，并且不再涵盖所有哺乳动物。寻找区分不同类别实例的最佳属性组合是构建最优分类模型的关键挑战。
3.2 一般的分类框架
分类是将标签分配给未标记数据实例的任务，分类器用于执行此类任务。分类器（classifier）通常按照上一节所述的模型进行描述。该模型是使用给定的一组实例创建的，这组实例称为训练集（training set），其中包含每个实例的属性值以及类别标签。学习给定训练集分类模型的系统化方法称为学习算法（learning algorithm）。使用学习算法从训练数据建立分类模型的过程称为归纳（induction）。这个过程通常也被描述为“学习一个模型”或“建立一个模型”。在未知的测试实例上应用分类模型来预测它们的类别标签的过程称为演绎（deduction）。因此，分类过程涉及两个步骤：将学习算法应用于训练数据以学习模型，然后应用模型将标签分配给未标记的实例。图3.3说明了分类的一般框架。
分类技术（classification technique）是指分类的一般方法，例如将在本章中研究的决策树技术。像大多数其他分类技术一样，这种分类技术由一系列相关模型和一些用于学习这些模型的算法组成。在第4章中，我们将研究其他分类技术，包括神经网络和支持向量机。
对术语的两点说明。首先，术语“分类器”和“模型”通常被认为是同义词。理想情况下，分类技术构建单一的全局模型。但是，虽然每个模型都定义了一个分类器，但并不是每个分类器都由一个模型定义。某些分类器（如k-最近邻分类器）不会构建显式模型（见4.3节），117而其他分类器（如集成分类器）会合并模型集合的输出（见4.10节）。其次，术语“分类器”通常用于更一般的含义来表示分类技术。因此，例如，“决策树分类器”可以指决策树分类技术或使用该技术构建的特定分类器。幸运的是，“分类器”的含义通常在上下文中较为清晰。
在图3.3所示的总体框架中，归纳和演绎步骤应该分开进行。事实上，正如将在3.6节中讨论的那样，训练集和测试集应该是相互独立的，以确保归纳模型能够准确预测以前从未遇到过的实例的类别标签。具有这种预测性见解的模型被称为具有良好的泛化性能（generalization performance）。模型（分类器）的性能可以通过比较实例的预测标签和真实标签来评估。这些信息可以在一个称为混淆矩阵（confusion matrix）的表格中总结出来。
表3.4描述了二分类问题的混淆矩阵。每个条目fij表示来自第i类的预测为类j的实例的数量。118例如，f01是从类0错误地预测为类1的实例的数量。模型进行的正确预测的数量是（f11+f00）并且不正确预测的数量是（f10+f01）。
尽管混淆矩阵提供了确定分类模型性能的信息，但将这些信息汇总为单个数据可以更方便地比较不同模型的相对性能。这可以使用诸如准确率（accuracy）这样的评估度量（evaluation metric）来完成：
对于二分类问题，模型的准确率由下式给出：
错误率（error rate）是另一个相关度量，对于二分类问题，其定义如下：
大多数分类技术的学习算法用于学习获得测试集最高准确率或等同地最低错误率的模型。我们将在3.6节重新讨论模型评估这个主题。
3.3 决策树分类器
本节介绍一种称为决策树分类器的简单分类技术。为了说明决策树如何工作，考虑使用表3.2所示的脊椎动物数据集区分哺乳动物和非哺乳动物的分类问题。119假设科学家发现了一个新物种。我们如何判断它是哺乳动物还是非哺乳动物？一种方法是提出关于物种特征的一系列问题。我们可能会问的第一个问题是该物种是冷血还是恒温的。如果它是冷血的，那肯定不是哺乳动物，否则，它不是鸟类就是哺乳动物。在后一种情况下，我们需要提出一个后续问题：物种的雌性是否会生下后代？答案是肯定的是哺乳动物，而答案是否定的可能是非哺乳动物（除了产卵的哺乳动物，如鸭嘴兽和刺食蚁兽）。
前面的例子说明了如何通过询问关于测试实例属性的一系列精心制作的问题来解决分类问题。每次收到答案时，我们都可以提出后续问题，直到能够确定其类别标签。可将这一系列问题及其可能的答案组织成称为决策树的分层结构。图3.4给出了一个决策树如何对哺乳动物进行分类的例子。该树有三种类型的结点：
- 根结点，没有传入连接和零个或多个传出连接。
- 内部结点，每个结点只有一个输入连接和两个或更多的传出连接。
- 叶结点或终端结点，每个结点只有一个输入连接并且没有输出连接。
决策树中的每个叶结点都与一个类别标签相关联。非终端（non-terminal）结点包括根结点和内部结点，包含使用单个属性定义的属性测试条件（attribute test condition）。属性测试条件的每个可能结果都与该结点的一个子结点相关联。例如，图3.4中显示的树的根结点使用属性“体温”来定义一个属性测试条件，该条件具有两个结果，即恒温和冷血，产生两个子结点。
给定一个决策树，可以很简单地对测试实例进行分类。从根结点开始，我们应用其属性测试条件，并根据测试结果按照适当的分支进行操作。这将导致我们转移到另一个内部结点或叶结点，该结点应用了新属性测试条件。一旦到达叶结点，我们将与该结点关联的类别标签分配给测试实例。举例来说，图3.5描绘了用于预测火烈鸟的类别标签的路径。该路径终止于标记为“非哺乳动物”的叶结点。
3.3.1 构建决策树的基本算法
许多可能的决策树由特定数据集构建。虽然其中一些树比其他树好，但由于搜索空间的指数级别上升，寻找最佳树的代价是昂贵的。有效的算法已经开发出来，可以在合理的时间内归纳出具有合理准确率的决策树，尽管不是最优的。这些算法通常采用贪心策略，以自顶向下的方式生成决策树，也就是是对划分训练数据时要使用的属性进行一系列局部最优决策。最早的方法之一是Hunt算法，它是当前许多决策树分类器实现的基础，包括ID3、C4.5和CART。本小节介绍了Hunt算法，并描述了构建决策树时必须考虑的一些设计问题。
1. Hunt算法
在Hunt算法中，决策树是以递归方式生长的。该树最初包含与所有训练实例关联的单个根结点。如果某个结点与来自多个类的实例相关联，则会使用由拆分标准（splitting criterion）确定的属性测试条件进行扩展。为属性测试条件的每个结果创建一个子叶结点，并根据测试结果将与父结点关联的实例分发给子结点。此结点扩展步骤可以递归应用于每个子结点，只要它具有多个类的标签即可。如果与某个叶结点相关的所有实例都具有相同的类别标签，则该结点不会进一步扩展。每个叶结点都会分配一个类别标签，该标签在与该结点关联的训练实例中出现的频率最高。
为了说明算法的工作原理，以表3.3中显示的贷款人分类问题训练集为例。假设我们应用Hunt的算法来拟合训练数据。该分类问题的初始决策树只有一个结点，如图3.6a所示。标记为“拖欠贷款者=否”，意味大多数贷款者都按时归还贷款。训练该树的错误率为30％，因为10个训练实例中有3个“拖欠贷款者=是”的类别标签。因为叶结点包含来自多个类的训练实例，所以可进一步扩展。
将“有房者”作为拆分训练实例的属性。选择该属性作为属性测试条件的理由将在后面讨论。图3.6b展示了“有房者”属性的二元划分。“有房者=是”的所有训练实例都传播到根结点的左子结点，其余传播到右子结点。之后将Hunt算法递归地应用于每个子结点。由于所有与此结点关联的实例都具有相同的类别标签，所以将左子结点标记为“拖欠贷款者=否”的叶结点。122右子结点具有来自每个类别标签的实例。因此，我们进一步拆分。图3.6c和d展示了递归扩展右子结点生成的子树。
如上所述，对Hunt算法做出了一些简化的假设，然而在实践中往往是不正确的。在下文中，我们将对这些假设进行描述并简要讨论一些处理它们的可能方法。
1） 如果任何训练实例都不具有特定的属性值，则在Hunt算法中创建的一些子结点可以为空。处理该情况的方法是将它们中的每个结点声明为叶结点，与该结点的父结点相关联的训练实例的类别标签出现得最为频繁。
2） 如果与一个结点相关的所有训练实例具有相同的属性值，但具有不同的类别标签，则不能进一步扩展该结点。处理这种情况的方法是将该结点声明为叶结点，并为其分配与该结点关联的在训练实例中出现最频繁的类别标签。
2.决策树归纳的设计问题
Hunt算法是以贪心策略增长决策树的通用方法。为了实现该算法，有两个必须解决的关键设计问题。
1） 什么是拆分标准？在每次递归中，必须选择一个属性，将与结点关联的训练实例划分为与其子结点关联的较小子集。拆分标准决定选择哪个属性作为测试条件以及如何将训练实例分配给子结点。这将在3.3.2节和3.3.3节中讨论。
2） 什么是终止标准？只有当与结点相关的所有训练实例具有相同的类别标签或具有相同的属性值时，基本算法才会停止扩展结点。虽然这些条件已经足够，但即使叶结点包含来自多个类的训练实例，也有理由更早地终止扩展结点。该过程被称为提前终止，且确定何时应该终止扩展结点的条件被称为终止标准。3.4节讨论了提前终止的优点。
3.3.2 表示属性测试条件的方法
决策树归纳算法必须为表达属性测试条件提供方法，为不同属性类型提供相应结果。
二元属性 二元属性的测试条件产生两个可能的输出，如图3.7所示。
标称属性 由于标称属性可以有多个属性值，因此它的测试条件可以用两种方式表示，如图3.8所示的多路划分和二元划分。对于多路划分（见图3.8a），其输出数取决于该属性不同值的个数。例如，如果婚姻状况有三个不同的属性值——单身、已婚和离异，其测试条件将产生三路划分。也可以将标称属性采用的所有值分成两组来创建二元划分。例如，某些决策树算法（如CART）只产生二元划分，124这些算法可创建k个属性值二元划分的2k-1-1种方法。图3.8b说明了将婚姻状况的属性值分为两个子集的三种不同方式。
序数属性 序数属性也可以产生二元或多路划分。只要分组不违反属性值的有序性，就可以对序数属性值进行分组。125图3.9显示了基于衬衣尺码属性划分训练记录的各种方法。图3.9a和图3.9b显示的分组保留了属性值之间的顺序，而图3.9c显示的分组违反了这一性质，因为它将属性值小号和大号分为一组，而将中号和超大号分为另一组。
连续属性 对于连续属性，测试条件可以表示为比较测试（例如A
3.3.3 选择属性测试条件的方法
可以用来确定属性测试条件优劣的度量方法有很多。这些度量方法试图优先考虑将训练实例划分为子结点中更纯子集的属性测试条件，这些子结点通常具有相同的类别标签。由于包含同一类的训练实例的结点不需要进一步扩展，因此属性更纯的结点是有意义的。相反，不纯的结点包含来自多个类的训练实例，可能需要多级扩展，从而极大地增加了树的深度。较大的树是我们不希望看到的，因为它们更容易受到模型过拟合的影响，这种情况可能会降低未知情况下的分类性能，这将在3.4节中讨论。与较小的树相比，它们难以解释，且会使训练和测试时间更长。
在下文中，我们提出了测量结点不纯性和其子结点集合不纯性的不同方法，这两种情况都将用于确定结点的最佳属性测试条件。
1.单结点的不纯性度量
127结点的不纯性度量，即度量共有结点的数据实例的类别标签的差异程度。以下是可用于评估结点t不纯性的度量示例：
其中，pi（t)是结点t属于类i的训练实例的相对频率，c是类的总个数，并且在计算熵时，0 log2 0=0。如果一个结点包含来自单个类的实例，并且该结点具有来自多个类的等比例实例的最大不纯性，则以上三个度量都给出零不纯性度量。
图3.11比较了二分类问题不纯性度量的相对大小。由于只有两个类，所以p0（t)+p1（t)=1。p表示属于其中一个类的实例所占的比例。当所有三个度量都属于一个类时（即，p0（t)=p1（t)=0.5）得到最大值，当所有实例属于一个类时，度量得到最小值（即p0（t)或p1（t)等于1）。下面的例子说明了当我们改变类别分布时，不纯性度量的值是如何变化的。
基于以上计算，结点N1具有最低的不纯性度量值，随后是N2和N3。该例与图3.11一同展示了不纯性度量的一致性，即如果结点N1的熵比结点N2低，那么N1的基尼指数（Gini index）和误差率也将低于N2。128尽管它们一致，但属性选择仍然因不纯性度量而不同（参见习题6）。
2.子结点的集合不纯性
设想一个属性测试条件，该条件将包含N个训练实例的结点拆分为k个子结点{v1，v2，…，vk}，其中每个子结点表示由属性测试的k个结果之一产生的数据划分条件。设N（vj)为与不纯性为I（vj）的子结点vj相关联的训练实例的数量。由于父结点中的训练实例在N（vj)N次数内到达结点vj，因此可以通过对子结点的不纯性度量进行加权求和来计算子结点的集合不纯性，如下所示：
例3.3 加权熵 考虑图3.12a和b所示的贷款借款人分类问题的候选人属性测试条件。对属性“有房者”进行划分将产生两个子结点，其加权熵计算如下：
另一方面，对于“婚姻状况”的划分，三个子结点的加权熵由下式给出：
因此，“婚姻状况”的加权熵低于“有房者”。
3.确定最佳属性测试条件
为了确定属性测试条件的优劣，我们需要比较父结点（在划分之前）的不纯性和子结点的不纯性的加权程度（分裂之后）。它们的差异越大，测试条件越好。这种差异（Δ）也称为属性测试条件的纯度增益（gain），定义如下：
其中I（父结点）是划分前结点的不纯性，I（子结点）是划分后结点的加权不纯性度量。可以证明，由于I（父结点）≥I（子结点），对于上述任何合理的度量，增益是非负的。增益越高，子结点相对于父结点的类越纯洁。决策树学习算法中的分裂准则选择最大增益的属性测试条件。请注意，在给定结点处最大化增益相当于最小化其子项的加权不纯性度量，因为对于所有候选属性测试条件，I（父结点）是相同的。最后，当熵用作不纯性度量时，熵的差异通常称为信息增益（information gain）——Δinfo。
在下文中，我们将给出说明性的方法来确定定性或定量属性的最佳属性测试条件。
4.定性属性的划分
考虑图3.12显示的前两个候选分组，涉及的定性属性为有房者和婚姻状况。在父结点处的初始类分布为（0.3，0.7），由于训练数据中有3个实例为是，7个实例为否，因此有：
有房者和婚姻状况的信息增益分别为：
由于婚姻状况的加权熵较低，因此其信息增益较高，将被考虑用于划分。
5.定性属性的二元划分
考虑仅使用二元划分和基尼指数作为不纯性度量来构建决策树。图3.13显示了属性有房者和婚姻状况的4个候选划分标准的例子。由于训练集中有3名借款人违约，另有7名借款人偿还了贷款（见图3.13中的表格），因此划分前的父结点的基尼指数为
如果选择有房者作为划分属性，则子结点N1和N2的基尼指数分别为0和0.490。这些子结点的加权平均基尼指数是
此处的权重代表分配给每个子结点训练实例的比例。使用有房者作为划分属性的增益为0.420-0.343=0.077。同样，也可以对属性婚姻状况应用二元划分。但是，由于婚姻状况是一个具有三种结果的标称属性，因此有三种可能的方式对属性值进行二元划分。图3.13显示了每个候选二元划分的子结点的加权平均基尼指数。根据这些结果，有房者和使用婚姻状况的二元分组显然是最好的候选，因为它们都产生最低的加权平均基尼指数。如果属性值的二元划分不违反顺序属性，则二元划分也可用于序数属性。
6.定量属性的二元划分
考虑为上述拖欠贷款分类问题确定最佳二元划分“年收入≤τ”的问题。正如之前讨论的那样，尽管τ可以在训练集中年收入的最小值和最大值之间取任意值，但只需将训练集中观察到的年收入值视为候选划分位置就足够了。对于每个候选τ，训练集被扫描一次以计算年收入小于或大于τ的借款人数量及其类别比例。然后，我们可以计算每个候选划分位置的基尼指数，并选择产生τ的最小值。在每个候选划分位置计算基尼指数需要O（N）次操作，其中N是训练实例的数量。由于最多有N个候选，所以该暴力法的计算复杂度为O（N2）。通过使用如下所述的方法（参见图3.14中的说明），可以将此问题的计算复杂度降至O（NlogN）。在这种方法中，首先根据年收入将训练实例排序，所需时间为O（NlogN）。从两个相邻的排过序的属性值中选择中间值作为候选划分点，得到候选划分点为55000美元、65000美元、72500美元等。对于第一位候选，由于无年收入低于或等于55000美元，年收入<55000美元的子结点的基尼指数等于零。相比之下，年收入大于55000美元的结点有3个实例是是，7个是否，该结点的基尼指数是0.420。第一候选划分位置τ=55000美元的加权平均基尼指数等于0×0+1×0.420=0.420。
对于第二个候选τ=65000，通过简单更新上一个候选的类分布，就可得到该候选的类分布。这是因为，当τ从55000美元增加到65000美元时，只有一个受此变化影响的训练实例。通过检查受影响的训练实例的类别标签，可以获得新的类分布。例如，当τ增加到65000美元时，133训练集中只有一个借款人，年收入为60000美元，受此变化影响。由于借款人的类别标签为否，所以类别否的计数从0增加到1（年收入≤65000美元），并从7减少到6（年收入>65000美元），如图3.14所示。是类的分布保持不变。新的候选划分的基尼指数为0.400。
重复此过程直至算出所有候选的基尼指数。最佳划分位置对应于产生最低基尼指数的点，即τ=97500美元。由于可以在O（1）时间内计算每个候选划分位置的基尼指数，如果所有值保持排序，找到最佳划分位置的时间复杂度为O（N），一次操作需要O（NlogN）时间。因此这种方法的计算复杂度为O（NlogN），比暴力法所花费的O（N2）时间小得多。通过仅考虑位于不同类别标签的两个相邻排序实例之间的候选划分位置，可以进一步减少计算量。例如，我们无须考虑位于60000美元至75000美元之间的候选划分位置，因为年收入在此范围内的三个实例（60000美元，70000美元和75000美元）都具有相同的类别标签。对比位于此范围之外的划分位置，选择此范围内的划分位置只会增加不纯性的程度。因此，在τ=65000美元和τ=72500美元的候选划分位置可以忽略。同样，我们也无须考虑候选划分位置87500美元、92500美元、110000美元、122500美元和172500美元，因为它们位于两个相邻且具有相同标签的实例之间。该策略将需考虑的候选划分位置的数量从9减少到2（不包括两个边界情况τ=55000美元和τ=230000美元）。
7.增益率
熵和基尼指数等不纯性度量存在一个潜在的局限，即它们更容易选择具有大量不同值的定性属性。图3.12给出了表3.3列出的划分数据集的三个候选属性。如上所述，选择属性婚姻状况优于选择属性有房者，因为前者提供了更大的信息增益。但是，如果将它们与顾客ID进行比较，后者因为加权熵和基尼指数等于零，会生成信息增益更大的最纯划分。然而，顾客ID并不是一个很好的划分属性，因为它对每个实例都有唯一的值。即使包含顾客ID的测试条件将准确对训练数据中的每个实例进行分类，我们也不能将此类测试条件用于含有未知顾客ID的新测试实例中。134这个例子表明单一的低不纯性结点不足以找到良好的属性测试条件。正如我们将在3.4节中讨论的，子结点越多，决策树越复杂，更容易出现过拟合。因此，在决定最佳属性测试条件时，还应该考虑划分属性产生的子结点数量。
有两种方法可以解决这个问题。一种方法是仅生成二元决策树，从而避免使用不同数量的划分来处理属性。决策树分类器（如CART）就是使用此策略。另一种方法是修改划分标准以考虑属性生成的划分数量。例如，在C4.5决策树算法中，使用称为增益率（gain ratio）的度量来补偿产生大量子结点的属性。这一度量的计算如下：
其中，N（vi）是分配给结点vi的实例数量，且k是划分的总数。划分信息测量将结点划分成子结点的熵，并评估划分是否会导致大量相同大小的子结点。例如，如果每个划分具有相同数量的实例，则i：N（vi）N=1k并且划分信息等于log2k。这说明如果属性产生大量的划分，则其划分信息也很大，从而降低了增益率。
例3.4 增益率 考虑习题2中给出的数据集。我们希望从性别、车型和顾客ID三个属性中选出最佳属性测试条件。划分前的熵为：
如果使用性别作为属性测试条件：
如果使用车型作为属性测试条件：
如果使用顾客ID作为属性测试条件：
因此，尽管顾客ID具有最高的信息增益，但其增益率低于车型，因为前者会产生更大数量的划分。
3.3.4 决策树归纳算法
算法3.1给出了决策树归纳算法的伪代码。该算法的输入是一组训练实例集E和属性集F。该算法递归地选择最优属性来划分数据（步骤7），并扩展树的叶结点（步骤11和12）直到满足结束条件（步骤1）。算法的细节如下。
1) createNode（)函数通过创建一个新结点来扩展决策树。决策树的结点要么具有测试条件，表示为node.test_cond，要么具有类别标签，表示为node.label。
2) find_best_split（)函数确定应当选择哪个属性作为划分训练实例的测试条件。划分属性的选择取决于使用哪种不纯性度量来评估划分。常用的措施包括熵和基尼指数。
3) Classify（)函数确定要分配给叶结点的类别标签。对于每个叶结点t，令p（it)表示该结点上属于类i的训练实例所占的比例。136分配给叶结点的标签通常是在与此结点关联的训练实例中最常出现的标签。
其中，argmax返回最大化p（it)的类i。p（it)除了提供确定叶结点的类别标签所需的信息之外，还可以用来估计分配到叶结点t的实例属于类别i的概率。4.11.2节和4.11.4节讨论，如何使用这种概率估计，来确定在不同代价函数下决策树的性能。
4) stopping_cond（)函数通过检查所有实例是否具有相同的类别标签，或相同的属性值来决定是否终止决策树的增长。由于决策树分类器采用自顶向下的递归划分方法来构建模型，因此随着树深度的增加，与结点关联的训练实例的数量也会减少。因此，叶结点包含的训练实例可能太少，以至于无法对其类别标签做出统计上显著的决定。这被称为数据碎片（data fragmentation）问题。避免此问题的一种方法是，当与结点关联的实例数量低于某个阈值时，137不允许划分结点。3.5.4节会讨论使用更系统的方法来控制决策树的大小（叶结点的数量）。
3.3.5 示例：Web机器人检测
现考虑区分Web机器人的访问模式与人类用户的访问模式的任务。Web机器人（也称为网络爬虫）是一种软件程序，通过跟踪从最初的一组种子URL中提取的超链接，从一个或多个网站自动检索文件。这些程序已被应用于各种用途，从代替搜索引擎搜集Web网页到执行一些更恶意的活动，如制造垃圾邮件、在在线广告中制造点击欺诈。
Web机器人检测问题可以转换为二分类任务。分类任务的输入数据是一个Web服务器日志，138图3.15a显示了一个样例。日志文件中的每一行对应于客户端（即人类用户或Web机器人）对Web服务器所做的请求。Web日志中记录的字段包括客户端的IP地址、请求的时间戳、请求文件的URL、文件的大小以及用户代理。用户代理是包含有关客户端标识信息的字段。对于人类用户，用户代理字段指定用于提取文件的Web浏览器或移动设备的类型，而对于Web机器人，它应在技术上包含爬虫程序的名称。然而，Web机器人可能会通过声明与已知浏览器相同的用户代理字段来隐藏其真实身份。因此，用户代理不是检测Web机器人的可靠方式。
构建分类模型的第一步是精确定义数据实例和关联属性。一种简单的方法是将每个日志条目视为数据实例，并将日志文件中的相应字段用作其属性集。但是，这种方法由于几个原因而不够可靠。首先，许多属性是标称值，并且取值范围广泛。例如，日志文件中唯一的客户端IP地址、URL和引用链接的数量可能非常大。这些属性对于构建决策树是不可取的，因为它们的划分信息非常大（参见式（3.9））。另外，可能无法对包含的IP地址、URL或参考者的测试实例进行分类，这些实例不存在于训练数据中。最后，通过将每个日志条目视为一个单独的数据实例，我们忽略了客户端检索的网页序列这一关键信息，即可以帮助区分Web机器人访问与人类用户的访问。
将每个Web会话视为数据实例是一种更好的选择。Web会话是客户在访问网站期间发出的一系列请求，每个Web会话都可以模拟为有向图，其中结点对应于网页，边对应于将一个网页连接到另一个网页的超链接。图3.15b显示了日志文件中给出的第一个Web会话的图形表示。每个Web会话都可以使用一些关于含有歧视性信息图形的有意义的属性进行表示。图3.15c显示了从图中提取的一些属性，包括扎根于网站入口处的相应树的深度和宽度。例如，图3.15b所示的树的深度和宽度都等于2。
3.15c显示的派生属性比日志文件中给出的原始属性包含更多信息，因为它们表示了客户端在网站上的行为。由于Web机器人（1级）和人类用户（0级）的会话数量相等，因此使用该方法创建了一个包含2916个实例的数据集。其中10％的数据用于训练，139其余90％用于测试。生成的决策树如图3.16所示，该决策树在训练集上的错误率为3.8％，在测试集上的错误率为5.3％。除了低错误率之外，决策树还显示了一些有趣的属性，有助于区分Web机器人与人类用户：
1) Web机器人的访问往往是广泛但浅显的，而人类用户的访问往往更集中（视野狭窄但深入）。
2) Web机器人很少检索与网页关联的图像页面。
3) 由Web机器人产生的会话往往很长，并且包含大量请求页面。
4) 由于人类用户检索的网页通常由浏览器缓存，所以Web机器人比人类用户更可能对同一网页重复请求。
3.3.6 决策树分类器的特征
以下是对决策树归纳算法的重要特征的总结。
1) 适用性：决策树是构建分类模型的非参数化方法。这种方法不需要任何关于管理数据的类别和属性概率分布的先验假设，因此适用于各种各样的数据集。它也适用于连续可分类数据，而不需要通过二值化、标准化或规范化将属性转换为通用表示。与第4章描述的某些二分类器不同，它也可以处理多分类问题，而不需要将它们分解为多个二分类任务。决策树分类器的另一个吸引人的特点是诱导树，特别是较短的树，相对容易解释。对许多简单的数据集，树的准确率也与其他分类技术相当。
2) 表达能力：决策树为离散值函数提供了一个通用表示。换句话说，它可以编码任何离散值属性的函数。这是因为每个离散值函数都可以表示为一个赋值表，其中每个离散属性的唯一组合都被赋予一个类别标签。由于每个属性组合可以表示为决策树中的一个叶结点，我们总能找到一个决策树，其叶结点处的标签分配与原始函数的分配表相匹配。当某些独特的属性组合可以由同一叶结点表示时，决策树还可以帮助提供紧凑的函数表示。例如，图3.17显示了涉及四个二元属性的布尔函数（A∧B）∨（C∧D）的分配表，从而导致总共24=16个可能的分配。图3.17中的树显示了此分配表的压缩编码。不需要具有16个叶结点的完全生长的树，可以使用仅具有7个叶结点的更简单的树对函数进行编码。尽管如此，并非所有离散值属性的决策树都可以被简化。一个值得注意的例子是奇偶校验函数，当其布尔属性中存在偶数个真值时，其值为1，否则为0。这种函数的精确建模需要一个带有2d个结点的完整决策树，其中d是布尔属性的数量（请参阅习题1）。
3) 计算效率：由于决策树的数量可能非常大，因此许多决策树算法采用基于启发式的方法来指导它们在广阔的假设空间中进行搜索。例如，3.3.4节介绍的算法使用自顶向下的贪心递归划分策略来生成决策树。对于许多数据集，即使训练集的规模非常大，这种技术也能快速构建合理的决策树。此外，一旦构建了决策树，可迅速对测试记录进行分类，最坏情况下的复杂度为O（ω），其中ω是树的最大深度。
4) 处理缺失值：在训练集和测试集中，决策树分类器都可以通过多种方式处理缺失的属性值。当测试集有缺失值时，如果给定的测试实例缺少划分结点属性的值，则分类器必须决定遵循哪个分支。C4.5决策树分类器采用概率划分法（probabilistic split method），根据缺失属性具有特定值的概率将数据实例分配给划分结点的每个子结点。相比之下，CART算法使用替代拆分法（surrogate split method），142将划分属性值缺失的实例根据其他非缺失替代属性的值分配给其中一个子结点，其中所述的其他非缺失替代属性划分最类似于基于缺失属性的划分。CHAID算法使用了另一种称为独立类法（separate class method）的方法，将缺失值视为与划分属性的其他值不同的单独分类值。图3.18显示了处理决策树分类器中缺失值的三种不同方式的示例。处理缺失值的其他策略基于数据预处理，其中有缺失值的实例在分类器被训练之前，利用模式（对于分类属性）或平均值（对于连续属性）进行估算或丢弃。
在训练过程中，如果属性ν在某个与结点相关的训练实例中为缺失值且该属性用于划分，则需要一种方法来测量纯度增益。一种简单的方法是在计算与每个子结点关联的实例的计数中排除具有缺失值ν的实例，并为每个可能的结果ν生成该实例。此外，如果选择ν作为结点上的属性测试条件，则可以使用上述任何方法将缺失值ν的训练实例传播到子结点，以处理测试实例中的缺失值。
5) 处理属性之间的相互作用：属性被认为是相互作用的，一起使用时能够区分类别，但是它们单独使用只能提供很少或不提供信息。由于决策树中划分标准的本质是贪心的，这些属性可能会与其他不太有效的属性一起使用，这可能导致生成非必要的更为复杂的决策树。因此，当属性之间存在相互作用时，决策树可能表现不佳。
为了说明这一点，考虑图3.19a所示的三维数据，其中包含来自两个类的数据点，一个类包含2000个，在图中表示为“+”和“o”。图3.19b显示了涉及属性X和Y的二维空间中两个类的分布，这是XOR布尔函数的噪声版本。可以看到，尽管这两个类在这个二维空间中很好地分离，但是这两个属性单独使用时都没有足够的信息来区分这两个类。例如，以下属性测试条件的熵（X≤10和Y≤10）接近于1，表明单独使用时，X和Y都不会减少不纯性度量。因此表明X和Y是相互作用的属性。数据集还包含第三个属性Z，其中两个类均匀分布如图3.19c和3.19d所示，可得出任何涉及Z的划分的熵都接近1。因此，Z可能被选作划分有相互作用但有效的属性X和Y。为了进一步说明这个问题，读者可以参考本章的例3.7和本章最后的练习7。
6) 处理不相关的属性：如果属性对分类任务无用，则属性无关紧要。由于不相关的属性与目标类别标签的关联性很差，它们在纯度上几乎没有增益，因此将被其他更相关的特性所忽略。由此可知，少量不相关属性的存在不会影响决策树构建过程。然而，并非所有提供很少或无增益的属性都不相关（见图3.19）。如果分类问题是复杂的（例如涉及属性之间的相互作用）并且存在大量不相关的属性，那么在树生长过程中可能会意外地选择这些属性中的一些，因为它们在一些偶然情况下可能会提供比相关属性更好的增益。特征选择技术可以通过预处理过程消除不相关的属性来帮助提高决策树的准确性。3.4节会探讨大量不相关属性的问题。
7) 处理冗余属性：如果属性与数据中的另一个属性强相关，则该属性是多余的。由于冗余属性在被选择用于划分时显示出相似的纯度增益，因此在决策树算法中只有其中一个属性被选为属性测试条件。由此可知，决策树可以处理冗余属性的存在。
8) 使用直线划分：本章到目前为止描述的测试条件一次只涉及一个属性。因此，树的生长过程可以看作将属性空间划分为不相交区域的过程，直到每个区域包含相同类别的记录为止。不同类别的两个相邻区域之间的边界称为决策边界（decision boundary)。图3.20显示了决策树以及二分类问题的决策边界。由于测试条件只涉及单个属性，因此决策边界是直线，即平行于坐标轴。这限制了决策树在表示具有连续属性数据集的决策边界时的表达能力。图3.21显示了一个涉及二分类的二维数据集，该数据集不能通过其属性测试条件，基于单个属性定义的决策树对数据进行完全分类。数据集中的二分类是由两个倾斜的高斯分布生成的，分别集中在（8，8）和（12，12）处。真正的决策边界用对角虚线表示，而决策树分类器产生的直线决策边界用粗实线表示。相反，倾斜决策树（oblique decision tree）可以通过允许使用多个属性指定测试条件来克服这个限制。例如，图3.21所示的二分类数据可以很容易地用具有单个根结点的测试条件x+y<20的倾斜决策树表示。
尽管倾斜决策树具有更强的表达能力，可以生成更紧凑的树，但寻找最佳测试条件的计算量更大。
9) 不纯性测量的选择：应该指出，不纯性测量的选择通常对决策树分类器的性能没有影响，因为许多不纯性测量值彼此非常一致，如图3.11所示。相反，用于修剪树的策略对最终树的影响大于不纯性度量的选择。
3.4 模型的过拟合
目前提出的分类模型学习方法试图在训练集上显示最低误差。但是，正如下面的例子将要展现的那样，有的模型即使能够很好地覆盖训练数据，但它仍然可能表现出较差的泛化性能，这种现象称为模型的过拟合（model overfitting）。
例3.5 决策树的过拟合和欠拟合 考虑图3.22a所示的二维数据集。数据集中的实例属于两个类，分别标记为“+”和“o”，每个类都有5400个实例。所有属于“o”类的实例服从均匀分布。在“+”类中，5000个实例的生成服从高斯分布，并通过单位方差法集中在（10，10)处，而其余400个实例的采样与“o”类一样服从均匀分布。由图3.22a可知，通过绘制一个以（10，10）为中心的适当大小的圆，可以很大程度地将“+”类与“o”类区分开来。为了生成这个二维数据集的分类器，随机抽取10%的数据进行训练，剩余90%用于测试。图3.22b所示的训练集看起来非常有代表性。我们使用基尼指数作为不纯性度量来构造决策树，通过递归将结点扩展到子结点，直到每个叶结点都是纯的，以此增加树的规模（叶结点数），详见3.3.4节。
图3.23a显示了树的大小从1到8变化时，训练集和测试集错误率的变化趋势。树在最初只有一个或两个叶结点时，错误率都很高。这种情况称作模型欠拟合（model undertting）。若学习的决策树过于简单，则会导致欠拟合，以致无法充分表示属性与类别标签之间的真实关系。随着将树的大小从1增加到8，我们有两个发现。首先，由于较大的树能够表示更复杂的决策边界，所以错误率会降低。其次，训练集和测试集的错误率十分接近，这表明训练集在性能上足以代表泛化性能。随着进一步将树的大小从8增加到150，训练错误率继续稳定下降，直至最终达到零，如图3.23b所示。然而，与此形成鲜明对比的是，测试错误率在树的规模到达某一值时停止下降，之后开始增加。一旦树的规模变得太大，训练错误率将不再足以评估测试集的错误率。此外，随着树的规模不断增大，训练错误率和测试错误率之间的差距不断扩大。这种看起来有悖直觉的现象被称为模型过拟合（model overfitting）。
模型过拟合的原因
模型过拟合指的是在追求训练错误率最小化的过程中，选择了一种过于复杂的模型，这种模型捕捉到了训练数据中的特定模式，但是没能获取到整体数据中属性和类别标签之间的本质关系。为了说明这一点，图3.24给出了两棵大小分别为5和50的决策树及其相应的决策边界（阴影矩形表示分配给“+”类的区域）。可以看出，大小为5的决策树显得非常简单，它的决策边界为最佳决策边界提供了一个合理的近似值，在这种情况下，它对应于以（10，10）处的高斯分布为中心的圆。149虽然它的训练和测试错误率非零，但是它们十分接近，这表明在训练集中学习到的模式能很好地泛化到测试集。另一方面，规模为50的决策树比规模为5的决策树看上去更复杂，同时具有繁复的决策边界。例如，一些阴影矩形（分配给“+”类）试图覆盖输入空间中仅包含一个或两个“+”类训练实例的狭窄区域。需要注意的是，150这类区域中的“+”实例在训练集中具有高度特异性，因为这些区域主要由整体数据集中的“-”实例占据。因此，为了完美拟合训练数据，规模为50的决策树开始调整以适配测试集中的特定模式，导致在独立选择的测试集上性能较差。
影响模型过拟合的因素有很多。在下文中，我们简要说明两个主要因素：有限的训练规模和过高的模型复杂度。尽管它们并非详尽无遗，但它们之间的相互影响可以帮助解释大多数现实应用中常见的过拟合现象。
1.有限的训练规模
需要注意的是，由有限个实例组成的训练集仅能对整体数据进行有限表示。因此，从训练集中学习得到的模式不能完全代表整体数据的实际模式，从而导致模型过拟合。一般来说，随着我们增大训练集的规模（训练实例的数量），从训练集中学习得到的模式与整体数据的实际模式越来越类似。因此，通过增大训练规模可以减少过拟合的影响，如下例所示。
例3.6 训练规模的影响 假设使用的训练实例数量是例3.5实验中使用的两倍。具体地，我们使用20％的数据进行训练，剩下的数据用于测试。图3.25b显示了树的大小从1变化到150时的训练和测试错误率。该图的变化趋势与图3.23b显示的变化趋势存在两个主要区别（仅使用10％的数据用于训练时）。首先，尽管两个图中的训练错误率都随着树规模的增大而减小，但当我们使用两倍规模的训练数据时，训练错误率的下降速率要小得多。其次，对于给定大小的树，当我们使用两倍训练数据时，训练与测试错误率之间的差距要小得多。这些差异表明，相比于使用10%的数据进行训练学习得到的模式，使用20%的数据进行训练得到的模式具有更好的泛化能力。
图3.25a显示了用20%的数据进行训练时，大小为50的树的决策边界。对于相同大小的树，与使用10%的训练数据（见图3.24d）学习的结果相反，我们可以看到决策树没有捕获训练集中“+”类噪声实例的特定模式。相反，具有50个叶结点的高模型复杂度常被用于学习以（10，10)为中心的“+”类实例的边界。
2.高模型复杂度
通常，较为复杂的模型能够更好地表示数据中的复杂模式。例如，与叶结点数较少的决策树相比，具有较多叶结点的决策树可以表示更复杂的决策边界。但是，一个过于复杂的模型倾向于学习训练集中的特定模式，而这类模型不能很好地概括那些隐藏的实例。因此，对于高度复杂的模型，应谨慎使用，避免出现过拟合现象。
从训练集中需要推导出的参数个数是模型复杂度的一种度量方式。例如，在决策树构造过程中，内部结点的属性测试条件数量与从训练集中推导出的模型参数数量一致。具有大量属性测试条件（导致更多叶结点）的决策树具有更多的“参数”，因此更为复杂。
给出一类模型以及一定数量的参数，一个学习算法试图筛选出令训练集的评价矩阵（例如，准确率）最大化的最佳参数值组合。152如果参数值的组合数很多（因此复杂度更高），学习算法需要通过有限的训练集，从大量可能的组合中筛选出最佳组合。在这种情况下，学习算法很有可能筛选出一个虚假的参数组合，由于随机因素导致了评价矩阵最大化。这类似于统计学中的多重比较问题（multiple comparisons problem）（也称多重测试问题）。
为了说明多重比较问题，考虑对未来10个交易日股市涨跌进行预测的任务。如果一位股票分析师的预测只是随机猜测，那么对于任意交易日的预测，其准确率都是0.5。然而，在10次预测中至少正确9次的概率为
该概率是极低的。
假设我们要从200位股票分析师中挑选出一位投资顾问。策略是挑选出在未来10个交易日中，能做出最多正确预测的分析师。这种策略的缺点是，假设所有分析师的预测都是随机产生的，那么至少有一人正确预测不少于9次的概率为1-（1-0.0107)^200=0.8847这是非常高的。尽管对于每个分析师，正确预测不小于9次的概率都很低，但综合考虑后，至少找到一个这样的分析师的概率是很高的。然而，我们无法确保这样一个分析师在未来能通过随机猜测的方法一直做出正确的预测。
多重比较问题与模型过拟合有什么关系呢？在学习分类模型的过程中，每个参数值组合都相当于一个分析师，而训练实例的数量相当于天数。类似于挑选出在连续日内，预测准确率最高的分析师的任务，学习算法的任务是挑选出最适配训练集的参数值组合。如果参数组合很多，但训练规模很小，最有可能的原因是学习算法选取了虚假的参数组合，这些组合由于随机因素导致了高的训练准确率。在下面的例子中，我们将阐述在构造决策树的过程中，因多重比较所导致的过拟合现象。
例3.7 多重比较和过拟合 考虑图3.26中包含了500个“+”类实例和500个“o”类实例的二维数据集，其类似于图3.19表示的数据。在这个数据集中，二维（X-Y）属性空间将两个类的分布清晰地分割开，但是这两个属性（X或Y）单独的信息量均不足以区分这两个类。因此，基于X属性或Y属性的任意值对数据集进行划分，会使不纯性度量接近于0。但是，如果同时使用X和Y属性作为划分依据（例如，在（X，Y)取值为（10，10)时进行划分)，则可以有效地对这两个类进行划分。
图3.27a显示了学习不同大小决策树时的训练和测试错误率，其中，30%的数据用于训练，其余的用于测试。我们可以看到，在叶结点数很少的时候，两个类就可以很容易被分开。图3.28显示了具有6个叶结点的树的决策边界，树杈按其在树中出现的顺序进行编号。值得注意的是，虽然分割1和3后获得的增益微乎其微，但是在它们之后对（2，4，5）进行划分可以提供巨大的增益，从而使得对这两个类的区分是有效的。
假设我们在二维数据X-Y中添加100个不相关属性。从这一合成数据中学习决策树将具有挑战性，因为在每个内部结点上进行划分选择时，候选属性的数量将从2个增加到102个。由于候选属性的测试条件繁多，很可能因为多重比较问题，使得内部结点选择虚假的属性测试条件。图3.27b显示了向训练集添加100个不相关属性后的训练误差和测试误差。155可以看到，即使使用50个叶结点，测试错误率也保持在接近0.5的水平，而训练错误率持续下降，最终变为0。
3.5 模型选择
现有许多可行的分类模型，它们具有不同层次的模型复杂性，可用于捕获训练数据中的模式。在这些可选项中，我们需要选择的是泛化错误率最低的模型。模型选择（model selection）指的是选择出复杂度适合且可以很好地泛化到隐藏的测试实例的模型。如上节所述，训练错误率不能可靠地作为模型选择的唯一标准。下面，我们将介绍三种通用的方法来评估模型的泛化能力，以此用于模型选择。本节主要讲述如何在决策树归纳中使用这些方法的特定策略。
3.5.1 验证集应用
值得注意的是，我们总是可以通过“样本外”估计来评估模型的泛化错误率，例如，可以在一个单独的验证集（validation set）上对模型进行评估，该集合未被用于模型训练。由于验证集未被用于训练模型，因此验证集的错误率（称为验证错误率）比训练错误率更能说明泛化性能。以下将介绍验证错误率在模型选择中的应用。
给定一个训练集D.train，我们可以将D.train划分为两个更小的子集——D.tr和D.val，其中，D.tr用于训练，而D.val作为验证集。例如，将D.train的23作为D.tr用于训练，剩余13作为D.val用于计算验证错误率。对于任何经过D.tr训练的分类模型m，我们可以通过D.val评估它的验证错误率——errval（m)。其中，errval（m)值最小的模型即为首选模型。
验证集的使用为模型选择提供了一种通用的方法。然而，这种方法具有一个局限性，它对从D.train中获得的D.tr和D.val的大小很敏感。如果D.tr的规模很小，可能会导致学习到一个性能不佳的分类模型，156这是因为较小的训练集不能很好地代表整体数据。另一方面，如果D.val的规模很小，使用验证错误率选择模型将变得不可靠，因为它仅在少量实例上进行计算。
例3.8 验证错误 在下面的示例中，我们演示了在决策树归纳中使用验证集的一种可行方法。对于图3.30生成的决策树，图3.29显示了其叶结点上的预测标签。位于叶结点下的计数表示验证集中到达该结点的数据实例比例。根据结点的预测标签，左树的验证错误率为，右树的验证错误率为
。基于它们的验证错误率，右树比左树更适合。
3.5.2 模型复杂度合并
由于模型越复杂，发生过拟合的可能性越大，因此模型选择方法不仅要考虑训练错误率，还要考虑模型的复杂度。这一策略来源于众所周知的奥卡姆剃刀原理（Occam’s razor），也就是所谓的节俭原则（principle of parsimony）。它表明，如果两个模型具有相同的误差，157较简单的模型将优于较复杂的模型。在评估泛化性能的同时考虑模型复杂度的一般方法如下所示。
给定一个训练集D.train，考虑学习一个属于模型M的分类模型m。例如，如果M代表所有可能的决策树的集合，那么m可以对应一个从训练集中学习到的特定决策树。我们对m的泛化错误率gen.error（m)有兴趣。如前文所述，当模型复杂度较高时，m的训练错误率train.error（m，D.train)会低估gen.error（m)。因此，我们在使用训练错误率的同时，还使用模型M的复杂度complexity（M)来表示gen.error（m)函数，如下所示：
其中，α是一个超参数，用于协调最小化训练错误和降低模型复杂度。一个过大的α取值在评估过程中更强调模型复杂度对泛化性能的影响。可以使用3.5.1节描述的利用验证集的方法选择合适的α值。例如，可以遍历α的所有可取值，从训练集的一个子集D.tr中学习到一个模型，然后通过一个独立的子集D.val计算得到模型的验证错误率。最后选择使验证错误率最低的α取值。
式（3.11）提供了一种可行的方法，将模型复杂度纳入对泛化性能的评估中。该方法成为许多用于评估泛化性能的技术的核心，例如结构风险最小化原则、赤池信息准则（Akaike’s Information Criterion，AIC）、贝叶斯信息准则（Bayesian Information Criterion，BIC）。结构风险最小化原则是学习支持向量机的基础，该部分会在第4章进行探讨。有关AIC和BIC的更多细节，请参阅参考文献。
下面将介绍两种不同的方法来评估模型的复杂度complexity（M)。前者专门用于决策树模型，而后者适用于任何类型的模型，更为通用。
1.决策树复杂度评估
决策树的复杂度可以用叶结点数与训练实例数的比值进行评估。设k为叶结点数，Ntrain为训练实例数。决策树的复杂度可用kNtrain表示。直观上，对于大规模的训练集，我们可以学习到一种具有大量叶结点的决策树，而其复杂度又不会太高。决策树T的泛化错误率可由式（3.11）计算得出，具体如下：
其中，err（T)是决策树的训练误差，Ω是权衡减小训练误差和最小化模型复杂度的超参数，类似于式（3.11）中使用的α。Ω可以看作为了防止训练误差，每添加一个叶结点的成本。在决策树归纳的文献中，上述评估泛化错误率的方法也称为悲观误差估计（pessimistic error estimate）。称其为悲观是因为它假设泛化错误率比训练错误率要差（通过增加模型复杂性的惩罚项）。与之相对，简单地使用训练错误率来评估泛化错误率，被称为乐观误差估计（optimistic error estimate）或再代入估计（resubstitution estimate）。
例3.9 泛化错误率估计 考虑图3.30中的两棵二叉决策树TL和TR。这两棵树由相同的训练数据生成的，159TL是通过扩展了TR的三个叶结点生成的，叶结点上的计数表示训练实例的类分布。如果根据到达叶结点的大多数训练实例标记该结点，则左树的训练错误率为err（TL)=424=0.167，右树的训练错误率为err（TR)=624=0.25。仅根据训练错误率进行评估，认为TL优于TR，即使TL比TR更复杂（即包含更多的叶子结点）。
现假设每个叶结点的成本Ω=0.5。然后，TL的泛化错误率估计为
TR的泛化错误率估计为
由于TL的泛化错误率较低，因此依旧认为TL优于TR。需要注意的是，Ω=0.5意味着如果一个结点增加了至少一个训练实例的预测，那么这个结点应该扩展出两个子结点，因为扩展结点的成本比对训练实例进行分类的成本更低。此外，如果Ω=1，TL的泛化错误率为errgen（TL)=1124=0.458，TR的泛化错误率为errgen（TR)=1024=0.417。此时由于TR的泛化错误率更低，因此认为TR优于TL。这个例子说明了基于泛化错误率估计对决策树进行选择时，Ω的不同取值会改变我们的选择偏好。然而，对于一个给定的Ω取值，悲观误差估计提供了一种方法，用于对未知测试实例的泛化性能进行建模。验证集有助于Ω取值的选择。
2.最小描述长度原则
另一种合并模型复杂性的方法是基于信息理论的方法，即最小描述长度原则（Minimam Description Length，MDL）。图3.31中的示例阐明了这种方法。在该示例中，A和B都被分类配了一组属性值x已知的实例。假设A知道所有实例中哪些类别标签为y，而B不知道。A希望向B发送包含类别标签信息的消息，与B实现类信息共享。消息包含Θ（N)位的信息，其中N表示实例数量。
或者，A可以不直接发送类别标签信息，而是根据实例构建一个分类模型，将其传给B。然后B可以利用该模型来确定实例的类别标签。如果该模型的准确率是100%，那么传输的成本等于模型编码所需的比特数。否则，A还必须传递关于哪些实例被模型错误分类的信息，以便B能够重新生成相同的类别标签。因此，总传输成本，即消息的描述长度为
右边的第一项是对被错误分类的实例进行编码所需的位数，第二项是对模型进行编码所需的位数。α是一个用于平衡错误的实例分类和模型之间相对成本的超参数。需要注意这个方程和式（3.11）中计算泛化错误率的通式之间的相似之处。一个好的模型，其总描述长度要小于编码整个类别标签序列所需的比特数。此外，给定两个对比模型，总描述长度较小的模型更好。习题10给出了一个如何计算决策树的总描述长度的示例。
3.5.3 统计范围估计
除了使用式（3.11）的方法估计模型的泛化错误率，还可对模型的训练错误率进行统计修正，用以表明模型的复杂性。如果训练错误率的概率分布是可用的或可被假设的，就可以对训练错误率进行统计修正。例如，可以假设决策树中叶结点所提交的错误数量服从二项分布。因此，我们可以计算用于模型选择的训练错误率上限，如下面的示例所示。
例3.10训练错误率的统计界限 考虑图3.30所示的二叉决策树的最左侧分支。观察到TR最左侧的叶结点扩展出了TL中的两个子结点。在分裂之前，结点的训练误差为27=0.286。通过用正态分布近似二项分布，可以得到训练误差e的上界，如下式所示：
其中，α是置信水平，zα2是标准正态分布的标准值，N是用于计算e的训练实例总数。当α=25%，N=7，e=27时，错误率的上界为eupper（7，27，0.25)=0.503，对应于7×0.503=3.521的误差。如果扩展出这些结点的子结点，如TL所示，那么这些子结点的训练错误率分别为14=0.250和13=0.333。使用式（3.13)，这些错误率的上界分别为eupper（4，14，0.25)=0.537和eupper（3，13，0.25)=0.650。子结点的整体训练误差为4×0.537+3×0.650=4.098，大于TR中对应结点的估计错误率，因此认为不应该划分TR的叶结点。
3.5.4 决策树的模型选择
基于以上介绍的通用方法，我们提出了两种常用的决策树归纳模型选择策略。
预剪枝（早停规则） 在这种方法中，在生成一个完美适配整个训练集的完全树之前，树生长算法就会停止。162为此，必须使用更为严格的停止条件。例如，在泛化错误率估计中，观察到增益下降到某个阈值以下时，停止扩展叶结点。泛化错误率的估计可以使用前面三小节给出的任何方法来计算，例如使用悲观误差估计、检验误差估计或统计界限。预剪枝的优势在于避免了与过度复杂的子树的相关计算，该子树的复杂源于过度拟合训练数据。然而，该方法的一个主要缺点是，使用现有的划分准则即使没有获得明显的增益，但随后的划分可能会得到更好的子树。如果由于决策树归纳的贪婪性质而使用预剪枝，则不会得到这样的子树。
后剪枝 在这种方法中，决策树首先增长到它的最大规模。之后再对树进行剪枝，该步骤以自下而上的方式对完全树进行修剪。修剪可以通过用一个新的叶结点替代一个子树或者使用最常用的分支子树方法（称为子树提升方法）来完成，该叶结点的类别标签是从隶属于该子树的多数类实例中确定的（称为子树替换方法）。当超过某个阈值时，观察到泛化错误率估计不再进一步改善，剪枝步骤终止。同样，泛化错误率的估计可以使用前面三小节中给出的任何方法来计算。与预剪枝相比，后剪枝倾向于给出更好的结果，因为后剪枝是基于完全树给出剪枝决策，这与预剪枝不同，后者可能会因提前终止树的生长而受到影响。但是，对于后剪枝，在对子树进行剪枝时，可能会浪费用于生成完全树的额外计算。
图3.32展示了3.3.5节中给出的Web机器人检测示例简化后的决策树模型。请注意使用子树提升方法时，在depth=1处生根的子树被一个breadth≤7，width>3且MultiP=1的树分支替换。另一方面，使用子树替换方法时，对应于depth>1且MultiAgent=0的子树被替换为分配给类0的一个叶结点。depth>1且MultiAgent=1的子树保持不变。
3.6 模型评估
上一节讨论了几种模型选择方法，可用于从训练集D.train中学习分类模型。在这里，我们讨论估计其泛化性能的方法，例如，D.train之外的未知实例的性能。这个过程被称为模型评估（model evaluation）。
请注意，3.5节讨论的模型选择方法也使用训练集D.train计算泛化性能的估计值。然而，这些估计值是未知实例性能的偏向指标，因为它们被用来指导分类模型的选择。例如，如果使用验证错误率进行模型选择（如3.5.1节所述），会特意选择能得到最少验证集错误的模型作为结果。因此，验证错误率可能会低估真正的泛化错误率，不能可靠地用于模型评估。
模型评估的正确方法是在被标注的测试集上，对学习模型的性能进行评估，且这些测试集未在模型选择的任何阶段被使用。这可以通过将整个被标记的实例集合D划分为两个不相交的子集来实现，D.train用于模型选择，而D.test用于计算测试错误率errtest。下面将介绍把D划分为D.train和D.test的两种不同方法，并计算测试错误率errtest。
3.6.1 保持方法
划分有标记数据集的最基础技术就是保持方法，其中标记集合D被随机划分为两个不相交的集合，即训练集D.train和测试集D.test。然后使用3.5节中介绍的模型选择方法，从D.train归纳得到分类模型，并用其在D.test中的错误率errtest估计泛化错误率。用于训练和测试的数据保留比例主要由分析师决定，例如，三分之二用于训练，三分之一用于测试。
类似于3.5.1节将D.train划分为D.tr和D.val时所面临的权衡，在标记数据集中，选择用于训练和测试的正确比例是十分重要的。如果D.train的规模很小，使用数量不足的训练实例可能学习到错误的分类模型，从而导致对泛化性能的估计有偏差。另一方面，如果D.test的规模很小，那么errtest可能不太可靠，因为它是基于少量测试实例计算出的。此外，当我们将D随机划分为D.train和D.test时，errtest可能会有很大的变化。
保持方法可以多次重复后获得测试错误率的分布，这种方法称为随机子采样（random subsampling）或重复保持方法。该方法生成的错误率分布有助于理解errtest的方差。
3.6.2 交叉验证
交叉验证是一种广泛应用于模型评估的方法，旨在有效地利用D中所有的标记实例进行训练和测试。为了说明这种方法，假设给定一个有标记的集合，将其随机地划分为三个相同大小的子集S1、S2和S3，如图3.33所示。第一次运行时，使用子集S2和S3训练模型（显示为空白块），165并在子集S1上测试模型。因此，在第一次运行计算中，S1上的测试错误率表示为err（S1)。类似地，在第二次运行中，使用S1和S3作为训练集，S2作为测试集，并计算测试错误率err（S2)。最后，在第三次运行中，使用S1和S2作为训练集，S3作为测试集，并计算测试错误率err（S3)。总的测试错误率由所有运行中的子集测试错误率之和除以总的实例数后得到。这种方法被称为三重交叉验证。
k重交叉验证方法一般指将标记数据D（大小为N）分割成k个相等大小的分区（或子类）的方法。在第i次运行中，D的一个分区作为D.test（i)用于测试，其余的分区作为D.train（i)用于训练。使用D.train（i)学习得到模型m（i)，并在D.test（i)上获得测试错误率之和errsum（i)。该过程重复k次。总测试错误率errtest的计算如下：
因此数据集中的每个实例恰好用于一次测试、（k-1)次训练。每次运行使用（k-1)/k部分的数据进行训练，用1k部分的数据进行测试。
k重交叉验证中k的正确选择取决于问题的若干特征。较小的k值使得每次运行时的训练集较小，这将导致所用得到的泛化错误率估计，比在整个标记集上训练的模型的预期更大。166另一方面，k的取值过高会导致每次运行时的训练集过大，这降低了泛化错误率估计中的偏置。在极端情况下，当k=N时，每次运行只使用一个数据实例进行测试，其余的数据用于测试。这种k重交叉验证的特殊情况称为留一法（leave-one-out）。这种方法的优点是能尽可能多地利用训练数据。但是，如习题11所示，留一法可能会在一些特殊情况下产生十分具有误导性的结果。此外，对于大型数据集，留一法在计算上会很昂贵，因为交叉验证程序需要重复N次。对于大多数实际应用，k在5到10之间进行选择，可提供估计泛化错误率的合理方法，因为每次重复都能够利用80％到90％的标记数据进行训练。
如上所述，k重交叉验证方法产生单一泛化错误率估计，而不提供关于估计方差的任何信息。为了获得这些信息，可以对每种可能的k个数据分区运行k重交叉验证，以此根据每个分区的计算，获得测试错误率分布。使用所有可能的划分的平均测试误差，能得到更稳健的泛化错误率估计。这种估计泛化错误率及其方差的方法称为完全交叉验证（complete cross-validation）法。尽管这样的估计非常稳健，但当数据集规模很大时，要得到所有可能的k个分区，通常代价太过昂贵。更实际的解决方案是多次重复交叉验证方法，每次都随机将数据划分为k个不同的分区，并使用平均测试错误率作为泛化错误率的估计。注意，由于留一法的方法只有一种划分可能，因此不可能估计出泛化错误率的方差，这是该方法的另一个限制。
k重交叉验证不能保证每个分区中正负实例的比例与其在整个数据集中的比例相等。对于该问题，一个简单的解决方法是在k个分区中，执行正负实例的分层抽样，这种方法称为分层交叉验证（stratified cross-validation）。
在k重交叉验证中，每次运行都会学习到不同的模型，然后对于这k个模型，聚合各模型在其测试子类上的性能，计算出总体测试错误率errtest。因此，errtest不反映这k个模型中任何一个模型的泛化错误率。相反，在一个与训练子类N（k-1)k大小一样的训练集上，167它反映了模型选择方法的预期泛化错误率。这与保持方法中计算的errtest不同，后者完全对应于从D.train上学习的特定模型。因此，尽管交叉验证法有效地利用了D中的每个数据实例进行训练和测试，但该方法计算出的errtest并不能代表在特定D.train上学习到的单一模型的性能。
尽管如此，errtest在实践中，通常用于估计基于D构建的模型的泛化错误率。其中一个原因是当训练子类的大小接近整体数据集时（当k很大时），errtest类似于在与D大小相同的数据集上学习到的模型的预期性能。例如，当k为10时，每个训练子类占整体数据的90%。然后，errtest应该接近在超过90%的整体数据上学习到的模型的预期性能，即接近在D上学习到的模型的预期性能。
3.7 超参数的使用
超参数是学习算法的参数，需要在学习分类模型之前确定。例如式（3.11）中出现的超参数α，为方便起见，此处继续使用该参数进行讲解。该等式用于估计模型选择方法的泛化错误率，用于明确表示模型的复杂性（见3.5.2节）。
其他有关超参数的示例，请参阅第4章。
与常规模型参数（例如决策树内部结点中的测试条件）不同，超参数（例如α）不会出现在用于对未标记样本进行分类的最终分类模型中。然而，超参数的取值需要在模型选择期间被确定，该过程称为超参数选择（hyper-parameter selection），同时模型评估期间也需要考虑超参数。幸运的是，稍微修改前一节中描述的交叉验证方法，就可以有效地完成这两项任务。
3.7.1 超参数选择
在3.5.2节中，使用验证集来选择α，这种方法普遍适用于超参数。设p是从有限区间P={p1，p2，…pn}中选取的超参数。168将D.train划分为D.tr和D.val。对于每个超参数的取值pi，可以在D.tr上习得模型mi，并在D.val上获得模型的验证错误率errval（pi)。设p'是验证错误率最低时的超参数值。然后选择p'对应的m'作为最终分类模型。
尽管上述方法有用，但仅使用了整体数据的一个子集D.train进行训练，一个子集D.val进行验证。3.6.2节中介绍的交叉验证框架解决了这两个问题，尽管这种方法常用于模型评估。这里将指出如何使用交叉验证方法进行超参数选择。为了介绍这种方法，将D.train分成三个部分，如图3.34所示。每次运行时，其中一个子类作为D.val用于验证，剩余两个子类作为D.tr用于训练，每个超参数的取值为pi。对三个子类中的错误率求和，以此计算对应于每个pi的总体验证错误率。之后，选择验证错误率最低时的超参数p'，并使用它在整个训练集D.train上习得模型m'。
算法3.2概括了上述使用k重交叉验证框架进行超参数选择的方法。在第i次交叉验证中，第i个子类的数据作为D.val（i)用于验证（步骤4），而D.train中的其余数据作为D.tr（i)用于训练（步骤5）。然后，对于每个超参数的取值pi，在D.tr（i)上学习一个模型（步骤7），并应用于D.val（i)以计算其验证误差（步骤8）。这用于计算在所有子集上使用pi习得的模型对应的验证错误率（步骤11）。验证错误率最低时的超参数p'（步骤12）用于在整体训练集D.train上学习最终模型m'（步骤13）。169因此，在该算法结束时，可以获得超参数的最佳选择以及最终的分类模型（步骤14），这两者都是通过有效利用D.train中的每个数据实例获得的。
3.7.2 嵌套交叉验证
上一节提供了一种有效利用D.train中的所有实例来学习分类模型的方法，该方法需要进行超参数选择。该方法可以在整个数据集D上习得最终分类模型。然而，在D上使用算法3.2只能得到最终分类模型m'，不能估计模型的泛化性能errtest。回想一下，算法3.2使用的验证错误率不能用于估计泛化性能，因为它们是用于指导最终模型m'选择的。但是，为了计算errtest，我们可以再次使用交叉验证框架来评估在整个数据集D上的性能，如3.6.2节所述。在这种方法中，每次交叉验证运行时，D都被划分为用于训练的D.train和用于测试的D.test。当涉及超参数时，可以在每次运行时，使用算法3.2在D.train上训练模型，从而在模型选择“内部”使用交叉验证。这种方法称为嵌套交叉验证（nested cross-validation）或双重交叉验证。算法3.3描述了有超参数的情况下，使用嵌套交叉验证估计errtest的完整过程。
图3.35将集合D划分为D.train和D.test后使用三重交叉验证，对该方法进行了说明。在该方法的第i次运行中，其中一个子类作为测试集D.test（i)，剩余两个子类作为训练集D.train（i)。这在图3.35中表示为第i个“外部”运行。为了使用D.train（i)选择模型，在每次内部运行中（即迭代，共三次），将D.train（i)划分为D.tr和D.val，然后再次使用“内部”三重交叉验证框架。如3.7节所述，我们可以使用内部交叉验证框架来选择最佳超参数值p'（i)，并在D.train（i)上学习得到分类模型m'（i)。然后我们可以在D.test（i)上应用m'（i)，获得第i个外部运行的测试误差。通过在每个外部运行中重复该过程，我们可以计算出整个标记集D的平均测试错误率errtest。请注意，在上述方法中，内部交叉验证框架用于模型选择，而外部交叉验证框架用于模型验证。
3.8 模型选择和评估中的陷阱
有效地应用模型选择和评估，可作为学习分类模型以及评估其泛化性能的优秀工具。然而，在实际环境中有效地使用它们时，存在一些会导致错误的或有误导性的结论的陷阱。其中一些陷阱很容易理解，也很容易避免，而其他一些陷阱本质上非常微妙，难以捕捉。在下文中，我们将介绍其中的两个陷阱，并讨论用于避免它们的最佳措施。
3.8.1 训练集和测试集之间的重叠
对于一个没有瑕疵的模型选择和评估方案，基本要求之一是用于模型选择的数据（D.train）必须与用于模型评估的数据（D.test）分开。如果两者之间存在重叠，在D.test上计算得到的测试错误率errtest不能代表未知实例的性能。使用errtest比较分类模型的有效性可能会产生误导，因为过于复杂的模型可能会由于模型过拟合而显示出错误的errtest低取值（参见本章习题12）。
为了说明确保D.train和D.test之间不重叠的重要性，考虑属性都是不相关的标记数据集，即这些属性与类别标签没有关系。使用这些属性时，认为分类模型没有随机猜测的执行效果好。但是，如果测试集包含的数据实例（即使是少量的）用于训练，则过于复杂的模型的性能可能比随机分类器表现得更好，即使属性是完全无关的。正如第10章将阐述的那样，这种情况实际上可以作为评判标准，用于检测由于实验设置不当而导致的过拟合。如果模型对不相关属性显示出比随机分类器更好的性能，它也能体现训练集和测试集之间的潜在反馈。
3.8.2 使用验证错误率作为泛化错误率
验证错误率errval在模型选择过程中起着重要作用，因为它提供了模型在未用于模型训练的实例D.val上的“样本外”误差估计。因此，与用于模型选择和超参数取值的训练错误率相比（分别于3.5.1节和3.7节所述），172errval是更好的度量标准。但是，一旦验证集用于选择分类模型m'，errval就不再能反映出m'在未知实例上的性能。
为了明晰使用验证错误率作为泛化性能估计时的陷阱，考虑使用验证集D.val，从值域P中选择出取值为p的超参数的问题。如果P中的可取值数量非常大并且D.val的规模很小，则可以随机在D.val上选择出性能良好的超参数p'。请注意此问题与3.4.1节讨论的多重比较问题的相似性。尽管使用p'学习的分类模型m'具有较低的验证错误率，但它缺乏在未知测试实例上的普适性。
估计模型m'的泛化错误率的正确方法是使用独立选择的测试集D.test，而该测试集未以任何方式用于影响m'的选择。根据经验，在模型选择过程中不应检查测试集，以确保不存在任何形式的过拟合。如果从标记数据集的任意部分获得了可以改进分类模型的助力，即使是以间接的方式，那么在测试期间也必须丢弃该部分数据。
3.9 模型比较
比较不同分类模型性能时的一个困难是，观察到的性能差异是否具有统计显著性。例如，考虑两个分类模型MA和MB。假设在包含30个实例的测试集上进行评估时MA的准确率为85％，而MB在另一个包含5000个实例的测试集上的准确率为75％。基于这些信息，MA是比MB更好的模型吗？此示例提出了两个关于性能指标统计显著性的关键问题：
1) 尽管MA具有比MB更高的准确率，但它是在较小的测试集上进行测试的。我们可以在多大程度上认为MA实际上的准确率是85％？
2) 是否有可能解释为，由于测试集的组成发生了变化，造成了MA和MB准确率之间的差异？
第一个问题涉及对模型准确率置信区间的估计。第二个问题涉及对观测偏差统计显著性的测试。本节的其余部分将对这些问题进行研究。
3.9.1 估计准确率的置信区间
为了确定准确率置信区间，我们需要构建样本准确率的概率分布。本节描述了通过二项式随机实验模拟分类任务，从而获得置信区间的方法。以下描述了该实验的特征：
1) 随机实验由N个独立试验组成，每个试验有两种可能的结果：成功或失败。
2) 每次试验的成功概率p是不变的。
二项式实验的一个例子是计算硬币投掷N次时正面朝上的次数。如果X是在N次试验中观察到的成功次数，那么X取特定值的概率由均值为Np、方差为Np（1-p)的二项式分布给出：
例如，如果掷币是公平的（p=0.5），并投掷50次，那么出现20次正面朝上的概率为：
如果实验重复多次，则预期的正面朝上的平均次数为50×0.5=25，方差为50×0.5×0.5=12.5。
对测试实例类别标签的预测任务也可看作二项式实验。给定一个包含N个实例的测试集，设X为模型正确预测的实例数，p为模型实际准确率。如果预测任务被模拟为二项式实验，则X符合二项式分布，其均值为Np、方差为Np（1-p)。可以证明，实验准确率acc=XN也符合二项式分布，其均值为p、方差为p（1-p)N（见习题14）。当N足够大时，二项式分布可以通过正态分布来近似。根据正态分布，acc的置信区间推导如下：
其中，是在置信水平（1-α）上通过标准正态分布获得的上限和下限。由于标准正态分布关于Z=0对称，因此
。重新排列该不等式，则p的置信区间如下：
下表显示了不同置信水平下Zα2的值：
例3.11 准确率的置信区间 在100个测试实例上进行评估时，考虑精度为80％的模型。在95％置信水平下，其真实准确率的置信区间是多少？根据上面给出的表，95％的置信水平对应于Zα2=1.96。将该项代入式（3.16）可得到71.1％～86.7％的置信区间。下表显示了实例数N增加时的置信区间：
注意，当N增加时，置信区间变得更紧密。
3.9.2 比较两个模型的性能
考虑两个模型M1和M2，分别在两个独立的测试集D1和D2上进行评估。设n1表示D1中的实例数，n2表示D2中的实例数。另外，假设M1在D1上的错误率为e1，M2在D2上的错误率为e2。我们的目标是测试从e1和e2之间观察到的差异是否具有统计学意义。
假设n1和n2足够大，则可以使用正态分布来估计错误率e1和e2。如果观察到的错误率差异表示为d=e1-e2，则d也符合正态分布，175其均值为dt（真实差值）且方差为σ2d。方差d计算如下：
其中，是错误率的方差。最后，在（1-α)％置信水平下，可以证明真实差异dt的置信区间如下式：
例3.12 显著性检测 考虑本节开头描述的问题。当测试实例数N1=30时，模型MA的错误率e1=0.15；当测试实例数N2=5000时，模型MB的错误率e2=0.25。观察到的错误率差异为d=0.15-0.25=0.1。在此示例中，我们正在执行双侧检验以检查dt=0或dt≠0。观察到的错误率差异的估计方差计算如下：
或σd=0.0655。将该值代入式（3.18），在95％置信水平下获得dt的置信区间，如下：
当区间跨越零值时，可以得出结论，即观察到的差异在95％置信水平下没有统计学意义。
在什么样的置信水平下我们可以拒绝dt=0的假设呢？为此，我们需要确定的值，使得dt的置信区间不跨越零值。可以将前面的计算反过来，寻找
的值，使得
。更换d和σd的值使得
<1.527。该值在
时最先出现（双侧检验时）。结果表明，零假设会在93.6％或更低的置信水平下被拒绝。
文献注释
早期的分类系统被用于组织各种对象集合，从生物体到无生命体。这样的例子比比皆是，从亚里士多德的物种编目，到杜威十进制。以及国家图书馆的书籍分类系统。这样的任务通常需要相当多的人力，以识别要分类的对象的属性，并将它们组织成易于区分的类别。
随着统计学和计算能力的发展，自动分类已成为深入研究的主题。经典统计中的分类研究有时称为判别分析（discriminant analysis），其目标是基于对应的特征来预测对象的组成员关系。一种著名的经典方法是Fisher的线性判别分析［142］，该方法旨在找到数据的线性投影，从而在不同类别的对象之间产生最佳划分。
许多模式识别问题也需要区分不同类别的对象。例如语音识别、手写字符识别和图像分类等。对模式识别分类技术的应用感兴趣的读者可以参考Jain等［150］和Kulkarni等［157］综述文章，或Bishop［125］、Duda等［137］和Fukunaga［143］的经典模式识别书籍。分类问题也是神经网络、统计学习和机器学习的主要研究课题。在Bishop［126］、Cherkassky和Mulier［132］、Hastie等［148］、Michie等［162］以及Murphy［167］和Mitchell［165］的书中有关于统计学和机器学习分类问题的深入讨论。最近几年也发布了许多公开的分类软件包，可以嵌入Java（Weka［147］)和Python（scikit-learn［174］)等编程语言中。
决策树归纳法的概述可以在Buntine［129］、Moret［166］、Murthy［168］和Safavian等［179］综述文章中找到。一些著名的决策树算法的示例包括CART［127］、ID3［175］、C4.5［177］和CHAID［153］。ID3和C4.5都使用熵测量作为它们的划分函数。Quinlan［177］对C4.5决策树算法进行了深入讨论。CART算法由Breiman等人［127］实现并使用基尼指数作为其划分函数。CHAID［153］使用统计χ2检验来确定决策树生长过程中的最佳划分。
本章介绍的决策树算法假设每个内部结点的划分条件只包含一个属性。倾斜决策树可以使用多个属性，在单个结点中形成属性测试条件［149,187］。Breiman等［127］在其CART实现中提供了一个使用属性线性组合的选项。Heath等［149］、Murthy等［169］、Cantú-Paz和Kamath［130］，以及Utgoff和Brodley［187］提出了生成倾斜决策树的其他方法。尽管倾斜决策树有助于提高模型的表达能力，但同时也让决策树归纳的计算过程具有了一定的挑战性。在不使用倾斜决策树的情况下提高决策树表达能力的另一种方法是构造归纳（constructive induction）［161］。该方法通过从原始数据创建复合特征来简化学习复杂划分函数的任务。
除了自顶而下的方法，其他生成决策树的策略还包括Landeweerd等［159］、Pattipati和Alexandridis［173］的自顶而上方法，以及Kim和Landgrebe［154］的双向方法。Schuermann和Doster［181］以及Wang和Suen［193］提出使用软划分标准（soft splitting criterion）来解决数据碎片问题。在该方法中，每个实例以不同的概率指派到决策树的不同分支。
模型过拟合是必须解决的重要问题，以确保决策树分类器在先前未标记的数据实例上具有同样良好的性能。许多作者已经研究过模型过拟合问题，包括Breiman等［127］、Schaffer［180］、Mingers［164］、Jensen和Cohen［151］。虽然噪声的存在通常被认为是过拟合的主要原因之一［164,170］，但Jensen和Cohen［151］认为过拟合是由于无法补偿多重比较问题而出现的现象。
Bishop［126］和Hastie等［148］对模型过拟合进行了很好的讨论，将其与著名的理论分析框架联系起来，称为偏置方差分解［146］。在该框架中，学习算法的预测被认为是训练集的函数，随着训练集的改变而变化。然后根据其偏置（使用不同训练集获得的平均预测的误差）、方差（使用不同训练集获得的预测的差异）和噪声（问题中固有的不可简化误差）来描述模型的泛化错误率。欠拟合模型被认为具有高偏置但低方差，而过拟合模型被认为具有低偏置但高方差。尽管偏置方差分解最初是针对回归问题提出的（其中目标属性是连续变量），但Domingos［136］已经提出了适用于分类的统一分析方法。第4章介绍集成学习方法时，将更详细地讨论偏置方差分解。
为了提供用于解释学习算法的泛化性能的理论框架，已经提出了各种学习原则，例如可能近似正确（PAC）学习框架［188］。在统计学领域，已经提出了许多在模型的拟合程度和复杂度之间进行权衡的性能估计方法。178其中最值得注意的是Akaike的信息准则［120］和贝叶斯信息准则［182］。它们都对模型的训练错误率使用校正项，以此降低复杂模型的评分。另一种广泛用于测量一般模型复杂性的方法是VC（Vapnik-Chervonenkis）维度［190］。对于任何可能的点分布，某类函数C的VC维度定义为可以被属于C的函数破坏的最大点数（每个点可以与其余点区分开）。VC维度奠定了结构风险最小化原则的基础［189］，该原理广泛用于许多学习算法，例如将在第4章中详细讨论的支持向量机。
奥卡姆的剃刀原则通常被认为是奥卡姆的哲学家威廉提出的。Domingos［135］告诫不要将奥卡姆剃刀误解为比较具有相似训练错误率，而不是泛化错误率的模型。Breslow和Aha［128］以及Esposito等［141］给出了关于避免过拟合的决策树修剪方法的综述。一些典型的修剪方法包括减低误差的剪枝［176］、悲观误差修剪［176］、最小误差修剪［171］、临界值修剪［163］、代价复杂度修剪［127］和基于误差的修剪［177］。Quinlan和Rivest提出使用最小描述长度原则对决策树进行剪枝［178］。
本章中关于交叉验证误差估计重要性的讨论来自第7章中提到的Hastie等［148］。其也是理解“交叉验证的正确和错误方法”的极好方法，类似于本章3.8节中关于陷阱的讨论。Krstajic等［156］提供了关于使用交叉验证进行模型选择和评估的一些常见陷阱的综合讨论。
最初的用于模型评估的交叉验证方法由Allen［121］、Stone［184］和Geisser［145］各自独立提出。尽管交叉验证可用于模型选择［194］，但其用于模型选择的方法与用于模型评估时的方法完全不同，正如Stone［184］所强调的那样。多年来，两种用法之间的区别经常被忽略，导致了错误的发现。使用交叉验证时常见的错误之一是使用整个数据集（例如，超参数调整或特征选择）179而不是在每个交叉验证运行的训练子类“内”执行预处理操作。Ambroise等用许多基因表达研究作为例子，提供了在交叉验证之外进行特征选择时出现的选择偏置的广泛讨论［124］。Allison等［122］也提供了评估微阵列数据模型的可用指导。
Dudoit和van der Laan［138］详细描述了用于超参数调整的交叉验证协议的使用。这种方法称为“网格搜索交叉验证”。正如本章3.7节所讨论的，对超参数选择和模型评估使用交叉验证的正确方法被Varma和Simon广泛讨论［191］。这种组合方法在现有文献中被称为“嵌套交叉验证”或“双重交叉验证”。近期，Tibshirani和Tibshirani［185］提出了一种新的超参数选择和模型评估方法。Tsamardinos等［186］将这种方法与嵌套交叉验证进行了比较。他们的实验发现，平均而言，这两种方法都能提供模型性能的保守估计，而Tibshirani和Tibshirani方法的计算效率更高。
Kohavi［155］进行了广泛的实证研究，以比较使用不同估计方法（如随机子采样和k重交叉验证）获得的性能指标。他们的结果表明，最佳估计方法是10重折叠分层的交叉验证。
模型评估的另一种方法是重抽样法，由Efron于1979年提出［139］。在该方法中，训练实例在被复制过的标签集中进行采样，即先前被选择为训练集的一部分实例同样可能再次被选择。如果原始数据具有N个实例，则可以看出大小为N的重抽样样本包含原始数据中大约平均为63.2％的实例。未包含在自助程序示例中的实例将成为测试集的一部分。用于获得训练集和测试集的重抽样程序重复b次，导致测试集在第i次运行时具有不同的错误率err（i)。为了获得整体错误率errboot，.632重抽样（.632 bootstrap）方法将err（i)与从包含所有标记示例的训练集获得的错误率errs结合起来，如下所示：
Efron和Tibshirani等［140］提供了交叉验证和被称为632+规则的重抽样方法之间的理论和实证比较。
虽然上面提出的.632重抽样法提供了对其估计中的低方差的泛化性能的稳健估计，但是在某些条件下它可能对高度复杂的模型产生误导性的结果，如Kohavi［155］所指出的例子。这是因为整体错误率并非真正的样本外错误估计，因为它取决于训练错误率errs，如果存在过拟合，则该值可能非常小。
当前的技术（如C4.5）要求整个训练数据集都能装入内存。为开发决策树归纳算法的并行和可伸缩的版本，已经做了大量的工作。已提出的算法包括Mehta等［160］的SLIQ、Shafei等［183］的SPRINT、Wang和Zaniolo［192］的CMP、Alsabti等［123］的CLOUDS、Gehrke等［144］的RainForest和Joshi等［152］的ScalParC。关于数据分类和其他数据挖掘任务的并行算法综述在文献［158］中给出。最近，在计算统一设备架构（CUDA）［131,134］和MapReduce［133,172］平台上实现大规模分类器已有广泛的研究。
参考文献
习题
1.为4个布尔属性A、B、C和D的奇偶函数画一棵完全决策树。可以简化该决策树吗？
2.考虑表3.5中二分类问题的训练样本。
（b) 计算属性顾客ID的基尼指数值。
（c) 计算属性性别的基尼指数值。
（d) 计算使用多路划分属性车型的基尼指数值。
（e) 计算使用多路划分属性衬衣尺码的基尼指数值。
（f) 下面哪个属性更好，性别、车型还是衬衣尺码？
（g) 解释为什么属性顾客ID的基尼指数值最低，但却不能作为属性测试条件。
3.考虑表3.6中的二分类问题的训练样本集。
（a) 整个训练样本集关于类属性的熵是多少？
（b) 关于这些训练样本，a1和a2的信息增益是多少？
（c) 对于连续属性a3，计算所有可能的划分的信息增益。
（d) 根据信息增益，哪个是最佳划分（在a1、a2和a3中）？
（e) 根据分类错误率，哪个是最佳划分（在a1和a2中）？
（f) 根据基尼指数，哪个是最佳划分（在a1和a2中）？
4.证明：将结点划分为更小的后继结点之后，结点熵不会增加。
5.考虑如下二分类问题的数据集。
（a) 计算按照属性A和B划分时的信息增益。决策树归纳算法将会选择哪个属性？
（b) 计算按照属性A和B划分时的基尼指数。决策树归纳算法将会选择哪个属性？
（c) 从图3.11可以看出熵和基尼指数在区间［0，0.5］都是单调递增的，而在区间［0.5，1］都是单调递减的。有没有可能信息增益和基尼指数增益支持不同的属性？解释你的理由。
6.考虑使用某些属性测试条件将父结点P拆分为两个子结点C1和C2。每个结点上标记的训练实例的组成总结在下表中。
（a) 计算父结点P的基尼指数和错误分类的错误率。
（b) 计算子结点的加权基尼指数。如果将基尼指数用作不纯性测量，你会考虑这个属性测试条件吗？
（c) 计算子结点的加权错误分类率。如果使用错误分类率作为不纯性测量，你会考虑这个属性测试条件吗？
7.考虑如下训练样本集。
（a) 用本章所介绍的贪心算法计算两层的决策树。使用分类错误率作为划分标准。决策树的总错误率是多少？
（b) 使用X作为第一个划分属性，两个后继结点分别在剩余的属性中选择最佳的划分属性，重复步骤（a)。所构造的决策树的错误率是多少？
（c) 比较（a)和（b)的结果。评述在划分属性选择上启发式贪心法的作用。
8.下表汇总了具有3个属性A、B、C，以及两个类标号+、-的数据集。建立一棵两层决策树。
（a) 根据分类错误率，哪个属性应当选作第一个划分属性？对每个属性给出列联表和分类错误率的增益。
（b) 对根结点的两个子结点重复以上问题。
（c) 最终的决策树错误分类的实例数是多少？
（d) 使用C作为划分属性，重复（a)（b)和（c)。
（e) 使用（c)和（d)中的结果分析决策树归纳算法的贪心本质。188
9.考虑图3.36中的决策树。
（a) 使用乐观方法计算决策树的泛化错误率。
（b) 使用悲观方法计算决策树的泛化错误率。（为了简单起见，使用在每个叶结点增加因子0.5的方法。）
（c) 使用提供的验证集计算决策树的泛化错误率。这种方法叫作降低误差剪枝（reduced error pruning)。
10.考虑图3.37中的决策树。假设产生决策树的数据集包含16个二元属性和3个类C1、C2和C3。
根据最小描述长度原则计算每棵决策树的总描述长度。
- 树的整体描述长度由下式给出：Cost（tree,data)=Cost（tree)+Cost（datatree)
- 树的每个内部结点用划分属性的ID进行编码。如果有m个属性，为每个属性编码的代价是log2m个二进位。
- 每个叶结点使用与之相关联的类的ID编码。如果有k个类，为每个类编码的代价是log2k个二进位。
- Cost（tree)是对决策树的所有结点编码的开销。为了简化计算，可以假设决策树的总开销是对每个内部结点和叶结点编码的开销总和。
- Cost（datatree)是对决策树在训练集上的分类错误编码的开销。每个错误用log2n个二进位编码，其中n是训练实例的总数。
根据MDL原则，哪棵决策树更好？
11.该练习受到文献［155］的启发，突出了留一法模型评估过程的一个已知局限性。考虑一个包含50个正实例和50个负实例的数据集，其中属性是完全随机的，不包含有关类别标签的信息。因此，在该数据上学习的任何分类模型的泛化错误率预计均为0.5。考虑一个分类器，它将训练实例的多数类别标签（通过使用正标签作为默认类）分配给所有测试实例，不管其属性值如何。这种方法叫作多数诱导分类器。使用以下方法确定此分类器的错误率。
（a) 留一法。
（b) 双重分层交叉验证法，其中每个子类的类别标签比例与整体数据保持相同。
（c) 从上面的结果来看，哪种方法能够更可靠地评估分类器的泛化错误率？190
12.考虑一个包含100个数据实例的标记数据集，该数据实例被随机分为A和B两组，每组包含50个实例。我们使用A作为训练集来学习两个决策树，T10具有10个叶结点，T100具有100个叶结点。数据集A和B的两个决策树的准确率如表3.7所示。
（a) 根据表3.7中显示的准确率，你认为哪个分类模型在未知实例上具有更好的性能？
（b) 现在，在整个数据集（A+B)上测试了T10和T100，发现T10在数据集（A+B)上的分类准确率为0.85，而T100在数据集（A+B)上的分类准确率为0.87。根据这些新信息和表3.7中的观察结果，你最终会选择哪个分类模型进行分类？
13.考虑如下测试分类法A是否优于另一个分类法B的方法。设N是数据集的大小，pA是分类法A的准确率，pB是分类法B的准确率，而是两种分类法的平均准确率。为了测试分类法A是否显著优于B，使用如下Z统计量：
如果Z>1.96，则认为分类法A优于分类法B。
表3.8在不同的数据集上比较3个不同分类法的准确率：决策树分类法、朴素贝叶斯分类法和支持向量机。（后两种分类法将在第4章中进行介绍。）
用下面3×3的表格来汇总表3.8中给定的分类法在数据上的分类性能：
表格中每个单元的内容包含比较行与列的两个分类器时的赢、输和平局的数目。
14.设X是一个均值为Np、方差为Np（1-p)的二元随机变量。证明比率X/N也服从均值为p、方差为p（1-p)/N的二项式分布。