2000字总结3种项目和面试中常用的集成学习算法

1 概念

俗话说，“三个臭皮匠，顶个诸葛亮”，多个比较弱的人若能有一种方法集中利用他们的智慧，也可以达到比较好的效果，这就是集成学习的思想。

集成学习是指通过构建并结合多个学习器来完成学习任务的一种机器学习方法

其结构如下图所示：

根据个体学习器的特点，可以分为以下两类：

• 同类型（如全是神经网络）的个体学习器，又称基学习器，构成同质集成
• 不同类型的个体学习器，又称组件学习器，构成异质集成

一般而言，个体学习器是所谓的弱学习器，即泛化能力略优于随机猜测的学习器。使用弱学习器进行集成学习已经可以获得足够好的泛化性能。当然也可以使用比较强的学习器。

理想的个体学习器应该具有好而不同的特点，即：

• 好：有一定的准确性
• 不同：个体学习器之间应该具有差异

2 原理

为什么使用多个弱学习器可以集成为一个强学习器呢？假设二分问题的最终结果是投票而来——即超过一半的弱学习器输出的结果为最终结果。即：

上式中H(x)为集成后的学习器，

为第i个弱学习器，sign为理想激活函数。

假设每个弱学习器的错误率为p，则集成的错误率为：(f(x)为真实的标记函数)

可以证明上式在 p<0.5 的条件下，随着T的增大，函数值指数级趋向于0，由此就得到了更强的学习器。

但是上式依赖于一个关键的条件：

基学习器的误差是相互独立的。

但是该条件在现实任务中是不成立的，因为这些基学习器都是围绕一个问题在同一个训练集上训练出来的。

所以，如何寻找好而不同的个体学习器，是集成学习要研究的重点。

3 常见模型

一般而言，要取得好而不同的学习器，有以下两大类：

• 个体学习器之间存在着依赖关系，必须串行的生成个体学习器。典型方法例如 AdaBoost。
• 个体学习器之间不存在强依赖关系，可以并行的生成。典型方法例如bagging、随机森林。

3.1 AdaBoost

AdaBoost是Boosting一族的代表算法。

Boost的含义是增强，Boosting方法就是从弱学习算法出发，在前一个学习器的基础上反复学习，得到一系列弱分类器，然后组合弱分类器，得到一个强分类器。Boosting方法在学习过程中通过改变训练数据的权值分布，针对不同的数据分布调用弱学习算法得到一系列弱分类器。

根据定义可以知道：

• boost是迭代算法，是通过前一个弱学习器进行优化，改变训练数据分布，从而得到下一个弱学习器，最终将所有的学习器进行组合的算法。
• boosting算法要求基学习器可以对特定的数据分布进行学习，一般以下两种方法:
• 采用重赋值法，根据样本分布对不同样本数据进行赋值，这要求基学习器可以对带权数据进行学习
• 采用重采样法：根据样本分布对原训练集进行重新采样以满足某个分布，进行下一轮次的学习。

AdaBoost最终的模型是对于基学习器的线性组合，即：

而该算法的目标是最小化指数损失函数：

其中，D为样本分布，f(x)为真实标记函数，H(x)为集成输出函数，E代表期望。

可以证明，当损失函数最小时，分类错误率也将最小化。

利用求导技巧最小化上式损失函数，可以得到该算法的具体流程：

 1# 算法输入：
 2# 训练集M={(x1,y1),(x2,y2)......(xm,ym)}
 3# 基学习算法B，训练轮数T
 4# 算法输出：
 5# 集成之后的学习器
 6def ensembleLearning(M,B,T):
 7    # 初始分布D1，即为均匀分布
 8    D1(x)=1/m
 9    # 循环训练T轮
10    for t in range(0,T):
11        # 训练得到学习器ht
12        ht(x)=B(D,Dt)
13        # 计算该学习器的错误率
14        pt = P(ht(x)!=f(x))
15        # 如果该学习器比随机性能还差，就停止算法
16        if pt < 0.5:
17              break
18        # 更新第t轮学习器的权重和下一轮的数据分布
19        at = 0.5 ln((1-pt)/pt) 
20        Dt+1 = refresh(Dt)
21return H(x)=sum(at*ht)

可见，迭代过程主要更新两个指标，分别是第 t 轮的学习器权重

和下一轮的数据分布

，他们的更新公式都是由最小化损失函数得来的:

其中

真实标记函数，

为第t、t+1轮的数据分布，

为到第t轮为止的集成算法。

AdaBoost主要关注减低偏差，而非方差，故可以通过很弱的弱学习器构建较强的集成学习器。

3.2 bagging

bagging属于无依赖型并行算法，它主要通过变换不同的数据集来得到不同的算法，然后通过简单投票法得到最后的结果。

如何变换不同数据集呢？可以采用之前介绍过的自助采样法：

自助法：假设有m个数据的数据集，每次有放回的从其中抽取一个样本，执行m次，最终大概有36.8%的数据未被抽取到，当做测试集，其余当做训练集。

• 优点：在数据集较小时用处较大，划分出的多个数据集有利于集成学习
• 缺点：改变了原数据样本的分布，会引入偏差

可以将上述方法重复T次，得到T个不同的数据集，便可以训练得到T个不同的弱学习器。

然后这多个弱学习器，通过简单投票，票多的结果胜出的方法，集成得到最终的强学习器。

bagging算法主要是降低方差，故它在一些易受到扰动的基学习器上使用效果更佳明显——例如神经网络，非剪枝决策树等。

3.3 随机森林

和bagging不同，随机森林采用另一种方法来达到好而不同的效果。随机森林是在决策树的基础上进行的。

• 在普通决策树的构建过程中，节点的划分是在剩余属性集合中找一个最优的属性集合——信息增益最大
• 在随机森林的构建过程中，现在属性集合中先随机选出一个容量为k(推荐为log(d)，其中d为属性总数)的属性子集，在从中找到最好的分类属性。

显然，k=d时，退化为普通决策树，k=1时，相当于随机划分。

随机森林在很多现实任务中都表现出了强大的泛化能力。

4 查看更多

陈浩然，北大在读，个人网站：chrer.com，里面记录了机器学习、深度学习的系统学习笔记，欢迎大家访问，感谢她的分享！