XGBoost
XGBoost是我第一个掌握的在工业界成熟使用的算法。
一，XGBoost简介
XGBoost算法又叫极度梯度提升树（Extreme Gradient Boosting），是boosting算法的一种实现方式。在数据竞赛和工业界中都取得了很好的成绩。在15年kaggle社区发布的29个冠军队解决方案中，有17个队伍在他们的队伍中使用了XGBoost。
XGB可以理解成GBDT的一个改进版本，其中的X代表着Extreme，意思是极度，意味着它可以更快更高效地训练部署模型。
二，基于树的集成学习方法
XGBoost也是一种基于树的集成学习方法。因此在介绍XGBoost之前，我们还是先说基于树的集成学习方法。
集成学习方法简单来说，就是通过某种方式，比如投票，将弱学习器结合成为一个强学习器。而基于树的集成学习方法中的弱学习器就是决策树。关于决策树的知识在周志华老师的西瓜书中写的很详细了，这里不多赘述。
其中比较重要的一点是，在分类任务中和回归任务中，判断结果的方式会有所不同。
对于回归树：预测结果会落在每片叶子上，回归树会将叶子上的数值求平均就是这片叶子结点的回归结果。
对于分类树：最终类别号会落在每片叶子上，叶子会遵循少数服从多数的结果，给出最终预测结果。
同时基于树的集成学习不用做特征归一化，使用起来非常方便；此外也可以做到特征组合，不用自己做升维。最后他们可以做到大规模数据并行处理，使得训练过程更快。
基于树的集成学习方法中比较著名的就是随机森林算法。
同时bagging和boosting是两种集成学习方法，上文所说的随机森林属于前者，XGB属于后者。
Bagging 是 Bootstrap Aggregating 的简称，意思就是再取样 (Bootstrap) 然后在每个样本上训练出来的模型取平均，所以是降低模型的 variance. Bagging 比如 Random Forest 这种先天并行的算法都有这个效果。
Boosting 则是迭代算法，每一次迭代都根据上一次迭代的预测结果对样本进行加权，所以随着迭代不断进行，误差会越来越小，所以模型的 bias 会不断降低。比如 Adaptive Boosting，XGBoost 就是 Boosting 算法。
三，目标函数
大多数机器学习算法中，目标函数总是一个很重要的部分。对于基于树的集成学习模型来说，这个点影响了两个重要问题：1，怎么设置叶子节点的值？2，怎么构造树的结构？
在经典的“决策树”算法中，ID3的目标函数基于“信息熵”，CART的目标函数基于“GINI系数”。而在XGboost中，“决策树“的目标函数引入了”偏差“这个变量，这也是XGBoost的魅力所在。
同时XGBoost整体思想就是直接把损失函数和正则项加起来合成一个整体的损失函数，对这个损失函数求二阶导，得到最终的目标函数，通过目标函数计算得到一个分数，这个分数越小越好，最终通过目标函数计算得到的分数确定了树的结构和整个强学习器的分数。所以XGBoost不是通过拟合残差实现的，而是计算目标函数直接得到的树结构。
1，函数形式
上图即为目标函数，左项为训练损失，用于评估拟合训练数据的效果有多好。右项为正则化项，提高模型的泛化能力，能够更好的再测试集或者预测集预测的更准确。这也是XGB对GBDT的一个提升，GBDT没有考虑模型的复杂性。基于树的集成学习，我们并不像线性回归任务一样有W参数，但是也有要求的参数。就是树的结构和叶子结点的分值。对于正则项，我们希望分值参数越小越好，因为越小模型越简单、泛化能力越强。
同时XGBoost作为一种Boosting算法，它的每一个决策树，都和上一颗决策树有关。详细地说，下一颗决策树会更加关注上一颗决策树的错误。因此，具体到第t颗树，它的目标函数是这样的。
对于上图两个公式结合k棵树对样本i的预测值=前k-1棵预测树的预测值+第k棵树的预测值。
2，优化函数
等到上图的函数以后，我们索要的就是优化该函数。怎么样才能使目标函数最小？
XGBoost，使用了一种类似于梯度下降的方法。用牛顿法快速地优化目标：
其中 gi 和 hi 分别代表损失函数的一阶和二阶导数。去掉其中的常数项以后，同时将其中的正则化项打开，并设定
其中的 T 为表示叶子结点数量，wi表示该树中，第i个叶子结点的值。现在我们可以通过简单的高中函数知识得到优化目标：
至此我们解决了第一个问题：如何设置叶子结点的值，使得目标函数最小。
3，确定树结构
解决完第一个问题以后，在实际应用中还有一个问题：我们无法做到遍历所有的树形结构，也就是说我们不能通过计算所有树形结构的目标函数值，而实现选出其中最小那个。因此我们要回答第二个问题：怎么构造树的结构？
在无法遍历所有可能的情况下，我们最好的做法就是使用贪心算法的思想。即：就是保证每一步都是最优解，从而接近全局最优解的方法。在XGBoost中就是保证每一次结点的分裂产生的新的树，都是目标函数值最小的。这一点和普通的决策树算法是一样的。
如果当前结点A要分裂成B和C，原先A结点的目标函数值，减去B和C部分的目标函数值的和。如果大于0，则代表分裂有益，可以分裂。同时我们注意到这个公式的最后加入了惩罚项，这是因为在分裂增益过小时，分裂增益无法抵消分裂带来的模型复杂度的副作用。重复分裂步骤，直到整个决策树所有特征都被使用，或者已经达到限定的层数。
四，特征划分
根据目标函数，我们已经解决了两个问题：1，怎么设置叶子节点的值？2，怎么构造树的结构？但是，现在还有一个重要的问题就是，如何划分特征，也就是如何提出候选分裂节点。XGBoost中使用的是Weighted Quantile Sketch，可以翻译成加权分位法。
为了得到值得进行尝试的划分点，我们需要一个函数对该特征的特征值进行”重要性”排序。根据排序的结果，再选出值得进行尝试的特征值。其中XGBoost提出一个用于排序重要性的函数，如下图：
其中的 Dk 第k个特征的每个样本的特征值 xnk 与其相应的 hi (即前文提到的二阶函数统计量)组成的集合。其表示特征值k小于z的实例的比例。之后对一个特征的所有特征值进行排序。在排序之后，设置一个值 ϵ 。这个值用于对要划分的点进行规范。同时满足要求如下：
对于特征k的特征值的划分点 {sk1,sk2…skl} 有，两个相连划分点的 rk 值的差的绝对值要小于 ϵ 。同时，为了增大算法的效率，也可以选择每个切分点包含的特征值数量尽可能多。简单来说，根据特征值的 rk 进行排序后，大约要选出 1/ϵ 个的点作为切分点。
在我们得到了使用加权分位法的分裂点之后，在贪心算法的分裂过程中，我们就只需要对这几个分裂点进行尝试，而不需要与原先一样，对所有的特征值进行尝试。这大大减少了算法的开销。
参考
最后的XGBoost的实战，可以参考另一篇博文。