Fork me on GitHub

Boosting_And_Bagging

在文章机器学习-决策树中详细阐述了目前常用的决策树TD3,C4.5,CART,但是在实际应用中,一般很少使用单个树进行模型设计,因为单个数很难实现一个更全面的模型,由此引入了集成学习,俗话说,三个臭皮匠赛过诸葛亮,集成学习可以看成将多个弱学习器的组合,以期望达到比单个弱学习器更好的监督模型,集成学习的思想是即使某一个弱分类器得到了错误的预测那么其他的弱分类器也可以将错误纠正。

根据个体学习器的生成方式,目前的主要集成学习方法可以分为两大类

  • 个体学习器之间存在强依赖关系,必须串行生成的序列化方法
  • 个体学习器之间不存在强依赖关系,可以同时生成的并行化方法

对于前者代表的是Boosting,后者的代表是Bagging

Boosting

和Bagging不同的是,Boosting主要针对模型的偏差进行优化,也就是提高模型的预测准确率,主要针对欠拟合进行优化,并且使用的是串行的训练方式,也就是要先训练一个学习器,基于上一个学习器的结果来训练第二个学习器,以此类推,对于Boosting来说,代表性的算法为AdaBoostGBDT

AdaBoost分类

根据弱学习的学习误差率表现来更新训练样本的权重,使得之前弱学习器1学习误差率高的训练样本点的权重变高,使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2.,如此重复进行,直到弱学习器数达到事先指定的数目T,最终将这T个弱学习器通过集合策略进行整合,得到最终的强学习器。

对于AdaBoost分类算法的过程如下所示

对于Adaboost多元分类算法,其实原理和二元分类类似,最主要区别在弱分类器的系数上。比如Adaboost SAMME算法,它的弱分类器的系数:

其中$R$为类别的数量,如果是二分类,则R=2和上述的二分类算法的弱分类器的系数是一致的。

AdaBoost回归

AdaBoost优缺点

优点

  1. Adaboost作为分类器时,分类精度很高
  2. 在Adaboost的框架下,可以使用各种回归分类模型来构建弱学习器,非常灵活。
  3. 作为简单的二元分类器时,构造简单,结果可理解。
  4. 不容易发生过拟合

缺点

对异常样本敏感,异常样本在迭代中可能会获得较高的权重,影响最终的强学习器的预测准确性。

GBDT-梯度提升决策树

与AdaBoost不同,GBDT不再是为了更新样本权重,而是使用缩小残差的方法。

GBM-梯度提升算法

在监督学习中模型的优化目标是最小化损失函数的期望$E[L(y,f(x))]$,因此优化过程可以看成$f^*=\ argmin _{f}E[L(y,f(x))]$,目前常用的是基于梯度下降的方法。在GBDT中采用的是分层学习的方法,经过m个步骤得到最终的模型$f$,其中第$m$步学习一个较弱的模型$f_m$,在第$m+1$步时,不直接优化$f_m$,而是学习一个基本模型$h(x)$,使得其拟合残差项$y-f_m$,这样就是的$m+1$步的预测值$f_{m+1}=f_m+h(x)$更接近于真实值$y$,有点残差网络类似,经过这样的设计优化目标就是找到最小的残差$h(x)=f_{m+1}-f_m$,最终得到了函数空间中的一组$h(x)$使得$f(x)=\sum_{i=1}^{M} \gamma _{i} h_{i}(x)+const$,优化目标就是找到最优的$f(x)$使得误差最小,梯度提升的算法如下

对于GBM,理论上可以选择不同的学习算法作为基学习器,实际应用中,多数使用的是决策树作为基学习器,也就是GBDT。

GBDT

之所以选择决策树作为基学习器(通常为CART)这决策树算法本身的特性有很大的关系,决策树可以看做是一种if-then的规则集合,易于理解,可解释性强,预测速度快,对数据敏感,特征工程少,但是对于单颗树来说,容易产生过拟合的风险,这就要进行剪枝,这也是为什么引入了集成学习。GBDT机制单颗决策树的复杂度,降低单颗树的拟合能力,在通过梯度提升的方法集成多个决策树,最终实现解决过拟合的问题。抑制单颗决策树的复杂度的方法为

抑制单颗决策树的复杂度的方法有很多,比如限制树的最大深度、限制叶子节点的最少样本数量、限制节点分裂时的最少样本数量、吸收bagging的思想对训练样本采样(subsample),在学习单颗决策树时只使用一部分训练样本、借鉴随机森林的思路在学习单颗决策树时只采样一部分特征、在目标函数中添加正则项惩罚复杂的树结构等。现在主流的GBDT算法实现中这些方法基本上都有实现,因此GBDT算法的超参数还是比较多的,应用过程中需要精心调参,并用交叉验证的方法选择最佳参数。

Bagging

对于Bagging主要是针对模型的方差进行优化,也就是提高模型的泛化能力。

Bagging 使用bootstrap的方法从整体数据集中有放回的抽样得到N个数据集,bootstrap也成为自助法,目的是为了得到统计量的分布及置信区间。

  • 采用有放回抽样从原始样本中抽取一定数量的样本
  • 根据抽取的样本计算想要得到的统计量
  • 重复N次得到N个统计量
  • 根据这N个统计量,得到统计量的置信区间

在Bagging中采用有放回的抽样方法得到N个数据集,在每个数据集中学习一个模型,最后的预测模型结果使用N个模型的输出得到,对于分类问题,采用N个模型预测投票的方法,对于回归问题采用N个模型预测的平均值。

对于Bagging,多个训练集训练的学习器之间是相互独立的,可以进行并行训练,最常用的是随机森林(RF),在随机森林算法中,使用随机的方式建立一个森林,森林由很多的决策树组成,随机森林的每一颗决策树之间是没有关联的。

随机森林的构建

对于随机森林的构建步骤

  1. 假设有N个样本,采用有放回抽样的方式选择N个样本,选择好的N个样本用来训练一个决策树,作为决策树根节点出的样本

  2. 假设每个样本都有M个属性,在决策树的每个节点需要分裂的时候,对于传统的决策树来数一般采用的是信息论的评价指标或者最小平常差损失,但是在随机森林中,随机的从这M个属性中选择出m个属性,满足条件$m<<M$。然后从这m个属性中采用决策树的的分类策略或回归策略,在这个属性自己种选择一个最优的属性来进行当前节点的划分

  3. 决策树形成过程中每个节点的划分都是按照上述方法进行划分(如果下一个节点选出来的属性刚刚是父节点分裂时用过的属性,则认为该节点已经达到了叶节点,因此当前节点无需分裂),一直到不能分裂为止,整个决策树的形成过程无需进行剪枝

  4. 按照上述的1-3步骤建立多个决策树,如此构成了整个随机森林,多个决策树之间是相互独立的,可以进行分别单独训练

NOTE:在每个决策树的创建过程中存在两个随机过程

  • 样本的随机性,采用有放回的抽样方式,总样本数量为N,放回抽样N次总共得到样本N个,由此得到的样本中肯定存在着重复的样本,当然也会有样本不会被抽取到,根据bootstrap的抽样方法,假设总样本集的数量为N,每个样本被抽取到的概率为$\frac{1}{N}$,那么在样本集中样本在N次采样中始终不被采样到的概率为$(1-\frac{1}{N})^N$,由此求极限可以得到$\lim _{N \rightarrow \infty} (1-\frac{1}{N})^N \mapsto \frac{1}{e} \approx 0.368$,可以认为初始数据集中约有$36 \%$的样本从未出现在采样的数据集中
  • 属性的随机性,在每个节点的划分时,不是针对所有的属性空间上而是针对一个属性空间的子集,该子集也是通过随机选择的方式从整个特种空间中选取。

随机森林的优缺点

优点

  • 在随机森林中,由于这两个随机性的加入,对单个决策树不进行剪枝的情况下有效避免了过拟合的风险
  • 能够处理高维数据(样本属性很多),并且不同进行特征选择,对数据集的适应性较强
  • 在创建随机森林的时候,对generlization error使用的是无偏估计,模型泛化能力强
  • 在训练过程中,能够检测到feature间的互相影响,$p_{ij}=\frac{a_{ij}}{N}$其中$a_{ij}$表示样本i和j出现在随机森林中同一个叶子节点的次数,N为随机森林中树的数量
  • 训练速度快,可以得到变量重要性排序
  • 容易进行并行训练

缺点

  • 随机森林已经被证明在某些噪音较大的分类或回归问题上会过拟

  • 对于有不同取值的属性的数据,取值划分较多的属性会对随机森林产生更大的影响,所以随机森林在这种数据上产出的属性权值是不可信的。

Reference

  1. RF,GBDT,XGBOOST
  2. 通俗理解kaggle比赛大杀器xgboost
  3. Adaboost算法
  4. Wiki: Gradient boosting
  5. 知乎:GBDT
-------------本文结束知识分享,方便你我-------------

本文标题:Boosting_And_Bagging

文章作者:ShiXiaofeng

发布时间:2019年01月25日 - 16:09

最后更新:2019年01月25日 - 20:53

原始链接:http://xiaofengshi.com/2019/01/25/Boosting-And-Bagging/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%