mb_knn.m

 function [Cmat,Crate,missed,info] = 
	mb_knn(train,trainclass,test,testclass,k) ;
% MB_KNN - k-Nearest Neighbor Classifier
% [CMAT CRATE MISSED INFO] = MB_KNN(TRAIN,TRAINCLASS,TEST,TESTCLASS,K) - 
%
%  Inputs:
%   train : Training data features, NUMTRAIN samples by NUMFEATURES features
%   trainclass : Training data classifications, NUMTRAIN by NUMCLASS
%   test : Test data features, NUMTEST samples by NUMFEATURES features
%   testclass : Test data classifications, NUMTEST by NUMCLASSES
%   k  : number of neighbors to consider
%
%  cmat   : confusion matrix
%  crate  : classification rate
%  missed : misclassified samples
%  info   : information about the misclassified samples
%
% Target vectors should look like:
%  class1 : 1 0 0 ... 0 0
%  class2 : 0 1 0 ... 0 0
%  ...
%  classN : 0 0 0 ... 0 1
%
%  Portions of this code are derived from knn.m by Yu Hen Hu, (c)1996.
%
% 15 Jan 99 - M.V. Boland

% $Id: mb_knn.m_tmp,v 1.1 1999/06/26 14:16:36 boland Exp $

%
% numtrain - number of training samples
% numtest - number of test samples
% numfeatures - number of features
% numclass - number of classes
%
[numtrain,numfeatures] = size(train) ;
[numtest,numclass] = size(testclass) ;


%
% NOTE: numclass==1 NOT tested -- M. Boland
if numclass==1,
  oneC=eye(numclass+1);
  testclass=[testclass ones(numtest,1)-testclass];  
	%  if C=1, change Or,Ot to 2 class format
  testclass=[testclass ones(numtrain,1)-trainclass]; 
else
%
% oneC is a C+1xC+1 identity matrix (+1 for the unknown class)
%
  oneC=eye(numclass+1);
end

class=[] ;
info.neighbors=[] ;

for i = 1:numtest,
	X = train-(ones(numtrain,1)*test(i,:)) ;
	d = sum((X .* X)') ;
%
% d contains the distances from each training sample to test sample i
%
   %  choose the minimum kN terms (k-nearest neighbor) of each column
   [y,sortidx]=sort(d);   % both y and sortidx are numtrain by 1, 
                          % first kN entries of idx
                          % give the indices of the kN nearest neighbors
   if k > 1,
%
% Sum the target vectors of the k nearest neighbors, identify the maximum
%
      numeachclass=sum(trainclass(sortidx(1:k),:)) ;
      [maxval,maxidx]=max(numeachclass);

%
% Confirm that the maximum is unique
%
      numeachclass(maxidx) = 0 ;
      [maxval2,maxidx2]=max(numeachclass);
      if(maxval2==maxval)
        class=[class;oneC(numclass+1,:)] ;
      else
        class=[class;oneC(maxidx,:)];
      end

%
% Collect information about what the nearest neighbors were
%
      info.neighbors=[info.neighbors ; sum(trainclass(sortidx(1:k),:))] ;

   else    % k=1
%
% Add to class the training target row of the nearest neighbor
%
      class=[class;trainclass(sortidx(1:k),:)];
   end
end % i-loop

%
% Misclassification Information
%  kclass - class assigned to each sample by kNN
%  trueclass - true classification (from input tc)
%  imiss - index into ti of misclassified samples
%
[max,kclass]    = max(class',[],1) ;
[max,trueclass] = max(testclass',[],1) ;
[val,imiss]     = find(kclass~=trueclass) ;
missed.index    = imiss ;
missed.true     = trueclass(imiss) ;
missed.assigned = kclass(imiss) ;

%
% form confusion matrix confusion (pad testclass to accomodate unknowns)
% confusion(i,j): class i is classified as class j
Cmat=[testclass zeros(size(testclass,1),1)]' * class ;  
%
% Delete the unknown row at the bottom
Cmat=Cmat(1:(end-1),:) ;
numunknown = sum(Cmat(:,end)) ;

Crate=[sum(diag(Cmat(:,1:(end-1))))*100/numtest ...
       sum(diag(Cmat(:,1:(end-1))))*100/(numtest-numunknown)] ;