Xgboost完全详细解读（原理+代码）-bros是什么牌子

 

本文首发公众号：NLP从入门到放弃

文中涉及到的代码直接去仓库：DA-southampton/NLP_ability

0.提升树

首先要明确一点，xgboost 是基于提升树的。

什么是提升树，简单说，就是一个模型表现不好，我继续按照原来模型表现不好的那部分训练第二个模型，依次类推。

来几个形象的比喻就是：

做题的时候，第一个人做一遍得到一个分数，第二个人去做第一个人做错的题目，第三个人去做第二个人做错的题目，以此类推，不停的去拟合从而可以使整张试卷分数可以得到100分（极端情况）。

把这个比喻替换到模型来说，就是真实值为100，第一个模型预测为90，差10分，第二个模型以10为目标值去训练并预测，预测值为7，差三分，第三个模型以3为目标值去训练并预测，以此类推。

1. xgboost原理解读

1.0 学习路径：

我们xgboost的学习路径可以按照下面四个步骤来：

构造原始目标函数问题： xgboost目标函数包含损失函数和基于树的复杂度的正则项；泰勒展开问题： 原始目标函数直接优化比较难，如何使用泰勒二阶展开进行近似；树参数化问题： 假设弱学习器为树模型，如何将树参数化，并入到目标函数中；这一步的核心就是要明白我们模型优化的核心就是优化参数，没有参数怎么训练样本，怎么对新样本进行预测呢？如何优化化简之后的目标函数问题： 优化泰勒展开并模型参数化之后的的目标函数，主要包含两个部分： 如何求得叶子节点权重如何进行树模型特征分割

1.1 目标函数

1.1.0 原始目标函数

目标函数，可以分为两个部分，一部分是损失函数，一部分是正则（用于控制模型的复杂度）。

xgboost属于一种前向迭代的模型，会训练多棵树。

对于第t颗树，第i个样本的，模型的预测值是这样的：

yi^(t)=∑k=1tfk(xi)=yi^(t−1)+ft(xi)\hat{y_{i}}^{(t)} = \sum_{k=1}^{t}f_{k}(x_{i}) = \hat{y_{i}}^{(t-1)}+f_{t}(x_{i}) \\注解：是第次迭代之后样本的预测结果；是第颗树的模型预测结果是第颗树的预测结果；注解：yi^(t)是第t次迭代之后样本i的预测结果；ft(xi)是第t颗树的模型预测结果yi^(t−1)是第t−1颗树的预测结果；\\注解：\hat{y_{i}}^{(t)}是第t次迭代之后样本i的预测结果；f_{t}(x_{i})是第t颗树的模型预测结果\\\hat{y_{i}}^{(t-1)}是第t-1颗树的预测结果；\\ \\

进一步，我们可以得到我们的原始目标函数，如下：

Obj=∑i=1nl(yi,y^i)+∑j=1tΩ(fj)Obj=\sum_{i=1}^{n}l(y_{i},\hat{y}_{i})+\sum_{j=1}^{t}\Omega(f_{j}) \\是我们模型的损失函数，是整个模型对第个样本的预测值，是第个样本的真实值l(yi,y^i)是我们模型的损失函数，y^i是整个模型对第i个样本的预测值，yi是第i个样本的真实值l(y_{i},\hat{y}_{i})是我们模型的损失函数，\hat{y}_{i}是整个模型对第i个样本的预测值，y_{i}是第i个样本的真实值 \\注解：是全部颗树的复杂度求和，在这里我们是当成了函数中的正则化项注解：∑j=1tΩ(fj)是全部t颗树的复杂度求和，在这里我们是当成了函数中的正则化项;\\注解：\sum_{j=1}^{t}\Omega(f_{j})是全部t颗树的复杂度求和，在这里我们是当成了函数中的正则化项; \\

从这个目标函数我们需要掌握的细节是，前后部分是两个维度的问题

两个累加的变量是不同的:

一个是i，i这边代表的是样本数量，也就是对每个样本我们都会做一个损失的计算，这个损失是第t个树的预测值和真实值之间的差值计算（具体如何度量损失视情况而定）。

另一个是累加变量是j，代表的是树的数量，也就是我们每个树的复杂度进行累加。

需要注意的是我们这里具体的损失函数是没有给出定义的，所以它可以是树模型，也可以是线性模型。

1.1.1 简单化简损失函数

正如上面所说，Xgboost是前向迭代，我们的重点在于第t个树，所以涉及到前t-1个树变量或者说参数我们是可以看做常数的。

所以我们的损失函数进一步可以化为如下，其中一个变化是我们对正则项进行了拆分，变成可前t-1项，和第t项：

Obj(t)=∑i=1nl(yi,y^i(t))+∑j=1tΩ(fj)Obj^{(t)}=\sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{(t)})+\sum_{j=1}^{t}\Omega(f_{j}) \\=∑i=1nl(yi,y^i(t−1)+ft(xi))+∑j=1tΩ(fj)=\sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{(t-1)}+f_{t}(x_{i}))+\sum_{j=1}^{t}\Omega(f_{j}) \\=∑i=1nl(yi,y^i(t−1)+ft(xi))+Ω(ft)+constant=\sum_{i=1}^{n}l(y_{i},\hat{y}_{i}^{(t-1)}+f_{t}(x_{i}))+\Omega(f_{t})+constant \\

基于此，在不改变目标函数精读的情况下，我们已经做了最大的简化，最核心的点就是我们认为前t-1个树已经训练好了，所以涉及到的参数和变量我们当成了常数。

接下来，我们使用泰勒级数，对目标函数近似展开.

1.2 泰勒公式对目标函数近似展开

使用泰勒公式进行近似展开的核心目标是就是对目标函数进行化简，将常数项抽离出来。

基本泰勒公式展开如下：

注解：此公式是对在点处进行的泰勒二阶展开f(x+Δx)≃f(x)+f′(x)Δx+12f″(x)Δx2注解：此公式是对f(x+Δx)在点x处进行的泰勒二阶展开f(x+\Delta x) \simeq f(x)+ f(x)\Delta x+\frac{1}{2}f(x)\Delta x^{2}\\注解：此公式是对f(x+\Delta x) 在点x处进行的泰勒二阶展开 \\

损失函数展开公式细节推导如下：

对应的是第颗树的模型，对应的是，Δx对应的是第t颗树的模型ft(xi)，x对应的是yi^(t−1)，\Delta x 对应的是第t颗树的模型f_{t}(x_i)，x对应的是\hat{y_{i}}^{(t-1)}， \\相应的对应到损失函数应该是相应的f(x)对应到损失函数应该是l(yi,yi^(t−1)+ft(xi))相应的f(x)对应到损失函数应该是l(y_{i},\hat{y_{i}}^{(t-1)}+f_{t}(x_{i})) \\

所以原有公式进行泰勒公式二阶展开，结果为:

l(yi,yi^(t−1)+ft(xi))=l(yi,yi^(t−1))+gift(xi)+12hift2(xi)l(y_{i},\hat{y_{i}}^{(t-1)}+f_{t}(x_{i}))=l(y_{i},\hat{y_{i}}^{(t-1)})+g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^2(x_{i}) \\注解：对应的是损失函数一阶导数，为二阶导数注解：gi对应的是损失函数一阶导数，hi为二阶导数注解：g_{i}对应的是损失函数一阶导数，h_{i}为二阶导数 \\

进而我们可以得到目标函数展开公式为如下：

Obj(t)≃∑i=1n[l(yi,yi^(t−1))+gift(xi)+12hift2(xi)]+Ω(ft)+constantObj^{(t)}\simeq \sum_{i=1}^{n}[l(y_{i},\hat{y_{i}}^{(t-1)})+g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^2(x_{i})]+\Omega(f_{t})+constant \\

还是那句话，我们可以使用任意一个损失函数，这里没有定式。

上述中树的表达我们都是使用函数f(x)来表示，本质上模型的优化求解是在求参数，所以我们需要对树模型参数化才可以进行进一步的优化

1.3 树的参数化

树的参数化有两个，一个是对树模型参数化，一个是对树的复杂度参数化。

1.3.0 树模型参数化-如何定义一个树

主要是定义两个部分：

每棵树每个叶子节点的值(或者说每个叶子节点的权重)w：这是一个向量，因为每个树有很多叶子节点样本到叶子节节点的映射关系q：(大白话就是告诉每个样本落在当前这个树的哪一个叶子节点上)叶子节点样本归属集合I：就是告诉每个叶子节点包含哪些样本

1.3.1 树复杂度的参数化-如何定义树的复杂度

定义树的复杂度主要是从两个部分出发：

每个树的叶子节点的个数（叶子节点个数越少模型越简单）叶子节点的权重值w（值越小模型越简单）

对于第二点，我们可以想一下L正则不就是想稀疏化权重，从而使模型变得简单吗，其实本质是一样的。

我们树的复杂度如下：

Ω(ft)=γT+12λ∑j=1Tωj2\Omega(f_{t}) = \gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}\omega_{j}^{2} \\注解：参数当前这颗树叶子节点的个数；是叶子节点值的范数注解：T参数当前这颗树叶子节点的个数；ωj2是叶子节点值的L2范数注解：T参数当前这颗树叶子节点的个数；\omega_{j}^{2}是叶子节点值的L_{2}范数 \\

进而我们可以对树进行了参数化，带入到目标函数我们可以得到如下：

Obj(t)≃∑i=1n[gift(xi)+12hift2(xi)]+Ω(ft)Obj^{(t)} \simeq \sum_{i=1}^{n}[g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]+\Omega(f_{t}) \\=∑i=1n[giwq(xi)+12hiwq2(xi)]+γT+12λ∑j=1Tωj2= \sum_{i=1}^{n}[g_{i}w_{q}(x_{i})+\frac{1}{2}h_{i}w_{q}^{2}(x_{i})]+ \gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}\omega_{j}^{2} \\=∑j=1T[(∑i∈Ijgi)wj+12(∑i∈Ijhi+λ)wj2]+γT= \sum_{j=1}^{T}[(\sum _{i\in I_{j}}g_{i})w_{j}+\frac{1}{2}(\sum _{i\in I_{j}}h_{i}+\lambda )w_{j}^{2}]+ \gamma T \\注解：最后一步的转化思路是从在这个树中，每个样本落在哪个节点转为了每个节点上有哪些样本注解：最后一步的转化思路是从在这个树中，每个样本落在哪个节点转为了每个节点上有哪些样本注解：最后一步的转化思路是从在这个树中，每个样本落在哪个节点转为了每个节点上有哪些样本 \\

随后我们做如下定义：

叶子节点 j 所包含的样本的一阶导数累加之和为：

Gj=∑i∈IjgiG_{j}=\sum_{i \in I_{j}}g_{i} \\

叶子节点 j 所包含的样本的二阶导数累加之和为：

Hj=∑i∈IjhiH_{j}=\sum_{i \in I_{j}}h_{i} \\

进而我们可以进一步化简为：

Obj(t)=∑j=1T[Gjwj+12(Hj+λ)wj2]+γTObj^{(t)}= \sum_{j=1}^{T}[G_{j}w_{j}+\frac{1}{2}(H_{j}+\lambda )w_{j}^{2}]+ \gamma T \\

针对这个目标函数，我们对Xgboost优有面临两个问题：

第一就是如何求得wjw_{j}：这一步其实很简单，直接使用目标函数对wjw_{j}求导就可以。

wj=−GjHj+λw_{j} =- \frac{G_{j}}{H_{j}+\lambda} \\注解：这一步就是二次函数求导注解：这一步就是二次函数求导注解：这一步就是二次函数求导 \\

还有一个就是如何做到特征的分裂，接下来我们详细聊一下如何去做

1.4寻找树的形状-特征分裂

首先明确一点，我们增益使用的是基于当前特征分裂点前后，目标函数的差值。

我们当然是希望，使用这个分裂点，目标函数降低的越多越好。

1.4.0 贪心算法

本质上是做两次循环，第一个是是针对每个特征的每个分割点做一次循环，计算收益，从而选择此特征的最佳分割点。分裂收益使用的是分裂之后的目标函数的变化差值。

第二个循环是对样本所有特征的循环，从中挑选出收益最大的特征。

简单说就是首先找到基于每个特征找到收益最大的分割点，然后基于所有特征找到收益最大的特征。

然后在这所有的循环中，挑出增益最大的那个分割点

1.4.1 近似算法-分位数候选点

对于每个特征，不去暴力搜索每个值，而是使用分位点

根据样本数量选择三分位点或者四分位点等等；

或者根据二阶导数（也就是梯度）作为权重进行划分

也就是说原来是某个特征的所有取值是候选点，现在是某个特征的分位点作为候选点。

2.工程实现细节

2.0 特征分裂并行寻找

寻找特征分隔点需要对特征值进行排序，这个很耗时间。我们可以在训练之前先按照特征对样本数据进行排序，并分别保存在不同的块结构中。每个块都有一个按照某个特征排好序的特征加对应的一阶二阶导数。

对于不同的特征的特征划分点，XGBoost分别在不同的线程中并行选择分裂的最大增益

2.1 缓存访问

特征是排好序，但是通过索引获取一阶二阶导数值是不连续的，造成cpu缓存命中率低； xgboost解决办法：为每个线程分配一个连续的缓存区，将需要的梯度信息存放在缓冲区中，这样就连续了；

同时通过设置合理的分块的大小，充分利用了CPU缓存进行读取加速（cache-aware access）。使得数据读取的速度更快。另外，通过将分块进行压缩（block compressoin）并存储到硬盘上，并且通过将分块分区到多个硬盘上实现了更大的IO。

2.2 xgboost特征的重要性是如何评估的

weight ：该特征在所有树中被用作分割样本的特征的总次数。gain ：该特征在其出现过的所有树中产生的平均增益（我自己的理解就是目标函数减少值总和的平均值，这里也可以使用增益之和）。cover ：该特征在其出现过的所有树中的平均覆盖范围。

这里有一个细节需要注意，就是节点分割的时候，之前用过的特征在当前节点也是可以使用的，所以weight才是有意义的。

3. 代码汇总

3.0 xgboost 如何筛选特征重要程度

xgboost 模型训练完毕之后，可以查一下每个特征在模型中的重要程度;

进一步的，我们可以暴力搜索一下，通过这个相关性筛选一下模型，看能不能在特征数量减少的情况下，模型表现能力不变甚至提升或者有我们可以接受的降低幅度。

核心代码如下(完整运行去github吧)

完整代篇幅太大，不展示在这里，直接去github：

3.1 xgboost完整训练代码

完整代篇幅太大，不展示在这里，直接去github：

xgboost 代码调参

框架参数：

booster：弱学习器类型

objective：分类还是回归问题以及对应的损失函数

n_estimators：弱学习器的个数

弱学习器参数：

max_depth：树的深度

min_child_weight：最小节点的权重阈值，小于这个值，节点不会再分裂；

gamma：节点分裂带来损失最小阈值，我们使用目标函数之差计算增益，小于这个阈值的时候，不再分裂

learning_rate:控制每个弱学习器的权重缩减系；这个系数会乘以叶子节点的权重值，它的作用在于削弱每个树的影响力，如果学习率小，对应的弱学习器的个数就应该增加。

xgboost常规面试题

与GBDT相比，Xgboost的优化点： 算法本身的优化：首先GBDT只支持决策树，Xgboost除了支持决策树，可以支持多种弱学习器，可以是默认的gbtree, 也就是CART决策树，还可以是线性弱学习器gblinear以及DART；其次GBDT损失函数化简的时候进行的是一阶泰勒公式的展开，而Xgboost使用的是二阶泰勒公式的展示。还有一点是Xgboost的目标函数加上了正则项，这个正则项是对树复杂度的控制，防止过拟合。可以处理缺失值。尝试通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向运行效率：并行化，单个弱学习器最耗时的就是决策树的分裂过程，对于不同特征的特征分裂点，可以使用多线程并行选择。这里想提一下，我自己理解，这里应该针对的是每个节点，而不是每个弱学习器。这里其实我当时深究了一下，有点混乱。为什么是针对每个节点呢？因为我每个节点也有很多特征，所以在每个节点上，我并行（多线程）除了多个特征，每个线程都在做寻找增益最大的分割点。还有需要注意的一点是Xgboost在并行处理之前，会提前把样本按照特征大小排好序，默认都放在右子树，然后递归的从小到大拿出一个个的样本放到左子树，然后计算对基于此时的分割点的增益的大小，然后记录并更新最大的增益分割点。

参考链接

刘建平：https://www.cnblogs.com/pinard/p/11114748.html

B站视频：https://www.bilibili.com/video/BV1mZ4y1j7UJ?from=search&seid=4849972439430408952

知乎：Microstrong：https://zhuanlan.zhihu.com/p/83901304