CART树的剪枝算法由两步组成：首先从生成算法的决策树$T_0$底端开始不断剪枝，直到$T_0$的根节点，形成一个子树序列{$T_0,T_1,T_2,…,T_n$};然后通过交叉验证法在独立的验证数据集上对子树序列进行测试，从中选择最优子树。
剪枝，形成一个子树序列
在剪枝过程中，计算子树的损失函数:
其中，T为任意子树，$C(T)$为对训练数据的预测误差（比如基尼指数或者错误率 ）,|T|为子树T的叶节点个数，a大于等于0为参数，$C_a(T)$为参数是a时的子树T的整体损失。参数a权衡训练数据的拟合程度与模型的复杂度。（又有一点正则化项的感觉）。
对固定的a，一定存在使损失函数$C_a(T)$最小的子树，将其表示为$T_a$。$T_a$在损失函数$C_a(T)$最小的意义下是最优的。容易验证这样的最优子树是唯一的。当a大的时候，最优子树$T_a$偏小（如果a比较大会导致后面一项比较大，所以尽量让|T|小一些）；当a小的时候，最优子树$T_a$偏大。极端情况下，如果a=0,那么整体树是最优的。当a接近于无穷，根节点组成的单节点树是最优的。
从整体树（最上面的根节点）$T_0$开始剪枝，对$T_0$的任意内部结点t（一般是自下而上的算），以t为单节点树的损失函数是(把t当做一个叶子结点计算，那么之前t下面的所有叶子结点的样本都会放到这个t结点中去),因为把t当做单节点，所以a后面的数是|1|,接着在计算以t为根节点的子树$T_t$的损失函数是：
当a=0时候或者a充分小时，有不等式
当a增大时，在某一a有
当a再增大时，不等式反向。那么我们知道，只要
这个t节点在做单结点或者子树时有相同的损失函数，而作为单结点的时候结点少，因此t比$T_t$更可取，所以我们对这个t结点以下的部分进行剪枝，让这个t变成单结点。
所以我们计算这课整体树$T_0$的每一个非叶节点，计算
这个式子表示减值后整体损失函数减少的程度。在$T_0$中剪去g(t)最小的$T_t$,将得到的子树作为$T_1$,同时将最小的g(t)设置为$a_1$,$T_1$为区间$[a_1,a_2)$的最优子树。
我们来捋一捋这段话，为什么g(t)表示剪枝后整体损失函数减少的程度，讲道理是g(t)越大越好对不对，但是为什么我们要先从g(t)最小的来做呢。
我们先再来理一遍剪枝时候的情况。对于每个给定的a值，树中的每个非叶子结点作为子结点或者叶子结点时，树的预测误差性是不同的，也就是说该结点修剪前和修剪之后，对应的树对训练数据的预测误差不同，代价函数的损失大小也不同。
如上图所示，假设在a变化时，数中的两个结点对应的预测误差的变化（修剪前后）分别是黑色和红色线所示，当a比较小的时候，结点不修剪的误差要小于修剪后的误差（因为a小，所以后面一项的值小，所以肯定树越复杂预测效果越好，损失函数越小），但当a增大时，慢慢的修剪后的误差和修剪前的误差会慢慢接近，直到相等，这个值我们把他叫做临界值$g(t)$
那我们为什么要选最小的g(t)呢，以图中两个点为例，结点1和结点2，$g(t)_2 > g(t)_1$,假设在所有的节点中g(t_2)最大，g(t_1)最小，那么我们如果选择最大的值，对结点2进行了剪枝，但此时结点1的不修剪的损失函数大于修剪之后的损失函数，这说明如果不修剪的话，误差会变大，依次类推，对于其他结点也如此，这相当于你的a是很大的，导致你的第二项很大，所以损失函数很大。这造成整体的累计误差也很大。但是如果我们选择了最小值，也就是对结点1进行了剪枝，则其余结点不剪枝的损失函数要小于剪枝之后的损失函数，对于这些结点来说不修剪就是最好的，也就说明整体误差小。从而以最小的g(t)剪枝获得子树是这个a值下的最优子树。
顺便说一下，上面的那个式子g(t)他也是等于a的，这是东西叫做误差增益，看看它的分子就会明白了：分子是由剪枝前后模型的拟合程度的差值构成的，也就是说，a的大小和剪枝前后模型的拟合能力的变化所决定的n ，由于剪枝的关系，模型在样本内的拟合能力通常是减弱的，所以才叫做”误差”增益值。所以对于那个完整的树$T_0$中的每个结点t，我们都要计算误差增益是多少，然后拟合能力减少最小的那个剪枝方案$T_1$就是我们最需要的。
下面还是拿个例子还说把，分类问题。
用我们上面的剪枝方法先初始$k=0,T=T_0$,自上而下的计算每个结点的g(t)
$C(t)$表示训练数据的预测误差（我们的例子用基尼指数计算）= 结点t上的数据占所有数据的比例*结点的误差率，而结点的误差率 = 分错的样本数/（这个结点总共的）。
$C(T_t)$表示子树$T_t$的预测误差 = 子树 $T_t$上所有叶子结点的预测误差之和，就等于要计算每一个叶子结点，按照计算$C(t)$那样计算，最后把值加到一起。
如假我们一共有60条数据，而这个T4结点一共包含了16条数据，我们开始计算T4的信息：
（某个叶节点k类比较多，我就认为这个正确分类是k类，其他不是k类的都是错分样本）
经过计算之后
令a = 1/60.
如果是回归问题的话，我们可能需要把基尼指数换成平方损失这种损失函数来进行计算了。
接下来进行第二部分
在剪枝得到的子树序列$T_0,T_1,T_2,…,T_n$中通过交叉验证选取最优子树$T_a$
具体的，利用独立的验证数据集，测试子树序列中各颗子树的平方误差或者基尼指数。平方误差或者基尼指数最小的决策树被认为是最优的决策树。每棵树都对应着参数a.所以，当最优子树$T_k$确定了，那么参数$a_k$也就确定了。
现在总结一下CART剪枝算法。
输入:CART算法生成的决策树$T_0$
输出：最优决策树
（1）设$k = 0,T=T_0$,a=正无穷。
（2）自下而上的对各非叶子结点计算$C(T_t),|T_t|,g(t)，a=min(a,g(t))$
(g(t)代表的是一个a的临界值，是当剪枝前和剪枝后的损失损失相同时的a值)，当计算完所有的叶子结点之后，这时的a是最小值，和最小的g(t)相等。
(3) 自上而下的访问每个非叶子结点，如果有g(t)=a，说明找到了最小的g(t)，进行剪枝，并对已经变成叶子 结点的t以多数表决发决定其类，得到树T。
（4）设$k=k+1,a_k=a,T_k=T$
(5) 如果T不是由根结点一个单结点组成的树，则退回到步骤2重新计算，划重点这时候退回去的树是一棵完整的原来的树，最开始的树，但是a已经变大了）（重新找最小的g(t)）,否则$T_k=T_n$
(6) 采用交叉验证法用验证集在子树集合中找到最优子树。
对整体过程更为直观的理解，注意上面的几个关键地方：
1.对树的更新是创建一个新的子树，并不是对更新了的子树赋值给树带回到步骤2，而回到步骤2的还是完整的没有任何剪枝树。
2.因为是逐渐增大，所以开始为0时，不会剪枝，因为过小，树的结构复杂也对损失函数造成不了什么影响，随着的增大，会到达某一个临界点，这个临界点就是所有内部结点算出的g(t)中的最小的g(t)，我们称为g(t0)，此时剪枝不剪枝损失相同，但为了结构更加简单(奥卡姆剃刀原理)，进行剪枝。
然后剪枝完了，得到一颗子树，并保存下来。之后恢复完整没剪枝的树回到步骤2里面，并且因为是自下而上的，所以对上面刚刚剪枝的临界值即g(t0)的基础上增大,第二次剪枝的时候就彻底不考虑g(t0)了，因为之前第一次剪枝的是所有里面最小的，所以后面的肯定比第一次的临界大，因此满足了书中的不断增加值。
然后再找一个g(t0)大的g(t1)，并且g(t1)比除了g(t0)的g(t)都小，于是这就是第二个剪枝的临界点，找到g(t1)对应的结点，并在此进行剪枝，又得到一棵子树，然后再找比g(t0) g(t1)大但比其他g(t)小的g(t2)，重复之前的过程，直到增大到恰好等于只剩初始完整树的根节点加俩叶节点时的g(tn)，停止，并返回这个树，增大也就结束了，也得到了一系列树。
再说一种剪枝的方法：
简单粗暴的 错误率降低剪枝
直接拿验证集来怼，如果减值后验证集准确率更低 就剪枝否则不减，真简单粗暴！
