4
\$\begingroup\$

I have implemented the K-Nearest Neighbor algorithm with Euclidean distance in R. It works fine but takes tremendously huge time than the library function (get.knn). Please point out the possibility of improvement.

knn<-function(list,k){
  n=nrow(list)
  if (n<=k) stop("k can not be more than n-1")
  neigh<- matrix(0,nrow=n,ncol=k)
  for(i in 1:n){
    dist<-matrix(0,ncol=2,nrow=n)
    for (j in 1:n){
      dist[j,1]<-j
      dist[j,2]<-sum((list[i,]-list[j,])^2)
      #dist[j,2]<-dtw(list[i,],list[j,])$distance
    }
    sorted<-dist[order(dist[,2]),]
    neigh[i,]<-sorted[2:(k+1),1]
  }
  return(neigh)
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Could you please clarify a couple things: is list a matrix and what are its typical dimensions? \$\endgroup\$
    – flodel
    Commented Jun 23, 2015 at 10:34

1 Answer 1

3
\$\begingroup\$

You can improve your code by using vectorization to speed up the computation of Euclidean distances in the inner loop. The code would be:

knn <- function(mat, k){
   n <- nrow(mat)
   if (n <= k) stop("k can not be more than n-1")
   neigh <- matrix(0, nrow = n, ncol = k)
   for(i in 1:n) {
      euc.dist <- colSums((mat[i, ] - t(mat)) ^ 2)  
      neigh[i, ] <- order(euc.dist)[2:(k + 1)]
   }
   return(neigh)
}

Notice that I also made a few changes:

  • list is a function in R so calling your object list is a pretty bad idea. Also, in the R language, a "list" refers to a very specific data structure, while your code seems to be using a matrix. So calling that input mat seemed more appropriate.
  • Similarly, there is a dist function in R so it is a bad idea to name your variable this way. I chose euc.dist since you were computing an euclidean distance.
  • order already returns an index, so the whole idea of column-biding your indices and distances was not necessary: you just need a vector of distances.

The code above might still be a bit too slow because of the computations inside the for loop. If the dimensions of your matrix are not astronomical, you could compute the matrix of distances at first using a compiled function. I once tested about a dozen of packages and found that fields::rdist (written in Fortran) was the fastest. If you do not wish to install it, you can use the base::dist function. The code would look like this:

knn <- function(mat, k){
   n <- nrow(mat)
   if (n <= k) stop("k can not be more than n-1")
   neigh <- matrix(0, nrow = n, ncol = k)
   library(fields)
   dist.mat <- rdist(mat, mat)
   for(i in 1:n) {
      euc.dist <- dist.mat[i, ]
      neigh[i, ] <- order(euc.dist)[2:(k + 1)]
   }
   return(neigh)
}

If my first suggestion is still too slow and your matrix is so large that my second solution cannot be used, you might want to use a mix between the two approaches, where you loop on chunks of rows, i.e. rely on rdist(chunk_of_rows_from_mat, mat). But I'll leave that to you as an exercise :-)

Finally, I will point out that if you are interested, you could search CRAN or the internet for a package that does exactly what you are after. KNN is a very common tool and there must be packages (compiled from C) that already do it much faster than this code will do. But not much to be learnt there...

\$\endgroup\$
2
  • \$\begingroup\$ The first code works better but still not fast enough. I want to get the neighbors based on DTW distance. There is no library available for the same. I think writing the code in python might work faster. \$\endgroup\$
    – Arighna
    Commented Jun 23, 2015 at 16:48
  • \$\begingroup\$ I tried to add resultat <- knn(i,3) but how to understand the output as far as I get lines such as [1,] 2 3 4 or [5,] 4 5 1 I know it sorts and returns the positions but how can I get the actual flowers ? and the line's expected classes ? \$\endgroup\$ Commented Mar 22, 2017 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.