知识卡片
预剪枝与后剪枝的代价
树越深,训练集上的错误越少,但泛化未必更好——分叉过细本质是在记忆噪声。剪枝就是拿一部分训练集上的拟合度,去换测试集上的稳定度。两条路线,代价不同:
| 先剪枝(预剪枝) | 后剪枝 | |
|---|---|---|
| 时机 | 生成过程中就停 | 先生成最大树,再自下而上剪 |
| 手段 | 阈值 ε、最大深度、最小样本数 | 按正则化阈值 α 逐个评估子树 |
| 代价 | 贪心短视:当前增益低的分裂后续可能很有用,容易欠拟合 | 训练成本高,且需要留出验证集 |
实践中用得多的是后剪枝,因为它能看到”整棵子树长完是什么样”再决定砍不砍。CART 把它形式化为代价复杂度:
L(α, T) = L(T) + α|T|
L(T) 是子树在验证集上的误差(分类用基尼、回归用平方误差),|T| 是叶子数,α ≥ 0 权衡精度与复杂度。α=0 时只看精度,偏向大树;α 很大时惩罚项占绝对优势,一路剪到只剩根节点。对每个内部节点 t,令”保留子树”与”剪成单节点”的损失相等,可解出该节点的临界值
α_t = (L(t) − L(T_t)) / (|T_t| − 1)
α 超过 α_t 时,留下这棵子树就不划算了。算法据此自下而上从 α_t 最小的节点开始剪(书中做法是取一个阈值 α_k,一次性剪掉所有 α_t ≤ α_k 的节点),每剪一轮得到一棵新子树,最终形成一串嵌套子树 {T0, T1, …, TK},再用验证集交叉验证挑出最优的那棵。
这解释了为什么剪枝强度由 α 一个数控制:α 是”每多一个叶子要付多少代价”的单价,单价越高树越小。也解释了后剪枝比先剪枝稳的原因——先剪枝在信息不全时就得决定,后剪枝在信息完整后按同一把尺子统一衡量。
结构图:
flowchart TD
A[训练集长成最大树T] --> B[自下而上算各内部节点的αt]
B --> C[剪掉α最小的子树 得Tk]
C --> D[加入候选子树集合W]
D --> E{还有节点可剪?}
E -->|是| B
E -->|否| F[验证集比较各子树误差]
F --> G[选误差最小的Tα]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 第06章 决策树
原书出处 · 1 处
- 第6章 决策树 6.4 决策树的剪枝 · 查看原书依据
剪枝有先剪枝和后剪枝两种,先剪枝是在生成决策树的过程中就采取一定措施来限制某些不必要的子树的生成(比如前面在C4.5决策树的生成过程中设置一个阈值,当小于阈值时就不再分叉子树了)。后剪枝就是先使用训练集中的大部分数据去尽可能生成一棵最大的树,然后从决策树的底端开始不断剪枝
参考来源
- 位置:《机器学习基础:从入门到求职》第6章《决策树》(源文件:extracted/机器学习基础:从入门到求职/_epub-src/OEBPS/text00009.html)
- 结论依据:原文区分先剪枝(生成中设阈值限制分叉)与后剪枝(先长最大树再自底向上剪、用余下数据交叉验证选最优),并给出 L(α,T)=L(T)+α|T|、α 的均衡作用及六步剪枝流程。
- 原始内容:剪枝有先剪枝和后剪枝两种,先剪枝是在生成决策树的过程中就采取一定措施来限制某些不必要的子树的生成(比如前面在C4.5决策树的生成过程中设置一个阈值,当小于阈值时就不再分叉子树了)。后剪枝就是先使用训练集中的大部分数据去尽可能生成一棵最大的树,然后从决策树的底端开始不断剪枝