【ML-6-2】集成学习-boosting（xgboost ）

2024-03-23 11:59:58

一、XGBoost简介

1.1 什么是XGBoost

XGBoost全名叫（eXtreme Gradient Boosting）极端梯度提升，是陈天奇在GBDT的基础上提出的一种优化算法，也是一种集成算法。经常被用在一些比赛中，其效果显著。它是大规模并行boosted tree的工具，它是目前最快最好的开源boosted tree工具包。既可以用于分类也可以用于回归问题中。

1.2 直观案例解析

预测一家人对电子游戏的喜好程度，考虑到年轻和年老相比，年轻更可能喜欢电子游戏。男性和女性相比，男性更喜欢电子游戏，故先根据年龄大小区分小孩和大人，然后再通过性别区分开是男是女，逐一给各人在电子游戏喜好程度上打分，如下图所示。

我们知道对于单个的决策树模型容易出现过拟合，并且不能在实际中有效应用。所以出现了集成学习方法。如下图，通过两棵树组合进行玩游戏得分值预测。其中tree1中对小男生的预测分值为2，tree2对小男生的预测分值为0.9。则该小男生的最后得分值为2.9，使得最后得分更加准确。

看到上面，很容易想起GBDT树（文末进行详细比较）。

1.3 XGBoost的用途

用于回归和分类问题。

二、XGBoost的基本思路

2.1 XGBoost的核心算法思想：

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

2.2 损失函数

其中：

红色箭头所指向的L 即为损失函数（比如平方损失函数)
红色方框所框起来的是正则项（包括L1正则、L2正则）
红色圆圈所圈起来的为常数项
对于f(x)，XGBoost利用泰勒展开三项，做一个近似。f(x)表示的是其中一颗回归树。

2.3 计算过程

显然，我们的目标是要使得树群的预测值y尽量接近真实值yi，而且有尽量大的泛化能力。类似之前GBDT的套路，XGBoost也是需要将多棵树的得分累加得到最终的预测得分（每一次迭代，都在现有树的基础上，增加一棵树去拟合前面树的预测结果与真实值之间的残差）。

那接下来，我们如何选择每一轮加入什么 f 呢？答案是非常直接的，选取一个 f 来使得我们的目标函数尽量最大地降低。

这里 f 可以使用二阶泰勒展开公式近似。

进一步简化目标函数：

实质是把样本分配到叶子结点会对应一个obj，优化过程就是obj优化。也就是分裂节点到叶子不同的组合，不同的组合对应不同obj，所有的优化围绕这个思想展开。到目前为止我们讨论了目标函数中的第一个部分：训练误差（上面式子的前半部分）。第二个部分：正则项（后半部分），即如何定义树的复杂度。

2.3.1 正则项定义

XGBoost对树的复杂度包含了两个部分：
一个是树里面叶子节点的个数T
一个是树上叶子节点的得分w的L2模平方（对w进行L2正则化，相当于针对每个叶结点的得分增加L2平滑，目的是为了避免过拟合）

我们再进一步优化目标函数：

对目标函数进行改写，可以直接套用泰勒二阶展开式，具体为何用这个，请看附件二的问答

Obj越小越好

2.3.2 分裂节点

在上面的推导中，我们知道了如果我们一棵树的结构确定了，如何求得每个叶子结点的分数。但我们还没介绍如何确定树结构，即每次特征分裂怎么寻找最佳特征，怎么寻找最佳分裂点。

目标函数中的G/(H+λ)部分，表示着每一个叶子节点对当前模型损失的贡献程度，融合一下，得到Gain的计算表达式，如下所示：

Gain是分割前减分割后，当然论文中的这个表达式更加准确一些：

最简单的树结构就是一个节点的树。我们可以算出这棵单节点的树的好坏程度obj*。假设我们现在想按照年龄将这棵单节点树进行分叉，我们需要知道：

1）按照年龄分是否有效，也就是是否减少了obj的值

2）如果可分，那么以哪个年龄值来分。

此时我们就是先将年龄特征从小到大排好序，然后再从左到右遍历分割

这样的分割方式，我们就只要对样本扫描一遍，就可以分割出GL，GR，然后根据Gain的分数进行分割，极大地节省了时间。所以从这里看，XGBoost中从新定义了一个划分属性，也就是这里的Gain，而这个划分属性的计算是由其目标损失决定obj的。

2.3.3 分裂停止条件

凡是这种循环迭代的方式必定有停止条件，什么时候停止呢？简言之，设置树的最大深度、当样本权重和小于设定阈值时停止生长以防止过拟合。具体而言，则
当引入的分裂带来的增益小于设定阀值的时候，我们可以忽略掉这个分裂，所以并不是每一次分裂loss function整体都会增加的，有点预剪枝的意思，阈值参数为（即正则项里叶子节点数T的系数）；
当树达到最大深度时则停止建立决策树，设置一个超参数max_depth，避免树太深导致学习局部样本，从而防止过拟合；
样本权重和小于设定阈值时则停止建树。什么意思呢，即涉及到一个超参数-最小的样本权重和min_child_weight，和GBM的 min_child_leaf 参数类似，但不完全一样。大意就是一个叶子节点样本太少了，也终止同样是防止过拟合；

三，集成学习小结

3.1 bagging、boosting的联系和区别

Bagging和Boosting都是将已有的分类或回归算法通过一定方式组合起来，形成一个性能更加强大的分类器，更准确的说这是一种分类算法的组装方法。即将弱分类器组装成强分类器的方法。

首先介绍Bootstraping，即自助法：它是一种有放回的抽样方法（可能抽到重复的样本）。

3.2 、Bagging (bootstrap aggregating)

Bagging即套袋法，其算法过程如下：

A）从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（k个训练集之间是相互独立的）

B）每次使用一个训练集得到一个模型，k个训练集共得到k个模型。（注：这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）

C）对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

3.3、Boosting

其主要思想是将弱分类器组装成一个强分类器。在PAC（概率近似正确）学习框架下，则一定可以将弱分类器组装成一个强分类器。

关于Boosting的两个核心问题：

1）在每一轮如何改变训练数据的权值或概率分布？

通过提高那些在前一轮被弱分类器分错样例的权值，减小前一轮分对样例的权值，来使得分类器对误分的数据有较好的效果。

2）通过什么方式来组合弱分类器？

通过加法模型将弱分类器进行线性组合，比如AdaBoost通过加权多数表决的方式，即增大错误率小的分类器的权值，同时减小错误率较大的分类器的权值。

而提升树通过拟合残差的方式逐步减小残差，将每一步生成的模型叠加得到最终模型。

3.4，随机森林和GBDT的区别：

（Gradient Boost Decision Tree 梯度提升决策树）GBDT的核心就在于：每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。

训练集选取：随机森林采用的Bagging思想，而GBDT采用的Boosting思想。这两种方法都是Bootstrap思想的应用，Bootstrap是一种有放回的抽样方法思想。虽然都是有放回的抽样，但二者的区别在于：Bagging采用有放回的均匀取样，而Boosting根据错误率来取样（Boosting初始化时对每一个训练样例赋相等的权重1／n，然后用该算法对训练集训练t轮，每次训练后，对训练失败的样例赋以较大的权重），因此Boosting的分类精度要优于Bagging。Bagging的训练集的选择是随机的，各训练集之间相互独立，弱分类器可并行，而Boosting的训练集的选择与前一轮的学习结果有关，是串行的；

决策树类型：组成随机森林的树可以是分类树，也可以是回归树；而GBDT只能由回归树（CART）组成；

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

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

异常值：随机森林对异常值不敏感；GBDT对异常值非常敏感；

方差/偏差：随机森林是通过减少模型方差提高性能；GBDT是通过减少模型偏差提高性能。

3.5 、GBDT 与 XGBOOST的比较（ xgboost为什么快？xgboost如何支持并行？）：
支持多样化：传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题），而且是结合了自身特性（比如树的大小和权值信息）。
导数：传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。而XGBoost损失函数对误差部分做二阶泰勒展开，更加准确。算法本身的优化是我们后面讨论的重点。
正则项：xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（补充：传统GBDT的实现也有学习速率）
列抽样（column subsampling）：xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
对缺失值的处理：对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。，论文中的default direction（具体做法时，遍历的尝试将所有的缺失值分裂到所有方向{left or right}，split and default directions with max gain）
xgboost工具支持并行：boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
block机制：空间争取时间的优化方式，XGBOOST提出了block的概念，简单的说将排序后的特征值放在block中，以后划分特征的时候，只需要遍历一次即可，因为决策树在处理属性值时，需要将属性值先排序，这是最耗时的步骤，而block预先存储了排序的特征值，在后续过程中可以重复利用这个结构中的数据，同时，计算每个特征的划分增益可以并行处理了。Collecting statistics for each column can be parallelized,giving us a parallel algorithm for split finding!!
近似直方图计算：贪心算法在选择最佳划分方式时需要遍历所有的划分点子集，在数据非常大时，这会非常低效，xgboost提出了近似直方图计算，根据数据的二阶导信息进行排序，提出一些候选划分点子集。用于高效地生成候选的分割点。

附件一：参考文献

xgboost原始论文：https://arxiv.org/pdf/1603.02754v1.pdf
xgboost作者讲义PPT：https://homes.cs.washington.edu/~tqchen/pdf/BoostedTree.pdf
xgboost原理：https://blog.csdn.net/a819825294/article/details/51206410
xgboost入门与实战（原理篇）：https://blog.csdn.net/sb19931201/article/details/52557382
怎样通俗的理解泰勒级数？：https://www.zhihu.com/question/21149770

附件二：问题答疑（考点）

1.XGboost进行了什么样的修改使得他可以用其他类型的弱学习器呢？

——XGBoost将损失函数关于弱学习器的一阶和二阶导数单独列出来，那么后续就可以直接使用这些一阶和二阶导数来做训练拟合，而不用关注于弱学习器的具体形式了。当然目前主要还是决策树弱学习器最主流。

2.xgb的近似划分中的 global和local的区别，论文中具体的划分说是按照二阶导来选择划分点的，这和global和local有什么关系呢

Global：在训练初期，就找好每个特征得分位点，然后在后续的训练中，分位点不变。

local：训练开始前找好每个特征得分位点，每次分枝，都会改变每个叶子节点样本的分布，根据该分枝中所有的样本，重新计算每个特征的分位点。

local比Global精度要高，所以在同等精度下，global需要在一起开分割的更细，也就是分位点更多。设定好global还是local后，通过计算每个样本在该特征得二阶导数作为权重来设置分位点。

3.XGboost假如用决策树解决回归问题，用的损失函数不是平方差损失，

（1）我们只对g(x), h (x) 计算而不进行拟合，而GBDT先计算g(x)再用决策树拟合g(x)呢？

（2）每次迭代建立决策树输出的是不是只是各样本点的误差拟合值，而不是误差梯度拟合值呢？

（3）是不是每次迭代针对样本点只生成一个树，并且输出的是各样本点的误差值？

a.GBDT只拟合g(x)，拟合时不考虑h(x) ，而XGBoost 对g(x), h (x) 计算而不进行拟合

c.是的，回归的话，每次迭代一颗决策树。

4.XGboost针对多分类问题

（1）XGboost是不是和GBDT一样，一个特征建立一个树，每一次迭代生成K个特征对应的k个树，而不同的仅仅是分裂根节点的依据和输出值的计算不同呢？

（2）XGboost第一次迭代中，对于第一个特征来说建立树过程中所依赖的各样本点的g(x),h(x)和对于第二个特征来说建立树过程中所依赖的各样本点的g(x),h(x)是否是不一样的呢？

a. 和GBDT类似，如果是k个类别，那么每轮迭代会生成k颗决策树，如果迭代T轮，则最后一共是T*k颗决策树。不是你说的k个特征就是k颗决策树。其余的表述都是对的。

b. g(x),h(x)只和样本有关，和样本的特征不同无关，所以你说的2个特征，那么对应的g(x),h(x)是一样的。

5.XGBoost建立决策树时，每分裂一个节点时都要重新计算该节点区域内所有样本点特征的最佳特征和最佳切分点吧？

对的。

6.XGBoost对于缺失值的处理时，缺失值不参与分裂根节点判断依据的计算，而有效的样本从大到小排序和从小到大排序的计算完全对称，这个怎么判断缺失值放在左节点好还是右节点好呢？

XGBoost对这个处理做了简化，即在所有缺失值样本整体进左子树 vs 所有缺失值样本整体进右子树中二选一。没有判断部分缺失值放在左节点好还是右节点好。

7、为什么xgboost要用泰勒展开，优势在哪里？

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

更进一步，引用的知乎答主宋佳慧的话，说：
实际上使用二阶泰勒展开是为了xgboost能够自定义loss function，如果按照最小二乘法的损失函数直接推导，同样能够得到xgboost最终的推导式子：

二阶泰勒展开实际不是约等于最小二乘法，平方损失函数的二阶泰勒展开=最小二乘法。但为何想用二阶泰勒展开呢，一方面是为了xgboost库的可扩展性，因为任何损失函数只要二阶可导即能复用xgboost所做的关于最小二乘法的任何推导。而且泰勒的本质是尽量去模仿一个函数，毕竟二阶泰勒展开已经足以近似大量损失函数了，典型的还有基于分类的对数似然损失函数。

这样同一套代码就能完成回归或者分类了，而不是每次都推导一番，重写训练代码。

此外，Xgboost官网上有说，当目标函数是MSE时，展开是一阶项（残差）+二阶项的形式（官网说这是一个nice form），而其他目标函数，如log loss的展开式就没有这样的形式。为了能有个统一的形式，所以采用泰勒展开来得到二阶项，这样就能把MSE推导的那套直接复用到其他自定义损失函数上。简短来说，就是为了统一损失函数求导的形式以支持自定义损失函数。当然，这是从为什么会想到引入泰勒二阶的角度来说的。

8 . xgboost怎么给特征评分？

xgboost作者在其原始论文中给出了两种分裂节。枚举所有不同树结构的贪心法

现在的情况是只要知道树的结构，就能得到一个该结构下的最好分数，那如何确定树的结构呢？

一个想当然的方法是：不断地枚举不同树的结构，然后利用打分函数来寻找出一个最优结构的树，接着加入到模型中，不断重复这样的操作。而再一想，你会意识到要枚举的状态太多了，基本属于无穷种，那咋办呢？

我们试下贪心法，从树深度0开始，每一节点都遍历所有的特征，比如年龄、性别等等，然后对于某个特征，先按照该特征里的值进行排序，然后线性扫描该特征进而确定最好的分割点，最后对所有特征进行分割后，我们选择所谓的增益Gain最高的那个特征，而Gain如何计算呢？

根据损失函数：

换句话说，目标函数中的G/(H+λ)部分，表示着每一个叶子节点对当前模型损失的贡献程度，融合一下，得到Gain的计算表达式，如下所示：

第一个值得注意的事情是"对于某个特征，先按照该特征里的值进行排序"，这里举个例子。

比如设置一个值a，然后枚举所有x < a、a < x这样的条件（x代表某个特征比如年龄age，把age从小到大排序：假定从左至右依次增大，则比a小的放在左边，比a大的放在右边），对于某个特定的分割a，我们要计算a左边和右边的导数和。

比如总共五个人，按年龄排好序后，一开始我们总共有如下4种划分方法：

①把第一个人和后面四个人划分开

②把前两个人和后面三个人划分开

③把前三个人和后面两个人划分开

④把前面四个人和后面一个人划分开

接下来，把上面4种划分方法全都各自计算一下Gain，看哪种划分方法得到的Gain值最大则选取哪种划分方法，经过计算，发现把第2种划分方法"前面两个人和后面三个人划分开"得到的Gain值最大，意味着在一分为二这个第一层层面上这种划分方法是最合适的。

换句话说，对于所有的特征x，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和GL和GR。然后用计算Gain的公式计算每个分割方案的分数就可以了。

然后后续则依然按照这种划分方法继续第二层、第三层、第四层、第N层的分裂。

第二个值得注意的事情就是引入分割不一定会使得情况变好，所以我们有一个引入新叶子的惩罚项。优化这个目标对应了树的剪枝，当引入的分割带来的增益小于一个阀值γ的时候，则忽略这个分割。换句话说，当引入某项分割，结果分割之后得到的分数 - 不分割得到的分数得到的值太小（比如小于我们的最低期望阀值γ），但却因此得到的复杂度过高，则相当于得不偿失，不如不分割。即做某个动作带来的好处比因此带来的坏处大不了太多，则为避免复杂多一事不如少一事的态度，不如不做。相当于在我们发现"分"还不如"不分"的情况下后（得到的增益太小，小到小于阈值γ），会有2个叶子节点存在同一棵子树上的情况。

下面是论文中的算法

近似算法

就职于Google的读者crab6789点评：

把样本从根分配到叶子结点，就是个排列组合。不同的组合对应的cost不同。求最好的组合你就要try，一味穷举是不可能的，所以才出来贪婪法。不看从头到尾就看当下节点怎么分配最好。这才有了那个greddy exact 方法，后来还想加速才有了histogram的做法。

实验代码可见：

https://github.com/yifanhunter/ML