Adaboost with trees is the best off-the-shelf classifier in the world. -Breiman 1996
决策树算法起源于1984年Breiman,Friedman等人提出的CART，后来又有人(Quinlan等)提出ID3，C4.5，C5.0，CHAID等算法，但是90年代随着支持向量机(SVM)的提出和发展，决策树遇到了极大的挑战。1996年，Freund和Schapire等人提出了Adaboost算法，可以将多个弱分类器(比如Stump决策树)组合起来形成一个更加强大的强分类器，其性能可以与支持向量机媲美，所以才会有Breiman上面那句话。
(一) 算法：
Adaboost算法的思想起源于80年代Valiant提出的PAC理论(Valiant因此获得2010年图灵奖)，1996年由Freund和Schapire提出该算法(二人因此获得2003年的 Godel Price ，是计算机理论界的最高奖)，其大体思想是，训练多个 弱分类器 (Weak Classifier，所谓弱分类器是指分类效果仅比随机分类器效果好就可以，亦即分类错误率要小于0.5，典型的弱分类器如 Stump ，亦即只有一个决策节点的决策树)，每个弱分类器都会更加关注上个弱分类器分错类的训练样例，最终的分类器由所有的这些弱分类器加权组成，亦即其分类结果为多个弱分类器的分类结果的加权和。下面是详细介绍：
Adaboost算法会训练M个弱分类器，每个分类器都会给所有的训练样例赋予权重，第一个分类器所有训练样例的权重都是1/N(N为训练样例的个数)，后面每个弱分类器都会提高前面的弱分类器分错类的训练样例的权重，以便使得这些训练样例尽量不会再分错。在此，我们仅讨论最简单的二分类，亦即分类结果为{+1，-1}：
1. 为第一个弱分类器的所有训练样例初始化权重，都设为1/N。
2. 迭代M次，亦即训练M个弱分类器：
(a) 训练当前弱分类器，使得训练样例的加权误差Jm最小。
(b) 求得当前弱分类器的加权误差率ε，如果ε>0.5，则当前分类器效果太差，算法终止，否则计算α=ln((1-ε)/ε)，α是一个大于1的数，用来增加被分错类的训练样例的权重。
(c) 对于所有被当前弱分类器分错类的训练样例，增大其权重(乘以α)，以便在训练下一个弱分类器时重视这些被分错类的训练样例(真正实现时还应进行标准化，亦即使得所有权重的和为1)。
3. 最终得到的强分类器利用M个弱分类器的分类结果的加权和作为测试训练样例的分类结果。
(二)Java实现
为了充分理解Adaboost算法，我写了一个简单的Java程序，训练样例是二维空间上的N个点，用到的弱分类器是最简单的Stump，亦即树桩。当训练数据是随机生成的时候，迭代10次后得到的分类器的准确率会达到75%-90%。当训练数据是形如下所示的分布时(但是我的数据集只有20个点)，准确率可以达到100%。
参考文献：
[1] Christopher M.Bishop Pattern Recognization and Machine Learnin ( PRML )， Chapter 14 Combining Models, p657
[2] Ethern Alpaydin 机器学习导论 15章 组合多学习器 p236
[4] 统计学习那些事 数据挖掘研究院
[5] Wiki:Decision Tree Learning
[6] Wiki:AdaBoost
