大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

集成算法大致分为两类：Boosting（迭代）和Bagging（装袋）。在前面的博客中，有提到，存在强依赖关系、必须串行生成的序列化方法，代表算法是Boosting，不存在强依赖关系、可同时生成的并行化方法，代表算法有Bagging、Random Forest。其中Boosting集成算法的典型代表算法有Adaboost，GBDT（Gradient Boosting Decision Tree），Xgboost（Extreme Gradient Boosting）；Random Forest（随机森林）是在Bagging的基础上进行改进的。GBDT算法，也称为梯度迭代决策树，是一种分类回归算法，具有较强的泛化能力。

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

1.前向分布算法

AdaBoost算法可以理解为，模型是加法模型、损失函数为指数函数、学习算法为前向分步算法时的二类分类学习方法。类似的，GBDT算法同样用到了前向分布算法。

前向分布算法，往往需要提到加法模型，首先定义加法模型：

$f(x)=\sum_{m=1}^{M}\beta _{m}b(x;\gamma _{m})$ (1)

其中， $b(x;\gamma _{m})$ 为基函数， $\gamma _{m}$ 为基函数的参数， $\beta _{m}为基函数的系数$ 为基函数的系数，数值大小代表对应的基函数在加法模型中的重要性。

一般的，在给定训练集以及损失函数 L(y;f(x)) 的情况下，学习加法模型 f(x) 就成为经验风险极小化(即损失函数极小化问题) :

$\min_{\beta _{m},\gamma _{m}}(\sum _{i=1}^{N}L(y_{i};\sum _{m=1}^{M}\beta _{m}b(x_{i};\gamma_{m})))$ (2)

这是个较为复杂的问题。

因此引入前向分布算法，即从前往后，每一步只学习一个基函数及其系数，计算出每一个基函数对应的损失函数，使其达到最小，最后综合起来即可。即简化为，每步只需求得公式（3）：

$\min_{\beta _{m},\gamma _{m}}(\sum _{i=1}^{N}L(y_{i};\beta _{m}b(x_{i};\gamma_{m})))$ (3)

前向分布算法求解过程可总结为如下：

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

输出：加法模型f(x)

1.初始化f0(x)= 0

2.对m = 1, 2,.., M

a.极小化损失函数

$(\beta _{m},\gamma _{m})=arg \min_{\beta, \gamma }\sum_{i=1}^{N}L(y_{i};f_{m-1}(x_{i})+\beta b(x_{i};\gamma))$

得到参数 $\beta_{m},\gamma_{m}$

b.更新

$f_{m}=f_{m-1}+\beta b(x_{i};\gamma )$

3.得到加法模型

$f(x)=f_{M}(x)=\sum_{i=1}^{M}\beta_{i} b(x;\gamma_{i})$

这样，前向分布算法将同时求解从m=1到M的所有参数 $\beta_{m},\gamma_{m}$ 的优化问题简化为逐次求解各个 $\beta_{m},\gamma_{m}$ 的优化问题，使问题简单化。

2.损失函数（loss function）

损失函数，亦称为代价函数（cost function），是将随机事件或其有关随机变量的取值映射为非负实数，以表示该随机事件的“风险”或“损失”的函数。常用的损失函数有：MSE（均方误差损失函数）；MAE（平均绝对误差）；Huber损失函数；分位数损失函数。这部分是参考《机器学习大牛最常用的5个回归损失函数，你知道几个？》（http://baijiahao.baidu.com/s?id=1603857666277651546&wfr=spider&for=pc）这篇文章进行粗略总结的。

对于回归算法，损失函数有以下几个：

MSE（均方误差损失函数）

均方误差是较为常用的损失函数，也称为L2，其公式满足：

$MSE=\sum _{i=1}^{N}(y_{i}-\overline{y_{i}})^{2}$ (1)

MAE（平均绝对误差）

平均绝对误差也称为L1，其公式满足：

$MAE=\sum_{i=1}^{N}|y_{i}-\overline{y_{i}}|$ (2)

处理异常点时，L1损失函数更稳定，但它的导数不连续，因此求解效率较低。L2损失函数对异常点更敏感，但通过令其导数为0，可以得到更稳定的封闭解。综合这两者的优缺点进行改进，可以得到Huber损失函数。

Huber损失函数

Huber损失函数，也称为平滑的平均绝对误差。Huber损失对数据中的异常点没有平方误差损失那么敏感，它在0处也可微分。本质上，Huber损失是绝对误差，只是在误差很小时，就变为平方误差。误差降到多小时变为二次误差由超参数δ（delta）来控制。当Huber损失在[0-δ,0+δ]之间时，等价为MSE，而在[-∞,δ]和[δ,+∞]时为MAE。

GBDT算法梳理_gbdt分类

分位数损失函数

当我们关注的是区间预测而不是点预测的时候，则需要用到分位数损失函数。

对于分类算法，其损失函数有指数损失函数、对数损失函数。

指数损失函数

L(y,f(x))=exp(-yf(x))

对数损失函数

3.负梯度（negative gradient descent）拟合

介绍了损失函数，那么，损失函数拟合方法有哪些呢？针对这个问题，大牛Freidman提出了用损失函数的负梯度来拟合本轮损失的近似值，进而拟合得到一个CART回归树。负梯度方向是多元可微函数在一点处梯度向量的反方向。

第t轮的第i个样本的损失函数的负梯度表示为

$r_{ti}=-[\frac{\partial L(y_{i},f(x_{i}))}{\partial f(x_{i})}]_{f(x)=f_{t-1}(x)}$

利用 $(x_{i},r_{ti}),(i=1,2,3,...,m)$ ，我们可以拟合一颗CART回归树，得到了第t颗回归树，其对应的叶节点区域 $R_{tj},j=1,2,...,J$ ，其中J为叶子节点的个数。

针对每一个叶子节点里的样本，求出使损失函数最小，也就是拟合叶子节点最好的的输出值 $c_{tj}$ 如下：

$c_{tj}=arg \min_{c}\sum_{x_{i}\in R_{tj}}L(y_{i},f_{t-1}(x_{i})+c)$

可得到本轮的决策树拟合函数：

$h_{t}(x)=\sum_{j=1}^{J}c_{tj}I(x\in R_{tj})$

经过本轮得到的强学习器表达式为：

$f_{t}(x)=f_{t-1}(x)+\sum_{j=1}^{J}c_{tj}I(x\in R_{tj})$

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

4.GBDT回归树

GBDT算法不仅可以用于分类，同时也可以用于回归。本次主要介绍GBDT算法的回归树。

输入训练集样本 $T=\left \{ (x_{1},y_{1}),(x_{2},y_{2}),...,(x_{m},y_{m}) \right \}$ ，最大迭代次数T，损失函数L。

输出是强学习器 f(x)

1)初始化弱学习器

$f_{0}(x)=arg \min_{c}\sum_{i=1}^{m}L(y_{i},c)$

2）对迭代轮数 t=1,2,...T 有：

a)对样本 i=1,2,...m ，计算负梯度

$r_{ti}=-[\frac{\partial L(y_{i},f(x_{i}))}{\partial f(x_{i})}]_{f(x)=f_{t-1}(x)}$

b)利用 $(x_{i},r_{ti}),(i=1,2,3,...,m)$ ，我们可以拟合一颗CART回归树，得到了第t颗回归树，其对应的叶节点区域 $R_{tj},j=1,2,...,J$ ，其中J为叶子节点的个数。

c)对叶子区域 j=1,2,...J ，计算最佳拟合值

$c_{tj}=arg \min_{c}\sum_{x_{i}\in R_{tj}}L(y_{i},f_{t-1}(x_{i})+c)$

d)更新强学习器

$f_{t}(x)=f_{t-1}(x)+\sum_{j=1}^{J}c_{tj}I(x\in R_{tj})$

3)得到强学习器f(x)的表达式

$f(x)=f_{T}(x)=f_{0}(x)+\sum_{t=1}^{T}\sum_{j=1}^{J}c_{tj}I(x\in R_{tj})$

5.二分类、多分类

GBDT二分类

对于二元GBDT，如果用类似于逻辑回归的对数似然损失函数，则损失函数为：

L(y,f(x))=log(1+exp(-y*f(x)))

其中， $y\in\left \{ -1, \right +1 \}$ ，此时的负梯度误差为

$r_{ti}=-[\frac{\partial L(y,f(x_{i}))}{\partial f(x_{i})}]_{f(x)=f_{t-1}(x)}=\frac{y_{i}}{1+exp(y_{i}f(x_{i}))}$

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

$c_{tj}=arg \min_{c} \sum_{x_{i}\in R_{tj}}log(1+exp(-y_{i}(f_{t-1}(x_{i})+c)))$

上式可使用近似值代替

$c_{tj}=\sum_{xi\in R_{tj}}\frac{r_{ti}}{\sum_{x_{i}\in R_{tj}}|r_{ti}|(1-|r_{ti}|)}$

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

GBDT多分类

多元GBDT要比二元GBDT复杂一些，对应的是多元逻辑回归和二元逻辑回归的复杂度的差别，假设类别数为K，则此时我们的对数似然损失函数为：

$L(y,f(x))=-\sum_{k=1}^{K}y_{k}log\ p_{k}(x)$

其中如果样本输出的类别为k，则 $y_{k}=1$ 。第k类的概率 $p_{k}(x)$ 的表达式为：

$p_{k}(x)=\frac{exp(f_{k}(x))}{\sum_{l=1}^{K}exp(f_{l}(x))}$

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

$r_{til}=-[\frac{\partial L(y_{i},f(x_{i}))}{\partial f(x_{i})}]_{f_{k}(x)=f_{l,t-1}(x)}=y_{il}-p_{l,t-1}(x_{i})$

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

对于生成的决策树，各个叶子节点的最佳负梯度拟合值为

$c_{tjl}=arg \min_{c_jl}\sum_{i=0}^{m}\sum_{k=1}^{K}L(y_{k},f_{t-1,l}(x)+\sum_{j=0}^{J}c_{jl}I(x_{i}\in R_{tj}))$

由于上式比较难优化，可用下式代替

$c_{tjl}=\frac{K-1}{K} \frac{\sum_{x_{i}\in R_{tjl}}r_{til}}{\sum_{x_{i}\in R_{til}}|r_{til}|(1-|r_{til}|)}$

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

6.正则化

和Adaboost一样，我们也需要对GBDT进行正则化，防止过拟合。GBDT的正则化主要有三种方式。第一种是和Adaboost类似的正则化项，即步长(learning rate)。定义为νν,对于前面的弱学习器的迭代

$f_{k}(x)=f_{k-1}(x)+h_{k}(x)$

如果我们加上了正则化项，则有

$f_{k}(x)=f_{k-1}(x)+\nu h_{k}(x)$

$\nu$ 的取值范围为0< $\nu$ ≤1。对于同样的训练集学习效果，较小的 $\nu$ 意味着我们需要更多的弱学习器的迭代次数。通常我们用步长和迭代最大次数一起来决定算法的拟合效果。

第二种正则化的方式是通过子采样比例（subsample），通常取值为(0,1]。注意这里的子采样和随机森林不一样，随机森林使用的是放回抽样，而这里是不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低，推荐在[0.5, 0.8]之间。

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

第三种是对于弱学习器即CART回归树进行正则化剪枝。

7.优缺点

GBDT优点主要有：

1）可以灵活处理各种类型的数据，包括连续值和离散值。

2）相对于SVM算法，在相对少的调参时间情况下，GBDT预测的准确率也可以比较高。

3）使用一些健壮的损失函数，对异常值的鲁棒性非常强。比如Huber损失函数和Quantile损失函数。

缺点主要有：

1）由于弱学习器之间存在依赖关系，难以并行训练数据。但是可以通过紫彩云的SGBT来达到部分并行。

8.sklearn参数

在scikit-learn中，GBDT类库包含GradientBoostingClassifier和GradientBoostingRegressor两个函数，其中，GradientBoostingClassifier用于GBDT分类，GradientBoostingRegressor用于GBDT回归。两者的参数完全相同，但是有些参数比如损失函数Loss的可选项并不相同，可以将参数分为两大类，第一类是Boosting框架的重要参数，第二类是弱学习器CART回归决策树的重要参数。下面，将从这两个方面进行介绍。

第一类：Boosting框架的重要参数

GBDT算法梳理_gbdt分类

第二类：弱学习器CART回归决策树的重要参数

1) 划分时考虑的最大特征数max_features: 可以使用很多种类型的值，默认是”None”,意味着划分时考虑所有的特征数；如果是”log2″意味着划分时最多考虑 $log_{2}N$ 个特征；如果是”sqrt”或者”auto”意味着划分时最多考虑 $\sqrt{N}$ 个特征。如果是整数，代表考虑的特征绝对数。如果是浮点数，代表考虑特征百分比，即考虑（百分比xN）取整后的特征数。其中N为样本总特征数。一般来说，如果样本特征数不多，比如小于50，我们用默认的”None”就可以了，如果特征数非常多，我们可以灵活使用刚才描述的其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间。

2) 决策树最大深度max_depth: 默认可以不输入，如果不输入的话，默认值是3。一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。常用的可以取值10-100之间。

3) 内部节点再划分所需最小样本数min_samples_split: 这个值限制了子树继续划分的条件，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分，默认是2。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。

4) 叶子节点最少样本数min_samples_leaf: 这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。默认是1,可以输入最少的样本数的整数，或者最少样本数占样本总数的百分比。如果样本量不大，不需要管这个值。如果样本量数量级非常大，则推荐增大这个值。

5）叶子节点最小的样本权重和min_weight_fraction_leaf：这个值限制了叶子节点所有样本权重和的最小值，如果小于这个值，则会和兄弟节点一起被剪枝。默认是0，就是不考虑权重问题。一般来说，如果我们有较多样本有缺失值，或者分类树样本的分布类别偏差很大，就会引入样本权重，这时我们就要注意这个值了。

6) 最大叶子节点数max_leaf_nodes: 通过限制最大叶子节点数，可以防止过拟合，默认是”None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到。

7) 节点划分最小不纯度min_impurity_split: 这个值限制了决策树的增长，如果某节点的不纯度(基于基尼系数，均方差)小于这个阈值，则该节点不再生成子节点。即为叶子节点。一般不推荐改动默认值1e-7。