机器学习

一颗完全生长的决策树会面临一个很严重的问题，就是过拟合问题，解决过拟合问题我们就要降低模型复杂度，对决策树进行剪枝，提升模型的泛化能力。

决策树的剪枝通常有两种方法，预剪枝和后剪枝。预剪枝，在生成决策树的过程中提前停止树的增长，后剪枝，在已生成的过拟合的决策树上进行剪枝，得到简化版本的剪枝决策树。

预剪枝的核心思想是在树中结点进行扩展之前，先计算当前的划分是否能够带来模型泛化能力的提升，如果不能，则不再进行生长子树。此时可能存在不同类别的样本同时存在于结点中，按照多数投票的原则判断该结点所属类别，预剪枝对于何时停止决策树的生长有以下几种方法：

1 当树达到一定深度的时候，停止树的生长。

2 当到达当前结点的样本数量小于某个阈值的时候，停止树的生长。

3 计算每次分裂对测试集的准确度提升，当小于某个阈值的时候，不再继续扩展。

预剪枝具有思想直接，算法简单，效率高效等特点，适合解决大规模问题，但是如何准确的估计何时停止树的生长，针对不同的问题会有很大的差别，需要一定的经验判断。而且预剪枝存在一定的局限性，有欠拟合的风险，虽然当前的划分会导致测试集准确率降低，但在之后的划分中，准确率有可能会有显著的上升。

后剪枝的核心思想是让算法生成一颗完全生长的决策树，然后从最底层向上计算是否剪枝。剪枝过程将子树删除，用一个叶子结点替代该结点的类别同一按照多数投票的原则进行判断，同样地，后剪枝也可以通过在测试集上的准确率进行判断，如果剪枝过后准确率有所提升，则进行剪枝，相比于预剪枝，后剪枝方法通常可以得到泛化能力更强的决策树，但是时间开销会更大。

常见的后剪枝方法有错误率降低剪枝，悲观剪枝，代价复杂度剪枝，最小误差剪枝，CVP，OOP等方法，这些剪枝方法各有利弊，关注不同的优化角度。

剪枝过程在决策树模型中占有及其重要的位置，很多研究表明剪枝比树的生成过程更为关键，对于不同划分标准生成的过拟合决策树，在经过剪枝之后都能保留最重要的属性划分，因此最终的性能差距并不大。理解剪枝方法的理论，在实际应用中根据不同的数据类型，规模决定使用何种决策树以及对应的剪枝策略，灵活变通，找到最优解决方案。