在本节对集成方法的介绍中，我们将重点讨论boosting算法中一个常用例子：AdaBoost（Adaptive Boosting的简称）。
AdaBoost背后的最初想法是由Robert Schapire于1990年提出的（R.E.Schapire.The Strength of Weak Learnability.Machine learning，5（2）:197——227，1990）。当Robert Schapire与Yoav Freund在第13届国际会议（ICML 1996）上发表AdaBoost算法后，随后的几年中，此算法就成为最广为应用的集成方法（Y.Freund,R.E.Schapire,et al.Experiments with a New Boosting Algorithm.In ICML,volume 96,pages 148——156,1996）。基于他们的开创性工作，Freund和Schapire在2003年获得了Goedel奖，这是发表计算机科学领域论文最负盛名的奖项。
在boosting中，集成分类器包含多个非常简单的成员分类器，这些成员分类器性能仅稍好于随机猜测，常被称作弱学习机。典型的弱学习机例子就是单层决策树。boosting主要针对难以区分的训练样本，也就是说，弱学习机通过在错误分类样本上的学习来提高集成分类的性能。与bagging不同，在boosting的初始化阶段，算法使用无放回抽样从训练样本中随机抽取一个子集。原始的boosting过程可总结为如下四个步骤：
1）从训练集D中以无放回抽样方式随机抽取一个训练子集d1，用于弱学习机C1的训练。
2）从训练集中以无放回抽样方式随机抽取第2个训练子集d2，并将C1中误分类样本的50%加入到训练集中，训练得到弱学习机C2。
3）从训练集D中抽取C1和C2分类结果不一致的样本生成训练样本集d3，以此训练第3个弱学习机C3。
4）通过多数投票组合三个弱学习机C1、C2和C3。
正如Leo Breiman所述[1]，与bagging模型相比，boosting可同时降低偏差和方差。在实践中，boosting算法（如AdaBoost）也存在明显的高方差问题，也就是说，对训练数据有过拟合倾向[2]。
AdaBoost与这里讨论的原始boosting过程不同，它使用整个训练集来训练弱学习机，其中训练样本在每次迭代中都会重新被赋予一个权重，在上一弱学习机错误的基础上进行学习进而构建一个更加强大的分类器。在深入到AdaBoost算法具体细节之前，先通过下图更深入了解一下AdaBoost的基本概念：
为循序渐进地介绍AdaBoost，我们从子图1开始，它代表了一个二类别分类问题的训练集，其中所有的样本都被赋予相同的权重。基于此训练集，我们得到一棵单层决策树（以虚线表示），它尝试尽可能通过最小化代价函数（或者是特殊情况下决策树集成中的不纯度得分）划分两类样本（三角形和圆形）。在下一轮（子图2）中，我们为前面误分类的样本（圆形）赋予更高的权重。此外，我们还降低被正确分类样本的权重。下一棵单层决策树将更加专注于具有最大权重的训练样本，也就是那些难于区分的样本。如子图2所示，弱学习机错误划分了圆形类的三个样本，它们在子图3中被赋予更大的权重。假定AdaBoost集成只包含3轮boosting过程，我们就能够用加权多数投票方式将不同重采样训练子集上得到的三个弱学习机进行组合，如子图4所示。
现在我们对AdaBoost的基本概念有了更好的认识，下面通过伪代码更深入地学习该算法。为了便于阐述，我们用十字符号（×）来表示向量的元素相乘，用点号（·）表示两个向量的内积，算法步骤如下：
虽然AdaBoost算法看上去很简单，我们接下来用下面表格中的10个样本作为训练集，通过一个具体的例子来更深入地了解此算法：
表格的第1列为样本的索引序号，为1～10。假设此表格代表了一个一维的数据集，第2列就相当于单个样本的值。第3列是对应于训练样本xi的真实类标yi，其中yi∈{1,-1}。第4列为样本的初始权重，权重值相等，且通过归一化使其和为1。在训练样本数量为10的情况下，我们将权重向量w中的权值wi都设定为0.1。假定我们的划分标准为x≤0.3，第5列存储了预测类标。基于前面伪码给出的权重更新规则，最后一列存储了更新后的权重值。
乍一看，权重更新的计算似乎有些复杂，我们来逐步讲解计算过程。首先计算第5步中权重的错误率：
下面来计算相关系数αj（第6步），该系数将在第7步权重更新及最后一个步骤多数投票预测中作为权重来使用。
在计算得到相关系数αj后，我们可根据下述公式更新权重向量：
由此，对于分类正确的样本，其对应的权重在下一轮boosting中将从初始的0.1降为0.066/0.914≈0.072。同样，对于分类错误的样本，其对应权重将从0.1提高到0.153/0.914≈0.167。
简而言之，这就是AdaBoost。下面进入实践操作，通过scikit-learn训练一个AdaBoost集成分类器。我们仍将使用上一节中训练bagging元分类器的葡萄酒数据集。通过base_estimator属性，我们在500棵单层决策树上训练AdaBoostClassifier。
由结果可见，与上一节中未剪枝决策树相比，单层决策树对于训练数据过拟合的程度更加严重一点：
还可以看到，AdaBoost模型准确预测了所有的训练集类标，与单层决策树相比，它在测试集上的表现稍好。不过，在代码中也可看到，我们在降低模型偏差的同时使得方差有了额外的增加。
出于演示的目的，我们使用了另外一个简单的例子，但可以发现，与单层决策树相比，AdaBoost分类器能够些许提高分类性能，并且与上一节中训练的bagging分类器的准确率接近。不过请注意：重复使用测试集进行模型选择不是一个好的方法。集成分类器的泛化性能可能会被过度优化，对此我们在第6章中已经做过详细介绍。
最后，我们来看一下决策区域的形状：
通过观察决策区域，我们可以看到Adabost的决策区域比单层决策树的决策区域复杂得多。此外，还注意到AdaBoost对特征空间的划分与上一节中训练的bagging分类器十分类似。
对集成技术做一个总结：毋庸置疑，与单独分类器相比，集成学习提高了计算复杂度。但在实践中，我们需仔细权衡是否愿意为适度提高预测性能而付出更多的计算成本。
关于预测性能与计算成本两者之间的权衡问题，一个常被提及的例子就是著名的一百万美元的奈飞竞赛（$1 Million Netflix Prize），最终胜出者就使用了集成技术。此算法的详细内容请参见A.Toescher等人的论文[3]。虽然获胜队伍得到了一百万美元的奖励，但由于模型的高复杂性，奈飞公司一直未将该模型投诸实际应用中[4]：
“……我们测得的准确率，额外的提高并不足以说服我们在工程方面进行投入，以将其应用到生产环境。”
[1] L. Breiman. Bias, Variance, and Arcing Classifiers. 1996.
[2] G. Raetsch, T. Onoda, and K. R. Mueller. An Improvement of Adaboost to Avoid Overfitting. In Proc. of the Int. Conf. on Neural Information Processing. Citeseer, 1998.
[3] A. Toescher, M. Jahrer, and R. M. Bell. The Bigchaos Solution to the Netflix Grand Prize. Netflix prize documentation, 2009（读者也可通过http://www.stat.osu.edu/~dmsl/GrandPrize2009_BPC_BigChaos.pdf 获取。
[4] 请见http://techblog.netflix.com/2012/04/netflix-recommendations-beyond-5-stars.html。