Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

My task is to determine which ones of these datasets given in the picture are suitable for k-means. My script says that k-means usually performs well on concave structures, however the sizes of the obvious clusters of case 1 differ very strongly, which would indicate a possible bad performance of k-means, right?

So my pick here would be case 2, since the sizes of the 3 clusters are almost identical and the shapes are - however not concave - very dense and case 3 has a lot of noise, which k-means can't handle. Are my thoughts correct?

enter image description here

Note, that i don't actually know any values for the dataset, so it is supposed to be clear by looking at the picture if k-means is suitable

share|improve this question

I would answer that the only really suitable data set would be 2. K-means pushes towards, kind of, spherical clusters of the same size. I say kind of because the divisions are more like voroinoi cells. From here that in the first example you would end up with overlapped clusters. There are clearly three clusters, a big one and two small ones. The two small ones would be understood by k-means but it would eat up a section of the big one when trying to define them. This is a classic example called "mouse". You can look at how k-means handles this data in the wikipedia k-means entry:

enter image description here

Another thing that should be noted in this image is that K-means can't understand noise, It always assigns all the points to a cluster or other. In fact it is quite sensitive to outliers as the algorithm itself is based on, well, means. So that leaves out example number 3. Example 2 has clusters of strange shapes but they are roughly the same size in the feature space as you can wrap them with circles of approximetely the same size. K-means clustering here would do a good job. Of course this is all quite subjective, unsupervised learning always is. Depending on the task and the obtained results, you can decide if you care a lot about the noise and if you can keep the discovered clusters even though they are not "perfect" and so on. Different clustering algorithms are based on different ideas so they will approach the problem trying to obtain different specific things. Meaning they will treat the data the only way they know how to and you have to decide if this answer is suitable for you. Look at this question which shows a cute diagram where you can see what different algorithms do to the same data sets.

share|improve this answer

In complement to JEquihua's great answer, I would like to add 2 points.

Case 3 is a nice example of a case where it would be useful to have a clustering algorithm that doesn't give only the cluster assignment but also some way to assess the degree of certitude that a point belongs to a cluster (e.g. membership degree in fuzzy clustering), which would subsequently allows us to spot noisy/ambiguous points.

Kaufman, Leonard, and Peter J. Rousseeuw. "Finding groups in data: An introduction to cluster analysis." (2005), Chapter 4 explains this issue into more details. Excerpt:

In a partition, each object of the data set is assigned to one and only one cluster. Therefore, partitioning methods (such as the standard k-means algorithm) are sometimes said to produce a hard clustering, because they make a clear-cut decision for each object. On the other hand, a fuzzy clustering method allows for some ambiguity in the data, which often occurs.

Another way to spot noisy/ambiguous points is to use some indices such as the silhouette, which provides a metric to assess how well each point lies within its cluster.

Regarding case 2, to rephrase slightly what JEquihua said, k-means would work not just because of the closeness of the points of each three groups, but also because groups have the same size. So it is somehow a lucky situation.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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