集成学习之Bagging

我们知道，想得到泛化性能强的集成，集成中的个体学习器应尽可能相互独立，虽然独立在现实中无法做到，但是可以设法使基学习器具有较大差异。

Bagging

Bagging是并行式集成学习方法最著名的代表，它是基于前面博客提到的自助采样法：给定m个样本的数据集，我们随机取出一个样本放入采样集中，再把该样本放回初始数据集，使得下一次采样时，该样本仍有可能被采到，这样经过m次随机采样操作，可以得到m个样本的采样集，初始训练集中有的样本在采样集中多次出现，有的则从未出现，据计算，有63.2%的样本出现在采样集中。

照这样，我们可以采样出T个含有m个训练样本的采样集，然后基于每个采样集训练出一个基学习器，再将这些学习器进行结合，这就是Bagging的基本流程。

在对预测输出进行结合时，Bagging通常对分类任务使用简单投票法，对回归任务使用简单平均法。若分类预测时出现两个类收到同样票数的情形则最简单的做法是随机选择一个，也可以进一步考察学习器投票的置信度来确定终胜者。

Bagging的复杂度与Bagging训练一个学习器的复杂度同阶，这说明它是一个很高效的集成学习算法。另外，与标准AdaBoost只适用于二分类任务不同，Bagging能不经修改地用于多分类、回归等任务。

由于每个基学习器只是用了初始训练集的约63.2%的样本，剩下约36.8%的样本可以作为验证集来对泛化性能进行“包外估计”。

事实上，包外估计还有很多用途，例如当基学习器是决策树时可以使用包外样本来辅助剪枝，或用于估计决策树中各结点的后验概率以辅助对零训练样本结点的处理；当基学习器是神经网络时，可使用包外样本来辅助早期停止以减小过拟合风险。

从偏差-方差分解角度来看，Bagging主要关注降低方差，因此它在不剪枝决策树、神经网络等易受样本扰动的学习器上效果更为明显。

随机森林

随机森林是Bagging的一个扩展变体，RF在以决策树为基学习器构建Bagging集成的基础上，进一步在决策树的训练过程中引入随机属性选择。具体来说，传统决策树在选择划分属性时是在当前结点的属性集合(假定有d个属性)中选择一个最优属性；而在RF中，对基决策树的每个结点， 先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性进行划分 ，这里的参数k控制了随机性的引入程度：若k=d，则基决策树的构建与传统决策树相同，若k=1则是随机选择一个属性进行划分；一般情况下，推荐值k=log2(d)。

随机森林的构建过程：

从原始样本中采用有放回抽样的方法选取 n 个样本；

对 n 个样本选取 A 个特征中的随机 a 个，重复 k 次，获得 k 个决策树。

随机森林简单，容易实现，计算开销小，它在很多现实任务中展现出强大性能。它与Bagging不同之处在于，Bagging中基学习器的多样性仅通过样本扰动，随机森林中基学习器的多样性不仅来自样本扰动，还来自属性扰动，这就使得最终集成额泛化性能可以通过个体学习器之间的差异度的增加进一步提升。

值得一提的是，随机森林的收敛性与Bagging相似，随机森林的起始性能往往较差特别是在集成中只包含一个基学习器时，然而，随着个体学习器数目的增加，罪及森林通常会手链到更低的泛化误差。随机森林的训练效率往往优于Bagging因为在个体决策树的构建中，Bagging使用的是确定型决策树，在选择划分属性时要对结点的所有属性进行考察，而随机森林使用的随机型决策树只需考察一个属性子集。

结合策略

学习器的结合可能会从三个方面带来好处：从统计方面来看，由于学习任务的假设空间很大，可能有多个假设在训练集上达到同等性能，此时若使用单学习器可能因误选而泛化性能不佳，结合多个学习器则会减小这一风险；从计算方面来看，学习算法往往会陷入局部极小，有的局部极小点所对应的泛化性能 可能很糟糕，而通过多次运行之后进行结合，可降低陷入糟糕局部极小的风险；从表示的方面来看，某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时若使用简单学习器则肯定无效，而通过结合多个学习器，由于相应的假设空间有所扩大，有可能学得更好的近似。

对各学习器的输出结合方法：

1.平均法

* 简单平均法

* 加权平均法

加权平均法的权重一般是从训练集数据中学习而得，现实任务中的训练样本通常不充分或存在噪声，这使得学出的权重不完全可靠，尤其是对规模比较大的集成来说，要学习的权重比较多，容易导致过拟合，因此，加权平均法未必一定优于简单平均法。一般来说，在个体学习器性能相差较大时宜使用加权平均法，而在个体学习器性能相近时宜使用简单平均法。

2.投票法

* 绝对多数投票法：若标记的票数过半，则预测为该标记，否则拒绝预测

* 相对多数投票法：预测为得票最多的标记，若同时有多个标记获得最高票，则从中随机选取一个

* 加权投票法：与加权平均法类似

标准的绝对多数投票法提供了拒绝预测选项，这在可靠性要求较高的学习任务中是一个很好的机制，但若学习任务要求必须提供预测结果，则绝对多数投票法将退化为相对多数投票法。因此，在不允许拒绝预测的任务中，绝对多数、相对多数投票法统称为多数投票法。

在现实中，不同类型个体学习器可能产生不同类型的hij(x)值，常见的有：

类标记：hij(x)属于{0,1}若将样本预测为类别cj则取值为1，否则为0，使用类标记的投票亦称硬投票。

类概率：hij(x)属于[0,1]相当于对后验概率的一个估计，抵用类概率的投票亦称软投票。

不同的hij(x)不能混用，对一些能在预测出类别标记的同时产生分类置信度的学习器，其分类置信度可转化为类概率使用。有趣的是，虽然分类估计出的类概率值一般都不太准确，但基于类概率进行结合往往比直接基于类标记进行结合性能更好。需要注意的是，若基学习器的类型不同则其类概率值不能直接进行比较，在此种情况下，通常可将类概率输出转化为类标记输出然后再投票。

3.学习法

当训练数据很多时，一种更为强大的结合策略是使用学习法，即通过另一个学习器来进行结合，Stacking是学习法的典型代表，这里我们把个体学习器称为初级学习器，用于结合的学习器称为次级学习器。

Stacking先从初始数据集训练出初级学习器然后生成一个新数据集用于训练次级学习器，在这个新数据集中，初级学习器的输出被当做样例输入特征，而初始样本的标记仍被当做样例标记，Stacking的算法。

一般通过使用交叉验证或留一法用训练初级学习器未使用的样本来产生次级学习器的训练样本。次级学习器的输入属性表示和次级学习算法对Stacking集成的泛化性能有很大影响。有研究表明，将初级学习器的输出类概率作为次级学习器的输入属性，用多响应线性回归作为次级学习算法效果较好，在MLR中使用不同的属性集效果更佳。

贝叶斯模型平均基于后要概率来为不同模型赋予权重，可视为加权平均法的一种特殊实现。理论上来说，若数据生成模型恰在当前考虑的模型中，且数据噪声很少，则BMA不差于Stacking；然而，在现实应用中无法确保数据生成模型一定在当前考虑的模型中，甚至可能难以用当前考虑的模型来进行近似，因此，Stacking通常优于BMA，因为其鲁棒性比BMA更好，而且BMA对模型近似误差非常敏感。

多样性

1.误差-分歧分解

周志华的西瓜书p186给出式子证明：个体学习器准确性越高、多样性越大，则集成越好。不过推导过程只适用于回归学习，难以直接推广到分类学习任务中去。

2.多样性度量

多样性度量适用于度量集成中个体分类器的多样性，即估算个体学习器的多样化程度，典型的做法是考虑分体分类器的两两相似性/不相似性。下面给出一些常见的多样性度量：

* 不合度量

* 相关系数

* Q-统计量

* k-统计量

以上介绍的都是成对型多样性度量，它们可以容易地通过二维图绘制出来

多样性增强

如何增强多样性？一般思路是在学习过程中引入随机性，常见做法主要是对数据样本、输出样本、输出表示、算法参数进行扰动。

* 数据样本扰动

给定初始数据集，可从中产生出不同的数据子集，再利用不同的数据子集训练出不同的个体学习器。数据样本扰动通常是基于采样法，例如在Bagging中使用自助采样，然而有一些基学习器对数据样本扰动不敏感，例如线性学习器、支持向量机、朴素贝叶斯、K近邻学习器等，这样的基学习器称为稳定基学习器，对此类基学习器进行集成往往需要使用输入属性扰动等其他机制。

* 输入属性扰动

著名的随机子空间算法就依赖于输入属性扰动，该算法从初始属性集中抽取出若干个属性子集，再基于每个属性子集训练一个基学习器。值得一提的是，对包含大量冗余属性的数据在子空间中训练个体学习器不仅能产生多样性大的个体，还会因属性数的减少而大幅度节省是假开销，同时，由于冗余属性多，减小一些属性后训练出的个体学习器也不至于太差。若数据只包含少量属性，或者冗余属性很少，则不宜使用输入属性扰动法。

* 输出表示扰动

此类做法的基本思路是对输出表示进行操纵以增强多样性。可对训练样本的类标记稍作变动，如翻转法，随机改变一些训练样本的标记；也可对输出表示进行转化，如输出调制法，将分类输出转化为回归输出后构建个体学习器；还可将原任务拆解为多个可同时求解的子任务，如ECOC法，利用纠错输出码将多分类任务拆解为一系列二分类任务来训练基学习器。

* 算法参数扰动

基学习算法一般都有参数需要进行设置，列入神经网络的隐层神经元数、初始连接权值等，通过随机设置不同的参数，往往可产生差别较大的个体学习器。对于参数较少的算法，可通过将其学习过程中的某些环节用其他类似方式代替，从而达到扰动的目的。

不同的多样性增强机制可同时使用，例如随机森林中同时使用了数据样本扰动和输入扰动，有些方法甚至同时使用了更多机制。

小结

常见得结合方法还有：D-S证据理论的方法、动态分类器选择、混合专家等，上面只介绍了成对型多样性度量，然而，现有多样性度量都存在显著缺陷。

在集成产生之后再试图来获得较小的集成，称为集成修剪。

对并行化集成进行修剪能在减小规模的同时提升泛化性能，并催生了基于优化的集成修剪技术。

由于集成包含多个学习器，即便个体学习器有较好的可解释性，集成仍是黑箱模型。

本文由韩冰冰 创作，采用 知识共享署名-相同方式共享 3.0 中国大陆许可协议 进行许可。

转载、引用前需联系作者，并署名作者且注明文章出处。

本站文章版权归原作者及原出处所有 。内容为作者个人观点， 并不代表本站赞同其观点和对其真实性负责。本站是一个个人学习交流的平台，并不用于任何商业目的，如果有任何问题，请及时联系我们，我们将根据著作权人的要求，立即更正或者删除有关内容。本站拥有对此声明的最终解释权。