Bagging (Bootstrap Aggregation)

Pruning Classification is one of the simplest classification algorithms. It works just like if-then. However, when aggregating a lot of prunnings we are able to create a powerful classifier.

The process of Bagging based on pruning is really simple but not trivial:

1. For j=1,…,b,
   
   1. Pick up m samples from a sample set with n samples {(xi,yi)}ni=1. Repeating is permitted. Then we get a new sample set.
   2. Train the pruning classifier ψj with the new sample set.
2. For all of the pruning classifiers {ψj}bj=1, calculate their average and get f:
   f(x)←1b∑j=1bψj(x)

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

for j=1:b
    db=ceil(2*rand); r=ceil(n*rand(n,1));
    xb=x(r,:); yb=y(r); [xs,xi]=sort(xb(:,db));
    el=cumsum(yb(xi)); eu=cumsum(yb(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)); Y=Y+sign(s*(X(:,:,db)-c))/b;
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');