3
$\begingroup$

I am trying to compare the outputs of k-means algorithm coded by me and the outputs of R's kmeans. Since the objective of the algorithm is to minimize the total within cluster sum of squares (WCSS), I have to look at the withinss output of kmeans and my WCSS. What I'm not able to figure out is, how much of variation should I allow i.e. how close should these values be so I can say that they are close.
(I know that I can also verify using the centroids, but when the data is not that well clustered, the centroids can be very different but the total WCSS can be close, and hence I'm looking at WCSS.)

Improve this question
$\endgroup$
5
  • $\begingroup$ how much of variation should I allow To be sure that your code is all right there should be no difference in results between your implementation and a reference implementation at all. Until you reach that regularly you can't tell if the difference is due to a code bug or due to some minor algorithmic divergence. $\endgroup$
    – ttnphns
    Mar 4, 2013 at 16:44
  • $\begingroup$ I agree that there should be no difference. I'm using the Iris dataset and we know that there are 2 clear clusters in the data. Hence when I give k=2, the output perfect matches with R's. In fact, the output is perfect for k=3 and k=4 too (I use 'nstart' to get the best output). But for k=5 and above, the values are varying. The total WCSS for R's kmeans for k=5 was 46.4 while the same for my algorithm was 49.4. So, should I allow this as a close output since I know that the actual number of clusters are 2 and that further clustering can happen in multiple ways? $\endgroup$
    – Prateek Kulkarni
    Mar 5, 2013 at 5:57
  • 2
    $\begingroup$ There must exist an option in k-means to set initial cluster centres. Compare the 2 programs in that regime (give identical initial centres for both programs). Test many times: different data sets, vary k, vary the initial centres. The 2 programs should give identical results consistenly. Only then you can be sure there is no bug in both programs. $\endgroup$
    – ttnphns
    Mar 5, 2013 at 6:28
  • $\begingroup$ Thanks. I tried what you just said for k=5 and the outputs unfortunately, are not the same. But they are very close. Only one point has been clustered differently. I think this is because that point might be equidistant from 2 centroids, and in the 2 algorithms, this point is put into different clusters (since equidistant points would be clustered randomly). And they were consitent for other k values too. The difference in WCSS for k=5 was 0.009. I feel this close enough, but I wish I had a quantitative threshold above which I would approve it as good enough clustering. $\endgroup$
    – Prateek Kulkarni
    Mar 5, 2013 at 10:00
  • $\begingroup$ Oops, I meant '..below which I would approve it as good enough clustering.' $\endgroup$
    – Prateek Kulkarni
    Mar 5, 2013 at 10:24

1 Answer 1

Reset to default
2
$\begingroup$

As k-means on multiple runs will find different local minima, they can pretty much vary arbitrarily much. On contrary, if two values are close but not identical, I'd consider it much more likely that there is some slight error in one of the two implementations.

If there are multiple local minima, multiple runs with different seedings should give you a number of candidates so there is a high chance of actually finding the same result.

But in the end, k-means is so simple, and such a crude heuristic, what good is it to compare two results? On many data sets it still pretty much a random partitioning; optimized for a local minimum but still meaningless.

Improve this answer
$\endgroup$
3
  • $\begingroup$ "On contrary, if two values are close but not identical, I'd consider it much more likely that there is some slight error in one of the two implementations." I disagree. If you assume a uniformly spread dataset, it is possible that the the centroids are not close but the WCSS are close. "But in the end, k-means is so simple, and such a crude heuristic, what good is it to compare two results?" - Do you mean to say that verifying k-means is meaningless. I mean, I can look at 2 different values of total WCSS and come to a conclusion that one way of clustering is better than the other. $\endgroup$
    – Prateek Kulkarni
    Mar 4, 2013 at 15:33
  • $\begingroup$ Yes, but uniform data does not have reasonable clusters. The clustering algorithm should reply "no clusters found". $\endgroup$
    – Has QUIT--Anony-Mousse
    Mar 4, 2013 at 16:23
  • $\begingroup$ Well, the kmeans in R clusters points irrespective of the data. The algorithm wouldn't know how many clusters are present. That might be something we would infer from the output. $\endgroup$
    – Prateek Kulkarni
    Mar 5, 2013 at 5:50

Your Answer

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

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