机器学习经典算法详解及Python实现--元算法、AdaBoost

第一节，元算法略述

遇到罕见病例时，医院会组织专家团进行临床会诊共同分析病例以判定结果。如同专家团临床会诊一样，重大决定汇总多个人的意见往往胜过一个人的决定。机器学习中也吸取了‘三个臭皮匠顶个诸葛亮’（实质上是由三个裨将顶个诸葛亮口误演化而来）的思想，这就是元算法的思想。元算法（meta-algorithm）也叫集成方法（ensemble method），通过将其他算法进行组合而形成更优的算法，组合方式包括：不同算法的集成，数据集不同部分采用不同算法分类后的集成或者同一算法在不同设置下的集成。

有了元算法的思想，PAC（(Probably Approximately Correct）学习模型中就有了弱学习算法和强学习算法的等价性问题--即组合任意给定的弱学习算法 ,是否可以将其提升为强学习算法 ? 如果二者等价 ,那么只需将弱学习算法提升为强学习算法就行，而不必寻找很难获得的强学习算法。理论证明，实际上只要弱分类器个数趋向于无穷个时，其组合而成的强分类器的错误率将趋向于零。

弱学习算法---识别错误率小于1/2(即准确率仅比随机猜测略高的学习算法)

强学习算法---识别准确率很高并能在可接受时间内完成的学习算法

介绍几种比较重要的将多个分类器整合为一个分类器的方法--boostrapping方法、bagging方法和Boosting算法。

1）Bootstrapping：

i)重复地从一个样本集合D中采样n个样本，新样本中可能存在重复的值或者丢失原样本集合的一些值。

ii)针对每次采样的子样本集，进行统计学习，获得假设H_i

iii)将若干个假设进行组合，形成最终的假设H_final

iv)将最终的假设用于具体的分类任务

2）Bagging方法

i)训练分类器-从整体样本集合中，抽样n^* < N个样本， 针对抽样的集合训练分类器C_i，抽取方法有很多种

ii)分类器进行投票，最终的结果是分类器投票的优胜结果，每个分类器权重是相等的

3）Boosting

Boosting是一种与Bagging很类似的技术，两者所使用的多个分类器的类型都是一致的。但是在前者当中，不同的分类器是通过串行训练而获得的，每个新分类器都在已训练出的分类器的性能基础上再进行训练，通过集中关注被已有分类器错分的些数据来获得新的分类器。Boosting分类的结果是基于所有分类器的加权求和结果的，分类器权重并不相等，每个权重代表的是其对应分类器在上一轮迭代中的成功度。Boosting算法有很多种，AdaBoost(Adaptive Boost)就是其中最流行的，与SVM分类并称机器学习中最强大的学习算法。

AdaBoost 是一种迭代算法，其核心思想是针对同一个训练集训练M个弱分类器，每个弱分类器赋予不同的权重，然后把这些弱分类器集合起来而构造一个更强的最终分类器，本文就详解AdaBoost算法的详细过程。

第二节，AdaBoost算法

（一）认识AdaBoost

AdaBoost算法有AdaBoost.M1和AdaBoost.M2两种算法，AdaBoost.M1是我们通常所说的Discrete AdaBoost，而AdaBoost.M2是M1的泛化形式。关于AdaBoost算法的一个结论是:当弱分类器算法使用简单的分类方法时,boosting的效果明显地统一地比bagging要好.当弱分类器算法使用C4.5时,boosting比bagging较好,但是没有前者明显。后来又有学者提出了解决多标签问题的AdaBoost.MH和AdaBoost.MR算法,其中AdaBoost.MH算法的一种形式又被称为Real Boost算法---弱分类器输出一个可能度，该值的范围是整个R, 和与之相应的权值调整，强分类器生成的AdaBoost算法。

事实上:Discrete AdaBoost是指,弱分类器的输出值限定在{-