I'm trying to use kmeans clustering on a relatively large matrix (4000x4000) using the amap::Kmeans function but R seems to be freezed even after more than half an hour. I have to restart R after this. Apparently it's not a RAM problem and R's built-in kmeans algorithm works fine using euclidean distance.

I think the problem lies in the implementation of amap::Kmeans but I see not alternatives to this function if I want to use the Kendall tau's dissimilarity distance measure.

As a "reproducible example" take the following line of code:

amap::Kmeans(matrix(rnorm(1:4000**2), 1:400, 1:400), centers = 10, method="kendall")

What other alternatives do I have if I want to achieve the same results that can be obtained from the above line of code?

  • $\begingroup$ K-means works with objects by features data, not with objects distance matrix (stats.stackexchange.com/a/81494/3277). If your program can work with a matrix you should describe what trick the algorithm of the program uses. $\endgroup$ – ttnphns May 23 '18 at 8:12
  • $\begingroup$ No tricks, it works with a matrix object in R. $\endgroup$ – mickkk May 23 '18 at 8:17
  • $\begingroup$ I presume it may be first converting the matrix into the data by means of PCoA. If that is so then the subsequent clustering will be standard, "euclidean", and will converge. However the loss of info or problems could occur on the PCoA step if your matrix is not euclidean distance one. On the other hand, if your program is implemented so that it can k-mean-cluster directly from a distance matrix (which is possible, while not efficient) then the clustering won't be proper and successful if your input matrix is not euclidean one. $\endgroup$ – ttnphns May 23 '18 at 8:43
  • $\begingroup$ Note also that tau is similarity, not dissimilarity. Does your program automatically revert similarity into dissimilarity? How? K-means, of course, will need distance, dissimilarity. $\endgroup$ – ttnphns May 23 '18 at 8:49
  • $\begingroup$ As stated in the comment below, I'm trying to follow the approach to clustering given in a paper. I quote from the paper (algorithm 2: Kmeans-SF): "Compute the k-means clusterings of T using Kendall tau similarity metric". This is why I was trying to do that. It's the first time I ever see using a distance metric different from the Euclidean one in kmeans. $\endgroup$ – mickkk May 23 '18 at 8:56

Kmeans is really designed for squared Euclidean distance.

For other distances it will (a) not find the optimum centers and (b) it may even fail to converge. You may well be experiencing this second case here.

Because of low-quality discussions of k-means in too many lectures and books, people always assume it is easy to use it with other distances, but it isn't... The convergence proof does not work.

  • $\begingroup$ Well now I'm between a rock and a hard place: I was using this specific distance (Kendall's Tau) because I'm following an algorithm specified by a scientific paper. I would normally use Euclidean distance but in the paper it is stated to use Kendall's. What do you suggest? Using Euclidean distance Kmeans converges and I get a result which looks plausible. I'm tempted to disregard the suggestions of the authors of the paper. $\endgroup$ – mickkk May 23 '18 at 8:19
  • 1
    $\begingroup$ There is k-medoids (PAM) which works with any distance function. It's safe to use with Kendall's. $\endgroup$ – Anony-Mousse May 23 '18 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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