决策树系列5：AdaBoost 竟如此简单

引言

AdaBoost 其实很简单，就像我们参加模拟考试。

比如我们高考前要模拟考试10次，每次模拟完都需要分析各科的强弱，然后有针对性的复习，提升弱势科目，准备下一次模拟考试。

• 第一次考完发现物理化学较弱，复习时就给物理化学多一些时间。
• 第二次发现物理化学上去了，数学又相对较弱，复习时就多给数学一些时间。
• 依次类推，每次把相对较弱的科目多用些时间。

通过这十次模拟考试，相信我们的综合成绩会有很大的提升，在高考来临时一定能考出好成绩！

AdaBoost 简介

AdaBoost 全称 (Adaptive Boosting) 自适应增强，可以自适应地调整样本权重和分类器权重。

AdaBoost 由多个基本分类器组成，各个分类器顺序执行，每个后续分类器都根据前一个分类器的结果调整样本的权重，正确分类的样本调高权重，错误分类的样本调低权重。最后各个分类器根据分类器权重组合成最终分类器，给出分类结果。

AdaBoost 详解

问题描述：N 个样本的二分类问题, 类别 $y \in \{1, -1\}$y∈{1,−1}。

1. 初始化权重

起初 N 个样本中每个样本的权重 $w_i = \frac{1}{N}$wi​=N1​，样本权重之和为 1.

2. 基本分类器

a. 根据样本权重 $w_{m,i}$wm,i​ 构建基本分类器 $G_m$Gm​（比如决策树, 这里下标 m 表示第几个分类器），利用基本分类器对样本进行分类：

• 分类正确时：$G_m(x_i) = y_i$Gm​(xi​)=yi​
• 分类错误时：$G_m(x_i) \ne y_i$Gm​(xi​)​=yi​

b. 误差率 $e_m$em​ 为分类错误的样本权重之和

$e_m = \sum_{i=1}^N w_{m,i} I(G_m(x_i) \ne y_i)$em​=i=1∑N​wm,i​I(Gm​(xi​)​=yi​)

其中 $I(x)$I(x) 用于计数：

$I(x) = \begin{cases} 1,\quad x = True \\ 0,\quad x = False \end{cases}$I(x)={1,x=True0,x=False​

3. 计算权重

a. 分类器 $G_m$Gm​ 在最终多个分类器中的权重：
$\alpha_m = \frac12\,log\,\frac{1-e_m}{e_m}$αm​=21​logem​1−em​​

当 $e_m$em​<=0.5 时，$\alpha_m$αm​ 随 $e_m$em​ 减小而增大，也即误差小的分类器权重更大，另外这里的对数是自然对数。

当 $e_m$em​ > 0.5 时一半以上分类不正确，说明该分类器本身有问题，不可取。

b. 更新每个样本的权重：

$w_{m+1,i} = \frac{w_{m,i}\,\beta_{m,i}}{\sum_{i=1}^N\,w_{m,i}\,\beta_{m,i}}$wm+1,i​=∑i=1N​wm,i​βm,i​wm,i​βm,i​​

其中权重系数
$\beta_{m,i} = \begin{cases} e^{-\alpha_m},\quad G_m(x_i) = y_i \\ e^{\alpha_m},\quad G_m(x_i) \neq y_i \end{cases}$βm,i​={e−αm​,Gm​(xi​)=yi​eαm​,Gm​(xi​)​=yi​​

注意到更新 $w_{m+1}$wm+1​ 的公式中分母为分子每个样本之和，称为规范化因子，是为了保证更新后每个样本的权重之和仍为 1.

4. 最终分类器

重复 2,3 步骤 M 次后得到 M 个基本分类器，把每个分类器 $G_m$Gm​ 按照分类器权重 $\alpha_m$αm​ 加和得到 f(x)：

$f(x) = \sum_{i=1}^M\,\alpha\,G_m(x)$f(x)=i=1∑M​αGm​(x)

最终分类器 G(x) 为：

$G(x) = sign(f(x)) = sign(\sum_{i=1}^M\,\alpha\,G_m(x))$G(x)=sign(f(x))=sign(i=1∑M​αGm​(x))

其中符号函数 sign(x):

$sign(x) = \begin{cases} 1,\quad x > 0 \\ 0,\quad x = 0 \\ -1,\quad x < 0 \end{cases}$sign(x)=⎩⎪⎨⎪⎧​1,x>00,x=0−1,x<0​

AdaBoost 举例

假设我们有10个样本待分类，样本如下：

x	y
0	1
1	1
2	1
3	-1
4	-1
5	-1
6	1
7	1
8	1
9	-1

基本分类器为：找到分类点 v, 将样本集按照 {x > v, x < v} 分为两类，使得分类器的误差率最低。

1. 初始化样本

每个样本初始权重$w_i$wi​:

$w_i = \frac1N = 0.1$wi​=N1​=0.1

2. 构建第一个分类器

a. 当权重一致时，阈值 v = 2.5 时分类器误差率最低，所以$G_1$G1​:
$G_1(x) = \begin{cases} 1,\quad x < 2.5 \\ -1,\quad x > 2.5 \end{cases}$G1​(x)={1,x<2.5−1,x>2.5​

b. 分类器$G_1$G1​误差率 $e_1$e1​:
$e_1 = \sum_{i=1}^{10} 0.1 I(G_1(x_i) \ne y_i) = 0.3$e1​=i=1∑10​0.1I(G1​(xi​)​=yi​)=0.3
c. 分类器 $G_1$G1​ 的权重 $\alpha_1$α1​:
$\alpha_1 = \frac12\,log\,\frac{1-e_1}{e_1} = 0.4236$α1​=21​loge1​1−e1​​=0.4236

d. 更新样本权重 $w_2$w2​：
$w_{2,i} = \frac{0.1\,\beta_{1,i}}{\sum_{i=1}^{10}\,0.1\,\beta_{1,i}}$w2,i​=∑i=110​0.1β1,i​0.1β1,i​​
其中
$\beta = \begin{cases} e^{-0.4236},\quad G_m(x_i) = y_i \\ e^{0.4236},\quad G_m(x_i) \neq y_i \end{cases}$β={e−0.4236,Gm​(xi​)=yi​e0.4236,Gm​(xi​)​=yi​​
更新后样本权重分布：

{0.07143,0.07143,0.07143,0.07143,0.07143,0.07143,0.16667,0.16667,0.16667,0.07143}

这里就会发现，对于分类错误的样本 {6，7，8} 提高了权重

e. 此时最终分类器 G:
$G(x) = sign(0.4236 G_1(x))$G(x)=sign(0.4236G1​(x))
错误分类样本数为3个。

3. 构建第二个分类器

a. 根据更新后的权重，阈值 v = 8.5 时分类器误差率最低，所以$G_2$G2​:
$G_2(x) = \begin{cases} 1,\quad x < 8.5 \\ -1,\quad x > 8.5 \end{cases}$G2​(x)={1,x<8.5−1,x>8.5​
b. 分类器$G_2$G2​误差率 $e_2 = 0.2143$e2​=0.2143

c. 分类器 $G_2$G2​ 的权重 $\alpha_2 = 0.6496$α2​=0.6496:

d. 更新样本权重 $w_3$w3​ 分布为：

{0.0455,0.0455,0.0455,0.1667,0.1667,0.1667,0.1060,0.1060,0.1060,0.0455}

e. 此时最终分类器 G:
$G(x) = sign(0.4236 G_1(x) + 0.6496 G_2(x))$G(x)=sign(0.4236G1​(x)+0.6496G2​(x))
错误分类样本数为3个。

4. 构建第三个分类器

a. 根据更新后的权重，阈值 v = 5.5 时分类器误差率最低，所以$G_3$G3​:
$G_2(x) = \begin{cases} 1,\quad x > 5.5 \\ -1,\quad x < 5.5 \end{cases}$G2​(x)={1,x>5.5−1,x<5.5​
b. 分类器$G_3$G3​误差率 $e_3 = 0.1820$e3​=0.1820

c. 分类器 $G_3$G3​ 的权重 $\alpha_3 = 0.7514$α3​=0.7514:

d. 更新样本权重 $w_4$w4​ 分布为：

{0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125}

e. 此时最终分类器 G:
$G(x) = sign(0.4236 G_1(x) + 0.6496 G_2(x) + 0.7514G_3(x))$G(x)=sign(0.4236G1​(x)+0.6496G2​(x)+0.7514G3​(x))
错误分类样本数为0个。

5. 最终分类器

建立三个分类器后最终分类器的错误分类样本数为0，所以最终分类器为：
$G(x) = sign(0.4236 G_1(x) + 0.6496 G_2(x) + 0.7514G_3(x))$G(x)=sign(0.4236G1​(x)+0.6496G2​(x)+0.7514G3​(x))

• 一般停止建立新的分类器的条件可以有两种：
  1. 一种是限制最终分类器的错误率小于某个阈值时停止(例子中的方式)
  2. 一种是限制分类器的个数达到某个阈值时停止(例如最多 5 个分类器)

后记

Adaboost 我们先聊到这里，下一次是决策树系列的最后一个主题，我们来聊聊终极大 boss: XGBoost!

欢迎关注本人公众号《大数据茶馆》，用大白话畅聊大数据。

来的都是客，欢迎您常来坐坐~