决策树剪枝

为何要剪枝

决策树递归地构建树，直到不能继续分裂下去为止，这样的树对于训练集可能拟合的较好，但对于训练集可能产生过拟合现象，原因是过多的考虑对训练集的划分精确度，从而构建出了复杂的决策树，缓解过拟合的方法是通过剪枝。

剪枝的思想

剪枝是通过极小化决策树整体的损失函数或代价函数来实现的

剪枝的过程即在构建新的模型，因此，可以将剪枝看作是模型选择的一种方法。

预剪枝

通过提前停止树的构造来对决策树进行剪枝
一旦停止该节点下树的继续构造，该节点就成了叶节点
该叶节点持有其数据集中样本最多的类或者其概率分布。

后剪枝

先构建完整的决策树，允许决策树过度拟合训练数据。
然后对那些置信度不够的节点的子树用叶节点来替代
该叶节点持有其子树的数据集中样本最多的类或者其概率分布。

后剪枝CCP

目前在CART、gbdt等集成树模型中的剪枝方法是后剪枝，重点关注CCP剪枝的流程。

计算时，之所以选择min(a, g(t))是因为a=g(t)，同时g(t)又表达每一个叶节点能带来的误差减小量，那么每次迭代选择误差减少量最少的那一个进行剪枝，因为误差减少量很少，则代表决策树此时没必要花力气向下生长。

转载注明：https://www.jianshu.com/p/ff73374ebe6a