对于XGBoost，它期望把第(2.2)步拟合一个回归树（弱分类器）和第(2.3)步计算最佳拟合值合并在一起做，即一次求解出决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解$c_{tj}$。下文会具体介绍。

从GBDT到XGBoost

XGBoost作为GBDT的高效实现，XGBoost是一个上限特别高的算法，因此在算法竞赛中比较受欢迎。简单来说，对比原算法GBDT，XGBoost主要从下面三个方面做了优化：

(1). 算法本身的优化：在算法的弱学习器模型选择上，对比GBDT只支持决策树，XGBoost还可以支持很多其他的弱学习器。在算法的损失函数上，除了本身的损失，还加上了正则化部分。在算法的优化方式上，GBDT的损失函数只对误差部分做负梯度（一阶泰勒）展开，而XGBoost损失函数对误差部分做二阶泰勒展开，更加准确。算法本身的优化是我们后面讨论的重点。

(2). 算法运行效率的优化：对每个弱学习器，比如决策树建立的过程做并行选择，找到合适的子树分裂特征和特征值。在并行选择之前，先对所有的特征的值进行排序分组，方便前面说的并行选择。对分组的特征，选择合适的分组大小，使用CPU缓存进行读取加速。将各个分组保存到多个硬盘以提高IO速度。

(3). 算法健壮性的优化：对于缺失值的特征，通过枚举所有缺失值在当前节点是进入左子树还是右子树来决定缺失值的处理方式。算法本身加入了L1和L2正则化项，可以防止过拟合，泛化能力更强。

Xgboost必备概念梳理（知识点）

1. 回顾Boosting集成学习的模型预测函数和损失函数：

预测模型为：

其中K$K$为树的总个数，fk$f_k$表示第k$k$颗树，y^i${\hat{y}}_i$表示样本xi$x_i$的预测结果。

损失函数为：　　

其中l(yi,yi^$l(y_i,\widehat{y_i}$为样本xi$x_i$的训练误差，Ω(fk)$\mathrm{\Omega }(f_k)$表示第k$k$棵树的正则项。

【补充】一般的目标函数都包含下面两项：

误差/损失函数L(Θ)$L(\mathrm{\Theta })$：指模型拟合数据的程度；

正则化项Ω