集成学习（ensemble learning）

集成学习（ensemble learning）通过构建并结合多个学习器来完成学习任务。也就是说，集成学习可以通过若干个“弱学习器”（weak learner）进行结合，常可获得比单一学习器性能优越的“强学习器”。
根据个体学习器的生成方式，目前集成学习方法大致可分成两类，即个体学习器间存在强依赖关系，必须串行生成的序列化方法；以及个体学习器间不存在强依赖关系，可同时生成的并行化方法；前者的代表是Boosting，后者的代表是Bagging和随机森林（Random Forest）。

I. Boosting
Boosting是一种可将弱学习器提升为强学习器的算法。这种算法的工作机制是：
a. 从初始训练集训练出一个基学习器
b. 根据基学习器调整训练样本分布，使得先前基学习器做错的训练样本获得更多的关注
c. 基于调整后的样本分布来训练下一个基学习器
d. 如此重复，直至基学习器数目达到事先指定的值T
e. 最终将这T个学习器加权结合

Boosting算法中最著名的代表是AdaBoost（additive model），
即基学习器的线性组合
H(x)=∑Tt=1atht(x)
来最小化指数损失函数（exponential loss function）
lexp(H|D)=Ex−D[e−f(x)H(x)]。

完整的AdaBoost算法如下：

算法步骤：
步骤1. 首先，初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权重：1/m。
D1=(w11,w12,...,w1i,w1m),w1i=1/m,i=1,2,...,m
步骤2. 进行多轮迭代，用m = 1,2, …, T表示迭代的第多少轮
a. 使用具有权值分布Dt的训练数据集学习，得到基本分类器：
ht(x)−>{−1,+1}
b. 计算Gm(x)在训练数据集上的分类误差率
ϵ=Px−Dt(ht(x)≠f(x))=∑mi=1wtiI(ht(xi)≠yi)
由上述式子可知，ht(x)在训练数据集上的误差率ϵ就是被ht(x)误分类样本的权值之和。
c. 计算ht(x)的系数，αt表示ht(x)在最终分类器中的重要程度（目的：得到基本分类器在最终分类器中所占的权重）：
αt=1/2∗ln1−ϵtϵ
由上述式子可知，ϵt≤1/2时，αt≥0，且αt随着ϵt的减小而增大，意味着分类误差率越小的基本分类器在最终分类器中的作用越大。
d. 更新训练数据集的权值分布（目的：得到样本的新的权值分布），用于下一轮迭代
Dt+1=(wt+1,1,wt+1,2,...,wt+1,iwt+1,m),wt+1,i=wtiZtexp(−αtyiht(xi)),i=1,2,...,m
使得被基本分类器ht(x)误分类样本的权值增大，而被正确分类样本的权值减小。就这样，通过这样的方式，AdaBoost方法能“聚焦于”那些较难分的样本上。
其中，Zm是规范化因子，使得Dm+1成为一个概率分布：
Zm=∑mi=1wtiexp(−αtyiht(xi))
步骤3. 组合各个弱分类器
f(x)=∑Tt=1αtht(x)
从而得到最终分类器，如下：
H(x)=sign(f(x))=sign(∑Tt=1αtht(x))

参考资料：
1. 机器学习（周志华）
2. http://www.360doc.com/content/17/0710/10/45249375_670248166.shtml