CART剪枝详解

CART之剪枝详解

我们这里用的是代价复杂度剪枝算法。

首先我们将一颗充分生长的树称为T0 ，我们希望减少树的大小来防止过拟化，但又担心去掉一些节点后预测的误差会增大，那么如何达到这两个变量之间的平衡则是问题的关键，因此我们用一个变量α 来平衡，因此损失函数定义为如下：

Cα(T)=C(T)+α|T|" role="presentation">Cα(T)=C(T)+α|T|

T为任意子树，C(T)为预测误差，可以是平方误差也可以是基尼指数，|T|为子树T的叶子节点个数，注意是叶子节点， α" role="presentation">α 是参数，C(T)衡量训练数据的拟合程度，|T|衡量树的复杂度（即大小）， α" role="presentation">α 权衡拟合程度与树的复杂度。

那么我们如何找到这个合适的α来使拟合程度与复杂度之间达到最好的平衡呢，最好的办法就是，我们将α从0取到正无穷，对于每一个固定的α，我们都可以找到使得Cα(T)最小的最优子树T(α) 。当α 很小的时候，T0 是这样的最优子树，当α 很大的时候，单独一个根节点是这样的最优的子树。

尽管α 取值无限多，但是T0 的子树是有限个，因此我们可以生成这样一个子树序列