4.1 — K-Means: The Algorithm, Step by Step

K-Means partitions data into k clusters by alternating two steps until convergence — this is Lloyd's algorithm:

1. Assign — each point joins the cluster of its nearest centroid (by Euclidean distance).
2. Update — each centroid moves to the mean of the points now assigned to it.

Repeat until assignments stop changing (or a max iteration count is hit).

Why initialization matters

K-Means converges to a local minimum, not necessarily the global one. Random initialization can land centroids badly — e.g. two centroids starting in the same true cluster, leaving another true cluster unrepresented entirely.

K-Means++ fixes this by initializing centroids to be spread out: each new centroid is chosen with probability proportional to its squared distance from the nearest already-chosen centroid, making it likely candidates start in different regions of the data. This is scikit-learn's default and dramatically improves typical results over pure random init.

from sklearn.cluster import KMeans

km = KMeans(n_clusters=3, init='k-means++', n_init=10, random_state=42)
km.fit(X)
km.labels_          # cluster assignment per point
km.cluster_centers_ # final centroid coordinates

Convergence and local minima

Each iteration of assign-then-update can only decrease (or hold steady) the total within-cluster distance, so the algorithm always converges — but where it converges depends on where it started. There's no guarantee of finding the globally best clustering, which is exactly why initialization strategy and multiple restarts (n_init) matter as much as the core algorithm itself.

Takeaways

• K-Means is assign → update → repeat, nothing more exotic under the hood.
• It only finds a local optimum — initialization quality directly determines result quality.
• K-Means++ and n_init are the two practical levers against bad local minima; both are on by default in scikit-learn for good reason.