XGBoost 算法原理
XGBoost(eXtreme Gradient Boosting)是GBDT(Gradient Boosting Decision Tree)的一种实现。GBDT又是提升树（Boosting Tree）的一种优化模型。Boosting则是集成学习的一种算法。
之前提到的 Bagging 的思想比较简单，即每一次从原始数据中根据均匀概率分布有放回的抽取和原始数据大小相同的样本集合，样本点可能出现重复，然后对每一次产生的训练集构造一个分类器，再对分类器进行组合。
Boosting的每一次抽样的样本分布都是不一样的。每一次迭代，都根据上一次迭代的结果，增加被错误分类的样本的权重，使得模型能在之后的迭代中更加注意到难以分类的样本，这是一个不断学习的过程，也是一个不断提升的过程，这也就是Boosting思想的本质所在。迭代之后，将每次迭代的基分类器进行集成。那么如何进行样本权重的调整和分类器的集成是我们需要考虑的关键问题。
GB(Gradient Boosting) 是一种 Boosting 算法，因此它也试图利用一群弱学习器来创建一个强学习器。该算法与 AdaBoost算法 算法相似，但在某些方面有所不同。在这种方法中，我们试图将增强问题形象化为一个优化问题。我们采用一个损失函数，并试图优化它。
提升树是一种以分类树或者回归树作为基本分类器的算法。提升树一般采用加法模型，即基函数的线性组合与前向分步算法。对分类问题决策树是二叉分类树，对回归问题决策树是二叉回归树。对于提升树，当损失函数是平方误差损失函数和指数损失函数时，每一步优化比较简单，但是对于一般损失函数，往往每一步优化没那么容易。通常优化损失函数，是希望损失函数能够不断的减小，而且是损失函数能够尽可能快的减小。而梯度提升算法针对这问题 ，让损失函数沿着梯度方向最速下降的方法。
GBDT是以决策树（CART）为基学习器的GB算法。GBDT的核心就在于：每一棵树学的是之前所有树结论和的残差，这个残差就是一个加预测值后能得真实值的累加量。比如A的真实年龄是18岁，但第一棵树的预测年龄是12岁，差了6岁，即残差为6岁。那么在第二棵树里我们把A的年龄设为6岁去学习，如果第二棵树真的能把A分到6岁的叶子节点，那累加两棵树的结论就是A的真实年龄；如果第二棵树的结论是5岁，则A仍然存在1岁的残差，第三棵树里A的年龄就变成1岁，继续学习。
GBDT的算法描述如下：
（1）首先对样本i=1,2,…,m，计算损失函数在当前模型 ft−1(x)f_{t−1}(x)ft−1(x)的负梯度值：
rti=−[∂L(yi,f(xi)))∂f(xi)]f(x)=ft−1 (x)r_{ti} = -\bigg[\frac{\partial L(y_i, f(x_i)))}{\partial f(x_i)}\bigg]_{f(x) = f_{t-1}\;\; (x)}rti=−[∂f(xi)∂L(yi,f(xi)))]f(x)=ft−1(x)
（2）利用(xix_ixi,rtir_{ti}rti)(i=1,2,…,m), 拟合一颗CART回归树,得到第t颗回归树，其对应的叶子节点区域为对应的叶节点区域为Rtj,j=1,2,...,JR_{tj}, j =1,2,..., JRtj,j=1,2,...,J；
（3）在叶结点区域j=1,2,...,Jj=1,2,...,Jj=1,2,...,J上计算最佳拟合值，使得损失最小化：
ctj=arg min⏟c∑xi∈RtjL(yi,ft−1(xi)+c)c_{tj} = \underbrace{arg\; min}_{c}\sum\limits_{x_i \in R_{tj}} L(y_i,f_{t-1}(x_i) +c)ctj=cargminxi∈Rtj∑L(yi,ft−1(xi)+c)
（4）更新强学习器：
ft(x)=ft−1(x)+∑j=1JctjI(x∈Rtj)f_{t}(x) = f_{t-1}(x) + \sum\limits_{j=1}^{J}c_{tj}I(x \in R_{tj})ft(x)=ft−1(x)+j=1∑JctjI(x∈Rtj)
上面第一步是得到负梯度，或者是泰勒展开式的一阶导数。第二步是第一个优化求解，即基于残差拟合一颗CART回归树，得到J个叶子节点区域。第三步是第二个优化求解，在第二步优化求解的结果上，对每个节点区域再做一次线性搜索，得到每个叶子节点区域的最优取值。最终得到当前轮的强学习器。
1.2 XGBoost作为GBDT的高效实现，XGBoost是一个上限特别高的算法，因此在算法竞赛中比较受欢迎。简单来说，对比原算法GBDT，XGBoost主要从下面三个方面做了优化：
一是算法本身的优化：在算法的弱学习器模型选择上，对比GBDT只支持决策树，XGBoost还支持很多其他的弱学习器。在算法的损失函数上，除了本身的损失，还加上了正则化部分。在算法的优化方式上，GBDT的损失函数只对误差部分做负梯度（一阶泰勒）展开，而XGBoost损失函数对误差部分做二阶泰勒展开，更加准确。算法本身的优化是我们后面讨论的重点。
二是算法运行效率的优化：对每个弱学习器，比如决策树建立的过程做并行选择，找到合适的子树分裂特征和特征值。在并行选择之前，先对所有的特征的值进行排序分组，方便前面说的并行选择。对分组的特征，选择合适的分组大小，使用CPU缓存进行读取加速。将各个分组保存到多个硬盘以提高IO速度。
三是算法健壮性的优化：对于缺失值的特征，通过枚举所有缺失值在当前节点是进入左子树还是右子树来决定缺失值的处理方式。算法本身加入了L1和L2正则化项，可以防止过拟合，泛化能力更强。
在上面三方面的优化中，第一部分算法本身的优化是重点也是难点。现在我们就来看看算法本身的优化内容。
二、XGboost的目标函数推导从上面GBDT的算法描述可以看出，GBDT求最优解的方法是分两步走：求解当前决策树最优的所有叶子节点区域和每个叶子节点区域的最优解ctjc_{tj}ctj。
对于XGBoost，它期望把第2步和第3步合并在一起做，即一次求解出决策树最优的所有叶子节点区域和每个叶子节点区域的最优解。在讨论如何求解前，我们先看看XGBoost的损失函数的形式。
2.1 重新定义一棵树我们将一颗树ft(x)=wq(x)f_t(x)=w_{q(x)}ft(x)=wq(x)重新定义，包括两个部分：
叶子结点的权重向量w； (实例 -> 叶子结点)的映射关系q（本质是树的分支结构）；一棵树的表达形式定义如下：
通俗的讲就是给定一个输入x之后，先通过q(x)从树中找到相应地叶子节点leaf，然后以这个节点作为下标从权重向量得到对应的权重，所以ft(x)f_t(x)ft(x)其实是权重值。 2.2 重新定义树的复杂度
我们将一颗树的复杂度重新定义为 Ω(ft)=γT+12λ∑j=1Twj2\Omega(f_t)=\gamma T+\frac{1}{2} \lambda \sum_{j=1}^T w_j^2Ω(ft)=γT+21λ∑j=1Twj2，它由两部分组成：
叶子结点的数量T； 叶子结点权重向量的L2范数wj2w_j^2wj2；实例如下：
首先，为了防止过拟合，XGBoost的目标函数在GBDT损失函数 ∑i=1nl(yi,y^i)\sum\limits_{i=1}^n l(y_i, \hat y_i)i=1∑nl(yi,y^i) 的基础上，将全部 K 棵树的复杂度进行累加求和作为正则项加入，最终XGBoost目标函数定义如下：
Obj=∑i=1nl(yi,y^i)+∑k=1KΩ(fk)(2.3.1) Obj=\sum\limits_{i=1}^n l(y_i, \hat y_i) + \sum\limits_{k=1}^K \Omega(f_k) \tag{2.3.1}Obj=i=1∑nl(yi,y^i)+k=1∑KΩ(fk)(2.3.1)
这里的 lll 是训练损失，y^i\hat y_iy^i 是第 i 个样本 xix_ixi 的预测值。由于XGBoost是一个加法模型，因此，预测得分是每棵树打分的累加之和：
假设我们第 t 次迭代要训练的树模型是 ft(xi)f_t(x_i)ft(xi) ，也就是要学习第 t 棵树，由于XGBoost 是一个加法模型，所以此时前 t-1 次的训练结果 y^i(t−1)\hat y_i^{(t-1)}y^i(t−1) 其实是已经通过之前累加得出来了，可以将其看做一个常数值，于是样本i的第t棵树的预测结果 y^i(t)\hat y_i^{(t)}y^i(t) 可表示为：
还要注意的一点是，这里我们将正则化项进行了拆分，和上面的y^\hat yy^一样，由于前 t-1棵树的结构已经确定，因此，前 t-1 棵树的复杂度之和可以用一个常量表示const，而Ω(ft)\Omega(f_t)Ω(ft)则是未知的第t棵树的复杂度，于是所有t棵树的复杂度之和可以表示为：
将上面两式带入等式（2.3.1）中的目标函数 Obj ，可以得到等式（2.3.2）：
注意上式中，只有一个变量，那就是第 t 棵树：ft(xi)f_t(x_i)ft(xi)，其余的都是已知量或可通过已知量可以计算出来的（注意要理解哦！）。
最终我们要极小化上面这个损失函数，得到第t个决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解。XGBoost没有和GBDT一样去拟合泰勒展开式的一阶导数，而是期望直接基于损失函数的二阶泰勒展开式来求解。下面我们来看看这个损失函数的二阶泰勒展开式。
2.4 二阶泰勒展开首先简单回忆一下，泰勒公式：
泰勒公式是将一个在 x = x0 处具有n阶导数的函数 f(x) 利用关于 (x-x0) 的n次多项式来逼近函数的方法。
泰勒公式的二阶展开形式如下：
回到我们的问题上来， f(x)f(x)f(x) 对应于我们的损失函数 lll ，x 对应于前 t-1 棵树的预测值，Δx\Delta xΔx 对应于我们正在训练的第 t 棵树。
首先定义损失函数 lll 关于 y^(t−1)\hat y^{(t-1)}y^(t−1) 的一阶偏导数gig_igi和二阶偏导数hih_ihi：
那么，我们的损失函数就可以转化为下式（标出了与泰勒公式中x和Δx的对应关系）。
将上述二阶展开式，带入到目标函数（2.3.2）中，可以得到目标函数 Obj 的近似值：
去掉全部常数项，得到目标函数（2.4.1）：
我们将属于第 j 个叶子结点的所有样本 xi , 划入到一个叶子结点样本集中，数学表示如下：
然后，将【2.1】和【2.2】中一棵树及其复杂度的定义，带入到泰勒展开后的目标函数Obj（2.4.1）中，具体推导如下：
可以看出，对叶子节点归组是为了把损失函数求和中的n个结点和树的复杂度求和中的T个叶子节点进行统一，结点权重wqw_qwq也因此统一成了wjw_jwj，方便了化简公式。
为进一步简化该式，我们进行如下定义：
Gj=∑i∈Ijgi,Hj=∑i∈IjhiG_j=\sum_{i \in I_j}g_i,H_j=\sum_{i \in I_j} h_iGj=∑i∈Ijgi,Hj=∑i∈Ijhi
含义如下：
GjG_jGj：叶子结点 j 所包含样本的一阶偏导数累加之和，是一个常量； HjH_jHj：叶子结点 j 所包含样本的二阶偏导数累加之和，是一个常量；将 GjG_jGj 和 HjH_jHj 带入目标式Obj，得到我们最终的目标函数（注意，此时式中的变量只剩下第t棵树的权重向量W）：
XGBoost目标函数的优化求解涉及到2个问题：
如果我们已经求出了第t个决策树的J个最优的叶子节点区域，如何求出每个叶子节点区域的最优解w∗w^*w∗？ 对当前决策树做子树分裂决策时，应该如何选择哪个特征和特征值进行分裂，使最终我们的目标函数最小化？ 3.1 求每个叶子节点区域的最优解回忆一下高中数学知识。假设有一个一元二次函数，形式如下：
Gx+12Hx2,H>0Gx+\frac{1}{2}Hx^2,H>0Gx+21Hx2,H>0
我们可以套用一元二次函数的最值公式轻易地求出最值点：
那回到我们的目标函数 Obj，该如何求出它的最值呢？
先简单分析一下上面的式子，对于每个叶子结点 j , 可以将其从目标式 Obj 中拆解出来：
在【2.5】中我们提到，GjG_jGj和 HjH_jHj 相对于第 t 棵树来说是可以计算出来的。那么，这个式子就是一个只包含一个变量 叶子结点权重wjw_jwj 的一元二次函数，上面也提到了，我们可以通过最值公式求出它的最值点。
再次分析一下目标函数Obj，可以发现，各个叶子结点的目标子式是相互独立的，也就是说，当每个叶子结点的子式都达到最值点时，整个目标函数式Obj才达到最值点（下面Obj中对每个叶子节点的求和）。
那么，假设目前树的结构已经固定，套用一元二次函数的最值公式，我们可以轻易求出，每个叶子结点的权重 wj∗w_j^*wj∗ 及其此时达到最优的 Obj 的目标值：
实例演示：
在GBDT里面，我们是直接拟合的CART回归树，所以树节点分裂使用的是均方误差。XGBoost这里不使用均方误差，而是使用贪心法，即每次分裂都期望最小化我们的损失函数的误差。在实际训练过程中，当建立第 t 棵树时，从树深为0时开始：
对树中的每个叶子结点尝试进行分裂；
每次分裂后，原来的一个叶子结点继续分裂为左右两个子叶子结点，原叶子结点中的样本集将根据该结点的判断规则分散到左右两个叶子结点中；
新分裂一个结点后，我们需要检测这次分裂是否会给损失函数带来增益，增益的定义如下：
也就是说，我们的决策树分裂标准不再使用CART回归树的均方误差，而是上式了。如果增益Gain>0，即分裂为两个叶子节点后，目标函数下降了，那么我们会考虑此次分裂的结果。
但是，在一个结点分裂时，可能有很多个分裂点，每个分裂点都会产生一个增益，如何才能寻找到最优的分裂点呢？接下来会讲到。
在分裂一个结点时，我们会有很多个候选分割点，寻找最佳分割点的大致步骤如下：
遍历每个结点的每个特征； 对每个特征，按特征值大小将特征值排序； 线性扫描，找出每个特征的最佳分裂特征值；在所有特征中找出最好的分裂点（分裂后增益最大的特征及特征值）
上面是一种贪心的方法，每次进行分裂尝试都要遍历一遍全部候选分割点，也叫做全局扫描法。
但当数据量过大导致内存无法一次载入或者在分布式情况下，贪心算法的效率就会变得很低，全局扫描法不再适用。
基于此，XGBoost提出了一系列加快寻找最佳分裂点的方案：
一棵树不会一直生长下去，下面是一些常见的限制条件。
(1) 当新引入的一次分裂所带来的增益Gain<0时，放弃当前的分裂。这是训练损失和模型结构复杂度的博弈过程。
(2) 当树达到最大深度时，停止建树，因为树的深度太深容易出现过拟合，这里需要设置一个超参数max_depth。
(3) 当引入一次分裂后，重新计算新生成的左、右两个叶子结点的样本权重和。如果任一个叶子结点的样本权重低于某一个阈值，也会放弃此次分裂。这涉及到一个超参数:最小样本权重和，是指如果一个叶子节点包含的样本数量太少也会放弃分裂，防止树分的太细，这也是过拟合的一种措施。
每个叶子结点的样本权值和计算方式如下：
具体如何分裂呢？举个简单的年龄特征的例子如下，假设我们选择年龄这个特征的值a作为决策树的分裂标准，则可以得到左子树2个人，右子树三个人，这样可以分别计算出左右子树的一阶和二阶导数和，进而求出最终的上式的值。我们可以发现对于所有的a，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和 GLG_LGL 和 GRG_RGR。然后用上面的公式计算每个分割方案的分数就可以了。
这里我们总结下XGBoost的算法主流程，基于决策树弱分类器。不涉及运行效率的优化和健壮性优化的内容。
输入：训练集样本I={(x,y1),(x2,y2),...(xm,ym)}I=\{(x_,y_1),(x_2,y_2), ...(x_m,y_m)\}I={(x,y1),(x2,y2),...(xm,ym)}， 最大迭代次数T, 损失函数L， 正则化系数 λ,γ\lambda, \gammaλ,γ。
输出：强学习器f(x)
对迭代轮数t=1,2,…T有：
(1) 计算第i个样本(i=1,2,…m)在当前轮损失函数L基于 ft−1(xi)f_{t-1}(x_i)ft−1(xi) 的一阶导数gtig_{ti}gti，二阶导数 htih_{ti}hti,计算所有样本的一阶导数和 Gt=∑i=1mgtiG_t=\sum_{i=1}^m g_{ti}Gt=∑i=1mgti,二阶导数和 Ht=∑i=1mhtiH_t=\sum_{i=1}^m h_{ti}Ht=∑i=1mhti
(2) 基于当前节点尝试分裂决策树，默认分数score=0
对特征序号 k=1,2…K:
(a) GL=0,HL=0G_L=0, H_L=0GL=0,HL=0
(b.1) 将样本按特征k从小到大排列，依次取出第i个样本，依次计算当前样本放入左子树后，左右子树一阶和二阶导数和：
GL=GL+gti,GR=G−GLG_L = G_L+ g_{ti}, G_R=G-G_LGL=GL+gti,GR=G−GL
HL=HL+hti,HR=H−HLH_L = H_L+ h_{ti}, H_R=H-H_LHL=HL+hti,HR=H−HL
(b.2) 尝试更新最大的分数：
score=max(score,12GL2HL+λ+12GR2HR+λ−12(GL+GR)2HL+HR+λ−γ)score = max(score, \frac{1}{2}\frac{G_L^2}{H_L + \lambda} + \frac{1}{2}\frac{G_R^2}{H_R+\lambda} - \frac{1}{2}\frac{(G_L+G_R)^2}{H_L+H_R+ \lambda} -\gamma )score=max(score,21HL+λGL2+21HR+λGR2−21HL+HR+λ(GL+GR)2−γ)
(3) 基于最大score对应的划分特征和特征值分裂子树。
(4) 如果最大score为0，则当前决策树建立完毕，计算所有叶子区域的wtjw_{tj}wtj, 得到弱学习器ht(x)h_t(x)ht(x)，更新强学习器ft(x)f_t(x)ft(x),进入下一轮弱学习器迭代.如果最大score不是0，则转到第2)步继续尝试分裂决策树。
五、XGBoost算法优化 5.1 XGBoost算法运行效率的优化上面我们重点讨论了XGBoost算法本身的优化，在这里我们再来看看XGBoost算法运行效率的优化。
首先明确的是：XGBoost的并行，并不是说每棵树可以并行训练，XGBoost本质上仍然采用 Boosting 思想，Boosting算法的弱学习器是没法并行迭代的，每棵树训练前需要等前面的树训练完成才能开始训练。但是单个弱学习器里面最耗时的是决策树的分裂过程，XGBoost针对这个分裂做了比较大的并行优化。对于不同的特征的特征划分点，XGBoost分别在不同的线程中并行选择分裂的最大增益。
XGBoost的特征维度的并行是这样实现的：在训练之前，每个特征按特征值对样本进行预排序，并以Block结构存储在内存中，在后面查找特征分割点时可以重复使用，减少计算量。计算量的减少是指：默认所有的样本都在右子树，然后从小到大迭代，依次放入左子树，并寻找最优的分裂点。这样做可以减少很多不必要的比较。而且特征已经被存储为一个个block结构，那么在寻找每个特征的最佳分割点时，可以利用多线程对每个block并行计算。
此外，通过设置合理的分块的大小，充分利用了CPU缓存进行读取加速（cache-aware access）。使得数据读取的速度更快。另外，通过将分块进行压缩（block compressoin）并存储到硬盘上，并且通过将分块分区到多个硬盘上实现了更大的IO。
首先我们来了解一下一般情况下对存在缺失值的特征的解决方法是：
离散型变量：用出现次数最多的特征值填充； 连续型变量：用中位数或均值填充；一些模型如SVM和KNN，其模型原理中涉及到了对样本距离的度量，如果缺失值处理不当，最终会导致模型预测效果很差。
而树模型对缺失值的敏感度低，大部分时候可以在数据缺失时时使用。原因就是，一棵树中每个结点在分裂时，寻找的是某个特征的最佳分裂点（特征值），完全可以不考虑存在特征值缺失的样本，也就是说，如果某些样本缺失的特征值缺失，对寻找最佳分割点的影响不是很大。
因此，对于有缺失值的数据在经过缺失处理后：
当数据量很小时，优先用朴素贝叶斯 数据量适中或者较大，用树模型，优先XGBoost 数据量较大，也可以用神经网络 避免使用距离度量相关的模型，如KNN和SVMXGBoost模型的一个优点就是允许特征存在缺失值，XGBoost对特征的缺失值的处理方式是这样的：
两种情形都计算一遍后，选择分裂后增益最大的那个方向（左分支或是右分支），作为预测时特征值缺失样本的默认分支方向，这样处理起来更加的灵活和合理。
如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子结点。
也就是说，其实每次都是针对没有缺失值的特征k的样本走上述第四节的一般流程。而对应有缺失值的特征，上面第4节的算法的步骤(a),(b.1)和(b.2)会执行2次，第一次假设特征k所有有缺失值的样本都走左子树，第二次假设特征k所有有缺失值的样本都走右子树。
(b.1)步要更新为：
GR=GR+gti,GL=G−GRG_R = G_R+g_{ti}, G_L=G-G_RGR=GR+gti,GL=G−GR
HR=HR+hti,HL=H−HRH_R = H_R+h_{ti}, H_L=H-H_RHR=HR+hti,HL=H−HR 六、面试题 珍藏版 | 20道XGBoost面试题，你会几个？(上篇) 珍藏版 | 20道XGBoost面试题，你会几个？(下篇)
参考
【0】 https://xgboost.ai
【1】【ML】XGBoost超详细推导，终于有人讲明白了！
【2】 机器学习经典算法（4）——Xgboost
【3】 机器学习总结（一） Adaboost,GBDT和XGboost算法
【4】 ID3、C4.5、CART、随机森林、bagging、boosting、Adaboost、GBDT、xgboost算法总结
【5】 梯度提升树(GBDT)原理小结
【6】 XGBoost算法原理小结
【7】 AdaBoost, GBDT和XGBoost的区别和联系
作者：Wisimer
