前面我们已经详细介绍了集成算法中的Adaboost和GBDT算法，今天我们继续来介绍一下目前最火的集成算法-XGBoost。
一、XGBoost介绍
XGBoost的全称是 eXtreme Gradient Boosting，翻译成中文就是“极端梯度提升”。它是陈天奇博士提出来的一种梯度提升算法，不同于传统的Gradient Boosting，XGBoost是一种Newton Boosting，它用二阶泰勒展开式去近似损失函数，然后通过让损失函数最小化，来求出最优的树结构以及叶子节点的值。XGBoost还在Gradient Boosting的基础上做了很多改良，例如在损失函数里增加了正则化项，训练基学习器的时候可以使用列采样，这些都能防止学习器过度拟合。
XGBoost算法流程
输入:
训练集
损失函数
弱学习器的个数
树复杂度超参数和
学习率
过程：
初始化一个常数值
-
For
= 1 to
2.1 求出每个样本的一阶导(gradients)和二阶导(hessians)
2.2 用
去拟合一颗决策树
，目标是使总体损失函数最小化。
目标函数为：
其中
是叶子节点的个数，
是划分到叶子节点
的所有样本的
和，
是划分到叶子节点
和；
(1) 通过最小化目标函数
，求得
(2) 选取最佳变量以及最佳分割点的度量标准是
通过选取让
最大的最佳分组变量以及最佳分割点来达到让损失函数最小化的目的；
2.3 更新后的模型
其中
是学习率，是一个超参数。
2.4 循环直到满足终止条件。
二、XGBoost的推导
我们知道，XGBoost也是一种加法模型+前向分步算法。
加法模型就是基模型的组合方式是通过相加的形式；
前向分步学习算法是用来解决加法模型优化问题的，通过循环迭代，每一步都固定前面的基模型不变，只训练当前的基模型，通过让总体目标函数最小来求得本次最优的基模型，循环迭代，以此来达到让总体目标函数最小化的目的，这样可以简化优化的复杂度。
上面我们已经知道了每个基模型最佳分组变量以及最佳切割点的选取标准，以及叶子节点值的计算公式。下面我们来看看这些是如何得来的。
XGBoost模型可以表示为：
1、目标函数推导
(1) 原始目标函数
设在第步时，目标函数为：
我们的目的是找到让目标函数到达最小值的。
(2) 泰勒展开后的目标函数
了解AdaBoost的人就会想，为什么要用泰勒展开式去近似损失函数呢，为什么不直接通过求导损失函数来获得最佳的呢，因为AdaBoost的损失函数是固定的(指数损失函数)，而XGBoost的损失函数可以任意设置，损失函数多种多样，不是所有的损失函数都可以通过求导的方式来顺利的求出最佳
，所以我们想到了用循环迭代的方式去一步步逼近最优值。这种思想和优化算法里的牛顿法思想是一致的。
通过用泰勒展开式来近似上面的目标函数，每次的基模型的训练目标都是让近似的目标函数达到最低点，循环迭代来达到让总体目标函数最小化的目的。
我们知道二阶泰勒展开式为：
定义：
则目标函数可以近似为：
由于步的模型已经固定，所以
是一个定值。
移除掉常数部分，目标函数变成：
定义基模型的复杂度为：
其中是叶子节点的个数，
是每个叶子节点的分数
则
代入式得：
定义：
损失函数变成：
2、基模型的确定
有了上面(3)式的目标函数，就可以指引我们找到让目标函数最小化的树结构以及叶子节点的值。
(1) 叶子节点分数确定
首先假设当前需要训练的基模型树结构是固定的，我们先来求出让目标函数最小化的叶子节点分数。
由于树是固定的，那么T的值也固定了，和
是事先设置的超参数，
和
是
步模型中每个样本的一阶导和二阶导，
步模型也是固定的，所以
和
也是一个固定的值。所以(3)式中的未知参数只有一个
。
那么(3)式其实可以看成是一个单变量二次函数。我们知道二次函数取得极值点的
，代入到(3)式得：
最优的叶节点分数
最小的损失值
(2) 树结构确定
当树的结构确定时，我们前面已经推导出其最优的叶节点分数以及对应的最小损失值。
现在我们不希望固定树结构，希望找到最优的树结构，但是，这里有无穷多的树结构，怎么确定树的结构呢。有2种思路：
① 暴力枚举所有可能的树结构，选择损失值最小的，但是这是一个NP难问题；
② 贪心法，每次尝试分裂一个叶节点，计算分裂前后的增益，选择增益最大的变量以及切割点；
在实践中，我们采用贪婪的学习方式。
已知最小的损失值，其中
衡量了每个叶子节点对总体损失函数的贡献，我们希望总体损失函数越小越好，所以其值越大越好。
由于我们的树是一个二叉树，因此对叶子节点进行分裂，分裂前后的增益定义为：
我们期望的值越大越好，所以当对一个叶子结点进行分裂时，挑选能让增益最大的变量以及切割点。
(3) 如何确定最佳切割点
方法1： 枚举所有特征上的所有可能拆分
方法2： 近似算法，对每个特征，只考察分位点，减少计算复杂度
global方法：在学习每棵树前，提出候选切割点，并在每次分裂时使用相同的拆分建议；
local方法：在每次分裂的时候，重新提出候选切割点；
对于global方法，通常需要更多的候选点，意思就是分位点需要设置得更细一点，因为每次分裂时候选变量的切割点都固定不变。local方法在每次分裂时都会重新提出候选切割点，更适合于更深的树。我们发现local方法确实只需要较少的候选点。如果有足够多的候选变点，global方法可以和local方法一样准确。
在实际应用的时候，通常不是简单的按个数的分位数去获取候选切割点，而是需要通过二阶导加权来获取候选切割点。
