Data Sets suitable for k-means

Question

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?

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

Answer 1

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 voronoi 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:

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.

Answer 2

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.