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
1700539930
1700539931
1700539932
1700539933
（12.6）
1700539934
1700539935
容易计算出分裂前后损失函数的差值为
1700539936
1700539937
1700539938
1700539939
1700539940
（12.7）
1700539941
1700539942
XGBoost采用最大化这个差值作为准则来进行决策树的构建，通过遍历所有特征的所有取值，寻找使得损失函数前后相差最大时对应的分裂方式。此外，由于损失函数前后存在差值一定为正的限制，此时γ起到了一定的预剪枝效果。
1700539943
1700539944
除了算法上与传统的GBDT有一些不同外，XGBoost还在工程实现上做了大量的优化。总的来说，两者之间的区别和联系可以总结成以下几个方面。
1700539945
1700539946
（1）GBDT是机器学习算法，XGBoost是该算法的工程实现。
1700539947
1700539948
（2）在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。
1700539949
1700539950
（3）GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。
1700539951
1700539952
（4）传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类器，比如线性分类器。
1700539953
1700539954
（5）传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机森林相似的策略，支持对数据进行采样。
1700539955
1700539956
（6）传统的GBDT没有设计对缺失值进行处理，XGBoost能够自动学习出缺失值的处理策略。
1700539957
1700539958
逸闻趣事
1700539959
1700539960
1700539961
1700539962
机器学习竞赛平台Kaggle的前世今生
1700539963
1700539964
XGBoost的火热与Kaggle的机器学习竞赛是分不开的，正是在各类竞赛中突出的表现，让XGBoost成为非常流行的机器学习框架，借此机会我们也向大家介绍一下Kaggle的前世今生。
1700539965
1700539966
Kaggle是全球机器学习竞赛、开放数据集和数据科学合作的发源地，也是当今最著名最火热的机器学习竞赛平台。在被谷歌收购之后，Kaggle的知名度和用户数不断攀升，已经跨过了百万用户的大关，进一步巩固了它在数据科学界家喻户晓的地位。