一、简介
XGBoost, LightGBM, CatBoost, NGBoost实际上是对GBDT方法的不同实现，针对同一目标、做了不同的优化处理。
xgboost的基学习器采用CART回归树。
二、公式——二阶泰勒展开
1、目标函数
目标函数=损失函数 + 正则化项
正则化项用于控制树的复杂度，防止过拟合，使得模型更简化，也使得最终的模型的预测结果更稳定。
其中，
T：叶子数量，
wj：叶子分数的L2正则项
r：加入新叶子节点引入的复杂度代价
例如：
此时
预测函数，样本的预测结果=每棵树预测分数之和
二、二阶泰勒展开
对目标函数改进，进行二阶泰勒展开：
定义
XGBoost 的目标函数：
T为叶子节点数量
Ij定义为每个叶子节点里面的样本集合
即每个样本所在叶子节点索引的分数（叶子权重w）
Gj，Hj分别表示每个叶子节点的一阶梯度的和，与二阶梯度的和：
目标函数改写为：
求偏导得到：
求解得
分数越小，代表树的结构越好。
三、贪心法（计算增益）
1、增益
求Obj分数最小的树结构，可以穷举所有可能，但计算量太大，使用贪心法，即利用打分函数（计算增益）。
以Gain作为是否分割的条件，Gain看作是未分割前的Obj减去分割后的左右Obj：
如果Gain<0，则此叶节点不做分割，分割方案个数很多，计算量依然很大。
2、贪心法
贪心方法，获取最优分割节点（split point）
将所有样本按照gi从小到大排序，通过遍历，查看每个节点是否需要分割
对于特征值的个数为n时，总共有n?1种划分
Step1，对样本扫描一遍，得出GL，GR
Step2，根据Gain的分数进行分割
通过贪心法，计算效率得到大幅提升，XGBoost重新定义划分属性，即Gain，而Gain的计算是由目标损失函数obj决定的
3、优化
XGBoost的分裂节点算法（近似算法，Histogram 2016 paper）：
对于连续型特征值，样本数量非常大，该特征取值过多时，遍历所有取值会花费很多时间，且容易过拟合
方法，在寻找split节点的时候，不会枚举所有的特征值，而会对特征值进行聚合统计，然后形成若干个bucket(桶)，只将bucket边界上的特征值作为split节点的候选，从而获得性能提升
从算法伪代码中该流程还可以分为两种，全局的近似是在新生成一棵树之前就对各个特征计算分位点并划分样本，之后在每次分裂过程中都采用近似划分，而局部近似就是在具体的某一次分裂节点的过程中采用近似算法
四、总结
XGBoost算法特点：
1、XGBoost将树模型的复杂度加入到正则项中，从而避免过拟合，泛化性能好
2、损失函数是用泰勒展开式展开的，用到了一阶导和二阶导，可以加快优化速度
3、在寻找最佳分割点时，采用近似贪心算法，用来加速计算
4、不仅支持CART作为基分类器，还支持线性分类器，在使用线性分类器的时候可以使用L1，L2正则化
5、支持并行计算，XGBoost的并行是基于特征计算的并行，将特征列排序后以block的形式存储在内存中，在后面的迭代中重复使用这个结构。在进行节点分裂时，计算每个特征的增益，选择增益最大的特征作为分割节点，各个特征的增益计算可以使用多线程并行
6、优点：速度快、效果好、能处理大规模数据、支持自定义损失函数等
缺点：算法参数过多，调参复杂，不适合处理超高维特征数据