集成学习——XGBoost_cyclic 对比 greedy

看了好几次XGBoost的文章，感觉总是过目就忘，以下对学习过的链接进行总结。平平无奇的搬运工。

参考:
July
小雨姑娘
萌弟
雪伦_
Y学习使我快乐V

XGBoost是高效地实现了GBDT算法并进行了算法和工程上的许多改进。XGBoost本质上还是一个GBDT，但是力争把速度和效率发挥到极致，所以叫X (Extreme) GBoosted，所以XGBoost也是boosting方法。XGBoost是一个优化的分布式梯度增强库，旨在实现高效，灵活和便携。 XGBoost提供了并行树提升（也称为GBDT，GBM），可以快速准确地解决许多数据科学问题。相同的代码在主要的分布式环境（Hadoop，SGE，MPI）上运行。Xgboost以CART决策树为子模型，通过Gradient Tree Boosting实现多棵CART树的集成学习，得到最终模型。
那么CART树是什么？
答：分类回归树（CART，Classification And Regression Tree）是用于分类树与回归树的总称，由Breiman等人首先提出。

那么分类树和回归树又是什么？
答：

• 分类树是指预测结果是样本所属的类别，比如今天打不打球？打还是不打
• 回归树是指预测结果是数值，比如预测房价的金额是多少？10000元一平米，或者120000元一平米等等。那么这个数值是怎么确定的呢？
  答：有的是节点内样本均值，有的是最优化算出来的比如Xgboost。

分类树就有很多的指标来判断分支点的效果好不好，如信息增益、信息增益率、基尼系数。那么回归树呢用什么判断呢？
答：预测误差用：均方误差、对数误差

XGBoost理论

类似gbdt的原理，多棵树的结论累加起来便是最终的结论。到这不就和GBDT一样了吗。但XGBoost的目标函数是

• 红色箭头指向的L是损失函数，可以是平方损失函数或logistic损失函数。
• 红色方框是正则项：L1正则、L2正则。
• 红色圆圈是常数项。
• 利用泰勒张开3项，做近似。

XGBoost核心思想：不断地添加树，不断地进行特征分裂来生长一棵树，每次添加一个树，其实是学习一个新函数，去拟合上次预测的残差。最后根据样本的特征落在每棵树的叶子结点对应的分数相加，就是样本的预测值。

其中，$w_{q(x)}$是叶子结点的分数，$F$是所有K棵回归树的结合，$f(x)$是某一棵回归树。

目标：树的预测值$\widehat{y_i}$尽可能接近真实值$y_i$，且泛化好。数学角度看这是泛函最优化问题 ，所以可简化为：

什么是泛函最优化问题？

后面的讲解，我是看July的这篇，看了之后有点模模糊糊（个人原因）。
补充阅读：小雨姑娘：hi可以看做计算残差时某个样本的重要性。
在模模糊糊的基础上看了萌弟的这篇公式推导，就更清楚了一点。

XGBoost关键在于：

• 对loss函数进行泰勒二阶展开
• 加入正则项限制复杂度（树中的叶子结点个数，叶子结点的得分w的L2模平方）

分裂算法

1. 精确贪心分裂算法：
   XGBoost在生成新树的过程中，最基本的操作是节点分裂。节点分裂中最重 要的环节是找到最优特征及最优切分点, 然后将叶子节点按照最优特征和最优切 分点进行分裂。选取最优特征和最优切分点的一种思路如下：首先找到所有的候 选特征及所有的候选切分点, 一一求得其 ${\mathcal{L}}_{\text{split }}$, 然后选择${\mathcal{L}}_{\mathrm{s}\mathrm{p}\mathrm{l}\mathrm{i}\mathrm{t}}$ 最大的特征及 对应切分点作为最优特征和最优切分点。我们称此种方法为精确贪心算法。该算法是一种启发式算法, 因为在节点分裂时只选择当前最优的分裂策略, 而非全局最优的分裂策略。精确贪心算法的计算过程如下所示：

2. 基于直方图的近似算法：
   精确贪心算法在选择最优特征和最优切分点时是一种十分有效的方法。它计算了所有特征、所有切分点的收益, 并从中选择了最优的, 从而保证模型能比较好地拟合了训练数据。但是当数据不能完全加载到内存时，精确贪心算法会变得 非常低效，算法在计算过程中需要不断在内存与磁盘之间进行数据交换，这是个非常耗时的过程, 并且在分布式环境中面临同样的问题。为了能够更高效地选 择最优特征及切分点, XGBoost提出一种近似算法来解决该问题。 基于直方图的近似算法的主要思想是：对某一特征寻找最优切分点时，首先对该特征的所有切分点按分位数 (如百分位) 分桶, 得到一个候选切分点集。特征的每一个切分点都可以分到对应的分桶; 然后，对每个桶计算特征统计G和H得到直方图, G为该桶内所有样本一阶特征统计g之和, H为该桶内所有样本二阶特征统计h之和; 最后，选择所有候选特征及候选切分点中对应桶的特征统计收益最大的作为最优特征及最优切分点。基于直方图的近似算法的计算过程如下所示：

   1. 对于每个特征 $k=1,2,\cdots ,m,$ 按分位数对特征 $k$ 分桶 $\Theta ,$ 可得候选切分点, S k = { S k 1 , S k 2 , ⋯   , S k l } 1 S_{k}=\left\{S_{k 1}, S_{k 2}, \cdots, S_{k l}\right\}^{1} Sk​={Sk1​,Sk2​,⋯,Skl​}1
   2. 对于每个特征 $k=1,2,\cdots ,m,$ 有：
      G k v ← = ∑ j ∈ { j ∣ s k , v ≥ x j k > s k , v − 1    } g j H k v ← = ∑ j ∈ { j ∣ s k , v ≥ x j k > s k , v − 1    } h j $$\begin{array}{l} G_{k v} \leftarrow=\sum_{j \in\left\{j \mid s_{k, v} \geq \mathbf{x}_{j k}>s_{k, v-1\;}\right\}} g_{j} \\ H_{k v} \leftarrow=\sum_{j \in\left\{j \mid s_{k, v} \geq \mathbf{x}_{j k}>s_{k, v-1\;}\right\}} h_{j} \end{array}$$ Gkv​←=∑j∈{j∣sk,v​≥xjk​>sk,v−1​}​gj​Hkv​←=∑j∈{j∣sk,v​≥xjk​>sk,v−1​}​hj​​

3. 类似精确贪心算法，依据梯度统计找到最大增益的候选切分点。
   下面用一个例子说明基于直方图的近似算法：
   假设有一个年龄特征，其特征的取值为18、19、21、31、36、37、55、57，我们需要使用近似算法找到年龄这个特征的最佳分裂点：

近似算法实现了两种候选切分点的构建策略：全局策略和本地策略。全局策略是在树构建的初始阶段对每一个特征确定一个候选切分点的集合, 并在该树每一层的节点分裂中均采用此集合计算收益, 整个过程候选切分点集合不改变。本地策略则是在每一次节点分裂时均重新确定候选切分点。全局策略需要更细的分桶才能达到本地策略的精确度, 但全局策略在选取候选切分点集合时比本地策略更简单。
在XGBoost系统中, 用户可以根据需求自由选择使用精确贪心算法、近似算法全局策略、近似算法本地策略, 算法均可通过参数进行配置。

参数说明

XGBoost的参数设置(括号内的名称为sklearn接口对应的参数名字):
推荐博客：https://link.zhihu.com/?target=https%3A//blog.csdn.net/luanpeng825485697/article/details/79907149
推荐官方文档：https://link.zhihu.com/?target=https%3A//xgboost.readthedocs.io/en/latest/parameter.html

XGBoost的参数分为三种：

• 通用参数：（两种类型的booster，因为tree的性能比线性回归好得多，因此我们很少用线性回归。）

  • booster:使用哪个弱学习器训练，默认gbtree，可选gbtree，gblinear 或dart
  • nthread：用于运行XGBoost的并行线程数，默认为最大可用线程数
  • verbosity：打印消息的详细程度。有效值为0（静默），1（警告），2（信息），3（调试）。
  • Tree Booster的参数：
    • eta（learning_rate）：learning_rate，在更新中使用步长收缩以防止过度拟合，默认= 0.3，范围：[0,1]；典型值一般设置为：0.01-0.2
    • gamma（min_split_loss）：默认= 0，分裂节点时，损失函数减小值只有大于等于gamma节点才分裂，gamma值越大，算法越保守，越不容易过拟合，但性能就不一定能保证，需要平衡。范围：[0，∞]
    • max_depth：默认= 6，一棵树的最大深度。增加此值将使模型更复杂，并且更可能过度拟合。范围：[0，∞]
    • min_child_weight：默认值= 1，如果新分裂的节点的样本权重和小于min_child_weight则停止分裂 。这个可以用来减少过拟合，但是也不能太高，会导致欠拟合。范围：[0，∞]
    • max_delta_step：默认= 0，允许每个叶子输出的最大增量步长。如果将该值设置为0，则表示没有约束。如果将其设置为正值，则可以帮助使更新步骤更加保守。通常不需要此参数，但是当类极度不平衡时，它可能有助于逻辑回归。将其设置为1-10的值可能有助于控制更新。范围：[0，∞]
    • subsample：默认值= 1，构建每棵树对样本的采样率，如果设置成0.5，XGBoost会随机选择一半的样本作为训练集。范围：（0,1]
    • sampling_method：默认= uniform，用于对训练实例进行采样的方法。
      • uniform：每个训练实例的选择概率均等。通常将subsample> = 0.5 设置 为良好的效果。
      • gradient_based：每个训练实例的选择概率与规则化的梯度绝对值成正比，具体来说就是$\sqrt{g^2+\lambda h^2}$，subsample可以设置为低至0.1，而不会损失模型精度。
    • colsample_bytree：默认= 1，列采样率，也就是特征采样率。范围为（0，1]
    • lambda（reg_lambda）：默认=1，L2正则化权重项。增加此值将使模型更加保守。
    • alpha（reg_alpha）：默认= 0，权重的L1正则化项。增加此值将使模型更加保守。
    • tree_method：默认=auto，XGBoost中使用的树构建算法。
      • auto：使用启发式选择最快的方法。
        • 对于小型数据集，exact将使用精确贪婪（）。
        • 对于较大的数据集，approx将选择近似算法（）。它建议尝试hist，gpu_hist，用大量的数据可能更高的性能。（gpu_hist）支持。external memory外部存储器。
      • exact：精确的贪婪算法。枚举所有拆分的候选点。
      • approx：使用分位数和梯度直方图的近似贪婪算法。
      • hist：更快的直方图优化的近似贪婪算法。（LightGBM也是使用直方图算法）
      • gpu_hist：GPU hist算法的实现。
    • scale_pos_weight:控制正负权重的平衡，这对于不平衡的类别很有用。Kaggle竞赛一般设置sum(negative instances) / sum(positive instances)，在类别高度不平衡的情况下，将参数设置大于0，可以加快收敛。
    • num_parallel_tree：默认=1，每次迭代期间构造的并行树的数量。此选项用于支持增强型随机森林。
    • monotone_constraints：可变单调性的约束，在某些情况下，如果有非常强烈的先验信念认为真实的关系具有一定的质量，则可以使用约束条件来提高模型的预测性能。（例如params_constrained[‘monotone_constraints’] = “(1,-1)”，(1,-1)我们告诉XGBoost对第一个预测变量施加增加的约束，对第二个预测变量施加减小的约束。）
  • Linear Booster的参数：
    • lambda（reg_lambda）：默认= 0，L2正则化权重项。增加此值将使模型更加保守。归一化为训练示例数。
    • alpha（reg_alpha）：默认= 0，权重的L1正则化项。增加此值将使模型更加保守。归一化为训练示例数。
    • updater：默认= shotgun。
      • shotgun：基于shotgun算法的平行坐标下降算法。使用“ hogwild”并行性，因此每次运行都产生不确定的解决方案。
      • coord_descent：普通坐标下降算法。同样是多线程的，但仍会产生确定性的解决方案。
    • feature_selector：默认= cyclic。特征选择和排序方法
      • cyclic：通过每次循环一个特征来实现的。
      • shuffle：类似于cyclic，但是在每次更新之前都有随机的特征变换。
      • random：一个随机(有放回)特征选择器。
      • greedy：选择梯度最大的特征。（贪婪选择）
      • thrifty：近似贪婪特征选择（近似于greedy）
    • top_k：要选择的最重要特征数（在greedy和thrifty内）

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

  • objective：默认=reg:squarederror，表示最小平方误差。
    • reg:squarederror,最小平方误差。
    • reg:squaredlogerror,对数平方损失。$\frac{1}{2}[log(pred+1)-log(label+1){]}^2$
    • reg:logistic,逻辑回归
    • reg:pseudohubererror,使用伪Huber损失进行回归，这是绝对损失的两倍可微选择。
    • binary:logistic,二元分类的逻辑回归，输出概率。
    • binary:logitraw：用于二进制分类的逻辑回归，逻辑转换之前的输出得分。
    • binary:hinge：二进制分类的铰链损失。这使预测为0或1，而不是产生概率。（SVM就是铰链损失函数）
    • count:poisson –计数数据的泊松回归，泊松分布的输出平均值。
    • survival:cox：针对正确的生存时间数据进行Cox回归（负值被视为正确的生存时间）。
    • survival:aft：用于检查生存时间数据的加速故障时间模型。
    • aft_loss_distribution：survival:aft和aft-nloglik度量标准使用的概率密度函数。
    • multi:softmax：设置XGBoost以使用softmax目标进行多类分类，还需要设置num_class（类数）
    • multi:softprob：与softmax相同，但输出向量，可以进一步重整为矩阵。结果包含属于每个类别的每个数据点的预测概率。
    • rank:pairwise：使用LambdaMART进行成对排名，从而使成对损失最小化。
    • rank:ndcg：使用LambdaMART进行列表式排名，使标准化折让累积收益（NDCG）最大化。
    • rank:map：使用LambdaMART进行列表平均排名，使平均平均精度（MAP）最大化。
    • reg:gamma：使用对数链接进行伽马回归。输出是伽马分布的平均值。
    • reg:tweedie：使用对数链接进行Tweedie回归。
    • 自定义损失函数和评价指标：https://xgboost.readthedocs.io/en/latest/tutorials/custom_metric_obj.html
  • eval_metric：验证数据的评估指标，将根据目标分配默认指标（回归均方根，分类误差，排名的平均平均精度），用户可以添加多个评估指标
    • rmse，均方根误差； rmsle：均方根对数误差； mae：平均绝对误差；mphe：平均伪Huber错误；logloss：负对数似然； error：二进制分类错误率；
    • merror：多类分类错误率； mlogloss：多类logloss； auc：曲线下面积； aucpr：PR曲线下的面积；ndcg：归一化累计折扣；map：平均精度；
  • seed ：随机数种子，[默认= 0]。

• 命令行参数（这里不说了，因为很少用命令行控制台版本）

实例

萌弟的这篇有使用方法和调参教学

还是得自己看论文和源码，现在我还是有点过目就忘。

LightGBM总结