回归树的剪枝算法 (Regression Tree Prunin

作者: 数科每日 | 来源:发表于2021-02-24 11:54 被阅读0次

回归树的剪枝算法 (Regression Tree Prunin
CART树
机器学习之CART4决策树（classification and
决策树、随机森林、GBDT
ML 监督学习回归树回归
机器学习 - 决策树算法[二]
分类回归树 ( CART)
回归树
机器学习实战——回归树
深入浅出学AI：第二章机器学习一览

本文介绍的剪枝算法是 Cost Complexity Pruning 又叫 Weakest Link Pruning. 本文介绍的是关于连续型变量的回归树的 Pruning 算法，但是对于离散型变量，以及 Classification Tree 只要将相关指标进行替代即可

SSR

SSR : Sum of Square Residual
$SSR = \sum_{j=1}^{J} \sum_{i \in R_{j}}\left(y_{i}-\hat{y}_{R_{j}}\right)^{2}$

$J$ : 假设一棵树有 $J$ 个分支。
$y_{i}$ : 第 i 个observation 的 reponse 值。
$\hat{y}_{R_{j}}$ 在第j 个分支上，所有预测值的均值。

SSR 是计算一棵树的数据预测能力的指标，它代表了一棵树对于所有数据预测值与实际值只差。 SSR 越大树的预测错误越大。

SSR 会随着树变深而减少，而且是单调减少。如果以SSR 为Cost Fucntion 就会导致树为每个 Observation 划分一个branch，那么整个模型就会走向过拟合

Tree Scroe

在SSR 基础上，派生出 Tree Scroe ，用来给一棵树打分
$\sum_{m=1}^{|T|} \sum_{i: x_{i} \in R_{m}}\left(y_{i}-\hat{y}_{R_{m}}\right)^{2}+\alpha|T|$
也就是
$Tree Scroe = SSR+\alpha|T|$
其中

$\alpha$ 一个超参数，取值为 0 - $\infty$
T 是这棵树的节点个数

其中 $\alpha$ 类似惩罚项，当 $\alpha$ 很大的时候，就会迫使一个树只留下根节点，而 $\alpha$ 为0的时候，树越深Tree Scroe 就会越高。

剪枝算法

1. 获得可选 $\alpha$ 集合

使用数据为所有的 Training Data
从 $\alpha=0$ 开始（ $\alpha_{0}$ ），构建出一个最深的树 $T_{0}$ 。然后不断增加 $\alpha$ 的值。随着 $\alpha$ 增加， $\alpha|T|$ 也会增加，在 $\alpha$ 等于一个值的时候，会出现一个比较浅的树 $T_{1}$ ，它的 $Tree Score_{T_{1}} < Tree Score_{T_{0}}$ , 那么就把此时的 $\alpha$ 记为 $\alpha_{1}$ 。不断提高 $\alpha$ 的值，直到只剩下一个树根。如果 $T_{0}$ 有 $j$ 个节点，此时，我们就可以得到 $j$ 颗树和每棵树对应的 $\alpha$ 。这 $j$ 个 $\alpha$ 的集合，记为 $A$ 。

2. Cross Validation

将Training Data 进行 $K$ Fold Cross Validation拆分。在每次使用中，就得到一个新的数据集合

新训练集合，由 $K-1$ 个fold 的数据组成
新测试集合，由 $1$ 个fold 的数据组成

2.1 用 $A$ 中每个 $\alpha$ 训练树，并获得其SSR

对于 $K$ Fold Cross Validation，每个Fold 都进行如下操作

利用 “新训练集合”的数据，以及 $A$ 中的 $j$ 个 $\alpha$ ，来获得 $j$ 颗树。
利用 “新测试集合” 测试本轮中 $j$ 颗树的 SSR（注意，不是 Tree Score）
找到一个SSR 最低的树，并记录其 $\alpha$

2.2 选出一个最好的 $\alpha$

步骤 2.1 会执行 $K$ 次，并获得 $K$ 个 $\alpha$ （可能有重复）。表现最好（重复次数）最多的 $\alpha$ ，将其定为最终的 $\alpha_{final}$ 。

3. 获得最终的Tree

将第1步中产生的 $j$ 颗树中，对应 $\alpha_{final}$ 的树定位 Final Model

总结

算法主要分如下几步：

利用 Tree Scroe 选出有限个不同的 $\alpha$
利用 Cross Validation 和 SSR 从有限个 $\alpha$ 中选出最优的 $\alpha_{final}$
找到 $\alpha_{final}$ 对应的树，为最终的模型

参考资料

https://www.youtube.com/watch?v=D0efHEJsfHo
An Introduction to Statistical Learning

回归树的剪枝算法 (Regression Tree Prunin
本文介绍的剪枝算法是 Cost Complexity Pruning 又叫 Weakest Link Prunin...
CART树
CART（classification and regression tree）算法是分类回归树算法，它是决策树的...
机器学习之CART4决策树（classification and
注意：后面补充ID3树步骤：生成决策树 - 剪枝 - 选择最优树 regression tree（continu...
决策树、随机森林、GBDT
概念决策树(Decision Tree)分为两大类，回归树(Regression Decision Tree)和...
ML 监督学习回归树回归
Scikit-Learn用分裂回归树（Classification And Regression Tree，简称 ...
机器学习 - 决策树算法[二]
1. CART决策树分类与回归树（classification and regression tree, CAR...
分类回归树 ( CART)
分类回归树 (classification and regression tree, CART) 。既可以用于创建...
回归树
传送门：分类树 1、原理分类与回归树（classification and regression tree，CA...
机器学习实战——回归树
CART算法 — DONE 回归与模型树 — DONE 树剪枝算法 — DONE Python中GUI的使用【C...
深入浅出学AI：第二章机器学习一览
一、按照算法类型分类 1.回归算法(Regression) 线性回归(Linear Regression or S...

回归树的剪枝算法 (Regression Tree Prunin

SSR

Tree Scroe