Average k-nearest neighbor distances

topK<-function(x,K)

{

n<-length(x);

l<-sample(1:n,1);

pivot<-x[l];

if(n<K | n==K) return(x);

idx<-c((1:n)[x>pivot],(1:n)[x==pivot]);

m<-length(idx);

if(m==n) { if(max(x)==min(x)) return(x[1:K]); }

if(m>K) { return(topK(x[idx],K));}

else if(m==K) { return(x[idx]);}

else

{

zL<-topK(x[-idx],(K-m));

return(c(x[idx],zL));

}

}

topKd<-function(x, k) {tmp<-topK(x,k); return(-1*min(tmp));}

infty<-10^20;

n<-1000;

tmp<-runif(2*n,0,1);

x<-matrix(tmp,n,2);

mdist1<-kronecker(x[,1],t(x[,1]),FUN="-");

mdist2<-kronecker(x[,2],t(x[,2]),FUN="-");

mdist<-mdist1*mdist1 + mdist2 * mdist2;

mdist<-sqrt(mdist);

diag(mdist)<-infty;

ks<-c(1,2,3,4,5,10,20,30,50,100);

maxKNNds<-matrix(0,length(ks),1);

for(i in 1:length(ks))

{

k<-ks[i];

cat("k=",k,"@ ", date(),"\n");

mindists<-apply(-mdist,1,function(x) topKd(x,k));

maxKNNds[i]<-mean(mindists);

}

plot(ks,maxKNNds,pch=18,type="b", col="blue",main="Average k-nearest neighbor distance",xlab="k",ylab="");