K-means partitions points into k clusters by minimising the total squared distance from each point to its cluster centre. Lloyd's algorithm alternates two cheap steps until nothing changes.

The two steps

• Assign: attach every point to its nearest centroid. This carves the plane into Voronoi cells.
• Update: move each centroid to the mean of the points assigned to it.

Repeat. Each step can only lower the objective, so the inertia (within-cluster sum of squared errors) never rises and the process converges.

Inertia

inertia = Σ‖xᵢ − μ_c(i)‖², the sum over all points of the squared distance to their assigned centroid μ. Watch it fall every iteration.

k-means++ seeding

Random initial centroids can give a poor local optimum. k-means++ picks the first centre at random, then chooses each subsequent centre with probability proportional to its squared distance from the nearest existing centre — spreading seeds out and giving far better, more stable results.

Limitations

K-means assumes roughly spherical, similarly sized clusters and needs you to fix k in advance. It struggles with elongated or nested shapes (try the Moons preset) — that is where density methods like DBSCAN shine.