|
|
相关文章推荐
|
文质彬彬的创口贴 · 说唱风格代表人物:匪帮放克- 歌单- 网易云音乐· 2 月前 · |
|
|
博学的煎饼 · 免费国际智商测试(图形版) 30题- ...· 5 月前 · |
|
|
欢快的领带 · 中关村科技园区管理委员会高精尖产业量子纠缠研 ...· 1 年前 · |
集成学习的系列博客：
- 集成学习（ensemble learning）基础知识
- 随机森林（random forest）
- AdaBoost算法（一）——基础知识篇
- AdaBoost算法（二）——理论推导篇
- 梯度提升决策树（Gradient Boosting Decision Tree，GBDT）
今天来讲一讲GBDT，GBDT的名声如雷贯耳，早在深度学习没火之前，集成学习大行其道的时候，GBDT无论是在机器学习比赛中，还是在工业界（尤其CTR预估）都被广泛使用，因为其优秀的性能。GBDT的改进如陈天奇的XGBoost和微软的LightGBM不仅性能优秀，尤其计算速度相比较原始的GBDT有巨大的提升，这两个算法都有现成的python库提供，当我们使用的时候可以调用，sklearn中也封装了基本的GBDT模型，想用也可以直接调用。
这篇博客想粗浅的讲下GBDT，只讲回归，虽然GBDT也可以用于分类，但貌似工业界回归用的多一些。首先GBDT是boosting算法中的一种，因此学习GBDT需要的前验知识有：
- Boosting这一类算法思想
- 分类与回归树（CART）回归部分
- 提升树
1、关于Boosting这一类算法思想倒也简单，因为博客
集成学习（ensemble learning）基础知识
已经讲得很清楚了，这里不再累述，不清楚的请移步这篇博客。
2、分类与回归树（CART）回归部分，我的博客
分类与回归树（classification and regression tree，CART）之回归
也有详细的讲解，因此，这里也不太讲解，不清楚的请移步。因为GBDT中的决策树通常都是CART。
实际上GBDT和AdaBoost的主要区别就在于AdaBoost是在每一次迭代中修改样本权重来使得后一次的树模型更加关注被分错的样本，而GBDT则是后一次树模型直接去拟合残差。这篇博客主要讲解的内容有：
- 提升树算法
- 梯度提升树算法
- GBDT的优缺点
- GBDT的改进算法
一、提升树算法
在前面介绍AdaBoost的时候，讲了提升方法实际上就是加法模型和前向分布法。提升树算法那也采用前向分步法，首先初始提升树
\hat{\Theta}_m = \arg\min_{\Theta_m}\sum_{i=1}^{N}L(y_i, f_{m-1}(x_i) + T(x_i;\Theta_m))\tag{2}
Θ
^
m
=
ar
g
Θ
m
min
i
=
1
∑
N
L
(
y
i
,
f
m
−
1
(
x
i
)
+
T
(
x
i
;
Θ
m
)
)
(
2
)
对于提升树而言，分类问题使用的损失函数是指数函数，回归问题使用的是均方误差。我们这里主要回归问题。
对于一个训练集
\begin{aligned} L(y, f_{m-1}(x) + T(x;\Theta_m)) &= [y-f_{m-1}(x) - T(x;\Theta_m)]^2 \\ &= [r - T(x;\Theta_m)]^2 \tag{5} \end{aligned}
L
(
y
,
f
m
−
1
(
x
)
+
T
(
x
;
Θ
m
)
)
=
[
y
−
f
m
−
1
(
x
)
−
T
(
x
;
Θ
m
)
]
2
=
[
r
−
T
(
x
;
Θ
m
)
]
2
(
5
)
其中，
r
=
y
−
f
m
−
1
(
x
)
为当前模型拟合数据的残差，也就是说对回归问题的提升树而言，下一次迭代中模型只需要拟合当前模型的残差即可。上面说了这么一堆，直接来看提升树的算法吧，可能更清晰点。
下面直接上例子，一直觉得举例子是最容易让人懂得，文字描述太扯淡，又不是写论文，搞这些形式化的文字意义不大。
数据集为（摘自李航《统计学习方法》,注，李航的书并未给出特征，只给出了x的取值范围，我这里把它给的切分点设置成了特征，这样最后结果保持不变）：
| 样本编号 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
m
(
9
.
5
)
=
1
5
.
7
4
把上面的误差放到一张表里，看的更清晰点。
能够看出当切分点为6.5时，误差最小，所以6.5为最优切分点。此时 y i |
5.56 | 5.70 | 5.91 | 6.40 | 6.80 | 7.05 | 8.90 | 8.70 | 9.00 | 9.05 | ||||||||||||||||||||
| 残差 | -0.68 | -0.54 | -0.33 | 0.16 | 0.56 | 0.81 | -0.01 | -0.21 | 0.09 | 0.14 |
此时，损失（均方误差）为：
T_2(x)=\left\{\begin{matrix} -0.52 & x\leq3.5\\ 0.22 & x>3.5 \end{matrix}\right.
T
2
(
x
)
=
{
−
0
.
5
2
0
.
2
2
x
≤
3
.
5
x
>
3
.
5
则，树模型
f_2(x) = f_1(x) + T_2(x)=\left\{\begin{matrix} 5.72 & x\leq3.5\\ 6.46 & 3.5 < x \leq 6.5 \\ 9.13 & x > 6.5 \end{matrix}\right.
f
2
(
x
)
=
f
1
(
x
)
+
T
2
(
x
)
=
⎩
⎨
⎧
5
.
7
2
6
.
4
6
9
.
1
3
x
≤
3
.
5
3
.
5
<
x
≤
6
.
5
x
>
6
.
5
注意看下分段函数的相加。
用
T_3(x)=\left\{\begin{matrix} 0.15 & x\leq6.5\\ -0.22 & x>6.5 \end{matrix}\right.
T
3
(
x
)
=
{
0
.
1
5
−
0
.
2
2
x
≤
6
.
5
x
>
6
.
5
f_3(x) = f_2(x) + T_3(x)=\left\{\begin{matrix} 5.87 & x\leq3.5\\ 6.61 & 3.5 < x \leq 6.5 \\ 8.91 & x > 6.5 \end{matrix}\right.
f
3
(
x
)
=
f
2
(
x
)
+
T
3
(
x
)
=
⎩
⎨
⎧
5
.
8
7
6
.
6
1
8
.
9
1
x
≤
3
.
5
3
.
5
<
x
≤
6
.
5
x
>
6
.
5
loss为：
T_4(x)=\left\{\begin{matrix} -0.16 & x\leq4.5\\ 0.11 & x>4.5 \end{matrix}\right.
T
4
(
x
)
=
{
−
0
.
1
6
0
.
1
1
x
≤
4
.
5
x
>
4
.
5
f_4(x) = f_3(x) + T_4(x)=\left\{\begin{matrix} 5.71 & x\leq3.5\\ 6.45 & 3.5 < x \leq 4.5 \\ 6.72 & 4.5 < x \leq 6.5 \\ 9.02 & x > 6.5 \end{matrix}\right.
f
4
(
x
)
=
f
3
(
x
)
+
T
4
(
x
)
=
⎩
⎪
⎪
⎨
⎪
⎪
⎧
5
.
7
1
6
.
4
5
6
.
7
2
9
.
0
2
x
≤
3
.
5
3
.
5
<
x
≤
4
.
5
4
.
5
<
x
≤
6
.
5
x
>
6
.
5
loss为：
T_5(x)=\left\{\begin{matrix} 0.07 & x\leq6.5\\ -0.11 & x>6.5 \end{matrix}\right.
T
5
(
x
)
=
{
0
.
0
7
−
0
.
1
1
x
≤
6
.
5
x
>
6
.
5
f_5(x) = f_4(x) + T_5(x)=\left\{\begin{matrix} 5.78 & x\leq3.5\\ 6.52 & 3.5 < x \leq 4.5 \\ 6.79 & 4.5 < x \leq 6.5 \\ 8.91 & x > 6.5 \end{matrix}\right.
f
5
(
x
)
=
f
4
(
x
)
+
T
5
(
x
)
=
⎩
⎪
⎪
⎨
⎪
⎪
⎧
5
.
7
8
6
.
5
2
6
.
7
9
8
.
9
1
x