source: distools/nnerror.m

%NNERROR Exact expected NN error from a dissimilarity matrix (2)
%
%   E = NNERROR(D,M)
%
% INPUT
%   D   NxN dissimilarity dataset
%   M   Number of objects to be selected per class (optional)
%
% OUTPUT
%   E   Expected NN errror 
%
% DEFAULT
%   M = minimum class size minus 1
%
% DESCRIPTION
% An exact computation is made of the expected NN error for a random 
% selection of M for training. D should be a dataset containing a labeled 
% square dissimilarity matrix.

% Copyright: R.P.W. Duin, r.p.w.duin@prtools.org
% Faculty EWI, Delft University of Technology
% P.O. Box 5031, 2600 GA Delft, The Netherlands


function e = nnerror(D,n)
isdataset(D);
discheck(D);
nlab     = getnlab(D);
[m,mm,c] = getsize(D);

% Number of objects per class
nc = classsizes(D);

% Compute for all training set sizes
if nargin < 2
        n = min(nc)-1;
end

if length(n) > 1
        e = zeros(1,length(n));
        for j=1:length(n)
                e(j) = nnerror(D,n(j));
        end
else
        if n >= min(nc)
                error('Requested size of the training set is too large.')
        end
        % Call for the given sample size        
        [D,I] = sort(D);
        I     = reshape(nlab(I),m,m);   % Order objects according to their distances
        ee    = zeros(1,m);
        
        % Loop over all classes
        for j = 1:c
                % Find probabilities Q that objects of other classes are not selected
                Q = ones(m,m);
                for i = 1:c
                        if i~=j
                                [p,q] = nnprob(nc(i),n); 
                                q = [1,q];
                                C = cumsum(I==i)+1;
                                Q = Q.*reshape(q(C),m,m);
                        end
                end
                
                % Find probabilitues P for objects of this class to be the first
                [p,q] = nnprob(nc(j),n); 
                p = [0,p];
                C = cumsum(I==j)+1;
                P = reshape(p(C),m,m);

                % Now estimate the prob EC it is really the NN
                J     = find(I==j);
                EC    = zeros(m,m);
                EC(J) = P(J).*Q(J);
                
                % Determine its error contribution
                L     = find(nlab==j);
                ee(L) = 1-sum(EC(2:m,L))./(1-EC(1,L));  % Correct for the training size
        end

        % Average for the final result
        e = abs(mean(ee));
end



%NNPROB Probability of selection as the nearest neighbor
%
% [P,Q] = NNPROB(M,K)
%
% If K objects are selected out of M, then P(i) is the probability
% that the i-th object is the nearest neigbor and Q(i) is the probability
% that this object is not selected.

function [p,q] = nnprob(m,k)
p = zeros(1,m);
q = zeros(1,m);
q(1) = (m-k)/m;
p(1) = k/m;
for i=2:(m-k+1)
        q(i) = q(i-1)*(m-k-i+1)/(m-i+1);
        p(i) = q(i-1)*k/(m-i+1);
end