3
$\begingroup$

The above shows the K-Means clustering algorithm applied to the data points.

I fail to understand how the circled point is assigned to cluster c2 and not c1. From what I have understood, the points are assigned to the (nearest?) centroid in order to minimise the squared distances i.e. to minimise the assignment cost.

Visually too, it appears to me that the circled point belongs to the first cluster.

Please correct me if I'm wrong.

Source - http://www.cs.yale.edu/homes/el327/papers/OnlineKMeansAlenexEdoLiberty.pdf

$\endgroup$
2
  • $\begingroup$ Yes you are correct $\endgroup$
    – Aditya
    May 26, 2018 at 13:07
  • $\begingroup$ If you don't give us the source for the image, we only see part of the story. Where did this come from? $\endgroup$
    – Spacedman
    May 26, 2018 at 15:00

3 Answers 3

1
$\begingroup$

K-means is an iterative algorithm. So what you have in the picture may be one of the early iterations and therefore the sum of squared distances (between points and clusters) has not been minimised yet. In further iterations, the circled point would indeed be assigned to cluster centroid C1.

Now, having said that, and this is purely speculation, but if the diagram in your picture is not simply 2 dimensional as we interpret it to be, but is actually a 2-d projection from a higher dimensional feature space, then indeed the circled point may be closer to centroid C2 in that higher dimensional space (although it doesn’t look like it in 2-d).

$\endgroup$
1
  • $\begingroup$ This will not even happen in early iterations. $\endgroup$ May 26, 2018 at 22:31
1
$\begingroup$

K-means clusters are always convex.

Even when not converged.

This does not hold here, and therefore that slide is not depicting k-means correctly. It's probably a bad set of slides. There are many many really bad slides on clustering.

$\endgroup$
0
$\begingroup$

Yes, I don't think this is the final result of k-means. K-means is an iterative process involving computing centroids and associating points to clusters. I think that the picture shows the state of the process when centroids have been recomputed but association has not been done for the new centroids.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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