五、CART算法
(2) CART剪枝 CART剪枝算法从"完全生长"的决策树的底端剪去一些子树，使决策树变小(模型变简单)，从而能够对未知数据有更准确的预测。 分两步： 1.从生产算法产生的整体的树
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 的最底端开始不断剪枝，直至剪到整个树
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 的根结点为止，从而形成了一个
子树序列 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） ；2.通过
交叉验证 法在独立的验证数据集上对子树序列进行测试，从中选出最优子树。
我们在这里也分两步来介绍：
1.剪枝，形成一个子树序列 剪枝剪枝，怎么来剪？ 从前面第4节将的剪枝内容来看，我们需要整一个
损失函数 来控制剪枝。
这个损失函数为：
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 其中，T为
任意子树 ，
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 为对训练数据的
预测误差(如基尼指数)， cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 为子树的叶结点个数，表示树的复杂度的。
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 为参数，
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 为参数是
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 时的子树T的整体损失。
参数 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 权衡训练数据的拟合程度与模型的复杂度。 上述关于损失函数的定义，在前面的章节中已经介绍的非常多了，看过前面的这部分就不难理解。以后的章节中，如果遇到前面详细介绍过的内容，除非必要，就都不啰嗦了。
对固定的一个
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 值，一定存在使损失函数
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 最小的子树，将其表示为
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 。这个
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 取值越大，最优子树就偏向于简单地子树(即叶结点少)，
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 取值越小，最优子树偏向于与训练数据集更好地拟合。我们可以想象一个极端情况，当
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 时，最优子树是根结点构成的
单结点树 ；当
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 时，最优子树就是
整体树本身 。(这个一定要结合上面的损失函数公式来理解)。
前面都了解了那么咱们继续。。。
Breiman(CART提出者)等人证明： 可以用递归的方法对树进行剪枝。什么意思呢？就是将
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 从0开始逐渐增大，
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） ，产生一系列的区间
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） ；对每一个
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 取值，都能得到一个最优子树，最终得到对应的最优子树集
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） ，序列中
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 是整树，一直到
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） (根结点构成的单结点树)，是
嵌套的 。子树序列对应着区间
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 。
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 整个剪枝过程的示意图如上。接下来我们来看看具体数学过程是怎样的。 从整体树
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 开始剪枝。对于
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 的任意内部结点t(除叶结点外的所有结点，包括根结点)，计算以t为
单结点树 的损失函数：
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 如下图
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 然后计算以t为
根结点的子树 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 的
损失函数 ：
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 如下图
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 接下来进行
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 的比较：
1） 当 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） ，有不等式 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 意思是，此时如果保留这个子树，得到的总的损失函数是会比剪掉它更小的，所以我们选择保留子树不剪。
2） 当 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 增大时，在某一 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 值时有 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 此时，由公式可以推出：
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 。
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 在这时取相同的
损失函数值 。但由于t的
结点少 ，因此t比
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 更可取，故应对子树
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 进行剪枝。
3） 当 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 再增大时，1）中的不等式反向，即 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 此时就应该再取下一个内部结点，进行下一步剪枝判断了。
对
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 中每一内部结点t，计算：
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） (即对应着不同的 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 取值) 这个g(t)表示
剪枝后整体损失函数减少的程度 。在
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 中减去g(t)值最小的子树
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） ，将得到的剩下的子树作为
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） ，同时将最小的g(t)设为
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 。
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 为区间
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 的最优子树。
如此剪枝下去，直至得到
根结点 。在这一过程中，不断地增加
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 的值，得到更小的子树，产生新的区间。就得到了
最优子树序列 ，
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） ，剪枝后对新的叶结点t以
多数表决法 决定其类。
2.在剪枝得到的子树序列 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 中通过交叉验证选取最优子树 cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 利用独立的
验证数据集 ，测试子树序列
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 中各棵子树的
平方误差或基尼指数 。选择平方误差或基尼指数
最小 的决策树作为最优的决策树。在子树序列中，每棵子树
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 都对应于一个参数
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 。所以，当最优子树
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 确定时，对应的
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 也确定了，即得到最优决策树
cart算法_第五章 决策树（第5节 CART算法 第2小节 CART剪枝） 。
