Question

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

算法概述

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

与 boosting 算法比较

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

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

算法步骤

1. 给定训练样本集 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.17+0.23333=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 算法的文档，我已经上传。