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

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,\dots,b$,
   
   1. Pick up $m$ samples from a sample set with $n$ samples $\{ (x_{i},y_{i}) \}_{i=1}^{n}$. Repeating is permitted. Then we get a new sample set.
   2. Train the pruning classifier $\psi_{j}$ with the new sample set.
2. For all of the pruning classifiers $\{\psi_{j}\}_{j=1}^{b}$, calculate their average and get $f$: $$f(x)\leftarrow \frac{1}{b}\sum_{j=1}^{b}\psi_{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');