本篇包含adaboost的手动实现例子以及adaboost在R上的实现例子。
Adaboost简介
几个特点
Adaboost是一种比较有特点的算法，可以总结如下：
1 每次迭代改变的是样本的分布，而不是重复采样（reweighting not resampling)
2 样本分布的改变取决于样本是否被正确分类
总是分类正确的样本权值低
总是分类错误的样本权值高（通常是边界附近的样本）
3 最终的结果是弱分类器的加权组合。 权值表示该弱分类器的性能
几个优点: 简单，有效
1 adaboost是一种有很高精度的分类器
2 可以使用各种方法构建子分类器，adaboost算法提供的是框架
3 当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单
4 简单，不用做特征筛选
5 不用担心overfitting
实例计算过程
| 序号 | 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个分类器$G_1$
样本权重$w_1$
首先给$x_1,x_2,\cdots,x_{10}$ 相同的权重，为$\frac{1}{10}$
| 序号 | 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 |
| $w_1$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ |
分类结果 $G_1$
找到阈值$v = 2.5$, 使该分类器对上述数据分类误差最低。
分类规则
1 | def g(x): |
分类结果
| 序号 | 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 |
| $G_1(x)$ | 1 | 1 | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| $w_1$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ |
误差$e_{1}$
误差实际就是错分案例的权重之和。
$e_{1} = \sum_{i=1}^{10}{w_{1i}I(G_{1}(x_{i}) \neq y_{i}}) = \frac{3}{10} = 0.3$
$G_1$在最终分类器中的权重$\alpha_{1}$
$\alpha_{1} = \frac{1}{2}log\frac{1-e_1}{e_1} = \ \frac{1}{2}log\frac{1-0.3}{0.3} = 0.4236$
可见，被误分类样本的权值之和影响误差率，误差率影响基本分类器在最终分类器中所占的权重。
最终分类器$f_1$
$f_1(x) = sign(\alpha_{1}G_{1}(x)) = sign(0.4236G_1(x))$
最终分类结果
| 序号 | 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 |
| $f_1(x)$ | 1 | 1 | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
分类器$f_1(x)$ 分类结果： 样本7,8,9最终被分错。
第2个分类器$G_2$
基于$G_1$分类误差调整所有样本权重$w_2$
$w_{2i} = \frac{w_{1i}}{Z_1}e^{-\alpha_{1}*G_1(x_i)y_i}$
其中，$Z_{1} = \sum_{i = 1}^{10}w_{1i}e^{-\alpha_{1}*G_1(x_i)y_i}$
由权重公式可知，每个样本的权重在下一轮是变大还是变小取决于该样本在上一轮分类中分类正确或错误。如果正确，则$-\alpha_{1}G_1(x_i)y_i < 0$,即$e^{-\alpha_{1}G_1(x_i)y_i} < 1$, 权重将会减小；如果错误, 则$-\alpha_{1}G_1(x_i)y_i > 0$,即$e^{-\alpha_{1}G_1(x_i)y_i} > 1$ 权重会增大。
| 序号 | 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 |
| $G_1(x)$ | 1 | 1 | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| $w_1$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ |
| $w_2$ | 0.0715 | 0.0715 | 0.0715 | 0.0715 | 0.0715 | 0.0715 | 0.1666 | 0.1666 | 0.1666 | 0.0715 |
由此可以看出，因为样本7,8,9被$G_1(x)$分错了，所以它们的权值由之前的0.1增大到0.1666，反之，其它数据皆被分正确，所以它们的权值皆由之前的0.1减小到0.0715。
基于新样本权重$w_2$得到新分类器$G_2$
找到阈值$v = 8.5$, 使得该分类器对上述数据分类误差最低。
分类规则
1 | def g(x): |
分类结果
| 序号 | 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 |
| $G_2(x)$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | -1 |
| $w_2$ | 0.0715 | 0.0715 | 0.0715 | 0.0715 | 0.0715 | 0.0715 | 0.1666 | 0.1666 | 0.1666 | 0.0715 |
计算误差$e_{2}$
$e_{2} = \sum_{i=1}^{10}{w_{2i}I(G_{2}x_{i} \neq y_{i})} = 3*0.0715 = 0.2145$
根据$e_{2}$计算$G_2$在最终分类器中的权重
$\alpha_{2} = \frac{1}{2}log\frac{1-e_2}{e_2} = \frac{1}{2}log\frac{1-0.2145}{0.2145} = 0.649$
最终分类器$f_2$
$f_{2}(x) = sign(\alpha_{1}G_{1}(x) + \alpha_{2}G_{2}(x)) \ = sign(0.4236G_1(x) + 0.649G_2(x))$
最终分类结果
| 序号 | 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 |
| $f_2(x)$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | -1 |
| $G_1(x)$ | 1 | 1 | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| $G_2(x)$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | -1 |
分类器$f_2(x)$分类结果： 样本4,5,6最终被分错。
第3个分类器$G_3$
基于$G_2$分类误差调整所有样本权重$w_3$
$w_{3i} = \frac{w_{2i}}{Z_2}e^{-\alpha_{2}*G_2(x_i)y_i}$
其中，$Z_{2} = \sum_{i = 1}^{10}w_{2i}e^{-\alpha_{2}*G_2(x_i)y_i}$
| 序号 | 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 |
| $G_2(x)$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | -1 |
| $w_1$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ | $\frac{1}{10}$ |
| $w_2$ | 0.0715 | 0.0715 | 0.0715 | 0.0715 | 0.0715 | 0.0715 | 0.1666 | 0.1666 | 0.1666 | 0.0715 |
| $w_3$ | 0.0455 | 0.0455 | 0.0455 | 0.1666 | 0.1666 | 0.1666 | 0.1060 | 0.1060 | 0.1060 | 0.0455 |
同理，由于上一轮结束后，样本4,5,6被$G_2(x)$分错了，所以它们的权值由之前的0.0715增大到.1666，反之，其它数据皆被分正确，所以它们的权值皆由之前的0.0715减小到0.0455。
基于新样本权重$w_3$得到新分类器$G_3$
找到阈值$v = 5.5$, 使得该分类器对上述数据分类误差最低。
分类规则
1 | def g(x): |
分类结果
| 序号 | 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 |
| $G_3(x)$ | -1 | -1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 | 1 |
| $w_3$ | 0.0455 | 0.0455 | 0.0455 | 0.1666 | 0.1666 | 0.1666 | 0.1060 | 0.1060 | 0.1060 | 0.0455 |
计算误差$e_{3}$
$e_{3} = \sum_{i=1}^{10}{w_{2i}I(G_{2}x_{i} \neq y_{i})} = 4*0.0455 = 0.182$
根据$e_{3}$计算$G_3$在最终分类器$f_3$中的权重
$\alpha_{3} = \frac{1}{2}log\frac{1-e_3}{e_3} = \frac{1}{2}log\frac{1-0.182}{0.182} = 0.7514$
最终分类器$f_3$
$f_{3}(x) = sign(\alpha_{1}G_{1}(x) + \alpha_{2}G_{2}(x) + \alpha_{3}G_{3}(x)) \\= sign(0.4236G_1(x) + 0.649G_2(x) + 0.7514G_3(x))$
最终分类结果
| 序号 | 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 |
| $f_3(x)$ | 1 | 1 | 1 | -1 | -1 | -1 | 1 | 1 | 1 | -1 |
| $G_1(x)$ | 1 | 1 | 1 | -1 | -1 | -1 | -1 | -1 | -1 | -1 |
| $G_2(x)$ | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | -1 |
| $G_3(x)$ | -1 | -1 | -1 | -1 | -1 | -1 | 1 | 1 | 1 | 1 |
分类器$f_3(x)$ 分类结果全部正确，没有错分情况。
至此，整个训练过程结束。
总结
现在来总结一下整个训练过程, 包含各样本权重，分类器误差率的变化：
1 训练之前，各个样本的权重被初始化为
2 第一轮分类后，样本7,8,9被分错，对应误差率为$e_1 = 0.3$，此第一个基本分类器在最终分类器中所占的权重为$\alpha_{1} = 0.4236$。 同时，用于下一轮迭代的样本新权重为
3 第二轮迭代后，样本3,4,5被分错，对应误差率为$e_2 = 0.2145$，此第二个基本分类器在最终分类器中所占的权重为$\alpha_{2} = 0.649$。 同时，用于下一轮迭代的样本新权值为
4 第三轮迭代中，样本样本1,2,3,10被分错，对应误差率为$e_3 = 0.1820$，此第三个基本分类器在最终分类器中所占的权重为$\alpha_{3} = 0.7514$。
从上述过程中可以发现，如果某些个样本被分错，它们在下一轮迭代中的权值将被增大，同时，其它被分对的样本在下一轮迭代中的权值将被减小。就这样，分错样本权值增大，分对样本权值变小。 最终分类器:
$f(x) = sign(f_3(x)) = sign(\alpha_1G_1(x) + \alpha_2G_2(x) + \alpha_3G_3(x)) \\= 0.4236G_1(x) + 0.6490G_2(x)+0.7514G_3(x)$