- 转载请注明作者和出处：http://blog.csdn.net/u011475210
- 代码地址：https://github.com/WordZzzz/ML/tree/master/Ch07
- 操作系统：WINDOWS 10
- 软件版本：python-3.6.2-amd64
- 编 者：WordZzzz
前言
终于，分类问题要收尾了。
当做重要决定时，大家肯定是到处取经，集四海八荒之智后，再做出自己的决定。机器学习也是如此，元算法（meta-algorithm）应运而生。元算法是对其他算法进行组合的一种方式。接下来我们将集中关注一个称作AdaBoost的最流行的元算法，该算法可以说是最好的监督学习的方法（巨人说的），所以它也是机器学习工具箱中最强有力的工具之一。
本系列博客，首先讨论不同分类器的集成方法，然后主要关注boosting方法及其代表分类器AdaBoost；接下来，我们会建立一个单层决策树（decision stump）分类器（实际上，它是一个单节点的决策树）；最后，AdaBoost算法将应用在上述单层决策树分类器之上，并在之前的病马数据集上应用AdaBoost分类器，以此来了解该算法是入个迅速超越其他分类器的。
本节，我们先来介绍一些概念性的东西。
基于数据集多重抽样的分类器
我们自然可以将前面学习的五种不同的分类方法组合起来，而这种组合结果则被称为集成方法（ensemble method）或者元算法（meta-algorithm）。只用集成方法时会有多种形式：可以是多种不同的算法的集成，可以是同一算法在不同设置下的集成，也可以是数据集不同部分分配给不同分类器的集成。接下来，我们将介绍基于同一种分类器多个不同实例的两种计算方法：bagging和boosting。
bagging
自举汇聚法（bootstrap aggregating），也称为bagging方法，实在从原始数据集选择S次之后得到S个新数据集的一种技术。新旧数据集大小相等，每个数据集都是通过在原始数据集中随机选择一个样本来进行替换而得到的（放回的随机抽样），也就是可以多次选择同一个样本。这一性质就允许新数据集中可以有重复的值，而原始数据集的某些值在新集合中则不再出现。
S个数据集建好之后，将某个学习算法分别作用于每个数据集就得到了S个分类器。当我们要对新数据进行分类时，就可以应用这S个分类器进行分类了（当然，还是多数表决的原则）。
当然，还有一些更先进的bagging方法，比如随机森林（random forest），在此就不多做介绍了，我们主要的精力，还是放在与bagging类似的集成分类器方法boosting。
boosting
boosting是一种与bagging很类似的技术。不论是在boosting还是bagging当中，所使用的多个分类器的类型都是一致的。但是boosting算法中，不同的分类器是通过串行训练而得到的，每个新分类器都根据已训练出的分类器的性能来进行训练。boosting通过集中关注已有分类器错分的那些数据来获得新的分类器。
由于boosting分类的结果是基于所有分类器的加权求和的结果，因此boosting与bagging不太一样。bagging中分类器的权重是相等的，而boosting中分类器的权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。
基本要点就这些了，下面介绍boosting中一个最流行的版本AdaBoost。
AdaBoost的一般流程：
- 收集数据：可以使用任意方法。
- 准备数据：依赖于所使用的弱分类器类型，本章使用的是单层决策树，这种分类器可以处理任何数据类型。当然也可以使用任意分类器作为弱分类器，前面介绍的五种分类器都可以充当弱分类器。作为弱分类器，简单分类器的效果更好。
- 分析数据：可以使用任意方法。
- 训练算法：AdaBoost的大部分时间都用在训练上，分类器将多次在同一数据集上训练弱分类器。
- 测试算法：计算分类的错误率；
- 使用算法：同SVM一样，AdaBoost预测两个类别中的一个。如果想把它应用到多个类别的场合，那么就要像多类SVM中的做法一样对AdaBoost进行修改。
基于错误提升分类器的性能
能否使用弱分类器和多个实例来构建一个强分类器，这是一个非常有趣的理论问题。这里的“弱”意味着分类器的性能比随机猜测要略好，但是也不会好太多。也就是说，在二分类情况下弱分类器的错误率会高于50%，而“强“分类器的错误率将会低很多。AdaBoost算法就是基于上述理论的。
AdaBoost是adaptive boosting（自适应boosting）的缩写，其运行过程如下：训练数据中的每个样本，并赋予其一个权重，这些权重构成了向量D。一开始，这些权重都初始化成相等值。首先在训练数据上训练出一个弱分类器并计算该分类器的错误率，然后再同一数据集上再次训练弱分类器。在分类器的第二次训练当中，将会重新调整每个样本的权重，其中第一次分对的样本的权重将会降低，而第一次分错的样本的权重将会提高。为了从所有弱分类器中得到最终的分类结果，AdaBoost为每个分类器都分配了一个权重值alpha，这些alpha值是基于每个弱分类器的错误率进行计算的。其中，错误率ε的定义为：
$$
\epsilon = \frac{未正确分类的样本数目}{所有样本数目}
$$
而alpha的计算公式如下：
$$
\alpha = \frac{1}{2} ln (\frac{1-\epsilon}{\epsilon})
$$
AdaBoost算法的流程如图所示。
左边是数据集，中间直方图的不同宽度表示每个样例上的不同权重。在经过一个分类器之后，加权的预测结果会通过三角形中的alpha值进行加权。每个三角形中输出的甲醛结果在圆形中求和，从而得到最终的输出结果。
计算出alpha的值之后，可以对权重向量D进行更新，以使得那些正确分类的样本的权重降低而错分样本的权重升高。D的计算方法如下。
如果某个样本被正确分类，那么该样本的权重更改为：
$$
D_i^{(t+1)} = \frac{D_i^{(t)}e^{-\alpha}}{Sum(D)})
$$
如果某个样本被错误分类，那么该样本的权重更改为：
$$
D_i^{(t+1)} = \frac{D_i^{(t)}e^{\alpha}}{Sum(D)})
$$
计算出来D之后，AdaBoost又开始进入下一轮迭代。AdaBoost算法会不断地重复训练和调整权重的过程，直到训练错误率为0或者弱分类器的数目达到用户的指定值为止。
下一篇博文我们来实现AdaBoost。
系列教程持续发布中，欢迎订阅、关注、收藏、评论、点赞哦～～(￣▽￣～)～
完的汪(∪｡∪)｡｡｡zzz