机器学习实战（八）AdaBoost算法(1)

红太狼 2021-11-05 20:14 512阅读 0赞

### 文章目录 ###

*   *  一、AdaBoost简介
     *  二、AdaBoost算法过程
     *  三、AdaBoost实例讲解
     *  四、AdaBoost的误差界以及指数损失函数推导
     *  五、AdaBoost的优点和缺点

## 一、AdaBoost简介 ##

**1.AdaBoost是什么？**  
AdaBoost，是英文"Adaptive Boosting"（自适应增强）的缩写，由Yoav Freund和Robert Schapire在1995年提出。它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。

Adaboost算法基本原理就是将多个弱分类器（弱分类器一般选用单层决策树）进行合理的结合，使其成为一个强分类器。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]  
**2.AdaBoost算法可以简述为三个步骤：**

（1）首先，是初始化训练数据的权值分布D1。假设有N个训练样本数据，则每一个训练样本最开始时，都被赋予相同的权值：w1=1/N。

（2）然后，训练弱分类器hi。具体训练过程中是：如果某个训练样本点，被弱分类器 h i h\_i hi**准确**地分类，那么在构造下一个训练集中，它对应的**权值要减小**；相反，如果某个训练样本点被**错误分类**，那么它的**权值**就应该**增大**。权值更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。

（3）最后，将各个训练得到的弱分类器组合成一个强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，**误差率低的弱分类器在最终分类器中占的权重较大，否则较小**。

## 二、AdaBoost算法过程 ##

给定一个训练数据集 T = ( x 1 , y 1 ) , ( x 2 , y 2 ) … ( x N , y N ) T=\{(x\_1,y\_1), (x\_2,y\_2)…(x\_N,y\_N)\} T=(x1,y1),(x2,y2)…(xN,yN)，其中实例 x ∈ χ x∈χ x∈χ，而实例空间![201908091023432.png][]， y i y\_i yi属于标记集合\{-1,+1\}，Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器，然后将这些弱分类器组合成一个强分类器。

**AdaBoost的算法流程如下：**

*  **步骤1.** 首先，初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权值：1/N。

![2019080910162331.png][]

*  **步骤2.** 进行多轮迭代，用m = 1,2, …, M表示迭代的第多少轮

（1）使用具有权值分布Dm的训练数据集学习，得到基本分类器（**选取让误差率最低的阈值来设计基本分类器**）：

![20190809101633967.png][]

（2） 计算Gm(x)在训练数据集上的分类误差率

![2019080910165251.png][]

**注：** 由上述式子可知， G m ( x ) G\_m(x) Gm(x)在训练数据集上的**误差率** e m e\_m em就是被 G m ( x ) G\_m(x) Gm(x)误分类样本的权值之和

（3）计算 G m ( x ) G\_m(x) Gm(x)的系数， a m a\_m am表示 G m ( x ) G\_m(x) Gm(x)在最终分类器中的重要程度（目的：得到基本分类器在最终分类器中所占的权重。注：这个公式 **写成 α m = 1 / 2 l n ( ( 1 − e m ) / e m α\_m = 1/2ln((1 - e\_m)/e\_m αm=1/2ln((1−em)/em 更准确，因为底数是自然对数e，故用In，** 写成log容易让人误以为底数是2或别的底数，下同）：

![20190809101705191.png][]

**注：** 由上述式子可知， e m < = 1 / 2 e\_m <= 1/2 em<=1/2时， a m > = 0 a\_m >= 0 am>=0，且 a m a\_m am随着 e m e\_m em的减小而增大，意味着分类误差率越小的基本分类器在最终分类器中的作用越大。

（4）更新训练数据集的权值分布（目的：得到样本的新的权值分布），用于下一轮迭代

![20190809101715662.png][]

**注：** 使得被基本分类器 G m ( x ) G\_m(x) Gm(x)误分类样本的权值增大，而被正确分类样本的权值减小。就这样，通过这样的方式，AdaBoost方法能“重点关注”或“聚焦于”那些较难分的样本上。  
其中， Z m Z\_m Zm是规范化因子，使得 D m + 1 D\_m+\_1 Dm\+1成为一个概率分布：

![20190809101729711.png][]

*  **步骤3.** 组合各个弱分类器

![20190809101738809.png][]

从而得到最终分类器，如下：

![20190809101746912.png][]

## 三、AdaBoost实例讲解 ##

注：博主有点懒，所以鉴于案例分析有点长，此次借用网上一篇博主的博客，附截图如下。如果有不明白的，可以在下面留言。

**例：给定如图所示的训练样本，弱分类器采用平行于坐标轴的直线，用Adaboost算法的实现强分类过程。**

![20190809103252681.png][]

**数据分析：**

将这10个样本作为训练数据，根据 X 和Y 的对应关系，可把这10个数据分为两类，图中用“+”表示类别1，用“O”表示类别-1。本例使用水平或者垂直的直线作为分类器，图中已经给出了三个弱分类器，即：

![20190809103347822.png][]

**初始化：**

首先需要初始化训练样本数据的权值分布，每一个训练样本最开始时都被赋予相同的权值： w i = 1 / N w\_i=1/N wi=1/N，这样训练样本集的初始权值分布 D 1 ( i ) D\_1(i) D1(i)：

令每个权值 w 1 i = 1 / N = 0.1 w\_1i = 1/N = 0.1 w1i=1/N=0.1，其中，N = 10，i = 1,2, …, 10，然后分别对于t= 1,2,3, …等值进行迭代（t表示迭代次数，表示第t轮），下表已经给出训练样本的权值分布情况：

![20190809103411567.png][]

**第1次迭代t=1：**

初试的权值分布 D 1 D\_1 D1为1/N（10个数据，每个数据的权值皆初始化为0.1）

D 1 D\_1 D1 =\[0.1, 0.1, 0.1, 0.1, 0.1, 0.1,0.1, 0.1, 0.1, 0.1\]

*  **在权值分布**  D 1 D\_1 D1的情况下，取已知的三个弱分类器h1、h2和h3中误差率最小的分类器作为第1个基本分类器H1(x)（三个弱分类器的误差率都是0.3，那就取第1个吧）

![20190809103425188.png][]

*  **可见** 被误分类样本的权值之和影响误差率e，误差率e影响基本分类器在最终分类器中所占的权重α。

![20190809103436129.png][]

*  **然后，** 更新训练样本数据的权值分布，用于下一轮迭代，对于正确分类的训练样本“1 2 3 4 6 9 10”（共7个）的权值更新为：

![20190809103448103.png][]

*  **这样**， 第1轮迭代后，最后得到各个样本数据新的权值分布：

D 2 D\_2 D2=\[1/14,1/14,1/14,1/14,1/6,1/14,1/6,1/6,1/14,1/14\]

由于样本数据 **“5 7 8”** 被  H 1 ( x ) H\_1(x) H1(x) 分错了，所以它们的权值由之前的0.1增大到1/6；反之，其它数据皆被分正确，所以它们的权值皆由之前的0.1减小到1/14，下表给出了权值分布的变换情况：

![20190809103505306.png][]

可得分类函数： f 1 ( x ) = α 1 H 1 ( x ) = 0.4236 H 1 ( x ) f\_1(x)= α\_1H\_1(x) = 0.4236H\_1(x) f1(x)=α1H1(x)=0.4236H1(x)。此时，组合一个基本分类器 s i g n ( f 1 ( x ) ) sign(f\_1(x)) sign(f1(x))作为强分类器在训练数据集上有3个误分类点（即5 7 8），此时强分类器的训练错误为：0.3

**第二次迭代t=2：**

在权值分布 D 2 D\_2 D2的情况下，再取三个弱分类器 h 1 h\_1 h1、 h 2 h\_2 h2和 h 3 h\_3 h3中误差率最小的分类器作为第2个基本分类器 H 2 ( x ) H\_2(x) H2(x)：

①当取弱分类器 h1=X1=2.5时，此时被错分的样本点为“5 7 8”：
    误差率e=1/6+1/6+1/6=3/6=1/2；
    
    ②　当取弱分类器h2=X1=8.5时，此时被错分的样本点为“3 4 6”：
    误差率e=1/14+1/14+1/14=3/14；
    
    ③　当取弱分类器h3=X2=6.5时，此时被错分的样本点为“1 2 9”：
    误差率e=1/14+1/14+1/14=3/14；

![20190809103520405.png][]

*  **因此**，取当前最小的分类器 h 2 h\_2 h2作为第2个基本分类器 H 2 ( x ) H\_2(x) H2(x)

![20190809103532319.png][]

*  **显然**， H 2 ( x ) H\_2(x) H2(x)把样本“3 4 6”分错了，根据 D 2 D\_2 D2可知它们的权值为 D 2 ( 3 ) = 1 / 14 D\_2(3)=1/14 D2(3)=1/14， D 2 ( 4 ) = 1 / 14 D\_2(4)=1/14 D2(4)=1/14，  
     D 2 ( 6 ) = 1 / 14 D\_2(6)=1/14 D2(6)=1/14，所以 H 2 ( x ) H\_2(x) H2(x)在训练数据集上的误差率：

![20190809103546134.png][]

*  **这样**，第2轮迭代后，最后得到各个样本数据新的权值分布：

D 3 D\_3 D3=\[1/22,1/22,1/6,1/6,7/66,1/6,7/66,7/66,1/22,1/22\]

**下表给出了权值分布的变换情况：**

![2019080910355914.png][]

可得分类函数： f 2 ( x ) = 0.4236 H 1 ( x ) + 0.6496 H 2 ( x ) f\_2(x)=0.4236H\_1(x) + 0.6496H\_2(x) f2(x)=0.4236H1(x)\+0.6496H2(x)。此时，组合两个基本分类器 s i g n ( f 2 ( x ) ) sign(f\_2(x)) sign(f2(x))作为强分类器在训练数据集上有3个误分类点（即**3 4 6**），此时强分类器的训练错误为：0.3

**第三次迭代t=3:**

在权值分布 D 3 D\_3 D3的情况下，再取三个弱分类器 h 1 h\_1 h1、 h 2 h\_2 h2和 h 3 h\_3 h3中误差率最小的分类器作为第3个基本分类器 H 3 ( x ) H\_3(x) H3(x)：

①当取弱分类器h1=X1=2.5时，此时被错分的样本点为“5 7 8”：
    误差率e=7/66+7/66+7/66=7/22；
    
    ②当取弱分类器h2=X1=8.5时，此时被错分的样本点为“3 4 6”：
    误差率e=1/6+1/6+1/6=1/2=0.5；
    
    ③当取弱分类器h3=X2=6.5时，此时被错分的样本点为“1 2 9”：
    误差率e=1/22+1/22+1/22=3/22；

![20190809103613657.png][]

*  **因此**，取当前最小的分类器 h 3 h\_3 h3作为第3个基本分类器 H 3 ( x ) H\_3(x) H3(x)：

![20190809103625356.png][]

*  **这样**，第3轮迭代后，得到各个样本数据新的权值分布为：
    
     D 4 D\_4 D4=\[1/6,1/6,11/114,11/114,7/114,11/114,7/114,7/114,1/6,1/38\]

**下表给出了权值分布的变换情况：**

![2019080910363888.png][]

可得分类函数： f 3 ( x ) = 0.4236 H 1 ( x ) + 0.6496 H 2 ( x ) + 0.9229 H 3 ( x ) f\_3(x)=0.4236H\_1(x) + 0.6496H\_2(x)+0.9229H\_3(x) f3(x)=0.4236H1(x)\+0.6496H2(x)\+0.9229H3(x)。此时，组合三个基本分类器 s i g n ( f 3 ( x ) ) sign(f\_3(x)) sign(f3(x))作为强分类器，在训练数据集上有0个误分类点。至此，整个训练过程结束。

**整合所有分类器，可得最终的强分类器为：**

![20190809103647552.png][]

**这个强分类器Hfinal对训练样本的错误率为0！**

## 四、AdaBoost的误差界以及指数损失函数推导 ##

可以参考:https://www.bbsmax.com/A/A2dmEpNbde/  
详细的推导请看《统计学习方法第二版》

## 五、AdaBoost的优点和缺点 ##

**优点**

（1）Adaboost提供一种框架，在框架内可以使用各种方法构建子分类器。可以使用简单的弱分类器，不用对特征进行筛选。

（2）Adaboost算法不需要弱分类器的先验知识，最后得到的强分类器的分类精度依赖于所有弱分类器。无论是应用于人造数据还是真实数据，Adaboost都能显著的提高学习精度。

（3）Adaboost算法不需要预先知道弱分类器的错误率上限，且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，可以深挖分类器的能力。Adaboost可以根据弱分类器的反馈，自适应地调整假定的错误率，执行的效率高。

（4）Adaboost对同一个训练样本集训练不同的弱分类器，按照一定的方法把这些弱分类器集合起来，构造一个分类能力很强的强分类器，即“三个臭皮匠赛过一个诸葛亮”。

**缺点：**

在Adaboost训练过程中，Adaboost会使得难于分类样本的权值呈指数增长，训练将会过于偏向这类困难的样本，导致Adaboost算法易受噪声干扰。此外，Adaboost依赖于弱分类器，而弱分类器的训练时间往往很长。

参考资料：  
\[1\]《统计学习方法》李航著

\[2\]《机器学习实战》Peter Harrington著

\[3\]https://blog.csdn.net/v\_JULY\_v/article/details/40718799

\[4\]https://blog.csdn.net/guyuealian/article/details/70995333

\[5\]https://blog.csdn.net/px\_528/article/details/72963977

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FzMTc4MDkyNTk3MTU_size_16_color_FFFFFF_t_70]: /images/20211104/bf747466c70b4e66b7fea527df6e13c9.png
[201908091023432.png]: /images/20211104/f64d3a1b3eb44ae29910211b4c450906.png
[2019080910162331.png]: /images/20211104/637f86fe945849d3ba642875018f5dfa.png
[20190809101633967.png]: /images/20211104/6f6b55f8a89f4bee9913fcf51fc8a506.png
[2019080910165251.png]: /images/20211104/c53cdc74c7234b23a1bee9aa2ec5eb8e.png
[20190809101705191.png]: /images/20211104/a09e9665d8f643e09d59a796de7e8bce.png
[20190809101715662.png]: /images/20211104/0847b683ba6341ecbab72dfed070f6ba.png
[20190809101729711.png]: /images/20211104/1672287120bb499f998866a23c54ba50.png
[20190809101738809.png]: /images/20211104/5fe74cb193b44f5e82fa8dce67e24a6d.png
[20190809101746912.png]: /images/20211104/c213ebcd38ee498887599e50a4d7e514.png
[20190809103252681.png]: /images/20211104/9960744574754723b7b68c7b1816f548.png
[20190809103347822.png]: /images/20211104/73d2a971232e465c89e7835ad31822b1.png
[20190809103411567.png]: /images/20211104/b4feee50a64b416f95920f526664cc34.png
[20190809103425188.png]: /images/20211104/e38bfc66c7274f97ae98364557d53ce4.png
[20190809103436129.png]: /images/20211104/95c8fe27bdc649f28f8b8ec4f5dd8771.png
[20190809103448103.png]: /images/20211104/d7017f7cdb79449daecf4a373bf776a6.png
[20190809103505306.png]: /images/20211104/1f1294fecfe944cfaee28e5e7ad6b051.png
[20190809103520405.png]: /images/20211104/f6881dfbc05c44ab891efdcdab219888.png
[20190809103532319.png]: /images/20211104/fd499918ef5c4b98baf8d6ca6f037a63.png
[20190809103546134.png]: /images/20211104/32cf9a9161d34a27ba173d0d37152697.png
[2019080910355914.png]: /images/20211104/cdb037092ce3442a9ef7ea8f6913ae94.png
[20190809103613657.png]: /images/20211104/fdb4d56ba11e45778a7bb713aec4cacb.png
[20190809103625356.png]: /images/20211104/1d6db080191345bcb787d03352a6f275.png
[2019080910363888.png]: /images/20211104/24421f69cd7240ac994234acf5a2041e.png
[20190809103647552.png]: /images/20211104/a3520126191346b6b7fa1c2d0e32579b.png