Home / 7. Features & clustering / k-means

k-means

Alternate between moving centres and reassigning points until the assignment stabilizes.

k-means steps
  1. Fix assignments → set each centroid to the mean of its points.
  2. Fix centroids → assign each point to the nearest centroid.

Repeat until little or no change. Initialize with random centres (or random labels). You must choose $K$ up front.

Two blobs

Points form two circular clouds. With $K=2$, k-means usually places a centre in each cloud after a few iterations. With $K=5$, it may split a true blob into artificial pieces — $K$ is a modelling choice.

centroid 1 centroid 2 Points assigned to nearest centre
Two clusters with filled centroids; each point belongs to the nearest centre.
Local optima

Different initializations can give different solutions. Run several times and keep the lowest loss.

Key takeaways

  • Alternating optimization.
  • Needs $K$ in advance.
  • Not guaranteed global optimum.