CART之剪枝详解
我们这里用的是代价复杂度剪枝算法。
首先我们将一颗充分生长的树称为$T_0$ ，我们希望减少树的大小来防止过拟化，但又担心去掉一些节点后预测的误差会增大，那么如何达到这两个变量之间的平衡则是问题的关键，因此我们用一个变量$\alpha$ 来平衡，因此损失函数定义为如下： T为任意子树，C(T)为预测误差，可以是平方误差也可以是基尼指数，|T|为子树T的叶子节点个数，注意是叶子节点，$\alpha$ 是参数，C(T)衡量训练数据的拟合程度，|T|衡量树的复杂度（即大小），$\alpha$ 权衡拟合程度与树的复杂度。
那么我们如何找到这个合适的$\alpha$来使拟合程度与复杂度之间达到最好的平衡呢，最好的办法就是，我们将$\alpha$从0取到正无穷，对于每一个固定的$\alpha$，我们都可以找到使得$C_{\alpha}(T)$最小的最优子树$T(\alpha)$ 。当$\alpha$ 很小的时候，$T_0$ 是这样的最优子树，当$\alpha$ 很大的时候，单独一个根节点是这样的最优的子树。
尽管$\alpha$ 取值无限多，但是$T_0$ 的子树是有限个，因此我们可以生成这样一个子树序列 $T_n$ 是最后剩下的那个根节点。（这里的子树生成是根据前一个子树$T_i$ ，剪掉某一个内部节点，生成$T_{i+1}$）然后对这样的子树序列分别用测试集进行交叉验证，找到最优的那个子树作为我们的决策树。
高能预警：(这里不注意的话，后面会有很大的疑惑)
Breiman证明：将$\alpha$ 从小增大，$0=\alpha_0<\alpha_0<…<\alpha_n<+\infty$ ，在每个区间$[\alpha_i,\alpha_{i+1})$ 中，子树$T_i$ 是这个区间里最优的。
这也是代价复杂度剪枝的核心思想。
基于上面的论述，剪枝可分为两部分，第一部分生成子树序列，第二部分交叉验证。
1. 生成子树序列
我们每次剪枝剪的都是某个内部节点的子节点，也就是将某个内部节点的所有子节点回退到这个内部节点里，并将这个内部节点作为叶子节点。因此在计算整体的损失函数时，这个内部节点以外的值都没变，只有这个内部节点的局部损失函数改变了，因此我们本需要计算全局的损失函数，但现在只需要计算内部节点剪枝前和剪枝后的损失函数。
对任意内部节点t，
剪枝前的状态：有$\mid T_t\mid$ 个叶子节点，预测误差是$C(T_t)$
剪枝后的状态：只有本身一个叶子节点，预测误差是$C(t)$
因此剪枝前的以t节点为根节点的子树的损失函数是 剪枝后的损失函数是 易得，一定存在一个$\alpha$ 使得$C_{\alpha}(T_t)=C_{\alpha}(t)$ ，这个值为 这个$\alpha$ 的值有什么意义，刚才我们高能预警的地方，$0=\alpha_0<\alpha_1<…<\alpha_n<+\infty$ ，在每个区间$[\alpha_i,\alpha_{i+1})$ 中，子树$T_i$ 是这个区间里最优的。为什么呢？原因就在刚才的推导，对于当前这个节点，只要$\alpha$ 大于这个值时，一定有$C_{\alpha}(t)<C_{\alpha}(T_t)$ ，也就是剪掉这个节点后都比不剪要更优。所以每个最优子树对应的是一个区间，在这个区间内都是最优的。
然后我们对$T_i$ 中的每个内部节点t都计算 (注意这里的t是变量，上面推$\alpha$ 时是针对一个特定的t，也就是t是常量。)
书上说g(t)表示剪枝后整体损失函数减少的程度，然后剪去g(t)最小的$T_t$.
当初这是非常困扰我的一个地方，1.为什么代表整体损失函数减少的程度。2.既然代表减少的程度，为什么剪去g(t)最小的$T_t$ ，而不是剪去g(t)最大的$T_t$ 。3.或者剪去$(C(t)+\alpha)$ 最小的$T_t$.
- 1.首先针对第一个问题
我承认我到现在也没弄懂，我觉得写的有问题或者有歧义？我觉得把它解释成误差减小率 更合适，我觉得它是衡量叶子节点增加的值不值的一个标准。首先分子是误差减小的量，如果我们单一的看误差见效的量有可能会有失偏颇，因为你可能是增加了很多很多的叶子节点才换来的这么一点误差的减小量，因此我们除以增加的叶子节点数，来代表每个叶子节点带来的误差减小量。
- 2.为什么剪去g(t)最小的$T_t$
如刚才说的g(t)代表每个叶子节点带来的误差减小量，如果g(t)越小，也就是增加叶子带来的误差减小量越小，也就是增加这个叶子节点的作用越小，花那么大的功夫增加叶子节点，误差才减小那么一点点，还不如不要，因此优先剪去g(t)最小的t
- 3.为什么不剪去$(C(t)+\alpha)$ 最小的$T_t$.
考虑过这个问题的说明有一定思考了。对当前的$T_i$ ，我们如果希望损失函数最小的话，应该是剪去损失函数最小的那个内部节点啊，这样的话损失函数才会最小嘛。
但是上面那句话真的对嘛？
整体损失函数 = 内部节点t的损失函数 + 其他节点的损失函数和
如果我们剪去的损失函数最小的那个内部节点，那么等号右边第一项是最小了，那第二项呢？所以提出的疑问也就不成立了。
进一步，为什么会让人产生这样的疑问呢？我觉得主要是没弄明白节点t是常量还是变量。
在计算$\alpha$ 时，节点t是常量，也就是只考虑这一个节点，当$\alpha>g(t)$ 时，剪掉会使整体损失函数减小，但跟整体损失函数是否是最小没有关系。考虑我们一开始说的因此在计算整体的损失函数时，这个内部节点以外的值都没变，只有这个内部节点的局部损失函数改变了，因此我们本需要计算全局的损失函数，但现在只需要计算内部节点剪枝前和剪枝后的损失函数。 这个只跟能否使整体损失函数减小有关，与整体损失函数能否达到最小无关。
2. 交叉验证
用交叉验证法在子树序列中选取最优子树。
