集成学习专题（二）

GBDT

GBDT是集成学习Boosting的一种。Gradient Boosting的主要的思想是，每一次建立单个学习器时，是在之前建立的模型的损失函数的梯度下降方向。损失函数越大，说明模型越容易出错，如果我们的模型能够让损失函数持续下降，则说明我们的模型在不停的改进，而最好的方式就是让损失函数在其梯度的方向上下降。

GBDT的核心就在于，每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。所以为了得到残差，GBDT中的树都是回归树，不是分类树。

GBDT的算法流程

输入是训练集样本，最大迭代次数T，每轮迭代输入数据是训练集无放回采样样本，损失函数L。

1. 初始化弱学习器。

$$T(x;\theta_m)$$

T表示决策树，x为输入样本，$\theta_m$为树分裂参数。

1. 对迭代轮数m = 1,2,…,T有：

（a）计算各个叶子区域损失函数L的负梯度值，将它作为残差的估计

$$r_{mi} = -[\frac{\partial L(y,f(x_i))}{\partial f(x_i)}]_{f(x)=f_{m-1}(x)}$$

（b）对$r_{mi}$拟合为一颗新的回归树，根据新的回归树得到m轮产生的叶子节点区域

（c）遍历回归树所有叶子节点区域，在各个区域使损失函数极小化找到残差

（d）更新强学习器

1. 得到输出的最终模型

$$f_M(x) = \sum_{m =1}^M T(x;\theta_m)$$

GBDT常用的损失函数

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

（1） 指数损失函数：$L(y,h(x)) = \exp(-yh(x))$

（2） 对数损失函数：分为二元分类和多元分类两种。

• 对于二元分类：$L(y,h(x)) = \log(1+\exp(-yh(x)))$
• 对于多元分类：设类别数为k， $L(yk,h(x)) = -\sum{k=1}^Ky_k\log(p_k(x))$，$y_k$为样本数据估计值，当一个样本x属于k时，$y_k=1$，否则$y_k=0$

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

1. 均方差：$L(y,h(x)) =(y-h(x))^2$

2. 绝对损失：$L(y,h(x)) = |y-h(x)|$

3. Huber损失：它是均方差和绝对损失的折衷产物，对于远离中心的异常点，采用绝对损失，而中心附近的点采用均方差。这个界限一般用分位数点度量

   $$L(y,f(x))= \begin{cases} \frac{1}{2}(y-f(x))^2&|y-f(x)|\le \delta\\ \delta(|y-f(x)|-\frac{\delta}{2})&|y-f(x)|\gt \delta \end{cases}$$

4. 分位树损失：它对应的是分位数回归的损失函数。

$$L(y,f(x)) = \sum_{y\ge f(x)}\theta|y-f(x)|+\sum_{y\lt f(x)}(1-\theta)|y-f(x)|$$

GBDT中为什么用负梯度来拟合残差计算

其实除了均方误差的情况一阶导是残差外，其他的情况没有残差的概念，GBDT每一轮拟合的都是损失函数负梯度。

使用梯度计算代替的主要原因是为了将GBDT扩展到更复杂的损失函数中。

当损失函数形式简单，可以认为$y^{‘}（模型输出值）= y（实际值）$时损失函数最小，但当损失函数加入了正则项后，并非$y^{‘}=y$时损失函数取得最小值，所以我们需要计算损失函数的梯度，而不能直接使用模型来计算残差。

GBDT不适合使用高维稀疏特征的原因

1. 特征太多，GBDT不一定跑的动，即使可以跑也会耗费时间，因为在每一次分割时需要比较大量的特征。
2. 树的分割往往只考虑了少量特征，大部分特征用不到，少量的特征在多次分裂时被重复用到，剩余的长尾基本用不到，所有高维稀疏特征会造成大量特征的浪费。

GBDT减少误差的方式

机器学习算法的误差分为偏差和方差两个部分。

GBDT迭代每一步都在拟合当前模型预测值和真实值之间的偏差，通过不断的迭代使偏差减小，所以只要选取方差较小的模型作为基分类器，GBDT就可以很好的减小预测误差。

GBDT的优缺点

GBDT主要的优点有：

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

（2）在相对少的调参时间情况下，预测的准确率也可以比较高

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

GBDT的主要缺点有：

（1）由于弱学习器之间存在依赖关系，难以并行训练数据。

GBDT如何进行正则化

第一种正则化方式为步长（learning rate）。定义为v，对于前面的弱学习器的迭代

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

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

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

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

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

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

GBDT如何构建特征

GBDT本身是不能产生特征的，但是我们可以利用GBDT去产生特征的组合，其主要思想是GBDT每棵树的路径直接作为其他模型的输入特征使用，例如输入逻辑回归模型。

用已有特征训练GBDT模型，然后利用GBDT模型学习到的树来构造新特征，最后把这些新特征加入原有特征一起训练模型。构造的新特征向量是取值0/1的，向量的每个元素对应于GBDT模型中树的叶子结点。当一个样本点通过某棵树最终落在这棵树的一个叶子结点上，那么在新特征向量中这个叶子结点对应的元素值为1，而这棵树的其他叶子结点对应的元素值为0。新特征向量的长度等于GBDT模型里所有树包含的叶子结点数之和。

上图的两棵树是GBDT学习到的，第一棵树有3个叶子结点，而第二棵树有2个叶子结点。对于一个输入样本点x，如果它在第一棵树最后落在其中第二个叶子结点，而在第二棵树里最后落在其中的第一个叶子结点。那么通过GBDT获得的新特征向量为[0,1,0,1,0]，其中向量中的前三位对应第一棵树的3个叶子结点，后两位对应第二棵树的2个叶子结点，原来的特征一起组合成为新的组合特征进行训练。实验证明这样会得到比较显著的提升模型效果。

经验证，树的数量最多500棵（500以上就没有提升了），每棵树的节点不多于12。

GBDT如何用于分类

GBDT无论用于分类还是回归一直都是使用的CART回归树。不会因为我们所选择的任务是分类任务就选用分类树。由于GBDT每轮的训练是在上一轮的训练的残差基础之上进行训练的。这里的残差就是当前模型的负梯度值。这个要求每轮迭代的时候，弱分类器的输出结果相减是有意义的，即残差相减是有意义的。

如果选用的弱分类器是分类树，类别相减是没有意义的。上一轮输出的是样本x属于A类，本一轮训练输出的是样本x属于B类。A和B很多时候甚至都没有比较的意义，A类-B类是没有意义的。

首先，我们在训练的时候，是针对样本X每个可能的类都训练一个分类回归树。举例说明，目前样本有三类，也就是K = 3。样本x属于第二类。那么针对该样本x的分类结果，其实我们可以用一个三维向量[0,1,0]来表示。0表示样本不属于该类，1表示样本属于该类。由于样本已经属于第二类了，所以第二类对应的向量维度为1，其他位置为0。

针对样本有三类的情况，我们实质上是在每轮的训练的时候是同时训练三棵树。第一棵树针对样本x的第一类，输入为(x,0)。第二棵树输入针对样本x的第二类，输入为(x,1)。第三棵树针对样本x的第三类，输入为(x,0)。

在这里每棵树的训练过程其实就是CART TREE的生成过程。按照生成树的流程可以解出三棵树，以及三棵树对x类别的预测$f_1(x),f_2(x),f_3(x)$。那么在此类训练中，我们仿照多分类的逻辑回归，使用softmax来产生概率，则属于类别1的概率：

$$p_1 = exp(f_1(x))/\sum_{k=1}^3\exp(f_k(x))$$

并且我们可以针对类别1求出残差$y{11}(x) =0-p_1(x)$;类别2求出残差$y{22} =1-p2(x)$;类别3求出残差$y{33}(x) = 0-p_3(x)$。

然后开始第二轮训练 针对第一类输入为$(x,y{11}(x))$，针对第二类输入为$(x,y{22}(x))$，针对第三类输入为$(x,y_{33}(x))$，继续训练出三棵树。一直迭代M轮。每轮构建3棵树，进行T轮迭代后，生成3*T棵树，样本属于某个类别的概率为：

$$p_c = \exp(f_c(x))/\sum_{k=1}^3exp(f_k(x))$$

GBDT需要调试的参数

GBDT训练中需要调试的参数如下：

1. n_estimators：也就是弱学习器的最大迭代次数，或者说最大弱学习器的个数。一般来说n_estimators太小，容易欠拟合，n_estimators太大，容易过拟合，一般选择一个适中的数值。
2. learning_rate：即每个弱学习器的权重缩减系数v，也称步长。
3. subsample：不放回抽样。如果取值为1，则全部样本都使用，等于没有使用子采样。如果取值小于1，则只有一部分样本会去做GBDT的决策树拟合。
4. max_features允许单个决策树使用特征的最大数量。
5. max_depth决策树最大深度

默认决策树在建立子树的时候不会限制子树的深度

1. min_sample_split 内部节点再划分所需最小样本数

内部节点再划分所需最小样本数，如果某节点的样本数少于min_samples_split，则不会继续再尝试选择最优特征来进行划分。

1. min_samples_leaf 叶子节点最少样本数

这个值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。

1. max_leaf_nodes 最大叶子节点数

通过限制最大叶子节点数，可以防止过拟合，默认是“None”，即不限制最大的叶子节点数。如果加了限制，算法会建立在最大叶子节点数内的最优的决策树。

1. min_impurity_split 节点划分最小不纯度

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

XGBoost

Xgboost算法思想

该算法就是不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数，最后只需要将每棵树对应的分数加起来就是该样本的预测值。

如下图例子，训练出了2棵决策树，小孩的预测分数就是两棵树中小孩所落到的结点的分数相加。爷爷的预测分数同理。

分裂结点问题上，XGBoost使用了和CART回归树一样的想法，利用贪婪算法，遍历所有特征的所有特征划分点，不同的是评价函数（分裂后的目标函数值比单子叶子节点的目标函数的增益，CART是MSE），同时限制树生长过深，还加了阈值，当增益大于阈值才能进行分裂。

Xgboost使用泰勒展开的优势

Xgboost使用了一阶和二阶偏导，二阶导数有利于梯度下降的更快更准，使用泰勒展开取得函数做自变量的二阶导数形式，可以在不选定损失函数具体形式的情况下，仅仅依靠输入数据的值就可以进行叶子节点分裂优化计算，本质上也就把损失函数的选取和模型算法优化/参数选择分开了。这种去耦合增加了xgboost的适用性，使得它按需选取损失函数，可以用于分类，也可以用于回归。

Xgboost如何寻找最优特征

Xgboost在训练的过程中给出各个特征的增益评分，最大增益的特征会被选出来作为分裂依据，从而记忆了每个特征对在模型训练时的重要性，从根到叶子中间节点涉及某特征的次数作为该特征重要性排序。

Xgboost的采样

Xgboost属于boosting集成学习方法，样本是不放回的，因而每轮计算样本不重复。另一方面，Xgboost支持子采样，也就是每轮计算可以不使用全部样本，以减少过拟合，进一步地，Xgboost还有列采样，每轮计算按百分比随机采样一部分特征，既提高计算速度又减少过拟合。

Xgboost中树的剪枝

首先看Xgboost分裂的决策函数：

$$Gain =\frac{1}{2}[\frac{G_L^2}{H_L+\lambda}+\frac{G_R^2}{H_R+\lambda}-\frac{(G_L+G_R)^2}{H_L+H_R+\lambda}]-\gamma$$

其中第一项为树的左孩子的分数，第二项为树的右孩子的分数，第三项为没有分裂的分数，$\gamma$在这里实际上是一个临界值，它的值越大，表示我们对切分后损失函数下降幅度要求越严。这个值也是可以在xgboost中设定的。Gain是正的，并且值越大，就越值得切分。

每一次分类选择Gain值最大的分裂方式，可以通过调节$\gamma$值的大小来改变树的分裂倾向，实现预剪枝。

其次Xgboost会在完整生成一棵决策树后回溯剪枝。

注意：xgboost的切分操作和普通的决策树切分过程是不一样的。普通的决策树在切分的时候并不考虑树的复杂度，而依赖后续的剪枝操作来控制。xgboost在切分的时候就已经考虑了树的复杂度，就是那个γ参数。所以，它不需要进行单独的剪枝操作。

Xgboost对缺失值的处理

当数据中含有缺失值的时候，我们可以不再填充缺失值。利用Xgboost的机制自动处理缺失值。

Xgboost的处理方式是，缺失值数据会被分到左子树和右子树分别计算损失，选择较优的那个。如果训练中没有数据缺失，预测时出现了数据缺失，默认分类到右子树。

Xgboost训练通常调整的参数

Xgboost训练需要调整的参数：

1. booster：选择每次迭代的模型，有两种选择：

• gbtree：基于树的模型

• gbliner：线性模型

1. n_estimatores：总共迭代的次数，即决策树的个数
2. eta：学习率，通过减少每一步的权重，可以提高模型的鲁棒性。
3. max_depth：树的深度
4. min_child_weight：决定最小叶子节点样本权重和
5. max_leaf_nodes：树上最大的节点或者叶子的数量
6. gamma：

在节点分裂时，只有分裂后损失函数的值下降了，才会分裂这个节点。

Gamma指定了节点分裂所需的最小损失函数下降值。

这个参数的值越大，算法越保守。这个参数的值和损失函数息息相关，所以是需要调整的。

1. lambda：权重的L2正则化项
2. alpha：权重的L1正则化项
3. objective：这个参数定义需要被最小化的损失函数
4. eval_metric：对于有效数据的度量方法

XGBoost和GBDT的异同

Xgboost/GBDT在调参数时为什么树的深度很少就能达到很高的精度，而随机森林需要的深度相对较高？

Xgboost/GBDT是基于Boosting思想的集成学习方法，随机森林是基于Bagging思想的集成学习方法。Boosting主要关注降低偏差，Bagging主要关注降低方差。

Bagging算法是这样做的：每个分类器都随机从原样本中做有放回的采样，然后分别在这些采样后的样本上训练分类器，然后再把这些分类器组合起来，简单的多数投票一般就可以。代表算法是随机森林。Boosting的意思是这样，他通过迭代地训练一系列的分类器，每个分类器采用的样本分布都和上一轮的学习结果有关。其代表算法是Adaboost，GBDT。

机器学习算法来说，其泛化误差可以分解为两部分，偏差和方差。

偏差指的是算法的期望预测与真实预测之间的偏差程度，反应了模型本身的拟合能力；方差度量了同等大小的训练集的变动导致学习性能的变化，刻画了数据扰动所导致的影响。

当模型越复杂时，拟合的程度就越高，模型的训练偏差就越小。但此时如果换一组数据可能模型的变化就会很大，即模型的方差很大。所以模型过于复杂的时候会导致过拟合。

当模型越简单时，即使我们再换一组数据，最后得出的学习器和之前的学习器的差别就不那么大，模型的方差很小。还是因为模型简单，所以偏差会很大。

对于Bagging算法来说，由于我们会并行地训练很多不同的分类器的目的就是降低这个方差，因为采用了相互独立的基分类器多了以后，方差的值会减小，所以对于每个基分类器来说，目标就是如何降低这个偏差，所以我们会采用深度很深甚至不剪枝的决策树。

对于Boosting来说，每一步我们都会在上一轮的基础上更加拟合原数据，所以可以保证偏差，所以可以保证偏差，对于每个基分类器来说，问题就在于如何选择方差更小的分类器，即更简单的分类器，所以我们选择深度很浅的决策树。

Xgboost和GBDT的区别

1. 传统GBDT以CART作为基分类器，Xgboost还支持线性分类器，这个时候Xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。

2. 传统GBDT在优化时只用到一阶导数信息，Xgboost则对代价函数进行二阶泰勒展开，同时用到了一阶和二阶导数。

3. Xgboost在代价函数里加入了正则项，用于控制模型的复杂度，损失函数如下：

   $$Obj = \sum_{i=1}^n l(y_i,\hat{y_i})+\sum_{k=1}^K\Omega(f_k)$$

   正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。

   $$\Omega(f_t) = \gamma T+\frac{1}{2}\lambda \sum_{j=1}^T w_j^2$$

4. Xgboost支持列抽样

Xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。

传统的GBDT在每轮迭代时使用全部的数据。

1. 传统的GBDT没有设计对缺失值进行处理，Xgboost能够自动学习出缺失值的处理策略。

2. Xgboost工具支持并行

Xgboost的并行不是tree粒度的并行，Xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。Xgboost的并行是在特征粒度上的。决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），Xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

可并行的近似直方图算法：

树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以Xgboost提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。