机器学习经典算法详解及Python实现--元算法、AdaBoost
第1节，元算法略述
遇到罕见病例时，医院会组织专家团进行临床会诊共同分析病例以判定结果。犹如专家团临床会诊1样，重大决定汇总多个人的意见常常胜过1个人的决定。机器学习中也吸取了‘3个臭皮匠顶个诸葛亮’（实质上是由3个裨将顶个诸葛亮口误演变而来）的思想，这就是元算法的思想。元算法（meta-algorithm）也叫集成方法（ensemble method），通过将其他算法进行组合而构成更优的算法，组合方式包括：不同算法的集成，数据集不同部份采取不同算法分类后的集成或同1算法在不同设置下的集成。
有了元算法的思想，PAC（(Probably Approximately Correct）学习模型中就有了弱学习算法和强学习算法的等价性问题--即组合任意给定的弱学习算法 ,是不是可以将其提升为强学习算法 ? 如果2者等价 ,那末只需将弱学习算法提升为强学习算法就行，而没必要寻觅很难取得的强学习算法。理论证明，实际上只要弱分类器个数趋向于无穷个时，其组合而成的强分类器的毛病率将趋向于零。
弱学习算法---辨认毛病率小于1/2(即准确率仅比随机猜想略高的学习算法)
强学习算法---辨认准确率很高并能在可接受时间内完成的学习算法
介绍几种比较重要的将多个分类器整合为1个分类器的方法--boostrapping方法、bagging方法和Boosting算法。
1）Bootstrapping：
i)重复地从1个样本集合D中采样n个样本，新样本中可能存在重复的值或丢失原样本集合的1些值。
ii)针对每次采样的子样本集，进行统计学习，取得假定Hi
iii)将若干个假定进行组合，构成终究的假定Hfinal
iv)将终究的假定用于具体的分类任务
2）Bagging方法
i)训练分类器-从整体样本集合中，抽样n* < N个样本， 针对抽样的集合训练分类器Ci，抽取方法有很多种
ii)分类器进行投票，终究的结果是分类器投票的优越结果，每一个分类器权重是相等的
3）Boosting
Boosting是1种与Bagging很类似的技术，二者所使用的多个分类器的类型都是1致的。但是在前者当中，不同的分类器是通过串行训练而取得的，每一个新分类器都在已训练出的分类器的性能基础上再进行训练，通过集中关注被已有分类器错分的些数据来取得新的分类器。Boosting分类的结果是基于所有分类器的加权求和结果的，分类器权重其实不相等，每一个权重代表的是其对应分类器在上1轮迭代中的成功度。Boosting算法有很多种，AdaBoost(Adaptive Boost)就是其中最流行的，与SVM分类并称机器学习中最强大的学习算法。
AdaBoost 是1种迭代算法，其核心思想是针对同1个训练集训练M个弱分类器，每一个弱分类器赋予不同的权重，然后把这些弱分类器集合起来而构造1个更强的终究分类器，本文就详解AdaBoost算法的详细进程。
第2节，AdaBoost算法
（1）认识AdaBoost
AdaBoost算法有AdaBoost.M1和AdaBoost.M2两种算法，AdaBoost.M1是我们通常所说的Discrete AdaBoost，而AdaBoost.M2是M1的泛化情势。关于AdaBoost算法的1个结论是:当弱分类器算法使用简单的分类方法时,boosting的效果明显地统1地比bagging要好.当弱分类器算法使用C4.5时,boosting比bagging较好,但是没有前者明显。后来又有学者提出了解决多标签问题的AdaBoost.MH和AdaBoost.MR算法,其中AdaBoost.MH算法的1种情势又被称为Real Boost算法---弱分类器输出1个可能度，该值的范围是全部R, 和与之相应的权值调剂，强分类器生成的AdaBoost算法。
事实上:Discrete AdaBoost是指,弱分类器的输出值限定在{⑴,+1}，和与之相应的权值调剂，强分类器生成的AdaBoost算法。本文就详解该2分类的AdaBoost算法，其他请参考‘Adaboost原理、算法和利用’。
假定是2值分类问题，X表示样本空间，Y={⑴,+1}表示样本分类。令S={(Xi,yi)|i=1,2,…,m}为样本训练集，其中Xi∈X，yi∈Y。再次重申，我们假定统计样本的散布式是均匀散布的，如此在两分类分类中（种别⑴或1）可以将阈值设为0。实际训练数据中，样本常常是不均衡的，需要算法来选择最优阈值（如ROC曲线）。AdaBoost算法就是学习出1个分类器YM(x) --由M个弱分类器构成。在进行分类的时候，将新的数据点x代入，如果YM(x)小于0则将x的种别赋为⑴，如果YM(x)大于0则将x的种别赋为1。均匀散布中阈值就是0，非均衡散布则还要根据ROC曲线等方法肯定1个分类的最优阈值。
基本进程：针对不同的训练集训练1个个基本分类器（弱分类器），然后集成而构成1个更强的终究的分类器（强分类器）。不同的训练集是通过调剂训练数据中每一个样本对应的权重实现的。每次训练后根据此次训练集中的每一个样本是不是被分类正确和上次的整体分类的准确率，来肯定每一个样本的权值。将修改权值的新数据送给下层分类器进行训练，然后将每次训练得到的分类器融会起来，作为最后的决策分类器。
每一个弱分类器可以是机器学习算法中的任何1个，如logistic回归，SVM，决策树等。
Adaboost有很多优点:
1)adaboost是1种有很高精度的分类器
2)可使用各种方法构建子分类器，adaboost算法提供的是框架
3)当使用简单分类器时，计算出的结果是可以理解的，而且弱分类器构造极为简单
4)简单，不用做特点挑选
5)不用担心overfitting
（2）AdaBoost算法进程
完全的adaboost算法以下（训练样本样本总数是N个，M是迭代停止后（积累毛病率为0或到达最大迭代次数）得到弱分类器数目）。
给定1个训练数据集T={(x1,y1), (x2,y2)…(xN,yN)}，其中实例
，而实例空间
，yi属于标记集合{⑴,+1}，Adaboost的目的就是从训练数据中学习1系列弱分类器或基本分类器，然后将这些弱分类器组合成1个强分类器，流程以下：
最开始的时候，每一个样本对应的权重是相同的（1/m），在此样本散布下训练出1个基本分类器h1(x)。对h1(x)错分的样本，则增加其对应样本的权重；而对正确分类的样本，则下降其权重。这样可使得错分的样本突出出来，并得到1个新的样本散布。同时，根据错分的情况赋予h1(x)1个权重，表示该基本分类器的重要程度，错分得越少权重越大。在新的样本散布下，再次对基本分类器进行训练，得到基本分类器h2(x)及其权重。顺次类推，经过M次这样的循环，就得到了M个基本分类器及对应权重。最后把这M个基本分类器按1定权重累加起来，就得到了终究所期望的强分类器YM(x)。迭代的停止条件就是到达了训练样本累加分类毛病率为0.0或到达了最大迭代次数。
（i）初始化训练数据的权值散布，每个训练样本最开始时被赋予相同的权值：1/N。
（ii）进行多轮迭代，迭代的停止条件就是到达了训练样本累加分类毛病率为0.0或到达了最大迭代次数L。用m = 1,2, ..., M表示迭代的第多少轮，也就是得到了多少个弱分类器，M<=L。
a.使用具有权值散布Dm的训练数据集学习，得到基本分类器：
b.计算Gm(x)在训练数据集上的分类误差率
由上述式子可知，Gm(x)在训练数据集上的误差率em就是被弱分类器Gm(x)分类毛病样本的权值之和。就是在这里，训练样本权重因子产生了作用，所有的1切都指向了当前弱分类器的误差。提高分类毛病样本的权值，下1个分类器学习中其“地位”就提高了（以单层决策树为例，由于每次都要得到当前训练样本中em最小的决策桩）；同时若这次的弱分类器再次分错了这些点，那末其毛病率em也就更大，终究致使这个分类器在全部混合分类器的权值am变低---让优秀的分类器占整体的权值更高，而挫的分类器权值更低。
c. 计算Gm(x)的权值系数，am表示Gm(x)在终究分类器中的重要程度（目的：得到基本分类器在终究分类器中所占的权重）：
可知:em <= 1/2时(两分类Adaboost算法em不可能大于1/2)，am >= 0;am随着em的减小而增大，意味着分类误差率越小的本分类器在终究分类器中的作用越大。
另外，若某1个若分类器分类毛病率为0计算am将会产生除数为0的异常，这属于边界处理。此时可以根据数据集的具体情况设定毛病率为1个很小的数值，例如1e⑴6。视察样本权重更新就能够知道:没有错分，所有样本的权重就不会进1步调剂,样本权重相当于没有改变。固然，该弱分类器权重alpha将较大，但是由于算法其实不因此停止，如果后面还有其他弱分类器也能到达训练毛病率为0，也一样会有较大的权重，从而避免由单个弱分类器完全决定强分类器的情况。固然，如果第1个弱分类器毛病率就为0，那末全部分类就完成了，它有再大的权重alpha也无妨。采取下述修正方案：
alpha = float(0.5*log((1.0-error)/max(error,1e⑴6) ))
d. 更新训练数据集的权值散布（目的：得到样本的新的权值散布），用于下1轮迭代。这使得被基本分类器Gm(x)分类毛病的样本的权值增大，而被正确分类样本的权值减小。通过这样的方式，AdaBoost算法提高了较难分类的样本的‘地位’。
Zm的意义在于让权重因子之和为1.0，使向量D是1个几率散布向量。其定义是
（iii） 组合各个弱分类器得到终究分类器，以下：
（3）Python实现单决策树AdaBoost算法
单层决策树（decision stump，也叫决策树桩）是1种简单的决策树，决策树中只有1个树桩，也就是仅基于样本单个特点来做决策分类。单层决策树是AdaBoost算法中最流行的弱分类器。
AdaBoost把多个不同的决策树用1种非随机的方式组合起来，表现出惊人的性能。第1，把决策树的准确率大大提高，可以与SVM媲美。第2，速度快，且基本不用调参数。第3，几近不Overfitting。本节就以多个单层决策树做基本分类器实现AdaBoost算法，值得注意的是每一个基本分类器单层决策树决策用分类使用的特点都是在样本N个特点中做最优选择的（也就是说在分类特点选择这个层面，每一个单层决策树彼此之间是完全独立的，可能若干个单层决策树都是基于同1个样本特点），而非样本特点的串连。
该版本的AdaBoost分类算法包括decisionstump.py（decisionstump对象，其属性是包括dim, thresh, ineqtype3个域的决策树桩，方法有buildstump()、stumpClassify()等。），adaboost.py, object_json.py, test.py，其中adaboot.py实现分类算法，对象adaBoost包括属性分类器词典adaboostClassifierDict和adaboost train&classify方法等。为了存储和传输更少的字节数，也能够在adaboost模块增加1个新类adaboostClassifier只用来存储分类词典和分类算法（本包中没有这么做）。test模块则包括了1个使用adaboost分类器进行分类的示例。
由于adaboost算法每个基本分类器都可以采取任何1种分类算法，因此通用的方案是采取dict来存储学习到的AdaBoost分类器，结构以下图：
adaboost对象可以针对决策树、SVM等定义私有的各种弱分类算法，train和classifier方法则会根据当前的弱分类器类型创建响应的弱分类器实例并调用私有弱分类trainclassifer方法完成trainclassify。需要记住的是，adaboost train方法创建的弱分类器对象只用来调用相应的弱分类器方法，而该弱分类实例所有的属性则存储在adaboostClassifierDict中，这样可以减少弱分类器实例数目。另外，方法jsonDumpsTransfer()和jsonLoadTransfer()则要根据adaboostClassifierDict中支持的弱分类器类型删除创建相应实例，从而支持JSON存储和解析。
采取上图中的分类器存储方案及相应的分类函数，AdaBoost支持每个基本分类器在决策树、贝叶斯、SVM等监督学习算法中做最优选择。分类其中adaboostClassifierDict中的classifierType用户可以自己指定，从而在上述分类存储结构的基础上做1些利于分类器程序编写的调剂。我实现的单层决策树Adaboost指定classifierType为desicionstump，即基本分类器采取desicionstump，每个弱分类器都是1个DS对象。所以存储结构可以调剂为下图所示（利于分类函数实现）：
通过调剂adaboost算法弱分类器的数目，会得到分类毛病率不同的adaboost分类器。测试证明，numIt=50时毛病率最低。
AdaBoost分类算法学习包的下载地址是：
machine learning adaboost
（4）Adaboost利用
由于adaboost算法是1种实现简单、利用也很简单的算法，应当说是1种很合适于在各种分类场景下利用的算法。adaboost算法的1些实际可使用的场景：
1）用于2分类或多分类的利用场景
2）用于做分类任务的baseline--无脑化，简单，不会overfitting，不用调分类器
3）用于特点选择（feature selection)
4）Boosting框架用于对badcase的修正--只需要增加新的分类器，不需要变动原有分类器
参考：
AdaBoost--从原理到实现
Adaboost 算法的原理与推导