1700539880
场景描述
1700539881
1700539882
XGBoost是陈天奇等人开发的一个开源机器学习项目，高效地实现了GBDT算法并进行了算法和工程上的许多改进，被广泛应用在Kaggle竞赛及其他许多机器学习竞赛中并取得了不错的成绩。我们在使用XGBoost平台的时候，也需要熟悉XGBoost平台的内部实现和原理，这样才能够更好地进行模型调参并针对特定业务场景进行模型改进。
1700539883
1700539884
知识点
1700539885
1700539886
XGBoost，GBDT，决策树
1700539887
1700539888
问题 XGBoost与GBDT的联系和区别有哪些？
1700539889
1700539890
难度：★★★☆☆
1700539891
1700539892
分析与解答
1700539893
1700539894
原始的GBDT算法基于经验损失函数的负梯度来构造新的决策树，只是在决策树构建完成后再进行剪枝。而XGBoost在决策树构建阶段就加入了正则项，即
1700539895
1700539896
1700539897
，
1700539898
1700539899
（12.2）
1700539900
1700539901
其中Ft−1(xi)表示现有的t−1棵树最优解。关于树结构的正则项定义为
1700539902
1700539903
1700539904
，
1700539905
1700539906
（12.3）
1700539907
1700539908
其中T为叶子节点个数，wj表示第j个叶子节点的预测值。对该损失函数在Ft−1处进行二阶泰勒展开可以推导出
1700539909
1700539910
1700539911
1700539912
1700539913
（12.4）
1700539914
1700539915
1700539916
1700539917
其中T为决策树ft中叶子节点的个数，，，Ij表示所有属于叶子节点j的样本的索引的结合。
1700539918
1700539919
假设决策树的结构已知，通过令损失函数相对于wj的导数为0可以求出在最小化损失函数的情况下各个叶子节点上的预测值
1700539920
1700539921
1700539922
1700539923
1700539924
（12.5）
1700539925
1700539926
然而从所有的树结构中寻找最优的树结构是一个NP-hard问题，因此在实际中往往采用贪心法来构建出一个次优的树结构，基本思想是从根节点开始，每次对一个叶子节点进行分裂，针对每一种可能的分裂，根据特定的准则选取最优的分裂。不同的决策树算法采用不同的准则，如IC3算法采用信息增益，C4.5算法为了克服信息增益中容易偏向取值较多的特征而采用信息增益比，CART算法使用基尼指数和平方误差，XGBoost也有特定的准则来选取最优分裂。
1700539927
1700539928
通过将预测值代入到损失函数中可求得损失函数的最小值
1700539929