xgboost（通俗理解）

待我称王封你为后i 2022-11-25 11:43 170阅读 0赞

原文链接：[https://www.jianshu.com/p/105faa5fb5c7][https_www.jianshu.com_p_105faa5fb5c7]

xgboost是时下热门的机器学习算法，在面试和竞赛中出现的频率非常高，但网上却没有一篇能够完全讲清楚的文章，因此，本文旨在用尽量少的公式，将xgboost讲清楚，明白，透彻。

## 1 背景知识 ##

xgboost是Boost（提升）算法家族中的一员，Boost根本思想在于通过多个简单的弱分类器，构建出准确率很高的强分类器。简单地来说，Boost（提升）就是指每一步我都产生一个弱预测模型，然后加权累加到总模型中，可以用于回归和分类问题。如果每一步的弱预测模型生成都是依据损失函数的梯度方向，则称之为梯度提升(Gradient boosting)，这样若干步以后就可以达到逼近损失函数局部最小值的目标。

boosting集成学习，由多个相关联的决策树联合决策，什么叫相关联，举个例子，有一个样本\[数据->标签\]是\[(2，4，5)-> 4\]，第一棵决策树用这个样本训练得预测为3.3，那么第二棵决策树训练时的输入，这个样本就变成了\[(2，4，5)-> 0.7\]，也就是说，下一棵决策树输入样本会与前面决策树的训练和预测相关。其中，0.7是模型预测和样本标记的差，称为残差。我们每次要学习的目标是上次学习的残差，直到残差小到满足我们的要求或其他终止条件。这个残差就是一个加预测值后能得真实值的累加量。

上面的例子，如果第二次直接预测得到0.7，并不一定好，因为每次走一小步逐渐逼近结果的效果，要比每次迈一大步很快逼近结果的方式更容易避免过拟合。换句话说我们思想不完全信任每一个棵残差树，我们认为每棵树只学到了真理的一小部分，累加的时候只累加一小部分，只有通过多学几棵树才能弥补不足。

> 举一个简单的例子，同样使用年龄进行分枝，假设我们A的真实年龄是18岁，但第一棵树的预测年龄是12岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁……以此类推学习下去

与之对比的是random forest（随机森林）算法，各个决策树是独立的、每个决策树在样本堆里随机选一批样本，随机选一批特征进行独立训练，各个决策树之间没有啥毛线关系。

## 2 初识xgboost ##

xgboost本质上就是k个CART树，k是一个正整数。

CART树也叫分类与回归树，是一种决策树，既能做分类任务也能做回归任务。分类树的输出是样本的类别， 回归树的输出是一个实数（连续型变量）。

回归树的运行流程与分类树基本类似，但有以下两点不同之处：

*  第一，回归树的每个节点得到的是一个预测值而非分类树式的样本计数，假设在某一棵树的某一节点使用了年龄进行分枝（并假设在该节点上人数>1，那么这个预测值就是属于这个节点的所有人年龄的平均值。
 *  第二，在分枝节点的选取上，回归树并没有选用最大熵值来作为划分标准，而是常用了最小化均方差，即
    
    ![Image 1][]
    
    这很好理解，被预测出错的次数越多，错的越离谱，均方差就越大，通过最小化均方差也就能够找到最靠谱的分枝依据。

对于回归问题，我们常用的损失函数是MSE（均方误差），即：

![Image 1][]

image

对于分类问题，我们常用的损失函数是对数损失函数：

![Image 1][]

image

前面提到，xgboost是具有k个CART树的集成学习算法，那么问题来了，我们应该怎么得到这k个树，k又是多少呢？（注意：不是随机得到k个树，是一个一个来，后一个依赖于前一个）

在我们一颗接着一颗树的构建过程中，我们的目标是：预测误差尽量小，叶子节点尽量少，节点数值尽量不极端。第一个目标很清晰，而第二个目标的原因是因为树的复杂度越低，泛化能力越强，在后面我们会知道叶子节点数量是树的复杂度计算中的一个考量，叶子节点数越多，树越复杂。节点数值尽量不极端指的是某棵树对一个样本的预测值相对于其它树对这个样本的预测值相差比较大，比如某个样本label数值为4，那么第一个回归树预测3，第二个预测为1；另外一组回归树，一个预测2，一个预测2，那么倾向后一种，为什么呢？前一种情况，第一棵树学的太多，太接近4，也就意味着有较大的过拟合的风险。

生成决策树：决策树算法相信大家都比较熟悉了，还不清楚的读者请先了解一下决策树算法。在xgboost中，生成决策树时，划分属性的方式如下：

![Image 1][]

为了更好的解释xgboost算法，我们必须定义一些公式了。

首先是模型的预测：

![Image 1][]

这里的K就是树的棵数，F表示所有可能的CART树，f表示一棵具体的CART树，f k(x i)表示样本x i在第k棵树上的预测值。这个模型由K棵CART树组成。

模型的目标函数：

![Image 1][]

第一部分就是损失函数，第二部分就是正则项。y i表示期望输出。关于第二部分的解释，我在网站找了个图，不过下边和上面的公式有点不一样，注意一下就好。

![Image 1][]

还记得xgboost树的生成过程吗？一棵接一棵是不是？那么，我们的目标函数的优化过程页应当如此：首先优化第一棵树，完了之后再优化第二棵树，直至优化完K棵树。整个过程如下

![Image 1][]

所以，对于第t棵树，它的目标函数就是

![Image 1][]

这里，我们把f t(x i)当做我们模型的变量参数，本身它表示样本xi在第t棵树上的预测值，这个预测值使我们经过第t棵决策树分类后再计算一下得到的，也就是说虽然分类了，但我们可以给他设不同的值（或者叫权值，一般用w表示），所以这个值就是优化模型过程中用到的参数之一。可以发现，目标函数是f t(x i)的一次式和二次式，而且一次式项的系数是残差，此时就是一个值。而且一次式和二次式的函数优化问题又是特别简单的，是不是很棒，很激动。

综上，我们可以将损失函数用以下函数表示：

![Image 1][]

但是，损失函数一定是二次函数吗？如果不是，就泰勒展开成二次，简单粗暴。

它背后的思路就是在损失函数上执行梯度下降，然后用基学习器对其进行拟合。当梯度为负时，我们称它为伪残差，因为它们依然能间接帮助我们最小化目标函数。

建树的过程中，在以下情况下完成这棵树的创建：  
（1）当引入的分裂带来的增益小于一个阀值的时候，我们可以剪掉这个分裂，所以并不是每一次分裂loss function整体都会增加的，有点预剪枝的意思。  
（2）当树达到最大深度时则停止建立决策树，设置一个超参数max\_depth，树太深很容易出现的情况学习局部样本，过拟合。  
（3）当样本权重和小于设定阈值时则停止建树。

## 3 XGBoost和GBDT的区别 ##

1）将树模型的复杂度加入到正则项中，来避免过拟合，因此泛化性能会好于GBDT。XGBoost的正则项会惩罚具有多个叶子节点的树结构。

2）损失函数是用泰勒展开式展开的，同时用到了一阶导和二阶导，可以加快优化速度。

3）和GBDT只支持CART作为基分类器之外，还支持线性分类器，在使用线性分类器的时候可以使用L1，L2正则化。

4）引进了特征子采样，像RandomForest那样，这种方法既能降低过拟合，还能减少计算。

5）在寻找最佳分割点时，考虑到传统的贪心算法效率较低，实现了一种近似贪心算法，用来加速和减小内存消耗，除此之外还考虑了稀疏数据集和缺失值的处理，对于特征的值有缺失的样本，XGBoost依然能自动找到其要分裂的方向。

6）XGBoost支持并行处理，XGBoost的并行不是在模型上的并行，而是在特征上的并行，将特征列排序后以block的形式存储在内存中，在后面的迭代中重复使用这个结构。这个block也使得并行化成为了可能，其次在进行节点分裂时，计算每个特征的增益，最终选择增益最大的那个特征去做分割，那么各个特征的增益计算就可以开多线程进行。

> 参考资料：  
> [https://blog.csdn.net/mxg1022/article/details/80702264][https_blog.csdn.net_mxg1022_article_details_80702264]  
> [https://blog.csdn.net/yinyu19950811/article/details/81079192][https_blog.csdn.net_yinyu19950811_article_details_81079192]  
> [https://www.cnblogs.com/jiangxinyang/p/9248154.html][https_www.cnblogs.com_jiangxinyang_p_9248154.html]  
> [https://www.jianshu.com/p/7467e616f227][https_www.jianshu.com_p_7467e616f227]  
> [https://blog.csdn.net/legendavid/article/details/78904353][https_blog.csdn.net_legendavid_article_details_78904353]

[https_www.jianshu.com_p_105faa5fb5c7]: https://www.jianshu.com/p/105faa5fb5c7
[Image 1]: 
[https_blog.csdn.net_mxg1022_article_details_80702264]: https://links.jianshu.com/go?to=https%3A%2F%2Fblog.csdn.net%2Fmxg1022%2Farticle%2Fdetails%2F80702264
[https_blog.csdn.net_yinyu19950811_article_details_81079192]: https://links.jianshu.com/go?to=https%3A%2F%2Fblog.csdn.net%2Fyinyu19950811%2Farticle%2Fdetails%2F81079192
[https_www.cnblogs.com_jiangxinyang_p_9248154.html]: https://links.jianshu.com/go?to=https%3A%2F%2Fwww.cnblogs.com%2Fjiangxinyang%2Fp%2F9248154.html
[https_www.jianshu.com_p_7467e616f227]: https://www.jianshu.com/p/7467e616f227
[https_blog.csdn.net_legendavid_article_details_78904353]: https://links.jianshu.com/go?to=https%3A%2F%2Fblog.csdn.net%2Flegendavid%2Farticle%2Fdetails%2F78904353