Adaboost算法详细讲解

转自线上数据建模

Adaboost算法详细讲解

Adaboost(Adaptive Boosting):

Adaboost是Boosting模型,和bagging模型(随机森林)不同的是:Adaboost会构建多个若分类器(决策树的max_depth=1),每个分类器根据自身的准确性来确定各自的权重,再合体。同时Adaboost会根据前一次的分类效果调整数据权重。

具体说来,整个Adaboost 迭代算法分为3步:

1. 初始化训练数据的权值分布。如果有N个样本,则每一个训练样本最开始时都被赋予相同的权值:1/N。

2. 训练弱分类器(带有样本权重的分类器都可以,sklearn的AdaBoostClassifier采用的就是max_depth=1的决策树)。具体训练过程中,如果某个样本点已经被准确地分类,那么在构造下一个训练集中,它的权值就被降低;相反,如果某个样本点没有被准确地分类,那么它的权值就得到提高,也就是如果某一个数据在这次分错了,那么在下一次我就会给它更大的权重。然后,权值更新过的样本集被用于训练下一个分类器,整个训练过程如此迭代地进行下去。

3. 将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后,加大分类误差率小的弱分类器的权重,使其在最终的分类函数中起着较大的决定作用, 而降低分类误差率大的弱分类器的权重,使其在最终的分类函数中起着较小的决定作用。如下图所示,误差率低的弱分类器在最终分类器中占的权重(am)较大,否则较小。

Adaboost算法详细讲解

接下来我们分两部分详细介绍Adaboost,分别从算法流程以及数据推导进行阐述。

Adaboost算法流程:

AdaBoost算法使用加法模型,损失函数为指数函数,学习算法使用前向分步算法。

1. 初始化每个训练样本的权值,共N个训练样本,每个样本的权重1/N。

Adaboost算法详细讲解

2. 构建M个基分类器(决策树 max_depth=1),第m个分类器如下,am是第m个分类器的权重,分类器准确率高通常am权重也高,反之相反:

Adaboost算法详细讲解

3. sign函数中的ΣamGm(x)>0时,sign返回+1,反之返回-1。

Adaboost算法详细讲解

4. 计算误差率em,用没有分对的样本权重除以总权重,其中总权重(归一化)=1,字母I代表满足条件的=1,不满足条件的=0,如下,当Gm(xi)≠yi的样本对应的I=1,其他的样本对应的I=0。这个误差率em最终会作用到基分类器Gm(x)的权重am上面,下面我们就详细推导一下。

Adaboost算法详细讲解

5. 接下来我们看一下em和am到底有什么关系?

6. 首先我们构建损失函数如下,当分类器预测正确时L(y,f(x))=e-1,预测错时L(y,f(x))=e,因此我们的损失函数是求极小值。

Adaboost算法详细讲解

7. 由于我们是构建多个若分类器,通过sign函数将多个弱分类器加总在一起构建一个强分类器,因此分类器具备可加性。

Adaboost算法详细讲解

8. 将上面的函数带入损失函数得:

Adaboost算法详细讲解

9. 现在我们设Adaboost算法详细讲解等于下面的等式,用以带入上面的方程进行简化操作,需要强调一下,这里的Adaboost算法详细讲解就是经过第m-1分类器调整后的样本权重w,换言之,就是样本权重w是由上一次基分类器调整后的结果进行调整,上一次分类越好的样本,Adaboost算法详细讲解=e-1权重就越小;分类越不好的样本,Adaboost算法详细讲解=e1权重就越大,这一点符合w优化要求,但是你可能会有疑问,此时更新后的样本权重之和≠1,Adaboost算法详细讲解,其实在公式推导层面,我们可以先不做归一化(下面会有讲到),可以等到公式推导完再对w进行归一化操作,因为此时是否做归一化不会对结果产生影响,后面会有证明。

Adaboost算法详细讲解

10. 带入Adaboost算法详细讲解到损失函数:

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

11. 此时G(x)有两种情况,预测对y=G(x)和预测错y≠G(x),将两种情况带入方程:

Adaboost算法详细讲解

12. 简化方程:

Adaboost算法详细讲解

13. 提取常数项:

Adaboost算法详细讲解

14. 字母I代表满足条件的=1,不满足条件的=0。

Adaboost算法详细讲解

15. 同时加减函数:

Adaboost算法详细讲解

Adaboost算法详细讲解

16. 最终得到上面损失函数,求极值,老套路,对a进行求偏导,让偏导等于0:

Adaboost算法详细讲解

Adaboost算法详细讲解

17. 还记得我们的误差率em吗,公式如下所示,可以得到Adaboost算法详细讲解 有没有做归一化都不会改变em的值(数学知识哈,分子分母同放大同缩小,值不变),既然em不变,那a也就不变,因此上面的公式推导,可以不对Adaboost算法详细讲解 做归一化:

Adaboost算法详细讲解

Adaboost算法详细讲解

18. 到此我们终于建立起分类器权重a与误差率e的关系,他们的关系是e越大,a越小,因此函数关系是反比关系,分类器越好(误差率低),权重应当越高。

Adaboost算法详细讲解

19. 而接下来我们要算em,此时我们才需要对Adaboost算法详细讲解 做归一化操作,公式也在告诉我们上一次分类器分的越好的样本,样本权重会减少,而分错的样本,样本权重会增加:

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

到此,我们知道了如何构建adaboost,其中包括如何更新w,以及找到了w,e和a的关系,接下来我们就尝试用实际的例子去构建adaboost,和传统例子不同,我们加入决策树作为若分类器,这一点和sklearn中的AdaBoostClassifier保持一致,很多网上关于adaboost的例子完全没有介绍真正的分类器是如何利用样本权重进行建树(决策树),只是通过简单的权重求和。因此为了能让大家充分了解adaboost是如何工作的,我就尝试将这两种方式(决策树 & 权重求和)通过对比的方式介绍给大家。

Adaboost具体实例:

Adaboost算法详细讲解

求解过程:

1. 初始化训练数据的权值分布,令每个权值W1,i = 1/N = 0.1。

2. 构建弱分类器:

迭代过程1:

假设我们用CART二叉树算法对X进行切分,还记得决策树一节讲到的“对连续型变量如何构建二叉树吗?”通过遍历β,找到最佳切分点对X进行切分。如果不考虑GINI指数,只通过误差率来判断,β的遍历情况应该如下:

1)阈值β取2.5时误差率为0.3(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.3=3*0.1)

2)阈 值β取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)

3)阈值β取8.5时误差率为0.3(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.3)

可以看到,无论阈值β取2.5,还是8.5,总会分错3个样本,故可任取其中任意一个如2.5,作为第一个基本分类器为:

Adaboost算法详细讲解

因为初始化样本权重都等于1/N,因此初始的决策树可以先不用考虑样本权重(因为默认的样本权重就是1/N),下面是通过决策树进行划分的结果。

Adaboost算法详细讲解

此时,决策树划分的结果和上面的一致,value列表[4,6]分别代表数据集中正负样本的权重,这里的初始权重为1,那真实的负样本总共有4个,正样本为6个。

然后根据误差率e1计算G1的系数:这个a1代表G1(x)在最终的分类函数中所占的权重,为0.4236。

Adaboost算法详细讲解

接着更新训练数据的权值分布,用于下一轮迭代:

Adaboost算法详细讲解

由于我们预测对了7个,分错3个,分母为:

Adaboost算法详细讲解

然后再分别计算每个样本权重,这里只给出两个例子,因为其他的都是重复的。

Adaboost算法详细讲解

Adaboost算法详细讲解

W1=(0.07142,0.07142,0.07142,0.07142,0.07142,0.07142,0.16666,0.16666,0.16666,0.07142)

Adaboost算法详细讲解

分类器1,

Adaboost算法详细讲解

迭代过程2:

1)阈值β取2.5时误差率为0.16666*3(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.16666*3)

2)阈值β取5.5时误差率为0.07142*3 + 0.07142(x > 5.5时取1,x < 5.5时取-1,则0 1 2 9分错,误差率为0.07142*3 + 0.07142)

3)阈值β取8.5时误差率为0.07142*3(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.07142*3)

阈值β取8.5时误差率最低,故第二个基本分类器为:

Adaboost算法详细讲解

带有样本权重的决策树分类如下:

Adaboost算法详细讲解

(0.286=4(负样本)*0.07142,0.714=3(正样本)*0.07142+3(正样本)*0.16666)

看到了吗,决策树通过带有样本权重的gini指数确定的β和通过误差率确定β的结果一致。

这里给出“带有样本权重的GINI”计算逻辑,通常是通过遍历方式计算每个β下的GINI,找到最优的β,这里就假设正好遍历到β=8.5,这时我们来计算一下GINI指数吧:

1. 初始GINI:

Adaboost算法详细讲解

平时我们算的概率Nj/N是没有加权的(每个样本权重都是1/N),下面的概率是加权后的概率。

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

2. β=8.5时的X分裂GINI指数(这里就不证明β=8.5,样本权重=w2时,是使得X分裂的GINI指数最小。穷举β很耗时,可以参考决策树章节):

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

from sklearn import tree
dtr = tree.DecisionTreeClassifier(max_depth = 1)
dtr.fit(df.X.values.reshape(-1,1), df.Y,sample_weight=[0.07142,0.07142,0.07142,0.07142,0.07142,0.07142,0.16666,0.16666,0.16666,0.07142])
print(dtr.tree_.threshold)

然后根据误差率e2计算G2的系数:这个a2代表G2(x)在最终的分类函数中所占的权重,为0.6497。

Adaboost算法详细讲解

Adaboost算法详细讲解

接着更新训练数据的权值分布,用于下一轮迭代:

Adaboost算法详细讲解

分母为:

Adaboost算法详细讲解

然后再分别计算每个样本权重:

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

W2=(0.04545,0.04545,0.04545,0.16667,0.16667,0.16667,0.10606,0.10606,0.10606,0.04545)

Adaboost算法详细讲解

分类器2,

Adaboost算法详细讲解

迭代过程3:

1)阈值β取2.5时误差率为0.10606*3(x < 2.5时取1,x > 2.5时取-1,则6 7 8分错,误差率为0.10606*3),

2)阈值β取5.5时误差率最低为0.04545*3 + 0.07142(x > 5.5时取1,x < 5.5时取-1,则0 1 2 9分错,误差率为0.04545*3 + 0.07142),

3)阈值β取8.5时误差率为0.16667*3(x < 8.5时取1,x > 8.5时取-1,则3 4 5分错,误差率为0.16667*3)

所以阈值β取5.5时误差率最低,故第三个基本分类器为:

Adaboost算法详细讲解

带有样本权重的决策树分类如下:

Adaboost算法详细讲解

推导逻辑和“迭代过程2”一致,这里就不再赘述。

from sklearn import tree
dtr = tree.DecisionTreeClassifier(max_depth = 1)
dtr.fit(df.X.values.reshape(-1,1), df.Y,sample_weight=[0.04545,0.04545,0.04545,0.16667,0.16667,0.16667,0.10606,0.10606,0.10606,0.04545])
print(dtr.tree_.threshold)

然后根据误差率e3计算G3的系数:这个a3代表G3(x)在最终的分类函数中所占的权重,为0.7520。

Adaboost算法详细讲解

Adaboost算法详细讲解

接着更新训练数据的权值分布,用于下一轮迭代:

Adaboost算法详细讲解

分母为:

Adaboost算法详细讲解

然后再分别计算每个样本权重:

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

Adaboost算法详细讲解

W3=(0.1249,0.1249,0.1249,0.1018,0.1018,0.1018,0.0648,0.0648,0.0648,0.1249)

Adaboost算法详细讲解

分类器3,

Adaboost算法详细讲解

此时,得到的第三个基本分类器sign(f3(x))在训练数据集上有0个误分类点。至此,整个训练过程结束,可以通过下面的方式,一个样本一个样本去试。

Adaboost算法详细讲解

Adaboost算法详细讲解

从上述过程中可以发现,如果某些个样本被分错,它们在下一轮迭代中的权值将被增大,同时,其它被分对的样本在下一轮迭代中的权值将被减小。就这样,分错样本权值增大,分对样本权值变小,而在下一轮迭代中,总是选取让误差率最低的阈值来设计基本分类器,所以误差率e(所有被Gm(x)误分类样本的权值之和)不断降低。

以上就是Adaboost的详细介绍,谢谢。

测试代码:

from sklearn.ensemble import AdaBoostClassifier
import pandas as pd
from sklearn.datasets import make_classification
X=[0,1,2,3,4,5,6,7,8,9]
Y=[1,1,1,-1,-1,-1,1,1,1,-1]
df=pd.DataFrame({'X':X,'Y':Y}) 
clf = AdaBoostClassifier(n_estimators=100, random_state=0)
clf.fit(df.X.values.reshape(-1,1), df.Y)
print(clf.score(df.X.values.reshape(-1,1), df.Y))

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
心中带点小风骚的头像心中带点小风骚普通用户
上一篇 2023年3月25日
下一篇 2023年3月25日

相关推荐