集成学习（Ensemble learning）

大家好，欢迎来到IT知识分享网。

1.集成学习简介

集成学习是通过构建并结合多个学习器来完成学习任务，这些学习器被称为“个体学习器”，不同的个体学习器 和 这些个体学习器的不同的集成方式决定了不同的集成学习方法。

如果个体学习器都是从某一种学习算法从训练数据中产生，则称这样的集成学习是同质的，此时的个体学习器也称作基学习器，相应的学习算法称作基学习算法；

如果个体学习器是从某几种学习算法从训练数据中产生，则称这样的集成学习是异质的

强可学习：一个概念（或一个类别），若存在一个多项式的学习算法能够学习它并且正确率很高，那么称这个概念是强可学习的

弱可学习：一个概念（或一个类别），若存在一个多项式的学习算法能够学习它，学习的正确率仅比随机猜测略好，那么称这个概念是弱可学习的

在PAC（概率近似正确）框架下，强可学习与弱可学习是等价的，即：若在学习中发现了 ”弱学习算法“ ，则可以通过某些办法将它提升为 ”强学习算法“，这也是集成学习的理论基础

2.集成学习的理论基础

以一个二分类问题举例。设单个样本为 ，真实类别为 

假定个体分类器的错误率为 ，即对每个个体分类器  有：

假设集成学习通过简单投票法结合  个个体分类器  。即：若有超过半数的个体分类器正确，则集成分类就正确。根据描述，给出集成学习器为：

所以集成学习器预测错误的条件为：少于一半的个体分类器预测正确，则错误的概率为，由霍夫丁不等式 ε<0.5 时

当M趋近于无穷时，集成学习的错误率趋近于0

举个例子：

由，取不同的M和ε

假设一个学习器错误率为0.3，则1个学习器的错误率就是0.3，5个学习器的集成就是M=5，错误率为0.253，M=10时，错误率为0.099；

假设一个学习器错误率为0.4，则1个学习器的错误率就是0.4，5个学习器的集成就是M=5，错误率为0.317，M=10时，错误率为0.267；

假设一个学习器错误率为0.5，则1个学习器的错误率就是0.5，5个学习器的集成就是M=5，错误率为0.5，M=10时，错误率为0.5；

假设一个学习器错误率为0.6，则1个学习器的错误率就是0.6，5个学习器的集成就是M=5，错误率为0.683，M=10时，错误率为0.733；

可见，集成学习对个体学习器提出了两个要求：

1.错误率应当尽量的低，个体学习器错误率越低，集成学习的增效越明显，个体学习器最差也应当优于随机选择，否则集成学习反而会增大错误率

2.以上计算都是基于不同学习器的决策相互独立的情况，即每个学习器是完全不同的，如果个体学习器给出的决策都是相同或相似的，集成学习就失去了意义

但是，实际情况是我们的个体学习器的决策不可能是完全独立的，个体学习器是为了解决同一个问题训练出来的，而且可能是同一类算法从同一个训练集中产生，实际上个体学习器的准确性和多样性本身就存在冲突，这也是“没有免费午餐”定理的体现，所以如何产生并结合”好而不同“的个体学习器就是集成学习研究的核心

集成学习的优点：

由于学习任务的假设空间往往很大，可能有多个假设在训练集上达到同等性能，此时如果使用单学习器可能因为造成误选而导致泛化性能不佳，通过学习器组合之后会减小这一风险。

学习算法往往会陷入局部极小。有的局部极小点所对应的泛化性能可能很差，而通过学习器组合之后可降低陷入糟糕局部极小的风险。

某些学习任务的真实假设可能不在当前学习算法所考虑的假设空间中，此时使用单学习器肯定无效，通过学习器组合之后，由于相应的假设空间有所扩大，有可能学得更好的近似。

3.Boosting

Boosting是一族算法，这类算法的基本原理是：

先从初始训练集训练出一个基学习器。

再根据基学习器的表现对训练样本分布进行调整，使得先前基学习器做错的训练样本在后续受到更多关注。

然后基于调整后的样本分布来训练下一个基学习器。

如此重复，直到基学习器数量达到事先指定的值M 。

最终将这M个基学习器进行加权组合。

Boosting族算法最著名的代表是AdaBoost算法：

集成学习器的形式：

（代表个体学习器，表示该个体学习器的重要性）

下面直接通过例子去理解AdaBoost算法。

例 给定如下表所示训练数据。假设个体学习器由x（输入）和y（输出）产生，其阈值v（判定正反例的分界线）使该分类器在训练数据集上分类误差率最低。（y=1为正例，y=-1为反例）

第一个个体学习器：

我们首先认为(i=1,2,…,10)的权重是一样的，即每一个数据同等重要。（权重是用来计算误差的）

（a）在权值分布为的训练数据上，阈值v取2.5（红线）时分类误差率最低（此时x=6,7,8的数据被错分为反例，误差为它们的权重之和=0.1+0.1+0.1=0.3，误差率小于才有意义），故个体学习器为

（b）根据误差计算系数=0.4236（公式：，可以发现只有当<时，>0，这样个体学习器才是有意义的）

（c）更新训练数据的权值分布（公式：，

是归一化函数

可以看到x=6,7,8的数据的权重变大了，而其他数据的权重降低了，这是希望能把之前经常分类错误（经常分类错误会出现权重不断变大）的数据能在下一个个体学习器分类正确（记住：权重是用来计算误差的，为了降低误差，选择阈值时会倾向把权重大的分类正确）

集成学习器（第一次集成，只有一个个体学习器）在训练数据集上有3个误分类点

第二个个体学习器：

（a）在权值分布为的训练数据上，阈值v取8.5时分类误差率最低（此时x=3,4,5的数据被错分为正例，误差为它们的权重之和=0.07143+0.07143+0.07143=0.2143，误差率降低了！），故个体学习器为

（b）根据误差计算系数

（c）更新训练数据的权值分布（在的基础上调整，分类正确的降低权重，分类错误的增加权重）：

对比可以看到x=3,4,5的数据的权重变大了，而其他权重降低了。

，

（注意：x<2.5时，也<8.5）

分类器在训练数据集上有3个误分类点

第三个个体学习器：

（a）在权值分布为的训练数据上，阈值v取5.5时分类误差率最低（=0.1820，误差率又降低了！x=0,1,2,9被分类错误），故个体学习器为

（b）根据误差计算系数

（c）更新训练数据的权值分布：

最终结果：

分类器在训练数据集上有0个误分类点（amazing！）

为什么Adaboost能有效：

容易分类对的数据大多数前面的分类器能分类对，虽然前面的分类器权值较低，但是个数多。不容易分类对的数据后面的分类器能分对，虽然个数少，但是权值高（比如，有一部分数据在1，2号分类器可以分对，有一部分在2，3号分类器可以分对）

标准的AdaBoost算法只适用二类分类问题，可以将它推广到多分类问题。 有两种算法：

SAMME 算法：该算法不需要个体分类器输出预测类别的概率。

SAMME.R 算法：该算法需要个体分类器输出类别的概率。（用类似于交叉熵的方式计算损失函数）

此外还有用于回归问题的AdaBoost回归算法。

思想与AdaBoost算法是类似的，在此就不介绍

4.Bagging

Bagging直接基于自助采样法。

自助采样法的步骤是：给定包含  个样本的数据集：先随机取出一个样本放入采样集中，再把该样本放回原始数据集。这样经过  次随机采样操作，得到包含  个样本的采样集。初始训练集中有的样本在采样集中多次出现，有的则从未出现。一个样本始终不在采样集中出现的概率是  。根据  ，因此初始训练集中约有 63.2% 的样本出现在了采样集中。

自助采样法给Bagging算法带来了额外的优点：由于每个基学习器只用初始训练集中约 63.2% 的样本来训练，剩下的约 36.8% 的样本可用作验证集来对泛化性能进行包外估计。

Bagging的基本流程：

经过M轮自助采样，可以得到N个包含训练样本的采样集。

然后基于每个采样集训练出一个基学习器。

最后将这M个基学习器进行组合，得到集成模型。

在使用 Bagging学习器进行预测时：

分类任务采取简单投票法，取每个基学习器的预测类别的众数。

回归任务使用简单平均法，取每个基学习器的预测值的平均。

从偏差-方差分解的角度来看：

Bagging主要关注降低方差，它能平滑强学习器的方差。因此它在非剪枝决策树、神经网络等容易受到样本扰动的学习器上效果更为明显。

Boosting 主要关注降低偏差，它能将一些弱学习器提升为强学习器。因此它在SVM 、knn 等不容易受到样本扰动的学习器上效果更为明显

随机森林:

随机森林Random Forest:RF 是Bagging的一个扩展变体。

随机森林对Bagging做了小改动：

Bagging中基学习器的“多样性”来自于样本扰动。样本扰动来自于对初始训练集的随机采样。随机森林中的基学习器的多样性不仅来自样本扰动，还来自属性扰动。这就是使得最终集成的泛化性能可以通过个体学习器之间差异度的增加而进一步提升。

随机森林在以决策树为基学习器构建Bagging集成模型的基础上，进一步在决策树的训练过程中引入了随机属性选择。传统决策树在选择划分属性时，是在当前结点的属性集合中(假定有n个属性)选择一个最优属性。随机森林中，对基决策树的每个结点，先从该结点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。

如果k=n则基决策树的构建与传统决策树相同。

如果k=1则随机选择一个属性用于划分。

通常建议

随机森林的优点：

训练效率较高。因为随机森林使用的决策树只需要考虑所有属性的一个子集。

随机森林简单、容易实现、计算开销小。

随机森林在很多现实任务中展现出强大的性能，被称作“代表集成学习技术水平的方法”。

随着树的数量的增加，随机森林可以有效缓解过拟合。因为随着树的数量增加，模型的方差会显著降低。但是树的数量增加并不会纠正偏差，因此随机森林还是会有过拟合。

5.集成策略

一共有三种集成策略：平均法，投票法，学习法

学习法：

学习法中，个体学习器的分类结果通过与另一个学习器来组合。

此时称个体学习器为初级学习器，用于组合的学习器称作次级学习器或者元学习器meta_learner。

学习法的典型代表就是stacking集成算法。stacking 集成算法中：

首先从初始数据集训练出初级学习器。

然后将初级学习器的预测结果作为一个新的数据集用于训练次级学习器，在这个新数据集中，初级学习器的输出被当作样本输入特征；初始样本的标记仍被视作标记。

若直接使用初级学习器的输出来产生次级训练集，则容易发生过拟合，一般是通过使用交叉验证，使用训练初级学习器时未使用的样本来产生次级学习器的训练样本。

次级学习器的输入属性表示和次级学习算法对stacking集成算法的泛化性能有很大影响。通常推荐：次级学习器的输入特征是以初级学习器的输出类概率为特征。或采用多响应线性回归Multi-response Linear Regression:MLR 。

增强多样性的方法：

数据样本扰动：给定初始数据集，可以从中产生出不同的数据子集。再利用不同的数据子集训练出不同的个体学习器。数据样本扰动通常是基于采样法，此类做法简单高效、使用最广。对于常见的基学习器，如决策树、神经网络等，训练样本稍加变化就会导致学习器有显著的变动，数据样本扰动法对这样的“不稳定基学习器”很有效。对于一些基学习器对数据样本的扰动不敏感，如线性学习器、支持向量机、朴素贝叶斯、KNN等，这样的基学习器称作稳定基学习器。对于此类的基学习器进行集成往往需要使用输入属性扰动等其他机制。

输入属性扰动：训练样本通常由一组属性描述，不同的“子空间”提供了观察数据的不同视角。显然从不同子空间训练出来的个体学习器必然有所不同。对于包含了大量冗余属性的数据，在子空间中训练个体学习器不仅能够产生多样性大的个体，还会因为属性数量的减少而大幅节省时间开销。同时由于冗余属性多，减少一些属性之后训练的个体学习器也不至于太差。对于只包含少量属性的数据，或者冗余属性较少，则不宜采用输入属性扰动法。

输出表示扰动：此类做法的思路是对输出表示进行操纵以增强多样性。如：可以对训练样本的类标记稍作变动，如翻转法Flipping Output随机改变一些训练样本的标记。

算法参数扰动：基学习算法一般都有超参数需要设置。可以通过随机设置不同的超参数，从而产生差别较大的个体学习器。使用单一学习器时通常需要使用交叉验证等方法来确定最佳的超参数值。这种做法实际上是用了不同的超参数训练出来了多个学习器，只不过最终挑选出来效果最好的那个学习器来使用。集成学习则是相当于把所有这些学习器都利用起来。

不同的多样性增强机制可以同时使用。如随机森林同时是用了数据样本扰动和输入属性扰动。

6.提升树（boosting tree，BT）

提升树boostring tree(BT)是以决策树为基本学习器的提升方法。它被认为是统计学习中性能最好的方法之一。
提升树模型可以表示为决策树为基本学习器的加法模型（也被叫做前向分步算法）：

梯度提升树（GBT）：

梯度提升树用于分类模型时，是梯度提升决策树GBDT；用于回归模型时，是梯度提升回归树GBRT

提升树中，当损失函数是平方损失函数和指数损失函数时，无论残差是什么值，拟合都非常简单，但当损失函数是其他自定义的函数时，拟合就会很困难，这是就要对残差做一些近似的操作，利用损失函数的负梯度在当前模型的值作为残差的近似值，从而拟合一个树。

思想类似于最速下降法，根据：

则有：

要使得损失函数降低，一个可选的方案是： 。

对于平方损失函数，它就是通常意义上的残差。对于一般损失函数，它就是残差的近似 。

提升树的正则化方法：

1.在工程应用中，通常利用下列公式来更新模型：

其中  称作学习率，学习率是正则化的一部分，它可以降低模型更新的速度（需要更多的迭代）。

2.xgboost算法：xgboost 也是使用与提升树相同的前向分步算法。其区别在于：xgboost 通过结构风险极小化来确定下一个决策树的参数

有一种常见的衡量决策树复杂程度的方法（该复杂度是一个经验公式。事实上还有很多其他的定义复杂度的方式，只是这个公式效果还不错）：

 其中： 为叶结点的个数； 为每个叶结点的输出值； 为系数，控制这两个部分的比重。

叶结点越多，则决策树越复杂。

每个叶结点输出值的绝对值越大，则决策树越复杂。