算法梳理之XGB_给定以下的便利商店选点数据集,并采用 cart

1.CART树

1.1原理

所谓CART，也就是Classification And Regression Tree是决策树的一种，并且是非常重要的决策树。CART算法既可以用于创建分类树，也可以用于创建回归树。两者在建树的过程稍有差异。

创建分类树的递归过程中：CART每次都选择当前数据集中具有最小Gini信息增益的特征作为结点划分决策树。ID3算法和C4.5算法虽然在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分支、规模较大，CART算法的二分法可以简化决策树的规模，提高生成决策树的效率。对于连续特征，CART也是采取和C4.5同样的方法处理。为了避免过拟合(Overfitting)，CART决策树需要剪枝。预测过程当然也就十分简单，根据产生的决策树模型，延伸匹配特征值到最后的叶子节点即得到预测的类别。

创建回归树时，观察值取值是连续的、没有分类标签，只有根据观察数据得出的值来创建一个预测的规则。在这种情况下，Classification Tree的最优划分规则就无能为力，CART则使用最小剩余方差(Squared Residuals Minimization)来决定Regression Tree的最优划分，该划分准则是期望划分之后的子树误差方差最小。创建模型树，每个叶子节点则是一个机器学习模型，如线性回归模型

CART算法的重要基础包含以下三个方面：

1）二分(Binary Split)：在每次判断过程中，都是对观察变量进行二分。
CART算法采用一种二分递归分割的技术，算法总是将当前样本集分割为两个子样本集，使得生成的决策树的每个非叶结点都只有两个分枝。因此CART算法生成的决策树是结构简洁的二叉树。因此CART算法适用于样本特征的取值为是或非的场景，对于连续特征的处理则与C4.5算法相似。

2）单变量分割(Split Based on One Variable)：每次最优划分都是针对单个变量。

3）剪枝策略：CART算法的关键点，也是整个Tree-Based算法的关键步骤。
剪枝过程特别重要，所以在最优决策树生成过程中占有重要地位。有研究表明，剪枝过程的重要性要比树生成过程更为重要，对于不同的划分标准生成的最大树(Maximum Tree)，在剪枝之后都能够保留最重要的属性划分，差别不大。反而是剪枝方法对于最优树的生成更为关键。

1.2过程

CART假设决策树是二叉树，内部结点特征的取值为“是”和“否”，左分支是取值为“是”的分支，右分支是取值为“否”的分支。这样的决策树等价于递归地二分每个特征，将输入空间即特征空间划分为有限个单元，并在这些单元上确定预测的概率分布，也就是在输入给定的条件下输出的条件概率分布。

CART算法由以下两步组成：

1.决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大； 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时损失函数最小作为剪枝的标准。

2.CART决策树的生成就是递归地构建二叉决策树的过程。CART决策树既可以用于分类也可以用于回归。本文我们仅讨论用于分类的CART。对分类树而言，CART用Gini系数最小化准则来进行特征选择，生成二叉树。 CART生成算法如下：

输入：训练数据集D，停止计算的条件：
输出：CART决策树。

根据训练数据集，从根结点开始，递归地对每个结点进行以下操作，构建二叉决策树：

设结点的训练数据集为D，计算现有特征对该数据集的Gini系数。此时，对每一个特征A，对其可能取的每个值a，根据样本点对A=a的测试为“是”或 “否”将D分割成D1和D2两部分，计算A=a时的Gini系数。

在所有可能的特征A以及它们所有可能的切分点a中，选择Gini系数最小的特征及其对应的切分点作为最优特征与最优切分点。依最优特征与最优切分点，从现结点生成两个子结点，将训练数据集依特征分配到两个子结点中去。
对两个子结点递归地调用步骤l~2，直至满足停止条件。
生成CART决策树。
算法停止计算的条件是结点中的样本个数小于预定阈值，或样本集的Gini系数小于预定阈值（样本基本属于同一类），或者没有更多特征。

2.XGB算法原理

2.1定义树的复杂度

把树拆分成结构部分q和叶子权重部分w。
树的复杂度函数和样例：

定义树的结构和复杂度的原因很简单，这样就可以衡量模型的复杂度，从而可以有效控制过拟合。

2.2 xgboost中的boosting tree模型

和传统的boosting tree模型一样，xgboost的提升模型也是采用的残差（或梯度负方向），不同的是分裂结点选取的时候不一定是最小平方损失。

2.3 对目标函数的改写

最终的目标函数只依赖于每个数据点的在误差函数上的一阶导数和二阶导数。这么写的原因很明显，由于之前的目标函数求最优解的过程中只对平方损失函数时候方便求，对于其他的损失函数变得很复杂，通过二阶泰勒展开式的变换，这样求解其他损失函数变得可行了。

当定义了分裂候选集合的时候，可以进一步改目标函数。分裂结点的候选响集是很关键的一步，这是xgboost速度快的保证，怎么选出来这个集合，后面会介绍。

求解：

2.4 树结构的打分函数

Obj代表了当指定一个树的结构的时候，在目标上面最多减少多少。(structure score)

对于每一次尝试去对已有的叶子加入一个分割

这样就可以在建树的过程中动态的选择是否要添加一个结点。

假设要枚举所有x < a 这样的条件，对于某个特定的分割a，要计算a左边和右边的导数和。对于所有的a，我们只要做一遍从左到右的扫描就可以枚举出所有分割的梯度和GL、GR。然后用上面的公式计算每个分割方案的分数就可以了。

2.5 寻找分裂结点的候选集

1、暴力枚举

2、近似方法

近似方法通过特征的分布，按照百分比确定一组候选分裂点，通过遍历所有的候选分裂点来找到最佳分裂点。
两种策略：全局策略和局部策略。在全局策略中，对每一个特征确定一个全局的候选分裂点集合，就不再改变；而在局部策略中，每一次分裂 都要重选一次分裂点。前者需要较大的分裂集合，后者可以小一点。对比补充候选集策略与分裂点数目对模型的影响。 全局策略需要更细的分裂点才能和局部策略差不多

3、Weighted Quantile Sketch

陈天奇提出并从概率角度证明了一种带权重的分布式的Quantile Sketch

3.损失函数

对于回归问题，我们常用的损失函数是MSE，即：

对于分类问题，我们常用的损失函数是对数损失函数：

XGBoost目标函数定义为：


目标函数由两部分构成，第一部分用来衡量预测分数和真实分数的差距，另一部分则是正则化项。正则化项同样包含两部分，T表示叶子结点的个数，w表示叶子节点的分数。γ可以控制叶子结点的个数，λ可以控制叶子节点的分数不会过大，防止过拟合。

正如上文所说，新生成的树是要拟合上次预测的残差的，即当生成t棵树后，预测分数可以写成：

同时，可以将目标函数改写成：

很明显，我们接下来就是要去找到一个f_t能够最小化目标函数。XGBoost的想法是利用其在f_t=0处的泰勒二阶展开近似它。所以，目标函数近似为：

其中g_i为一阶导数，h_i为二阶导数：

由于前t-1棵树的预测分数与y的残差对目标函数优化不影响，可以直接去掉。简化目标函数为：

上式是将每个样本的损失函数值加起来，我们知道，每个样本都最终会落到一个叶子结点中，所以我们可以将所以同一个叶子结点的样本重组起来，过程如下图：

因此通过上式的改写，我们可以将目标函数改写成关于叶子结点分数w的一个一元二次函数，求解最优的w和目标函数值就变得很简单了，直接使用顶点公式即可。因此，最优的w和目标函数公式为

4.分裂结点算法

在上面的推导中，我们知道了如果我们一棵树的结构确定了，如何求得每个叶子结点的分数。但我们还没介绍如何确定树结构，即每次特征分裂怎么寻找最佳特征，怎么寻找最佳分裂点。

正如上文说到，基于空间切分去构造一颗决策树是一个NP难问题，我们不可能去遍历所有树结构，因此，XGBoost使用了和CART回归树一样的想法，利用贪婪算法，遍历所有特征的所有特征划分点，不同的是使用上式目标函数值作为评价函数。具体做法就是分裂后的目标函数值比单子叶子节点的目标函数的增益，同时为了限制树生长过深，还加了个阈值，只有当增益大于该阈值才进行分裂。

5.正则化

xgboost使用了如下的正则化项：

注意：这里出现了γ和λ，这是xgboost自己定义的，在使用xgboost时，你可以设定它们的值，显然，γ越大，表示越希望获得结构简单的树，因为此时对较多叶子节点的树的惩罚越大。λ越大也是越希望获得结构简单的树。

为什么xgboost要选择这样的正则化项？很简单，好使！效果好才是真的好。

6.对缺失值处理

xgboost模型却能够处理缺失值，模型允许缺失值存在。

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

7.优缺点

优点：

1） xgBoosting支持线性分类器，相当于引入L1和L2正则化项的逻辑回归（分类问题）和线性回归（回归问题）；

2） xgBoosting对代价函数做了二阶Talor展开，引入了一阶导数和二阶导数；

3）当样本存在缺失值是，xgBoosting能自动学习分裂方向；

4）xgBoosting借鉴RF的做法，支持列抽样，这样不仅能防止过拟合，还能降低计算；

5）xgBoosting的代价函数引入正则化项，控制了模型的复杂度，正则化项包含全部叶子节点的个数，每个叶子节点输出的score的L2模的平方和。从贝叶斯方差角度考虑，正则项降低了模型的方差，防止模型过拟合；

6）xgBoosting在每次迭代之后，为叶子结点分配学习速率，降低每棵树的权重，减少每棵树的影响，为后面提供更好的学习空间；

7）xgBoosting工具支持并行,但并不是tree粒度上的，而是特征粒度，决策树最耗时的步骤是对特征的值排序，xgBoosting在迭代之前，先进行预排序，存为block结构，每次迭代，重复使用该结构，降低了模型的计算；block结构也为模型提供了并行可能，在进行结点的分裂时，计算每个特征的增益，选增益最大的特征进行下一步分裂，那么各个特征的增益可以开多线程进行；

8）可并行的近似直方图算法，树结点在进行分裂时，需要计算每个节点的增益，若数据量较大，对所有节点的特征进行排序，遍历的得到最优分割点，这种贪心法异常耗时，这时引进近似直方图算法，用于生成高效的分割点，即用分裂后的某种值减去分裂前的某种值，获得增益，为了限制树的增长，引入阈值，当增益大于阈值时，进行分裂；

缺点：

1）xgBoosting采用预排序，在迭代之前，对结点的特征做预排序，遍历选择最优分割点，数据量大时，贪心法耗时，LightGBM方法采用histogram算法，占用的内存低，数据分割的复杂度更低；

2）xgBoosting采用level-wise生成决策树，同时分裂同一层的叶子，从而进行多线程优化，不容易过拟合，但很多叶子节点的分裂增益较低，没必要进行跟进一步的分裂，这就带来了不必要的开销；LightGBM采用深度优化，leaf-wise生长策略，每次从当前叶子中选择增益最大的结点进行分裂，循环迭代，但会生长出更深的决策树，产生过拟合，因此引入了一个阈值进行限制，防止过拟合.

8.sklearn参数

1. eta [默认 0.3]

和 GBM 中的 learning rate 参数类似。 通过减少每一步的权重，可以提高模型的稳定性。 典型值为 0.01-0.2。

2. min_child_weight [默认 1]

决定最小叶子节点样本权重和。和 GBM 的 min_child_leaf 参数类似，但不完全一样。XGBoost 的这个参数是最小样本权重的和，而 GBM 参数是最小样本总数。这个参数用于避免过拟合。当它的值较大时，可以避免模型学习到局部的特殊样本。但是如果这个值过高，会导致欠拟合。这个参数需要使用 CV 来调整。

3. max_depth [默认 6]

和 GBM 中的参数相同，这个值为树的最大深度。这个值也是用来避免过拟合的。max_depth 越大，模型会学到更具体更局部的样本。需要使用 CV 函数来进行调优。 典型值：3-10

4. max_leaf_nodes

树上最大的节点或叶子的数量。 可以替代 max_depth 的作用。因为如果生成的是二叉树，一个深度为 n 的树最多生成 n2 个叶子。 如果定义了这个参数，GBM 会忽略 max_depth 参数。

5. gamma [默认 0]

在节点分裂时，只有分裂后损失函数的值下降了，才会分裂这个节点。Gamma 指定了节点分裂所需的最小损失函数下降值。 这个参数的值越大，算法越保守。这个参数的值和损失函数息息相关，所以是需要调整的。

6、max_delta_step[默认 0]

这参数限制每棵树权重改变的最大步长。如果这个参数的值为 0，那就意味着没有约束。如果它被赋予了某个正值，那么它会让这个算法更加保守。 通常，这个参数不需要设置。但是当各类别的样本十分不平衡时，它对逻辑回归是很有帮助的。 这个参数一般用不到，但是你可以挖掘出来它更多的用处。

7. subsample [默认 1]

和 GBM 中的 subsample 参数一模一样。这个参数控制对于每棵树，随机采样的比例。 减小这个参数的值，算法会更加保守，避免过拟合。但是，如果这个值设置得过小，它可能会导致欠拟合。 典型值：0.5-1

8. colsample_bytree [默认 1]

和 GBM 里面的 max_features 参数类似。用来控制每棵随机采样的列数的占比 (每一列是一个特征)。 典型值：0.5-1

9. colsample_bylevel [默认 1]

用来控制树的每一级的每一次分裂，对列数的采样的占比。 我个人一般不太用这个参数，因为 subsample 参数和 colsample_bytree 参数可以起到相同的作用。但是如果感兴趣，可以挖掘这个参数更多的用处。

10. lambda [默认 1]

权重的 L2 正则化项。(和 Ridge regression 类似)。 这个参数是用来控制 XGBoost 的正则化部分的。虽然大部分数据科学家很少用到这个参数，但是这个参数在减少过拟合上还是可以挖掘出更多用处的。

11. alpha [默认 1]

权重的 L1 正则化项。(和 Lasso regression 类似)。 可以应用在很高维度的情况下，使得算法的速度更快。

12. scale_pos_weight [默认 1]

在各类别样本十分不平衡时，把这个参数设定为一个正值，可以使算法更快收敛。

学习目标参数

这个参数用来控制理想的优化目标和每一步结果的度量方法。

1. objective [默认 reg:linear]

这个参数定义需要被最小化的损失函数。最常用的值有：

binary:logistic 二分类的逻辑回归，返回预测的概率 (不是类别)。 multi:softmax 使用 softmax 的多分类器，返回预测的类别 (不是概率)。

在这种情况下，你还需要多设一个参数：num_class(类别数目)。 multi:softprob 和 multi:softmax 参数一样，但是返回的是每个数据属于各个类别的概率。

2. eval_metric [默认值取决于 objective 参数的取值]

对于有效数据的度量方法。对于回归问题，默认值是 rmse，对于分类问题，默认值是 error。 典型值有：

rmse 均方根误差、mae 平均绝对误差、logloss 负对数似然函数值、error 二分类错误率 (阈值为 0.5)、merror 多分类错误率、mlogloss 多分类 logloss 损失函数、auc 曲线下面积

3. seed [默认 0]

随机数的种子设置它可以复现随机数据的结果，也可以用于调整参数。

参考：

https://blog.csdn.net/a1b2c3d4123456/article/details/52849091
https://www.cnblogs.com/Sugar-Chl/p/10168838.html