1
$\begingroup$

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?

Improve this question
$\endgroup$
7
  • $\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
    Commented May 23, 2018 at 8:12
  • $\begingroup$ No tricks, it works with a matrix object in R. $\endgroup$
    – mickkk
    Commented May 23, 2018 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
    Commented May 23, 2018 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
    Commented May 23, 2018 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
    Commented May 23, 2018 at 8:56

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented May 23, 2018 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$
    – Has QUIT--Anony-Mousse
    Commented May 23, 2018 at 18:21

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.