下载掌阅APP，畅读海量书库
立即打开
决策树是一种基于树结构的机器学习模型，常用于回归或分类等预测性任务。决策树的基本思想是直接模拟人类进行级联选择或决策的过程，它按照属性的某个优先级依次对数据的全部属性进行判别，从而得到输入数据所对应的预测输出。决策树模型的求解思路与线性模型有很大差异：决策树模型按照属性的优先级依次对数据的全部属性进行判别，从而完成对样本数据的回归或分类预测任务；线性模型则是将样本数据的所有特征通过赋予权重参数再相加得到一个综合数值，重点在于得到样本数据各属性值的权重参数。因此，决策树模型比线性模型更具可解释性，更易于理解。决策树学习是指从训练样本数据中自动构造出决策树模型的机器学习技术。目前，决策树模型及其机器学习技术已被广泛应用于医学、制造产业、天文学、生物学以及商业等诸多领域。本节首先介绍决策树模型的基本结构，然后分析决策树模型的内部结点选择的判别标准，最后给出决策树模型的若干训练构造算法。
决策树模型将思维过程抽象为一系列对已知数据属性的判别或决策过程，使用树结构表示判别的逻辑关系和一系列的判别过程，并通过叶结点表示判别或决策结果，计算过程条理清晰，逻辑结构一目了然。例如，学生小明在周五晚上考虑他在周末的安排，需要根据诸如有无作业、有无聚会和天气是否适宜等因素做出安排或决策，可用图3-7所示的决策树模型表示小明的决策过程。
如图3-7所示，决策树是一个外向树模型，包含一个根结点、若干内部结点和叶结点。其中叶结点表示决策的结果，内部结点表示对样本某一属性的判别。这些判别直接或间接地影响着决策的最终结果。从根结点到某一叶结点的路径称为 测试序列 ，例如，图3-8所示的一条测试序列表示这个周末小明没有作业也没有聚会，并且天气适宜，这种情况所对应的决策结果就是运动。决策树使用内部结点表示对确定属性的判别，每个结点可以看作一个if-then规则判别。例如，对于“有无作业”这一属性，如果判别结果为“有”，则小明周末就去学习，否则就进一步判断“有无聚会”。显然，决策树的测试序列可以看作是一系列if-then规则判别的组合，因此决策树是一类基于规则的模型。如果将决策树的每个测试序列分别看作一条规则，那么对于给定的机器学习任务和用于处理该任务的决策树模型，每个决策结论将有且仅有一条相应的规则与之对应。
图3- 用于周末安排的决策树模型
图3-8 测试序列示意图
【例题3.4】 现有12枚外观相同的硬币，其中有1枚是假的且比真币重。如何使用一个无砝码天平把假币找出来，要求不超过三次称重。
【解】 如图3-9所示，把硬币等分成三份，用天平分别对其中任意两份进行称重，确定假币在哪一份。之后再对假币所在的那一份进行等分，并通过称重确定假币在哪一份，直至找到假币。由图3-9可知，从根到叶就是一种基于分组比较的求解过程，该树有12片叶子，故最多有12种可能的解。由于树高为3，故最多只需要3次判别就能得到结论。
图3-9 用于找假币的决策树模型
决策树模型的构造可以通过对训练样本数据的学习来实现。事实上，决策树模型的构造是一个通过递归方式对训练样本集不断进行子集划分的过程。例如，对于上述小明周末安排的问题，表3-4列出所有8种可能状态。在对根结点进行判别之后，原数据集便按“有无作业”被划分为了两个子数据集，即表3-4中左边4种情况和右边4种情况。
表3-4 周末安排问题的整个数据集
不同判别策略会产生不同的属性划分标准，从而在决策树模型中产生不同的内部结点和分支。因此，构造决策树模型的关键在于选择适当内部结点所对应的属性，即通过选择适当的内部结点的判别属性来合理地构造分支。每个分支结点根据判别属性将其对应的数据集划分为相应的子数据集，使得每个子数据集中的样本尽可能属于同一类别。当结点上的数据都是属于同一类别或者没有属性可以再用于对数据集进行划分时，则停止划分并获得划分结果。
综上所述，可得决策树构造的基本思路如下：首先，根据某种分类规则得到最优的划分特征，计算最优特征子函数，并创建特征的划分结点，按照划分结点将数据集划分为若干部分子数据集；然后，在子数据集上重复使用判别规则，构造出新的结点，作为树的新分支。在每一次生成子数据集之前，都要检验递归是否符合递归终止条件，即数据均属于同一类别或者再也没有用于数据划分的属性。若满足递归终止条件，则结束构造过程，否则将新结点所包含数据集和类别标签作为输入，重复递归执行。
决策树构造完成后，对于给定的样本输入，可通过决策树提供的一系列判别条件找到最终的叶结点所对应的类别标签，得到判别所需的判别结果。
如前所述，构造决策树的关键在于合理选择其内部结点所对应的样本属性，使得结点所对应样本子集中的样本尽可能多地属于同一类别，即具有尽可能高的纯度。如果结点的样本子集属于同一类型，则可将该结点置为该类别的叶结点，不用对其做进一步判别。因此，内部结点所对应样本子集的纯度越高，决策树模型对样本数据的分类能力也就越强。一般来说，决策树判别标准需要满足以下两点：
第一，如果结点对应数据子集中的样本基本属于同一个类别，则不用再对结点的数据子集做进一步划分，否则就要对该结点的数据子集做进一步划分，生成新的判别标准；
第二，如果新判别标准能够基本上把结点上不同类别的数据分离开，使得每个子结点都是类别比较单一的数据，那么该判别标准就是一个好规则，否则需重新选取判别标准。
由以上分析可得决策树判别属性的选择标准，即对于一个给定决策树分支结点，选择该结点所对应子集纯度最高的属性作为判别标准最为合理。
为合理量化决策树的判别属性选择标准，可以使用信息论中熵的有关知识来对样本集合的纯度进行定量表示和分析。 信息熵 （简称为熵）是信息论中定量描述随机变量不确定度的一类度量指标，主要用于衡量数据取值的无序程度，熵值越大则表明数据取值越杂乱无序。
假设 ξ 为具有 n 个可能取值{ s 1 ， s 2 ，…， s n }的离散型随机变量，概率分布为 P （ ξ = s i ）= p i ，则其信息熵定义为
显然，如果 H （ ξ ）值越大，则随机变量 ξ 的不确定性就越大。
对于任意给定的两个离散随机变量 ξ ， η ，其联合概率分布为
P （ ξ = s i ， η = t i ）= p ij ， i =1，2，…， n ； j =1，2，…， m
则 η 关于 ξ 的条件熵 H （ η | ξ ）定量表示在已知随机变量 ξ 取值的条件下随机变量 η 取值的不确定性，计算公式为随机变量 η 基于条件概率分布的熵对随机变量 ξ 的数学期望，即有
其中， p i = P （ ξ = s i ）， i =1，2，…， n 。
对于任意给定的训练样本集合 D ，可将集合 D 看成是一个关于样本标签取值状态的随机变量，由此可根据熵的本质内涵来定义一个量化指标 H （ D ）进而度量 D 中样本类型的纯度，通常称 H （ D ）为 经验熵 。 H （ D ）值越大，则表明 D 中所包含样本标签取值越杂乱； H （ D ）值越小，则表明 D 中所包含样本标签取值越纯净。 H （ D ）的具体计算公式如下
其中， n 表示样本标签值的取值状态数； C k 表示训练样本集 D 中所有标注值为第 k 个取值的训练样本组成的集合，| D |和| C k |分别表示集合 D 和 C k 的基数。
对于训练样本集合 D 上的任意属性 A ，可在经验熵 H （ D ）的基础上进一步定义一个量化指标 H （ D | A ）来度量集合 D 中的样本在以属性 A 为标准划分后的纯度，通常称 H （ D | A ）为集合 D 关于属性 A 的 经验条件熵 。 H （ D | A ）的计算公式如下
其中， m 表示属性 A 的取值状态数； D i 表示集合 D 在以属性 A 为标准划分后所生成的子集，即为 D 中所有属性 A 取第 i 个状态的样本组成的集合。
由经验熵 H （ D | A ）的定义可知，其值越小则样本集合 D 的纯度越高。可在经验熵的基础上进一步计算每个属性作为划分指标后对数据集合经验熵变化的影响，即 信息增益 。信息增益度量的是已知随机变量 ξ 的信息使得随机变量 η 的信息不确定性减少的程度。
对于任意给定的训练样本数据集合 D 及其上的某个属性 A ，属性 A 关于集合 D 的信息增益 G （ D ， A ）定义为经验熵 H （ D ）与条件经验熵 H （ D | A ）之差，即有
显然，对于属性 A 关于集合 D 的信息增益 G （ D ， A ），如果其值越大则表示使用属性 A 划分后的样本集合纯度越高，使得决策树模型具有更强的分类能力，故可将 G （ D ， A ）作为标准选择合适的判别属性，通过递归计算样本属性的信息增益以实现对决策树的构造。
【例题3.5】 表3-5所示的数据集表示豌豆种子在不同环境下能否发芽的情况。豌豆种子自身有形状、大小和种皮颜色等特征，外部影响环境有土壤、水分和日照等特征。试通过表3-5所示数据集构造决策树并根据最后一行测试数据预测该豌豆能否发芽。
表3-5 豌豆数据集
（续）
【解】 首先，计算训练样本数据集的经验熵。每个训练样本的标注有两个可能的取值，分别是能发芽和不能发芽，其中是能发芽占比为5/9，不能发芽占比为4/9，故有
然后，分别计算各属性的信息增益。若以“形状”作为划分属性，则将训练样本集合 D 划分成 D （圆形）和 D （皱形）这两个子集，分别计算 D （圆形）和 D （皱形）的经验熵
由此可得形状属性的信息增益如下
同理可得其他属性的信息增益如下： G （ D ，颜色）=0.09， G （ D ，大小）=0.09， G （ D ，土壤）=0.09， G （ D ，水分）=0.23， G （ D ，日照）=0.09。
显然，水分属性的信息增益最大，故选择“水分”作为第一个划分属性，得到图3-10所示的初始决策树，其中 D （多）={1，3，4，8}表示水分为多的训练样本集， D （少）={2，5，6，7，9}表示水分为少的训练样本集。同理继续对 D （多）和 D （少）进行划分，可得图3-11所示的完整决策树。
图3-10 初始决策树
图3-11 完整决策树
使用所得决策树对测试1中的样本进行预测。首先，其“水分”为“多”，故进入左子树，接着其“日照”在“12h以下”进入左子树，最后其“大小”为“饱满”得到它的分类为“是”，故根据该决策树的预测结果，判断测试1中的样本为能够发芽。
使用信息增益指标作为划分属性选择标准时，选择结果通常会偏向取值状态数目较多的属性。为解决这个问题，最简单的思路是对信息增益进行归一化， 信息增益率 便可看作对信息增益进行归一化后的一个度量标准。信息增益率在信息增益基础上引入一个校正因子，消除属性取值数目的变化对计算结果的干扰。具体地说，对于任意给定的训练样本数据集合 D 及其上的某个属性 A ，属性 A 关于集合 D 的信息增益率 G r （ D ， A ）定义如下
其中 Q （ A ）为校正因子，由下式计算
显然，属性 A 的取值状态数 m 值越大，则 Q （ A ）值也越大，由此可以减少信息增益的不良偏好对决策树模型构造所带来的影响，使得所建决策树拥有更强的泛化能力。
对于决策树模型，还可采用 基尼指数 （Gini Index）作为划分标准来选择最优属性。与熵的概念类似，基尼指数可用来度量数据集的纯度。对于任意给定的一个 m 分类问题，假设样本点属于第 k 类的概率为 p k ，则关于这个概率分布 p 的基尼指数可以定义为
即有
相应地，对于任意给定的样本集合 D ，可将其基尼指数定义为
其中， C k 是 D 中属于第 k 类的样本子集； m 是类别数。
样本集合 D 的基尼指数表示在 D 中随机选中一个样本被错误分类的概率。显然，Gini（ D ）的值越小，数据集 D 中样本的纯度越高，或者说 D 中样本种类的一致性越高。
若样本集合 D 根据属性 A 是否取某一可能值 a 而被分割为 D 1 和 D 2 两部分，即
则在属性 A 为划分属性的条件下，集合 D 的基尼指数可以定义为
例如，可以根据表3-5给出的豌豆数据集计算某些特征的基尼指数，将“大小”作为划分属性把集合划分为 D （饱满）和 D （皱缩）这两个子集，分别计算这两个子集的基尼指数
由此可得在“大小”这一属性条件下 D 的基尼指数为
同理可得：Gini（ D ，形状）=0.489，Gini（ D ，颜色）=0.433，Gini（ D ，土壤）=0.433，Gini（ D ，水分）=0.344，Gini（ D ，日照）=0.433。其中水分属性的基尼指数最小，故将水分作为第一个划分属性，将集合 D 划分为 D （多）和 D （少），分别对样本集合 D （多）和 D （少）递归调用以上步骤，最后可得如图3-12所示的完整决策树。
图3-12 依据基尼指数构造的决策树模型
本节介绍基于上述判别标准的三种经典的决策树生成算法，即基于信息增益的ID3算法、基于信息增益率的C4.5算法以及基于基尼指数的CART算法。
ID3算法以信息增益最大的属性为分类特征，基于贪心策略自顶向下地搜索遍历决策树空间，通过递归方式构造决策树。具体地说：从根结点开始，计算当前结点所有特征的信息增益，选择信息增益最大的特征作为该结点的分类特征，并针对该分类特征的每个不同取值分别建立相应子结点；再分别对所有子结点递归地调用以上方法，构造决策树，直到所有特征的信息增益、很小或没有特征可以选择为止，由此得到一个完整的决策树模型。
【例题3.6】 表3-6是一个由16个样本组成的感冒诊断训练数据集 D 。每个样本由4个特征组成，即体温、流鼻涕、肌肉疼、头疼。其中体温特征有3个可能取值：正常、较高、非常高；流鼻涕、肌肉疼、头疼分别有两个可能取值：是、否；样本的标注值为是否感冒。试用ID3算法通过训练数据集 D 建立一个用于判断是否感冒的决策树。
表3-6 感冒诊断数据表
（续）
【解】 首先，计算训练数据集 D 的经验熵为
若以“体温”作为划分属性，则可将数据集 D 划分为 D （正常）、 D （较高）、 D （非常高）这三个子集合，分别计算它们的经验熵，得到：
由此可得“体温”属性的信息增益为 G （ D ，体温）=0.0385。同理可得其他属性的信息增益：
其中， G （ D ，流鼻涕）的值最大，故取“流鼻涕”作为第一个划分属性。
将集合 D 划分为
对集合 D 1 计算其余三个属性的信息增益，得到：
其中， G （ D 1 ，体温）的值最大，故选择“体温”作为对集合 D 1 的划分属性。同理，对集合 D 2 计算其余三个属性的信息增益，得到：
由于 G （ D 2 ，体温）= G （ D 2 ，肌肉疼），故可在这两者中任选其一作为该结点的划分属性。此处选择“肌肉疼”作为集合 D 2 的划分属性。
对于已划分的子数据集，若其不满足算法终止条件，则递归调用上述步骤进一步对子集进行划分，直至满足算法终止条件，得到图3-13中所示的完整决策树。
图3-13 由ID3算法构造的完整决策树
ID3算法所采用的信息增益度量倾向于选择具有较多属性值的属性作为划分属性，有时这些属性可能不会提供太多有价值的信息，并且ID3算法并不能处理连续值和缺失值。为此可对ID3算法进行改进，使用信息增益率代替信息增益作为决策树判别标准，由此产生C4.5算法。C4.5算法通常泛指基本C4.5生成算法、C4.5剪枝策略，以及拥有多重特性的C4.5规则等一整套算法。对于任意给定的训练样本集 D ，在 D 上运行C4.5算法可以通过学习得到一个从特征空间到输出空间的映射，进而可使用该映射去预测新实例的类别。
在使用基本的C4.5算法构造决策树时，信息增益率最大的属性即为当前结点的划分属性。随着递归计算的进行，被计算的属性的信息增益率会变得越来越小，到后期则选择相对比较大的信息增益率的属性作为划分属性。为避免过拟合现象，C4.5算法中引入了剪枝策略， 剪枝 就是从决策树上裁剪掉一些子树或者叶结点，并将其根结点或父结点作为新的叶结点，从而简化分类树模型。剪枝的目的是为了减少决策树学习中出现的过拟合现象，决策树剪枝策略有 预剪枝 和 后剪枝 两种。
预剪枝是指在决策树的生成过程中，对每个子集在划分前先进行估计，若当前结点的划分不能带来泛化性能的提升，则停止划分并将当前结点标记为叶结点。事实上，在决策树的生成过程中，虽然对有些分支的当前划分并不能提升泛化性能，甚至有可能导致泛化性能暂时下降，但有利于从整体上提升决策树的泛化性能。因此，通常难以保证预剪枝方法不会错误地阻止决策树的生长。后剪枝则先从训练样本集生成一棵完整决策树，然后自底向上或自顶而下考察分支结点，若将该结点对应子树替换为叶结点能提升模型泛化性能，则进行替换。这样可以保证剪枝操作不会降低决策树模型的泛化性能，因此通常采用后剪枝策略。
C4.5算法通常采用一种名为悲观错误剪枝（Pessimistic-Error Pruning，PEP）的算法来实现对决策树的剪枝优化。PEP算法是一种自顶而下的后剪枝方法，主要以剪枝前后的错误率为标准来判定是否进行子树的修剪。因此，该方法不需要单独的剪枝数据集。
PEP算法的基本思想是分别考察每个内部结点对应的子树所覆盖训练样本的误判率与剪去该子树后所得叶结点对应训练样本的误判率，然后通过比较二者间的大小关系确定是否进行剪枝操作。当剪枝后所获得叶结点的误判率小于所对应的子树误判率时，进行剪枝显然提升了决策树的泛化性能。然而，由于PEP算法直接通过训练样本集来对子树和叶结点进行评估，导致子树的误判率一定小于叶结点的误判率，从而得到在任何情况下都不需要剪枝的错误结论。为避免出现这种错误结论，PEP算法在计算误判率时添加了一个经验性惩罚因子。
具体地说，假设由训练样本数据集生成的决策树为 T ，对于 T 的任意一个叶结点 t ，与其对应的训练样本个数为 n （ t ），其中被错误分类的样本个数为 e （ t ）。由于训练数据既用于生成决策树又用于对决策树的剪枝，故基于此训练数据集的误判率 r （ t ）= e （ t ） /n （ t ）具有一定偏差，不能直接作为是否进行剪枝的判断标准。因此，PEP算法在计算误判率时添加了一个经验性惩罚因子1/2，将误判率计算公式修正为
不失一般性，设 T t 为树 T 的子树， i 为覆盖 T t 的叶结点， N i 为子树 T t 的叶结点数，则子树 T t 的分类误判率为
在定量分析中，为简单起见，直接使用作为分子的误判样本数代替误判率参与计算。对于叶结点 t ，有
对于子树 T t ，有
由此可得子树 T t 被叶结点 t 替换的条件是
其中， S e （ e′ （ T t ））表示标准误差，具体计算公式如下
如果式（3-32）成立，则子树 T t 应被修剪掉，并用相应的叶结点替代；否则，不进行剪枝。对所有非叶结点自顶而下依次计算测试，判断它们是否应被修剪掉。
例如，对于图3-14所示的决策树，将其中第 i 个结点记为 t i 。令 A 和 B 分别表示训练样本集中的两个不同类别。现用PEP算法对该决策树进行剪枝。首先，计算各分支结点的误差。例如， t 1 对应的训练数据集中包含55个 A 类样本、25个 B 类样本，则 e （ t 1 ）=25。表3-7中数据为决策树中各分支结点的PEP算法参数和算法结果。由计算结果可知 t 4 结点的子树应该被剪枝，由此可得如图3-15所示的剪枝后的优化决策树。
表3-7 参与PEP算法判别各项的取值表
图3-14 初始决策树
图3-15 PEP算法剪枝后的决策树
根据以上分析得到C4.5算法的基本步骤如下：
（1）确定阈值 ε ，并令 Γ 表示样本属性组成的集合；
（2）若数据集 D 中所有样本属于同一个类 C i ，则置Tree为单结点树，并将 C i 作为该结点的类，返回Tree。若 Γ =Ø，则置Tree为单结点树，并将 D 中样本数最大的类 C i 作为该结点的类，返回Tree；否则，分别计算集合 Γ 中所有属性对于训练数据集 D 的信息增益率，选择其中信息增益率最大的属性 A g 作为划分属性；
（3）如果划分属性 A g 的信息增益率小于阈值 ε ，则置Tree为单结点树，并将 D 中实例数最大的类 C i 作为该结点的类，返回Tree；否则，对 A g 的每个可能取值 a gi ，依照 A g = a gi 将 D 分割为若干非空样本子集 D i ，将 D i 中样本数最大的类别作为标记值，由此构造子结点并由该结点及其子结点构成树Tree，返回Tree；
（4）对结点 i ，以 D i 为训练集，以 Γ -{ A g }为特征集，递归地调用步骤（2）～步骤（3），得到子树Tree i ，返回Tree i ；
（5）对生成的决策树使用PEP算法进行剪枝，得到所求优化决策树模型。
【例题3.7】 某公司每年端午节都会组织公司员工进行龙舟比赛，举行龙舟比赛通常要考虑天气因素，若天气情况糟糕，则公司会取消比赛。现有2003～2016年端午节当天的数据（编号为1～14）及天气情况如表3-8所示，试根据该表中的数据集使用C4.5算法构造用于帮助公司判断是否会取消龙舟比赛的决策树。
表3-8 天气情况表
【解】 对于表3-8所示数据集 D ，令 A 和 C 分别表示其特征集合和输出空间，则有 A ={天气，温度，湿度，风速}， C ={进行，取消}。首先，计算训练样本集 D 的信息增益： D 中包含14个样本，其中属于类别“进行”的有9个，属于类别“取消”的有5个，其信息增益为
然后，计算特征集合 A 中的每个特征对数据集 D 的经验条件熵 H （ D | A ），得到：
根据以上结果可算得每个属性的信息增益值：
为计算信息增益率，还需计算各个属性的校正因子 Q （ A ）值。天气属性有3个取值（晴、雨、阴），其中5个样本取晴、5个样本取雨、4个样本取阴，故有：
温度属性有3个取值（炎热、适中、寒冷），其中4个样本取炎热、6个样本取适中、4个样本取寒冷，故有：
湿度属性有2个取值（高、正常），其中7个样本取正常、7个样本取高，故有：
风速属性有2个取值（强、弱），其中6个样本取强、8个样本取弱，故有：
根据以上结果算得信息增益率 G r （ D ， A ）的值如下：
由于 G r （ D ，天气）的取值最大，故将天气属性作为所求决策树的第一个决策结点，将样本集合 D 划分为 D （阴）、 D （晴）、 D （雨）这三个子集合，其中 D （阴）={3，7，12，13}， D （晴）={1，2，8，9，11}， D （雨）={4，5，6，10，14}。由于 D （阴）中所有样本都属于同一类，故不再对其进行划分，并将其标记为进行活动。通过递归调用算法分别对样本集合 D （晴）和 D （雨）做进一步划分，直到满足算法结束条件。由以上过程可得到图3-16所示的决策树模型，其中 Y 表示进行活动的天数， N 表示取消活动的天数。对该决策树所有分支点计算PEP算法参数，得到表3-9所示的计算结果，由表中数据可知当前决策树已是所求最优决策树，不需要剪枝。
图3-16 C4.5生成算法构造的决策树
表3-9 PEP算法参数和计算结果
上述ID3算法和C4.5算法构造的决策树模型都属于分类树，即通过数据对象的特征来预测该对象所属的离散类别。CART算法则既可构造用于分类的分类决策树，也可构造用于回归分析的回归决策树。与C4.5算法和ID3算法不同的是，CART算法依据特征取值对训练样本集进行二元划分，使得由CART算法构造的决策树必是一棵二叉树。
例如，对于年龄特征的三个取值{青年，中年，老年}，相应结点通常应取3个分支，由于CART算法要求决策树为二叉树，使得内部结点的特征取值为“是”或“否”，故需对该年龄特征的每个取值进行人为二元划分，得到三对不同取值形式，即有：
年龄=青年，年龄≠青年；年龄=中年，年龄≠中年；年龄=老年，年龄≠老年
使用CART算法构造分类决策树需选择合适的特征作为结点属性，并选择合适的二元划分形式作为结点分支的判别条件。如前所述，基尼指数值越小就说明二分之后子数据集样本种类的纯度越高，即选择该属性和该二元划分形式分别作为结点属性和判别条件的效果越好。因此，CART算法主要使用基尼指数值作为划分特征选择的标准。
具体地说，如果需要使用属性 A 将训练样本集划分为两个部分，则需要确定选择何种二元划分方式来构造分支。假设属性 A 的可能取值为{ a 1 ， a 2 ，…， a n }并选择其中第 i 个特征值 a i 作为划分标准，即该分支所对应的判别条件分别为 A = a i ， A ≠ a i ，则将划分得到的两个子数据集分别记为 D 1 、 D 2 ，并算出该划分所对应的基尼指数
根据以上方法分别算出特征 A 的所有二元划分所对应的基尼指数，并取其中最小基尼指数所对应的二元划分作为候选分支结点判别条件。计算所有特征的候选分支结点判别条件，取其中基尼指数最小的判别条件作为该结点的分支判别条件，完成对该结点的分支。
CART算法主要通过最小化平方误差的优化计算方式构造回归决策树。对于输入空间中给定的某个划分，可通过构造回归树将该划分的所有划分单元分别映像到对应输出值上。对于给定回归任务和训练样本集 D ={（ X 1 ， y 1 ），（ X 2 ， y 2 ），…，（ X n ， y n ）}，若将该回归任务的输入空间划分为 k 个单元 L 1 ， L 2 ，…， L k ，则回归决策树 f 在第 s 个单元 L s 上的整体平方误差为
显然，当决策回归树 f 对划分 D s 的输出为该划分中所有输入样本所对应真实标记的均值时， R s 最小。即当
时， R s 最小。记
由于CART算法要求生成一棵二叉树，故采用递归二元划分方式通过对输入空间的划分构造回归树。具体地说，对于训练样本集 D ={ X 1 ， X 2 ，…， X n }，CART算法递归寻找单个特征 x j 作为切分变量并确定 x j 的某个取值 b 作为切分点，将训练子集划分为两个区域
决策树 f 在这两个区域上的整体误差平方和为
选择不同的切分变量和切分点对上述整体误差平方和进行优化，其值达到最小时所对应的切分变量和切分点即为回归决策树当前结点属性和对应的分支判别条件。因此，回归决策树当前结点的属性 X j 和对应判别阈值 b 可通过求解如下优化问题得到
递归上述过程直至满足算法终止条件，便可生成一棵完整的回归决策树。此类通过最小化误差平方和而构造的回归树通常也称为 最小二乘回归树 。
【例题3.8】 使用表3-10所示训练样本集构造一棵含三个叶结点的最小二乘回归树 f 。
表3-10 训练样本集
【解】 记编号为 i 的样本为 X i ，由于样本只有一个特征 x ，故 x 为最优切分变量。考虑9个切分点{1.5，2.5，3.5，4.5，5.5，6.5，7.5，8.5，9.5}，选用误差平方和作为目标函数 F （ θ ），则有
其中
将上述9个切分点分别代入目标函数，例如，取 θ =1.5时，有
L
1
={
X
1
}，
L
2
={
X
2
，
X
3
，
X
4
，
X
5
，
X
6
，
X
7
，
X
8
，
X
9
，
X
10
}；
，
选取所有不同切分点
θ
可得
的取值如表3-11所示。
表3-11
取值表
将
，
代入目标函数
F
（
θ
）可得到目标函数的取值如表3-12所示。
表3-12 目标函数 F （ θ ）取值表
可见取 θ =6.5时， F （ θ ）最小。故切分变量 x 的第一个切分点为 θ =6.5。使用选定的切分变量和切分点划分区域，并决定输出值。两个区域分别是
当前情况下决策树的输出值为
继续对得到的样本子集进行划分，对
L
1
继续进行划分，选取不同的切分点
θ
可得到
的取值如表3-13所示。计算得
F
（
θ
）的取值如表3-14所示。
表3-13
取值表
表3-14 F （ θ ）取值表
由表3-14中数据可知，当 θ =3.5时， F （ θ ）取值最小，故得切分点为 θ =3.5。由此可得如下所求回归决策树：当 x ≤3.5时， f （ X ）=5.72；当3.5< x ≤6.5时， f （ X ）=6.75；当 x >6.5时， f （ X ）=8.91。
CART算法主要通过代价复杂度剪枝（Cost-Complexity Pruning，CCP）方法防止所建决策树模型产生过拟合现象。CCP剪枝方法首先通过某种策略从待剪枝决策树 T 0 的底端开始不断剪枝，一直剪到 T 0 的根结点，由此形成一个子树序列{ T 0 ， T 1 ，…， T n }，然后在独立验证数据集上对子树序列进行测试，从中选择最优子树。
为找出决策树中适合剪枝的子树，CCP方法采用公式 R α （ T ）= R （ T ）+ α | T |度量子树的整体泛化性能。其中， T 为任意子树； R （ T ）为子树 T 对训练样本集的预测误差（如误差平方和）；| T |为子树叶结点个数； α ≥0为参数，用于权衡子树 T 对训练样本集拟合程度与模型复杂度之间的制约关系； R α （ T ）为参数为 α 时子树 T 的整体泛化性能值， R α （ T ）的取值越小，则所对应子树 T 的泛化性能就越好。
显然，对给定的 α 值，一定存在使整体泛化性能值 R α （ T ）最小的子树，将其记为 T α 。易知最优子树 T α 对于给定的 α 值是唯一的。当 α 较大时， T α 的规模偏小，因为此时 R α （ T ）对模型复杂度惩罚力度较大，倾向于生成较小子树；反之，当 α 较小时，最优子树 T α 规模较大，极端地，当 α =0时，整个树为最优，当 α → ∞ 时，由根结点组成的单结点树为最优。
对于任意给定的待剪枝原始树 T 0 及其任意内部结点 t ，设以 t 为单结点树和以 t 为根结点子树 T t 的泛化性能值分别为 R α （ t ）和 R α （ T t ），则有
显然，多结点子树 T t 对训练样本集的拟合程度优于单结点子树 t ，即有 R （ T t ）< R （ t ）。换言之，在 α 较小时，预测误差项所占权重较大，故有： R α （ T t ）< R α （ t ）。若增大 α 取值，则模型复杂程度对整体性能度量的影响将会逐渐增大，最终使得 R α （ T t ）> R α （ t ）。
不难证明，若取 α （ t ）=[ R （ t ）- R （ T t ）]/（| T t |-1），则多结点子树 T t 与单结点子树 t 的整体性能度量取值相等。由于此时 t 的结点较少，因此 t 比 T t 更可取，此时可对 T t 进行剪枝。
对 T 0 中每一内部结点 t 计算 α （ t ）值，然后在 T 0 中剪去 α （ t ）值最小的 T t 并将所得子树记为 T 1 ，同时将 α （ t ）的最小值记为 α 1 。递归上述过程，直至得到由根结点构成的单结点子树。在这一过程中，不断地增加 α 的值，获得一个取值递增的参数序列 α 1 ， α 2 ，…， α n ，以及剪枝后得到的子树序列{ T 0 ， T 1 ，…， T n }。可使用独立测试集从{ T 0 ， T 1 ，…， T n }中选取最优子树 T α 。具体地说，就是通过独立测试集分别测试子树序列{ T 0 ， T 1 ，…， T n }中各棵子树的泛化性能，从中选择性能最优的子树作为所求剪枝结果。
【例题3.9】 表3-15为拖欠贷款人员训练样本数据集，使用CART算法基于该表数据以构造决策树模型，并使用表3-16中测试样本集确定剪枝后的最优子树。
表3-15 拖欠贷款人员训练样本数据集
表3-16 拖欠贷款人员测试样本数据集
【解】 先考察房产状况特征，根据是否有房可将数据集划分为 D （有）={1，4，7}和 D （无）={2，3，5，6，8，9，10}，分别计算 D （有）和 D （无）的基尼指数
故用房产状况特征对 D 进行子集划分时所得的基尼指数为
若按婚姻情况特征划分，需对其构造二元划分，此时可将婚姻情况特征分为如下三对可能取值形式，并分别计算每种取值形式所对应子集划分的基尼指数。
当划分取值为“婚姻情况=已婚”和“婚姻情况≠已婚”时：
当划分取值为“婚姻情况=单身”和“婚姻情况≠单身”时：
当划分取值为“婚姻情况=离异”和“婚姻情况≠离异”时：
对比上述计算结果，取值分组“婚姻情况=已婚”和“婚姻情况≠已婚”所得基尼指数最小，故取Gini（ D ，婚姻）=0.3。
最后考虑年收入特征，由于该特征为连续性数值，故对其进行二元划分时可用阈值将年收入特征取值范围划分为两个不同区间，具体做法如下：首先，依据“年收入”特征取值对样本进行升序排序，从小到大依次用“年收入”特征相邻取值的均值作为划分阈值，将训练样本集划分为两个子集。
例如，有两个相邻样本的“年收入”取值分别为60和70时，取它们的均值65作为划分阈值，即用 R =65表示年收入的划分点，将“年收入> R ”和“年收入< R ”的样本分别划分到两个样本子集中，并计算对应的基尼指数
同理可得表3-17所示其余划分方式及所对应的基尼指数，由表3-17中数据可知，使用年收入特征对 D 进行划分的最小基尼指数为Gini（ D ， R =97.5）=0.3。
表3-17 年收入特征的划分方式与基尼指数取值表
根据以上计算可知，婚姻情况和年收入特征所对应基尼指数并列最小，均为0.3。不妨选取婚姻状况作为第一个划分点，将集合 D 划分为 D （已婚）={2，4，6，9}和 D （ ¬ 已婚）={1，3，5，7，8，10}，得到如图3-17a所示的初始决策树。
由于 D （已婚）中所有人均不欠贷款，故不用再划分。对 D （ ¬ 已婚）递归调用上述过程继续划分，最后得到图3-17b所示的完整决策树，其中 Y 和 N 分别表示两类不同取值的样本数目。
图3-17 使用CART生成算法构造的完整决策树
现对图3-17b所示决策树进行CCP剪枝优化。设 k =0， T = T k ， α k =+ ∞ ，从根结点 t 1 往下计算每个点的 α （ t ），得到 t 2 和 t 3 的 α （ t ）值并列最小，均为0.1，故有 α 1 =0.1。此时可选择剪枝规模较小的结点，对 t 3 进行剪枝，得到图3-18a所示子树，记为 T 1 。
令 k = k +1， T = T k ， α k =1/10，对图3-18a中决策树继续剪枝，不难得出此时 α （ t 2 ）的取值0.1为最小，故有 α 2 =0.1。剪掉 t 2 得到图3-18b所示子树，记为 T 2 。
令 k = k +1， T = T k ， α k =1/10，此时决策树只包含一个根结点 t 1 ，可算出 α （ t 1 ）=0.2，故有 α 3 =0.2。
将未经剪枝的决策树记为 T 0 ，则可得到 T 0 ， T 1 ， T 2 三棵子树，使用表3-16中测试集分别测试三棵子树的性能，得到子树 T 0 ， T 1 ， T 2 的预测错误率分别为
由于子树 T 0 与 T 2 在测试集上的预测错误率并列最小，但 T 2 的结构较为简单，故选择图3-18b所示子树 T 2 作为所求决策树模型。
图3-18 剪枝后的决策树