带你了解数据挖掘入门（原书第 2 版）第 3 期：分类：基本概念和技术

点击查看第一章
点击查看第二章

第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 undertting）。若学习的决策树过于简单，则会导致欠拟合，以致无法充分表示属性与类别标签之间的真实关系。随着将树的大小从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%的数据用