数据挖掘算法学习（八）Adaboost算法

数据挖掘算法学习（八）Adaboost算法

来源：http://blog.csdn.net/iemyxie/article/details/40423907

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

算法概述

1、先通过对N个训练样本的学习得到第一个弱分类器；2、将分错的样本和其他的新数据一起构成一个新的N个的训练样本，通过对这个样本的学习得到第二个弱分类器；3、将1和2都分错了的样本加上其他的新样本构成另一个新的N个的训练样本，通过对这个样本的学习得到第三个弱分类器4、最终经过提升的强分类器。即某个数据被分为哪一类要由各分类器权值决定。

与boosting算法比较

使用加权后选取的训练数据代替随机选取的训练样本，这样将训练的焦点集中在比较难分的训练数据样本上；　　2. 将弱分类器联合起来，使用加权的投票机制代替平均投票机制。让分类效果好的弱分类器具有较大的权重，而分类效果差的分类器具有较小的权重。

与Boosting算法不同的是，AdaBoost算法不需要预先知道弱学习算法学习正确率的下限即弱分类器的误差，并且最后得到的强分类器的分类精度依赖于所有弱分类器的分类精度，这样可以深入挖掘弱分类器算法的能力。

算法步骤

给定训练样本集S，其中X和Y分别对应于正例样本和负例样本；T为训练的最大循环次数；2. 初始化样本权重为1/n ，即为训练样本的初始概率分布；　　3. 第一次迭代：(1)训练样本的概率分布相当，训练弱分类器;(2)计算弱分类器的错误率;(3)选取合适阈值，使得误差最小；(4)更新样本权重；　　经T次循环后，得到T个弱分类器，按更新的权重叠加，最终得到的强分类器。

具体步骤如下：

一.样本

Given: m examples (x1, y1), …, (xm, ym)
     where xiX, yiY={-1, +1}
     xi表示X中第i个元素，
     yi表示与xi对应元素的属性值，+1表示xi属于某个分类，
     -1表示xi不属于某个分类

二.初始化训练样本

xi的权重D(i) :i=1,……，m;
     (1).若正负样本数目一致，D1(i) = 1/m
     (2).若正负样本数目m+, m-则正样本D1(i) = 1/m+，
         负样本D1(i) = 1/m-

实例详解

图中“+”和“-”表示两种类别。我们用水平或者垂直的直线作为分类器进行分类。

算法开始前默认均匀分布D，共10个样本，故每个样本权值为0.1.

第一次分类：

第一次划分有3个点划分错误，根据误差表达式

计算可得e1=（0.1+0.1+0.1）/1.0=0.3

分类器权重：

然后根据算法把错分点的权值变大。对于正确分类的7个点，权值不变，仍为0.1,对于错分的3个点，权值为：

D1=D0*(1-e1)/e1=0.1*(1-0.3)/0.3=0.2333

第二次分类：

如图所示，有3个"-"分类错误。上轮分类后权值之和为：0.1_7+0.2333_3=1.3990

分类误差：e2=0.1*3/1.3990=0.2144

分类器权重a2=0.6493

错分的3个点权值为：D2=0.1*（1-0.2144）/0.2144=0.3664

第三次分类：

同上步骤可求得：e3=0.1365 ；a3=0.9223；D3=0.6326

最终的强分类器即为三个弱分类器的叠加，如下图所示：

每个区域是属于哪个属性，由这个区域所在分类器的权值综合决定。比如左下角的区域，属于蓝色分类区的权重为h1 中的0.42和h2 中的0.65，其和为1.07；属于淡红色分类区域的权重为h3 中的0.92；属于淡红色分类区的权重小于属于蓝色分类区的权值，因此左下角属于蓝色分类区。因此可以得到整合的结果如上图所示，从结果图中看，即使是简单的分类器，组合起来也能获得很好的分类效果。

分类器权值调整的原因

由公式可以看到，权值是关于误差的表达式。每次迭代都会提高错分点的权值，当下一次分类器再次错分这些点之后，会提高整体的错误率，这样就导致分类器权值变小，进而导致这个分类器在最终的混合分类器中的权值变小，也就是说，Adaboost算法让正确率高的分类器占整体的权值更高，让正确率低的分类器权值更低，从而提高最终分类器的正确率。

算法优缺点

优点

1)Adaboost是一种有很高精度的分类器2)可以使用各种方法构建子分类器,Adaboost算法提供的是框架3)当使用简单分类器时，计算出的结果是可以理解的。而且弱分类器构造极其简单4)简单，不用做特征筛选5)不用担心overfitting(过度拟合)

缺点

1)容易受到噪声干扰，这也是大部分算法的缺点

2)训练时间过长

3)执行效果依赖于弱分类器的选择

SQL实现

#开始迭代
while(@i<=3) do  
    set @evalue=0,@temp=0;
    set @flag1=0,@flag2=0,@flag3=0,@flag4=0;
    set @las=concat('d',@i-1);
    set @cur=concat('d',@i);
    set @a=concat('select hx,hy into @hx,@hy from hea where id = ',@i);
    prepare stmt1 from @a;
    execute stmt1;
    set @aa=concat('update adaset set ',@cur,' = ',@las);
    prepare stmt111 from @aa;
    execute stmt111;
#1.分类器为垂直x轴直线
    if (@hy=0) then
    #处理分类1
        set @b=concat('select count(class) into @l_1 from adaset where class=1 and x < ',@hx);
        prepare stmt2 from @b;
        execute stmt2;
        set @c=concat('select count(class) into @l_2 from adaset where class=-1 and x < ',@hx);
        prepare stmt3 from @c;
        execute stmt3;
        if(@l_1=0 and @l_2!=0) then
        set @clas=concat('update hea set l=-1 where id = ',@i);
        prepare stmt28 from @clas;
        execute stmt28;
        end if;
        if(@l_1!=0 and @l_2 =0) then
            set @clas=concat('update hea set l=1 where id = ',@i);
            prepare stmt29 from @clas;
            execute stmt29;
        end if;
        set @weight=concat('d',@i-1);
        if (@l_1 !=0 and @l_2 !=0 and @l_1>@l_2) then #@l_2是错分点
            set @d=concat('select sum(',@weight,') into @temp from adaset where class=-1 and x < ',@hx);
            prepare stmt4 from @d;
            execute stmt4;
            set @evalue=@evalue+@temp;
            set @flag1=1;
            set @clas=concat('update hea set l=1 where id = ',@i);
            prepare stmt20 from @clas;
            execute stmt20;
        end if;
        if (@l_1 !=0 and @l_2 !=0 and @l_1<@l_2) then #@l_1是错分点
            set @d=concat('select sum(',@weight,') into @temp from adaset where class=1 and x < ',@hx);
            prepare stmt5 from @d;
            execute stmt5;
            set @evalue=@evalue+@temp;
            set @flag2=1;
            set @clas=concat('update hea set l=-1 where id = ',@i);
            prepare stmt21 from @clas;
            execute stmt21;
        end if;
#总权值&误差
    set @h=concat('select sum(',@weight,') into @temp from adaset');
    prepare stmt10 from @h;
    execute stmt10;
    set @evalue = round(@evalue/@temp,4);
    set @avalue = round((0.5*ln((1-@evalue)/@evalue)),4);
    set @eee=round((1-@evalue)/@evalue,4);
#更新误差e&假设权重a
    set @j=concat('update hea set e = ',@evalue,' ,a = ',@avalue,' where id = ',@i);
    prepare stmt11 from @j;
    execute stmt11;
#更新错分样本的权重
    if (@hy=0) then
        if (@flag1=1) then
            set @k=concat('update adaset set ',@cur,' = ',@las,'*',@eee,' where class=-1 and x < ',@hx);
            prepare stmt12 from @k;
            execute stmt12;
        end if;
        if (@flag2=1) then
            set @m=concat('update adaset set ',@cur,' = ',@las,'*',@eee,' where class=1 and x < ',@hx);
            prepare stmt13 from @m;
            execute stmt13;
        end if;
        if (@flag3=1) then
            set @n=concat('update adaset set ',@cur,' = ',@las,'*',@eee,' where class=-1 and x > ',@hx);
            prepare stmt14 from @n;
            execute stmt14;
        end if;
        if (@flag4=1) then
            set @o=concat('update adaset set ',@cur,' = ',@las,'*',@eee,' where class=1 and x > ',@hx);
            prepare stmt15 from @o;
            execute stmt15;
        end if;
    end if;
set @i=@i+1;
end while;

以上是博主最近用SQL实现的Adaboost算法的部分代码。数据库表以后整理一下再贴。Ubuntu不稳定啊，死机两次了。。编辑的博客都没了。。累觉不爱。。

个人疑问

上文中的缺点提到，Adaboost算法的效果依赖于弱分类器的选择，那么面对巨大的待分类数据时，如何选择弱分类呢？有没有什么原则。博主依旧在探索中，找到答案的话会在这里更新。

推荐资料：由Adaboost算法创始人Freund和Schapire写的关于Adaboost算法的文档，我已经上传。

原文: https://wizardforcel.gitbooks.io/dm-algo-top10/content/adaboost.html

7. AdaBoost

数据挖掘算法学习（八）Adaboost算法