决策树剪枝

剪枝是决策树的结构化正则, 在“拟合训练集”与“模型复杂度”之间显式权衡。代价复杂度 (cost-complexity): $R_\alpha(T) = R(T) + \alpha |T|$, 其中 $R(T)$ 是经验风险 — 分类: 叶子误分类率加权和 $R(T) = \sum_{t \in \text{leaves}(T)} \frac{|D_t|}{|D|} \cdot \text{err}(t)$($\text{err}(t)$ 为叶子 $t$ 内多数类错误比例), 回归: 叶子 MSE 加权和; $|T|$ 是叶子数, $\alpha \geq 0$ 是每片叶子的复杂度惩罚。预剪枝: 分裂前先评估, 若本次分裂不能让验证集误差下降 (或样本量低于阈值/深度超限) 就停止生长; 后剪枝 (CART 代价复杂度剪枝): 先生成完整树, 再自底向上考察内部节点 $t$ — 把子树 $T_t$ 换成单叶子 $t$ 时, 代价从 $R(T_t) + \alpha |T_t|$ 变为 $R(t) + \alpha$, 两边相等解出临界 $\alpha = \frac{R(t) - R(T_t)}{|T_t| - 1}$: 当 $\alpha$ 大于该临界值时剪枝后 $R_\alpha$ 更小, 应该剪。CART 从 $\alpha = 0$ 起逐步挑临界 $\alpha$ 最小的节点逐个剪掉 (最弱连接 weakest-link 剪枝), 得到嵌套子树序列 $T_0 \supset T_1 \supset \cdots \supset T_k$, 最后用验证集 (或交叉验证) 选 $R(T_i)$ 最小的树, 即选定 $\alpha^*$。C4.5 用悲观剪枝: 用加连续性校正的经验误差 $R_{pe}(t) = \frac{\text{err}(t) + \frac{|T_t|}{2}}{|D_t|}$ 判断是否值得剪。

“树过拟合怎么办”“max_depth / min_samples_leaf 与 $\alpha$ 的关系”类高频题; 也是理解 XGBoost 的 $\gamma$ (最小分裂增益, 与后剪枝同效)、随机森林“不剪枝靠随机化”的桥梁。

不剪枝的完整树能在训练集上误差归零但方差极大 — 预剪枝边建边停、时间高效, 但有“短视”风险 (当前无增益的分裂可能为更深层带来大增益, 提前停止易欠拟合); 后剪枝先看全局再剪、泛化通常更好, 但先建后剪计算代价高。代价复杂度剪枝把“选树”变成“选 $\alpha$”的一维问题: 候选子树数从指数级压缩到 $|T| + 1$ 个嵌套序列, 一次交叉验证即可确定 $\alpha^*$, 是偏差-方差权衡在树上的标准答案。

白板推导代价复杂度 $R_\alpha(T) = R(T) + \alpha |T|$: 各符号含义; $\alpha$ 增大时最优子树如何变化?

临界剪枝条件推导: 为什么内部节点 $t$ 当且仅当 $\frac{R(t) - R(T_t)}{|T_t| - 1} \leq \alpha$ 时剪成叶子?

预剪枝 vs 后剪枝: 时间开销、过拟合/欠拟合风险、泛化能力对比

CART 最弱连接剪枝流程: 如何生成嵌套子树序列 $T_0 \supset T_1 \supset \cdots$? 如何用交叉验证选 $\alpha^*$?

剪枝对偏差-方差的影响; 与 XGBoost 的 $\gamma$、max_depth、min_samples_leaf 的关系