目录
- 一、简介
- 二、公式——二阶泰勒展开
-
- 1、目标函数
- 二、二阶泰勒展开
- 三、贪心法（计算增益）
-
- 1、增益
- 2、贪心法
- 3、优化
- 四、总结
- 五、gbdt与xgboost的区别
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、优点：速度快、效果好、能处理大规模数据、支持自定义损失函数等
缺点：算法参数过多，调参复杂，不适合处理超高维特征数据
1、gbdt以cart作为基分类器，xgboost除此之外还支持线性分类器。这时xgboost相当于带正则化的逻辑回归（分类）/线性回归（回归）。
2、xgboost的目标函数中加入了正则化，控制了模型的复杂度，减少了过拟合。除此之外，xgboost支持自定义目标函数，需要函数一阶二阶可导。
3、gbdt只包括一阶导数信息，xgboost进行了二阶泰勒展开，包含一阶导数和二阶导数信息。
4、xgboost借鉴了随机森林的做法，支持列采样。一方面减少了过拟合，另一方面降低了模型的参数。另一方面，xgboost支持行采样，抽取部分样本。
5、xgboost可以自动学习缺失值的分裂方向。在处理特征时，先不计算带缺失值的样本，对没有确实的样本进行排序。在遍历分裂点时，分别将缺失值划分在左子树和右子树中，计算损失求最优值。
6、xgboost支持并行处理。xgboost的并行是在特征粒度上的。xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
7、可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。
8、xgboost先建立自顶向下的子树，再从底向上进行剪枝，相比gbdt，这样可以避免陷入局部最优解。
9、shrinkage（即学习速率，将学习速率调小，迭代次数增加，有正则化作用），与gbdt相同。