进击数据挖掘十大算法(五):AdaBoost

引言

提升(boosting)方法是一种常用的统计学习方法,应用广泛且有效。在分类问题中,它通过改变训练样本的权重,学习多个分类器,并将这些分类器进行线性组合,提高分类的性能。

提升方法基于这样一种思想:对于一个复杂任务来说,将多个专家的判断进行适当的综合所得出的判断,要比其中任何一个专家的单独判断好。实际上,就是“三个臭皮匠顶个诸葛亮”的道理。提升方法就是从弱学习算法出发,反复学习,得到一系列弱分类器,然后组合这些弱分类器,构成一个强分类器。大多数提升方法都是改变训练数据的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列的弱分类器。

这样,对提升方法来说,有两个问题:一是每一轮如何改变训练数据的权值分布;二是如何将弱分类器组合成一个强分类器。关于第一个问题,AdaBoost的做法是提高那些被前一轮弱分类器错误分类样本的权值,而降低那些被正确分类样本的权值。这样一来,那些没有得到正确分类的数据,由于其权值的加大而收到后一轮的弱分类器的更大关注。至于第二个问题,AdaBoost采取加权多数表决的方法,即加大分类误差率小的弱分类器的权值,使其在表决中起较大的作用;减小分类误差率大的弱分类器的权值,使其在表决中起较小的作用。

AdaBoost的巧妙之处就在于它将这些想法自然且有效的实现在一种算法里。

一、AdaBoost算法

假定给定一个二分类的训练数据集:

$$T=\{(x_1,y_1),(x_2,y_2),\dots,(x_N,y_N)\}$$

其中,每个样本点由实例与标记组成。实例 $x_i\in X \subseteq R^n$ ,标记 $y_i \in Y = \{-1, +1\}$,X是实例空间,Y是标记集合。 AdaBoost利用以下算法,从训练数据中学习一系列弱分类器或基本分类器,并将这些弱分类器线性组合成一个强分类器。

1.1 算法 — AdaBoost

  • 输入:训练数据集 $T$;弱学习算法;

  • 输出:最终分类器 $G(x)$

(1) 初始化训练数据的权值分布

$$D_1 = (w_{11},\cdots,w_{1i},\cdots,w_{1N}),w_{1i} = \frac{1}{N},i=1,2,\cdots,N$$

(2) 对 $m=1,2,\cdots,M$

  • (a) 使用具有权值分布 $D_m$ 的训练数据集学习,得到基本分类器

$$G_m(x):X\rightarrow\{-1,+1\}$$

  • (b) 计算 $G_m(x)$ 在训练数据集上的分类误差率

$$e_m=\sum_{i=1}^NP(G_m(x_i) \neq y_i)=\sum_{i=1}^Nw_{mi}I(G_m(x_i)\neq y_i)$$

  • (c) 计算 $G_m(x)$ 的系数

$$a_m=\frac{1}{2} \ln\frac{1-e_m}{e_m}$$

  • (d) 更新训练数据集的权值分布

$$D_{m+1}=(w_{m+1,1},\cdots,w_{m+1,i},\cdots,w_{m+1,N})$$

$$w_{m+1,i}=\frac{w_{mi}}{Z_m}exp(-a_my_iG_m(x_i)),i=1,2,\cdots, N$$

$$Z_m=\sum_{i=1}^{N}w_{mi}exp(-a_my_iG_m(x_i))$$

(3) 构建基本分类器的线性组合

$$f(x)=\sum_{m=1}^Ma_mG_m(x)$$

得到最终分类器

$$G(x)=sign(f(x))=sign(\sum_{m=1}^Ma_mG_m(x))$$

1.2 AdaBoost算法说明

步骤(1):假设训练数据集具有均匀的权值分布,即每个训练样本在基本分类器的学习中作用相同,这一假设保证第1步能够在原始数据上学习基本分类器 $G_1(x)$。

步骤(2): AdaBoost反复学习基本的分类器,在每一轮 $m=1,2,\cdots, M$ 顺次执行下列操作:

  • (a) 使用当前分布 $D_m$ 加权的训练数据集,学习基本分类器 $G_m(x)$。

  • (b) 计算基本分类器 $G_m(x)$ 在加权训练数据集上的分类误差率

  • (c) 计算基本分类器 $G_m(x)$ 的系数 $a_m$。$a_m$ 表示 $G_m(x)$ 在最终分类器中的重要性。由公式可知,分类误差率越小的基本分类器在最终分类器中的作用越大。

  • (d) 更新训练数据的权值分布为下一轮做准备,被基本分类器误分类样本的权值得以扩大,而被正确分类样本的权值得以缩小。因此,误分类样本在下一轮学习中起更大的作用。不改变所给的训练数据,而不断改变训练数据的权值分布,使得训练数据在基本分类器的学习中起不同的作用,这是AdaBoost的一个特点

步骤(3): 线性组合 $f(x)$ 实现 $M$ 个基本分类器的加权表决。系数 $a_m$ 表示了基本分类器 $G_m(x)$ 的重要性。这里,所有 $a_m$ 之和并不为1$f(x)$的符号决定实例 $x$ 的类,$f(x)$ 的绝对值表示分类的确信度。利用基本分类器的线性组合构建最终分类器是AdaBoost的另一特点

二、AdaBoost实例

序号 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) 初始化数据权值分布

$$D_1 = (w_{11},w_{12},\cdots,w_{110})$$

$$w_{1i}=0.1,i=1,2,\cdots,10$$

(2) 对 $m=1$ :

  • (a) 在权值分布为 $D_1$ 的训练数据上,阈值 $v$ 取2.5时分类误差率最低,故基本分类器为

$$G_1(x)=\begin{cases}1,&x<2.5 \cr -1,&x>2.5\end{cases}$$

  • (b) $G_1(x)$ 在训练数据集上的误差率 $e_1 = P(G_1(x_i)\neq y_i)=0.3$

  • (c) 计算 $G_1(x) 的系数:a_1=\frac{1}{2}\ln\frac{1-e_1}{e_1}=0.4236$

  • (d) 更新训练数据的权值分布

$$D_2=(w_{21},\cdots,w_{2i},\cdots,w_{210})$$

$$w_{2i}=\frac{w_{1i}}{Z_1}exp(-a_1y_iG_1(x_i)),i=1,2,\cdots,10$$

$$D_2 = (0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143)$$

$$f_1(X)=0.4236G_1(x)$$

分类器 $sign[f_1(x)]$ 在训练数据集上有3个误分类点。

(3) 对 $m=2$:

  • (a) 在权值分布为 $D_2$ 的训练数据上,阈值 $v$ 取8.5时分类误差率最低,故基本分类器为

$$G_2(x)=\begin{cases}1,&x<8.5 \cr -1,&x>8.5\end{cases}$$

  • (b) $G_2(x)$ 在训练数据集上的误差率 $e_2 = P(G_2(x_i)\neq y_i)=0.2143$

  • (c) 计算 $G_2(x) 的系数:a_2=\frac{1}{2}\ln\frac{1-e_2}{e_2}=0.6496$

  • (d) 更新训练数据的权值分布

$$D_3=(w_{31},\cdots,w_{3i},\cdots,w_{310})$$

$$w_{3i}=\frac{w_{2i}}{Z_2}exp(-a_2y_iG_2(x_i)),i=1,2,\cdots,10$$

$$D_3 = (0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455)$$

$$f_2(X)=0.4236G_1(x)+0.6496G_2(x)$$

分类器 $sign[f_2(x)]$ 在训练数据集上有3个误分类点。

(4) 对 $m=3$:

  • (a) 在权值分布为 $D_3$ 的训练数据上,阈值 $v$ 取5.5时分类误差率最低,故基本分类器为

$$G_3(x)=\begin{cases}1,&x>5.5 \cr -1,&x<5.5\end{cases}$$

  • (b) $G_3(x)$ 在训练数据集上的误差率 $e_3 = P(G_3(x_i)\neq y_i)=0.1820$

  • (c) 计算 $G_3(x) 的系数:a_3=\frac{1}{2}\ln\frac{1-e_3}{e_3}=0.7514$

  • (d) 更新训练数据的权值分布

$$D_4=(w_{41},\cdots,w_{4i},\cdots,w_{410})$$

$$w_{4i}=\frac{w_{3i}}{Z_3}exp(-a_3y_iG_3(x_i)),i=1,2,\cdots,10$$

$$D_4 = (0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)$$

$$f_3(X)=0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)$$

分类器 $sign[f_2(x)]$ 在训练数据集上误分类点个数为0。

于是最终分类器为

$$G(x)=sign[f_3(x)]=sign[0.4236G_1(x)+0.6496G_2(x)+0.7514G_3(x)]$$

三、Reference

  • 李航《统计学习方法》

(注:公式证明过程略,可以去B站找对应视频,这篇只用作日后回忆)