XGBoost笔记

xgboost研读过程笔记，写的不对的地方请指正

——————————————————————————————————

集成树目标函数：

提升树目标函数：

前半部分为loss function，后半部分为 regularization， fi为表示一棵树，包含结构和叶子分数等。

Additive Training

如果考虑使用均方误差作为损失函数则：

均方误差包含一次残差项，和二次项。但是，对于损失函数（如logloss）想要得到如此标准的包含一次，二次项的目标函数，通常情况下是对loss function 在当前f（x）上进行泰勒展开：

其中：

分别表示梯度在当前残差的一阶导和二阶导。去除常数项之后，对于时刻t的目标函数为：

新的目标函数仅包含残差的一次导项和二次导项。因此XGBoost可以用任何包含一次项和二次项的损失函数做为目标函数。

模型复杂度

对于当前树的复杂度，定义树f（x）为：

其中W为叶子的值向量，q表示每个数据点和叶子结点的映射关系。T为叶子节点数，在XGBoost中，树的复杂度定义为：

两个参数在软件接口中又给出，可通过交叉验证的得到参数值。

训练目标

经过前面部分的推导，可以得到第t棵树的目标函数为：

其中表示分到叶子节点j的所有数据点的集合。分到相同的叶子节点的数据点，预测得分是一样的。定义和可得：

注意到式子中的是二次的，因此，可以求得给定数据和叶子节点关系q(x)，可得到最优梯度下降为：

第二个式子衡量该树的好坏，即在该树结构下，梯度最多减少多少（structure score）。官方教程中解释该式子给出了图：

该式子不仅作为决策树的衡量标准，将模型的复杂度也考虑了进去。

———————————————————————————

构建树

论文中对于节点分裂的方法：

贪心：

公式解释：假设当前节点为a，1、计算a的左孩子的得分，2、计算a的右孩子的得分，3不分割的分数，4最后一项是对新增加的叶子几点的正则化，具有剪枝作用。如果增益gain小于0则不分裂该结点。对于实际数据，从左往右扫描所有分裂节点，找出最佳分裂节点即可。

算法流程：

算法整体概括

论文中正对大数据集采取的近似分裂方法（对特征抽样）

后续代码走读部分就不写了，自己看去了。。。。。

参考文献

（1）http://blog.csdn.net/a819825294/article/details/51206410#t0

（2）Introduction to Boosted Trees

（3）XGBoost: A Scalable Tree Boosting System