集成学习之bagging和boosting

什么是集成学习？

1. 将多个分类方法聚集在一起，以提高分类的准确率。
（这些算法可以是不同的算法，也可以是相同的算法）
   
   • 集成学习法由训练数据构建一组基分类器，然后通过对所有基分类器的预测投票进行分类。
   • 严格来说，集成学习并不算是一种分类器，而是一种分类器结合的方法。
   • 通常，一个集成分类器的分类性能会好于单个分类器。
   • 如果把单个分类器当作一个决策者的话，集成学习的方法就相当于多个决策者共同进行一项决策。
     

集成学习的条件

通过集成学习提高分类器的整体泛化能力是有条件的：
1、分类器之间应该有差异，否则只不过是好多个自己在重复做同一件事而已，分类出来的结果是不会有变化的。
2、分类器的精度。每个基分类器的分类精度必须大于0.5。如果都小于0.5的话，随着集成规模的增加，分类精度会下降，最终趋于0。

如何构建具有差异性的分类器？

• 处理数据集
  其实就是抽样。获得多个不同的训练子集。流行的方法有袋装（bagging）和提升（boosting）。
• 处理数据特征
  通过对训练数据的特征抽取不同子集再分别进行训练。一般用随机子空间，少量余留法（抽取最重要的一些特征），遗传算法等。
• 处理分类器
  通过改变一个算法的参数来生成有差异性的同质分类器，比如改变神经网络的结构就可以构建出不同的分类器。

如何得到若干个分类器

参考集成学习原理小结
集成学习的第一个问题就是如何得到若干个分类器。这里我们有两种选择。

　　第一种就是所有的个体学习器都是一个种类的，或者说是同质的。比如都是决策树个体学习器，或者都是神经网络个体学习器。第二种是所有的个体学习器不全是一个种类的，或者说是异质的。比如我们有一个分类问题，对训练集采用支持向量机个体学习器，逻辑回归个体学习器和朴素贝叶斯个体学习器来学习，再通过某种结合策略来确定最终的分类强学习器。

　 目前来说，同质个体学习器的应用是最广泛的，一般我们常说的集成学习的方法都是指的同质分类器器。而同质分类器使用最多的模型是CART决策树和神经网络。
　 同质个体学习器按照个体学习器之间是否存在依赖关系可以分为两类，第一个是个体学习器之间存在强依赖关系，一系列个体学习器基本都需要串行生成，代表算法是boosting系列算法，第二个是个体学习器之间不存在强依赖关系，一系列个体学习器可以并行生成，代表算法是bagging和随机森林（Random Forest）系列算法。下面就分别对这两类算法做一个概括总结。

如何对基分类器的结果进行整合？

• 平均法——对于回归预测（数值预测）
  
  1. 简单平均，就是取各个分类器结果的平均值。
  2. 加权平均，H(x)=∑Ti=1ωihi(x)$H(x)=\sum _{i=1}^T{\omega }_i{h}_i(x)$

• 投票法——对于分类（类别预测）
  1、相对多数投票法：少数服从多数。如果不止一个类别获得最高票，则随机选择一个做最终类别。
  
2、绝对多数投票法：要票过半数。在相对多数投票法的基础上，不光要求获得最高票，还要求票过半数。否则会拒绝预测。
  

3、加权投票法：和加权平均法一样，每个弱学习器的分类票数要乘以一个权重，最终将各个类别的加权票数求和，最大的值对应的类别为最终类别。

• 学习法
  前两个方法都是对弱学习器的结果做平均或者投票，相对比较简单，但是可能学习误差较大，于是就有了学习法这种方法，对于学习法，代表方法是stacking，当使用stacking的结合策略时， 我们不是对弱学习器的结果做简单的逻辑处理，而是再加上一层学习器，也就是说，我们将训练集弱学习器的学习结果作为输入，将训练集的输出作为输出，重新训练一个学习器来得到最终结果。

在这种情况下，我们将弱学习器称为初级学习器，将用于结合的学习器称为次级学习器。对于测试集，我们首先用初级学习器预测一次，得到次级学习器的输入样本，再用次级学习器预测一次，得到最终的预测结果。

bagging(bootstrap aggregating的缩写)

bagging算法（图片来自https://www.cnblogs.com/pinard/p/6131423.html）

从上图可以看出，bagging的个体弱学习器的训练集是通过随机采样得到的。通过T次的随机采样，我们就可以得到T个采样集，对于这T个采样集，我们可以分别独立的训练出T个弱学习器，再对这T个弱学习器通过集合策略来得到最终的强学习器。

对于这里的随机采样有必要做进一步的介绍，这里一般采用的是自助采样法（Bootstap sampling）,即对于m个样本的原始训练集，我们每次先随机采集一个样本放入采样集，接着把该样本放回，也就是说下次采样时该样本仍有可能被采集到，这样采集m次，最终可以得到m个样本的采样集，由于是随机采样，这样每次的采样集是和原始训练集不同的，和其他采样集也是不同的，这样得到多个不同的弱学习器。

随机森林是bagging的一个特化进阶版，所谓的特化是因为随机森林的弱学习器都是决策树。所谓的进阶是随机森林在bagging的样本随机采样基础上，又加上了特征的随机选择，其基本思想没有脱离bagging的范畴。

boosting

boosting算法（图片来自https://www.cnblogs.com/pinard/p/6131423.html）

从图中可以看出，Boosting算法的工作机制是首先从训练集用初始权重训练出一个弱学习器1，根据弱学习的学习误差率表现来更新训练样本的权重，使得之前弱学习器1学习误差率高的训练样本点的权重变高，使得这些误差率高的点在后面的弱学习器2中得到更多的重视。然后基于调整权重后的训练集来训练弱学习器2…如此重复进行，直到弱学习器数达到事先指定的数目T，最终将这T个弱学习器通过集合策略进行整合，得到最终的强学习器。

Boosting系列算法里最著名算法主要有AdaBoost算法和提升树(boosting tree)系列算法。提升树系列算法里面应用最广泛的是梯度提升树(Gradient Boosting Tree)。

bagging算法举个栗子

X 表示一维属性，Y 表示类标号（1或-1）测试条件：当x<=k时，y=？；当x>k时，y=？；k为最佳分裂点。
下表为属性x对应的唯一正确的y类别：

现在进行5轮抽样，结果
如表格所示：


每一轮随机抽样后，都生成一个分类器。然后再将五轮分类融合：

对比符号和实际类，我们可以发现：在该例子中，Bagging使得准确率可达90%。

由此，总结一下bagging方法：
1、Bagging通过降低基分类器的方差，改善了泛化误差。

2、其性能依赖于基分类器的稳定性；如果基分类器不稳定，bagging有助于降低训练数据的随机波动导致的误差；如果稳定，则集成分类器的误差主要由基分类器的偏倚引起。

3、由于每个样本被选中的概率相同，因此bagging并不侧重于训练数据集中的任何特定实例。

bagging减少variance，boosting减少bias

图片来自coursera

High variance 是model过于复杂overfit，记住太多细节noise，受outlier影响很大；high bias是underfit，model过于简单，cost function不够好。

• bagging随机选取data的subset，outlier因为比例比较低，参与model training的几率也比较低，所以bagging降低了outliers和noise对model的影响，所以降低了variance。
• boosting，minimize loss function by definition minimize bias.
  来自知乎 https://www.zhihu.com/question/26760839/answer/68915634

bagging & boosting区别

1. 样本选择
   bagging随机有放回抽样；
   boosting每一轮的训练集不变，只改变样本的权重。
2. 样本权重
   bagging均匀抽样，每个样本权重相等；
   boosting根据错误率调整样本权重，错误率越大的样本权重越大。
3. 预测函数
   bagging所有预测函数权重相等；
   boosting误差越小的预测函数权重越大。
4. 并行计算
   bagging各个预测函数可以并行生成；
   boosting各个预测函数必须顺序迭代生成。