adaboost算法原理

AdaboostAdaboost算法的原理与推导2目录123Adaboost算法基础Adaboost算法原理Adaboost算法示例Adaboost31Adaboost算法基础Adaboost分类是数据挖掘的一种非常重要的方法。分类的概念是在已有数据的基础上学会一个分类函数或构造出一个分类模型（即：分类器(Classifier)）。该函数或模型能够把数据库中的数据纪录映射到给定类别中的某一个，从而可以应用于数据预测。总之，分类器是数据挖掘中对样本进行分类的方法的统称，包含决策树、逻辑回归、朴素贝叶斯、神经网络等算法。1.1分类器41Adaboost算法基础Adaboost1.2强分类器、弱分类器分类器的强弱是其分类能力的一种描述。能够迅速正确的识别的过程就是强分类器，而易错的则是弱分类器(基本分类器)。强分类器可以由多个弱分类器组成。51Adaboost算法基础Adaboost1.3分类器训练基本分类器1G1(X)弱分类器nGn(x)弱分类器i+1Gi+1(x)弱本分类器iGi(x)弱分类器2G2(X)......权重a1权重an权重ai+1权重ai权重a2样本1样本2样本i样本i+1样本n......强分类器f(x)=∑Gi(x)*ai分类器训练过程62Adaboost算法原理AdaboostAdaBoost，是英文AdaptiveBoosting（自适应增强）的缩写，由YoavFreund和RobertSchapire在1995年提出。它的自适应在于：前一个基本分类器分错的样本会得到加强，加权后的全体样本再次被用来训练下一个基本分类器。针对同一个训练集训练不同的分类器(弱分类器)，然后把这些弱分类器集合起来，构成一个更强的最终分类器(强分类器)，同时，在每一轮中加入一个新的弱分类器，直到达到某个预定的足够小的错误率或达到预先指定的最大迭代次数。2.1Adaboost是什么7Adaboost步骤1、初始化训练数据的权值分布。如果有N个样本，则每一个训练样本最开始时都被赋予相同的权重：1/N。2、训练弱分类器。具体训练过程中，如果某个样本点已经被准确地分类，那么在构造下一个训练集中，它的权重就被降低；相反，如果某个样本点没有被准确地分类，那么它的权重就得到提高。然后，权重更新过的样本集被用于训练下一个分类器，整个训练过程如此迭代地进行下去。3、将各个训练得到的弱分类器组合成强分类器。各个弱分类器的训练过程结束后，加大分类误差率小的弱分类器的权重，使其在最终的分类函数中起着较大的决定作用，而降低分类误差率大的弱分类器的权重，使其在最终的分类函数中起着较小的决定作用。换言之，误差率低的弱分类器在最终分类器中占的权重较大，否则较小。8给定一个训练数据集T={(x1,y1),(x2,y2)…(xN,yN)}，其中实例，而实例空间，yi属于标记集合{-1,+1}，Adaboost的目的就是从训练数据中学习一系列弱分类器或基本分类器，然后将这些弱分类器组合成一个强分类器。2Adaboost的原理Adaboost2.2Adaboost算法流程9Adaboost步骤1初始化训练数据的权值分布。每一个训练样本最开始时都被赋予相同的权重：1/N。10c.计算Gm(x)的系数，am表示Gm(x)在最终分类器中的重要程度（目的：得到基本分类器在最终分类器中所占的权重）：（这里的log表示ln，的推导式在《统计学习方法》第八章）由上述式子可知，em=1/2时，am=0，且am随着em的减小而增大，意味着分类误差率越小的基本分类器在最终分类器中的作用越大Adaboost步骤2进行多轮迭代，用m=1,2,...,M表示迭代的第多少轮a.使用具有权值分布Dm的训练数据集学习，得到基本分类器：由上述式子可知，Gm(x)在训练数据集上的误差率em就是被Gm(x)误分类样本的权值之和。b.计算Gm(x)在训练数据集上的分类误差率（这里相当于概率论里面的数学期望：E=∑Xi*Pi）由上述式子可知，Gm(x)在训练数据集上的误差率em就是被Gm(x)误分类样本的权值之和。d.更新训练数据集的权值分布（目的：得到样本的新的权值分布），用于下一轮迭代使得被基本分类器Gm(x)误分类样本的权值增大，而被正确分类样本的权值减小。就这样，通过这样的方式，AdaBoost方法能“聚焦于”那些较难分的样本上。其中，Zm是规范化因子，使得Dm+1成为一个概率分布：Zm的推导过程在《统计学习方法》第六章：最大熵模型11Adaboost步骤3组合各个弱分类器：从而得到最终分类器，如下：123Adaboost算法示例Adaboost初步分析下面，给定下列训练样本，请用AdaBoost算法学习一个强分类器。求解过程：初始化训练数据的权值分布，令每个权值W1i=1/N=0.1，其中，N=10，i=1,2,...,10，然后分别对于m=1,2,3,...等值进行迭代。拿到这10个数据的训练样本后，根据X和Y的对应关系，要把这10个数据分为两类，一类是“1”，一类是“-1”，根据数据的特点发现：“012”这3个数据对应的类是“1”，“345”这3个数据对应的类是“-1”，“678”这3个数据对应的类是“1”，9是比较孤独的，对应类“-1”。抛开孤独的9不讲，“012”、“345”、“678”这是3类不同的数据，分别对应的类是1、-1、1，直观上推测可知，可以找到对应的数据分界点，比如2.5、5.5、8.5将那几类数据分成两类。当然，这只是主观臆测，下面实际计算下这个过程。13Adaboost对于m=1，在权值分布为D1（10个数据，每个数据的权值皆初始化为0.1）的训练数据上，经过计算可得：阈值v取2.5时误差率为0.3（x2.5时取1，x2.5时取-1，则678分错，误差率为0.3），阈值v取5.5时误差率最低为0.4（x5.5时取1，x5.5时取-1，则345678皆分错，误差率0.6大于0.5，不可取。故令x5.5时取1，x5.5时取-1，则0129分错，误差率为0.4），阈值v取8.5时误差率为0.3（x8.5时取1，x8.5时取-1，则345分错，误差率为0.3）。所以无论阈值v取2.5，还是8.5，总得分错3个样本，故可任取其中任意一个如2.5，弄成第一个基本分类器为：从而得到G1(x)在训练数据集上的误差率（被G1(x)误分类样本“678”的权值之和）e1=P(G1(xi)≠yi)=3*0.1=0.3。然后根据误差率e1计算G1的系数：这个a1代表G1(x)在最终的分类函数中所占的权重，为0.4236。迭代过程114Adaboost迭代过程1接着更新训练数据的权值分布，用于下一轮迭代：值得一提的是，由权值更新的公式可知，每个样本的新权值是变大还是变小，取决于它是被分错还是被分正确。即如果某个样本被分错了，则yi*Gm(xi)为负，负负等正，结果使得整个式子变大（样本权值变大），否则变小。第一轮迭代后，最后得到各个数据新的权值分布D2=(0.0715,0.0715,0.0715,0.0715,0.0715,0.0715,0.1666,0.1666,0.1666,0.0715)。由此可以看出，因为样本中是数据“678”被G1(x)分错了，所以它们的权值由之前的0.1增大到0.1666，反之，其它数据皆被分正确，所以它们的权值皆由之前的0.1减小到0.0715。分类函数f1(x)=a1*G1(x)=0.4236G1(x)。此时，得到的第一个基本分类器sign(f1(x))在训练数据集上有3个误分类点（即678）。从上述第一轮的整个迭代过程可以看出：被误分类样本的权值之和影响误差率，误差率影响基本分类器在最终分类器中所占的权重。15Adaboost迭代过程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.1666*3（x2.5时取1，x2.5时取-1，则678分错，误差率为0.1666*3），阈值v取5.5时误差率最低为0.0715*4（x5.5时取1，x5.5时取-1，则0129分错，误差率为0.0715*3+0.0715），阈值v取8.5时误差率为0.0715*3（x8.5时取1，x8.5时取-1，则345分错，误差率为0.0715*3）。所以，阈值v取8.5时误差率最低，故第二个基本分类器为：面对的还是下述样本：很明显，G2(x)把样本“345”分错了，根据D2可知它们的权值为0.0715,0.0715,0.0715，所以G2(x)在训练数据集上的误差率e2=P(G2(xi)≠yi)=0.0715*3=0.2143。16Adaboost迭代过程2计算G2的系数：更新训练数据的权值分布：D3=(0.0455,0.0455,0.0455,0.1667,0.1667,0.01667,0.1060,0.1060,0.1060,0.0455)。被分错的样本“345”的权值变大，其它被分对的样本的权值变小。f2(x)=0.4236G1(x)+0.6496G2(x)此时，得到的第二个基本分类器sign(f2(x))在训练数据集上有3个误分类点（即345）。17Adaboost迭代过程3对于m=3，在权值分布为D3=(0.0455,0.0455,0.0455,0.1667,0.1667,0.01667,0.1060,0.1060,0.1060,0.0455)的训练数据上，经过计算可得：阈值v取2.5时误差率为0.1060*3（x2.5时取1，x2.5时取-1，则678分错，误差率为0.1060*3），阈值v取5.5时误差率最低为0.0455*4（x5.5时取1，x5.5时取-1，则0129分错，误差率为0.0455*3+0.0715），阈值v取8.5时误差率为0.1667*3（x8.5时取1，x8.5时取-1，则345分错，误差率为0.1667*3）。所以阈值v取5.5时误差率最低，故第三个基本分类器为（下图画反了，待后续修正）：依然还是原样本：此时，被误分类的样本是：0129，这4个样本所对应的权值皆为0.0455，所以G3(x)在训练数据集上的误差率e3=P(G3(xi)≠yi)=0.0455*4=0.1820。5.5,15.5,1xG3xx）（18Adaboost迭代过程3计算G3的系数：更新训练数据的权值分布：D4=(0.125,0.125,0.125,0.102,0.102,0.102,0.065,0.065,0.065,0.125)。被分错的样本“0129”的权值变大，其它被分对的样本的权值变小。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)]。19谢谢！Adaboost