XGBoost算法通过优化结构化损失函数（加入了正则项的损失函数，可以起到降低过拟合的风险）来实现弱学习器的生成，并且XGBoost算法没有采用搜索方法，而是直接利用了损失函数的一阶导数和二阶导数值，并通过预排序、加权分位数等技术来大大提高了算法的性能。
GBDT算法流程：
第一步是得到负梯度，或者是泰勒展开式的一阶导数。第二步是第一个优化求解，即基于函数的负梯度拟合一颗CART回归树，得到J个叶子节点区域。
第三步是第二个优化求解，在第二步优化求解的结果上，对每个节点区域再做一次线性搜索，得到每个叶子节点区域的最优取值。最终得到当前轮的强学习器。
本质上是求解当前决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优值。GBDT采用的方法是分两步，先求出所有的J个叶子节点区域，再求出每个叶子节点区域的最优解。
对于XGBoost而言，它期望一次求出决策树最优的所有J个叶子节点区域和每个叶子节点区域的最优解。
XGBoost推导
最优切分点
在决策树的生长过程中，一个非常关键的问题是如何找到节点的最优切分点， 我们学过了决策树的建树过程，那么我们知道ID3也好，C4.5或者是CART，它们寻找最优切分点的时候都有一个计算收益的东西，分别是信息增益，信息增益比和基尼系数。而xgboost这里的切分， 其实也有一个类似于这三个的东西来计算每个特征点上分裂之后的收益。
- 从深度为 0 的树开始，对每个叶节点枚举所有的可用特征；
- 针对每个特征，把属于该节点的训练样本根据该特征值进行升序排列，通过线性扫描的方式来决定该特征的最佳分裂点，并记录该特征的分裂收益；（这个过程每个特征的收益计算是可以并行计算的，xgboost之所以快，其中一个原因就是因为它支持并行计算，而这里的并行正是指的特征之间的并行计算，千万不要理解成各个模型之间的并行）
- 选择收益最大的特征作为分裂特征，用该特征的最佳分裂点作为分裂位置，在该节点上分裂出左右两个新的叶节点，并为每个新节点关联对应的样本集（这里稍微提一下，xgboost是可以处理空值的，也就是假如某个样本在这个最优分裂点上值为空的时候， 那么xgboost先把它放到左子树上计算一下收益，再放到右子树上计算收益，哪个大就把它放到哪棵树上。）
- 回到第 1 步，递归执行到满足特定条件为止
xgboost在切分的时候就已经考虑了树的复杂度（obj里面看到那个了吗）。所以，它不需要进行单独的剪枝操作。
xgboost寻找切分点的时候不用遍历所有的，而是只看候选点就可以了。而且在特征上，xgboost是可以并行处理的。
XGBoost利用二阶泰勒展开
1、便于模块化，g和h是不依赖于损失函数的形式的，只要这个损失函数二次可微就可以。所以采用泰勒展开来得到二阶项，这样就能把MSE推导的那套直接复用到其他自定义损失函数上。简短来说，就是为了统一损失函数求导的形式以支持自定义损失函数。这是从为什么会想到引入泰勒二阶的角度来说的
二阶信息本身就能让梯度收敛更快更准确。
2、Xgboost引入了二阶导之后，相当于在模型降低残差的时候给各个样本根据贡献度不同加入了一个权重，这样就能更好的加速拟合和收敛，GBDT只用到了一阶导数，这样只知道梯度大的样本降低残差效果好，梯度小的样本降低残差不好
集合策略
利用新的决策树预测样本值，并累加到原来的值上若干个决策树是通过加法训练的， 所谓加法训练，本质上是一个元算法，适用于所有的加法模型，它是一种启发式算法。运用加法训练，我们的目标不再是直接优化整个目标函数，而是分步骤优化目标函数，首先优化第一棵树，完了之后再优化第二棵树，直至优化完K棵树。
上图中会发现每一次迭代得到的新模型前面有个n（这个是让树的叶子节点权重乘以这个系数）， 这个叫做收缩率，这个东西加入的目的是削弱每棵树的作用，让后面有更大的学习空间，有助于防止过拟合。也就是，我不完全信任每一个残差树，每棵树只学到了模型的一部分，希望通过更多棵树的累加来来弥补，这样让这个让学习过程更平滑，而不会出现陡变。这个和正则化防止过拟合的原理不一样，这里是削弱模型的作用，而前面正则化是控制模型本身的复杂度。
优点
与GBDT相比：
- 精度更高：GBDT只用到一阶泰勒， 而xgboost对损失函数进行了二阶泰勒展开， 一方面为了增加精度， 另一方面也为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数
- 灵活性更强：GBDT以CART作为基分类器，而Xgboost不仅支持CART，还支持线性分类器，另外，Xgboost支持自定义损失函数，只要损失函数有一二阶导数。
- 正则化：xgboost在目标函数中加入了正则，用于控制模型的复杂度。有助于降低模型方差，防止过拟合。正则项里包含了树的叶子节点个数，叶子节点权重的L2范式。
- Shrinkage（缩减）：相当于学习速率。这个主要是为了削弱每棵树的影响，让后面有更大的学习空间，学习过程更加的平缓
- 列抽样：这个就是在建树的时候，不用遍历所有的特征了，可以进行抽样，一方面简化了计算，另一方面也有助于降低过拟合
- 缺失值处理：这个是xgboost的稀疏感知算法，加快了节点分裂的速度
- 并行化操作：块结构可以很好的支持并行计算
参考链接：
