本文来自我的个人博客 https://www.zhangshenghai.com/posts/31705/

分类与回归树（classification and regression tree, CART）模型是应用广泛的决策树学习方法，同样由特征选择、树的生成和剪枝组成，既可以用于分类也可以用于回归。

CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。

CART算法主要由以下两步组成：

决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。
决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。

CART生成

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

回归树的生成

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

$\begin{align} \\ & D = \left\{ \left(x_{1},y_{1}\right), \left(x_{2},y_{2}\right),\cdots,\left(x_{N},y_{N}\right) \right\}\end{align}$

可选择第 $j$ 个变量 $x_{j}$ 及其取值 $s$ 作为切分变量和切分点，并定义两个区域
$\begin{align} \\ & R_{1} \left( j,s \right) = \left\{ x | x_{j} \leq s \right\}, \quad R_{2} \left( j,s \right) = \left\{ x | x_{j} > s \right\} \end{align}$
然后寻找最优切分变量 $x_{j}$ 及最优切分点 $s$ ，具体地，求解
$\begin{align*} \\ & j,s = \arg \min_{j,s} \left[ \min_{c_{1}} \sum_{x_{i} \in R_{1} \left(j,s\right)} \left( y_{i} - c_{1} \right)^{2} + \min_{c_{2}} \sum_{x_{i} \in R_{2} \left(j,s\right)} \left( y_{i} - c_{2} \right)^{2}\right] \end{align*}$
其中， $c_{m}$ 是区域 $R_{m}$ 上的回归决策树输出，是区域 $R_{m}$ 上所有输入实例 $x_{i}$ 对应的输出 $y_{i}$ 的均值
$\begin{align*} \\ & c_{m} = ave \left( y_{i} | x_{i} \in R_{m} \right), \quad m=1,2 \end{align*}$
对每个区域 $R_{1}$ 和 $R_{2}$ 重复上述过程，将输入空间划分为 $M$ 个区域 $R_{1},R_{2},\cdots,R_{M}$ ，在每个区域上的输出为 $c_{m},m=1,2,\cdots,M$ ，最小二乘回归树可表示为
$\begin{align*} \\ & f \left( x \right) = \sum_{m=1}^{M} c_{m} I \left( x \in R_{m} \right) \end{align*}$

最小二乘回归树生成算法

输入：训练数据集 $D$
输出：回归树 $f \left( x \right)$

选择最优切分变量 $x_{j}$ 与切分点 $s$
$\begin{align*} \\ & j,s = \arg \min_{j,s} \left[ \min_{c_{1}} \sum_{x_{i} \in R_{1} \left(j,s\right)} \left( y_{i} - c_{1} \right)^{2} + \min_{c_{2}} \sum_{x_{i} \in R_{2} \left(j,s\right)} \left( y_{i} - c_{2} \right)^{2}\right] \end{align*}$
用最优切分变量 $x_{j}$ 与切分点 $s$ 划分区域并决定相应的输出值
$\begin{align*} \\ & R_{1} \left( j,s \right) = \left\{ x | x_{j} \leq s \right\}, \quad R_{2} \left( j,s \right) = \left\{ x | x_{j} > s \right\} \\ & c_{m} = \dfrac{1}{N} \sum_{x_{i} \in R_{m} \left( j,s \right)} y_{i}, \quad m=1,2\end{align*}$
继续对两个子区域调用步骤1.和2.，直到满足停止条件
将输入空间划分为 $M$ 个区域 $R_{1},R_{2},\cdots,R_{M}$ ，生成决策树
$\begin{align*} \\ & f \left( x \right) = \sum_{m=1}^{M} \hat c_{m} I \left( x \in R_{m} \right) \end{align*}$

分类树的生成

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

分类问题中，假设有 $K$ 个类，样本点属于第 $k$ 类的概率为 $p_{k}$ ，则概率分布的基尼指数定义为：
$\begin{align*} \\ & Gini \left( p \right) = \sum_{k=1}^{2} p_{k} \left( 1 - p_{k} \right) = 2p\left(1-p\right) \end{align*}$
对于二类分类问题，若样本点属于第1类的概率为 $p$ ，则概率分布的基尼指数为：
$\begin{align*} \\ & Gini \left( p \right) = \sum_{k=1}^{2} p_{k} \left( 1 - p_{k} \right) = 2p\left(1-p\right) \end{align*}$
对于给定样本集和 $D$ ，其基尼指数为：
$Gini \left( D \right) = 1 - \sum_{k=1}^{K} \left( \dfrac{\left| C_{k} \right|}{\left| D \right|} \right)^{2}$
其中， $C_{k}$ 是 $D$ 中属于第 $k$ 类的样本自己， $K$ 是类别个数。

如果样本集合 $D$ 根据特征 $A$ 是否取某一可能值 $a$ 被分割成 $D_{1}$ 和 $D_{2}$ 两个部分，即
$\begin{align*} \\ & D_{1} = \left\{ \left(x,y\right) | A\left(x\right)=a \right\}, \quad D_{2} = D - D_{1} \end{align*}$
则在特征 $A$ 的条件下，集合 $D$ 的基尼指数为：
$\begin{align*} \\ & Gini \left( D, A \right) = \dfrac{\left| D_{1} \right|}{\left| D \right|} Gini \left( D_{1} \right) + \dfrac{\left| D_{2} \right|}{\left| D \right|} Gini \left( D_{2} \right)\end{align*}$
基尼指数 $Gini \left( D \right)$ 表示集合 $D$ 的不确定性，基尼指数 $Gini \left( D,A \right)$ 表示经 $A=a$ 分割后集合 $D$ 的不确定性。基尼指数值越大，样本集合的不确定性也越大，这一点与熵类似。

CART生成算法

输入：训练数据集 $D$ ，特征 $A$ ，阈值 $\varepsilon$
输出：CART决策树

设结点的训练数据集为 $D$ ，对每一个特征 $A$ ，对其可能取的每个值 $a$ ，根据样本点对 $A=a$ 的测试为“是”或“否”将 $D$ 分割成 $D_{1}$ 和 $D_{2}$ 两部分，并计算 $Gini\left(D,A\right)$ 。
在所有可能的特征 $A$ 以及其所有可能的切分点 $a$ 中，选择基尼指数最小的特征及其对应的切分点作为最优特征与最优切分点。依此从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
对两个子结点递归地调用1.和2.，直至满足停止条件。
生成CART决策树 $T$ 。

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

CART剪枝

CART剪枝算法从“完全生长”的决策树低端剪去一些子树，使决策树边小，从而能够对未知数据有更准确的预测。

剪枝，形成一个子树序列 $T_0, T_1, ... , T_n$

对整体树 $T_{0}$ 任意内部结点 $t$ ，以 $t$ 为单结点树的损失函数是：
$\begin{align} \\ & C_{\alpha} \left( t \right) = C \left( t \right) + \alpha \end{align}$
以 $t$ 为根结点的子树 $T_{t}$ 的损失函数是：
$\begin{align} \\ & C_{\alpha} \left( T_{t} \right) = C \left( T_{t} \right) + \alpha \left| T_{t} \right| \end{align}$
当 $\alpha = 0$ 及 $\alpha$ 充分小时，有不等式：
$\begin{align*} \\ & C_{\alpha} \left( T_{t} \right) < C_{\alpha} \left( t \right) \end{align*}$
当 $\alpha$ 增大时，在某一 $\alpha$ 有：
$\begin{align*} \\ & \quad\quad C_{\alpha} \left( T_{t} \right) ＝ C_{\alpha} \left( t \right) \\ & C \left( T_{t} \right) + \alpha \left| T_{t} \right| ＝ C \left( t \right) + \alpha \\ & \quad\quad \alpha = \dfrac{C\left( t \right) - C \left(T_{t}\right)} { \left| T_{t} \right| -1 }\end{align*}$
即 $T_{t}$ 与 $t$ 有相同的损失函数值，而 $t$ 的结点少，因此对 $T_{t}$ 进行剪枝。

在剪枝得到的子树序列 $T_0, T_1, ... , T_n$ 中通过交叉验证选取最优子树 $T_n$

具体地，利用独立的验证数据集，测试子树序列 $T_0, T_1, ... , T_n$ 中各棵子树的平方误差或基尼指数。平方误差或基尼指数最小的决策树被认为是最优的决策树。在子树序列中，每棵子树 $T_0, T_1, ... , T_n$ 都对应一个参数 $\alpha_1, \alpha_2, ... , \alpha_n$ 。所以，当最优子树 $T_k$ 确定时，对应的 $\alpha_k$ 也确定了，即得到最优决策树 $T_{\alpha}$ 。

CART剪枝算法

输入：CART决策树 $T_{0}$
输出：最优决策树 $T_{\alpha}$

设 $k=0, T=T_{0}$
设 $\alpha=+\infty$
自下而上地对各内部结点 $t$ 计算 $C\left(T_{t}\right),\left| T_{t} \right|$ ，以及
$\begin{align*} \\ & g\left(t\right) = \dfrac{C\left( t \right) - C \left(T_{t}\right)} { \left| T_{t} \right| -1 } \\ & \alpha = \min \left( \alpha, g\left( t \right) \right) \end{align*}$
其中， $T_{t}$ 表示以 $t$ 为根结点的子树， $C\left(T_{t}\right)$ 是对训练数据的预测误差， $\left| T_{t} \right|$ 是 $T_{t}$ 的叶结点个数。
自下而上地访问内部结点 $t$ ，如果有 $g\left(t\right)=\alpha$ ，则进行剪枝，并对叶结点 $t$ 以多数表决法决定其类别，得到树 $T$
设 $k=k+1, \alpha_{k}=\alpha, T_{k}=T$
如果 $T$ 不是由根结点单独构成的树，则回到步骤4.
采用交叉验证法在子树序列 $T_{0},T_{1},\cdots,T_{n}$ 中选取最优子树 $T_{\alpha}$