基于树模型的集成算法---GBDT

一、模型介绍

GBDT 的全称是 Gradient Boosting Decision Tree，梯度提升决策树。 GBDT 也是集成学习 Boosting 家族的成员，但是却和传统的 Adaboost 有很大的不同。
回顾下 Adaboost，我们是利用前一轮迭代弱学习器的误差率来更新训练集的权重，这样一轮轮的迭代下去。GBDT 也是迭代，使用了前向分布算法，但是弱学习器限定了只能使用 CART 回归树模型，无论是处理回归问题还是二分类以及多分类，GBDT 使用的决策树通通都是 CART 回归树。因为 GBDT 每次迭代要拟合的是梯度值，是连续值所以要用回归树。同时迭代思路和 Adaboost 也有很大不同。在 RF、Adaboost 等加法模型中，都是通过直接拟合真实值来构建模型的，而在 GBDT 里面：非首轮迭代的模型拟合的目标值不再是真实值，而是一个梯度值，主要是通过拟合损失函数的负梯度值在当前模型的值来构建模型。

二、模型原理

Gradient Bossting：梯度提升树

梯度提升树（Grandient Boosting）是提升树（Boosting Tree）的一种改进算法。
首先我们来看一下提升树的思想：假如有个人 30 岁，我们首先用 20 岁去拟合，发现损失有 10 岁，这时我们用 6 岁去拟合剩下的损失，发现差距还有 4 岁，第三轮我们用 3 岁拟合剩下的差距，差距就只有一岁了。如果我们的迭代轮数还没有完，可以继续迭代下面，每一轮迭代，拟合的岁数误差都会减小。最后将每次拟合的岁数加起来便是模型输出的结果。

1. 初始化 $f_0(x) = 0$
1. 对 m = 1,2,3……M
  (1) 计算残差 $r_{mi} = y_i - f_{m-1}(x_i) , i = 1,2,3……M$
  (2) 拟合残差 $r_{mi}$ 学习一个回归树，得到 $h_m(x)$ .
  (3) 更新 $f_m(x) = f_{m-1}(x) + h_m(x)$
1. 得到回归树 $f_{M}(x) = \sum_{m=1}^{M} h_m(x)$

在提升树算法中，假设我们上一轮迭代得到的强学习器是 $f_{t-1}(x)$ ，损失函数是 $L(y, f_{t-1}(x))$ ，我们本轮迭代的目标是找到一个弱学习器 $h_t(x)$ ，当我们采用平方损失函数时 $L(y, f_{t-1}(x) + h_t(x)) = (y - f_{t-1}(x) - h_{t}(x))^2 = (r - h_{t}(x))^2$
这里的 $r = y - f_{t-1}(x)$ 是当前模型拟合数据的残差（residual）。所以，对于提升树来说只需要简单地拟合当前模型的残差。
当损失函数是平方损失和指数损失函数时，梯度提升树每一步优化是很简单的，但是对于一般损失函数而言，往往每一步优化起来不那么容易，针对这一问题，Freidman 提出了梯度提升树算法，这是利用最速下降的近似方法，其关键是利用损失函数的负梯度作为提升树算法中的残差的近似值。

对于负梯度：
第 t 轮的第 i 个样本的损失函数的负梯度为：
$-\left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right]_{f(x)=f_{t-1}(x)}$
根据上式可以看出，不同的损失函数将会得到不同的负梯度，如果选择平方损失： $L(y_i, f(x_i)) = \frac{1}{2}(y_i-f(x_i))^2$
负梯度：
$-\left[\frac{\partial L(y_i,f(x_i))}{\partial f(x_i)} \right]_{f(x)=f_{t-1}(x)}= -\left[\frac{\partial \frac{1}{2}(y_i - f(x_i))^2}{\partial f(x_i)} \right]_{f(x)=f_{t-1}(x)} = y_i - f(x_i)$
可以看出，此时的负梯度就是残差。所以对于回归问题来说，我们要拟合的就是残差。对于分类问题，损失函数都是 log loss。

原理：

上面介绍完了 Gradient Bossting 的原理，那么对于 GBDT 的算法原理如下：

1. 初始化弱学习器 $f_0(x) = arg \underset{c}{min}\sum_{i=1}^{N}L(y_i, c)$
1. 对于 m = 1,2,3……M 有：
  （1）对每个样本 i = 1,2,3……N，计算负梯度，即残差 $r_{im} = - \left[ \frac{\partial L(y_i, f(x_i))}{\partial f(x_i)}\right]_{f(x) = f_{m-1}(x)}$
  （2）将上面得到的残差作为样本新的真实值，并将数据 $(x_i, r_{im})，i=1,2,3……N$ 作为下棵树的训练数据，得到一棵新的回归树 $f_m(x)$ 其对应的叶子节点区域为 $R_{jm}，j=1,2,3……J$ 其中 J 为回归树 t 的叶子节点的个数。
  （3）对叶子区域 j = 1,2,3……J，计算最佳拟合值 $\gamma_{jm} = arg \underset{\gamma}{min} \sum_{x_i \epsilon R_{jm}}L(y_i, f_{m-1}(x_i) + \gamma)$
  （4）更新强学习器 $f_m(x) = f_{m-1}(x) + \sum_{j=1}^{J}\gamma_{jm} I(x \epsilon R_{jm})$
1. 得到最终学习器： $f(x) = f_M(x) = f_0(x) + \sum_{m=1}^{M}\sum_{j=1}^{J}\gamma_{jm} I (x\epsilon R_{jm})$

三、模型细节

1. 对于分类算法来说， GBDT 如何实现？

GBDT 的分类算法从思想上和 GBDT 的回归算法没有区别，但是由于样本输出不是连续的值，而是离散的类别，导致无法直接从输出类别去拟合类别输出的误差。为了解决这个问题，主要有两个方法，一个是用指数损失函数，此时 GBDT退化为 Adaboost 算法。另一种方法是用类似于逻辑回归的对数似然损失函数的方法。也就是说，用的是类别的预测概率值和真实概率值的差来拟合损失。接下来讨论用对数似然损失函数的 GBDT。而对于对数似然损失函数，又有二元分类和多元分类的区别。

2. GBDT 常用的损失函数

指数损失函数，同 Adaboost 算法中的损失函数。
$L(y, f(x)) = exp(-yf(x))$
对数损失函数，分为二元分类和多元分类两种。
$L(y, f(x)) = log(1+ exp(-yf(x)))$ $L(y,f(x)) = - \sum_{k=1}^{k}y_k \log{p_k(x)}$
均方差，这个是最常见的回归损失函数。
$L(y, f(x)) = (y-f(x))^2$
绝对损失，基于残差的GBDT在解决回归问题上也不算是一个好的选择，一个比较明显的缺点就是对异常值过于敏感。一般回归类的损失函数会用绝对损失或者huber损失函数来代替平方损失函数。
$L(y, f(x)) = |y-f(x)|$
Huber损失，它是均方差和绝对损失的折中产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量。
分位数损失。它对应的是分位数回归的损失函数。

对于Huber损失和分位数损失，主要用于健壮回归，也就是减少异常点对损失函数的影响。

3. 对于 GBDT 的正则化

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

四、模型优缺点

优点：

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

缺点：

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

五、模型使用

from sklearn.ensemble import GradientBoostingClassifier, GradientBoostingRegressor
gbclf = GradientBoostingClassifier(loss='deviance', learning_rate=0.1, n_estimators=100,
                 subsample=1.0, criterion='friedman_mse', min_samples_split=2,
                 min_samples_leaf=1, min_weight_fraction_leaf=0.,
                 max_depth=3, min_impurity_decrease=0.,
                 min_impurity_split=None, init=None,
                 random_state=None, max_features=None, verbose=0,
                 max_leaf_nodes=None, warm_start=False,
                 presort='deprecated', validation_fraction=0.1,
                 n_iter_no_change=None, tol=1e-4, ccp_alpha=0.0)
gbclf.fit(x,y)
gbclf.predict(test_x)


gbreg = GradientBoostingRegressor(loss='ls', learning_rate=0.1, n_estimators=100,
                 subsample=1.0, criterion='friedman_mse', min_samples_split=2,
                 min_samples_leaf=1, min_weight_fraction_leaf=0.,
                 max_depth=3, min_impurity_decrease=0.,
                 min_impurity_split=None, init=None, random_state=None,
                 max_features=None, alpha=0.9, verbose=0, max_leaf_nodes=None,
                 warm_start=False, presort='deprecated',
                 validation_fraction=0.1,
                 n_iter_no_change=None, tol=1e-4, ccp_alpha=0.0)
gbreg.fit(x,y)
gbreg.predict(test_x)