Adaboost原理算法应用及源程序.doc

Adaboost原理、算法、应用及源程序
引言:
古语言:三个臭皮匠,顶个诸葛亮。很早就想过通过组合弱分类器来实现一个强分类器的问题。当学习到线性分类器以及著名的决策树之类分类器后,很容易联想到高中时代线性规划里面对不少区域的划分。要是能够找到一种方法,组合这些简单的直线方程,不就可以实现“山寨诸葛亮”的理想?
实际上,在Kearns和Valiant在1989年大作中指出了这种算法的可行性。而后,Freund在1990年以及他和Schapire在1994-1996年提出了boosting整个算法思路,似乎这种算法走到了实际应用的开端。然而直到AdaBoost被viola在其人脸识别系统中运用(2001Viola和Jones),这种方法才彻底开始暴火。在NIPS会议tutorial中,也可以看到Schapire神采奕奕的样子了。
Adaboost实际具体解决了两个问题:
怎么处理训练样本?
在AdaBoost中,每个样本都被赋予一个权重。如果某个样本没有被正确分类,它的权重就会被提高, 反之则降低。这样, AdaBoost方法将注意力更多地放在“难分”的样本上。
怎么合并若分类器成为一个强分类器?
强分类器表示为若干弱分类器的线性加权和形式, 准确率越高的弱学习机权重越高。
算法介绍:
通过研究在Schapire的大作中提到了一个Toy Game的例子,这里给出了一个类似的Matlab代码。终于感到了这个算法强大。
首先是程序需要产生一些随机的样本数据,然后分别调用其他的matlab函数实现分类结果输出。代码如下:
clear all
clc
tr_n=200; %the population of the train set
te_n=200; %the population of the test set
weak_learner_n=20; %the population of the weak_learner
tr_set=[1,5;2,3;3,2;4,6;4,7;5,9;6,5;6,7;8,5;8,8];
te_se=[1,5;2,3;3,2;4,6;4,7;5,9;6,5;6,7;8,5;8,8];
tr_labels=[2,2,1,1,2,2,1,2,1,1];
te_labels=[2,2,1,1,2,2,1,2,1,1];
figure;
subplot(2,2,1);
hold on;axis square;
indices=tr_labels==1;
plot(tr_set(indices,1),tr_set(indices,2),'b*');
indices=~indices;
plot(tr_set(indices,1),tr_set(indices,2),'r*');
title('Training set');
subplot(2,2,2);
hold on;axis square;
indices=te_labels==1;
plot(te_set(indices,1),te_set(indices,2),'b*')3
;
indices=~indices;
plot(te_set(indices,1),te_set(indices,2),'r*');
title('Training set');
% Training and testing error rates
tr_error=zeros(1,weak_learner_n);
te_error=zeros(1,weak_learner_n);
for i=1:weak_learner_n
adaboost_model=adaboost_tr(***@threshold_tr,***@threshold_te,tr_set,tr_labels,i);
[L_tr,hits_tr]=adaboost_te(adaboost_model,***@threshold_te,te_set,te_labels);
tr_error(i)=(tr_n-hits_tr)/tr_n;
[L_te,hits_te]=adaboost_te(adaboost_model,***@threshold_te,te_set,te_labels);
te_error(i)=(te_n-hits_te)/te_n;
end
subplot(2,2,3);
plot(1:weak_learner_n,tr_error);
axis([1,weak_learner_n,0,1]);
title('Training Error');
xlabel('weak classifier number');