Machine Learning 决策树 boosting GBDT

Boosting 方法

从决策树到提升方法，到GBDT和xgboost

Posted by Xiya Lv on May 22, 2018

前言

​ 本文主要分析adaboost、GBDT和xgboost等提升方法。本文从决策树开始，梳理出boosting算法的原理，和各种不同boosting算法之间的差异和适用场景，并结合具体案例进行分析。

​ 本文主要内容如下：

  • 决策树

    • 原理

    • CART算法

  • Boosting
    • 原理
    • adaboost
    • GBDT
    • xgboost

决策树

原理

​ 决策树是一种基本的分类和回归方法，通过树形结构对实例进行分类（回归同理），可以认为是if-then规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。决策树本质上是从训练数据集中归纳出一组分类规则（对应if-then规则），从另一个角度，决策树学习是由训练集估计条件概率模型。

​ 决策树可能有多个，目的是选出一个最优的决策树，但是这个问题是一个NP问题，因此，决策树算法是一种启发式方法，选择的结果是次最优的。决策树算法通常是一个递归选择最优特征，并根据该特征对特征空间进行划分，对应着决策树的构建的一种算法。

​ 优点：可读性高，分类速度快。

​ 决策树主要分三个步骤：特征选择，决策树生成和决策树剪枝。

​ 决策树算法主要有ID3和C4.5，用以分类问题；CART既能分类，又能做回归问题。

​ 接下来从决策树的三个步骤分别进行阐述：

特征选择

​ 特征选择的标准是信息增益或信息增益比。

  • 名词解释

    • 熵（entropy）$H(X)$

      熵是随机变量不稳定的度量。（我们想要的是熵小）

      设$X$是一个取有限个离散的随机变量，概率分布为

      则熵定义为：

      若$p_i=0$，则认为$0log0=0$，若log以2为底，熵的单位是比特（bit），若log以e为底，熵的单位是纳特（nat）。

      当熵由数据计算出来的时候，称为经验熵。

    • 条件熵（conditional entropy）

      表示已知随机变量X的条件下随机变量Y的不确定性。

      其中,

      当条件熵有数据计算出来的时候，称为经验条件熵。

    • 信息增益

      信息增益就是经验熵和经验条件熵之差，也叫互信息（mutual information）

      ​

      可以认为这里的D是label，A为特征的一个。

    • 信息增益比

      ​ ,

      其中, n是特征A取值的个数。

  • 信息增益算法

    1. 计算经验熵H(D)
    2. 计算经验条件熵$H(D \mid A)$
    3. 计算信息增益 $g(D \mid A) = H(D) - H(D \mid A)$
决策树生成
  • 主要有两个算法：ID3和C4.5
  • 两者的区别在于ID3采用信息增益来选择特征；C4.5采用信息增益比来选择特征；
决策树的剪枝

​ 决策树的剪枝往往通过极小化决策树整体的损失函数（loss function）来实现。损失函数定义为：

​

其中，$H_t(T)$为叶节点t上的经验熵，$a \geq 0$为参数。经验熵, 因此上式的第一项就变成了$C(T) = - \sum \limits_{t=1}^{|T|}\sum\limits_{k=1}^KN_{tk}log\frac{N_{tk}}{N_t}$, 此时上式就变成了 $C_a{T}=C(T)+a|T|$, 第一项表示模型对训练数据的预测误差，$|T|$表示模型复杂度，参数$a$控制两者的关系。较大的$a$促使选择较简单的模型树，较小的$a$促使选择较复杂的模型树。

CART算法

原理

​ CART算法即可用于分类，也可用于回归。是在给定输入随机变量X条件下输出随机变量Y的条件概率分布的学习方法。CART中的决策树是二叉树。

​ CART算法由两步组成：决策树生成，且生成的决策树要尽量大；决策树剪枝，以损失函数最小为剪枝的标准。

CART生成

生成CART针对分类问题和回归问题所采用的准则不同，分类问题用基尼指数（Gini index），回归问题用平方误差最小化准则。

WechatIMG33005

CART的算法：

输入：CART算法生成的决策树$T_0$

输出：最优决策树$T_a$

  1. 设k=0，T=$T_0$, $a=+fin$
  2. 自下而上对各内部结点t计算$C(T_t)$, $|T_t|$以及 $g(t)=\frac{C(t)-C(T_t)}{|T_t|-1}$ $a=min(a, g(t))$ 这里，$T_t$表示以t为根节点的子树，$C(T_t)$是对训练数据的预测误差，$|T_t|$是$T_t$的叶节点的个数。C(t)表示t为单个结点时的对训练数据的预测误差。
  3. 对$g(t)=a$的内部结点t进行剪枝，并对叶节点t以多数表决法决定其类，得到树T。
  4. 设$k=k+1, a_k=a, T_k=T$
  5. 如果$T_k$不是由根节点及两个叶节点构成的树，则回到步骤3；否则令$T_k=T_n$
  6. 采用交叉验证法在子树序列$T_0,T_1,…T_n$中选取最有子树$T_a$.

提升方法

原理

提升方法通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能。

adaboost

可参见博客

他是一个加法模型，损失函数是指数函数，学习算法是前向分布算法的二类分类学习方法。

  • Adaboost优点
    • 不容易发生过拟合。
    • Adaboost是一种有很高精度的分类器。
    • 当使用简单分类器时，计算出的结果是可理解的。
    • 可以使用各种方法构建子分类器，Adaboost算法提供的是框架。
  • Adaboost缺点
    • 训练时间过长。
    • 执行效果依赖于弱分类器的选择。
    • 对样本敏感，异常样本在迭代中可能会获得较高的权重，影响最终的强学习器的预测准确性。

提升树

采用加法模型与前向分步算法，以决策树为基函数的提升方法。在分类问题上，只需将基函数变成决策树，其他和adaboost基本一致。在回归问题上，通过计算第一步计算残差的方式，后续的每一步均是对上一步计算的残差进行学习一个回归树。

该方法通过计算残差的方式，而并非通过损失函数拟合。因此后续出来了GBDT提出用损失函数的负梯度来拟合本轮损失的近似值，进而拟合一个CART回归树。

可分类，可回归

GBDT

可参见博客

多元分类和回归

  • 优点
    • 相对少的调参时间情况下可以得到较高的准确率。
    • 可灵活处理各种类型数据，包括连续值和离散值，使用范围广。
    • 可使用一些健壮的损失函数，对异常值的鲁棒性较强，比如Huber损失函数。
  • 缺点
    • 弱学习器之间存在依赖关系，难以并行训练数据。

XGboost

主要是Xgboost和GBDT的差异：

  1. 传统的GBDT以CART树作为基学习器，XGBoost还支持线性分类器，这个时候XGBoost相当于L1和L2正则化的逻辑斯蒂回归（分类）或者线性回归（回归）；

  2. 传统的GBDT在优化的时候只用到一阶导数信息，XGBoost则对代价函数进行了二阶泰勒展开，得到一阶和二阶导数；

  3. xgboost可自定义目标函数，但是目标函数必须二阶可导。

  4. XGBoost在代价函数中加入了正则项，用于控制模型的复杂度。从权衡方差偏差来看，它降低了模型的方差，使学习出来的模型更加简单，防止过拟合，这也是XGBoost优于传统GBDT的一个特性；

  5. shrinkage（缩减），相当于学习速率（XGBoost中的eta）。XGBoost在进行完一次迭代时，会将叶子节点的权值乘上该系数，主要是为了削弱每棵树的影响，让后面有更大的学习空间。（GBDT也有学习速率）；

  6. 列抽样。XGBoost借鉴了随机森林的做法，支持列抽样，不仅防止过拟合，还能减少计算；

  7. 对缺失值的处理。对于特征的值有缺失的样本，XGBoost还可以自动 学习出它的分裂方向；

  8. XGBoost工具支持并行，在特征粒度的并行。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），XGBoost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代 中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

  9. xgboost在算法实现时做了很多优化，大大提升了算法的效率！

  • 对训练的每个特征排序并且以块的的结构存储在内存中，方便后面迭代重复使用，减少计算量，不仅如此，在不同的特征属性上采用多线程并行方式寻找最佳分割点

  • 上述的优化导致每个样本的梯度信息在内存中不连续，直接累加有可能会导致cache-miss，所以xgboost先将样本的统计信息取到线程的内部buffer，然后再进行小批量的累加
  • xgboost在实现时考虑了当训练数据很大、内存空间不够时，如何有效的利用磁盘空间？主要是利用了分块、预取、压缩、多线程协作的思想。

参考文献：

  1. https://blog.csdn.net/qq_28031525/article/details/70207918
  2. 李航统计机器学习
  3. https://weizhixiaoyi.com/
  4. 知乎：https://www.zhihu.com/question/41354392
CATALOG
    FEATURED TAGS
    Machine Learning Deep Learning Object Detection 决策树 boosting GBDT APUE iNode 链接