locboost.m

用于分类的一个工具箱

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);
train_indices   = 1:Nf;
test_indices    = [];
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            = [];

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(Niterations, Dims+1);
phi			= zeros(Niterations, Dims+Dims^2);
h			= ones(1,Nf);

phi(:,Dims+1:end) = ones(Niterations,Dims^2);

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

P           = LocBoostFunctions(theta(1,:), 'class_kernel', [train_patterns(:,train_indices); ones(1,Nf)], train_targets(train_indices)); 

%Find the local classifiers
for t = 2:Niterations,
    
    %Do inital guesses
    [phi_init, indices, dist]	= compute_initial_k_means_value(train_patterns(:,train_indices), (P<0.5), P, dist);
    
    if (isempty(indices))
        phi     = phi(1:t-1,:);
        theta   = theta(1:t-1,:);
        break
    end

    phi(t,:) = phi_init;
        
    [D, tmp_theta] = feval(Wtype, train_patterns(:,train_indices(indices)), train_targets(train_indices(indices)), train_patterns(:,1:2), Wparams);
    %[D, t_theta] = feval(Wtype, train_patterns(:,train_indices).*(ones(Dims,1)*LocBoostFunctions(phi(t,:), 'gamma_kernel', train_patterns(:,train_indices))),train_targets(train_indices)>0, train_patterns(:,1:2), Wparams);
    theta(t, 1:size(theta, 2)) = tmp_theta;
    
    opt_error(2) = 1;
    for i = 1:Nem,
        %Compute h(t-1)
        gamma_ker 	   = LocBoostFunctions(phi(t,:), 'gamma_kernel', train_patterns(:,train_indices), [], [], Dims);  %Gamma(x, gamma(C))
        class_ker      = LocBoostFunctions(theta(t,:), 'class_kernel', [train_patterns(:,train_indices); ones(1,Nf)], train_targets(train_indices)); 
        h_tminus1      = gamma_ker .* class_ker ./ ((1-gamma_ker).*P + gamma_ker.*class_ker);
        
        %Optimize theta(t,:) using first part of the Q function
        temp_theta     = fminsearch('LocBoostFunctions', theta(t,:), options, 'Q1', [train_patterns(:,train_indices(indices)); ones(1,length(indices))], train_targets(train_indices(indices)), h_tminus1(indices));
        %[d, temp_theta(1,1:size(theta,2))] = feval('LS', train_patterns(:,train_indices), train_targets(train_indices), train_patterns(:,1:2), h_tminus1);
        
        %Optimize gamma(t,:) using second part of the Q function
        %temp_phi       = fminsearch('LocBoostFunctions', phi(t,:), options, 'Q2',  train_patterns(:,train_indices(indices)), train_targets(train_indices(indices)), h_tminus1(indices), Dims);
        
        theta(t,:) = temp_theta;
        %phi(t,:)   = temp_phi;
    end
    
    oldP = P;
    %Compute new P function 
    gamma_ker	   = LocBoostFunctions(phi(t,:), 'gamma_kernel', train_patterns(:,train_indices), [], [], Dims);  
    class_ker     = LocBoostFunctions(theta(t,:), 'class_kernel', [train_patterns(:,train_indices); ones(1,Nf)], train_targets(train_indices)); 
    P             = (1-gamma_ker).*P + gamma_ker.*class_ker;
    
    disp(['Finished iteration number ' num2str(t-1)])

    if (sum(P==.5) == Nf),
       %Nothing more to do
       phi         = phi(1:t,:);
       theta       = theta(1:t,:);
       disp('P=0.5 for all indices')
       break
    end
    
end

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

if (length(unique(train_targets)) == 2)
    test_targets = test_targets > 0.5;
end

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

function [phi, indices, dist] = compute_initial_value(train_patterns, train_targets, P, 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)),
   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;

Uc           = unique(component);
n1      	 = hist(component, Uc);
[m, N]   	 = max(n1);
indices		 = find(component == Uc(N));

phi = zeros(1,Dim+Dim^2);
if (~isempty(indices))
    if (length(indices) == 1)
        means = train_patterns(:,indices);
        stds  = zeros(1, size(indices,2));
    else
        means = mean(train_patterns(:,indices)');
        stds  = std(train_patterns(:,indices)');
    end
    full_stds      = diag(stds);
    phi(1:Dim)     = means;
    phi(Dim+1:end) = full_stds(:);
else
    a=1;
end

%End

function [phi, indices, dist] = compute_initial_k_means_value(train_patterns, train_targets, P, dist)

[Dim,n] = size(train_patterns);

in      = find(train_targets == 1);

[patterns, targets, label] = k_means(train_patterns(:,in), train_targets(in), floor(n/50), 0);

Uc           = unique(label);
n1      	 = hist(label, Uc);
[m, N]   	 = max(n1);
indices		 = in(find(label == Uc(N)));

phi = zeros(1,Dim+Dim^2);
if (~isempty(indices))
    if (length(indices) == 1)
        means = train_patterns(:,indices);
        stds  = zeros(1, size(indices,2));
    else
        means = mean(train_patterns(:,indices)');
        stds  = std(train_patterns(:,indices)');
    end
    full_stds      = inv(diag(stds));
    phi(1:Dim)     = means;
    phi(Dim+1:end) = full_stds(:);
end