locboost.m

经典教材《机器学习》里的几乎所有算法 作者就是《机器学习》的2大牛人 有的函数添加了中文的注释 仅供参考

function [test_targets, P, theta, phi] = LocBoost(train_patterns, train_targets, test_patterns, params)

% Classify using the local boosting algorithm
% Inputs:
% 	train_patterns	- Train patterns
%	train_targets	- Train targets
%   test_patterns   - Test  patterns
%   params          - A vector containing the algorithm paramters:
%                     [Number of boosting iterations, number of EM iterations, Number of optimization iterations, Weak learner, Weak learner parameters]
%                     IMPORTANT: The weak learner must return a hyperplane parameter vector, as in LS
%
% Outputs
%	test_targets	- Predicted targets
%   P               - The probability function (NOT the probability for the train_targets!)
%	theta		    - Sub-classifier parameters
%	phi		        - Sub-classifier weights

test_percentage = 0.1;                  %Percentage of points to be used as a test set
[Dims, Nf]      = size(train_patterns);
Nt              = 0;
train_targets	= (train_targets > .5)*2-1;	%Set targets to {-1,1}
[Niterations, Nem, Noptim, Wtype, Wparams] = process_params(params);
Niterations		= Niterations + 1;
dist            = [];
errors          = ones(1, Niterations);
max_width       = 1e2;

%if ((Niterations < 1) | (Nem < 1) | (Noptim < 1)),
%   error('Iteration paramters must be positive!');
%end

options		= optimset('Display', 'off', 'MaxIter', Noptim);
  
%Find first iteration parameters
theta     	= zeros(1, Dims+1);
phi			= zeros(1, Dims+Dims^2);
h			= ones(1,Nf);
counter     = 1;

%Initial value is the largest connected component again all the others
[D, tmp_theta]                 = feval(Wtype, train_patterns, train_targets, train_patterns(:,1:2), Wparams);
theta(1, 1:size(tmp_theta, 2)) = tmp_theta;

P           = LocBoostFunctions(theta(1,:), 'class_kernel', [train_patterns; ones(1,Nf)], train_targets); 
errors(1)   = mean(P<.5);

%Find the local classifiers
for t = 2:Niterations,
    
    %Do inital guesses
    [components, dist]	= compute_initial_value(train_patterns, (P<0.5), dist);
    Uc                  = unique(components);
    if (length(Uc) > 1)
        Nc              = hist(components, Uc);
    else
        Nc              = length(components);
    end
    
    in                  = find(Uc>0);
    Uc                  = Uc(in);
    
    if (all(Nc(in) == 1))
        all_one = 1;
    else
        all_one = 0;
    end
    
    if isempty(components) 
        phi     = phi(1:counter,:);
        theta   = theta(1:counter,:);
        break
    end
    
    for i = 1:length(Uc),
        indices = find(components == Uc(i));
        
        %plot_process(train_patterns(:,indices),1)
        
        %if ((all_one == 0) & (length(indices) == 1))
        %    continue;
        %end
            
        counter = counter + 1;

        if (length(indices) > 1)
            means          = mean(train_patterns(:,indices)');
            sigma          = cov(train_patterns(:,indices)',1);
            if (cond(sigma) < 1e10)
               full_stds   = inv(sigma);
            else
                stds       = std(sigma);
                stds(find(stds==0)) = 1;
                if (cond(diag(stds)) < 1e10)
                    full_stds = inv(diag(stds.^2));
                else
                    full_stds = ones(Dims)*max_width;
                end
            end
        else
            means          = train_patterns(:,indices)';
            full_stds      = eye(Dims)*max_width;
        end
        phi(counter,1:Dims)     = means;
        phi(counter,Dims+1:end) = full_stds(:)';
        
        if (length(unique(train_targets(indices))) > 1)
            [D, theta(counter, 1:size(theta, 2))] = feval(Wtype, train_patterns(:,indices), train_targets(indices), train_patterns(:,1:2), Wparams);
        else
            theta(counter,:)   = 0;
            theta(counter,end) = unique(train_targets(indices))*10;
        end
        
        for i = 1:Nem,
            %Compute h(t-1)
            gamma_ker 	   = LocBoostFunctions(phi(counter,:), 'gamma_kernel', train_patterns, [], [], Dims);  %Gamma(x, gamma(C))
            class_ker      = LocBoostFunctions(theta(counter,:), 'class_kernel', [train_patterns; ones(1,Nf)], train_targets); 
            h_tminus1      = gamma_ker .* class_ker ./ ((1-gamma_ker).*P + gamma_ker.*class_ker);
        
            %Optimize theta(t,:) using first part of the Q function
            if (length(unique(train_targets(indices))) > 1)
                temp_theta     = fminsearch('LocBoostFunctions', theta(counter,:), options, 'Q1', [train_patterns; ones(1,Nf)], train_targets, h_tminus1);
            else
               temp_theta      = zeros(1,Dims+1);
               temp_theta(end) = unique(train_targets(indices))*10;
            end         
                %[d, temp_theta(1,1:size(theta,2))] = feval('LS', train_patterns, train_targets, train_patterns(:,1:2), h_tminus1);
        
            %Optimize gamma(t,:) using second part of the Q function
            %temp_phi       = fmincon('LocBoostFunctions', phi(t,:), [], [], [], [], lb, [], [], options, 'Q2',  train_patterns, train_targets, h_tminus1, Dims);
            temp_phi       = fminsearch('LocBoostFunctions', phi(counter,:), options, 'Q2',  train_patterns, train_targets, h_tminus1, Dims);
        
            theta(counter,:) = temp_theta;
            phi(counter,:)   = temp_phi;
        end
    
        oldP = P;
        %Compute new P function 
        gamma_ker	   = LocBoostFunctions(phi(counter,:), 'gamma_kernel', train_patterns, [], [], Dims);  
        class_ker     = LocBoostFunctions(theta(counter,:), 'class_kernel', [train_patterns; ones(1,Nf)], train_targets); 
        P             = (1-gamma_ker).*P + gamma_ker.*class_ker;
    
        errors(counter)     = mean(P<.5);
    
        %figure(2)
        %contourf(reshape(LocBoostFunctions(phi(1:counter,:), 'NewTestSet', test_patterns, ones(1, size(test_patterns,2)), [], theta(1:counter,:))>.5,100,100))
        %figure(1)
        disp(['Finished iteration number ' num2str(counter-1) '. Incorrectly classified on train set: ' num2str(sum(P<.5)/length(P))])
        
        
        if (sum(P>.5) == Nf),
           %Nothing more to do
           phi         = phi(1:counter,:);
           theta       = theta(1:counter,:);
           disp('P>0.5 for all indices')
           break
       end
    end
    
end

[m, cut] = min(errors); cut = cut(1);
phi      = phi(1:cut,:);
theta    = theta(1:cut,:);

%Classify test patterns
test_targets = LocBoostFunctions(phi, 'NewTestSet', test_patterns, ones(1, size(test_patterns,2)), [], theta);
test_targets = test_targets > 0.5;

%end LocBoost
%*********************************************************************

function [component, dist] = compute_initial_value(train_patterns, train_targets, dist)

%Returns the initial guess by connected components

[Dim,n] = size(train_patterns);

% Compute all distances, if it has not been done before
if (isempty(dist)),
    dist = zeros(n);
    for i = 1:n,
      dist(i,:) = sum((train_patterns(:,i)*ones(1,n) - train_patterns).^2);
    end
end

ind_plus	= find(train_targets == 1);
size_plus   = length(ind_plus);

G = zeros(n);
for i=1:size_plus   
   [o,I] = sort(dist(ind_plus(i),:));
   for j=1:n
      if (train_targets(I(j)) == 1),
         G(ind_plus(i),I(j)) = 1;
         G(I(j),ind_plus(i)) = 1;
      else
         break
      end
   end
end
G = G - (tril(G).*triu(G)); %Remove main diagonal

if ~all(diag(G)) 
    [p,p,r,r] = dmperm(G|speye(size(G)));
else
    [p,p,r,r] = dmperm(G);  
end;
 
% Now the i-th component of G(p,p) is r(i):r(i+1)-1.
sizes   = diff(r);        % Sizes of components, in vertices.
k       = length(sizes);      % Number of components.
 
% Now compute an array "blocks" that maps vertices of G to components;
% First, it will map vertices of G(p,p) to components...
component           = zeros(1,n);
component(r(1:k))   = ones(1,k);
component           = cumsum(component);
 
% Second, permute it so it maps vertices of A to components.
component(p) = component;

component    = component .* train_targets; %Mark all correctly assigned targets as zeros