算法流程

• 定义目标函数

xgboost本身就是一种树的boosting方式，同GBDT一样采用前相加法训练的方式进行残差的迭代，最终将叶子节点的值相加即得到最终过的输出。因此XGB的输出
$\hat y=\sum_{k=1}^Kf_k(x)$y^​=k=1∑K​fk​(x)
其中$f_k(x)$fk​(x)即每一颗CART树，那么如何确定这树的构成和参数呢？

对于树的结构是通过前相加法训练得到的，即首先优化第一棵树然后优化第二课，重复进行直到第$K$K颗。

而在这过程中，最优的CART树是优化目标函数得到的，第t颗树的目标函数的通用形式如下：
$obj^{(t)}=\sum_{i=1}^{n}l(y_i, \hat{y_i}^{(t)})+\sum_{i=1}^t\Omega(f_t)$obj(t)=i=1∑n​l(yi​,yi​^​(t))+i=1∑t​Ω(ft​)
其中$obj^{(t)}$obj(t)为第t颗树的目标函数，$i$i为样本编号，$y_i$yi​为第$i$i个样本的标签，$\hat{y_i}^{(t)}$yi​^​(t)为样本$i$i在这t棵树叶子节点的输出和，$\Omega$Ω为t棵树的正则项。

XGB与原生的GBDT的差异即在于目标函数进行了二阶展开，首先对第t棵树的目标函数进行变换，这里我们先把正则项去掉，后续单独讨论。
$obj^{(t)}=\sum_{i=1}^{n}l(y_i, \hat{y_i}^{(t-1)}+f_t(x_i))$obj(t)=i=1∑n​l(yi​,yi​^​(t−1)+ft​(xi​))
即将前t棵树的输出表示为：前t-1棵树与第t棵树的输出相加。

泰勒展开公式如下：
$f(x) = \frac {f^n(x_0)} {n!}(x-x_0)^n$f(x)=n!fn(x0​)​(x−x0​)n
对公式目标函数在$\hat {y_i}^{(t-1)}$yi​^​(t−1)处进行二阶泰勒展开，则有
$obj^{(t)}=\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(x_i)$obj(t)=i=1∑n​l(yi​,yi​^​(t−1))+gi​ft​(xi​)+21​hi​ft​(xi​)
其中$g_i$gi​和$h_i$hi​分别为loss function在$\hat {y_i}^{(t-1)}$yi​^​(t−1)的一阶和二阶偏导，即
$g_i=\frac {\partial l(y_i,\hat {y_i}^{t-1})} {\partial \hat {y_i}^{t-1}}$gi​=∂yi​^​t−1∂l(yi​,yi​^​t−1)​

$h_i=\frac {\partial^2 l(y_i,\hat {y_i}^{t-1})} {\partial \hat {(y_i}^{t-1})^2}$hi​=∂(yi​^​t−1)2∂2l(yi​,yi​^​t−1)​

对于不同任务loss function的定义不同，但其形式一旦固定，其一阶导数和二阶导数的形式就固定了，只要在表达式带入$\hat {y_i}^{(t-1)}$yi​^​(t−1)的值即可。这里可以看到N个样本之间$g_i$gi​和$h_i$hi​的计算都是独立的，因此可以并行计算，再加上层内节点并行，XGB速度优势的来源已经明了。

这里把正则项单独拿出来说，直接给出正则的定义：
$\Omega=\gamma T+\frac 1 2 \lambda \sum_{j=1}^Tw_j^2$Ω=γT+21​λj=1∑T​wj2​
其中$\gamma$γ和$\lambda$λ是超参数，$T$T是树的棵数，$w_j$wj​是第$j$j棵树的输出，即$f_t(x_i)$ft​(xi​)，因此xgb的目标函数为：
$obj^{(t)}=\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(x_i)] +\gamma T+\frac 1 2 \lambda \sum_{j=1}^Tw_j^2$obj(t)=i=1∑n​[l(yi​,yi​^​(t−1))+gi​ft​(xi​)+21​hi​ft​(xi​)]+γT+21​λj=1∑T​wj2​
进一步做聚合有
$obj^{(t)}=loss_i^{(t-1)}+\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]+\lambda T$obj(t)=lossi(t−1)​+j=1∑T​[(i∈Ij​∑​gi​)wj​+21​(i∈Ij​∑​hi​+λ)wj2​]+λT
其中$i\in I_j$i∈Ij​表示为落在第j个叶子节点的样本集合，令$G_j=\sum_{i \in {I_j}}g_i$Gj​=∑i∈Ij​​gi​，$H_j=\sum_{i \in I_j}h_i$Hj​=∑i∈Ij​​hi​，则最终有
$obj^{(t)}=loss_i^{(t-1)}+\sum_{j=1}^T[G_jw_j+\frac 1 2 (H_j+\lambda)w_j^2]+\lambda T$obj(t)=lossi(t−1)​+j=1∑T​[Gj​wj​+21​(Hj​+λ)wj2​]+λT
上式是一个一元二次方程，可以很容易求出各个叶子节点的最佳值
$w_j^*=- \frac {G_j} {H_j+\lambda}$wj∗​=−Hj​+λGj​​
以及目标函数的值
$obj^*=-\frac 1 2 \sum_{j=1}^T \frac {G_j^2} {H_j+\lambda} + \lambda T$obj∗=−21​j=1∑T​Hj​+λGj2​​+λT
$obj^*$obj∗代表了这棵树的结构有多好，值越小，代表这样结构越好。也就是说，它是衡量第t棵CART树的结构好坏的标准。注意，这个值仅仅是用来衡量结构的好坏的，与叶子节点的值可是无关的。

• 生成树结构

树结构的生成与决策树的生成大体相同，对于每个节点遍历特征，排序特征的取值，并遍历切分点，计算划分为左右节点时的增益，即
$Gain=obj-(obj_R+obj_L)=\frac 1 2 [\frac {G_R^2} {H_R+\lambda} + \frac {G_L^2} {H_L+\lambda}-\frac {(G_R+G_L)^2} {H_R+H_L+\lambda}] - \lambda$Gain=obj−(objR​+objL​)=21​[HR​+λGR2​​+HL​+λGL2​​−HR​+HL​+λ(GR​+GL​)2​]−λ
如果$Gain$Gain的值是正的，则当$Gain$Gain越大，证明切分后$obj$obj的值之和比父节点的$obj$obj越小，就越值得切分。同时，我们还可以观察到，$Gain$Gain的左半部分如果小于右侧的$\gamma$γ，则$Gain$Gain就是负的，表明切分后$obj$obj反而变大了。$\gamma$γ在这里实际上是一个临界值，它的值越大，表示我们对切分后$obj$obj下降幅度要求越严。这个值也是可以在xgboost中设定的。

扫描结束后，就可以确定是否切分，如果切分，对切分出来的两个节点，递归地调用这个切分过程，我们就能获得一个相对较好的树结构。

但注意XGB的生成操作已经考虑了树的复杂度，因此与普通决策树不同，XGB不需要进行剪枝

Shrinkage and Column Subsampling

XGBoost还提出了两种防止过拟合的方法：Shrinkage and Column Subsampling。Shrinkage方法就是在每次迭代中对树的每个叶子结点的分数乘上一个缩减权重η，这可以使得每一棵树的影响力不会太大，留下更大的空间给后面生成的树去优化模型。Column Subsampling类似于随机森林中的选取部分特征进行建树。其可分为两种，一种是按层随机采样，在对同一层内每个结点分裂之前，先随机选择一部分特征，然后只需要遍历这部分的特征，来确定最优的分割点。另一种是随机选择特征，则建树前随机选择一部分特征然后分裂就只遍历这些特征。一般情况下前者效果更好。

近似算法

对于连续型特征值，当样本数量非常大，该特征取值过多时，遍历所有取值会花费很多时间，且容易过拟合。因此XGBoost思想是对特征进行分桶，即找到l个划分点，将位于相邻分位点之间的样本分在一个桶中。在遍历该特征的时候，只需要遍历各个分位点，从而计算最优划分。从算法伪代码中该流程还可以分为两种，全局的近似是在新生成一棵树之前就对各个特征计算分位点并划分样本，之后在每次分裂过程中都采用近似划分，而局部近似就是在具体的某一次分裂节点的过程中采用近似算法。

针对稀疏数据的算法（缺失值处理）

当样本的第i个特征值缺失时，无法利用该特征进行划分时，XGBoost的想法是将该样本分别划分到左结点和右结点，然后计算其增益，哪个大就划分到哪边。

算法优点

之所以XGBoost可以成为机器学习的大杀器，广泛用于数据科学竞赛和工业界，是因为它有许多优点：

1. 使用许多策略去防止过拟合，如：正则化项、Shrinkage and Column Subsampling等。

2. 目标函数优化利用了损失函数关于待求函数的二阶导数

3. 支持并行化，这是XGBoost的闪光点，虽然树与树之间是串行关系，但是同层级节点可并行。具体的对于某个节点，节点内选择最佳分裂点，候选分裂点计算增益用多线程并行。训练速度快。

4. 添加了对稀疏数据的处理。

5. 交叉验证，early stop，当预测结果已经很好的时候可以提前停止建树，加快训练速度。

6. 支持设置样本权重，该权重体现在一阶导数g和二阶导数h，通过调整权重可以去更加关注一些样本。