下载掌阅APP，畅读海量书库
立即打开
5.5 CART算法
分类与回归树（classification and regression tree，CART）模型由Breiman等人在1984年提出，是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。以下将用于分类与回归的树统称为决策树。
CART是在给定输入随机变量 X 条件下输出随机变量 Y 的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。
CART算法由以下两步组成：
（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；
（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。
决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数（Gini index）最小化准则，进行特征选择，生成二叉树。
假设 X 与 Y 分别为输入和输出变量，并且 Y 是连续变量，给定训练数据集
考虑如何生成回归树。
一棵回归树对应着输入空间（即特征空间）的一个划分以及在划分的单元上的输出值。假设已将输入空间划分为 M 个单元 R 1 , R 2 ,…, R M ，并且在每个单元 R m 上有一个固定的输出值 c m ，于是回归树模型可表示为
当输入空间的划分确定时，可以用平方误差
来表示回归树对于训练数据的预测误差，用平方误差最小的准则求解每个单元上的最优输出值。易知，单元
R
m
上的
c
m
的最优值
是
R
m
上的所有输入实例
x
i
对应的输出
y
i
的均值，即
问题是怎样对输入空间进行划分。这里采用启发式的方法，选择第 j 个变量 x ( j ) 和它取的值 s ，作为切分变量（splitting variable）和切分点（splitting point），并定义两个区域：
然后寻找最优切分变量 j 和最优切分点 s 。具体地，求解
对固定输入变量 j 可以找到最优切分点 s 。
遍历所有输入变量，找到最优的切分变量 j ，构成一个对（ j , s ）。依此将输入空间划分为两个区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止。这样就生成一棵回归树。这样的回归树通常称为最小二乘回归树（least squares regression tree），现将算法叙述如下。
算法5.5（最小二乘回归树生成算法）
输入：训练数据集 D ；
输出：回归树 f （ x ）。
在训练数据集所在的输入空间中，递归地将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树：
（1）选择最优切分变量 j 与切分点 s ，求解
遍历变量 j ，对固定的切分变量 j 扫描切分点 s ，选择使式（5.21）达到最小值的对（ j , s ）。
（2）用选定的对（ j , s ）划分区域并决定相应的输出值：
（3）继续对两个子区域调用步骤（1），（2），直至满足停止条件。
（4）将输入空间划分为 M 个区域 R 1 , R 2 ,…, R M ，生成决策树：
分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。
定义5.4（基尼指数） 分类问题中，假设有 K 个类，样本点属于第 k 类的概率为 p k ，则概率分布的基尼指数定义为
对于二类分类问题，若样本点属于第1个类的概率是 p ，则概率分布的基尼指数为
对于给定的样本集合 D ，其基尼指数为
这里， C k 是 D 中属于第 k 类的样本子集， K 是类的个数。
如果样本集合 D 根据特征 A 是否取某一可能值 a 被分割成 D 1 和 D 2 两部分，即
则在特征 A 的条件下，集合 D 的基尼指数定义为
基尼指数Gini（ D ）表示集合 D 的不确定性，基尼指数Gini（ D , A ）表示经 A = a 分割后集合 D 的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。
图5.7显示二类分类问题中基尼指数Gini（ p ）、熵（单位比特）之半 H （ p ）/2和分类误差率的关系。横坐标表示概率 p ，纵坐标表示损失。可以看出基尼指数和熵之半的曲线很接近，都可以近似地代表分类误差率。
图5.7 二类分类中基尼指数、熵之半和分类误差率的关系
算法5.6（CART生成算法）
输入：训练数据集 D ，停止计算的条件；
输出：CART决策树。
根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：
（1）设结点的训练数据集为 D ，计算现有特征对该数据集的基尼指数。此时，对每一个特征 A ，对其可能取的每个值 a ，根据样本点对 A = a 的测试为“是”或“否”将 D 分割成 D 1 和 D 2 两部分，利用式（5.25）计算 A = a 时的基尼指数。
（2）在所有可能的特征 A 以及它们所有可能的切分点 a 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
（3）对两个子结点递归地调用（1），（2），直至满足停止条件。
（4）生成CART决策树。
算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。
例5.4 根据表5.1所给训练数据集，应用CART算法生成决策树。
解 首先计算各特征的基尼指数，选择最优特征以及其最优切分点。仍采用例5.2的记号，分别以 A 1 ， A 2 ， A 3 ， A 4 表示年龄、有工作、有自己的房子和信贷情况4个特征，并以1，2，3表示年龄的值为青年、中年和老年，以1，2表示有工作和有自己的房子的值为是和否，以1，2，3表示信贷情况的值为非常好、好和一般。
求特征 A 1 的基尼指数：
由于Gini（ D , A 1 =1）和Gini（ D , A 1 =3）相等，且最小，所以 A 1 =1和 A 1 =3都可以选作 A 1 的最优切分点。
求特征 A 2 和 A 3 的基尼指数：
由于 A 2 和 A 3 只有一个切分点，所以它们就是最优切分点。
求特征 A 4 的基尼指数：
Gini（ D , A 4 =3）最小，所以 A 4 =3为 A 4 的最优切分点。
在 A 1 ， A 2 ， A 3 ， A 4 几个特征中，Gini（ D , A 3 =1）=0.27最小，所以选择特征 A 3 为最优特征， A 3 =1为其最优切分点。于是根结点生成两个子结点，一个是叶结点。对另一个结点继续使用以上方法在 A 1 ， A 2 ， A 4 中选择最优特征及其最优切分点，结果是 A 2 =1。依此计算得知，所得结点都是叶结点。
对于本问题，按照CART算法所生成的决策树与按照ID3算法所生成的决策树完全一致。
CART剪枝算法从“完全生长”的决策树的底端剪去一些子树，使决策树变小（模型变简单），从而能够对未知数据有更准确的预测。CART剪枝算法由两步组成：首先从生成算法产生的决策树 T 0 底端开始不断剪枝，直到 T 0 的根结点，形成一个子树序列{ T 0 , T 1 ,…, T n }；然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
在剪枝过程中，计算子树的损失函数：
其中， T 为任意子树， C （ T ）为对训练数据的预测误差（如基尼指数），| T |为子树的叶结点个数， α ≥0为参数， C α （ T ）为参数是 α 时的子树 T 的整体损失。参数 α 权衡训练数据的拟合程度与模型的复杂度。
对固定的 α ，一定存在使损失函数 C α （ T ）最小的子树，将其表示为 T α 。 T α 在损失函数 C α （ T ）最小的意义下是最优的。容易验证这样的最优子树是唯一的。当 α 大的时候，最优子树 T α 偏小；当 α 小的时候，最优子树 T α 偏大。极端情况，当 α =0时，整体树是最优的。当 α→∞ 时，根结点组成的单结点树是最优的。
Breiman等人证明：可以用递归的方法对树进行剪枝。将 α 从小增大，0= α 0 < α 1 <…< α n <+ ∞ ，产生一系列的区间[ α i , α i +1 ）, i =0,1,…, n ；剪枝得到的子树序列对应着区间 α ∈[ α i , α i +1 ）， i =0,1,…, n 的最优子树序列{ T 0 , T 1 ,…, T n }，序列中的子树是嵌套的。
具体地，从整体树 T 0 开始剪枝。对 T 0 的任意内部结点 t ，以 t 为单结点树的损失函数是
以 t 为根结点的子树 T t 的损失函数是
当 α =0及 α 充分小时，有不等式
当 α 增大时，在某一 α 有
当
α
再增大时，不等式（5.29）反向。只要
，
T
与
t
有相同的
t
损失函数值，而
t
的结点少，因此
t
比
T
t
更可取，对
T
t
进行剪枝。
为此，对 T 0 中每一内部结点 t ，计算
它表示剪枝后整体损失函数减少的程度。在 T 0 中剪去 g （ t ）最小的 T t ，将得到的子树作为 T 1 ，同时将最小的 g （ t ）设为 α 1 。 T 1 为区间[ α 1 , α 2 ）的最优子树。
如此剪枝下去，直至得到根结点。在这一过程中，不断地增加 α 的值，产生新的区间。
具体地，利用独立的验证数据集，测试子树序列 T 0 , T 1 ,…, T n 中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每棵子树 T 1 , T 2 ,…, T n 都对应于一个参数 α 1 , α 2 ,…, α n 。所以，当最优子树 T k 确定时，对应的 α k 也确定了，即得到最优决策树 T α 。
现在写出CART剪枝算法。
算法5.7（CART剪枝算法）
输入：CART算法生成的决策树 T 0 ；
输出：最优决策树 T α 。
（1）设 k =0， T = T 0 。
（2）设 α =+ ∞ 。
（3）自下而上地对各内部结点 t 计算 C （ T t ），| T t |以及
这里， T t 表示以 t 为根结点的子树， C （ T t ）是对训练数据的预测误差，| T t |是 T t 的叶结点个数。
（4）对 g （ t ）= α 的内部结点 t 进行剪枝，并对叶结点 t 以多数表决法决定其类，得到树 T 。
（5）设 k = k +1， α k = α ， T k = T 。
（6）如果 T k 不是由根结点及两个叶结点构成的树，则回到步骤（2）；否则令 T k = T n 。
（7）采用交叉验证法在子树序列 T 0 , T 1 ,…, T n 中选取最优子树 T α 。