决策树主要通过剪枝策略来对付过拟合, 剪枝有预剪枝和后剪枝两种
预剪枝: 在决策树生成过程中, 对于每个结点在划分前进行评估, 若当前结点的划分不能带来泛化性能的提升, 则停止划分并且将当前结点标记为叶结点
后剪枝: 后剪枝则是先从训练集生成一棵完整的决策树, 自底向上地对非叶结点进行考察, 若对应地子数替换为叶结点时能带来泛化性能的提升, 则将子数替换为叶结点.
剪枝效果的评估主要是通过预留一部分数据作为验证集以进行性能评估.
预剪枝和后剪枝的优缺点:
1. 预剪枝使得决策树的很多分支都没有"展开", 这不仅降低了过拟合的风险, 还显著减少了决策树的训练时间开销和测试时间开销. 但另一方面, 有些分支的当前划分虽不能提升泛化性能, 甚至导致下降, 但是后续的划分可能带来性能的显著提升。但预剪枝会忽略这种情况, 导致欠拟合的风险.
2. 后剪枝通常比预剪枝保留更多的分支, 欠拟合的风险会降低, 泛化性能提升, 但是时间开销大.