boosting方法是一种常用的统计学习方法，应用广泛且有效，在分类问题中，它通过改变训练样本的权重，学习多个分类器，并将这些分类器进行线性组合，提高分类的性能，这里我们通过Adaboost算法的示例分析来了解boosting方法的基本思路。
Adaboost算法
1 Adaboost算法流程图
左边是训练数据集，其中直方图的不同长度表示每个样例的权重。在经过一个分类器之后，加权的预测结果会通过三角形中的alpha值进行加权。每个三角形中输出的加权结果在圆形中求和，从而得到最终的输出结果。
2 Adaboost算法详细流程
输入：训练数据集 T={(x1,y1),(x2,y2),...,(xN,yN)}，xi为一个n维的特征点，yi∈{−1,+1}
输出：分类器G(x)
步骤1. 初始化训练数据权值分布
D1={w11,...,w1i,...w1N},w1i=1N,i=1,2,...N
步骤2. for T=1 to M
(1) 对于权值分布为Dm的训练数据集学习，得到弱分类器
Gm:xi→{−1，+1}
(2) 计算
Gm(x)在训练数据集上的分类误差
em=P(Gm(xi)≠yi)=∑i=1NwmiI(Gm(xi)≠yi)
(3) 计算分类器
Gm(x)的权重
αm=12ln1−emem
（4）更新训练数据集的分布
Dm+1={wm+1,1,...,wm+1,i,...wm+1,N}
wm+1,i=wmiZme−αmyiGmxi,i=1,2,...N
Zm=∑i=1Nwmie−αmyiGmxi
Zm是一个规范化因子
步骤3.分类器线性组合得到最终分类器
G(x)=sign(f(x))=sign(∑m=1MαmGm(x))
3 算法示例
给定如下样例数据，假设弱分类器由x<v或x>v产生，其阈值v使得分类器在训练数据集上分类误差最低，用Adaboost算法学习一个强分类器。
| Index |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
| x |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| y |
1 |
1 |
1 |
-1 |
-1 |
-1 |
1 |
1 |
1 |
-1 |
步骤1. 初始化样本权重
D1=(0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1)
样本个数为10，所以均匀分布每个样本的权重就为0.1
步骤2.迭代更新
第一轮迭代:
(a) 对于权值分布为D1的数据集，当分界点取为2.5时分类误差率最低，所以得到基分类器
x<0.5(y=1)x>0.5(y=−1)error=510=0.5
x>0.5(y=1)x<0.5(y=−1)error=510=0.5
x<1.5(y=1)x>1.5(y=−1)error=410=0.5
x>1.5(y=1)x<1.5(y=−1)error=610=0.5
x<2.5(y=1)x>2.5(y=−1)error=310=0.4
x>2.5(y=1)x<2.5(y=−1)error=710=0.6
x<3.5(y=1)x>3.5(y=−1)error=410=0.3
x>3.5(y=1)x<3.5(y=−1)error=610=0.7
x<4.5(y=1)x>4.5(y=−1)error=510=0.4
x>4.5(y=1)x<4.5(y=−1)error=510=0.6
...
G1(x)={1,x<2.5−1,x>2.5
(b)分类器误差:
e1=310=0.3
(c)分类器权重：
α1=12ln1−0.30.3=0.4236
(d)更新样本权重：
w2,i=w1iZ1e−α1yiG1xi,i=1,2,...N
D2=(0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143)
(e)最终分类器:
G(x)=sign(0.4236G1(x)),分类错误的样本数为3
从迭代结果可以看出因为分类器取2.5为分界点，所以索引为6,7,8 的样本分类错误，对应的样本权重更新后从0.1上调为了0.16667，而其他的样本都分类正确，样本权重下调为了0.07143。
第二轮迭代：
(a)对于权值分布为D2的数据集，分界点为8.5时误差率最低,基分类器为：
G2(x)={1,x<8.5−1,x>8.5
(b)分类器误差:
e2=0.2143
(c) 分类器权重：
α2=0.6496
(d)更新样本权重：
D3=(0.0455,0.0455,0.0455,0.16667,0.16667,0.16667,0.1060,0.1060,0.1060,0.0455)
(e)最终分类器：
G(x)=sign(0.4236G1(x)+0.6496G2(x))，分类错误样本数为3
从第二轮迭代的结果来看，基分类器对3，4，5的分类错误，而在第一轮迭代中分类错误的6，7，8分类正确了，所以3，4，5的样本权重上调为了0.1667,而6，7，8的样本权重下调为了0.1060，其它在第一轮和第二轮迭代中都分类正确的样本权重就变得更低。
第三轮迭代：
(a)在权值分布为D3的数据集上，分界点为5.5时分类误差率最低，基分类器为：
G3(x)={1,x>5.5−1,x<5.5
(b)分类器误差：
e3=0.1820
(c)分类器权重：
α3=0.7514
(d)更新数据权值分布：
D4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)
(e)最终分类器
G(x)=sign(0.4236G1(x)+0.6496G2(x)+0.7514G3(x)),误分点个数为0
