%KNNC K-Nearest Neighbor Classifier
%
%   [W,K,E] = KNNC(A,K)
%   [W,K,E] = KNNC(A)
%
% INPUT
%   A  Dataset
%   K  Number of the nearest neighbors (optional; default: K is 
%      optimized with respect to the leave-one-out error on A)
%
% OUTPUT
%   W  k-NN classifier 
%   K  Number of the nearest neighbors used
%   E  The leave-one-out error of the KNNC
%
% DESCRIPTION  
% Computation of the K-nearest neighbor classifier for the dataset A. 
% The resulting classifier W is automatically evaluated by KNN_MAP.
%
% Warning: class prior probabilities in A are neglected.
%
% SEE ALSO (<a href="http://37steps.com/prtools">PRTools Guide</a>)
% MAPPINGS, DATASETS, KNN_MAP

% Copyright: R.P.W. Duin, duin@ph.tn.tudelft.nl
% Faculty of Applied Physics, Delft University of Technology
% P.O. Box 5046, 2600 GA Delft, The Netherlands

% $Id: knnc.m,v 1.4 2007/04/13 09:29:57 duin Exp $

function [W,knn,e,ek] = knnc(a,knn)

		if (nargin < 2)
      prwarning(4,'Number of nearest neighbors not supplied, optimized wrt the leave-one-out error.');
      knn = [];
   end

	% No input data, return an untrained classifier.
	if (nargin == 0) | (isempty(a))
		W = prmapping('knnc',knn);
		if (isempty(knn))
			W = setname(W,'K-NN');
		else
			W = setname(W,[num2str(knn) '-NN']);
		end
		return; 
	end

	islabtype(a,'crisp','soft');
	isvaldfile(a,1,2); % at least 1 object per class, 2 classes
	a = testdatasize(a);
	a = testdatasize(a,'objects');
	
	a = seldat(a);    % get labeled objects only
	[m,k,c] = getsize(a);
	nlab = getnlab(a);

	if (isempty(knn))							

		% Optimize knn by the LOO procedure.
		[num,bat] = prmem(m,m);
		z = zeros(1,m);
		N = zeros(c,m);
    s = sprintf('Compute distance matrix in %i batches: ',num);
    prwaitbar(num,s);
		for i = 0:num-1							% Compute the distance matrix part by part
      prwaitbar(num,i+1,[s int2str(i+1)]);
			if (i == num-1)						% depending on the available memory.
				nn = m - num*bat + bat;
			else
				nn = bat;
			end
			I = [i*bat+1:i*bat+nn];
			D=+distm(a,a(I,:));         
			[Y,L] = sort(D);					% Sort in columns.

      % L are the labels of the nearest-to-further neighbors for the objects from I.
			L = nlab(L)';							
			Ymax = zeros(nn,m);       
			Yc = zeros(nn,m);
			if islabtype(a,'soft')
				error('Soft labels not yet allowed for optimisation of k')
			end
			for j = 1:c
				Y = +(L == j);				  % Mark by 1 the positions of the class j in 
				for n = 3:m             % the ordered distances to the objects from I.  
					Y(:,n) = Y(:,n-1) + Y(:,n);
				end
				% Y is NN x M; for objects from I, Y(:,P) counts all the objects 
				% from the class j that are within the first P nearest neighbors.
				Y(:,1) = zeros(nn,1);   
				J = Y > Ymax;						% J is the index of the 'winning' class 
				Ymax(J) = Y(J);					% within the first nearest neighbors.
				Yc(J) = j*ones(size(Yc(J)));
			end
			z = z + sum(Yc == repmat(nlab(I),1,m),1); % number of objects correctly classified for knn = 0,1,2,...
    end
    prwaitbar(0);

		name = 'K-NN';
		[e,knn] = max(z); % select best neighborhood size
		knn = knn-1;      % correct for leave-one-out
		knn = max(knn,1); % correct for pathological case knn = 0 (it appeared to exist!: all objects were
		                  % incorrectly classified for all neighbood sizes).
		e = 1 - e/m;
		ek = 1 - z/m;
		ek(1) = []; 
	
	else													% knn is fixed
		if (knn > m)
			error('The number of neighbors should not be larger than number of training objects.')
		end
		if (nargout > 2)
			e = testk(a,knn);
		end
		name = [num2str(knn) '-NN'];
	end

	W = prmapping('knn_map','trained',{a,knn},getlablist(a),k,c);
	W = setname(W,name);
	W = setcost(W,a);

return