Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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)

4 possible clusterings of data

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

share|improve this question
    
It would be good to know how your teacher or Professor explains this –  Andy Clifton May 25 at 17:52
3  
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. –  felbo May 25 at 22:05
add comment

3 Answers 3

up vote 6 down vote accepted

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).

share|improve this answer
1  
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! –  felbo May 25 at 22:08
add comment

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

share|improve this answer
3  
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 at 12:28
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

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.