我在决策树小结中介绍了决策树的相关只是，也介绍了分类与回归树（CART）的构建等等。这篇文章主要是对 CART 的具体计算方式进行例子展示。
分类与回归树简介
分类与回归树的英文是 Classfication And Regression Tree ，缩写为 CART。CART 算法采用二分递归分割的技术将当前样本集分为两个子样本集，使得生成的每个非叶子节点都有两个分支。非叶子节点的特征取值为 True 和 False，左分支取值为 True，右分支取值为 False，因此CART算法生成的决策树是结构简洁的二叉树。CART 可以处理连续型变量和离散型变量，利用训练数据递归的划分特征空间进行建树，用验证数据进行剪枝。如果待预测分类是离散型数据，则 CART 生成分类决策树。如果待预测分类是连续性数据，则 CART 生成回归决策树。
CART 分类树
算法分析
CART 分类树预测分类离散型数据，采用基尼指数选择最优特征，同时决定该特征的最优二值切分点。分类过程中，假设有 $K$ 个类，样本点属于第 $k$ 个类的概率为 $p_k$，则概率分布的基尼指数定义为：
根据基尼指数定义，可以得到样本集合 $D$ 的基尼指数，其中 $C_k$ 表示数据集 $D$ 中属于第 $k$ 类的样本子集。
如果数据集 $D$ 根据特征 $A$ 在某一取值 $a$ 上进行分割，得到 $D1$，$D2$ 两部分后，那么在特征 $A$ 下集合 $D$ 的基尼系数如下所示。
其中基尼系数 $Gini(D)$ 表示集合 $D$ 的不确定性，基尼系数 $Gini(D,A)$ 表示 $A=a$ 分割后集合 $D$ 的不确定性。基尼指数越大，样本集合的不确定性越大。
对于属性 $A$，分别计算任意属性值将数据集划分为两部分之后的 $Gain\_Gini$，选取其中的最小值，作为属性 $A$ 得到的最优二分方案。然后对于训练集 $S$，计算所有属性的最优二分方案，选取其中的最小值，作为样本集 $S$ 的最优二分方案。
实例详解
| 名称 | 体温 | 胎生 | 水生 | 类标记 |
|---|---|---|---|---|
| 人 | 恒温 | 是 | 否 | 哺乳类 |
| 巨蟒 | 冷血 | 否 | 否 | 爬行类 |
| 鲑鱼 | 冷血 | 否 | 是 | 鱼类 |
| 鲸 | 恒温 | 是 | 是 | 哺乳类 |
| 蛙 | 冷血 | 否 | 有时 | 鱼类 |
| 巨蜥 | 冷血 | 否 | 否 | 爬行类 |
| 蝙蝠 | 恒温 | 是 | 否 | 哺乳类 |
| 猫 | 恒温 | 是 | 否 | 哺乳类 |
| 豹纹鲨 | 冷血 | 是 | 是 | 鱼类 |
| 海龟 | 冷血 | 否 | 有时 | 爬行类 |
| 豪猪 | 恒温 | 是 | 否 | 哺乳类 |
| 鳗 | 冷血 | 否 | 是 | 鱼类 |
| 蝾螈 | 冷血 | 否 | 有时 | 两栖类 |
针对上述离散型数据，按照体温为恒温和非恒温进行划分。其中恒温时包括哺乳类 5 个、鸟类 2 个，非恒温时包括爬行类 3 个、鱼类 3 个、两栖类 2 个，如下所示我们计算 $D1$，$D2$ 的基尼指数。
然后计算得到特征体温下数据集的 Gini 指数。
依照上述的方法分别计算各个特征的 $Gain\_Gini$，最后我们选择 $Gain\_Gini$ 最小的特征和相应的划分。然后对于每一个分支集合，分别在剩余的特征中选择最优的特征进行划分（同一层的左右节点二次划分的特征不一定相同），直到满足决策树的终止条件。
CART 回归树
算法详解
CART 回归树预测回归连续型数据，假设 $X$ 与 $Y$ 分别是输入和输出变量，并且 $Y$ 是连续变量。在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。
选择最优切分变量 $j$ 与切分点 $s$：因为对于连续变量，不能再使用 Gini 系数来衡量节点划分的好坏了，在 CART 中，一般使用平方误差来对衡量。遍历变量 $j$，对规定的切分变量 $j$ 扫描切分点 $s$，选择使下式得到最小值时的 $(j, s)$ 对。其中 $R_m$ 是被划分的输入空间，$c_m$ 是空间 $R_m$ 对应的固定输出值，也就是预测值。
用选定的($j$, $s$)对，划分区域并决定相应的输出值
继续对两个子区域调用上述步骤，将输入空间划分为 $M$ 个区域 $R_1$, $R_2$, …, $R_m$，生成决策树。
当输入空间划分确定时，可以用平方误差来表示回归树对于训练数据的预测方法，用平方误差最小的准则求解每个单元上的最优输出值。
实例详解
| $x_i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $y_i$ | 5.56 | 5.70 | 5.91 | 6.40 | 6.80 | 7.05 | 8.90 | 8.70 | 9.00 | 9.05 |
考虑如上所示的连续性变量，根据给定的数据点，考虑 1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5 切分点。对各切分点依次求出 $R_1$, $R_2$, $c_1$, $c_2$ 及 $m(s)$，例如当切分点 $s=1.5$ 时，得到 $R_1={1}$, $R2={2,3,4,5,6,7,8,9,10}$，其中 $c_1$, $c_2$, $m(s)$ 如下所示。
依次改变($j$, $s$)对，可以得到 $s$ 及 $m(s)$ 的计算结果，如下表所示。
| $s$ | 1.5 | 2.5 | 3.5 | 4.5 | 5.5 | 6.5 | 7.5 | 8.5 | 9.5 |
|---|---|---|---|---|---|---|---|---|---|
| $m(s)$ | 15.72 | 12.07 | 8.36 | 5.78 | 3.91 | 1.93 | 8.01 | 11.73 | 15.74 |
当 $x=6.5$ 时，此时 $R_1={1,2,3,4,5,6}$, $R_2={7,8,9,10}$, $c_1=6.24$, $c_2=8.9$。回归树 $T_1(x)$ 为
和分类树一样，我们对每个子树分别递归使用未处理的特征进行上述操作，直到满足决策树终止的条件，这样就构建了一颗 CART 回归树。
GBDT 计算
接上面的例子，下面展示了 GBDT 树中残差计算与构建过程，仅供参考。
首先计算上述的 $f_1(x)$ 拟合训练数据的残差，如下表所示：
| $x_i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| $y_i$ | -0.68 | -0.54 | -0.33 | 0.16 | 0.56 | 0.81 | -0.01 | -0.21 | 0.09 | 0.14 |
用 $f_1(x)$ 拟合训练数据得到平方误差：
第二步求 $T_2(x)$ 与求 $T_1(x)$ 方法相同，只是拟合的数据是上表的残差。可以得到:
用 $f_2(x)$ 拟合训练数据的平方误差
继续求得 $T_3(x)$、$T_4(x)$、$T_5(x)$、$T_6(x)$，如下所示
用 $f_6(x)$ 拟合训练数据的平方损失误差如下所示，假设此时已经满足误差要求，那么 $f(x)=f_6(x)$ 便是所求的回归树。
CART 剪枝
CART 剪枝的方法很多，此处我们介绍代价复杂度剪枝算法。
我们将一颗充分生长的树称为 $T_0$ ，希望减少树的大小来防止过拟化。但同时去掉一些节点后预测的误差可能会增大，那么如何达到这两个变量之间的平衡则是问题的关键。因此我们用一个变量 $\alpha$ 来平衡，定义损失函数如下：
- $T$ 为任意子树，$|T|$ 为子树 $T$ 的叶子节点个数。
- $\alpha$ 是参数，权衡拟合程度与树的复杂度。
- $C(T)$ 为预测误差，可以是平方误差也可以是基尼指数，$C(T)$ 衡量训练数据的拟合程度。
那么我们如何找到这个合适的 $\alpha$ 来使拟合程度与复杂度之间达到最好的平衡呢？准确的方法就是将 $\alpha$ 从 0 取到正无穷，对于每一个固定的 $\alpha$，我们都可以找到使得 $C_\alpha(T)$最小的最优子树 $T(\alpha)$。
- 当 $\alpha$ 很小的时候，$T_0$ 是这样的最优子树.
- 当 $\alpha$ 很大的时候，单独一个根节点就是最优子树。
尽管 $\alpha$ 的取值无限多，但是 $T0$ 的子树是有限个。$T_n$ 是最后剩下的根结点，子树生成是根据前一个子树 $T_i$，剪掉某个内部节点后，生成 $T{i+1}$。然后对这样的子树序列分别用测试集进行交叉验证，找到最优的那个子树作为我们的决策树。子树序列如下：
因此 CART 剪枝分为两部分，分别是生成子树序列和交叉验证，在此不再详细介绍。
Sklearn实现
我们以 sklearn 中 iris 数据作为训练集，iris 属性特征包括花萼长度、花萼宽度、花瓣长度、花瓣宽度，类别共三类，分别为 Setosa、Versicolour、Virginca。
1 | from sklearn.datasets import load_iris |