# Clusterings that can be caused by K-means

I have gotten the following question as a test question for my exam and I simply cannot understand the answer.

A scatter plot of the data projected onto the first two principal components is shown below. We wish to examine if there exists some group structure in the data set. To do this, we have run the k-means algorithm with k = 2 using the Euclidean distance measure. The result of the k-means algorithm can vary between runs depending on the random initial conditions. We ran the algorithm several times and got some different clustering results.

Only three of the four clusterings shown can be obtained by running the k-means algorithm on the data. Which one can not be obtained by k-means? (there's nothing special about the data)

The correct answer is D. Can any of you explain why?

-
It would be good to know how your teacher or Professor explains this – Andy Clifton May 25 '14 at 17:52
This is the answer given by my professor: The k-means algorithm proceeds until convergence by computing the mean of each cluster and assigning data objects to the closest cluster. If the clustering in D were a solution, the two cluster means would be around -1.8 and 0 on the PC2 axis, which would force the data objects between -0.9 and -1.8 on the PC2 axis to be grouped into the first cluster in the next iteration of the k-means algorithm. Thus, D can not be a solution. – pir May 25 '14 at 22:05

## 4 Answers

To put some more meat on Peter Flom's answer, k-means clustering looks for k groups in data. The method assumes that Each cluster has a centroid at a certain (x,y). The k-means algorithm minimizes the distance of each point to the centroid (this could be euclidian or manhattan distance depending on your data).

To identify the clusters, an initial guess is made of which data points belong in which cluster, and the centroid is calculated for each cluster. The distance metric is then calculated, and then some points are swapped between clusters to see if the fit improves. There are lots of variations on the details, but fundamentally k-means is a brute force solution that is dependent on the initial conditions, as there are local minima to the clustering solution.

So, in your case it looks like case A had initial conditions that were widely separated in x and so the clusters resolve because the distances from the centroids to the data are small, and it's a stable solution. Conversely, you can't obtain D because that single red point is closer to the centroid of the blue points than many others, so the red point should have become part of the blue set.

Therefore the only way you could get D is if you interrupt the clustering process before it's finished (or the code that made the clusters is broken).

-
Both the answer from Peter Flom and Andy Clifton made it more clear to me why one cannot get D from clustering in the original post. However, I think this answer is the most thorough, which can more easily make somebody else understand it. Thanks for the help! – pir May 25 '14 at 22:08

Because the circled point in D is not far from other points in either PC1 dimension, PC2 dimension or the Euclidean distance combining them.

In A, the single point is far from the others on PC1

In B and C there are two large groups that are easily separable. Indeed, B and C are the same clustering (unless I am missing a dot) they only vary in terms of label

-
Yes, and I would say it is unlikely that any cluster analysis - not K-means only - will give the solution D (unless maybe when inproperly tuned). – ttnphns May 25 '14 at 12:28

Since D contains a single point only, its center is exactly at this point.

For the remainder of the data, the center must be close to 0,0 in this projection.

At least one of the blue points is substantially closer to the red center than to the blue in the first two principal components. The result does not appear to be produced by Voronoi cells.

-

This is not a direct answer to your question, but I don't understand how the set-up your teacher suggests, i.e. first applying PCA then looking for clusters, makes sense:

If the dataset has a clustered structure, the dimensional reduction obtained through PCA is not guaranteed to respect this structure whatsoever. In your figures, PC1 and PC2 will only give you the variables (or linear combinations of variables) that capture the most variation in the data.

Put differently: if you hypothesise from the onset that the dataset contains clusters, the most important features are clearly the ones that discriminate between clusters, which, in general do not coincide with the directions of great variations in the whole dataset.

In such a scenario what makes more sense is to first cluster (without any dimensionality reduction) and then perform LDA or XCA, or something similar that preserves the class/cluster discriminatory information.

-