xgboost介绍
xgboost是华盛顿大学博士陈天奇创造的一个梯度提升（Gradient Boosting）的开源框架。至今可以算是各种数据比赛中的大杀器，被大家广泛地运用。接下来，就简单介绍一下xgboost和普通的GBDT比，有什么不同。(何为Gradient Boosting, GBDT请看我上篇文章)
1. 梯度下降
在GBDT中，我们每次生成下一个弱学习器，都是把损失函数的梯度作为学习目标，相当于利用梯度下降法进行优化来逼近损失函数的最小值，也就是使得损失函数为0，最终学习器尽可能接近真实结果。
$$
F_n(x)=\sum_{i=1}^n f_i(x)
$$
$$
F_n(x) = F_{n-1}(x) +f_n(x) = F_{n-1}(x) - \nabla L(F_{n-1}(x))
$$
而xgboost中，我们则是把损失函数的二阶泰勒展开的差值作为学习目标，相当于利用牛顿法进行优化，来逼近损失函数的最小值，也就是使得损失函数为0。
$$
F_n(x)=\sum_{i=1}^n f_i(x)
$$
$$
F_n(x) = F_{n-1}(x) +f_n(x) = F_{n-1}(x) -\frac {L’(F_{n-1}(x))} {L’’(F_{n-1}(x))}
$$
那为什么可以这么逼近呢？这就涉及到泰勒展开：
$$
L(x)=L(x_0)+L’(x_0)(x-x_0)+L’’(x_0)\frac{(x-x_0)^2}{2}+O[(x-x_0)^2]
$$
梯度下降法就是用一阶泰勒展开来近似函数：
$$
L(x)\approx L(x_0)+L’(x_0)(x-x_0)
$$
而牛顿法则是用二阶泰勒展开来近似函数：
$$
L(x)\approx L(x_0)+L’(x_0)(x-x_0)+L’’(x_0)\frac{(x-x_0)^2}{2}
$$
$$
L’(x)\approx L’(x_0)+L’’(x_0)(x-x_0)
$$
$$
x=x_0+\frac{L’(x_0)}{L’’(x_0)}
$$
之后具体的迭代收敛原理请看最优化方法。
2. 正则项
正则项是为了防止模型过拟合。于是，一般的损失函数$L(x)$就变成了目标函数$L(x)+\Omega(x)$。这样，随着树的复杂度增大，对应的目标函数也就变大，这样就有效防止了过拟合。叶子节点个数(T)，叶节点分数(w)
$$
\Omega=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^T w_j^2
$$
对叶子节点个数进行惩罚，相当于在训练过程中做了剪枝。
- 增益打分函数
将xgboost的目标函数进行化简，并把 $f(x)=w_q(x)$ 决策树（其中q(x)表示分到哪个叶子节点，$w\in R^T$）和 $\Omega=\gamma T+\frac{1}{2}\lambda\sum_{j=1}^T w_j^2$ 代入：
$$
\mathcal{L}^{(t)}=\sum_{i=1}^n l\left(y_{i}, \hat{y}{i}^{(t-1)}+f{t}\left(\mathbf{x}{i}\right)\right)+\Omega\left(f{t}\right)\
$$
$$
\begin{aligned}
\tilde{\mathcal{L}}^{(t)}&=\sum_{i=1}^{n}\left[g_{i} f_{t}\left(\mathbf{x}{i}\right)+\frac{1}{2} h{i} f_{t}^{2}\left(\mathbf{x}{i}\right)\right]+\Omega\left(f{t}\right)\
&=\sum_{j=1}^{T}\left[\left(\sum_{i \in I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T \
&=\sum_{j=1}^{T}\left[G_{j} w_{j}+\frac{1}{2}\left(H_{j}+\lambda\right) w_{j}^{2}\right]+\gamma T
\end{aligned}
$$
令其导数为0，解得每个叶节点的最优预测分数为：
$$
w_{j}^{*}=-\frac{G_{j}}{H_{j}+\lambda}
$$
代入目标函数，得到最小损失为：
$$
\tilde L^*=-\frac{1}{2}\sum_{j=1}^T\frac{G_j^2}{H_j+\lambda}+\gamma T
$$
$$
\operatorname{Gain}=\frac{1}{2}\left[\frac{G_{L}^{2}}{H_{L}+\lambda}+\frac{G_{R}^{2}}{H_{R}+\lambda}-\frac{\left(G_{L}+G_{R}\right)^{2}}{H_{L}+H_{R}+\lambda}\right]-\gamma
$$
Gain的值越大，分裂后 L 减小越多。所以当对一个叶节点分割时，计算所有候选(feature,value)对应的gain，选取gain最大的进行分割。
3. 树节点分裂方法
精确算法：遍历所有特征的所有可能分割点，来寻找使目标函数最小的分割点。
近似算法：对于每个特征，只考察分位点，减少计算复杂度。
而XGBoost不是简单地按照样本个数进行分位，而是以二阶导数值作为权重(Weighted Quantile Sketch)，比如:
4. 其他特征
- shrinkage（收缩）方法：相当于学习系数eta。对每颗子树都要乘上该系数，防止过拟合。
- 列采样：对特征进行降采样，灵感来源于随机森林，除了能降低计算量外，还能防止过拟合。
- 行采样
- 缺失值处理：通过枚举所有缺失值在当前节点是进入左子树，还是进入右子树更优来决定一个处理缺失值默认的方向。
- xgboost工具支持并行(Column Block)。一般决策树中，我们需要每次都对特征的值进行排序，来寻找分割点，极其费时。xgboost中，我们先对每个特征进行分块（block）并排序，使得在寻找最佳分裂点的时候能够并行化计算。这个结构加速了split finding的过程，只需要在建树前排序一次，后面节点分裂时直接根据索引得到梯度信息。这是xgboost比一般GBDT更快的一个重要原因。
- Cache Aware Access: column block按特征大小顺序存储，相应的样本的梯度信息是分散的， 造成内存的不连续访问，降低CPU cache 命中率。缓存优化方法：预取数据到buffer中（非连续->连续），再统计梯度信息，调节块的大小
- out-of-core优化内存等方法来加速计算。
重要性排序
下面就结合这张图，解释下各指标含义:
weight: {‘f0’: 1, ‘f1’: 2}
在所有树中，某特征被用来分裂节点的次数，在本例中，可见分裂第1个节点时用到f0，分裂第2，3个节点时用到f1，所以weight_f0 = 1, weight_f1 = 2。
total_cover: {‘f0’: 10.0, ‘f1’: 8.0}
第1个节点，f0被用来对所有10个样例进行分裂，之后的节点中f0没再被用到，所以f0的total_cover为10.0，此时f0 >= 0.855563045的样例有5个，落入右子树；
第2个节点，f1被用来对上面落入右子树的5个样例进行分裂，其中f1 >= -0.178257734的样例有3个，落入右子树；
第3个节点，f1被用来对上面落入右子树的3个样例进行分裂。
总结起来，f0在第1个节点分裂了10个样例，所以total_cover_f0 = 10，f1在第2、3个节点分别用于分裂5、3个样例，所以total_cover_f1 = 5 + 3 = 8。total_cover表示在所有树中，某特征在每次分裂节点时处理(覆盖)的所有样例的数量。
cover: {‘f0’: 10.0, ‘f1’: 4.0}
cover = total_cover / weight，在本例中，cover_f0 = 10 / 1，cover_f1 = 8 / 2 = 4.
total_gain: {‘f0’: 0.265151441, ‘f1’: 0.75000003}
在所有树中，某特征在每次分裂节点时带来的总增益，如果用熵或基尼不纯衡量分裂前后的信息量分别为i0和i1，则增益为(i0 - i1)。
gain: {‘f0’: 0.265151441, ‘f1’: 0.375000015}
gain = total_gain / weight，在本例中，gain_f0 = 0.265151441 / 1，gain_f1 = 75000003 / 2 = 375000015.
在平时的使用中，多用total_gain来对特征重要性进行排序。
————————————————
参考资料：
知乎上有关问题的回答 https://www.zhihu.com/question/41354392
一个很详细的PPT http://wepon.me/files/gbdt.pdf