本文记录的目的是方便自己学习和复习，有误之处请谅解，欢迎指出。
XGBoost全名叫（eXtreme Gradient Boosting）极端梯度提升，经常被用在一些比赛中，其效果显著。它是大规模并行boosted tree的工具，它是目前最快最好的开源boosted tree工具包。XGBoost 所应用的算法就是 GBDT（gradient boosting decision tree）的改进，既可以用于分类也可以用于回归问题中。
公式推导
首先XGBoost与GBDT相比考虑正则化项，目标函数定义如下：
其中，为损失函数，而
为正则化项，
为决策树的叶子节点数，
为叶子权重，
和
为惩罚正则项。
由前向分布算法知，原损失函数可改写为：
又由泰勒公式，可以进一步化简为：
其中，和
分别为一阶导数和二阶导数。
由于前个树的残差对当前优化不影响，因此可直接抹去，即：
对上式损失函数进一步改写：
第一个改写原因：将树的映射函数
看成每个叶子节点的总输出；总的输出表示一个树
第二个改写原因：将总输出进一步划分到叶子区域，
个叶子区域。
第三个改写原因：合并正则化项化简。
为了简化公式，再进一步改写：
其中，和
分别表示叶子节点总的一阶梯度和二阶梯度。
目标是最小化损失函数，所以对叶子节点分数求偏导，得到叶子节点分数的计算公式。
现在得到了叶子结点取值的表达式。
现在还有一个重要的问题需要解决，就是如何确定分裂规则。Adaboost和GBDT的分裂规则分别采用最小化分类误差和最小平方损失。分裂原则与损失函数无关。
但是Xgboost的分裂规则与损失函数有关，即：
总结：
1.在损失函数的基础上加入了正则项。
2.对目标函数进行二阶泰勒展开。
3.利用推导得到的表达式作为分裂准则, 来构建每一颗树。
算法流程
1）求出损失函数一阶导和二阶导公式；并计算保存所有样本的一阶导和二阶导。
2）计算所有可能的特征值划分点，然后求出每个划分点的左右分支样本的一阶导和二阶导总和，计算增益，求出最优的那个划分点。依次构建一个树。
3）迭代1）和2）两步骤
总体上看，XBGboost每次构建树的时候需要计算所有样本的一阶导、二阶导，并遍历所有可能的特征划分点。之后出现的LightGBM对此进行了有关改进。
实际例子
下面这个例子由https://blog.csdn.net/qq_22238533/article/details/79477547给出。
