机器学习：集成学习之AdaBoost算法

一、集成学习

集成学习（Ensemble Learning），简单来说，就是先通过一定的规则生成多个学习器，再采用某种集成策略进行组合，最后综合判断输出最终结果。一般而言，通常所说的集成学习中的多个学习器都是同质的“弱学习器”。基于该弱学习器，通过样本集扰动、输入特征扰动、输出表示扰动、算法参数扰动等方式生成多个学习器，进行集成后获得一个精度较好的“强学习器”。

相比单个弱学习器，集成学习方法通常在准确率，对噪点的抗干扰性更优，但是效率上要差一些，所以有时候也用一些相对较“强”的学习器到集成算法当中，以提高算法效率。最常见的集成学习算法有两种，Boost和Bagging，先简单介绍一下Bagging的算法思路，然后重点讲一下Boost算法中具有代表性的AdaBoost，Bagging的算法流程图如下：

从上图可见Bagging算法那中的弱学习器之间没有依赖关系，可以并行生成Bagging的个体弱学习器的训练集是通过随机采样得到的。通过T次的随机采样，就可以得到T个采样集，对于这T个采样集可以分别独立的训练出T个弱学习器，再对这T个弱学习器通过集合策略来得到最终的强学习器。

二、AdaBoost集成学习算法

2.1 算法介绍

AdaBoost是一种迭代算法，核心思想也就是集成学习的思想，针对同一个训练集训练不同的弱分类器，然后把这些弱分类器集合起来，构成一个更强的最终分类器（强分类器）。AdaBoost是英文"Adaptive Boosting"（自适应增强）的缩写。AdaBoost方法的自适应在于：前一个分类器分错的样本会被用来训练下一个分类器。AdaBoost方法对于噪声数据和异常数据很敏感，相对于大多数其它学习算法而言，不会很容易出现过拟合现象。AdaBoost方法中使用的分类器可能很弱（比如出现很大错误率），但只要它的分类效果比随机好一点（比如两类问题分类错误率略小于0.5），就能够改善最终得到的模型。而错误率高于随机分类器的弱分类器也是有用的，因为在最终得到的多个分类器的线性组合中，可以给它们赋予负系数，同样也能提升分类效果。以下是AdaBoost算法流程示意图：

跟Bagging不同的是，AdaBoost中的弱学习器之间不是“并行”的，而是“线性”的。即在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它被某个分类器选入训练集的概率。如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。通过这样的方式，AdaBoost方法能“聚焦于”那些较难分的样本上。在具体实现上，最初令每个样本的权重都相等，对于第k次迭代操作，就根据这些权重来选取样本点，进而训练分类器C

跟Bagging不同的是，AdaBoost中的弱学习器之间不是“并行”的，而是“线性”的。即在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率。每一个训练样本都被赋予一个权重，表明它被某个分类器选入训练集的概率。如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它被选中的概率就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。通过这样的方式，AdaBoost方法能“聚焦于”那些较难分的样本上。在具体实现上，最初令每个样本的权重都相等，对于第k次迭代操作，就根据这些权重来选取样本点，进而训练分类器Ck。然后就根据这个分类器，来提高被它分错的的样本的权重，并降低被正确分类的样本权重。然后，权重更新过的样本集被用于训练下一个分类器Ck+1。整个训练过程如此迭代地进行下去。

2.2 算法流程

AdaBoost的算法流程如下：

（1）有样本集，y值为-1和1，是个二分类的样本集合：

（2）初始化每个样本的权重：

（3）For m in 1,2,…M，进行M次迭代：

（a）选择分类器Km(x)，使损失函数最小，简单来讲，就是选定一个弱分类器，使得分类错误的样本点的权重之和最小：

（b）计算am，am代表当前分类器在最终的强分类器中的权重：

（c）集成到分类器，最终的强分类器由每次迭代的弱分类器和对应的权重求和得到：

（d）更新权重wi，并归一化：

2.3 算法推导

2.4 算法示例

2.5 多分类算法介绍

由于AdaBoost的算法定义上，决定了AdaBoost算法只适用于二分类算法，那么AdaBoost算法应该如何进行多分类呢？

AdaBoost二分类算法扩展

一、将训练样本集中的某一类当成一类，其他的所有类当成另外一类，这样多分类问题就退化成了多次二分类问题；

二、多分类中所有类，俩俩生成分类器，最后根据投票决定所在类。

SAMME

SAMME算法基于AdaBoost算法思想，不同的点在于计算分类器的权重计算公式：

三、案例实验

3.1 分类案例

使用AdaBoost算法，预测学生成绩：

l 每个学生具有15个属性，如性别、年龄及家庭、双亲教育等；

l 学生成绩取值为0-20的整数；

l 样本数800+；

样本数据截图如下：

算法流程：

数据清洗

1. 离散特征升维，如性别（原始数据为F/M），我们将性别拆分为2维特征，即isMale和isFemale，若原始特征是F，则拆分后对应的两维特征分别为：(isMale-0，isFemale-1)

2. 连续特征归一化，如自由支配时间在0-5，则对其除以5.0，将其归一化到[0， 1]这个区间；

模型调优

使用sklearn库的实现，尝试使用决策树回归方法、最小梯度下降回归方法，结合AdaBoost增强学习，寻求最佳模型

最终实验选用的是决策树+AdaBoost的模型：

1. 决策树max_depth=4
2. AdaBoost弱学习器n_estimators=100

通过多次调参验证，上述参数是实验最终结果最优的参数。

3.2 分类器类别对结果的影响

如下图，选取了三种“弱”分类器进行AdaBoost算法，分别是决策树、朴素贝叶斯和随机森林，可以看到三种弱分类器在收敛速度和准确度的差异还是很明显：

1. 决策树的准确度、收敛速度上都最差，而且迭代过程中还有抖动；

2. 随机森立的收敛很稳定，收敛速度也比较快；

3. 朴素贝叶斯分类器本身是相对较“强”的分类器，所以它很快就收敛了，而且准确度也很高；

3.3 分类器强弱对结果的影响

如下图，采用决策树作为基础“弱”分类器，然后分别设置决策树的深度为1、2、4、8，来看分类器本身的效果，以及应用到AdaBoost算法当中的效果：

1. 随着决策树层数的增加，决策树本身的分类准确度越来越好（图中横线）；

2. 但是应用到AdaBoost中，效果最好的决策树层数为2和4的弱分类器，层数8的分类器效果反倒不够理想，这说明，在实际应用中，不是基础分类器越“强”越好，还是要根据实际样本集的训练效果来决定；

3.4 学习率对分类结果的影响

设置了不同的学习率来观察AdaBoost算法的结果，结论是，最好的学习率是0.4和0.8，说明学习率并不是越小越好，还是要根据实际的样本训练结果以及效率还选取合适的学习率。

参考资料

https://baike.baidu.com/item/%E9%9B%86%E6%88%90%E5%AD%A6%E4%B9%A0/3440721?fr=aladdin

https://en.wikipedia.org/wiki/Ensemble_learning#Ensemble_theory

http://www.cnblogs.com/jasonfreak/p/5657196.html

https://scikit-learn.org/stable/modules/ensemble.html#adaboost

https://zhuanlan.zhihu.com/p/27126737

https://matplotlib.org/api/_as_gen/matplotlib.pyplot.plot.html

https://www.cnblogs.com/litthorse/p/9332370.html