首页天道酬勤AdaBoost算法属于Bagging算法,AdaBoost算法是什么

AdaBoost算法属于Bagging算法,AdaBoost算法是什么

admin 08-19 20:17 282次浏览
基本概念

Adaboost算法,将多个弱分类器,组合成强分类器。
AdaBoost,是英文"Adaptive Boosting"(自适应增强)的缩写,由Yoav Freund和Robert Schapire在1995年提出。
它的自适应在于:前一个弱分类器分错的样本的权值(样本对应的权值)会得到加强,权值更新后的样本再次被用来训练下一个新的弱分类器。在每轮训练中,用总体(样本总体)训练新的弱分类器,产生新的样本权值、该弱分类器的话语权,一直迭代直到达到预定的错误率或达到指定的最大迭代次数。
总体——样本——个体三者间的关系需要搞清除
总体N。样本:{ni}i从1到M。个体:如n1=(1,2),样本n1中有两个个体。

优点:
(1)精度很高的分类器。
(2)提供的是框架,可以使用各种方法构建弱分类器。
(3)简单,不需要做特征筛选。
(4)不用担心过度拟合。
实际应用:
(1)用于二分类或多分类。
(2)特征选择
(3)分类人物的baseline。

算法原理:

(1)初始化训练数据(每个样本)的权值分布:如果有N个样本,则每一个训练的样本点最开始时都被赋予相同的权重:1/N。
(2)训练弱分类器。具体训练过程中,如果某个样本已经被准确地分类,那么在构造下一个训练集中,它的权重就被降低;相反,如果某个样本点没有被准确地分类,那么它的权重就得到提高。同时,得到弱分类器对应的话语权。然后,更新权值后的样本集被用于训练下一个分类器,整个训练过程如此迭代地进行下去。
(3)将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后,分类误差率小的弱分类器的话语权较大,其在最终的分类函数中起着较大的决定作用,而分类误差率大的弱分类器的话语权较小,其在最终的分类函数中起着较小的决定作用。换言之,误差率低的弱分类器在最终分类器中占的比例较大,反之较小。

算法流程:

第一步:
初始化训练数据(每个样本)的权值分布。每一个训练样本,初始化时赋予同样的权值w=1/N。N为样本总数。

D1表示,第一次迭代每个样本的权值。w11表示,第1次迭代时的第一个样本的权值。
N为样本总数。
第二步:进行多次迭代,m=1,2…M。m表示迭代次数。
a)使用具有权值分布Dm(m=1,2,3…N)的训练样本集进行学习,得到弱的分类器。

该式子表示,第m次迭代时的弱分类器,将样本x要么分类成-1,要么分类成1.那么根据什么准则得到弱分类器?
准则:该弱分类器的误差函数最小,也就是分错的样本对应的 权值之和,最小。

b)计算弱分类器Gm(x)的话语权,话语权am表示Gm(x)在最终分类器中的重要程度。其中em,为上步中的εm(误差函数的值)

该式是随em减小而增大。即误差率小的分类器,在最终分类器的 重要程度大。
c)更新训练样本集的权值分布。用于下一轮迭代。其中,被误分的样本的权值会增大,被正确分的权值减小。

Dm+1是用于下次迭代时样本的权值,Wm+1,i是下一次迭代时,第i个样本的权值。
其中,yi代表第i个样本对应的类别(1或-1),Gm(xi)表示弱分类器对样本xi的分类(1或-1)。若果分对,yi*Gm(xi)的值为1,反之为-1。其中Zm是归一化因子,使得所有样本对应的权值之和为1.

该公式并不难,仔细看看、想想。
第三步迭代完成后,组合弱分类器。
首先,
然后,加个sign函数,该函数用于求数值的正负。数值大于0,为1。小于0,为-1.等于0,为0.得到最终的强分类器G(x)

额外(关于权值、话语权、弱分类器准则的公式,想深入了解的可以看看。使用的话,知道上面的内容已经足够)
利用前向分布加法模型(简单说,就是把一起求n个问题,转化为每次求1个问题,再其基础上,求下一个问题,如此迭代n次),adaboost算法可以看成,求式子的最小。tn时样本n对应的正确分类,fm是前m个分类器的结合(这里乘了1/2,因为博主看的文章的am是1/2log(~~),这个无所谓,无非是多个1/2少个1/2。


然后,假设前m-1个相关的参数已经确定。通过化简E这个式子,我们可以得到:

其中,是一个常量。

然后,

其中,Tm是分类正确的样本的权值,Mm是分类错误的样本的权值。式子不算难,自己多看几遍就能理解了。
到现在,可以看出,最小化E,其实就是最小化

这个式子是什么?看看前面,这个就是找弱分类器时的准则!
然后得到了弱分类器ym后,我们可以进推导出am和样本的权值。这里给出am的推导过程(手写的,字很烂)其中,ε是
该图中,最右边的是“+exp(-am/2)*1”,写得太乱(—_—)

最后求出来的am没有1/2,这个无所谓。因为这里定义fm是多乘了个1/2。

实现(Python2.7)

adaBoost.py:adaboos算法实现。

# coding: UTF-8from __future__ import divisionimport numpy as npimport scipy as spfrom weakclassify import WEAKCfrom sign import *class ADABC:def __init__(self,X,y,Weaker=WEAKC):''' x是一个N*M的矩阵Weaker是一个弱分类器的类It should have a train(self.W) method pass the weight parameter to train需要调用~~~方法,去训练权值参数pred(test_set) method which return y formed by 1 or -1~~~方法,返回y(y的值为-1或1) <统计学习方法>''' ###初始化数据##X是样本点self.X=np.array(X)##列优先排列 Y是样本对应的类别 排成一个行向量self.y=np.array(y).flatten(1)#判断数据维度的列数是否一样(数据是否对应)assert self.X.shape[1]==self.y.size #弱分类器self.Weaker=Weakerself.sums=np.zeros(self.y.shape)#初始化权值 每个样本的权值为 1/样本数self.W=np.ones((self.X.shape[1],1)).flatten(1)/self.X.shape[1]self.Q=0#print self.Wdef train(self,M=4):'''M 是最大类别(第M个)弱分类器的下标,其实就是迭代的次数,'''#初始化弱分类器字典(空)self.G={}#弱分类器的话语权self.alpha={}for i in range(M):self.G.setdefault(i) #{0:none,...i:None}self.alpha.setdefault(i)#0:none,...i:None}for i in range(M): #用样本初始化弱分类器self.G[i]=self.Weaker(self.X,self.y)#调用train方法,训练弱分类器,同时计算最小误差率e=self.G[i].train(self.W)#print self.G[i].t_val,self.G[i].t_b,e#计算弱分类器Gi的话语权(根据公式)self.alpha[i]=1/2*np.log((1-e)/e)#print self.alpha[i]#计算弱分类器Gi对样本的分类结果sg=self.G[i].pred(self.X)#计算归一化因子(计算样本权值时,保证权值之和为1)Z=self.W*np.exp(-self.alpha[i]*self.y*sg.transpose())#更新样本的权值self.W=(Z/Z.sum()).flatten(1)#记录迭代次数(从0开始)self.Q=i#print self.finalclassifer(i),'==========='#判断组合起来的强分类器的效果,如果没有错分,不在迭代if self.finalclassifer(i)==0:print i+1," weak classifier is enough to make the error to 0"breakdef finalclassifer(self,t):'''将第1个到第t个弱分类器组合起来(跟踪adaboost强分类器组合公式)'''#组合成强分类器,并直接计算出其对样本的分类结果(没有用sing函数计算前)self.sums=self.sums+self.G[t].pred(self.X).flatten(1)*self.alpha[t]#print self.sums#用sign对分类器计算出的值进行判别pre_y=sign(self.sums)#sums=np.zeros(self.y.shape)#for i in range(t+1):#sums=sums+self.G[i].pred(self.X).flatten(1)*self.alpha[i]#print sums#pre_y=sign(sums)#对分类结果计算对比,统计不相同个数,如果全分对则为0t=(pre_y!=self.y).sum()return tdef pred(self,test_set):test_set=np.array(test_set)#判断数据大小是否一样assert test_set.shape[0]==self.X.shape[0]sums=np.zeros((test_set.shape[1],1)).flatten(1) #计算分类器训练样本的结果for i in range(self.Q+1):sums=sums+self.G[i].pred(test_set).flatten(1)*self.alpha[i]print sums#用sign函数判断类别pre_y=sign(sums)return pre_y

adaboost_test.py:测试adaboost算法

# coding: UTF-8from __future__ import divisionimport numpy as npimport scipy as spfrom adaBoost import ADABCfrom weakclassify import WEAKC''' Example 0: this example is from the <统计学习方法>''''''X = np.array([0,1,2,3,4,5,6,7,8,9]).reshape(1,-1)y = np.array([1,1,1,-1,-1,-1,1,1,1,-1]).transpose()a= ADABC(X,y)a.train(5)''''''Example 1:this is example for 2 dimension'''X=np.array([[0.55,4.4],[1.1,2.8],[1.85,1.95],[3.15,1.7],[4,2.7],[3.75,3.95],[2.8,4.4],[2.35,3.2],[3.05,2.25],[3.55,2.6],[3.1,3],[3,3.4],[1,7.3],[1.4,6.7],[3.05,6.9],[4.3,7.15],[4.75,7],[5.5,5.85],[5.95,4.75],[6.45,3.15],[6.5,1.35],[6.3,0.95],[5.95,0.85],[5.95,1.6],[5.85,2.75],[5.65,4],[5.35,5.25],[5,6.15],[4.7,6.3],[3.85,6.5],[2.55,6.55],[1.4,6.65],[0.6,6.75],[0.6,6.85],[5.35,0.9]]).transpose()y=np.array([[-1],[-1],[-1],[-1],[-1],[-1],[-1],[-1],[-1],[-1],[-1],[-1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1],[1]]).transpose()a= ADABC(X,y)a.train(5)print a.pred([[0.55,1.1,5.35],[4.4,2.8,0.9]])

其余的两个模块如下:
**weakclassify.py:**弱分类器

# coding: UTF-8from __future__ import divisionimport numpy as npimport scipy as spclass WEAKC:def __init__(self,X,y):'''X is a N*M matrixy is a length M vectorM is the number of traincasethis weak classifier is a decision Stumpit's just a basic example from <统计学习方法>'''self.X=np.array(X)self.y=np.array(y)self.N=self.X.shape[0]def train(self,W,steps=100):'''W is a N length vector'''#print Wmin = 100000000000.0t_val=0;t_point=0;t_b=0;self.W=np.array(W)for i in range(self.N):q ,err = self.findmin(i,1,steps)if (err<min):min = errt_val = qt_point = it_b = 1for i in range(self.N):q ,err = self.findmin(i,-1,steps)if (err<min):min = errt_val = qt_point = it_b = -1self.t_val=t_valself.t_point=t_pointself.t_b=t_bprint self.t_val,self.t_point,self.t_breturn mindef findmin(self,i,b,steps):t = 0now = self.predintrain(self.X,i,t,b).transpose()err = np.sum((now!=self.y)*self.W)#print nowpgd=0buttom=np.min(self.X[i,:])up=np.max(self.X[i,:])mins=1000000;minst=0st=(up-buttom)/stepsfor t in np.arange(buttom,up,st):now = self.predintrain(self.X,i,t,b).transpose()#print now.shape,self.W.shape,(now!=self.y).shape,self.y.shapeerr = np.sum((now!=self.y)*self.W)if err<mins:mins=errminst=treturn minst,minsdef predintrain(self,test_set,i,t,b):test_set=np.array(test_set).reshape(self.N,-1)gt = np.ones((np.array(test_set).shape[1],1))#print np.array(test_set[i,:]*b)<t*bgt[test_set[i,:]*b<t*b]=-1return gtdef pred(self,test_set):test_set=np.array(test_set).reshape(self.N,-1)t = np.ones((np.array(test_set).shape[1],1))t[test_set[self.t_point,:]*self.t_b<self.t_val*self.t_b]=-1return t

sign.py:sign函数

import numpy as npimport scipy as spimport warnings#np.seterr(all='raise')def sign(x):#print x,'========='#print "======================="q=np.zeros(np.array(x).shape)q[x>=0]=1q[x<0]=-1return q

实验结果:得到了4个 弱分类器,4个弱分类器组合后,分类错误率为0。
如:3.763 0 1 表示,一条在x等于3.763的位置的 直线(弱分类器),0表示3.763在x轴上,1表示大于3.763为类别1,小于为类别-1.
虾米的4行三列的数据,用训练后的4的个弱分类器,求三个测试样本的 值。最后 的-1,-1,1。是将其组合成强分类器后,判断得到的 样本分类。

个人见解,难免有疏漏,欢迎讨论。

云游戏 UGameQt MQTT开发环境如何搭建UCDN违规事件处理说明 云分发 UCDN原来是没掌握这些代码Debug技巧React中的权限组件设计问题小结
AdaBoost的实际算法操作,使用adaboost算法解决一个现实生活中的分类问题 AdaBoost算法,adaboost算法优点
相关内容