function [mis_class] = cross_valid_knn(kmax,training_data)

% Computes the leave-one-out misclassification error rate for knn on 
% training_data for values of k from 1 to kmax. 

% OUTPUT:
% mis_class = vector of misclassification error rates from k=1:kmax


dim_x2 = size(training_data,2);

x = training_data(:,1:dim_x2-1); % training features
group = training_data(:,dim_x2); % training class labels

mis_class = zeros(kmax,1);
for i=1:kmax
    [k_nearest,class,misclass] = k_opt_cross_val(i,x,group);
    mis_class(i) = misclass;
end

%%%%%%%%%%%%%%%
    
function [k_nearest,class,misclass] = k_opt_cross_val(k,x,group)

[neigh_class,neigh_dist] = nearest_neighs_k(x,group);

[n1,I] = sort(neigh_dist,2); 

dimx = size(x,1);
class = zeros(dimx,1);

for i=1:dimx
    
    k_nearest = neigh_class(i,I(i,1:k));
    class(i) = mode(k_nearest);
    
end

misclass = sum(class~=group)/dimx;


%%%%%%%%%%%%%%%%%%%%%%%%%%%

function [neigh_class,neigh_dist,rho_max] = nearest_neighs_k(x,group)

% x = training data; k = # of classes; rho = cut-off dist
% neighs = matrix where column i corresponds to the neighbours of test point
% i among the training set.

dim_x = size(x,1);

big_dist=100000;

neigh_dist = zeros(dim_x,dim_x);

for i=1:dim_x    
    
    x_tmp = kron( x(i,:),ones(dim_x,1));
    dist_i = sum( (x_tmp-x).^2,2 ).^(0.5);
    neigh_dist(i,:) = dist_i';
    neigh_dist(i,i) = big_dist;

end

neigh_class = kron(group',ones(dim_x,1));
tmp = ones(dim_x,dim_x)-eye(dim_x,dim_x);
neigh_class = neigh_class.*tmp;
                                           % these lines find a reasonable maximal distance.
neigh_dist1 = neigh_dist - big_dist*eye(dim_x);             % a reasonable maximal radius is the median distance
distances = reshape(neigh_dist1,dim_x^2,1);  % between all possible pairs of points.
%s = find(distances); % Pick out non-zero distances.
%rho_max = median(s(distances));
dis = sort(distances);
rho_max = dis(round(size(dis,1)*0.75)); % 75% percentile of distances

