Adaboost

Adaboost

什么是集成学习

在机器学习的有监督问题中,我们的目标是通过学习获得一个正确率很高的模型(强可学习)。但往往我们无法获得效果这么好的模型,只能得到一个学习率仅比随机猜测略好的模型(弱可学习)。Schapire证明,强可学习和弱可学习是等价的。因此,问题变成了,如何将我们容易获得的弱可学习模型变为强可学习模型。而集合学习便是这样一种方法,他通过多个弱可学习模型的组合得到一个强可学习模型。

集成学习主要分为以下几类:Bagging,Boosting和Stacking。

Bagging

Bagging是bootstrap aggregating的简写。在Bagging方法中,利用bootstrap方法从整体数据集中采取有放回抽样得到N个数据集,在每个数据集上学习出一个模型,最后的预测结果利用N个模型的输出得到,具体地:分类问题采用N个模型预测投票的方式,回归问题采用N个模型预测平均的方式。

Boosting

Boosting也是学习一系列弱可学习模型然后组成一个强可学习模型。与Bagging不同的是,Boosting通过改变训练数据的概率分布(训练数据的权值分布),学习出一系列弱可学习模型,再组合为一个强可学习模型。AdaBoost是其中最具代表性的,下文也将详细讲解。

Stacking

Stacking方法是指训练一个模型用于组合其他各个模型。首先我们先训练多个不同的模型,然后把之前训练的各个模型的输出为输入来训练一个模型,以得到一个最终的输出。理论上,Stacking可以表示上面提到的两种Ensemble方法,只要我们采用合适的模型组合策略即可。但在实际中,我们通常使用logistic回归作为组合策略。


Adaboost算法详解(针对分类问题)

基本思路

对于一个提升方法(Boosting),需要解决两个问题。

  • 在每一轮如何改变数据的权值或概率分布;
  • 如何将弱分类器组合成一个强分类器。

AdaBoost的做法是:

  • 提高被上一轮弱分类器错误分类的样本的权值,降低那些被正确分类的样本的权值;
  • 加大分类误差较小的弱分类器的权值,减小分类误差较大的弱分类器的权值。

AdaBoost算法

输入:训练数据集 $ T = \lbrace (x_1,y_1),(x_2,y_2),…,(x_n,y_n)\rbrace $ ,其中 x i ∈ X , y i ∈ Y x_i \in X ,y_i \in Y xi​∈X,yi​∈Y
输出: 最终弱分类器 G ( x ) G(x) G(x) 。
步骤:

  1. 初始化训练集权值分布
    D 1 = ( w 11 , w 12 , . . . , w 1 N ) , w 1 i = 1 N , i = 1 , 2 , 3... , N D_1 = (w_{11},w_{12},...,w_{1N}),\quad w_{1i} = \frac{1}{N} , \quad i = 1, 2,3...,N D1​=(w11​,w12​,...,w1N​),w1i​=N1​,i=1,2,3...,N
  2. 对 m = 1,2,…,M(m = epoch)
    (a) 使用具有权值分布的 D m D_m Dm​训练数据集学习,得到弱分类器 G m ( x ) G_m(x) Gm​(x)
    (b) 计算 G m ( x ) G_m(x) Gm​(x)在训练数据集上的分类误差 e m = ∑ i = 1 N w m i I ( G m ( x i ) ≠ y i ) e_m = \sum_{i=1}^{N}w_{mi}I(G_m(x_i)\neq y_i) em​=i=1∑N​wmi​I(Gm​(xi​)​=yi​)
    © 计算 G m ( x ) G_m(x) Gm​(x)的系数 α m = 1 2 l o g 1 − e m e m \alpha_m=\frac{1}{2}log\frac{1-e_m}{e_m} αm​=21​logem​1−em​​
    (d)更新数据集的权值分布 D m + 1 = ( w m + 1 , 1 , . . . w m + 1 , i , . . . w m + 1. N ) D_{m+1} = (w_{m+1,1},...w_{m+1,i},...w_{m+1.N}) Dm+1​=(wm+1,1​,...wm+1,i​,...wm+1.N​) w m + 1 , i = w m i Z m e x p ( − α m y i G m ( x i ) ) , i = 1 , 2 , , . . . , N w_{m+1,i}=\frac {w_{mi}}{Z_m}exp(-\alpha_my_iG_m(x_i)),\quad i=1,2,,...,N wm+1,i​=Zm​wmi​​exp(−αm​yi​Gm​(xi​)),i=1,2,,...,N
    其中, Z m Z_m Zm​是规范因子:
    Z m = ∑ i = 1 N w m i e x p ( − α m y i G m ( x i ) ) Z_m = \sum_{i=1}^{N}w_{mi}exp(-\alpha_my_iG_m(x_i)) Zm​=i=1∑N​wmi​exp(−αm​yi​Gm​(xi​))

可以理解为 S o f t M a x SoftMax SoftMax的变形

  1. 构建弱分类器的线性组合 f ( x ) = ∑ m = 1 M α m G m ( x ) f(x)=\sum_{m=1}^{M}\alpha_mG_m(x) f(x)=m=1∑M​αm​Gm​(x)最终分类器即为:
    G ( x ) = s i g n ( f ( x ) ) = s i g n ( ∑ m = 1 M α m G m ( x ) ) G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha_mG_m(x)) G(x)=sign(f(x))=sign(m=1∑M​αm​Gm​(x))

AdaBoost例子

数据集

序号 1 2 3 4 5 6 7 8 9 10 11 12
x 0 1 2 3 4 5 6 7 8 9 10 11
y 1 1 1 -1 -1 -1 1 1 1 -1 -1 1

解: 初始化数据权值分布 D 1 = ( w 11 , w 12 , . . . , w 112 ) D_1 =(w_{11},w_{12},...,w_{112}) D1​=(w11​,w12​,...,w112​) w 1 I = 1 12 , i = 1 , 2 , . . . 12 w_{1I}=\frac{1}{12},i =1,2,...12 w1I​=121​,i=1,2,...12

对m=1
(1) 在 D 1 D1 D1的权值分布上, v v v取3.5时分类误差率最低,所以 G 1 ( x ) G_1(x) G1​(x)为: G 1 ( x ) = {     1 , x < 3.5 − 1 , x > 3.5 G_1(x)=\begin{cases} \ \ \ 1,\quad x<3.5\\ -1, \quad x>3.5\\ \end{cases} G1​(x)={   1,x<3.5−1,x>3.5​
(2) G 1 ( x ) G_1(x) G1​(x)的误差率为 e 1 = 0.333 e_1=0.333 e1​=0.333
(3) 计算 G 1 ( x ) G_1(x) G1​(x)的系数:$\alpha_1 = \frac{1}{2}ln\frac{1-e_1}{e_1}=0.3465 $
(4) 更新权值分布 w 2 i = w 1 i Z 1 e x p ( − α 1 y i G 1 ( x ) ) , x = 1 , 2... , 12 w_{2i}=\frac{w_{1i}}{Z_1}exp(-\alpha_1y_iG_1(x)),\quad x=1,2...,12 w2i​=Z1​w1i​​exp(−α1​yi​G1​(x)),x=1,2...,12 D 2 = ( w 21 , w 22 , . . . , w 212 ) D_2=(w_{21},w_{22},...,w_{212}) D2​=(w21​,w22​,...,w212​) = ( 0.0625 , 0.0625 , 0.0625 , 0.0625 , 0.0625 , 0.0625 , 0.125 , 0.125 , 0.125 , 0.0625 , 0.0625 , 0.125 ) =(0.0625,0.0625,0.0625,0.0625,0.0625,0.0625,0.125,0.125,0.125,0.0625,0.0625,0.125) =(0.0625,0.0625,0.0625,0.0625,0.0625,0.0625,0.125,0.125,0.125,0.0625,0.0625,0.125) f 1 ( x ) = 0.3465 G 1 ( x ) f_1(x)=0.3465G_1(x) f1​(x)=0.3465G1​(x)
分类器 G 1 ( x ) G_1(x) G1​(x)在训练集上有三个误分类点。

对m=2

  1. 在 D 2 D2 D2的权值分布上, v v v取9.5时分类误差率最低,所以 G 2 ( x ) G_2(x) G2​(x)为: G 2 ( x ) = {     1 , x < 9.5 − 1 , x > 9.5 G_2(x)=\begin{cases} \ \ \ 1,\quad x<9.5\\ -1, \quad x>9.5\\ \end{cases} G2​(x)={   1,x<9.5−1,x>9.5​
    (2) G 2 ( x ) G_2(x) G2​(x)的误差率为 e 2 = 0.3125 e_2=0.3125 e2​=0.3125
    (3) 计算 G 1 ( x ) G_1(x) G1​(x)的系数:$\alpha_2 = \frac{1}{2}ln\frac{1-e_2}{e_2}=0.3942 $
    (4) 更新权值分布 w 3 i = w 2 i Z 2 e x p ( − α 2 y i G 2 ( x ) ) , x = 1 , 2... , 12 w_{3i}=\frac{w_{2i}}{Z_2}exp(-\alpha_2y_iG_2(x)),\quad x=1,2...,12 w3i​=Z2​w2i​​exp(−α2​yi​G2​(x)),x=1,2...,12 D 3 = ( w 。 21 , w 22 , . . . , w 212 ) D_3=(w_。{21},w_{22},...,w_{212}) D3​=(w。​21,w22​,...,w212​) = ( 0.0431 , 0.0431 , 0.0431 , 0.0948 , 0.0948 , 0.0948 , 0.0862 , 0.0862 , 0.0862 , 0.0948 , 0.0431 , 0.1896 ) =(0.0431, 0.0431, 0.0431, 0.0948, 0.0948, 0.0948, 0.0862, 0.0862, 0.0862, 0.0948, 0.0431, 0.1896) =(0.0431,0.0431,0.0431,0.0948,0.0948,0.0948,0.0862,0.0862,0.0862,0.0948,0.0431,0.1896) f 2 ( x ) = 0.3465 G 1 ( x ) + 0.3942 G 2 ( x ) f_2(x)=0.3465G_1(x)+0.3942G_2(x) f2​(x)=0.3465G1​(x)+0.3942G2​(x)
    分类器 G 2 ( x ) G_2(x) G2​(x)在训练集上有三个误分类点。

对于m = 3,4,…重复迭代上述过程,直到 G m ( x ) G_m(x) Gm​(x)没有误分类点。

最终分类器为

G ( x ) = s i g n ( f ( x ) ) = s i g n ( ∑ m = 1 M α m G m ( x ) ) G(x)=sign(f(x))=sign(\sum_{m=1}^{M}\alpha_mG_m(x)) G(x)=sign(f(x))=sign(m=1∑M​αm​Gm​(x))

上一篇:[转]集成学习之Adaboost算法原理小结


下一篇:数据挖掘领域十大经典算法之—AdaBoost算法(超详细附代码)