33.3K
8354
剪枝
在决策树学习过程中，为了尽可能正确分类训练样本，结点划分过程将不断重复，有时会造成决策树分支过多，从而把训练集自身的一些特点当作所有数据都具有的一般性质，即出现过拟合。剪枝是主动去掉一些分支来降低过拟合的风险，是决策树学习算法对付过拟合的主要手段。只有少量问题有此类算法。
决策树剪枝的基本策略有预剪枝（prepruning）和后剪枝（postpruning）。预剪枝是指在决策树生成过程中，对每个结点在划分前先进行估计，若当前结点的划分不能带来决策树泛化性能提升，则停止划分并将当前结点标记为叶结点。后剪枝则是先从训练集生成一棵完整的决策树，然后自底向上地对非叶结点进行考察，若将此结点对应的子树替换为叶结点能够带来决策树泛化能力的提升，则将此树替换为叶结点。常用的后剪枝策略包括：降低错误剪枝(reduced error pruning，REP)、悲观错误剪枝(pessimistic error pruning，PEP)、基于错误剪枝(error based pruning，EBP)、代价复杂度剪枝(cost complexity pruning，CCP)和最小错误剪枝(minimum error pruning，MEP)等。
通常后剪枝决策树比预剪枝决策树保留更多的分支。在一般情形下，后剪枝决策树的欠拟合风险很小，其泛化性能往往优于预剪枝决策树。但是，后剪枝过程是在生成完整决策树之后进行的，并且要自底向上地对树中的所有非叶结点进行逐一考察，因此其训练时间开销比未剪枝决策树和预剪枝决策树都要大得多。
