这里我就简单讲下CART剪枝的核心思想，纯属个人意见，如有不当，请指正。
在《统计学习方法法》中已经提到了决策树的剪枝算法了，理所当然，我们是顺着书中提到的思路来理解下决策树剪枝的关键步骤。我们定义了
该定义表示了决策树的损失函数。whaterver它是什么，现在有了损失函数这个衡量标准，并且假设我们已经根据training set生成了一棵复杂的决策树，且参数
已知。算法该如何实现决策树的剪枝呢？
首先明确一个概念，原本躺在那的一堆数据集，在没有决策规则被挖掘时，我们只能知道数据集中的分类标签的情况。如银行贷款问题中，银行只知道有多少人可以贷款，有多少人不可以贷款，所以躺在那的数据集的不确定度是最高的。关于这部分的理解可以参看博文【决策树之理解ID3算法和C4.5算法 - Demon-初来驾到 - 博客频道 - CSDN.NET】，由此决策树越复杂，整体数据的不确定度越低。（数据被规则所明确，即银行在得知用户有房子的情况下，能根据训练数据统计出所有用户都是可以贷款的，这样的规则被银行挖掘出来了。）那么，显而易见，规则越多，数据分类的不确定性将大大降低。
咱们来看看决策树损失函数的定义。其中第一部分
就是事物的不确定性次数。我们都知道存在噪声的情况下，模型将趋于复杂。在决策树中也就是
的数值越大。再来看看损失函数中的
，假设参数
已知的，那么复杂的模型，所带来的结果就是
也将增大。且决策树存在过拟合现象，那么为了使得损失函数减小，有两种办法：
- 降低第一部分的不确定次数，但我们知道这是不可能的了，因为降低不确定次数的办法是再找寻一个特征，或者找寻特征的最优切分点。这在生成决策时就已经决定了，无法改变。
- 进行剪枝操作，这是可以的。剪枝最明显地变化就是叶结点个数变少。假设是一个三叉树，那么一次剪枝它的叶结点数减少2个。变化量为 ，有了这变化量，我们就可以用来求解最优决策子树了。
CART树剪枝的操作的理解
因为
参数给定，所以一次剪枝，损失函数的减少量也是固定的。所有子结点都是三叉树时，我们可以简单认为损失函数的减少量为2
。假设只有一个子结点发生剪枝，那么该子结点上的叶结点都将全部归并到该结点，由此我们计算此结点的不确定次数。倘若不确定次数增大的量超过2
，那么剪枝失败，算法将尝试其他子结点。因为新得的子树损失函数反而增大。这从侧面又反映了什么样的事实？该子结点的分类规则是大大降低不确定次数的，并不存在噪声，所以没必要进行剪枝。所以在剪枝过程中，找寻的就是那些噪声点，却被过度规则那些子结点，把这些合并了，万事大吉，自然而然决策树的准确率将上升。
在上述剪枝过程中，还需要注意一个有趣的问题。对应于每一个参数
，剪枝后的子树是唯一的嘛？个人觉得这是一个最基本的前提假设，在算法中，它提到了一点，给定参数
，找寻损失函数最小的子树
，也就是说
是一一对应的！并不存在一个
对应于多个子树。CART剪枝算法中将用到该基本假设。
那么问题来了，参数
给定的？谁来给？领域专家给？这是一种行之有效的办法，但却需要领域知识。理想化的模型都希望参数由data决定，也就是
也由数据决定。那么我们能想到的就是拿测试数据去测试在给定
下生成的子树。如果给定
下，测试数据的准确率达到一定阈值我们就以这个
为准。这就存在一个非常大的问题，
如何变化，才能让测试数据准确率呈现极大值？这个问题在上述算法中并不好解决！
CART剪枝核心思想
刚才的思路是什么？从最宏观的角度去考虑的话，就是利用
生成
。抽象一下，从【无限的实数】中找寻【有限个数的
】，这问题当然不好解决了！思路其实已经出来了，CART剪枝算法的核心思想就是说，一个复杂的决策树，不管多复杂，都能生成有限个数的子树，我们记作
，那么我们只要找寻到对应于每一个子树的
不就可以了嘛！没错，抽象一下，从【有限个数的
】中找寻对应的【
】，万事解决。
咱们先来看看决策树损失函数的定义：
做一些数学变换得：
所以说，衡量损失函数大小的真正贡献在于每个叶结点，叶结点不确定次数的累加并加个常数
就是我们决策树整体的损失函数。
为了得到树T的所有子序列
，我们需要从底自上，每次只进行一次剪枝操作，那么进行剪枝操作后，该子序列应该是当前参数的最优子树。且应该是根据所剪的那个结点来计算参数
。
为什么要这么做？接下来的思路是什么？因为我们刚才说了，是通过最优子树来求解参数
，因此，我们先【假设】我们找到了当前的最优子树，且必然发生剪枝。【注意加黑的这句话！】具体地，需要归并的子结点为t，以t为单结点损失函数就可以表示为：（该子结点t已经成为我们的叶结点咯！在接下来给出的公式中，请思考哪些是已知参数，哪些是未知参数。）
这公式是最初的决策树损失函数变化而来的！它是其中一个子结点【吞并】它的子树，所得到【叶结点后】的损失函数。还需要强调下，因为在最初理解这个C(t)含义时，自己也被搞混了。该公式已经是剪枝完毕后的表达式了，也就是说原先的子结点已经变成了当前的叶结点。接下来会给剪枝前的表达式！
表示在该叶结点中的不确定次数。
那么【剪枝前】是什么情况呢？剪枝前是以t为根结点的子树
的损失函数是：
也就是说，剪枝前该子结点的损失函数如上。具体的含义之前都有解释过，就不再叙述了。接下来我们要明确哪些是已知参数，因为决策树已经生成了，所以每个结点的不确定次数都是知道的，即
,
和
是已知的。未知参数是
如何求解？还记得加粗的假设嘛？
假设1：必然发生剪枝！
从中我们便能求得
，为什么？我们来观察下，上述两个式子。
当
或者充分小，明显地，不确定次数：
决策树叶结点越多，不确定性越低，不解释。
当增大
时，总有那么一个点，能够使得：
当继续增大
时，
不等式反向，所以我们只要取
时，当且仅当
时，剪枝必然发生。
必须满足上述条件，否则前提假设将失去意义。所以说，我们通过假设剪枝必然发生就能找到对应的
。可对于任何一个子结点t都可以嘛？别忘了第二个假设。
假设2：剪枝发生后，当前决策树是我们的最优子树
最优子树？现在t变成了一个变量，因为我们并不知道到底剪枝哪个子结点后决策树是最优的。不急，再来看看，公式：
剪枝已经发生，此时，对应于每一个子结点t会生成不同的
我们记作
，由此得：
剪枝的决策树什么时候最优？对于当前参数
而言，能够找到这样的t，使得
然而在这里为了能够求得
的一个序列，貌似直接最小化了
找的
即找到了子结点t，即完成了剪枝，即找到了最优子树
。有了上述的步骤，为了得到决策树
的所有子序列，直接递归下去，直到根节点即可。在这一过程中，不断地增加
的值，产生新的区间。
后面的思路就很简单了，根据生成的子树序列，用测试集去测试这些子树，谁的测试准确率最高，谁就获胜。具体算法可以参看《统计学习方法》，讲的很详细。
总的来说，CART剪枝算法的核心在于用【有限个子树
】计算【无限个
】，你会发现，计算过程中
变成了一个个分段区间。在利用公式推导时，注意【必剪枝】和【当前最优子树】的两个假设，且时刻问自己【已知参数】和【未知参数】是哪些。