# Clarification on K Means Clustering Algorithm and its Analysis

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.

• Yes you are correct May 26 '18 at 13:07
• If you don't give us the source for the image, we only see part of the story. Where did this come from? May 26 '18 at 15:00

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

• This will not even happen in early iterations. May 26 '18 at 22:31

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.