当前位置: 代码迷 >> 综合 >> 机器学习(五):AdaBoost
  详细解决方案

机器学习(五):AdaBoost

热度:18   发布时间:2023-12-16 16:53:44.0

一,Adaboost算法

Adaboost是一种迭代算法,其核心思想是针对同一个训练集训练不同的分类器(弱分类器),然后把这些弱分类器集合起来,
构成一个更强的最终分类器(强分类器)。其算法本身是通过改变数据分布来实现的,它根据每次训练集之中每个样本的分类 是否正确,以及上次的总体分类的准确率,来确定每个样本的权值。
修改过权值的新数据集送给下层分类器进行训练,最后将每次训练得到的分类器最后融合起来,作为最后的决策分类器。使用adaboost分类器可以排除一些不必要的训练数据特征,并放在关键的训练数据上面

在这里插入图片描述
下面是将决策树与这些算法框架进行结合所得到的新的算法:

  • Bagging + 决策树 = 随机森林
  • AdaBoost + 决策树 = 提升树
  • Gradient Boosting + 决策树 = GBDT

二,数学表达

1.首先,初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权重:1/N。
在这里插入图片描述

接下来,如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它被选中的概率就被降低;相反,如果某个样本点没有被准确地分类,那么它的权重就得到提高。具体说来,则是:

2.对于m = 1,2, …, M
a.使用具有权值分布Dm的训练数据集学习,得到基本二元分类器:

在这里插入图片描述

b.计算Gm(x)在训练数据集上的分类误差率
在这里插入图片描述

c. 计算Gm(x)的系数,am表示Gm(x)在最终分类器中的重要程度(决定了在最终强学习里面的话语权):

在这里插入图片描述
由上述式子可知,em <= 1/2时,am >= 0,且am随着em的减小而增大,意味着分类误差率越小的基本分类器在最终分类器中的作用越大。
d. 更新训练数据集的权值分布
在这里插入图片描述

使得被基本分类器Gm(x)误分类样本的权值增大,而被正确分类样本的权值减小。就这样,通过这样的方式,AdaBoost方法能“聚焦于”那些较难分的样本上。
其中,Zm是规范化因子,使得Dm+1成为一个概率分布:

在这里插入图片描述

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

在这里插入图片描述
从而得到最终分类器(强分类器),如下:
在这里插入图片描述

三,流程

  1. 给定训练样本集S,其中X和Y分别对应于正例样本和负例样本; T为训练的最大循环次数;

  2. 初始化样本权重为1/n ,即为训练样本的初始概率分布;

  3. 第一次迭代:

    (1) 训练样本的概率分布相当下,训练弱分类器;

    (2) 计算弱分类器的错误率;

    (3) 选取合适阈值,使得误差最小;

    (4) 更新样本权重;

经T次循环后,得到T个弱分类器,按更新的权重叠加,最终得到的强分类器

四,实例

例1. 下面,给定下列训练样本,请用AdaBoost算法学习一个强分类器。在这里插入图片描述


求解过程:初始化训练数据的权值分布,令每个权值W1i = 1/N = 0.1,其中,N = 10,i = 1,2, …, 10,然后分别对于m = 1,2,3, …等值进行迭代。

拿到这10个数据的训练样本后,根据 X 和 Y 的对应关系,要把这10个数据分为两类,一类是“1”,一类是“-1”,根据数据
的特点发现:“0 1 2”这3个数据对应的类是“1”,“3 4 5”这3个数据对应的类是“-1”,“6 7 8”这3个数据对应的类是“1”,9是比较孤独的,对应类“-1”。抛开孤独的9不讲,“0 1 2”、“3 4 5”、“6 7 8”这是3类不同的数据,分别对应的类是1、-1、1,直观上推测可知,可以找到对应的数据分界点,比如2.5、5.5、8.5 将那几类数据分成两类。当然,这只是主观臆测,下面实际计算下这个过程。

迭代过程1

对于m=1,在权值分布为D1(10个数据,每个数据的权值皆初始化为0.1)的训练数据上,经过计算可得:

阈值v取2.5时误差率为0.3(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.3),
阈值v取5.5时误差率最低为0.4(x < 5.5时取1,x > 5.5时取-1,则3 4 5 6 7 8皆分错,误差率0.6大于0.5,不可取。故令x > 5.5时取1,x < 5.5时取-1,则0 1 2 9分错,误差率为0.4),
阈值v取8.5时误差率为0.3(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.3)。
所以无论阈值v取2.5,还是8.5,总得分错3个样本,故可任取其中任意一个如2.5,弄成第一个基本分类器为:

在这里插入图片描述

上面说阈值v取2.5时则6 7 8分错,所以误差率为0.3,更加详细的解释是:因为样本集中

0 1 2 对应的类(Y)是1,因它们本身都小于2.5,所以被G1(x)分在了相应的类“1”中,分对了。
3 4 5 本身对应的类(Y)是-1,因它们本身都大于2.5,所以被G1(x)分在了相应的类“-1”中,分对了。
6 7 8 本身对应类(Y)是1,却因它们本身大于2.5而被G1(x)分在了类"-1"中,所以这3个样本被分错了。
9本身对应的类(Y)是-1,因它本身大于2.5,所以被G1(x)分在了相应的类“-1”中,分对了。
从而得到G1(x)在训练数据集上的误差率:(被G1(x)误分类样本“6 7 8”的权值之和)
e1=P(G1(xi)≠yi) = 3*0.1 = 0.3。

然后根据误差率e1计算G1的系数:
在这里插入图片描述

这个a1代表G1(x)在最终的分类函数中所占的权重,为0.4236。
接着更新训练数据的权值分布,用于下一轮迭代:
在这里插入图片描述
值得一提的是,由权值更新的公式可知,每个样本的新权值是变大还是变小,取决于它是被分错还是被分正确。

即如果某个样本被分错了,则yi * Gm(xi)为负,负负等正,结果使得整个式子变大(样本权值变大),否则变小。

第一轮迭代后,最后得到各个数据新的权值分布
D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)。由此可以看出,因为样本中是数据“6 7 8”被G1(x)分错了,所以它们的权值由之前的0.1增大到0.1666,反之,其它数据皆被分正确,所以它们的权值皆由之前的0.1减小到0.0715。

分类函数f1(x)= a1*G1(x) = 0.4236G1(x)。

此时,得到的第一个基本分类器sign(f1(x))在训练数据集上有3个误分类点(即6 7 8)。

从上述第一轮的整个迭代过程可以看出:被误分类样本的权值之和影响误差率,误差率影响基本分类器在最终分类器中所占的权重。

迭代过程2

对于m=2,在权值分布为D2 = (0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.0715, 0.1666, 0.1666, 0.1666, 0.0715)的训练数据上,经过计算可得:

阈值v取2.5时误差率为0.16663(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.16663),
阈值v取5.5时误差率最低为0.07154(x > 5.5时取1,x < 5.5时取-1,则0 1 2 9分错,误差率为0.07153 + 0.0715),
阈值v取8.5时误差率为0.07153(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.07153)。
所以,阈值v取8.5时误差率最低,故第二个基本分类器为:
在这里插入图片描述

面对的还是下述样本:

在这里插入图片描述

很明显,G2(x)把样本“3 4 5”分错了,根据D2可知它们的权值为0.0715, 0.0715, 0.0715,所以G2(x)在训练数据集上的误差率e2=P(G2(xi)≠yi) = 0.0715 * 3 = 0.2143。

计算G2的系数:

在这里插入图片描述

更新训练数据的权值分布:
在这里插入图片描述

D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.1667, 0.1060, 0.1060, 0.1060, 0.0455)。被分错的样本“3 4 5”的权值变大,其它被分对的样本的权值变小。
f2(x)=0.4236G1(x) + 0.6496G2(x)
此时,得到的第二个基本分类器sign(f2(x))在训练数据集上有3个误分类点(即3 4 5)。

迭代过程3

对于m=3,在权值分布为D3 = (0.0455, 0.0455, 0.0455, 0.1667, 0.1667, 0.1667, 0.1060, 0.1060, 0.1060, 0.0455)的训练数据上,经过计算可得:

阈值v取2.5时误差率为0.10603(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.10603), 阈值v取5.5时误差率最低为0.04554(x > 5.5时取1,x < 5.5时取-1,则0 1 2 9分错,误差率为0.04553 + 0.0715), 阈值v取8.5时误差率为0.16673(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.16673)。 所以阈值v取5.5时误差率最低,故第三个基本分类器为(下图画反了,待后续修正):即修正为 x < 5.5 分为-1 类,x > 5.5分为1类

在这里插入图片描述

依然还是原样本:

在这里插入图片描述

此时,被误分类的样本是:0 1 2 9,这4个样本所对应的权值皆为0.0455,

所以G3(x)在训练数据集上的误差率e3= P(G3(xi)≠yi) = 0.0455*4 = 0.1820。

计算G3的系数:

在这里插入图片描述

更新训练数据的权值分布:
在这里插入图片描述

D4 = (0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125)

。被分错的样本“0 1 2 9”的权值变大,其它被分对的样本的权值变小。

f3(x)=0.4236G1(x) + 0.6496G2(x)+0.7514G3(x)

此时,得到的第三个基本分类器sign(f3(x))在训练数据集上有0个误分类点。至此,整个训练过程结束。

G(x) = sign[f3(x)] = sign[ a1 * G1(x) + a2 * G2(x) + a3 * G3(x) ]

, 将上面计算得到的a1、a2、a3各值代入G(x)中,得到最终的分类器为:
G(x) = sign[f3(x)] = sign[ 0.4236G1(x) + 0.6496G2(x)+0.7514G3(x) ]

五,adaboost的优缺点

AdaBoost的优缺点:

  • 优点:泛化错误率低,易编码,可以应用在大部分分类器上,无参数调整。

  • 缺点:对离群点敏感

  • 其他:
    集成方法通过组合多个分类器的分类结果,获得了比简单的单分类器更好的分类结果。本文只介绍了利用同一分类器的集成方法。除此之外,还有一些利用不同分类器的集成方法。
    多个分类器组合可能会进一步凸显出单分类器的不足,比如过拟合问题。

进一步深入(点下面博客)

  • 深入了解分类器错误率上下限
  • 进一步了解对分类器的性能判断:多出多重指标

来源:CSDN
原文:https://blog.csdn.net/c406495762/article/details/78212124
原文:https://blog.csdn.net/tiandijun/article/details/48036025