adacost算法（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算法使用加法模型 ，损失函数为指数函数 ，学习算法使用前向分步算法 。
1. 初始化每个训练样本的权值 ，共N个训练样本 ，每个样本的权重1/N 。
2. 构建M个基分类器（决策树 max_depth=1） ，第m个分类器如下 ，am是第m个分类器的权重 ，分类器准确率高通常am权重也高 ，反之相反：
3. sign函数中的ΣamGm(x)>0时 ，sign返回+1 ，反之返回-1 。
4. 计算误差率em ，用没有分对的样本权重除以总权重 ，其中总权重（归一化）=1 ，字母I代表满足条件的=1 ，不满足条件的=0 ，如下 ，当Gm(xi)≠yi的样本对应的I=1 ，其他的样本对应的I=0 。这个误差率em最终会作用到基分类器Gm(x)的权重am上面 ，下面我们就详细推导一下 。
5. 接下来我们看一下em和am到底有什么关系？
6. 首先我们构建损失函数如下 ，当分类器预测正确时L(y,f(x))=e-1 ，预测错时L(y,f(x))=e ，因此我们的损失函数是求极小值 。
7. 由于我们是构建多个若分类器 ，通过sign函数将多个弱分类器加总在一起构建一个强分类器 ，因此分类器具备可加性 。
8. 将上面的函数带入损失函数得：
9. 现在我们设等于下面的等式 ，用以带入上面的方程进行简化操作 ，需要强调一下 ，这里的就是经过第m-1分类器调整后的样本权重w ，换言之 ，就是样本权重w是由上一次基分类器调整后的结果进行调整 ，上一次分类越好的样本 ，=e-1权重就越小；分类越不好的样本 ，=e1权重就越大 ，这一点符合w优化要求 ，但是你可能会有疑问 ，此时更新后的样本权重之和≠1 ， ，其实在公式推导层面 ，我们可以先不做归一化（下面会有讲到） ，可以等到公式推导完再对w进行归一化操作 ，因为此时是否做归一化不会对结果产生影响 ，后面会有证明 。
10. 带入到损失函数：
11. 此时G(x)有两种情况 ，预测对y=G(x)和预测错y≠G(x) ，将两种情况带入方程：
12. 简化方程：
13. 提取常数项：
14. 字母I代表满足条件的=1 ，不满足条件的=0 。
15. 同时加减函数：
16. 最终得到上面损失函数 ，求极值 ，老套路 ，对a进行求偏导 ，让偏导等于0：
17. 还记得我们的误差率em吗 ，公式如下所示 ，可以得到 有没有做归一化都不会改变em的值(数学知识哈 ，分子分母同放大同缩小 ，值不变) ，既然em不变 ，那a也就不变 ，因此上面的公式推导 ，可以不对 做归一化：
18. 到此我们终于建立起分类器权重a与误差率e的关系 ，他们的关系是e越大 ，a越小 ，因此函数关系是反比关系 ，分类器越好（误差率低） ，权重应当越高 。
19. 而接下来我们要算em ，此时我们才需要对 做归一化操作 ，公式也在告诉我们上一次分类器分的越好的样本 ，样本权重会减少 ，而分错的样本 ，样本权重会增加：
到此 ，我们知道了如何构建adaboost ，其中包括如何更新w ，以及找到了w ，e和a的关系 ，接下来我们就尝试用实际的例子去构建adaboost ，和传统例子不同 ，我们加入决策树作为若分类器 ，这一点和sklearn中的AdaBoostClassifier保持一致 ，很多网上关于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 ，作为第一个基本分类器为：
因为初始化样本权重都等于1/N ，因此初始的决策树可以先不用考虑样本权重（因为默认的样本权重就是1/N） ，下面是通过决策树进行划分的结果 。
此时 ，决策树划分的结果和上面的一致 ，value列表[4,6]分别代表数据集中正负样本的权重 ，这里的初始权重为1 ，那真实的负样本总共有4个 ，正样本为6个 。
然后根据误差率e1计算G1的系数：这个a1代表G1(x)在最终的分类函数中所占的权重 ，为0.4236 。
接着更新训练数据的权值分布 ，用于下一轮迭代：
由于我们预测对了7个 ，分错3个 ，分母为：
然后再分别计算每个样本权重 ，这里只给出两个例子 ，因为其他的都是重复的 。
W1=(0.07142,0.07142,0.07142,0.07142,0.07142,0.07142,0.16666,0.16666,0.16666,0.07142)
分类器1 ，
迭代过程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时误差率最低 ，故第二个基本分类器为：
带有样本权重的决策树分类如下：
（0.286=4(负样本)*0.07142 ，0.714=3(正样本)*0.07142+3(正样本)*0.16666）
看到了吗 ，决策树通过带有样本权重的gini指数确定的β和通过误差率确定β的结果一致 。
这里给出“带有样本权重的GINI ”计算逻辑 ，通常是通过遍历方式计算每个β下的GINI ，找到最优的β ，这里就假设正好遍历到β=8.5 ，这时我们来计算一下GINI指数吧：
1. 初始GINI：
平时我们算的概率Nj/N是没有加权的（每个样本权重都是1/N） ，下面的概率是加权后的概率 。
2. β=8.5时的X分裂GINI指数（这里就不证明β=8.5 ，样本权重=w2时 ，是使得X分裂的GINI指数最小 。穷举β很耗时 ，可以参考决策树章节）：
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 。
接着更新训练数据的权值分布 ，用于下一轮迭代：
分母为：
然后再分别计算每个样本权重：
W2=(0.04545,0.04545,0.04545,0.16667,0.16667,0.16667,0.10606,0.10606,0.10606,0.04545)
分类器2 ，
迭代过程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时误差率最低 ，故第三个基本分类器为：
带有样本权重的决策树分类如下：
推导逻辑和“迭代过程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 。
接着更新训练数据的权值分布 ，用于下一轮迭代：
分母为：
然后再分别计算每个样本权重：
W3=(0.1249,0.1249,0.1249,0.1018,0.1018,0.1018,0.0648,0.0648,0.0648,0.1249)
分类器3 ，
此时 ，得到的第三个基本分类器sign(f3(x))在训练数据集上有0个误分类点 。至此 ，整个训练过程结束,可以通过下面的方式 ，一个样本一个样本去试 。
从上述过程中可以发现 ，如果某些个样本被分错 ，它们在下一轮迭代中的权值将被增大 ，同时 ，其它被分对的样本在下一轮迭代中的权值将被减小 。就这样 ，分错样本权值增大 ，分对样本权值变小 ，而在下一轮迭代中 ，总是选取让误差率最低的阈值来设计基本分类器 ，所以误差率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))创心域SEO版权声明：以上内容作者已申请原创保护，未经允许不得转载，侵权必究！授权事宜、对本内容有异议或投诉，敬请联系网站管理员，我们将尽快回复您，谢谢合作！