xgboost是基于梯度提升的树，公式如下：

其中为CART回归树，每个叶子都有一个连续分数，拟合最终目标的loss函数如下，为预测值，为真实值，T为叶子节点个数，为叶子节点权重平方和。

 

其中

将loss进行泰勒公式展开，可以得到：

最终得到每个叶子节点的权重为，而对应第t棵树的loss为，其中G为所有样本在该叶子节点的loss的一阶导数之和，H为所有样本在该叶子节点的loss的二阶导数之和。

通常采用遍历得到树的结构，每次分裂的loss reduction：

XGBoost在贪心全局扫描的基础上提出了加快寻找分裂点的方案：

• 特征预排序+缓存：在训练之前，对每个特征按照特征值大小进行排序保存为block结构，后续每次迭代重复利用该结构减少计算量。

• 分位点近似点：对每个特征按照特征值大小排序后，采用类似分位点选取的方法，选出常数个特征值作为该特征的候选分割点并选出最优的。

• 并行查找：由于已存block结构，支持利用多个线程并行计算每个特征的最佳分割点。

XGBoost相对于GBDT的不同：

• 基分类器：XGBoost不仅支持CART，还支持线性分类器，相当于带L1和L2正则化项的logistic回归或者线性回归；

• 导数信息：XGBoost对损失函数进行了二阶泰勒展开，损失函数一阶、二阶可导即可，GBDT仅用了一阶导数信息；

• 列抽样：XGBoost支持列抽样，用于过拟合；

• 缺失值处理：对树中的每个非叶子节点，XGBoost可以自动学习它的默认分裂方向；

• 并行化：XGBoost预先将每个特征按照特征值大小排序存储为block结构，分裂时通过多线程并行查找每个特征的最佳分裂点；