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 allclctr_n=200; %the population of the train sette_n=200; %the population of the test setweak_learner_n=20; %the population of the weak_learnertr_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 ratestr_error=zeros(1,weak_learner_n);te_error=zeros(1,weak_learner_n);for i=1:weak_learner_nadaboost_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;endsubplot(2,2,3);plot(1:weak_learner_n,tr_error);axis([1,weak_learner_n,0,1]);title(Training Error);xlabel(weak classifier number);ylabel(error rate);grid on;subplot(2,2,4);axis square;plo