首页 > 模式识别 > Ababoost

Ababoost

2012年7月28日 发表评论 阅读评论

毕设时曾经有个模式识别的东西想用Adaboost算法来实现，然后自己就傻不溜秋的用matlab写了一个API，也是为了方便将来用，后来不但没用上这个算法，而且指导老师跟我说，你难道不知道有个软件叫weka么？？让后我就SB了。。。

不管怎么样，好歹是学过且用过的。

Adaboost的算法思想就是把许许多多的弱分类器合并起来，变成一个强分类器。

在二分类问题中，所谓弱分类器就是对于训练集里面，识别率略高于50%的分类器，其实就是比随机乱猜好一点的分类器，即便是51%的识别率我们也能称之为弱分类器。

好吧，为了科普一点。。所谓的分类器，就是由一个特征，一个方向，一个阈值组成的，比如说判断一幅图像是黑夜还是白天，我们可以选择一个特征，那就是图像的灰度图的平均值，这个叫特征值，假设我们把图像时白天成为1，黑夜成为-1，那么我们可以构建一个简单的分类器，就是灰度值大于125那么就是1，小于125就是-1，所以我们懂啦，大于还是小于那就是分类器的方向，125就是阈值。

一般模式识别里面的分类器都是这样的。只是一般对象的特征值不一定就是一个数，也可能是一个向量，或者一个矩阵。假设这个特征向量是[x1, x2, x3, x4…xn]，然后分类器就是判断f(x1, x2, x3, x4…xn)>θ。

而adaboost的思想就是三个臭皮匠赛过诸葛亮，通过把弱分类器级联起来，这样就得到一个强分类器。不懂？请看下图：

如果让你画一条线就把上图中红色和蓝色区别出来，那显然是不可能的，对不？

上面两种画法是 一把能想到的比较好的分类方法，虽然不是100%的分别率，但是还是超过50%的，然后呢，要怎么样才可以合成一个强分类器呢？

就是这样，哈哈，别说我开玩笑啦，好吧，我这里不想写表达式，看我这么说你们懂不懂吧，就是说我们现在有两个弱分类器，第一个弱分类器划出一条线，说上篮下红，（见上上图的前两个），我们认为这个分类器是f1(x,y)，它的阈值θ1 ，第二个弱分类器划出另一条线，说上篮下红（见上上图的后两个），我们认为这个分类器是f2(x,y)，它的阈值θ2。

然后现在有个点我想判断它属于红还是属于蓝，那我就分别用这个两个分类器判断一下，给个结果，假设如果分类器觉得是蓝那么它会输出1，否则它会输出-1。现在我们给两个分类器都赋予一个权值，假设是一个是0.4，一个是0.6，那么识别过程中，如果两个都认为是1，那么输出结果就是1，如果都认为是-1，那么结果显然也是-1，如果权重一个认为是1，一个认为是-1的话，那么就是要加权！

在上面那个例子中，假设我们认为第一个分类器的权重是0.6，第二个分类器的权重是0.4的话，那么上图中两条线把图分成4块，其中有三块是可以识别正确的，这样就比了两个弱分类器都要强，因为每个弱分类器都只能正确识别上图4块中的两块。

而我们的Adaboost算法就有两件事情要做，一是怎么样才可以寻找到好的弱分类器，二是怎么样分配权值才可以把强分类器的识别率提到最大！

我们的运算方法如下：

  1. 首先我们把每个训练样本都打上tag，也就是表明它是正样本还是负样本，为了表示特征值，我们用(x,y)来表示一个样本，其中x是特征值，加了粗表示不一定是一个数，也可能是一个向量，y=±1；
  2. 每个样本我们都设置一个权重，初始化为di = 1/N，其中N是总样本数。
  3. 在所有可能的分类器中我们需找一个最好的弱分类器hi，它在所有候选的分类器中具有最好的识别率。
  4. 计算这个弱分类器的误识别率ei，就是把所有错误识别的样本的权重相加。
  5. 然后我们就根据弱分类器的误识别率得到弱分类器的权重：
    \(\alpha_i=\dfrac{1}{2}ln\dfrac{1-e_i}{e_i}\)
  6. 接下来我们就要更新一下每个样本的权重，原则是这样的，就是如果分类器没有将其正确分类，那么我们认为这是一个重要的样本，后面机器学习过程中要重点对待，所以要提高他的权重，识别正确的话可以降低后面对它的重视程度，所以\(d’_i=d_ie^{-\alpha_iy_ih_i(x)}\),这个更新公式可以这么理解，如果hi分类分类正确的话，那么yihi(x)=1，否则等于-1，正确就降低样本权值，错误就提高权值，就是这样。
  7. 所有样本的权值归一化，就是让他们的和为1。
  8. 合成的强分类器就是\(\sum\alpha_ih_i(x)\)，如果对于所有测试样本，这个强分类器的分别率还没有达到要求，那么就回到步骤3，寻找一个新的弱分类器级联进来。不达目的不罢休！！
Adaboost的算法思想就是如上面所说，只要迭代次数足够多，测试样本足够丰富，那么就可以达到很高的精度！
function Adaboost()
% clc;
all_value = importdata('DTW_TWO_DIM_DIST_a_r_25.mat');%%训练数据
all_value = abs(all_value);
[m n] = size(all_value);
train_begin = [1 100];
test_begin = [101 110];
train_num = train_begin(2)-train_begin(1)+1;
test_num = test_begin(2)-test_begin(1)+1;

train_value = zeros(train_num*10,n);
test_value = zeros(test_num*10,n);
train_cc = 1;
test_cc = 1;
for i = 0:9
for j = 1 : 110
        if(j< =train_begin(2) && j>=train_begin(1))
            train_value(train_cc,:) = all_value(i*110+j,:);
            train_cc = train_cc + 1;
        end
        if(j< =test_begin(2) && j>=test_begin(1))
            test_value(test_cc,:) = all_value(i*110+j,:);
            test_cc = test_cc + 1;
        end
    end
end

judge = zeros(10,test_num*10);
for Number = 0 : 9
    target = zeros(1,train_num*10);
    target(Number*train_num+1:(Number+1)*train_num) = 1;
    target = target';
    [Flag Threshold Polarity Alpha] = AdaboostTrain(train_value,target,50);
    T = length(Flag);

    w_ans=zeros(1,test_num*10);
    newtarget=zeros(1,test_num*10);
    for k=1:test_num*10
        for i=1:T
            idx=Flag(i);
            value=test_value(k,idx);
            if Polarity(i)*value< Polarity(i)*Threshold(i)
                w_ans(k)=w_ans(k)+Alpha(i);
            else
                w_ans(k)=w_ans(k)-Alpha(i);
            end
        end
        if w_ans(k)>0
            newtarget(k)=1;
        else
            newtarget(k)=0;
        end
 end
    judge(Number+1,:) = w_ans;
end
save adaboost_result.mat judge;

% % delta=xor(target',newtarget);
% % figure;
% % sum(delta)
% % subplot(211);plot(w_ans);
% % subplot(212);plot(delta);

w = importdata('adaboost_result.mat');
judge = zeros(10,10);
for i = 1 : test_num*10
    temp = w(:,i);
    result = find(temp == max(temp));
    judge(floor((i-1)/test_num)+1,result) = judge(floor((i-1)/test_num)+1,result)+1;
end
judge
rate = zeros(1,10);
for i = 1 : 10
    rate(i) = judge(i,i)/sum(judge(i,:));
end

rate
mean(rate)

%%target:1 正样本 0 负样本
function [Flag Threshold Polarity Alpha] = AdaboostTrain(trainset,target,Iter)
[allnum feacture_dimem] = size(trainset);

weigth = ones(1,allnum)/allnum;
% weigth = zeros(1,allnum);
% weigth(target==1)  = 0.5/110;
% weigth(target==0)  = 0.5/990;

Threshold = zeros(1,Iter);
Flag=zeros(1,Iter);
Polarity=zeros(1,Iter);
Error =zeros(1,Iter);
Beta=zeros(1,Iter);

actual_iter_num = 0;
for ii = 1 : Iter
    ii
    actual_iter_num = actual_iter_num+1;
    error = 0.5;
    for k = 1 : feacture_dimem
        [bestThresh,bestParity,bestErr,ans_target] = weaklearner(trainset(:,k),weigth,target,allnum);
        if bestErr< =error&&bestErr~=0
            error=bestErr;
            Error(ii)=bestErr;
            Threshold(ii)=bestThresh;
           Flag(ii)=k;
           Polarity(ii)=bestParity;
           Beta(ii)= bestErr / (1 - bestErr);%
           new_target=ans_target;
       end
   end
    delta = xor(target,new_target);%if h(xi)yi = -1  delta=1;
    weigth = weigth .* (Beta(ii) .^ (1-delta'));
    weigth = weigth./sum(weigth);
    out=TestStrong(trainset,target,allnum,Threshold, Flag,Polarity,Beta,ii);

    if(out == 1)
        break;
    end
end
Threshold = Threshold(1:actual_iter_num);
Flag = Flag(1:actual_iter_num);
Polarity = Polarity(1:actual_iter_num);
Beta = Beta(1:actual_iter_num);
Alpha = log(1./Beta)/2;

function [bestThresh,bestParity,bestErr,ans_target]
 =weaklearner(data,weight,target,num)
% posWeight = sum(weigth(target==1));
% negWeight = sum(weigth(target==0));
posWeight=0;%正样本的权重之和
negWeight=0;
for i=1:num
    if target(i)==1
        posWeight=weight(i)+posWeight;
    elseif target(i)==0
        negWeight=weight(i)+negWeight;
    end
end

[data_sort,Idx]=sort(data);
lposweight=0;
lnegweight=0;
bestErr=0.5;
bestParity=0;
bestThresh=-1; 

for i = 2 : num
    if target(Idx(i-1))==1
        lposweight=weight(Idx(i-1))+lposweight;
    else
        lnegweight=weight(Idx(i-1))+lnegweight;
    end

    if ( lposweight+negWeight-lnegweight ) < bestErr
        bestErr = lposweight + negWeight - lnegweight;
        bestParity = -1; %分类器种类
        bestThresh = (data_sort(i) + data_sort(i-1)) / 2;%阈值
    elseif lnegweight+posWeight-lposweight < bestErr
        bestErr = lnegweight + posWeight - lposweight;
        bestParity = 1;
        bestThresh = (data_sort(i) + data_sort(i-1)) / 2;
    end
end
ans_target = (bestParity*data<bestParity*bestThresh);

function out=TestStrong(value_theta,target,num,Threshold, Flag,Polarity,Beta,T)
w_ans=zeros(1,num);
newtarget=zeros(1,num);
for k=1:num
    for i=1:T
        idx=Flag(i);
        value=value_theta(k,idx);
        if Polarity(i)*value< Polarity(i)*Threshold(i)
            w_ans(k)=w_ans(k)+log(1/Beta(i))/2;
        else
            w_ans(k)=w_ans(k)-log(1/Beta(i))/2;
        end
    end
    if w_ans(k)>0
        newtarget(k)=1;
    else
        newtarget(k)=0;
    end
end
delta=xor(target',newtarget);
out=0;
if sum(delta)< 1
    out=1;
end

【完】

本文内容遵从CC版权协议，转载请注明出自http://www.kylen314.com

分类: 模式识别 标签: , ,
  1. 御宅暴君
    2016年1月18日19:16 | #1
    回复 | 引用

    本科就做模式识别这么高大上的东西了。

  2. 御宅暴君
    2016年1月19日16:03 | #3
    回复 | 引用

    Boost classifiers 一共有四个：DAB – Discrete AdaBoost, RAB – Real AdaBoost, LB – LogitBoost, GAB – Gentle AdaBoost.

    不知你用的是哪一种。

  3. 御宅暴君
    2016年4月16日15:12 | #5
    回复 | 引用

    其实有 C++ 机器学习框架 mlpack 实现了 adaboost, 反正我不喜欢 Java.

验证码：4 + 7 = ?

友情提示：留言可以使用大部分html标签和属性;

添加代码示例:[code lang="cpp"]your code...[/code]

添加公式请用Latex代码，前后分别添加两个$$