I researched about k-means and these are what I got: k-means is one of the simplest algorithm which uses unsupervised learning method to solve known clustering issues. It works really well with large datasets.

However, there are also drawbacks of K-Means which are:

  • Strong sensitivity to outliers and noise
  • Doesn't work well with non-circular cluster shape -- number of cluster and initial seed value need to be specified beforehand
  • Low capability to pass the local optimum.

Is there anything great about k-means, because it seems that the drawbacks are beyond the good things about k-means.

Please teach me.

  • 3
    $\begingroup$ There is no such thing as a good method or good algorithm without the context of a problem it is used in. Thus we do use k-means because there are problems for which k-means is an optimal solution (; $\endgroup$ – user88 May 13 '13 at 15:58

Other clustering algorithms with better features tend to be more expensive. In this case, k-means becomes a great solution for pre-clustering, reducing the space into disjoint smaller sub-spaces where other clustering algorithms can be applied.

  • $\begingroup$ More expensive as in the cost of the program? or ? $\endgroup$ – Gold Skull with Pattern May 13 '13 at 13:05
  • 5
    $\begingroup$ More expensive as in slow and memory-intensive. $\endgroup$ – Martin O'Leary May 13 '13 at 13:06
  • $\begingroup$ Oh I see. Is there any other benefits other than fast, robust, and easier to understand? And anyway thanks for the responses @MartinO'Leary and @ zeferino $\endgroup$ – Gold Skull with Pattern May 13 '13 at 13:11

K-means is the simplest. To implement and to run. All you need to do is choose "k" and run it a number of times.

Most more clever algorithms (in particular the good ones) are much harder to implement efficiently (you'll see factors of 100x in runtime differences) and have much more parameters to set.

Plus, most people don't need quality clusters. They actually are happy with anything remotely working for them. Plus, they don't really know what to do when they had more complex clusters. K-means, which models clusters using the simplest model ever - a centroid - is exactly what they need: massive data reduction to centroids.


K-means is like the Exchange Sort algorithm. Easy to understand, helps one get into the topic, but should never be used for anything real, ever. In the case of Exchange Sort, even Bubble Sort is better because it can stop early if the array is partially sorted. In the case of K-means, the EM algorithm is the same algorithm but assumes Gaussian distributions for clusters instead of the uniform distribution assumption of K-means. K-means is an edge case of E-M when all clusters have diagonal covariance matrices. The Gaussian structure means that the clusters shrink-wrap themselves to the data in a very nice way. This gets around the serious objections you correctly raise in the question. And E-M is not much more expensive than K-means, really. (I can implement both in an Excel spreadsheet.) But for serious clustering applications, one should really look at the hierarchical spectrum from single-link to complete-link clustering.


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.