机器学习boosting算法—Adaboost之示例解析

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	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