本节主要补充决策树的剪枝算法。
十分钟 机器学习 统计学习方法 李航 第二版 之《决策树：一棵有理想的树》_哔哩哔哩_bilibili
这个老师讲的很好，自己看书不好理解，也完全可以看这个老师的讲解视频。
文章目录
前言
一、剪枝简介
1.预剪枝
2.后剪枝
二、预剪枝的方法
1.限制决策树的深度。
2.设定一个阈值。
3.设置某个指标，比较结点划分前后的泛化能力。
二、后剪枝的方法
1.降低错误剪枝（REP）
2.悲观错误剪枝（PEP）
3.最小误差剪枝（MEP）
4.基于错误的剪枝（EBP）
5.代价-复杂度剪枝（CCP）
总结
前言
决策树生成算法递归的生成决策树，直到不能继续划分为止。这样产生的决策树往往对训练数据的分类很准确，但对于未知的测试数据往往不是很准确，即出现过拟合现象。过拟合的原因往往是在学习过程中一味的追求对训练数据的正确分类，从而构建出过于复杂的决策树，所以为了减少模型的复杂度，对决策树进行剪枝。
一、剪枝简介
一棵优秀的决策树：
在具有好的拟合和泛化能力的同时：
- 深度小
- 叶节点少
- 深度小叶节点少
剪枝就是处理决策树的过拟合问题。
1.预剪枝
生成过程中，对每个结点划分前进行估计，若当前结点的划分不能提升泛化能力，则停止划分，记当前结点为叶节点。
2.后剪枝
生成一棵完整的决策树之后，自底而上地对内部结点考察，若此内部结点变为叶结点，可以提升泛化能力，则做此替换。
二、预剪枝的方法
1.限制决策树的深度。
很简单，暴力的方法，通过限制决策树的高度限制决策树的复杂度。当达到所限制的深度挑选划分出的子集中最多类别的分类作为叶节点的分类。
2.设定一个阈值。
阈值在决策树的生成算法中已经提到了，这里有更详细的算法流程，以便更好的理解。
3.设置某个指标，比较结点划分前后的泛化能力。
比如说测试集上的误差率作为指标，如果将该节点进行划分，所在测试集的误差率减小，说明模型的泛化能力得到提升，则将此节点划分，否则不进行划分。
这种方法其实就是使用测试集对训练模型来进行约束。
二、后剪枝的方法
1.降低错误剪枝（REP）
原理：自下而上，使用测试集来剪枝。对每个结点，计算剪枝前和剪枝后的误判个数，若是剪枝有利于减少误判（包括相等的情况），则剪掉该结点所在分支。
经过训练集学习后完整的树。
可以看到当剪枝前的决策树对测试集的误判个数为2，而剪枝后误判个数为1，故替换。
如此反复自底而上进行上述步骤最后得到经过降低错误剪枝法得到的决策树为：
降低错误剪枝的优缺点：
- 计算复杂性是线性的
- 操作简单，容易理解
- 受测试集影响大，如果测试集比训练集小很多，会限制分类的精度。
2.悲观错误剪枝（PEP）
原理：根据剪枝前后的错误率来决定是否剪枝。和REP不同之处在于，PEP只需要训练集即可，不需要验证集，并且PEP是自上而下剪枝的。
3.最小误差剪枝（MEP）
原理：根据剪枝前后的最小分类错误概率来决定是否剪枝。自下而上剪枝，只需要训练集即可。
4.基于错误的剪枝（EBP）
原理：根据剪枝前后的误判个数来决定是否剪枝。自下而上剪枝，只需要训练集即可。
5.代价-复杂度剪枝（CCP）
原理：根据剪枝前后的损失函数来决定是否剪枝。这种方法就是统计学习方法中运用的方法。
总结
本节主要对决策树的剪枝进行补充，这部分的确有点难记住，用到了在回来看一下就可以了。
