决策树的剪枝

由于生成的决策树会存在过拟合的现象，需要对决策树进行简化，这个过程叫做剪枝。

剪枝可分为：预剪枝 和 后剪枝

预剪枝：基于信息增益准则，找出最佳分支结点时候通过验证集计算这个节点的验证集精度，如果该节点的划分不能提高验证集合的精度，那么这个节点将不允许被划分。预剪枝虽然降低了过拟合的风险，而且减少了训练时间和测试时间的开销，但这样也带来了欠拟合的风险。

后剪枝：对已经生成的决策树做剪枝操作。本章主要讲述后剪枝操作。

其实三种决策树（ID3、C4.5、CART）剪枝过程都相同，只是对当前树的评价标准不一样：信息增益、信息增益率、基尼指数。

---

CART剪枝

剪枝过程：

1.剪枝，形成一个子树序列T0，T1，T2....Tn

2.交叉验证，选最有子树

1.剪枝

决策树的剪枝往往通过极小化决策树整体的损失函数来实现。

在减持过程中指数的损失函数可以定义为。

以r为根的子树：

剪枝前的损失函数：

剪枝后的损失函数

只要令

将内部节点都算一遍，原来的树是R0，R0中剪去最小的Rt，得到R1。

同样在R1中剪去最小的Rt子树，得到R2

重新计算，一直这样剪枝下去，直到根节点

最后得到n个子树：R0，R1，R2......Rn

2.交叉验证，选取最优子树

利用验证数据集，测试各子树R0，R1，R2......Rn的平方误差和基尼指数，平方误差或者基尼指数最小的决策树被认为最优的决策树。

评价函数：