本文结构：

• CART算法有两步
• 回归树的生成
• 分类树的生成
• 剪枝

---

CART － Classification and Regression Trees

分类与回归树，是二叉树，可以用于分类，也可以用于回归问题，最先由 Breiman 等提出。

分类树的输出是样本的类别， 回归树的输出是一个实数。

---

CART算法有两步：

决策树生成和剪枝。

决策树生成：递归地构建二叉决策树的过程，基于训练数据集生成决策树，生成的决策树要尽量大；

自上而下从根开始建立节点，在每个节点处要选择一个最好的属性来分裂，使得子节点中的训练集尽量的纯。

不同的算法使用不同的指标来定义"最好"：

分类问题，可以选择GINI，双化或有序双化；
回归问题，可以使用最小二乘偏差（LSD）或最小绝对偏差（LAD）。

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

这里用代价复杂度剪枝 Cost-Complexity Pruning(CCP)

---

回归树的生成

回归树模型表示为：

其中，数据空间被划分成了 R1～Rm 单元，每个单元上有一个固定的输出值 cm。
这样就可以计算模型输出值与实际值的误差：

我们希望每个单元上的 cm，可以使得这个平方误差最小化，易知当 cm 为相应单元上的所有实际值的均值时，可以达到最优：

那么如何生成这些单元划分？

假设，我们选择变量 xj 为切分变量，它的取值 s 为切分点，那么就会得到两个区域：

当 j 和 s 固定时，我们要找到两个区域的代表值 c1，c2 使各自区间上的平方差最小，

前面已经知道 c1，c2 为区间上的平均，

那么对固定的 j 只需要找到最优的 s，
然后通过遍历所有的变量，我们可以找到最优的 j，
这样我们就可以得到最优对（j，s），并得到两个区间。

上述过程表示的算法步骤为：

即：
(1)考虑数据集 D 上的所有特征 j，遍历每一个特征下所有可能的取值或者切分点 s，将数据集 D 划分成两部分 D1 和 D2
(2)分别计算上述两个子集的平方误差和，选择最小的平方误差对应的特征与分割点，生成两个子节点。
(3)对上述两个子节点递归调用步骤(1)(2),直到满足停止条件。

---

分类树的生成

(1)对每个特征 A，对它的所有可能取值 a，将数据集分为 A＝a，和 A!＝a 两个子集，计算集合 D 的基尼指数：

(2)遍历所有的特征 A，计算其所有可能取值 a 的基尼指数，选择 D 的基尼指数最小值对应的特征及切分点作为最优的划分，将数据分为两个子集。
(3)对上述两个子节点递归调用步骤(1)(2), 直到满足停止条件。
(4)生成 CART 决策树。

其中 GINI 指数：

1、是一种不等性度量；
2、是介于 0~1 之间的数，0-完全相等，1-完全不相等；
3、总体内包含的类别越杂乱，GINI指数就越大（跟熵的概念很相似）

定义：
分类问题中，假设有 K 个类，样本属于第 k 类的概率为 pk，则概率分布的基尼指数为：

样本集合 D 的基尼指数为：

其中 Ck 为数据集 D 中属于第 k 类的样本子集。

如果数据集 D 根据特征 A 在某一取值 a 上进行分割，得到 D1 ，D2 两部分后，那么在特征 A 下集合 D 的基尼指数为：

其中算法的停止条件有：

1、节点中的样本个数小于预定阈值，
2、样本集的Gini系数小于预定阈值（此时样本基本属于同一类），
3、或没有更多特征。

下面来看一下例子：

最后一列是我们要分类的目标。

例如，按照“体温为恒温和非恒温”进行划分，计算如下：

恒温时包含哺乳类5个、鸟类2个

非恒温时包含爬行类3个、鱼类3个、两栖类2个

得到特征‘体温’下数据集的GINI指数：

最后我们要选 GINI_Gain 最小的特征和相应的划分。

---

剪枝

就是在完整的决策树上，剪掉一些子树，使决策树变小。

是为了减少决策树过拟合，如果每个属性都被考虑，那决策树的叶节点所覆盖的训练样本基本都是“纯”的，这时候的决策树对训练集表现很好，但是对测试集的表现就会比较差。

决策树很容易发生过拟合，可以改善的方法有：
1、通过阈值控制终止条件，避免树形结构分支过细。
2、通过对已经形成的决策树进行剪枝来避免过拟合。
3、基于Bootstrap的思想建立随机森林。

这里我们用 代价复杂度剪枝 Cost-Complexity Pruning(CCP) 方法来对 CART 进行剪枝。

从整个树 T0 开始，先剪去一棵子树，生成子树 T1，
在 T1 上再剪去一棵子树，生成子树 T2，
重复这个操作，直到最后只剩下一个根节点的子树 Tn，
得到了子树序列 T0～Tn，
利用独立的验证数据集，计算每个子树的平方误差或者基尼指数，
选择误差最小的那个子树作为最优的剪枝后的树。

那么这个子树序列是怎么剪出来的？
因为建模的时候，目标就是让损失函数达到最优，那剪枝的时候也用损失函数来评判。

损失函数是什么呢？
对任意子树 T，损失函数如下形式，cost-complexity function：

其中 CT 为误差（例如基尼指数），|T| 为 T 的叶节点个数，alpha 为非负参数，用来权衡训练数据的拟合程度和模型的复杂度。

alpha 固定时，一定可以找到一个子树 T，使得等式右边达到最小，那么这个 T 就叫做最优子树。

对固定的 alpha 找到损失函数最小的子树 T，二者之间有这样的关系：alpha 大时，T 偏小，alpha 小时，T 偏大。

那如果将 alpha 从小增大设置为一个序列，T 就可以从大到小得到相应的最优子树序列，并且还是嵌套的关系。

剪的时候，哪个树杈是可以被剪掉的呢？
很容易想到的是，如果剪掉后和没剪时的损失函数一样或者差别不大的话，那当然是剪掉好了，只留下一个点，就能代表一个树杈，这样树就被简化了。

以节点 t 为单节点树时，它的损失函数为：（后面剪枝后就可以用一个点来代替一个树杈）

以节点 t 为根节点的子树 Tt，它的损失函数为：（后面剪枝这个树杈）

那么接下来的问题就是能不能找到这样的点呢？
上面令 alpha＝0，就有 Tt 和 t 的损失函数的关系为：

那么增大 alpha，当它为如下形式时：

此时，Tt 和 t 的损失函数相等，而 t 的节点少，那么保留 t 就可以了，Tt 就可以剪掉了。

那么在剪枝算法的第三步时，对每个 t，计算一下 gt，也就是能找到子树 Tt 和 t 的损失函数相等时的 alpha，

每个点 t 都可以找到符合这样条件的 alpha，
遍历所有节点 t 后，找到最小的这个 alpha，

第四步，再把这个 alpha 对应的节点 t 的子树 Tt 剪掉，
并用多数投票表决法决定 t 上的类别，
这样得到的剪枝后的树 T 记为 Tk，
这时的 alpha 记为 alpha k，

经过上面步骤，会得到：
α1⩽α2⩽ ... ⩽αk⩽ ...
T1⊇T2⊇ ... ⊇Tk⊇ ... ⊇{root}

例子：

下面这棵树，有三个点 t1≡root,t2,t3

α(1)=0

计算每个点的 gt：

t2，t3 时的 gt 相等，此时我们可以选择剪枝少的点，那就是 t3 剪掉。

并且 α(2)=1/8

这时剩下 t1，t2，再继续计算 gt：

t2 的小，所以剪掉 t2:

并且令 α(3)=1/8

最后剩下 t1，计算后 gt=1/4，所以 α(4)=1/4。

如此我们得到：α(0)=0,α(1)=1/8,α(2)=1/8,α(3)=1/4
并且得到了相应的子树，
接下来就可以利用独立的验证数据集，计算每个子树的平方误差或者基尼指数，