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的知名度和用户数不断攀升，已经跨过了百万用户的大关，进一步巩固了它在数据科学界家喻户晓的地位。
1700539967
1700539968
“英雄起于阡陌，壮士拔于行伍”，Kaggle也不是平地惊雷般出现的，而是起于创始人一个非常朴素的想法。2010年，就职于澳大利亚财政部的Anthony Goldbloom对他当前的工作略感失望，他的主要工作是预测GDP、通货膨胀和失业，但传统的经济数据规模很小而且噪声很大，所以很难得出有趣的发现。为了获得更有趣的数据集和问题，Anthony利用业余时间构建了Kaggle，这个日后最火热的机器学习竞赛平台就这样诞生了。
1700539969
1700539970
和最初的愿景有所不同，Kaggle的发展有些出乎Anthony的意料。本来只想收集一些有趣的问题和数据供自己研究，但随着越来越多的大神加入，Anthony发现自己无论如何也做不了那么好。既然如此，Anthony索性致力于社区的发展，期望让 Kaggle成为一个充满活力的代码、数据和讨论的生态系统。也正是这样的改变，让Kaggle注入了开放的基因。
1700539971
1700539972
时至今日，Kaggle已经成了Google AI生态中不可或缺的一环，Anthony在回顾自己创业经历的时候，说了两点建议。一是，去解决那些你自己有切身体会，并且觉得其他人也正经历，而且还没有被解决的问题；二是，你要对这个问题充满热情。
1700539973
1700539974
不过笔者还是要说，“时势造英雄啊”，Kaggle正是在AI第三次热潮的风口“飞”起来的。祝各位创业者在有激情，能够解决痛点的同时，还有一个好的运气。