机器学习之boosting大家族

发表于 | 更新于 | 评论数： | 阅读次数：

本文主要节选自：http://izhaoyi.top/2017/09/23/sklearn-xgboost/

adaboost

adaboost 解决二分类问题$y\in{0,1}$，算法针对同一训练集训练出许多不同的弱分类器，将训练的分类器以某种方式组合起来，组合成一个强分类器。算法每次训练分类器时，会将前一个分类器分错的样本给与更大地权重，加强后的全体样本会用于下一次分类器的训练，每一轮加入一个新的弱分类器，知道达到某个预定的足够小的的错误率或达到预定的最大迭代次数。

参考资料

  1. https://www.cnblogs.com/en-heng/p/5974371.html

GBDT

GBDT 模型也是基于boosting的集成学习算法的变种，GB这边，就是Gradient Boost，通过在梯度上进行boost，每一次的计算是为了减少上一次的残差(residual)，在Gradient Boost中，每个新的模型的遍历是为了使得之前模型的残差往梯度方向减少。与传统Boost对错误的样本进行加权有着很大的区别。从公式上，就是下一个函数等于上一个函数+拟合了残差的函数（实际上这个残差函数会乘以一个乘数，是让目标函数最小化，这个乘数怎么来不作展开）。

XGBoost

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

一些特性

  1. GBDT无显式正则化，xgboost对每棵树的叶子节点个数和权重都做了惩罚，避免过拟合
  2. 类似于随机森林，XGBoost在构建树的过程中，加入了行采样与列采样，防止过拟合
  3. GBDT仅使用了目标函数一阶泰勒展开，而XGBoost使用了二阶的泰勒展开值
    1. 为什么二阶展开？加快收敛速度，另外有说本身模型训练的学习率shrinkage可以通过二阶导数做一个逼近，而原始的GBDT没有计算这个，所以一般是通过预设的超参数eta人为指定
  4. 分裂算法有两种，一种是精确的分裂，一种是近似分裂算法，精确分裂算法就是把每个属性的每个取值都当作一次阈值进行遍历，采用的决策树是CART。近似分裂算法是对每个属性的所有取值进行分桶，按照各个桶之间的值作为划分阈值，xgboost提出了一个特殊的分桶策略，一般的分桶策略是每个样本的权重都是相同的，但是xgboost使每个样本的权重为损失函数在该样本点的二阶导(泰勒展开不应该是损失函数关于模型的展开吗？为什么会有在该样本点的二阶导这种说法？ 因为模型是对所有样本点都通用的，把该样本输入到二阶导公式中就可以得到了)。
  5. xgboost加入了对缺失值的处理，xgboost分别将缺失样本放置到左子树和右子树，比较两者分裂增益，选择增益较大的那一边作为该样本的分裂方向。
  6. XGBoost通过预排序的方法来实现特征并行，提高模型训练效率
  7. xgboost 在实现时，需要将所有数据导入内存，做一次pre-sort（exact algorithm），这样在选择分裂节点时比较迅速。

缺点

  1. level-wise 建树方式对当前层的所有叶子节点一视同仁，有些叶子节点分裂收益非常小，对结果没影响，但还是要分裂，加重了计算代价。
  2. 预排序方法空间消耗比较大，不仅要保存特征值，也要保存特征的排序索引，同时时间消耗也大，在遍历每个分裂点时都要计算分裂增益(不过这个缺点可以被近似算法所克服)

与GBDT比较

  1. 正则化方式不同（XGB在目标函数中加入显式的控制树复杂程度的项）
  2. GBDT仅使用了目标函数一阶泰勒展开，而XGBoost使用了二阶的泰勒展开值
  3. XGB可以处理缺失值
  4. 特征重要性的判断标准
    1. sklearn GBDT是根据树的节点特征对应的深度来判断
    2. XGBoost则有三种方法(get_score)
      1. weight:特征用来作为切分特征的次数
      2. gain:使用特征进行切分的平均增益
      3. cover:各个树中该特征平均覆盖情况(根据样本？)
  5. XGB 树的切分算法：原始的贪心算法(每个特征值切分)、近似贪心(分位点切分)(使得对于大量的特征取值尤其是连续变量时XGBoost会比sklearn-gbdt快很多)、直方图算法

lightgbm

相对XGB进行了大量优化

  1. 在效率和内存上：采用直方图算法，将连续特征（属性）值存储到离散区间。这加快了培训速度并减少了内存使用量。基于直方图的算法的优点包括：
    1. 减少内存使用量(用离散箱替换连续值)
    2. 降低并行学习的通信成本
    3. 在训练决策树计算切分点的增益时，预排序需要对每个样本的切分位置计算，所以时间复杂度是O(#data)而LightGBM则是计算将样本离散化为直方图后的直方图切割位置的增益即可，时间复杂度为O(#bins),时间效率上大大提高了(初始构造直方图是需要一次O(#data)的时间复杂度，不过这里只涉及到加和操作)
    4. 直方图做差进一步提高效率，计算某一节点的叶节点的直方图可以通过将该节点的直方图与另一子节点的直方图做差得到
  2. LEAF-WISE(BEST-FIRST)树生长策略：相对于level-wise的生长策略而言，这种策略每次都是选取当前损失下降最多的叶节点进行分割使得整体模型的损失下降得更多，但是容易过拟合(特别当数据量较小的时候)，可以通过设置参数max_depth来控制树身防止出现过拟合（Notes:XGBoost现在两种方式都是支持的）
  3. LightGBM直接支持类别特征：在对离散特征分裂时，每个取值都当作一个桶，分裂时的增益算的是“是否属于某个category”的gain。类似于one-hot编码。（基于单热特征构建的树往往是不平衡的，并且需要非常深地生长以实现良好的准确性）
  4. 优化通信代价：特征并行、数据并行、投票并行
  5. 使用多项评价指标同时评价时两者的早停止策略不同，XGBoost是根据评价指标列表中的最后一项来作为停止标准，而LightGBM则受到所有评价指标的影响

参考资料

  1. http://izhaoyi.top/2017/09/23/sklearn-xgboost/
  2. https://www.cnblogs.com/mata123/p/7440774.html
  3. sklearn
  4. LGB_DOC
  5. XGB_DOC