集成剪枝分类算法的Adaboost集成学习算法示例

Adaboost (Adaptive Boosting) Classifier

Boosting algorithms try to aggregate a couple of poor classifiers by order to make a powerful one. They assign weights to every labeled sample. When one of the poor classifier fails to correctly classify a sample, the weight of that sample is boosted. Then it tries another poor classifier.
Let’s take Adaboost and Pruning algorithms for example:

1. For the training set $\{ (x_{i},y_{i})\}_{i=1}^{n}$, initialize their weights $\{w_{i}\}_{i=1}^{n}$ as $1/n$. And let $f\leftarrow 0$.
2. For $j=1,\dots,b$:
   
   1. Based on current sample weights $\{w_{i}\}_{i=1}^{n}$, pick up the classifier with the smallest weighted error rate $R$: $$\varphi_{j}=\arg\min_{\varphi}R(\varphi),\quad R(\varphi)=\sum_{j=1}^{n}\frac{w_{i}}{2}\left( 1-\varphi(x_{i})y_{i} \right)$$
   2. Calculate the weight of classifier $\varphi_{j}$: $$\theta_{j}=\frac{1}{2}\log\frac{1-R(\varphi_{j})}{R(\varphi_{j})}$$
   3. Update the aggregated classifier $f$: $$f\leftarrow f+\theta_{j}\varphi_{j}$$
   4. Update the weights of samples $\{w_{i}\}_{i=1}^{n}$: $$w_{i}\leftarrow \frac{\exp(-f(x_{i})y_{i})}{\sum_{k=1}^{n}\exp(-f(x_{k})y_{k})},\quad \forall i=1,2,\dots,n$$

n=50; x=randn(n,2); 
y=2*(x(:,1)>x(:,2))-1;
b=5000; a=50; Y=zeros(a,a);
yy=zeros(size(y)); w=ones(n,1)/n;
X0=linspace(-3,3,a);
[X(:,:,1), X(:,:,2)]=meshgrid(X0);

for j=1:b
    wy=w.*y; d=ceil(2*rand); [xs,xi]=sort(x(:,d)); 
    el=cumsum(wy(xi)); eu=cumsum(wy(xi(end:-1:1)));
    e=eu(end-1:-1:1)-el(1:end-1);
    [em,ei]=max(abs(e)); c=mean(xs(ei:ei+1));s=sign(e(ei));
    yh=sign(s*(x(:,d)-c)); R=w'*(1-yh.*y)/2;
    t=log((1-R)/R)/2; yy=yy+yh*t; w=exp(-yy.*y); w=w/sum(w);
    Y=Y+sign(s*(X(:,:,d)-c))*t;
end

figure(1); clf; hold on; axis([-3,3,-3,3]);
colormap([1 0.7 1; 0.7 1 1]);
contourf(X0,X0,sign(Y));
plot(x(y==1,1),x(y==1,2),'bo');
plot(x(y==-1,1),x(y==-1,2),'rx');