AdaBoost算法

对于使用提升(Boosting)方法，需要解决两个问题：

如何改变每一轮训练数据的权重或者概率分布；
如何将各个弱分类器(弱学习器)组合成一个强分类器(强学习器)。

AdaBoost算法的做法是：

提高那些前一轮被弱分类器错误分类样本的权重，降低那些被正确分类样本的权重；
对于弱分类器的组合，AdaBoost采取的是加权多数表决的方法。具体做法是：加大分类误差率小的弱分类器的权重，使其在表决中起较大作用；减小分类误差率大的弱分类器的权重，使其在分类中表决中起较小的作用。

AdaBoost算法过程：
假设有训练数据集 $T = {(x_{1}, y_{1}), (x_{2}, y_{2}), . . ., (x_{n}, y_{n})}$ ，
其中 $x_{i} \in X \subseteq R^{n}, i = 1, 2, . . ., n$ ；
类标 $y_{i} \in Y = {- 1, + 1}, i = 1, 2, . . ., n$ ；
最终训练出一个强分类器 $G (x)$

1、初始化训练数据的权值分布，确保每份训练数据的权重一致：

D = (w_{1}, . . ., w_{i}, . . ., w_{N})

其中

w_{i} = \frac{1}{N}, i = 1, 2, . . ., N

2、用训练数据集

T

训练

M

个弱分类器

G_{m} (x)

，则可以得到

M

个的权值分布，即有：

G_{m} (x) : X \to Y

D_{m} = (w_{m 1}, w_{m 2}, . . ., w_{m i}, w_{m N})

其中

m = 1, 2, . . ., M

3、计算 $G_{m} (x)$ 在训练数据集上的分类误差率

e_{m} = P (G_{m} (x_{i}) \neq y_{i}) = \frac{\sum_{i = 1}^{N} I (G_{m} (x_{i}) \neq y_{i})}{N}

4、计算

G_{m} (x)

系数

α_{m} = \frac{1}{2} \ln \frac{1 - e_{m}}{e_{m}}

α_{m}

的图像如下

由图像可知，随着分类误差率

e_{m}

越大，

G_{m} (x)

系数

α_{m}

会越小。

4、更新训练数据的权值分布：

D_{m + 1} = (w_{m + 1, 1}, w_{m + 1, 2}, . . ., w_{m + 1, i}, w_{m + 1, N})

Z_{m} = \sum_{i = 1}^{N} w_{m i} \cdot e x p (- α_{m} y_{i} G_{m} (x_{i}))

w_{m + 1, i} = \frac{w_{m i} \cdot e x p (- α_{m} y_{i} G_{m} (x_{i}))}{Z_{m}}

5、构建弱分类器的线性组合：

f (x) = \sum_{m = 1}^{M} α_{m} G_{m} (x)

6、最终经过

M

轮迭代，构建出来的强分类器为：

G (x) = s i g n (f (x)) = s i g n (\sum_{m = 1}^{M} α_{m} G_{m} (x))

其中

s i g n (x)

是一个符号函数，它符合:

s i g n (x) = {\begin{cases} 1, & x > 0 \\ 0, & x = 0 \\ - 1, & x < 0 \end{cases}

相关推荐