集成学习



集成学习

什么是集成学习

弱学习和强学习
集成学习有效的前提
集成学习分类


AdaBoost

Adaboost的算法流程
弱分类器的误差和AdaBoost框架的误差
多属性数据集的处理


Bagging

Bagging的策略


模型的偏差和方差

方差和偏差的来源


随机森林

算法

随机选取训练样本集
随机选取分裂属性集特征投影
特征扩展
特征选择


随机森林的优点与缺点


Stacking








  
什么是集成学习
  
  
所谓集成学习简单理解就是指采用多个分类器对数据集进行预测，从而提高整体分类器的泛化能力。
  
  
弱学习和强学习
  
  
准确率仅比随机猜测略高的学习算法称为弱学习算法;识别准确率很高并能在多项式时间内完成的学习算法称为强学习算法。
  
  
集成学习有效的前提
  
  
1.分类器的精度，每个弱分类器的分类精度必须大于0.5。 

  2.弱分类器之间应该具有差异性，否则集成效果不是很好
  
  
集成学习分类
  
  
按照基本分类器之间的关系可以分为异态集成学习和同态集成学习。 

  异态集成学习是指弱分类器之间本身不同 

  同态集成学习是指弱分类器之间本身相同只是参数不同


>


  
AdaBoost
  
  
AdaBoost，是英文”Adaptive Boosting”（自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。
  
  
Adaboost是一种迭代算法，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。其核心思想是针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)。
  
  
算法根据每次训练集中每个样本的分类是否正确，以及上次的总体分类的准确率，来确定每个样本的权值。将修改过权值的新数据集送给下层分类器进行训练，最后将每次训练得到的分类器最后融合起来，作为最后的决策分类器。
  
  
在具体实现上，最初令每个样本的权重都相等，对于第k次迭代操作，我们就根据这些权重来选取样本点，进而训练分类器。然后就根据这个分类器，来提高被它分错的的样本的权重，并降低被正确分类的样本权重。然后，权重更新过的样本集被用于训练下一个分类器。整个训练过程如此迭代地进行下去。
  
  
Adaboost的算法流程
  
  
1、初始化训练数据的权值分布 $D_1$ 。每一个训练样本最开始时都被赋予相同的权重: $1/m$ 

  
 $$D_1=(w_{11},w_{12},...,w_{1m}), w_{1i}=1/m$$ 

  
  
接下来，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。具体说来，则是
  
  
2、对于 $t=1,2,...,T$
  
  

    
3、基于分布 $D_t$ 从数据集 $D$ 中训练出分类器 $h_t$。（选取让误差率最低的阈值来设计基本分类器） 

    
 $$h_t(x)=\xi(D,D_t)$$ 

    
    
4、计算 $h_t(x)$ 在训练数据集上的分类误差 

    
 $$e_t=P(h_t(x_i) \neq  y_i)= \sum\limits_{i = 1}^m {w_{ti}I(h_t(x_i) \neq  y_i)}$$  

     $$I(h_t(x_i) \neq  y_i)= \begin{cases}
0 & \text{ if } h_t(x_i)=y_i \\ 
1 & \text{ if } h_t(x_i)\neq y_i
\end{cases}$$  

    由上述式子可知，$h_t(x)$ 在训练数据集上的误差率 $e_t$ 就是被$h_t(x)$ 误分类样本的权值之和。

    
    
5、计算分类器 $h_t$ 的权重，$\alpha _t$ 表示 $h_t(x)$ 在最终分类器中的重要程度 

    
 $$\alpha _t=\frac{1}{2}ln(\frac{1-e_t}{e_t})$$  

     

    由上述式子可知，$e_t <= 1/2$ 时，$a_t >= 0$，且 $a_t$ 随着 $e_t$ 的减小而增大，意味着分类误差率越小的基本分类器在最终分类器中的作用越大

    
    
6、更新训练数据集的权值分布，得到样本的新的权值分布，用于下一轮迭代 

    
 $$D_{t+1}=(w_{t+1,1},w_{t+1,2},...,w_{t+1,m})$$  

     $$w_{t+1,i}=\frac{w_{t,i}}{Z_t}\times \begin{cases}
exp(-\alpha _t) & \text{ if } h_t(x_i)=y_i \\ 
exp(\alpha _t)  & \text{ if } h_t(x_i)\neq y_i
\end{cases}\\=\frac{w_{t,i}}{Z_t}exp(-\alpha _th_t(x_i)y_i)$$  

    使得被基本分类器 $h_t(x)$ 误分类样本的权值增大，而被正确分类样本的权值减小。通过这样的方式，AdaBoost方法能“聚焦于”那些较难分的样本上。其中，$Z_t$ 是规范化因子，使得 $D_{t+1}$ 成为一个概率分布。 

     $$Z_t=\sum_{i=1}^{m}w_{ti}exp(-\alpha_t y_ih_t(x_i))$$ 

    
    
7、最后总体分类的判决使用各个弱分类器的加权平均 

    
 $$f(x)=\sum_{t=1}^{T}\alpha _th_t(x)$$ 

  
  
  
8、得到最终分类器 

  
 $$h(x)=sign\left ( f(x) \right )=sign\left (\sum_{t=1}^{T}\alpha _t h_t(x) \right )$$ 

  
  
弱分类器的误差和AdaBoost框架的误差
  
  
在整个训练的过程中，每轮训练得到的弱分类器可能一直会存在分类错误的问题（不论训练了多少轮，生成的单个弱分类器都有分类错误），然而整个AdaBoost框架却有可能快速收敛（整个AdaBoost框架的错误率为0）。造成这个现象的原因是：
  
  
每轮训练结束后，AdaBoost框架会对样本的权重进行调整，该调整的结果是越到后面被错误分类的样本权重会越高。这样到后面，单个弱分类器为了达到较低的带权分类误差都会把样本权重高的样本分类正确。
  
  
虽然单个弱分类器会造成分类错误，但这些错误分类的弱分类器的权重相对全体分类器是比较低的，在最后输出时会被前面正确分类的高权重弱分类器“平衡”掉。这样造成的结果就是，虽然每个弱分类器可能都有分错的样本，然而整个AdaBoost框架却能保证对每个样本进行正确分类，从而实现快速收敛。
  
  
多属性数据集的处理
  
  
在每一轮训练过程中，在每个属性上根据分割的阈值不同得到多个单层分类器。在这些从所有属性上得到的分类器中选取一个带权误差率最小的单层分类器作为该轮训练的弱分类器。




Bagging


  
想要得到泛化性能强的集成，集成中的个体学习器应尽可能相互独立，但是相互独立很难做到，我们可以做的是使基学习器尽可能具有较大的差异。
  
  
一种可能的做法是对训练样本进行采样，产生若干个不同的子集，再从每个子集中训练出一个基学习器。这样获得的基学习器渴望有较大的差异。为了获得好的集成，使用相互有交叠的采样子集，这样每个学习器使用到足够多的训练数据，使得学习器不会太差
  
  
Bagging是并行式集成学习方法的著名代表，它是基于自助采样法(有放回的取样)来提高学习器泛化能力的一种很高效的集成学习方法。 
  
  
Bagging的策略
  
  
从包含 $m$ 个样本的数据集 $D$ 中用自助采样选出 $m$ 个样本，执行 $T$ 次，选出 $T$ 个样本子集 $\{D_1,D_2,...,D_T\}$。在所有属性上，分别对应这 $T$ 个样本子集建立 $T$ 个学习器 $\{h_1(x),h_2(x),...,h_T(x)\}$，将这 $T$ 个学习器放在各自的训练数据上进行学习通过投票法或平均法对这 $T$ 个学习器进行结合。 

  
  
  
由于Bagging采用的是自助采样法，那么基学习器大概只使用了初始训练集中约63.2%的样本，剩下的样本可以用作验证集来对泛化性能进行估计。


模型的偏差和方差


  
任何模型中出现的误差都可以在数学上分解成三个分量 

  
 $$Err(x)=(E[\widehat{f}(x)]-f(x))^2+E[\widehat{f}(x)-E[\widehat{f}(x)]]^2+\sigma_e^2$$  

   $$Err(x)=Bias^2+Variance+Irreducible Error$$ 

  
  
偏差：描述的是预测值（估计值）的期望与真实值之间的差距。偏差越大，越偏离真实数据， 

  方差：描述的是预测值的变化范围，离散程度，也就是离其期望值的距离。方差越大，数据的分布越分散
  
  
通常情况下，增加模型的复杂性时，偏差的降低将直接导致模型总误差的减少，但当过了某个特定的点之后，再增加模型的复杂程度则会适得其反。最终，模型将面临过度拟合的问题，并且具有了较高的方差。理论上，最优的模型应该做到尽量保持上述两类误差之间平衡。 

  
  
  
方差和偏差的来源
  
  
机器学习的模型，对数据非常依赖。如果我们不知道数据服从什么样的分布，或者没有办法拿到所有可能的数据，那么训练出来的模型和真实模型之间就会存在不一致。这种不一致表现在两个方面。
  
  

    
1、真实模型根本就没有包含在我们训练模型的模型空间中。比如本来是非线性模型，你非要拿线性模型去拟合数据，那么不论你怎么调整模型参数去选择模型，结果也是不对的。这就是偏差的来源。表现为模型不正确。
    
    
2、不管真实模型在不在我们训练模型的空间中，由于我们不能拿到所有可能的数据，如果拿到的数据不是那么具有代表性，那么不同的数据训练出来的模型参数就会不同。然后用这个模型去做预测，结果也就会和真实值之间有差异。这就是方差的来源。表现为模型不稳定。
  
  
  
用打靶的例子来说明。偏差好比你的瞄准能力；方差好比你使用的枪的性能。 

  


随机森林


  
Bagging算法通过自助采样得到不同的数据，然后得到不同的学习器，最后通过投票和平均的方式得到最终的学习器，以达到降低variance的效果。决策树算法通过递归方式建立子树，最终得到完整的树，它对于不同的数据相对会敏感，即其算法的variance很大。如果将这两种方法结合起来，就是随机森林。
  
  
随机森林是一种多功能的机器学习算法，能够执行回归和分类的任务。在随机森林中，我们将生成很多的决策树。在分类任务中，随机森林中的每一棵树都会给出自己的分类选择，并由此进行“投票”，森林整体的输出结果将会是票数最多的分类选项；在回归问题中，随机森林的输出将会是所有决策树输出的平均值。
  
  
Alt text
  
  
算法
  
  

  
  
随机选取训练样本集
  
  
使用自助采样方法形成每颗树的训练集。
  
  
随机选取分裂属性集(特征投影)
  
  
假设共有M个属性，指定一个属性数F≤M，在每个内部结点，从M个属性中随机抽取F个属性，以这F个属性上最好的分裂方式对结点进行分裂。这个过程中，相当于作了低维度的投影。 得到的特征实际上是原始特征的随机子集，这使得生成模型过程中的效率也大大提高了。
  
  
特征扩展
  
  
更加有能力的特征投影就是不再单一选取单一维度的特征，而是将多个维度的特征进行组合，得到新的一维的特征，这称为特征扩展。
  
  
特征选择
  
  
为了解决如何选择特征的组合方式的问题，我们暂不考虑特征之间的相关关系，而是为每个特征打一个分数，表示特征的重要性，然后按照重要性进行排序，选择最重要的前K个特征作为选取出来的特征。
  
  
特征选择舍去不必要的特征，使得模型复杂度大大降低，可以简化假设，缩短预测时间；同时，舍去了特征的噪声，可以提高模型的泛化能力，使得模型不容易对噪声过拟合。随机森林算法是一个非线性的模型，我们不能单纯以线性模型中的权重作为衡量特征重要性的标准。
  
  
Permutation Test:
  
  

    
Permutation Test的方法是通过将第i个维度特征的所有数据重新的随机调整位置，然后比较一下原始数据和调整之后的数据表现的差距，来评价这个维度的特征是有多么重要。 
  
  
  
随机森林的优点与缺点
  
  
优点： 

  1.随机森林算法能解决分类与回归两种类型的问题，并在这两个方面都有相当好的估计表现
  
  
2.随机森林对于高维数据集的处理能力令人兴奋，它可以处理成千上万的输入变量，并确定最重要的变量，因此被认为是一个不错的降维方法。
  
  
3.在对缺失数据进行估计时，随机森林是一个十分有效的方法。就算存在大量的数据缺失，随机森林也能较好地保持精确性；
  
  
4.当存在分类不平衡的情况时，随机森林能够提供平衡数据集误差的有效方法；
  
  
5.模型的上述性能可以被扩展运用到未标记的数据集中，用于引导无监督聚类、数据透视和异常检测 

  缺点： 

  1.随机森林在解决回归问题时并不能给出一个连续型的输出。随机森林不能够作出超越训练集数据范围的预测，这可能导致在对某些还有特定噪声的数据进行建模时出现过度拟合。
  
  
2.对于许多统计建模者来说，随机森林给人的感觉像是一个黑盒子——你几乎无法控制模型内部的运行，只能在不同的参数和随机种子之间进行尝试。


Stacking


  
stacked 产生方法是一种截然不同的组合多个模型的方法，它讲的是组合学习器的概念
  
  
过程 

  1、划分训练数据集为两个不相交的集合。 

  2、 在第一个集合上训练多个学习器。 

  3、 在第二个集合上测试这几个学习器 

  4、把第三步得到的预测结果作为输入，把正确的回应作为输出，训练一个高层学习器，
  
  

 

集成学习简介

集成学习（ensemble learning）通过构建并结合多个学习器来完成学习任务。

如何产生“好而不同”的个体学习器，是集成学习研究的核心。

集成学习的思路是通过合并多个模型来提升机器学习性能，这种方法相较于当个单个模型通常能够获得更好的预测结果。这也是集成学习在众多高水平的比赛如奈飞比赛，KDD和Kaggle，被首先推荐使用的原因。

一般来说集成学习可以分为三大类：

用于减少方差的bagging
	
用于减少偏差的boosting
	
用于提升预测结果的stacking
集成学习方法也可以归为如下两大类：

串行集成方法，这种方法串行地生成基础模型（如AdaBoost）。串行集成的基本动机是利用基础模型之间的依赖。通过给错分样本一个较大的权重来提升性能。
	
并行集成方法，这种方法并行地生成基础模型（如Random Forest）。并行集成的基本动机是利用基础模型的独立性，因为通过平均能够较大地降低误差。
大部分集成模型都通过一个基础学习算法来生成一个同质的基础学习器，即同类型的学习器，也叫同质集成。

有同质集成就有异质集成，为了集成后的结果表现最好，异质基础学习器需要尽可能准确并且差异性够大。

 

 

Bagging

 

Bagging是引导聚合的意思。减少一个估计方差的一种方式就是对多个估计进行平均。例如，我们可以用训练集的不同子集（随机选择并替代训练集）训练M个不同的树然后计算最后的结果：

Bagging使用装袋采样来获取数据子集训练基础学习器。通常分类任务使用投票的方式集成，而回归任务通过平均的方式集成。

 

1）从原始样本集中抽取训练集。每轮从原始样本集中使用Bootstraping（有放回）的方法抽取n个训练样本（在训练集中，有些样本可能被多次抽取到，而有些样本可能一次都没有被抽中）。共进行k轮抽取，得到k个训练集。（我们这里假设k个训练集之间是相互独立的，事实上不是完全独立）

2）每次使用一个训练集得到一个模型，k个训练集共得到k个模型。但是是同种模型。（注：，k个训练集虽然有重合不完全独立，训练出来的模型因为是同种模型也是不完全独立。这里并没有具体的分类算法或回归方法，我们可以根据具体问题采用不同的分类或回归方法，如决策树、感知器等）

3）对分类问题：将上步得到的k个模型采用投票的方式得到分类结果；对回归问题，计算上述模型的均值作为最后的结果。（所有模型的重要性相同）

对于Bagging需要注意的是，每次训练集可以取全部的特征进行训练，也可以随机选取部分特征训练，例如随机森林就是每次随机选取部分特征

 

 

常用的集成算法模型是随机森林和随机树

在随机森林中，每个树模型都是装袋采样训练的。另外，特征也是随机选择的，最后对于训练好的树也是随机选择的。

这种处理的结果是随机森林的偏差增加的很少，而由于弱相关树模型的平均，方差也得以降低，最终得到一个方差小，偏差也小的模型。



在一个极端的随机树算法中，随机应用的更为彻底：训练集分割的阈值也是随机的，即每次划分得到的训练集是不一样的。这样通常能够进一步减少方差，但是会带来偏差的轻微增加。

 

 

下面通过应用Iris数据集的分类问题来距离说明bagging。

我们可以使用两种基础模型：决策树和KNN。图中展示了基础模型与集成模型学习得到的决策边界。

Accuracy: 0.63 (+/- 0.02) [Decision Tree]      Accuracy: 0.64 (+/- 0.01) [Bagging Tree]

Accuracy: 0.70 (+/- 0.02) [K-NN]                 Accuracy: 0.59 (+/- 0.07) [Bagging K-NN]

 



 

决策树学到的是轴平行边界，然而k=1最近邻对数据拟合的最好。bagging通过训练10个基础模型能过随机选择80%的数据作为训练集，同样随机选择80%的特征进行训练。

 

决策树bagging集成相比K-NN bagging集成获得了更高的准确率。K-NN对于训练样本的扰动并不敏感，这也是为什么K-NN成为稳定学习器的原因。

整合稳定学习器对于提升泛化性能没有帮助。

图像结果同样展示了通过增加集成模型的个数带来的测试准确率变化。基于交叉验证的结果，我们可以看到整合基础模型个数大于10个之后性能就基本不再提升了，只是带来了计算复杂度的增加。

最后一张图绘制的是集成学习模型的学习曲线，注意训练集数据的平均误差为0.3，在对训练集做80%采样的时候训练集和验证集误差最小。

 

 

Boosting(提高)

Boosting指的是通过算法集合将弱学习器转换为强学习器。boosting的主要原则是训练一系列的弱学习器，所谓弱学习器是指仅比随机猜测好一点点的模型，例如较小的决策树，训练的方式是利用加权的数据。在训练的早期对于错分数据给予较大的权重。

对于训练好的弱分类器，如果是分类任务按照权重进行投票，而对于回归任务进行加权，然后再进行预测。boosting和bagging的区别在于是对加权后的数据利用弱分类器依次进行训练。

 



boosting是一族可将弱学习器提升为强学习器的算法，这族算法的工作机制类似：

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



下面描述的算法是最常用的一种boosting算法，叫做AdaBoost，表示自适应boosting。



AdaBoost算法每一轮都要判断当前基学习器是否满足条件，一旦条件不满足，则当前学习器被抛弃，且学习过程停止。

AdaBoost算法中的个体学习器存在着强依赖关系，应用的是串行生成的序列化方法。每一个基生成器的目标，都是为了最小化损失函数。所以，可以说AdaBoost算法注重减小偏差。

由于属于boosting算法族，采用的是加性模型，对每个基学习器的输出结果加权处理，只会得到一个输出预测结果。所以标准的AdaBoost只适用于二分类任务。

 

我们可以看到第一个分类器y1(x)是用相等的权重系数进行训练的。在随后的boosting中，错分的数据权重系数将会增加，正确分类的数据权重系数将会减小。

epsilon表示单个分类器的加权错误率。alpha是分类器的权重，正确的分类器alpha较大。



 

AdaBoost算法的表现如上图所示。每个基础模型包含一个深度为1的决策树，这种决策树依靠线性划分进行分类，决策平面跟其中一个轴平行。上图还展示了集成规模的增加带来的测试准确率变化以及训练和测试集的学习曲线。

 

梯度树提升（Gradient Tree Boosting）是一个boosting算法在损失函数上的泛化。能够用于分类和回归问题。Gradient Boosting采用串行方式构建模型。



每新增一个决策树hm(x)都尽可能的选择是的当前模型Fm-1(x)损失最小的那个：



注意：分类和回归使用的损失函数有所差别。

 

 

Stacking（堆叠）

Stacking是通过一个元分类器或者元回归器来整合多个分类模型或回归模型的集成学习技术。基础模型利用整个训练集做训练，元模型将基础模型的特征作为特征进行训练。

基础模型通常包含不同的学习算法，因此stacking通常是异质集成。算法伪代码如下：





各基础模型的预测结果如下：

Accuracy: 0.91 (+/- 0.01) [KNN]

Accuracy: 0.91 (+/- 0.06) [Random Forest]

Accuracy: 0.92 (+/- 0.03) [Naive Bayes]

Accuracy: 0.95 (+/- 0.03) [Stacking Classifier]

Stacking集成效果如上图所示。分别在K-NN，Random Forest,Naive Bayes做训练和预测，然后将其输出结果作为特征，利用逻辑回归作为元模型进一步训练。如图所示，stacking集成的结果由于每个基础模型，并且没有过拟合。

Stacking被Kaggle竞赛获奖者广泛使用。例如，Otto Group Product分类挑战赛的第一名通过对30个模型做stacking赢得了冠军。他将30个模型的输出作为特征，继续在三个模型中训练，这三个模型XGBoost，Neural Network和Adaboost，最后再加权平均。详见文章(https://www.kaggle.com/c/otto-group-product-classification-challenge/discussion/14335)。

结构如下：



 

 

结合策略



集成学习的第二类模型，为了提高集成的泛化能力，每个基学习器之间不存在很强的依赖性，所以最终预测结果时，需要一定的策略对T个结果进行结合。下面介绍结合策略。

平均法

对数值型输出，最常见的结合策略是使用平均法。

简单平均法
	
加权平均法

	但是对于规模比较大的集成来说，权重参数比较多，较容易导致过拟合。加权平均法未必一定优于简单平均法。
一般而言，在个体学习器性能相差较大时，宜使用加权平均法，而在个体学习器性能相近时，宜使用简单平均法。

这一点在第二个项目中深有体会，该模型有三个损失函数，每个损失函数的性能差别比较大，所以用了加权，在第一个数据集中调好参数以后，在第二个数据集中，效果就不是很好，需要重新进行调参。

投票法

绝对多数投票法

	若某标记得票过半数，则预测为该标记；否则拒绝预测。
	
相对多数投票法

	预测为得票最多的标记。若同时有多个标记获得最高票，则从中随机选取一个。
	
加权投票法
学习法

当训练数据很多时，一种更为强大的结合策略是使用“学习法”，即通过另一个学习器来进行结合。



代码

本文的代码参见： ipython notebook.

 

总结

 

除了本文所提到的集成学习研究之外，集成学习还被广泛应用于利用多种分类器做训练的深度学习模型中。深度学习模型中的分类器可能在架构、超参数以及训练技巧上存在差异，都可以进行集成。

集成学习已经被证明在Kaggle数据科学竞赛中能够获得较好的成绩。

 

推荐阅读

 

Zhi-Hua Zhou, “Ensemble Methods: Foundations and Algorithms”, CRC Press, 2012
	
L. Kuncheva, “Combining Pattern Classifiers: Methods and Algorithms”, Wiley, 2004
	
Kaggle Ensembling Guide
	
Scikit Learn Ensemble Guide
	
S. Rachka, MLxtend library
	
Kaggle Winning Ensemble
 

参考：

https://blog.statsbot.co/ensemble-learning-d1dcd548e936

https://www.jianshu.com/p/0a23d578ac81

 

 

 

 

 

文章目录
集成学习
AdaBoost
代码
Bagging与随机森林
Bagging
随机森林(Random Forest)
结合策略
增加多样性的策略
多样性度量

集成学习
​	之前已经讲过了好几个学习算法，或者说分类器、模型。都能达到一定的分类效果，俗话说的好：三个臭皮匠赛过诸葛亮。集成学习就是想将不同的学习算法集成在一起来工作，以期达到$1+1\ge2$的效果。
​	 集成学习一般的结构为：


​	个体学习期就是之前说过的各种各样的学习器：决策树、线性模型、支持向量机、贝叶斯分类器等。

如果所有的个体学习器都相同，这样的集成学习就是“同质”集成学习，个体学习器被称为“基学习器”或者“基学习算法”
如果所有的个体学习器不同，这样的集成学习就是“异质”集成学习，个体学习器就不被称为“基学习器”了。

​	从上面的图中可以看出，集成学习的重点部分就是在于各个个体徐诶器的结合策略。和足球队一样，大家要取长补短才能达到$1+1\ge2$的效果。
​	比如下图中有三个个体学习器：$h1, h2, h3$，如果结合策略采用最基本的“少数服从多数”的策略的话，根据不同的情况，同样的集成策略会有完全不同的效果。


​	另外还有一个问题就是，到底用多少个学习器会比较合适呢？《机器学习》上给出了一个数学推导。

假设每个基学习器(同质集成学习)的错误率是$\epsilon$，也就是$P(h_i(x)\neq f(x)) = \epsilon$
我们使用T个基学习器进行整合，通过简单的投票规则进行整合，以超过半数的结果为准。 那么集成的错误率就是:

$P(H(x)\neq f(x))=\sum_{k=0}^{T/2}(\begin{matrix}T\\k\end{matrix})(1-\epsilon)^k\epsilon^{T-k} \\ \le exp(-\frac{1}{2}T(1-2\epsilon)^2)$
​		从这个式子看出，如果T越大，错误率就会越低。

但是，这里的一个前提是所有的学习器都是相互独立的。而我们面对同一个问题而训练出来的学习器都是基于相同的数据，或者是通过某种划分策略选出来的训练样本，所以不可能是相互独立的。因此，直接增加基学习器的数量是无法直接达到提高准确率的。

​	学习器的集成方法一般分成两种：

串行的、强依赖的方式：AdaBoost
并行的、低依赖的方式：Bagging与随机森林

AdaBoost
​	书中的AdaBoost算法是基于同质集成学习来进行讨论的。
​	AdaBoost是基于以下的思路进行集成：

依次训练若干个(T个)基学习算法。
为训练集中的每个样本分配相应的权重，这些权重在每一次训练可以视作为一种分布$D$。
在前一个学习器训练完之后，更新样本的权重，使得在第一次学习器中分类失败的样本权重升高，分类正确的样本的权重降低。
每个学习器也存在一个权重$\alpha$，权重$\alpha$会根据每次训练的错误率$\epsilon$来进行计算。最终得到集成输出$H(x)=sign(\sum_{t=1}^T{\alpha_th_t(x)})$。

​	书中给出了训练过程的伪代码：

​	这里解释下其中几行伪代码的来历：


第一行初始化权重，每个样本的权重均为1/m。


第四行是计算训练后学习器的错误率。


第五行是因为，如果训练错误率小于0.5，对于二分类问题比随机猜测还低，就不值得考虑了。语境中的弱学习器也是要高于0.5的正确率的。


第六行是根据错误率来计算当前学习器的权重的。从这个公式来看，错误率越低，相应的权重就会越大。为啥等于这个公式，我没怎么看懂就接受了这个结论，有兴趣的朋友可以去琢磨一下。


第7行是为下一次迭代计算样本权重。按照AdaBoost的思路，下一次的迭代在最好情况下应该可以修复掉前一轮的所有错误样本分类。这里解释一下东西：当$h_t(x)=f(x)$时，$h_t(x)*f(x)=1$，因为作为一个二分类问题，$h(x)$和$f(x)$符号相同的话，肯定是等于1。所以，当$h_t(x)\neq f(x)$时，$h_t(x)f(x)=-1$。所以根据第7行的公式，先不看$Z_t$的话:
$D_{t+1}(x)=D_t(x)*e^{-\alpha_t}, if h_t(x)=f(x) \\D_{t+1}(x)=D_t(x)*e^{\alpha_t}, if h_t(x)\neq f(x)$

接下来是$Z_t$的问题，书中的解释是一个规范化因子，我不是很理解这个东西，结合《机器学习实战》里面的代码实现，我理解这个东西应该是一个归一化的东西，$D_{t+1}$这个权重向量计算出来之后还是一个分布，也就是$\sum_{i=1}^mD_{i} = 1$。所以我这里参考《机器学习实战》一书中的：$Z_t=\sum{D_{i=n}^m{ti}}$
同样，如果有兴趣得知这个推导过程的可以自行研究，我是没太看明白。


把所有的学习器训练完之后，输出还是采用$T$个学习器对新样本都输出，针对每个学习器的输出来乘以权重$\alpha_i$，求和后进行$sign$函数输出。


标准的AdaBoost只适合二分类问题，如要处理其他问题则需要做一些改造。


代码
def stumpClassify(dataMatrix,dimen,threshVal,threshIneq):#just classify the data
    retArray = ones((shape(dataMatrix)[0],1))
    if threshIneq == 'lt':
        retArray[dataMatrix[:,dimen] <= threshVal] = -1.0
    else:
        retArray[dataMatrix[:,dimen] > threshVal] = -1.0
    return retArray
    

def buildStump(dataArr,classLabels,D):
    dataMatrix = mat(dataArr); labelMat = mat(classLabels).T
    m,n = shape(dataMatrix)
    numSteps = 10.0; bestStump = {}; bestClasEst = mat(zeros((m,1)))
    minError = inf #init error sum, to +infinity
    for i in range(n):#loop over all dimensions
        rangeMin = dataMatrix[:,i].min(); rangeMax = dataMatrix[:,i].max();
        stepSize = (rangeMax-rangeMin)/numSteps
        for j in range(-1,int(numSteps)+1):#loop over all range in current dimension
            for inequal in ['lt', 'gt']: #go over less than and greater than
                threshVal = (rangeMin + float(j) * stepSize)
                predictedVals = stumpClassify(dataMatrix,i,threshVal,inequal)#call stump classify with i, j, lessThan
                errArr = mat(ones((m,1)))
                errArr[predictedVals == labelMat] = 0
                weightedError = D.T*errArr  #calc total error multiplied by D
                #print "split: dim %d, thresh %.2f, thresh ineqal: %s, the weighted error is %.3f" % (i, threshVal, inequal, weightedError)
                if weightedError < minError:
                    minError = weightedError
                    bestClasEst = predictedVals.copy()
                    bestStump['dim'] = i
                    bestStump['thresh'] = threshVal
                    bestStump['ineq'] = inequal
    return bestStump,minError,bestClasEst

def adaBoostTrainDS(dataArr,classLabels,numIt=40):
    weakClassArr = []
    m = shape(dataArr)[0]
    D = mat(ones((m,1))/m)   #init D to all equal
    aggClassEst = mat(zeros((m,1)))
    for i in range(numIt):
        bestStump,error,classEst = buildStump(dataArr,classLabels,D)#build Stump
        #print "D:",D.T
        alpha = float(0.5*log((1.0-error)/max(error,1e-16)))#calc alpha, throw in max(error,eps) to account for error=0
        bestStump['alpha'] = alpha  
        weakClassArr.append(bestStump)                  #store Stump Params in Array
        #print "classEst: ",classEst.T
        expon = multiply(-1*alpha*mat(classLabels).T,classEst) #exponent for D calc, getting messy
        D = multiply(D,exp(expon))                              #Calc New D for next iteration
        D = D/D.sum()
        #calc training error of all classifiers, if this is 0 quit for loop early (use break)
        aggClassEst += alpha*classEst
        #print "aggClassEst: ",aggClassEst.T
        aggErrors = multiply(sign(aggClassEst) != mat(classLabels).T,ones((m,1)))
        errorRate = aggErrors.sum()/m
        print "total error: ",errorRate
        if errorRate == 0.0: break
    return weakClassArr,aggClassEst

def adaClassify(datToClass,classifierArr):
    dataMatrix = mat(datToClass)#do stuff similar to last aggClassEst in adaBoostTrainDS
    m = shape(dataMatrix)[0]
    aggClassEst = mat(zeros((m,1)))
    for i in range(len(classifierArr)):
        classEst = stumpClassify(dataMatrix,classifierArr[i]['dim'],\
                                 classifierArr[i]['thresh'],\
                                 classifierArr[i]['ineq'])#call stump classify
        aggClassEst += classifierArr[i]['alpha']*classEst
        print aggClassEst
    return sign(aggClassEst)

Bagging与随机森林
Bagging
​	上面提到的AdaBoost是串行的进行训练，每个学习器都是使用全部的训练集样本数据。这样使得所有的学习器都没法“独立”。因此，Bagging是与AdaBoost不同的思路，是将所有的样本拆分成T份，用每份数据去训练T个学习器，从而降低学习器之间的关联关系。
​	将样本进行拆分的策略也不是简单的进行M/T的划分，而是采用前面介绍过的
​	进行划分来生成T份训练样本集。对T个学习器的决策输出也是采用基本的投票法(分类)或者简单平均法(回归)进行输出：

随机森林(Random Forest)
​	如果使用Bagging集成方法，而基学习器为决策树的话(
)，再增加一点改造就是随机森林了。所以说随机森林是Bagging集成方法上的一个特殊变体。这点点改造就是指在决策树的基学习器训练过程中，每次创建节点选择最优属性进行划分时，引入一个随机变量$k$。如果令$k=d$，就是普通的决策树，而训练多个决策树后进行集成就是普通的Bagging方法。
​	如果令$k=1$，就是在随机选择一个。每个基学习器通过随机选择增加泛化能力。一般的策略是令$k=\log_2d$。
结合策略
​	在对多个个体学习器进行结合输出的时候，这里就涉及到一个决策输出的策略问题，一般来说有如下几种：


平均法，一般用于回归问题。

简单平均法：$H(x)=\frac{1}{T}\sum_{i=1}^T{h_i(x)}$。
加权平均法：$H(x)=\frac{1}{T}\sum_{i=1}^T{w_ih_i(x)}$



投票法，一般用于分类问题。

绝对多数投票法：若某类别超过半数，则预测为该类别。
相对多数投票法：预测类别为票数最多的那个类别。
加权投票法：为每个学习器给一个权值，然后再进行票数计数。



学习法，所有的个体学习器称为初级学习器，结合策略时也使用一个学习器，称之为次级学习器。使用初级学习器的输出样本来训练这个次级学习器，最终来做输出。


增加多样性的策略
​	开篇时讲到的，解决学习器之间的耦合性，让每个学习器尽量的“独立”，是提高集成学习的一个重要手段。

数据样本扰动：使用一些例如自助采样的不同的采样方法，对输入的样本数据进行一些挑选，来解决学习器之间的耦合性。
输入属性扰动：如果样本中的一些属性是冗余的，每个不同的学习器使用不同的属性集合进行训练。
输出表示扰动：手动修改一些标记。
算法参数扰动：也就是改一下算法模型的一些参数，增加一些随机变量进去。

多样性度量
​	那么怎么评价两个算法是否有耦合性呢？
​	首先列出两个算法之间的预测结果列联表：

​	$h_i, h_j$表示两个学习器，其中$a+b+c+d=m$。

不合度量：$dist_{ij} = \frac{b+c}{m}$，也就是两个学习器不同的样本数有多少，值越大，多样性越大。
相关系数：$\rho_{ij}=\frac{ad-bc}{\sqrt{(a+b)(a+c)(c+d)(b+d)}}$，如果值为0，则表示$h_i,h_j$无关。
Q-统计量：$Q_{ij}=\frac{ad-bc}{ad+bc}$。
$\kappa$统计量：$\kappa=\frac{p1-p2}{1-p2}$。其中$p1$为两个分类器取得一致的概率：$p1=\frac{a+d}{m}$，$p2$为两个分类器偶然达成一致的概率，若两个分类器完全一致则$\kappa=1$，若只是偶然一致则$\kappa=0$。

集成学习(ensemble learning)可以说是现在非常火爆的机器学习方法了。它本身不是一个单独的机器学习算法，而是通过构建并结合多个机器学习器来完成学习任务。也就是我们常说的“博采众长”。集成学习可以用于分类问题集成，回归问题集成，特征选取集成，异常点检测集成等等，可以说所有的机器学习领域都可以看到集成学习的身影。本文就对集成学习的原理做一个总结。

1. 集成学习概述

　　　　从下图，我们可以对集成学习的思想做一个概括。对于训练集数据，我们通过训练若干个个体学习器，通过一定的结合策略，就可以最终形成一个强学习器，以达到博采众长的目的。



　　　　也就是说，集成学习有两个主要的问题需要解决，第一是如何得到若干个个体学习器，第二是如何选择一种结合策略，将这些个体学习器集合成一个强学习器。

2. 集成学习之个体学习器

　　　　上一节我们讲到，集成学习的第一个问题就是如何得到若干个个体学习器。这里我们有两种选择。

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

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

3. 集成学习之boosting

　　　　boosting的算法原理我们可以用一张图做一个概括如下：



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

　　　　Boosting系列算法里最著名算法主要有AdaBoost算法和提升树(boosting tree)系列算法。提升树系列算法里面应用最广泛的是梯度提升树(Gradient Boosting Tree)。AdaBoost和提升树算法的原理在后面的文章中会专门来讲。

4. 集成学习之bagging

　　　　Bagging的算法原理和 boosting不同，它的弱学习器之间没有依赖关系，可以并行生成，我们可以用一张图做一个概括如下：



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

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

　　　　随机森林是bagging的一个特化进阶版，所谓的特化是因为随机森林的弱学习器都是决策树。所谓的进阶是随机森林在bagging的样本随机采样基础上，又加上了特征的随机选择，其基本思想没有脱离bagging的范畴。bagging和随机森林算法的原理在后面的文章中会专门来讲。

5. 集成学习之结合策略

　　　　在上面几节里面我们主要关注于学习器，提到了学习器的结合策略但没有细讲，本节就对集成学习之结合策略做一个总结。我们假定我得到的T个弱学习器是

5.1 平均法

　　　　对于数值类的回归预测问题，通常使用的结合策略是平均法，也就是说，对于若干和弱学习器的输出进行平均得到最终的预测输出。

　　　　最简单的平均是算术平均，也就是说最终预测是

　　　　如果每个个体学习器有一个权重

，则最终预测是

　　　　其中

是个体学习器的权重，通常有

5.2 投票法

　　　　对于分类问题的预测，我们通常使用的是投票法。假设我们的预测类别是

,对于任意一个预测样本x，我们的T个弱学习器的预测结果分别是

。

　　　　最简单的投票法是相对多数投票法，也就是我们常说的少数服从多数，也就是T个弱学习器的对样本x的预测结果中，数量最多的类别

为最终的分类类别。如果不止一个类别获得最高票，则随机选择一个做最终类别。

　　　　稍微复杂的投票法是绝对多数投票法，也就是我们常说的要票过半数。在相对多数投票法的基础上，不光要求获得最高票，还要求票过半数。否则会拒绝预测。

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

5.3 学习法

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

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

 

　　　　以上就是集成学习原理的一个总结，后面会分别对Adaboost, 提升树，bagging和随机森林的算法原理做一个总结，敬请期待。