GBDT算法梳理

它主要的思想是，每一次建立模型是在建立模型损失函数的梯度下降方向。损失函数是评价模型性能，我们认为损失函数越小，性能越好。让损失函数持续下降，就能使得模型不断改性提升性能，其最好的方法就是使损失函数沿着梯度方向下降。

3. 负梯度拟合

如何解决损失函数拟合方法的问题，Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。第t轮的第i个样本的损失函数的负梯度表示为

r t i l = − [ ∂ L ( y i , f ( x i ) ) ) ∂ f ( x i ) ] f k ( x ) = f t − 1    ( x ) r_{til} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f_k(x) = f_{t-1}\;\; (x)} rtil=−[∂f(xi)∂L(yi,f(xi)))]fk(x)=ft−1(x)

利用( x i x_{i} xi, r t i r_{ti} rti)(i=1,2,…m),可以拟合一颗CART回归树，得到了第t颗回归树，其对应的叶节点区域 R t j R_{tj} Rtj,j=1,2,…,N。其中N为叶子节点的个数。

针对每一个叶子节点里的样本，求出使损失函数最小，得到了本轮的决策树拟合函数 h t ( x ) h_{t}(x) ht(x)

通过损失函数的负梯度来拟合，找到了一种通用的拟合损失误差的办法，这样无轮是分类问题还是回归问题，通过其损失函数的负梯度的拟合，就可以用GBDT来解决的分类回归问题。区别仅仅在于损失函数不同导致的负梯度不同而已。

4. 损失函数

① 分类模型的损失函数包括有

●对数似然损失函数

L ( y , f ( x ) ) = l o g ( 1 + e x p ( − y f ( x ) ) ) ) L(y,f(x))=log(1+exp(-yf(x)))) L(y,f(x))=log(1+exp(−yf(x))))

●指数损失函数

L ( y , f ( x ) ) = e x p ( − y f ( x ) ) L(y, f(x)) = exp(-yf(x)) L(y,f(x))=exp(−yf(x))

② 回归模型的损失函数包括

●均方差

L ( y , f ( x ) ) = ( y − f ( x ) ) 2 L(y, f(x)) =(y-f(x))^2 L(y,f(x))=(y−f(x))2

●绝对损失

L ( y , f ( x ) ) = ∣ y − f ( x ) ∣ L(y, f(x)) =|y-f(x)| L(y,f(x))=∣y−f(x)∣

●Huber损失,均方差和绝对损失的折中产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量。用于健壮回归，也就是减少异常点对损失函数的影响.

L ( y , f ( x ) ) = { 1 2 ( y − f ( x ) ) 2 ∣ y − f ( x ) ∣ ≤ δ δ ( ∣ y − f ( x ) ∣ − δ 2 ) ∣ y − f ( x ) ∣ < δ L(y, f(x))=\begin{cases}\frac{1}{2}(y-f(x))^2& {|y-f(x)| \leq \delta}\\\delta(|y-f(x)| - \frac{\delta}{2})& {|y-f(x)| < \delta}\end{cases} L(y,f(x))={21(y−f(x))2δ(∣y−f(x)∣−2δ)∣y−f(x)∣≤δ∣y−f(x)∣<δ

●分位数损失,它对应的是分位数回归的损失函数

L ( y , f ( x ) ) = ∑ y ≥ f ( x ) θ ∣ y − f ( x ) ∣ + ∑ y f ( x ) ( 1 − θ ) ∣ y − f ( x ) ∣ L(y, f(x)) =\sum\limits_{y \geq f(x)}\theta|y - f(x)| + \sum\limits_{y f(x)}(1-\theta)|y - f(x)| L(y,f(x))=y≥f(x)∑θ∣y−f(x)∣+yf(x)∑(1−θ)∣y−f(x)∣

其中θ为分位数，需要我们在回归前指定。

5. GBDT算法

该部分参照文档文档链接

①回归算法

输入是训练集样本 T = { ( x , y 1 ) , ( x 2 , y 2 ) , . . . ( x m , y m ) } T=\{(x_,y_1),(x_2,y_2), ...(x_m,y_m)\} T={(x,y1),(x2,y2),...(xm,ym)}，最大迭代次数T, 损失函数L。输出是强学习器f(x)

初始化弱学习器 f 0 ( x ) = a r g   m i n ⎵ c ∑ i = 1 m L ( y i , c ) f_0(x) = \underbrace{arg\; min}_{c}\sum\limits_{i=1}^{m}L(y_i, c) f0(x)=c

argmini=1∑mL(yi,c)
对迭代轮数t=1,2,…T有：

(1)对样本i=1,2，…m，计算负梯度 r t i = − [ ∂ L ( y i , f ( x i ) ) ) ∂ f ( x i ) ] f ( x ) = f t − 1    ( x ) r_{ti} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = f_{t-1}\;\; (x)} rti=−[∂f(xi)∂L(yi,f(xi)))]f(x)=ft−1(x)

(2)利用 ( x i , r t i )    ( i = 1 , 2 , . . m ) (x_i,r_{ti})\;\; (i=1,2,..m) (xi,rti)(i=1,2,..m), 拟合一颗CART回归树,得到第t颗回归树，其对应的叶子节点区域为 R t j , j = 1 , 2 , . . . , J R_{tj}, j =1,2,..., J Rtj,j=1,2,...,J。其中J为回归树t的叶子节点的个数。

(3) 对叶子区域j =1,2,…J,计算最佳拟合值 c t j = a r g   m i n ⎵ c ∑ x i ∈ R t j L ( y i , f t − 1 ( x i ) + c ) c_{tj} = \underbrace{arg\; min}_{c}\sum\limits_{x_i \in R_{tj}} L(y_i,f_{t-1}(x_i) +c) ctj=c

argminxi∈Rtj∑L(yi,ft−1(xi)+c)

(4) 更新强学习器 f t ( x ) = f t − 1 ( x ) + ∑ j = 1 J c t j I ( x ∈ R t j ) f_{t}(x) = f_{t-1}(x) + \sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj}) ft(x)=ft−1(x)+j=1∑JctjI(x∈Rtj)
得到强学习器f(x)的表达式 f ( x ) = f T ( x ) = f 0 ( x ) + ∑ t = 1 T ∑ j = 1 J c t j I ( x ∈ R t j ) f(x) = f_T(x) =f_0(x) + \sum\limits_{t=1}^{T}\sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj}) f(x)=fT(x)=f0(x)+t=1∑Tj=1∑JctjI(x∈Rtj)

②分类算法

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

目前主要有两个方法

1.指数损失函数，此时GBDT退化为Adaboost算法。

2.对数似然损失函数的方法。用类别的预测概率值和真实概率值的差来拟合损失。

●二元分类

二元分类的损失函数类似于逻辑回归对数似然损失函数：

L ( y , f ( x ) ) = l o g ( 1 + e x p ( − y f ( x ) ) ) ) L(y,f(x))=log(1+exp(-yf(x)))) L(y,f(x))=log(1+exp(−yf(x))))其中 y ∈ { − 1 , + 1 } y \in\{-1, +1\} y∈{−1,+1}，

则此时的负梯度误差为:

r t i = − [ ∂ L ( y , f ( x i ) ) ) ∂ f ( x i ) ] f ( x ) = f t − 1 ( x ) = y i / ( 1 + e x p ( y i f ( x i ) ) ) r_{ti}= -\bigg[\frac{\partial L(y, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = f_{t-1} (x)} = y_i/(1+exp(y_if(x_i))) rti=−[∂f(xi)∂L(y,f(xi)))]f(x)=ft−1(x)=yi/(1+exp(yif(xi)))

对于生成的决策树，我们各个叶子节点的最佳残差拟合值为:

c t j = a r g   m i n ⎵ c ∑ x i ∈ R t j l o g ( 1 + e x p ( − y i ( f t − 1 ( x i ) + c ) ) ) c_{tj} = \underbrace{arg\; min}_{c}\sum\limits_{x_i \in R_{tj}} log(1+exp(-y_i(f_{t-1}(x_i) +c))) ctj=c

argminxi∈Rtj∑log(1+exp(−yi(ft−1(xi)+c)))

由于上式比较难优化，我们一般使用近似值代替:

c t j = ∑ x i ∈ R t j r t i / ∑ x i ∈ R t j ∣ r t i ∣ ( 1 − ∣ r t i ∣ ) c_{tj} = \sum\limits_{x_i \in R_{tj}}r_{ti}\bigg / \sum\limits_{x_i \in R_{tj}}|r_{ti}|(1-|r_{ti}|) ctj=xi∈Rtj∑rti/xi∈Rtj∑∣rti∣(1−∣rti∣)

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

●多元分类

我们的对数似然损失函数为：

L ( y , f ( x ) ) = − ∑ k = 1 K y k l o g   p k ( x ) L(y, f(x)) = -\sum\limits_{k=1}^{K}y_klog\;p_k(x) L(y,f(x))=−k=1∑Kyklogpk(x)

其中如果样本输出类别为k，则 y k = 1 y_k=1 yk=1。

第k类的概率 p k ( x ) p_k(x) pk(x)的表达式为：

p k ( x ) = e x p ( f k ( x ) ) / ∑ l = 1 K e x p ( f l ( x ) ) p_k(x) = exp(f_k(x)) \bigg / \sum\limits_{l=1}^{K} exp(f_l(x)) pk(x)=exp(fk(x))/l=1∑Kexp(fl(x))

集合上两式，我们可以计算出第 t t t轮的第 i i i个样本对应 l l l类别的负梯度误差为：

r t i l = − [ ∂ L ( y i , f ( x i ) ) ) ∂ f ( x i ) ] f k ( x ) = f l , t − 1    ( x ) = y i l − p l , t − 1 ( x i ) r_{til} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f_k(x) = f_{l, t-1}\;\; (x)} = y_{il} - p_{l, t-1}(x_i) rtil=−[∂f(xi)∂L(yi,f(xi)))]fk(x)=fl,t−1(x)=yil−pl,t−1(xi)

观察上式可以看出，其实这里的误差就是样本 i i i对应类别 l l l的真实概率和 t − 1 t-1 t−1轮预测概率的差值。

对于生成的决策树，我们各个叶子节点的最佳残差拟合值为

c t j l = a r g   m i n ⎵ c j l ∑ i = 0 m ∑ k = 1 K L ( y k , f t − 1 , l ( x ) + ∑ j = 0 J c j l I ( x i ∈ R t j ) ) c_{tjl} = \underbrace{arg\; min}_{c_{jl}}\sum\limits_{i=0}^{m}\sum\limits_{k=1}^{K} L(y_k, f_{t-1, l}(x) + \sum\limits_{j=0}^{J}c_{jl} I(x_i \in R_{tj})) ctjl=cjl

argmini=0∑mk=1∑KL(yk,ft−1,l(x)+j=0∑JcjlI(xi∈Rtj))

由于上式比较难优化，我们一般使用近似值代替 c t j l = K − 1 K   ∑ x i ∈ R t j l r t i l ∑ x i ∈ R t i l ∣ r t i l ∣ ( 1 − ∣ r t i l ∣ ) c_{tjl} = \frac{K-1}{K} \; \frac{\sum\limits_{x_i \in R_{tjl}}r_{til}}{\sum\limits_{x_i \in R_{til}}|r_{til}|(1-|r_{til}|)} ctjl=KK−1xi∈Rtil∑∣rtil∣(1−∣rtil∣)xi∈Rtjl∑rtil

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

6. 正则化

与大多数算法一样，GBDT也需要进行正则化，以防止过拟合。GBDT的正则化主要有三种方式。

① 步长(learning rate)正则化。

②通过子采样比例（subsample）正则化。

取值为(0,1]。不同于随机森林使用的放回抽样，此处为不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。一般在[0.5, 0.8]之间。

使用子采样的GBDT有时也称作随机梯度提升树(Stochastic Gradient Boosting Tree, SGBT)。由于使用子采样，程序可以通过采样分发到不同的任务去做boosting的迭代过程，最后形成新树，从而可以并行学习。

③CART回归树进行正则化剪枝。

7. 优缺点及与RF的比较

① GBDT主要的优点有：

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

②GBDT的主要缺点有：

由于弱学习器之间存在依赖关系，难以并行训练数据。不过可以通过自采样的SGBT来达到部分并行。
数据维度较高时会加大算法的计算复杂度.

③GBDT与RF区别

1、组成随机森林的树可以是分类树，也可以是回归树；而GBDT只由回归树组成，GBDT的会累加所有树的结果，而这种累加是无法通过分类完成的，因此GBDT的树都是CART回归树，而不是分类树（尽管GBDT调整后也可以用于分类但不代表GBDT的树为分类树）

2、组成随机森林的树可以并行生成；而GBDT只能是串行生成

3、对于最终的输出结果而言，随机森林采用多数投票等；而GBDT则是将所有结果累加起来，或者加权累加起来

4、随机森林对异常值不敏感，GBDT对异常值非常敏感

5、随机森林对训练集一视同仁，GBDT是基于权值的弱分类器的集成

6、随机森林是通过减少模型方差提高性能，GBDT是通过减少模型偏差提高性能

8. sklearn参数

①boosting框架参数

n_estimators: 也就是弱学习器的最大迭代次数，或者说最大的弱学习器的个数。一般来说n_estimators太小，容易欠拟合，n_estimators太大，又容易过拟合，一般选择一个适中的数值。默认是100。
learning_rate: 即每个弱学习器的权重缩减系数，也称作步长。通常用步长和迭代最大次数一起来决定算法的拟合效果。所以这两个参数n_estimators和learning_rate要一起调参。默认是1。
subsample: 即在正则化中讲到的子采样，取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。推荐在[0.5, 0.8]之间，默认是1.0。
init: 即初始化的时候的弱学习器，如果不输入，则用训练集样本来做样本集的初始化分类回归预测。否则用init参数提供的学习器做初始化分类回归预测。
loss: 即GBDT算法中的损失函数。分类模型和回归模型的损失函数是不一样的。

对于分类模型，有对数似然损失函数"deviance"和指数损失函数"exponential"两者输入选择。默认是对数似然损失函数"deviance"。一般来说，推荐使用默认的"deviance"。它对二元分离和多元分类各自都有比较好的优化。而指数损失函数等于带到了Adaboost算法。

对于回归模型，有均方差"ls", 绝对损失"lad", Huber损失"huber"和分位数损失“quantile”。默认是均方差"ls"。一般来说，如果数据的噪音点不多，用默认的均方差"ls"比较好。如果是噪音点较多，则推荐用抗噪音的损失函数"huber"。而如果需要对训练集进行分段预测的时候，则采用“quantile”。
alpha：这个参数只有GradientBoostingRegressor有，当使用Huber损失"huber"和分位数损失“quantile”时，需要指定分位数的值。默认是0.9，如果噪音点较多，可以适当降低这个分位数的值。

②弱学习器参数

max_features: 划分时考虑的最大特征数。

默认是"None",意味着划分时考虑所有的特征数；

log2意味着划分时最多考虑log2N个特征；

sqrt或者auto意味着划分时最多考虑√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的适用面非常广。亦可用于二分类问题（设定阈值，大于阈值为正例，反之为负例）。GBDT同时也可以用于特征工程中，用GBDT来选择特征。详见论文“Practical Lessons from Predicting Clicks on Ads at Facebook”

[Task2] GBDT算法梳理GBDT算法梳理