XGBoosts和GBDT简单对比

发表于 | 分类于

参考https://www.cnblogs.com/pinard/p/11114748.html

GBDT

GBDT在每一次迭代的时候，都需要遍历整个训练数据多次。如果把整个训练数据装进内存则会限制训练数据的大小；如果不装进内存，反复地读写训练数据又会消耗非常大的时间。尤其面对工业级海量的数据，普通的GBDT算法是不能满足其需求的。

XGBoots和GBDT简单对比

XGBoost作为GBDT的高效实现，在算法竞赛中很受欢迎。对比GBDT，XGBoost主要在三个方面做了优化：

  1. 算法本身的优化

    • 在算法的弱学习器模型选择上，对比GBDT只支持决策树，还可以支持线性学习器；
    • 在算法的损失函数上，除了本身的损失，还加上了正则化的部分（$L_t=\sum_{i=1}^m L(y_i,f_{t-1}(x_i))+\gamma J+\frac{\lambda}{2}\sum_{j=1}^Jw^2_{tj}$）
    • 在算法的优化方式上，GBDT的损失函数只对误差部分做负梯度（一阶泰勒）展开，而XGBoost损失函数对误差部分做二阶泰勒展开，更加准确。

  2. 算法运行效率的优化

    对每个弱学习器，比如决策树建立的过程做并行选择，找到合适的子树分裂特征和特征值。在并行选择之前，先对所有的特征的值进行排序分组，方便进行并行选择；对分组的特征，选择合适的分组大小，使用CPU缓存进行读取加速。将各个分组保存到多个硬盘以提高IO速度。

  3. 算法健壮性的优化

    对于缺失值的特征，通过枚举所有缺失值在当前节点是否进入左子树还是右子树来决定缺失值的处理方式。算法本身加入了L1和L2正则化项，可以防止过拟合，泛化能力更强。

XGBoost的优点

  • 精度更高：GBDT只用到一阶泰勒展开，而XGBoost对损失函数进行了二阶泰勒展开。XGBoost引入二阶导，一方面是为了增加精度，另一方面是为了能够自定义损失函数，二阶泰勒展开可以近似大量损失函数。
  • 灵活性更强：GBDT以CART作为弱学习器，XGBoost不仅支持CART，还支持线性分类器。使用线性分类器的XGBoost相当于带正则化向的逻辑斯蒂回归（分类问题）和线性回归（回归问题）。此外，XGBoost还支持自定义损失函数，只需要函数支持一阶和二阶求导。
  • 正则化：XGBoost在目标函数中加入了正则项，用于控制模型的复杂度。正则项包含了树的叶子节点个数、叶子节点权重的范式。正则项降低了模型的方差，使学习出来的模型更加简单，有助于防止过拟合。
  • Shrinkage(缩减)：相当于学习速率。XGBoost在进行完一次迭代后，会将叶子节点的权重乘上该系数，主要是为了削弱每棵树的影响，让其后面有更大的学习空间。传统GBDT也有这个实现。
  • 列抽样：XGBoost借鉴了随机森林的做法，支持列抽样，不仅能降低过拟合，还能减少计算。
  • XGBoost工具支持并行：XGBoost的并行不是tree粒度的并行，而是在特征粒度上的。决策树学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为块结构，随后在迭代中重复地使用这个结构，大大减少计算量。这个块结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，则各个特征的增益计算可以开多线程进行。
  • 可并行的近似算法：树节点在进行分裂时，需要计算每个特征的每个分割点对应的增益，即用贪心法枚举所有可能的分割点。当数据无法一次载入内存或者在分布式情况下，贪心算法效率会变得很低。所以XGBoost提出了一种可并行的近似算法，用于高效地生成候选的分割点。
  • 对缺失值能自动学习出对应的处理策略。

XGBoost的缺点

XGBoost是基于预排序方法的决策树算法。这种构建决策树的算法基本思想是：首先，对所有特征都按照特征的数值进行预排序。其次，在遍历分割点的时候用O(#data)（遍历数据集）的代价找到一个特征上的最好分割点。最后，在找到一个特征的最好分割点后，将数据分裂成左右子节点。

这种预排序算法的优点是能精确地找到分割点。

缺点也很明显：

  1. 空间消耗大。这样的算法需要保存数据的特征值，还保存了特征排序的结果（预排序过程不仅需要存储特征值，还需要存储特征对应样本的梯度统计值的索引），这就需要消耗训练数据两倍的内存。
  2. 时间上也有较大的开销，在遍历每一个分割点的时候，都需要进行分裂增益的计算，消耗的代价大。
  3. 对cache优化不友好。在预排序后，特征对梯度的访问是一种随机访问，并且不同的特征访问的顺序不一样，无法对cache进行优化。同时，在每一层长树的时候，需要随机访问一个行索引到叶子索引的数组，并且不同特征访问的顺序也不一样，也会造成较大的cache miss。

LightGBM原理

参考推文：夕小瑶的卖萌屋

LightGBM的优化

  • 基于直方图的决策树算法：将连续特征值离散化为k个整数，存储在直方图中，遍历一次数据后，可根据直方图的离散值遍历寻找最优分割点。最直接的优点：1. 内存占用更小，不需要额外存储预排序的结果，而可以只保存特征离散化后的值；2. 计算代价更小，预排序算法XGBoost每遍历一个特征值就需要计算一次分裂的增益，而LightGBM只需要计算k次。（粗糙的分割点有正则化效果）
  • 带深度限制的Leaf-wise的叶子生长策略：大多数GBDT工具使用低效的按层生长 (level-wise) 的决策树生长策略，该策略遍历一次数据可以同时分裂同一层的叶子，容易进行多线程优化。因为它不加区分的对待同一层的叶子，带来了很多没必要的开销。实际上很多叶子的分裂增益较低，没必要进行搜索和分裂。LightGBM使用了带有深度限制的按叶子生长 (leaf-wise) 算法，该策略每次从当前所有叶子中，找到分裂增益最大的一个叶子，然后分裂，如此循环。（需要加上最大深度的限制，防止过拟合）
  • 单边梯度采样 Gradient-based One-Side Sampling(GOSS)：使用GOSS可以减少大量只具有小梯度的数据实例，这样在计算信息增益的时候只利用剩下的具有高梯度的数据就可以了，相比XGBoost遍历所有特征值节省了不少时间和空间上的开销。
  • 互斥特征捆绑 Exclusive Feature Bundling(EFB)：使用EFB可以将许多互斥的特征绑定为一个特征，这样达到了降维的目的。
  • 直接支持类别特征(Categorical Feature)：大多数机器学习工具都无法直接支持类别特征，一般需要把类别特征通过ont-hot编码，转化到多维的特征，降低了空间和时间的效率。
  • 支持高效并行：在每台机器上保存全部训练数据，在得到最佳划分方案后可在本地执行划分而减少了不必要的通信。比如，不需要传其他节点划分的样本的索引，只需要把最优特征以及分裂点告诉其他节点即可。
  • Cache命中率优化

XGBoost类库参数

XGBoost框架参数

  1. booster决定了XGBoost使用的弱学习器类型。可以是默认的gbtree, 也就是CART决策树，还可以是线性弱学习器gblinear以及DART。一般来说，我们使用gbtree就可以了，不需要调参。
  2. n_estimators则是非常重要的要调的参数，它关系到我们XGBoost模型的复杂度，因为它代表了我们决策树弱学习器的个数。这个参数对应sklearn GBDT的n_estimators。n_estimators太小，容易欠拟合，n_estimators太大，模型会过于复杂，一般需要调参选择一个适中的数值。
  3. objective代表了我们要解决的问题是分类还是回归，或其他问题，以及对应的损失函数。具体可以取的值很多，一般我们只关心在分类和回归的时候使用的参数。在回归问题objective一般使用reg:squarederror ，即MSE均方误差。二分类问题一般使用binary:logistic, 多分类问题一般使用multi:softmax。

XGBoost弱学习器参数

使用gbtree默认弱学习器的参数。

  1. max_depth：使用网格搜索调参。

  2. min_child_weight: 最小的子节点权重阈值. 使用网格搜索调参。

  3. gamma: XGBoost的决策树分裂所带来的损失减小阈值。也就会我们在尝试树结构分裂时，会尝试最大化下式：

    image.png

    这个最大化后的值需要大于我们的gamma，才能继续分裂子树。这个值需要使用网格搜索调参。

  4. subsample: 子采样参数，不放回抽样。选择小于1的比例可以减少方差，即防止过拟合，但是会增加样本拟合的偏差，因此取值不能太低。初期可以取值1，如果发现过拟合后可以网格搜索调参找一个相对小一些的值。

  5. colsample_bytree/colsample_bylevel/colsample_bynode: 这三个参数都是用于特征采样的，默认都是不做采样，即使用所有的特征建立决策树。colsample_bytree控制整棵树的特征采样比例，colsample_bylevel控制某一层的特征采样比例，而colsample_bynode控制某一个树节点的特征采样比例。

  6. reg_alpha/reg_lambda: XGBoost的正则化参数。

上面这些参数都是需要调参的，不过一般先调max_depth，min_child_weight和gamma。如果发现有过拟合的情况下，再尝试调后面几个参数。

XGBoost其他参数

  1. learning_rate: 控制每个弱学习器的权重缩减系数，较小的learning_rate意味着我们需要更多的弱学习器的迭代次数。所以这两个参数n_estimators和learning_rate要一起调参才有效果。
  2. n_jobs: 控制算法的并发线程数
  3. scale_pos_weight: 用于类别不平衡的时候，负例和正例的比例
  4. importance_type: 可以查询各个特征的重要性程度。可以选择“gain”, “weight”, “cover”, “total_gain” 或者 “total_cover”。最后可以通过调用booster的get_score方法获取对应的特征权重。“weight”通过特征被选中作为分裂特征的计数来计算重要性，“gain”和“total_gain”则通过分别计算特征被选中做分裂特征时带来的平均增益和总增益来计算重要性。“cover”和 “total_cover”通过计算特征被选中做分裂时的平均样本覆盖度和总体样本覆盖度来来计算重要性。

我们可以通过验证集的准确率来判断我们前面网格搜索调参是否起到了效果。实际处理的时候需要反复搜索参数并验证。