Gradient Boosting Decision Tree

作者: Acapella_Zhang | 来源:发表于2019-04-05 11:29 被阅读0次

概述

GBDT全称Gradient Boosting Decison Tree，同为Boosting家族的一员，它和Adaboost有很大的不同。Adaboost 是利用前一轮弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去，简单的说是Boosting框架+任意基学习器算法+指数损失函数。GBDT也是迭代，也使用了前向分布算法，但是弱学习器限定了只能使用CART回归树模型，同时迭代思路和Adaboost也有所不同，简单的说Boosting框架+CART回归树模型+任意损失函数。
GBDT的思想可以用一个通俗的例子解释，假如有个人30岁，我们首先用20岁去拟合，发现损失有10岁，这时我们用6岁去拟合剩下的损失，发现差距还有4岁，第三轮我们用3岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。

1.前向分布算法

于是，前向分布算法总结如下：

输入：
训练数据集T ={(x1,y1), (x2, y2), ..., (xN, yN)}；损失函数L(y, f(x))；基函数集{b(x; r)}；
输出：
加法模型f(x)

解：

初始化f0(x)= 0
对m = 1, 2,.., M
a. 极小化损失函数
$(\beta_m,\gamma_m)= argmin\sum_{i=1}^NL(y_i,f_{m-1}(x_i)+\beta b(x_i;\gamma))$
得到参数βm, rm
b. 更新
$f_m(x)= f_{m-1}(x)+\beta_mb(x;\gamma_m)$
得到加法模型
$f(x) = f_M(x)=\sum_{m=1}^M\beta_mb(x;\gamma_m)$
这样，前向分布算法将同时求解从m=1到M的所有参数βm, rm的优化问题简化为逐次求解各个βm, rm的优化问题。

2.负梯度拟合

在GBDT的迭代中，假设我们前一轮迭代得到的强学习器是 $H_{t−1}(x)Ht−1(x)$ , 损失函数是
$J = L(f(x),H_{t−1}(x))L(f(x),H_{t−1}(x))$
我们本轮迭代的目标是找到一个CART回归树模型的弱学习器 $h_t(x)$
让本轮的损失 $L(f(x),h_t(x)+H_{t−1}(x))L(f(x),h_t(x)+H_{t−1}(x))$ 最小
那么GBDT是如何实现让本轮的损失最小的呢？
针对这个问题，大牛Freidman提出了用损失函数的负梯度来拟合本轮损失 $L(f(x),ht(x)+H_{t−1}(x))L(f(x),h_t(x)+H_{t−1}(x))$ 的近似值，进而拟合一个CART回归树。第 t 轮的第 i 个样本的损失函数的负梯度表示为

$-\left[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}\right]_{f(x)=f_{m-1}(x)}$ 利用 $(xi,r_ti),i=1,2,⋯,m(xi,r_ti),i=1,2,⋯,m$ ,我们可以拟合一棵CART回归树，得到了第 t 棵回归树，其对应的叶结点区域 $R_{tj},j=1,2,⋯,JR_{tj},j=1,2,⋯,J$ 。其中 $J$ 为叶子结点的个数。

针对每一个叶子结点里的样本，我们求出使损失函数最小，也就是拟合叶子结点最好的输出值 $c_{tj}$
本轮的决策树拟合函数如下：
$h_t(x)=\sum_{j=1}^Jc_{tj}I(x\epsilon R_{tj})$
最终的道德强学习器表达式如下：
$h_t(x)=h_{t-1}(x)+\sum_{j=1}^Jc_{tj}I(x \epsilon R_tj)$
通过损失函数的负梯度来拟合，我们找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，我们通过其损失函数的负梯度的拟合，就可以用GBDT来解决我们的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。

3.损失函数

这里我们再对常用的GBDT损失函数做一个总结。

对于分类算法，其损失函数一般有对数损失函数和指数损失函数两种:

如果是指数损失函数，则损失函数表达式为
$L(y,h(x))=exp(−yh(x))$
其负梯度计算和叶子节点的最佳残差拟合参见Adaboost原理篇。
如果是对数损失函数，分为二元分类和多元分类两种，
对于二元分类
$L(y,h(x))=log(1+exp(−yh(x)))$

对于回归算法，常用损失函数有如下4种:

均方差，这个是最常见的回归损失函数了
$L(y,h(x))=(y−h(x))^2$
绝对损失，这个损失函数也很常见
$L(y,h(x))=|y−h(x)|$
对应负梯度误差为：
$sign(y_i−h(x_i))$
Huber损失，它是均方差和绝对损失的折衷产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量。
分位数损失。它对应的是分位数回归的损失函数。

4.回归

输入：训练样本 $D={(x1,y1),(x2,y2),⋯,(xm,ym)}D={(x1,y1),(x2,y2),⋯,(xm,ym)}$ ,最大迭代次数（基学习器数量)T，损失函数 L
输出：强学习器 $H(x)$

算法流程

step1:
初始化基学习器
$h0(x)=argmin_c\sum_{i=1}^m L(y_i,c)$
step2:
当迭代次数 t=1,2,⋯,Tt=1,2,⋯,T

计算 t 次迭代的负梯度
利用 $(x_i,r_ti)(i=1,2,⋯,m)(x_i,r_ti)(i=1,2,⋯,m)$ ,拟合第 t 棵CART回归树，其对应的叶子结点区域为 $R_{tj},j=1,2,⋯,JR_{tj},j=1,2,⋯,J。$ 其中 $J$ 为回归树的叶子结点的个数
对叶子结点区域 $j=1,2,⋯,Jj=1,2,⋯,J$ ，计算最佳拟合值
$ctj=argmin_c\sum_{cxi∈Rtj}L(y_i,h_t−1(x_i)+c)$
更新强学习器
$h_t(x)=h_{t−1}(x)+∑^J_{j=1}c_{tj}I(x∈R_{tj})$
Step3:
得到强学习器:
$H(x)=h_0(x)+∑^T_{t=1}∑^J_{j=1}c_{tj}I(x∈Rtj)$

5.二分类，多分类

GBDT的分类算法从思想上和GBDT的回归算法没有本质区别，但是由于样本输出不是连续的值，而是离散的类别，导致我们无法直接从输出类别去拟合类别输出的误差。

为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时GBDT退化为Adaboost算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，我们用的是类别的预测概率值和真实概率值的差来拟合损失。本文仅讨论用对数似然损失函数的GBDT分类。而对于对数似然损失函数，我们又有二元分类和多元分类的区别。

5.1 二分类

对于二元GBDT，如果用类似于逻辑回归的对数似然损失函数，则损失函数为：
$L(y,h(x))=log(1+exp(−y_h(x)))$
其中，y∈{−1,+1}y∈{−1,+1}。此时的负梯度误差是 :

对于生成的决策树，我们各个叶子节点的最佳残差拟合值为 :
$c_{tj}=argmin_c∑_{x_i∈R_{tj}}log(1+exp(−y_ih(x_i)+c))$
由于上式比较难优化，我们一般使用近似值代替

除了负梯度计算和叶子节点的最佳残差拟合的线性搜索，二元GBDT分类和GBDT回归算法过程相同。

6.正则化

和Adaboost一样，我们也需要对GBDT进行正则化，防止过拟合。GBDT的正则化主要有三种方式。

第一种是和Adaboost类似的正则化项，即步长(learning rate)。定义为ν,对于前面的弱学习器的迭代
$H_t(x)=H_{t−1}(x)+h_t(x)H_t(x)=H_{t−1}(x)+h_t(x)$
如果我们加上了正则化项，则有:
$H_t(x)=H_{t−1}(x)+αh_t(x),0<α≤1$
对于同样的训练集学习效果，较小的ν意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。
第二种正则化的方式是通过子采样比例（subsample）。取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间。
使用了子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用了子采样，程序可以通过采样分发到不同的任务去做boosting的迭代过程，最后形成新树，从而减少弱学习器难以并行学习的弱点。
第三种是对于弱学习器即CART回归树进行正则化剪枝。

7.优缺点

优点：

可以灵活处理各种类型的数据，包括连续值和离散值。
在相对少的调参时间情况下，预测的准备率也可以比较高。这个是相对SVM来说的。
使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如 Huber损失函数和Quantile损失函数。

缺点：
由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。

8.sklearn参数

8.1 boosting框架参数

n_estimators: 也就是弱学习器的最大迭代次数，或者说最大的弱学习器的个数。一般来说n_estimators太小，容易欠拟合，n_estimators太大，又容易过拟合，一般选择一个适中的数值。默认是100。在实际调参的过程中，我们常常将n_estimators和下面介绍的参数learning_rate一起考虑。
learning_rate: 即每个弱学习器的权重缩减系数ν，也称作步长，在原理篇的正则化章节我们也讲到了，加上了正则化项，我们的强学习器的迭代公式为fk(x)=fk−1(x)+νhk(x)fk(x)=fk−1(x)+νhk(x)。νν的取值范围为0<ν≤10<ν≤1。对于同样的训练集拟合效果，较小的νν意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。所以这两个参数n_estimators和learning_rate要一起调参。一般来说，可以从一个小一点的νν开始调参，默认是1。
subsample: 即我们在原理篇的正则化章节讲到的子采样，取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间，默认是1.0，即不使用子采样。
init: 即我们的初始化的时候的弱学习器，拟合对应原理篇里面的f0(x)f0(x)，如果不输入，则用训练集样本来做样本集的初始化分类回归预测。否则用init参数提供的学习器做初始化分类回归预测。一般用在我们对数据有先验知识，或者之前做过一些拟合的时候，如果没有的话就不用管这个参数了。
loss: 即我们GBDT算法中的损失函数。分类模型和回归模型的损失函数是不一样的。

对于分类模型，有对数似然损失函数"deviance"和指数损失函数"exponential"两者输入选择。默认是对数似然损失函数"deviance"。在原理篇中对这些分类损失函数有详细的介绍。一般来说，推荐使用默认的"deviance"。它对二元分离和多元分类各自都有比较好的优化。而指数损失函数等于把我们带到了Adaboost算法。
对于回归模型，有均方差"ls", 绝对损失"lad", Huber损失"huber"和分位数损失“quantile”。默认是均方差"ls"。一般来说，如果数据的噪音点不多，用默认的均方差"ls"比较好。如果是噪音点较多，则推荐用抗噪音的损失函数"huber"。而如果我们需要对训练集进行分段预测的时候，则采用“quantile”。

alpha：这个参数只有GradientBoostingRegressor有，当我们使用Huber损失"huber"和分位数损失“quantile”时，需要指定分位数的值。默认是0.9，如果噪音点较多，可以适当降低这个分位数的值。

8.2 GBDT类库弱学习器参数

这里我们再对GBDT的类库弱学习器的重要参数做一个总结。由于GBDT使用了CART回归决策树，因此它的参数基本来源于决策树类，也就是说，和DecisionTreeClassifier和DecisionTreeRegressor的参数基本类似。

划分时考虑的最大特征数max_features: 可以使用很多种类型的值，默认是"None",意味着划分时考虑所有的特征数；如果是"log2"意味着划分时最多考虑log2Nlog2N个特征；如果是"sqrt"或者"auto"意味着划分时最多考虑N−−√N个特征。如果是整数，代表考虑的特征绝对数。如果是浮点数，代表考虑特征百分比，即考虑（百分比xN）取整后的特征数。其中N为样本总特征数。一般来说，如果样本特征数不多，比如小于50，我们用默认的"None"就可以了，如果特征数非常多，我们可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间。
决策树最大深度max_depth: 默认可以不输入，如果不输入的话，决策树在建立子树的时候不会限制子树的深度。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。
内部节点再划分所需最小样本数min_samples_split: 这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。默认是2.如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。
叶子节点最少样本数min_samples_leaf: 这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。默认是1,可以输入最少的样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。
叶子节点最小的样本权重和min_weight_fraction_leaf：这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。
最大叶子节点数max_leaf_nodes: 通过限制最大叶子节点数，可以防止过拟合，默认是"None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到。
节点划分最小不纯度min_impurity_split: 这个值限制了决策树的增长，如果某节点的不纯度(基于基尼系数，均方差)小于这个阈值，则该节点不再生成子节点。即为叶子节点。一般不推荐改动默认值1e-7。

9.应用场景

该版本GBDT几乎可用于所有回归问题（线性/非线性），相对logistic regression仅能用于线性回归，GBDT的适用面非常广。亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）

10.GBDT调参实例

import pandas as pd
import numpy as np
from sklearn.ensemble import GradientBoostingClassifier #！！！

from sklearn import model_selection,metrics
from sklearn.model_selection import GridSearchCV

import matplotlib.pylab as plt
%matplotlib inline

train = pd.read_csv('/home/kesci/input/GBDT2936/train_modified.csv')
target='Disbursed' # Disbursed的值就是二元分类的输出
IDcol = 'ID'
train['Disbursed'].value_counts() #分别计算0，1的个数

得到：

0 19680
1 320
Name: Disbursed, dtype: int64

x_columns = [x for x in train.columns if x not in [target, IDcol]] #使用不是target，ID列的数字
X = train[x_columns]
y = train['Disbursed']

先不进行任何调参看一下结果：

gbm0 = GradientBoostingClassifier(random_state=10)
gbm0.fit(X,y)
y_pred = gbm0.predict(X)
y_predprob = gbm0.predict_proba(X)[:,1]
print ("Accuracy :" ,metrics.accuracy_score(y.values, y_pred))
print ("AUC Score (Train):", metrics.roc_auc_score(y, y_predprob))

输出如下：
Accuracy : 0.98525
AUC Score (Train): 0.9005309165396341
可见拟合得还可以，我们下面看看怎么通过调参提高模型的泛化能力。

首先我们从步长(learning rate)和迭代次数(n_estimators)入手。一般来说,开始选择一个较小的步长来网格搜索最好的迭代次数。这里，我们将步长初始值设置为0.1。对于迭代次数进行网格搜索如下：

param_test1 = {'n_estimators':range(20,81,10)}
gsearch1 = GridSearchCV(estimator = GradientBoostingClassifier(learning_rate=0.1, min_samples_split=300,
                                  min_samples_leaf=20,max_depth=8,max_features='sqrt', subsample=0.8,random_state=10), 
                       param_grid = param_test1, scoring='roc_auc',iid=False,cv=5)
gsearch1.fit(X,y)
print(gsearch1.best_params_, gsearch1.best_score_)

输出如下，可见最好的迭代次数是60。

([mean: 0.81285, std: 0.01967, params: {'n_estimators': 20},
mean: 0.81438, std: 0.01947, params: {'n_estimators': 30},
mean: 0.81451, std: 0.01933, params: {'n_estimators': 40},
mean: 0.81618, std: 0.01848, params: {'n_estimators': 50},
mean: 0.81751, std: 0.01736, params: {'n_estimators': 60},
mean: 0.81547, std: 0.01900, params: {'n_estimators': 70},
mean: 0.81299, std: 0.01860, params: {'n_estimators': 80}],
{'n_estimators': 60},
0.8175146087398375)

找到了一个合适的迭代次数，现在我们开始对决策树进行调参。首先我们对决策树最大深度max_depth和内部节点再划分所需最小样本数min_samples_split进行网格搜索。

param_test2 = {'max_depth':range(3,14,2), 'min_samples_split':range(100,801,200)}
gsearch2 = GridSearchCV(estimator = GradientBoostingClassifier(learning_rate=0.1, n_estimators=60, min_samples_leaf=20, 
      max_features='sqrt', subsample=0.8, random_state=10), 
   param_grid = param_test2, scoring='roc_auc',iid=False, cv=5)
gsearch2.fit(X,y)
gsearch2.best_params_, gsearch2.best_score_

{'max_depth': 7, 'min_samples_split': 300},
0.8213724275914632)

决策树深度7是一个比较合理的值，我们把它定下来,下面我们再对内部节点再划分所需最小样本数min_samples_split和叶子节点最少样本数min_samples_leaf一起调参。

param_test3 = {'min_samples_split':range(800,1900,200), 'min_samples_leaf':range(60,101,10)}
gsearch3 = GridSearchCV(estimator = GradientBoostingClassifier(learning_rate=0.1, n_estimators=60,max_depth=7,
                                     max_features='sqrt', subsample=0.8, random_state=10), 
                       param_grid = param_test3, scoring='roc_auc',iid=False, cv=5)
gsearch3.fit(X,y)
gsearch3.best_params_, gsearch3.best_score_

得到：
({'min_samples_leaf': 60, 'min_samples_split': 1200}, 0.8222032996697154)

gbm1 = GradientBoostingClassifier(learning_rate=0.1, n_estimators=60,max_depth=7, min_samples_leaf =60, 
               min_samples_split =1200, max_features='sqrt', subsample=0.8, random_state=10)
gbm1.fit(X,y)
y_pred = gbm1.predict(X)
y_predprob = gbm1.predict_proba(X)[:,1]
print ("Accuracy : ",metrics.accuracy_score(y.values, y_pred))
print ("AUC Score (Train): ",metrics.roc_auc_score(y, y_predprob))

得到结果如下：
Accuracy : 0.984
AUC Score (Train): 0.9080987201473576
对比我们最开始完全不调参的拟合效果，可见精确度稍有下降，主要原理是我们使用了0.8的子采样，20%的数据没有参与拟合。

现在我们再对最大特征数max_features进行网格搜索。

param_test4 = {'max_features':range(7,20,2)}
gsearch4 = GridSearchCV(estimator = GradientBoostingClassifier(learning_rate=0.1, n_estimators=60,max_depth=7, min_samples_leaf =60, 
               min_samples_split =1200, subsample=0.8, random_state=10), 
                       param_grid = param_test4, scoring='roc_auc',iid=False, cv=5)
gsearch4.fit(X,y)
gsearch4.best_params_, gsearch4.best_score_

输出如下：
{'max_features': 9},
0.822412506351626)

现在我们再对子采样的比例进行网格搜索：

#再对子采样比例进行网格搜索
param_test5 = {'subsample':[0.6,0.7,0.75,0.8,0.85,0.9]}
gsearch5 = GridSearchCV(estimator = GradientBoostingClassifier(learning_rate=0.1, n_estimators=60,max_depth=7, min_samples_leaf =60, 
               min_samples_split =1200, max_features=9, random_state=10), 
                       param_grid = param_test5, scoring='roc_auc',iid=False, cv=5)
gsearch5.fit(X,y)
gsearch5.best_params_, gsearch5.best_score_

({'subsample': 0.7}, 0.8234378969766262)

现在基本已经得到我们所有调优的参数结果了。这时我们可以减半步长，最大迭代次数加倍来增加我们模型的泛化能力。再次拟合模型：

gbm2 = GradientBoostingClassifier(learning_rate=0.05, n_estimators=120,max_depth=7, min_samples_leaf =60, 
               min_samples_split =1200, max_features=9, subsample=0.7, random_state=10)
gbm2.fit(X,y)
y_pred = gbm2.predict(X)
y_predprob = gbm2.predict_proba(X)[:,1]
print("Accuracy :", metrics.accuracy_score(y.values, y_pred))
print("AUC Score :",metrics.roc_auc_score(y, y_predprob))

Accuracy : 0.984
AUC Score : 0.9053244886941056

可以看到AUC分数比起之前的版本稍有下降，这个原因是我们为了增加模型泛化能力，为防止过拟合而减半步长，最大迭代次数加倍，同时减小了子采样的比例，从而减少了训练集的拟合程度。
下面我们继续将步长缩小5倍，最大迭代次数增加5倍，继续拟合我们的模型：

gbm3 = GradientBoostingClassifier(learning_rate=0.01, n_estimators=600,max_depth=7, min_samples_leaf =60, 
               min_samples_split =1200, max_features=9, subsample=0.7, random_state=10)
gbm3.fit(X,y)
y_pred = gbm3.predict(X)
y_predprob = gbm3.predict_proba(X)[:,1]
print("Accuracy :", metrics.accuracy_score(y.values, y_pred))
print("AUC Score :",metrics.roc_auc_score(y, y_predprob))

输出如下，可见减小步长增加迭代次数可以在保证泛化能力的基础上增加一些拟合程度。
Accuracy : 0.984
AUC Score (Train): 0.908581
最后再来一次：

gbm4 = GradientBoostingClassifier(learning_rate=0.005, n_estimators=1200,max_depth=7, min_samples_leaf =60, 
               min_samples_split =1200, max_features=9, subsample=0.7, random_state=10)
gbm4.fit(X,y)
y_pred = gbm4.predict(X)
y_predprob = gbm4.predict_proba(X)[:,1]
print("Accuracy :", metrics.accuracy_score(y.values, y_pred))
print("AUC Score :",metrics.roc_auc_score(y, y_predprob))

Accuracy : 0.984
AUC Score : 0.9082321042936993
输出如下，此时由于步长实在太小，导致拟合效果反而变差，也就是说，步长不能设置的过小。

Gradient Boosting Decision Tree

概述

1.前向分布算法

2.负梯度拟合

3.损失函数

4.回归

算法流程

5.二分类，多分类

5.1 二分类

6.正则化

7.优缺点

8.sklearn参数

8.1 boosting框架参数

8.2 GBDT类库弱学习器参数

9.应用场景

10.GBDT调参实例

参考资料：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读