【机器学习】集成学习(一)----基本思想和方法

集成学习可谓是机器学习中的大杀器，诸如GBDT(梯度提升树)，RF(随机森林)这些算法都是用到了集成学习的思想。这一篇主要就是复习一下Boosting，Bagging和Stacking这三种方法和常用的结合策略。

集成学习(Ensemble Learning)

也被称为多分类器系统(multi-classifier system)、基于委员会的学习(committee-based learning)。顾名思义，就是将多个个体学习器用某种策略组合起来成为强学习器，通常个体学习器是由已有的学习算法从训练数据中学习产生的。
同质集成，即集成中只包含同种类型的个体学习器，这些个体学习器亦被称为基学习器，产生这些基学习器的学习算法叫作基学习算法。
异质集成，即集成中的个体学习器由不同的学习算法生成。

我们有时也会称基学习器为弱学习器。
对于强弱学习，在《统计学习方法》中有描述，概括来说就是：

在PAC框架中：	定义
强可学习	一个概念，如果存在一个多项式的学习算法能够学习它，并且正确率很高，那么就称这个概念是强可学习
弱可学习	一个概念，如果存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么就称这个概念是弱可学习

其实这个没太理解，不过不影响后面。

集成学习如何能获得比单一学习更好的性能呢？
既然我们将这些弱学习器集成起来得到强学习器，也就是希望能够通过这种方式提高学习器的性能，使准确率能够高于单一的弱学习器(个体学习器)。那么至少满足什么样的条件才能让集成起来的弱学习器能够比单一的弱学习器性能要好呢？
这里举《数据挖掘导论》上的一个例子来说明：
假设我们有25$25$个做二分类的个体学习器，其中每一个个体学习器的误差均为ε=0.35$\epsilon =0.35$。
1.若是所有基学习器都是没有差别的，那么集成这些基学习器之后，性能并没有提高，误差还是0.35$0.35$。
2.若是所有个体学习器都是相互独立的(即它们的误差不相关)，则当我们采用“投票法”这种结合策略时，仅当超过一半的个体学习器都预测错误时，集成后的学习器才会作出错误的预测。这种情况下，集成后的学习器误差为：
eensemble=∑i=1325Ci25εi(1−ε)25−i=0.06$e_{ensemble}=\sum _{i=13}^{2}5C_{25}^i{\epsilon }^i(1-\epsilon {)}^{25-i}=0.06$
明显远小于单个个体学习器的误差。
3.但是当这些个体学习器的误差ε>0.5$\epsilon >0.5$时，我们会发现集成后的学习器的性能并比不上单个的个体学习器。
因此，我们想要让集成起来的个体学习器能够比单一的个体学习器性能要好必须满足两个条件：(1)个体学习器之间应该是相互独立的；(2)个体学习器的性能应当好于随机猜测。
《机器学习》一书中对此是这样描述的，个体学习器应“好而不同”，即个体学习器要有一定的“准确性”，不能太坏，并且要有“多样性”，即学习器之间具有差异。

在理想情况下，我们希望个体学习器相互独立，但在现实任务中，个体学习器是为解决同一个问题而训练出来的，显然不可能相互独立。因此我们如何产生并结合“好而不同”的个体学习器，是最为关键的问题。

集成学习分类

目前，同质个体学习器应用最为广泛，根据这些个体学习器之间是否存在依赖关系可以将其分为两类：
一类是存在强依赖关系、必须串行生成的序列化方法，如Boosting.
另一类是不存在强依赖关系、可同时生成的并行化方法，如Bagging和RF.

根据集成思想，架构可分为三类：
即Boosting、Bagging和Stacking

【Boosting】

Boosting基本思想：先从初始训练集训练出一个基学习器，再根据基学习器的表现对训练样本的分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注，然后基于调整后的样本分布来训练下一个基学习器；如此重复进行，直至基学习器数目达到事先指定的值T$T$，最后将这T$T$个基学习器进行加权结合。
过程如下图：

对于调整样本分布，我们一般用重赋权法(re-weighting)实施，即在训练过程的每一轮中，根据样本分布为每个训练样本重新赋予一个权重。当基学习算法无法接受带权样本时，则可以通过重采样法(re-sampling)来处理，即在每一轮学习中，根据样本分布对训练集重新进行采样，再用重采样而得的样本集对基学习器进行训练。一般而言，这两种方法没有显著优劣差别。

Boosting$Boosting$系列算法中最著名的算法主要有AdaBoost$AdaBoost$和提升树。

提升树中应用最广的是梯度提升树(GBDT,Gradient Boosting Decision Tree)

【Bagging】(Bootstrap Aggregaing的缩写)

Bootstrap:

自助法，是一种有放回的抽样方法，目的是为了得到统计量的分布以及置信区间。
Bootstrap具体步骤
给定一个包含m$m$个样本的初始训练数据集，每次随机取出一个样本放入采样数据集中，再把这个样本放回初始训练数据集，经过m$m$次随机采样操作，我们得到了一个含m$m$个样本的采样数据集(根据公式limm↦∞(1−1m)m↦1e≈0.368$\underset{m\mapsto \mathrm{\infty }}{lim}(1-\frac{1}{m}{)}^m\mapsto \frac{1}{e}\approx 0.368$可知，初始训练数据集中约有63.2%的样本出现采样集)

Bagging

Bagging基本思想：从初始训练数据集中采样出T$T$个含m$m$个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些基学习器根进行结合。
过程如下图：

RF(Random Forest)，随机森林，它是Bagging$Bagging$的一个扩展变体，后续再去看这个算法。

【Stacking】是结合策略——学习法的典型代表

Stacking基本思想：
先从初始训练数据集根据不同的初级学习算法训练出初级学习器，然后“生成”(如交叉验证或留一法等)一个新的数据集用于训练次级学习器。在这个新数据集中，初级学习器的输出被当作样例输入特征，而初始样本的标记仍被当作样例标记。
过程如下图：

结合策略

【平均法】

①简单平均法

H(x)=1T∑i=1Thi(x)$H(x)=\frac{1}{T}\sum _{i=1}^T{h}_i(x)$

②加权平均法

H(x)=∑i=1Tωihi(x)$H(x)=\sum _{i=1}^T{\omega }_i{h}_i(x)$，通常要求ωi≥0${\omega }_i\ge 0$，∑i=1Tωi=1$\sum _{i=1}^T{\omega }_i=1$

【投票法】

①相对多数投票法

H(x)=Cargmaxj∑i=1Thji(x)$H(x)=C_{arg\underset{j}{max}\sum _{i=1}^T{h}_i^j(x)}$(Cj指输出类别)$(C_j指输出类别)$
即预测为得票最多的标记，若同时有多个标记获得最高票，则从中随机选取一个。

②绝对多数投票法

H(x)=⎧⎩⎨⎪⎪cj,reject,当∑i=1Thji(x)>0.5∑k=1n∑i=1Thki(x)拒绝预测$H(x)=\{\begin{array}{ll}{c}_j,& 当\sum _{i=1}^T{h}_i^j(x)>0.5\sum _{k=1}^n\sum _{i=1}^T{h}_i^k(x)\\ reject,& \text{拒绝预测}\end{array}$
即预测为得票过半数的标记；否则拒绝预测。

③加权投票法

H(x)=Cargmaxj∑i=1Tωihji(x)$H(x)=C_{arg\underset{j}{max}\sum _{i=1}^T{\omega }_i{h}_i^j(x)}$，通常要求ωi≥0${\omega }_i\ge 0$，∑i=1Tωi=1$\sum _{i=1}^T{\omega }_i=1$

以上三个投票法中没有限制个体学习器输出值的类型。在现实任务中，不同类型个体学习器可能产生不同类型的hji(x)$h_i^j(x)$值，常见的有：
类标记：hji(x)∈{0,1}$h_i^j(x)\in \{0,1\}$
即hji(x)$h_i^j(x)$将样本x$x$预测为类别cj$c_j$则取值为1，否则为0。这种使用类标记的投票亦称为“硬投票”。
类概率：hji(x)∈[0,1]$h_i^j(x)\in [0,1]$
相当于对后验概率P(cj|x)$P(c_j|x)$的一个估计。这种使用类概率的投票亦称为“软投票”。

对于不同类型的hji(x)$h_i^j(x)$值不能混用。对一些能在预测出类别标记的同时产生分类置信度的学习器，其分类置信度可转化为类概率使用。若此类值未进行规范化，例如支持向量机的函数间隔(此处可以看SVM第一篇对函数间隔与置信度的分析)，则必须使用一些技术如Platt$Platt$缩放、等分回归等进行“校准”后才能作为类概率使用。有趣的是，虽然分类器估计出的类概率值一般都不太准确，但基于类概率进行结合却往往比直接基于类标记进行结合性能更好。需注意的是，若基学习器的类型不同，则其类概率值不能直接进行比较；在此情形下，通常可将类概率输出转化为类标记输出(例如将类概率输出最大的hji(x)$h_i^j(x)$设为1，其他设为0)然后再投票。（摘自《机器学习》）

【学习法】

Stacking$Stacking$是学习法的典型代表，当训练数据很多时，这种策略更加强大。

参考文献：《统计学习方法》、《机器学习》、《数据挖掘导论》