Data Science Stack Exchange is a question and answer site for Data science professionals, Machine Learning specialists, and those interested in learning more about the field. It only takes a minute to sign up.
Sign up to join this community
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
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).
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.
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.
