【机器学习】gbdt/xgboost/lightGBM比较

发表于 | 浏览 次
字数统计: 3,579 | 阅读时长 ≈ 12

1. 概述

RF、GBDT和XGBoost都属于集成学习（Ensemble Learning），集成学习的目的是通过结合多个基学习器的预测结果来改善单个学习器的泛化能力和鲁棒性。
　　根据个体学习器的生成方式，目前的集成学习方法大致分为两大类：即个体学习器之间存在强依赖关系、必须串行生成的序列化方法，以及个体学习器间不存在强依赖关系、可同时生成的并行化方法；前者的代表就是Boosting，后者的代表是Bagging和“随机森林”（Random Forest）。

2. 随机森林RF

提到随机森林，就不得不提Bagging，Bagging可以简单的理解为：放回抽样，多数表决（分类）或简单平均（回归）,同时Bagging的基学习器之间属于并列生成，不存在强依赖关系。
　　Random Forest（随机森林）是Bagging的扩展变体，它在以决策树 为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入了随机特征选择，因此可以概括RF包括四个部分：

  1. 随机选择样本（放回抽样）
  2. 随机选择特征
  3. 构建决策树
  4. 随机森林投票（平均）。

随机选择样本和Bagging相同，随机选择特征是指在树的构建中，会从样本集的特征集合中随机选择部分特征，然后再从这个子集中选择最优的属性用于划分，这种随机性导致随机森林的偏差会有稍微的增加（相比于单棵不随机树），但是由于随机森林的‘平均’特性，会使得它的方差减小，而且方差的减小补偿了偏差的增大，因此总体而言是更好的模型。

​ 在构建决策树的时候，RF的每棵决策树都最大可能的进行生长而不进行剪枝；在对预测输出进行结合时，RF通常对分类问题使用简单投票法，回归任务使用简单平均法。
　　RF的重要特性是不用对其进行交叉验证或者使用一个独立的测试集获得无偏估计，它可以在内部进行评估，也就是说在生成的过程中可以对误差进行无偏估计，由于每个基学习器只使用了训练集中约63.2%的样本，剩下约36.8%的样本可用做验证集来对其泛化性能进行“包外估计”。
　　RF和Bagging对比：RF的起始性能较差，特别当只有一个基学习器时，随着学习器数目增多，随机森林通常会收敛到更低的泛化误差。随机森林的训练效率也会高于Bagging，因为在单个决策树的构建中，Bagging使用的是‘确定性’决策树，在选择特征划分结点时，要对所有的特征进行考虑，而随机森林使用的是‘随机性’特征数，只需考虑特征的子集。

优缺点：

　　随机森林的优点较多，简单总结：

  1. 在数据集上表现良好，训练速度快、预测准确度较高；
  2. 能够处理很高维的数据，并且不用特征选择，而且在训练完后，给出特征的重要性；
  3. 容易做成并行化方法。

　　RF的缺点：在噪声较大的分类或者回归问题上回过拟合。

3. GBDT

​ 提GBDT之前，谈一下Boosting，Boosting是一种与Bagging很类似的技术。不论是Boosting还是Bagging，所使用的多个分类器类型都是一致的。但是在前者当中，不同的分类器是通过串行训练而获得的，每个新分类器都根据已训练的分类器的性能来进行训练。Boosting是通过关注被已有分类器错分的那些数据来获得新的分类器。
　　由于Boosting分类的结果是基于所有分类器的加权求和结果的，因此Boosting与Bagging不太一样，Bagging中的分类器权值是一样的，而Boosting中的分类器权重并不相等，每个权重代表对应的分类器在上一轮迭代中的成功度。

3.1 原理

​ 原始的Boost算法是在算法开始的时候，为每一个样本赋上一个权重值，初始的时候，大家都是一样重要的。在每一步训练中得到的模型，会使得数据点的估计有对有错，我们就在每一步结束后，增加分错的点的权重，减少分对的点的权重，这样使得某些点如果老是被分错，那么就会被“严重关注”，也就被赋上一个很高的权重。然后等进行了N次迭代（由用户指定），将会得到N个简单的分类器（basic learner），然后我们将它们组合起来（比如说可以对它们进行加权、或者让它们进行投票等），得到一个最终的模型。

​ GBDT与传统的Boosting区别较大，它的每一次计算都是为了减少上一次的残差，而为了消除残差，我们可以在残差减小的梯度方向上建立模型,所以说，在GradientBoost中，每个新的模型的建立是为了使得之前的模型的残差往梯度下降的方法，与传统的Boosting中关注正确错误的样本加权有着很大的区别。
　　在GradientBoosting算法中，关键就是利用损失函数的负梯度方向在当前模型的值作为残差的近似值，进而拟合一棵CART回归树。

​ GBDT的会累加所有树的结果，而这种累加是无法通过分类完成的，因此GBDT的树都是CART回归树，而不是分类树（尽管GBDT调整后也可以用于分类但不代表GBDT的树为分类树）。

一些特性

  1. 每次迭代获得的决策树模型都要乘以一个缩减系数，从而降低每棵树的作用，提升可学习空间。
  2. 每次迭代拟合的是一阶梯度。

3.2 优缺点

GBDT的性能在RF的基础上又有一步提升，因此其优点也很明显，

  1. 它能灵活的处理各种类型的数据；
  2. 在相对较少的调参时间下，预测的准确度较高。

缺点：当然由于它是Boosting，因此基学习器之前存在串行关系，难以并行训练数据。

4. XGBoost

4.1 原理

​ XGBoost 是GBDT的一个变种，最大的区别是xgboost通过对目标函数做二阶泰勒展开，从而求出下一步要拟合的树的叶子节点权重（需要先确定树的结构），从而根据损失函数求出每一次分裂节点的损失减小的大小，从而根据分裂损失选择合适的属性进行分裂。

​ 这个利用二阶展开的到的损失函数公式与分裂节点的过程是息息相关的。先遍历所有节点的所有属性进行分裂，假设选择了这个a属性的一个取值作为分裂节点，根据泰勒展开求得的公式可计算该树结构各个叶子节点的权重，从而计算损失减小的程度，从而综合各个属性选择使得损失减小最大的那个特征作为当前节点的分裂属性。依次类推，直到满足终止条件。

4.2 XGBoost与GBDT区别

  1. 传统GBDT以CART作为基分类器，xgboost还支持线性分类器，这个时候xgboost相当于带L1和L2正则化项的逻辑斯蒂回归（分类问题）或者线性回归（回归问题）。
  2. 传统GBDT在优化时只用到一阶导数信息，xgboost则对代价函数进行了二阶泰勒展开，同时用到了一阶和二阶导数。顺便提一下，xgboost工具支持自定义代价函数，只要函数可一阶和二阶求导。
  3. xgboost在代价函数里加入了正则项，用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出的score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。
  4. Shrinkage（缩减），相当于学习速率（xgboost中的eta）。xgboost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。实际应用中，一般把eta设置得小一点，然后迭代次数设置得大一点。（传统GBDT的实现也有学习速率）
  5. 列抽样（column subsampling）。xgboost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算，这也是xgboost异于传统gbdt的一个特性。
  6. 对缺失值的处理。对于特征的值有缺失的样本，xgboost可以自动学习出它的分裂方向。对于在训练过程中遇到的缺失值，xgboost将其分别归到左子树和右子树分别计算损失，选取较优的哪一个。如果在训练中没有缺失值，在预测时遇到缺失值，就默认分到右子树。
  7. xgboost工具支持并行。注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。
  8. 可并行的近似直方图算法。树节点在进行分裂时，我们需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率就会变得很低，所以xgboost还提出了一种可并行的近似直方图算法，用于高效地生成候选的分割点。

4.3 xgboost正则化（预剪枝）

xgboost的目标函数如下：img

xgboost中树节点分裂时所采用的公式：img

这个公式形式上跟ID3算法、CART算法是一致的，都是用分裂后的某种值减去分裂前的某种值，从而得到增益。为了限制树的生长，我们可以加入阈值，当增益大于阈值时才让节点分裂，上式中的gamma即阈值，它是正则项里叶子节点数T的系数，所以xgboost在优化目标函数的同时相当于做了预剪枝。另外，上式中还有一个系数lambda，是正则项里leaf score的L2模平方的系数，对leaf score做了平滑，也起到了防止过拟合的作用，这个是传统GBDT里不具备的特性。

5. lightGBM与XGBoost区别

5.1 决策树算法

由于在决策树在每一次选择节点特征的过程中，要遍历所有的属性的所有取值并选择一个较好的。

XGBoost使用的是pre-sorted算法（对所有特征都按照特征的数值进行预排序，在遍历分割点的时候用O(data)的代价找到一个特征上的最好分割点），能够更精确的找到数据分隔点；（xgboost的分布式实现也是基于直方图的，利于并行）

LightGBM使用的是histogram算法（X发给类似一种分桶算法），占用的内存更低，数据分隔的复杂度更低。

直方图优化参考：开源 | LightGBM：三天内收获GitHub 1000 星

而这两个算法的比较见参考文献如何看待微软新开源的LightGBM?

5.2 决策树生长策略

XGBoost采用的是level-wise生长策略，如Figure 1所示，能够同时分裂同一层的叶子，从而进行多线程优化，也好控制模型复杂度，不容易过拟合；但实际上Level-wise是一种低效的算法，它不加区分的对待同一层的叶子，带来了很多没必要的开销，因为实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。

img

LightGBM采用leaf-wise生长策略，如Figure 2所示，每次从当前所有叶子中找到分裂增益最大（一般也是数据量最大）的一个叶子，然后分裂，如此循环；但会生长出比较深的决策树，产生过拟合。因此 LightGBM 在leaf-wise之上增加了一个最大深度的限制，在保证高效率的同时防止过拟合。

img

5.3 其他

  1. 直方图做差加速

    一个子节点的直方图可以通过父节点的直方图减去兄弟节点的直方图得到，从而加速计算。

    1. lightgbm支持直接输入categorical 的feature

      在对离散特征分裂时，每个取值都当作一个桶，分裂时的增益算的是”是否属于某个category“的gain。类似于one-hot编码。

    2. 多线程优化

6. 参考资料

  1. XGBoost, LightGBM性能大对比
  2. LightGBM微软官方中文介绍
  3. 关于树的几个ensemble模型的比较（GBDT、xgBoost、lightGBM、RF）