成本复杂度剪枝：最弱连接和子树序列

参考

• James、Witten、Hastie、Tibshirani：An Introduction to Statistical Learning（第 2 版）8.1 决策树的基础
• Breiman、Friedman、Olshen、Stone：Classification and Regression Trees（1984）第 3 章 最弱连接剪枝
• Hastie、Tibshirani、Friedman：The Elements of Statistical Learning（第 2 版）9.2 Tree-based methods

覆盖的考试公式

• SML-005成本复杂度剪枝SRMPAMAS-II

公式条目按精算考试的公式表整理，编号和中文名是平台自己的。

这个方法算什么

长一棵大树，按最弱连接算出剪枝的序列：每一步剪掉 g(t) = (R(t) − R(T_t)) / (|T_t| − 1) 最小的内部节点，得到 α_1 < α_2 < … 和嵌套的子树。对给定的 α 列出每棵子树的代价 R(T) + α|T|，标出最小的那棵。

说明和限制

• R(t) 是节点 t 作叶子时的风险（回归树是残差平方和，车险频率是泊松偏差），T_t 是以 t 为根的子树。
• 同一个 α 下几个节点的 g(t) 相等时一起剪掉。α 从 α_k 到 α_{k+1} 之间，最优的子树都是 T_k（Breiman 等 1984 定理 3.10）。
• 这里只算剪枝的序列。用交叉验证选 α 见 statistical_learning.regression_tree。

数据

看参数里选的数据：选平台的数据集时是真实数据或公开样例，填自己的数时只用输入的数。上面运行的输出里写明这一次用的是哪种。

开源库和版本

• numpy2.4.6BSD-3-Clause数值计算