XGBoost

• [x] 为什么xgboost要使用二阶的泰勒展开？

  进行二阶泰勒展开主要目的是为了后面目标函数对叶子结点权值求导，然后算出当前结构的最优叶子结点的权值，代入目标函数后得到一个值称为结构分数，根据结构分数的变化我们可以选择分裂节点，也就是树的结构。所以二阶泰勒展开只是为了将目标函数化成一个类似 Gain的概念的函数。也就是可以让xgboost能够自定义 loss function xgboost使用了一阶和二阶偏导, 二阶导数有利于梯度下降的更快更准. 使用泰勒展开取得函数做自变量的二阶导数形式, 可以在不选定损失函数具体形式的情况下, 仅仅依靠输入数据的值就可以进行叶子分裂优化计算, 本质上也就把损失函数的选取和模型算法优化/参数选择分开了. 这种去耦合增加了xgboost的适用性, 使得它按需选取损失函数, 可以用于分类, 也可以用于回归。 简短来说，就是为了统一损失函数求导的形式以支持自定义损失函数。当然，这是从为什么会想到引入泰勒二阶的角度来说的。

• [x] 分裂的准则

  xgboost自定义损失函数之后，一种分裂结构，会对应一种叶子权值的最优值，也会对应一个结构分数（loss function），那么分裂前和分裂后的损失下降了多少呢（不一定会下降），每一轮选取损失下降最大的特征及其分割点作为分裂点，其实就类似与选取 增益 Gain 最大的特征分割点。不过这个Gain ，xgboost使用自定义loss function的差值定义的。

• [x] Xgboost如何处理缺失值

  通常情况下，我们人为在处理缺失值的时候大多会选用中位数、均值或是二者的融合来对数值型特征进行填补，使用出现次数最多的类别来填补缺失的类别特征。 论文中关于缺失值的处理将其看与稀疏矩阵的处理看作一样。在寻找split point的时候，不会对该特征为missing的样本进行遍历统计，只对该列特征值为non-missing的样本上对应的特征值进行遍历，通过这个技巧来减少了为稀疏离散特征寻找split point的时间开销。在逻辑实现上，为了保证完备性，会分别处理将missing该特征值的样本分配到左叶子结点和右叶子结点的两种情形，计算增益后选择增益大的方向进行分裂即可。 计算这个结构分数的下降程度 故这个与缺失无关，这是可以计算出来的。从而是可以计算出来的。 可以为缺失值或者指定的值指定分支的默认方向，这能大大提升算法的效率。如果在训练中没有缺失值而在预测中出现缺失，那么会自动将缺失值的划分方向放到右子树。

• [x] XGb与GBDT的区别

  首先，xgboost与gbdt的区别 ：

  1. GBDT是机器学习算法，XGBoost是该算法的工程实现。
  2. 在使用CART作为基分类器时，XGBoost显式地加入了正则项来控制模 型的复杂度，有利于防止过拟合，从而提高模型的泛化能力。
  3. GBDT在模型训练时只使用了代价函数的一阶导数信息，XGBoost对代 价函数进行二阶泰勒展开，可以同时使用一阶和二阶导数。
  4. 传统的GBDT采用CART作为基分类器，XGBoost支持多种类型的基分类 器，比如线性分类器。
  5. 传统的GBDT在每轮迭代时使用全部的数据，XGBoost则采用了与随机 森林相似的策略，支持对数据进行采样。
  6. 传统的GBDT没有设计对缺失值进行处理，XGBoost能够自动学习出缺 失值的处理策略。

前言：

类比于Cart决策树的构造，其实就是寻找分裂节点，使得gini指数最小。那么XGBoost集成树的训练目标也想变成这样的形式，其目标就是在构造新的树的时候（新的分裂规则），使得一个损失函数最小。那么要做到这一点，XGBoost做的工作就是将损失函数换成二阶泰勒展开的形式，再经过一系列的转换，最终得到这样的目标。

总的指导原则如就职Google的读者crab6789所说：

实质是把样本分配到叶子结点会对应一个obj，优化过程就是obj优化。也就是分裂节点到叶子不同的组合，不同的组合对应不同obj，所有的优化围绕这个思想展开。

1. 什么是XGBoost

XGBoost是陈天奇等人开发的一个开源机器学习项目，高效地实现了GBDT算法并进行了算法和工程上的许多改进，被广泛应用在Kaggle竞赛及其他许多机器学习竞赛中并取得了不错的成绩。
说到XGBoost，不得不提GBDT(Gradient Boosting Decision Tree)。因为XGBoost本质上还是一个GBDT，但是力争把速度和效率发挥到极致，所以叫X (Extreme) GBoosted。包括前面说过，两者都是boosting方法。
关于GBDT，这里不再提，可以查看我前一篇的介绍，点此跳转。

1.1 XGBoost树的定义

先来举个例子，我们要预测一家人对电子游戏的喜好程度，考虑到年轻和年老相比，年轻更可能喜欢电子游戏，以及男性和女性相比，男性更喜欢电子游戏，故先根据年龄大小区分小孩和大人，然后再通过性别区分开是男是女，逐一给各人在电子游戏喜好程度上打分，如下图所示。

就这样，训练出了2棵树tree1和tree2，类似之前gbdt的原理，两棵树的结论累加起来便是最终的结论，所以小孩的预测分数就是两棵树中小孩所落到的结点的分数相加：2 + 0.9 = 2.9。爷爷的预测分数同理：-1 + （-0.9）= -1.9。具体如下图所示：

恩，你可能要拍案而起了，惊呼，这不是跟上文介绍的GBDT乃异曲同工么？
事实上，如果不考虑工程实现、解决问题上的一些差异，XGBoost与GBDT比较大的不同就是目标函数的定义。XGBoost的目标函数如下图所示：
其中：

• 红色箭头所指向的L 即为损失函数（比如平方损失函数：，或logistic损失函数：）
• 红色方框所框起来的是正则项（包括L1正则、L2正则）
• 红色圆圈所圈起来的为常数项
• 对于，xgboost利用泰勒展开三项，做一个近似

1.2 XGBoost目标函数

xgboost的核心算法思想不难，基本就是

• 不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。

注：为叶子节点 的分数，对应了所有K棵回归树（regression tree）的集合，而为其中一棵回归树。

• 当我们训练完成得到k棵树，我们要预测一个样本的分数，其实就是根据这个样本的特征，在每棵树中会落到对应的一个叶子节点，每个叶子节点就对应一个分数
• 最后只需要将每棵树对应的分数加起来就是该样本的预测值。

那么我们怎么去添加新的树呢，依据什么原则？

显然，我们的目标是要使得树群的预测值尽量接近真实值，而且有尽量大的泛化能力。
所以，从数学角度看这是一个泛函最优化问题，故把目标函数简化如下：

如你所见，这个目标函数分为两部分：损失函数和正则化项。且损失函数揭示训练误差（即预测分数和真实分数的差距），正则化定义复杂度。

其实也就是 损失函数 = 经验风险 + 结构风险 经验风险造成欠拟合， 结构风险造成过拟合， 所以我们的模型需要在这两者之间做一个折中。 其中，误差/损失函数鼓励我们的模型尽量去拟合训练数据，使得最后的模型会有比较少的 bias。而正则化项则鼓励更加简单的模型。因为当模型简单之后，有限数据拟合出来结果的随机性比较小，不容易过拟合，使得最后模型的预测更加稳定。

再回到目标函数：

忽略损失函数 中的（别忘了上面说的“ 在第t步，是真实值，即已知 ”，不影响后续目标函数对的偏导计算），做下一一对应：

• 泰勒二阶展开f 里的x对应目标函数里的，
• f 里的对应目标函数的，
• 从而f 对x求导数时，对应为目标函数对求偏导

得到：

其中，，

1.3 XGBoost正则项：树的复杂度

当我们把树成结构部分q和叶子权重部分w后，结构函数q把输入映射到叶子的索引号上面去，而w给定了每个索引号对应的叶子分数是什么。

另外，如下图所示，xgboost对树的复杂度包含了两个部分：

1. 一个是树里面叶子节点的个数，也就是树越来越多，损失函数的经验风险下降会越来越缓慢，而结构风险会占主要的部分，则新树的叶子结点个数会越来越少。
2. 一个是树上叶子节点的得分的模平方（对模平方（对进行正则化，相当于针对每个叶结点的得分增加平滑，目的是为了避免过拟合)。

所以我们就有变形后的目标函数：

理解这个推导的关键在哪呢？在和AI lab陈博士讨论之后，其实就在于理解这个定义：被定义为每个叶节点 j 上面样本下标的集合 ，这个定义里的要表达的是：每个样本值 都能通过函数映射到树上的某个叶子节点，从而通过这个定义把两种累加统一到了一起。也就是说假设我们这个树的结构（每一个样本对应哪个叶子结点）是已知的，那么就可以把原来对每一个样本的损失，转化到每一个叶子结点上面的损失。

接着，我们可以定义

最终公式可以化简为

通过对求导等于0，可以得到

然后把最优解代入得到：

当我们假设知道了每个样本对应的叶子结点所属之后，我们就可以将损失函数简化，从而可以对每一个叶子结点的取值 求导，这样就可以得到当前树结构的最优的损失函数的值。那么现在就是说我们找到了一个对应关系，每个树结构，对应一个损失函数，那么我们可以根据这个关系来分裂树。这个 叫结构分数，根据分裂前后结构分数的下降大小，来选择分裂的节点。

1.4 XGBoost正则项：树的复杂度

Obj代表了当我们指定一个树的结构的时候，我们在目标上面最多减少到多少。我们可以把它叫做结构分数(structure score), 也就是指定一个树的结构就能计算出一个结构分数， 所以这个结构分数越小，那么这个树的结构越好。

2. 树的分裂

当我们有了一个树的结构对应的目标函数，那我们要做的不就是找到这棵树吗？那么我们怎么去找这么一个树呢？一个想当然的方法是：不断地枚举不同树的结构，然后利用打分函数来寻找出一个最优结构的树，接着加入到模型中，不断重复这样的操作。而再一想，你会意识到要枚举的状态太多了，基本属于无穷种，那根本就不可能。可以选择贪心算法， 我们试下贪心法，从树深度0开始，每一节点都遍历所有的特征，比如年龄、性别等等，然后对于某个特征，先按照该特征里的值进行排序，然后线性扫描该特征进而确定最好的分割点，最后对所有特征进行分割后，我们选择所谓的增益Gain最高的那个特征，而Gain如何计算呢？增益其实就是分裂这个叶子节点带来的损失函数的下降
我们的损失函数为：

表达式 的意思其实就是表示着每一个叶子节点对当前模型损失的贡献程度，如果说分裂后的要比分裂前的小，小多少？当然是越小越好，那么当一个叶子结点分成两个叶子结点，其损失的变化是啥？可以定义一个增益，那么这就回到了前言说的那里表达的意思。

1. 特征值进行排序

一个值得注意的地方：为什么要对特征里的值进行排序之后来找最优分割点？

比如设置一个值a，然后枚举所有x < a、a < x这样的条件（x代表某个特征比如年龄age，把age从小到大排序：假定从左至右依次增大，则比a小的放在左边，比a大的放在右边），对于某个特定的分割a，我们要计算a左边和右边的导数和。

比如总共五个人，按年龄排好序后，一开始我们总共有如下4种划分方法：

1. 把第一个人和后面四个人划分开
2. 把前两个人和后面三个人划分开
3. 把前三个人和后面两个人划分开
4. 把前面四个人和后面一个人划分开

接下来，把上面4种划分方法全都各自计算一下Gain，看哪种划分方法得到的Gain值最大则选取哪种划分方法，经过计算，发现把第2种划分方法“前面两个人和后面三个人划分开”得到的Gain值最大，意味着在一分为二这个第一层层面上这种划分方法是最合适的。

换句话说，对于所有的特征x，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和GL和GR。然后用计算Gain的公式计算每个分割方案的分数就可以了。
然后后续则依然按照这种划分方法继续第二层、第三层、第四层、第N层的分裂。

这也是为什么XGBoost支持并行化：

注意XGBoost的并行不是tree粒度的并行，XGBoost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。XGBoost的并行是在特征粒度上的。 　　我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

1. 分割不一定会降低损失

第二个值得注意的事情就是引入分割不一定会使得情况变好，所以我们有一个引入新叶子的惩罚项。优化这个目标对应了树的剪枝， 当引入的分割带来的增益小于一个阀值γ 的时候，则忽略这个分割。

换句话说，当引入某项分割，结果太小（比如小于我们的最低期望阀值γ），但却因此得到的复杂度过高，则相当于得不偿失，不如不分割。即做某个动作带来的好处比因此带来的坏处大不了太多，则为避免复杂 多一事不如少一事的态度，不如不做。

相当于在我们发现“分”还不如“不分”的情况下后（得到的增益太小，小到小于阈值γ），会有2个叶子节点存在同一棵子树上的情况。

就职于Google的读者crab6789点评：

把样本从根分配到叶子结点，就是个排列组合。不同的组合对应的cost不同。求最好的组合你就要try，一味穷举是不可能的，所以才出来贪婪法。不看从头到尾 就看当下节点怎么分配最好。这才有了那个exact greddy方法，后来还想加速才有了histogram的做法。

1. 特征值分箱的另一个办法

将特征值进行排序，如果是取值很多的连续特征的话，那么对排序之后的分割点进行选择可以使用等距分箱，等频分箱；论文中还有一个分箱的方法来选择 split points。假设数据集，代表第 个特征，与 每一个样本点的 二阶导数值，定义排序函数：

代表了第 个特征的值小于 的比例，但是每个数据的权重并不是 1 ，而是每个数据的二阶导数值。
那么有了这个公式之后，我们就可以找到分割点了。

这个 一定程度代表了分割点的个数，大约会有 个分割点。如果较小，那么分割点数就多。如果说每个 二阶导数都是 1 的话，那么这就等价于等频分箱，其中每组的比例是 。

3. 总结

总结一下xgboost算法

4. 实例

4.1 xgboost需要调整参数

xgboost的参数分为三类

1. 通用参数，起到宏观控制作用，比如使用什么弱分类器，使用多少线程

2. 弱分类器的参数

3. 目标参数，使用什么方式训练（分类或者回归），使用什么损失函数。

https://zhouchen.blog.csdn.net/article/details/89643720
https://www.cnblogs.com/timssd/p/8231130.html

4.1 General Parameters

• booster [default=gbtree]
  有两中模型可以选择gbtree和gblinear。gbtree使用基于树的模型进行提升计算，gblinear使用线性模型进行提升计算。缺省值为gbtree
• silent [default=0]
  取0时表示打印出运行时信息，取1时表示以缄默方式运行，不打印运行时信息。缺省值为0
• nthread
  XGBoost运行时的线程数。缺省值是当前系统可以获得的最大线程数
• num_pbuffer
  预测缓冲区大小，通常设置为训练实例的数目。缓冲用于保存最后一步提升的预测结果，无需人为设置。

• num_feature
  Boosting过程中用到的特征维数，设置为特征个数。XGBoost会自动设置，无需人为设置。

  4.2 Parameters for Tree Booster

• eta [default=0.3]
  为了防止过拟合，更新过程中用到的收缩步长,类似学习速率。在每次提升计算之后，算法会直接获得新特征的权重。 eta通过缩减特征的权重使提升计算过程更加保守。缺省值为0.3
  取值范围为：[0,1]

• gamma [default=0]
  • 在节点分裂时，只有分裂后损失函数的值下降了，才会分裂这个节点。Gamma指定了节点分裂所需的最小损失函数下降值(加入一个分裂节点所要付出的结构损失)。
  • 这个参数的值越大，算法越保守。属于需要调整的重点参数。
    取值范围为：[0,∞]
• max_depth [default=6]
  • 数的最大深度。缺省值为6。这个值也是用来避免过拟合的。max_depth越大，模型会学到更具体更局部的样本。
  • 典型值为3-10
  • 取值范围为：[1,∞]
• min_child_weight [default=1]
  • 孩子节点中最小的样本权重和。如果一个叶子节点的样本权重和小于min_child_weight则拆分过程结束。在现行回归模型中，这个参数是指建立每个模型所需要的最小样本数。该参数越大算法越conservative ，越小可能会过拟合，越大可能欠拟合
  • 取值范围为：[0,∞]
• max_delta_step [default=0]
  • 这参数限制每棵树权重改变的最大步长。如果这个参数的值为0，那就意味着没有约束。如果它被赋予了某个正值，那么它会让这个算法更加保守。
  • 通常这个参数是没有必要的，但是当各类别的样本十分不平衡的时候，需要设置。把它范围设置为1-10之间也许能控制更新。
  • 取值范围为：[0,∞]
• subsample [default=1]
  • 用于训练模型的子样本占整个样本集合的比例。如果设置为0.5则意味着XGBoost将随机的从整个样本集合中随机的抽取出50%的子样本建立树模型，这能够防止过拟合。
  • 减小这个参数的值，算法会更加保守，避免过拟合。这个值设置得过小，它可能会导致欠拟合。
  • 典型值为0.5-1
  • 取值范围为：(0,1]
• colsample_bytree [default=1]
  • 在建立树时对特征采样的比例。缺省值为1
  • 取值范围为：(0,1]
• lambda
  • 默认1
  • 权重的L2正则化项,增加使得模型保守。

4.3 Parameter for Linear Booster

• lambda [default=0]
  L2 正则的惩罚系数
• alpha [default=0]
  L1 正则的惩罚系数

• lambda_bias
  在偏置上的L2正则。缺省值为0（在L1上没有偏置项的正则，因为L1时偏置不重要）

  4.4 Task Parameters

• objective [ default=reg:linear ]定义学习任务及相应的学习目标，可选的目标函数如下：

  • “reg:linear” —— 线性回归。
  • “reg:logistic”—— 逻辑回归。
  • “binary:logistic”—— 二分类的逻辑回归问题，输出为概率。
  • “binary:logitraw”—— 二分类的逻辑回归问题，输出的结果为wTx。
  • “count:poisson”—— 计数问题的poisson回归，输出结果为poisson分布。在poisson回归中，max_delta_step的缺省值为0.7。(used to safeguard optimization)
  • “multi:softmax” –让XGBoost采用softmax目标函数处理多分类问题，同时需要设置参数num_class（类别个数）
  • “multi:softprob” –和softmax一样，但是输出的是ndata * nclass的向量，可以将该向量reshape成ndata行nclass列的矩阵。没行数据表示样本所属于每个类别的概率。
  • “rank:pairwise” –set XGBoost to do ranking task by minimizing the pairwise loss
• base_score [ default=0.5 ]
  • 所有实例的初始化预测分数，全局偏置；
  • 为了足够的迭代次数，改变这个值将不会有太大的影响。
• eval_metric [ default according to objective ] 损失函数
  • 校验数据所需要的评价指标，不同的目标函数将会有缺省的评价指标（rmse for regression, and error for classification, mean average precision for ranking）-
  • 用户可以添加多种评价指标，对于Python用户要以list传递参数对给程序，而不是map参数list参数不会覆盖’eval_metric’
  • 可供的选择如下:
    • “rmse”: root mean square error
    • “logloss”: negative log-likelihood
    • “error”: Binary classification error rate. It is calculated as #(wrong cases)/#(all cases). For the predictions, the evaluation will regard the instances with prediction value larger than 0.5 as positive instances, and the others as negative instances.
    • “merror”: Multiclass classification error rate. It is calculated as #(wrongcases)#(allcases).
    • “mlogloss”: Multiclass logloss
    • “auc”: Area under the curve for ranking evaluation.
    • “ndcg”:Normalized Discounted Cumulative Gain
    • “map”:Mean average precision
    • “ndcg@n”,”map@n”: n can be assigned as an integer to cut off the top positions in the lists for evaluation.
    • “ndcg-“,”map-“,”ndcg@n-“,”map@n-“: In XGBoost, NDCG and MAP will evaluate the score of a list without any positive samples as 1. By adding “-” in the evaluation metric XGBoost will evaluate these score as 0 to be consistent under some conditions. training repeatively
• seed [ default=0 ]
  • 随机数的种子。缺省值为0