机器学习之XGBoost

1、 什么是XGBoost

XGBoost ：eXtreme Gradient Boosting
项目地址：https://github.com/dmlc/xgboost
文档：http://xgboost.readthedocs.io...
一个可升级的树提升算法(a scalable machine learning system for tree boosting)，XGBoost通过不断迭代，将多个弱分类器组合成一个强分类器，它的基学习器是决策树。相对于GBDT，XGBoost使用二阶信息，可以更快在训练集上收敛。
(本文主要描述xgboost的公式推导)

2、参数定义

说明：各个参数的定义来源于论文XGBoost: A Scalable Tree Boosting System

n examples and m features
树的预测值：

最终归属于叶子节点j的样本集：

3、公式推导

目标函数：

其中，
是惩罚项，只与第t棵决策树有关，与样本无关，也与前t-1棵决策树无关，因为在第t次迭代中前t-1棵决策树已经确定；

是损失函数；

表示t棵决策树在第i个样本处的预测值；

表示第t棵决策树在第i个样本处的预测值（未知），可以认为f_t (X_i )是前t-1棵树的优化量。
注意区分：t棵决策树和第t棵决策树
使用二阶泰勒展开式(式(6))来近似代替损失函数，加快最小化速度：

又第t次迭代中前t-1棵决策树已经确定，即其损失函数也已经确定，故认为
是常数，将其省略且将式(5)代入得到式(8)：

联立式(2)(3)(8)，得到：

ω_j是叶子节点的权重（对于分类问题，预测类别对应不同的权值；对于回归问题，预测值即为权重）
由式(8)到式(9)，将两个式子中的求和分开：
是所有n个样本对应的预测值（即分类类别的权重）乘以其对应得而梯度gi，求和。
决策树的T个叶子节点，每个样本都一定且唯一被分类到T个节点中的一个，一个叶子节点可以被分到多个样本。先将每个叶子节点上的样本的梯度g_i相加，再乘以该叶子节点的权值；最后对所有叶子节点求和。
两者得而结果一样。
（类比：一个班有n个学生，要求某门课程班级总分；式(8)的求法可理解为直接将每个同学的成绩相加；而式(9)的求法可理解为先求各个分段的同学的成绩总分，再将每个分段总分相加）
对公式(9)求关于ωj的导数，并令其等于零，得到式(10):

将式(10)代入式(9)，得到最优解：

4、分割算法

即将更新。。。

参考文献

Chen T, Guestrin C. XGBoost: A Scalable Tree Boosting System[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2016:785-794.点此下载
小象学院《机器学习升级版》第七期第12课
https://blog.csdn.net/a819825...