分类与回归树模型，英文全称classification and regression tree，简称CART，由Breiman等人在1984年提出，是应用广泛的决策树学习方法。CART同样由特征选择、树的生成及剪枝组成，既可以用于分类也可以用于回归。

CART是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

CART算法由以下两步组成：

（1）决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大；

（2）决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

1. CART生成

决策树的生成就是递归地构建二叉决策树的过程。对回归树用平方误差最小化准则，对分类树用基尼指数最小化准则，进行特征选择，生成二叉树。

1.1. 回归树的生成

假设X与Y分别为输入和输出变量，并且Y是连续变量，给定训练数据集

考虑如何生成回归树。

遍历所有输入变量，找到最优的切分变量j，构成一个对(j,s)。依此将输入空间划分为两个区域。接着，对每个区域重复上述划分过程，直到满足停止条件为止。这样就生成一棵回归树。这样的回归树通常称为最小二乘回归树，现将算法叙述如下。

最小二乘回归树的生成算法

输入：训练数据集D；

输出：回归树f(x)。

在训练数据集所在的输入空间中，递归地将每个区域划分为两个区域并决定每个子区域上的输出值，构建二叉决策树：

（1）选择最优切分变量j与切分点s，求解

遍历变量j，对固定的切分变量j扫描切分点s，选择使上式达到最小值的对(j,s)。

（2）用选定的对(j,s)划分区域并决定相应的输出值：

（3）继续对两个子区域调用步骤（1），（2），直到满足停止条件。

1.2. 分类树的生成

分类树用基尼指数选择最优特征，同时决定该特征的最优二值切分点。

对于二类分类问题，若样本点属于第一个类的概率是p，则概率分布的基尼指数为

对于给定的样本集合D，其基尼指数为

这里，C_k是D中属于第k类的样本子集，K是类的个数。

则在特征A的条件下，集合D的基尼指数定义为

基尼指数Gini(D)表示集合D的不确定性，基尼指数Gini(D,A)表示经A=a分割后集合D的不确定性。基尼指数值越大，样本集合的不确定性也就越大，这一点与熵相似。

CART生成算法

输入：训练数据集D，停止计算的条件；

输出：CART决策树。

根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

（2）在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。

（3）对两个子结点递归地调用（1），（2），直到满足停止条件。

（4）生成CART决策树。

算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。

2. CART剪枝

2.1. 剪枝，形成一个子树序列

在剪枝过程中，计算子树的损失函数：

以t为根结点的子树$\ce{T_t}的损失函数是

当α=0及α充分小时，有不等式

当α增大时，在某一α有

当α再增大时，

如此剪枝下去，直到得到根结点。在这一过程中，不断地增加α的值，产生新的区间。

CART剪枝算法

参考文献

【1】统计学习方法（第2版），李航著，清华大学出版社