K-Means: Full Algorithm
K-Means partitions points into clusters by minimizing the within-cluster sum of squared distances to centroids:
The algorithm alternates two steps, each of which provably decreases .
The algorithm steps and why each decreases J
Step 0: Initialize centroids (random pick from data, or K-Means++).
Step 1: Assign. Assign every point to its nearest centroid:
With centroids fixed, decomposes into per-point terms; assigning each to the nearest centroid minimizes its term and therefore minimizes overall.
Step 2: Update. Move each centroid to the mean of its assigned points:
With assignments fixed, cluster 's contribution to is . Setting its gradient to zero:
The mean is the unique minimizer of within-cluster squared distance — that is why the update uses the mean.
Step 3: Repeat Steps 1–2 until no point changes cluster (convergence).
Guaranteed convergence, local optimum
Both steps only decrease , and there are finitely many possible assignment configurations, so K-Means must terminate. But it converges to a local minimum — different initializations can give different final clusters. Use K-Means++ and n_init ≥ 10 in practice.
Watch it run
Step through the loop on five points with — every distance calculation as each point picks its centroid, and reported before and after each update so you can watch both steps drive it down. The arithmetic is worked out by hand in the section below if you want to check any number.
K-Means — assign, update, converge (and land in a local optimum)
Five points, K = 2, with the centroids initialized on top of A and E. K-Means alternates two steps — assign, then update — and both are guaranteed to lower the objective J, the total squared distance from each point to its centroid.
J = Σ ‖x − μ‖² over all points. Watch it fall at every step, and watch it stop falling exactly when no point changes cluster.
The full assign/update loop on five points with K = 2, matching the hand-worked iteration above. Every distance calculation is shown as each point picks its centroid, and the objective J is reported before and after each update so you can watch both steps decrease it. The final step re-runs the identical algorithm from a different initialization and converges to a worse partition — the local-optimum caveat, demonstrated rather than asserted.
What to notice as you step:
- The update never changes an assignment, and the assignment never moves a centroid. That strict alternation is why each step can be proved to decrease separately, and why the proof is so short.
- Convergence is detected by nothing happening. The loop ends when the recomputed centroids equal the old ones, which happens exactly when no point changed cluster.
- The final step re-runs the identical code from a different initialization and converges just as confidently to a worse partition ( against ). Nothing went wrong — simply has more than one basin, and the starting point decides which one you fall into.
A full worked iteration on 5 points
Here .
Points: , , , , .
Initialize: , .
Iteration 1: Assign
Compute squared Euclidean distance from each point to each centroid (closer one wins):
| Point | Assigned | ||
|---|---|---|---|
, .
Objective with old centroids: .
Iteration 1: Update
Recomputing with new centroids:
— the update step lowered exactly as the derivation guarantees.
Iteration 2: Reassign
Check whether any point is closer to the other cluster's new centroid:
| Point | Same cluster? | ||
|---|---|---|---|
| ✓ | |||
| ✓ | |||
| ✓ | |||
| ✓ | |||
| ✓ |
No point changes assignment. Converged after 2 iterations.
Final clusters: , .
Implementing K-Means from scratch in NumPy
import numpy as np
def kmeans(X, K, n_iter=100, seed=42):
rng = np.random.default_rng(seed)
# Random initialization
mu = X[rng.choice(len(X), K, replace=False)]
for _ in range(n_iter):
# Step 1 — assign
dists = np.linalg.norm(X[:, None] - mu[None], axis=2) # (n, K)
labels = dists.argmin(axis=1)
# Step 2 — update
new_mu = np.array([X[labels == k].mean(axis=0) for k in range(K)])
if np.allclose(new_mu, mu): # converged
break
mu = new_mu
J = sum(np.sum((X[labels == k] - mu[k])**2) for k in range(K))
return labels, mu, J
X = np.array([[1,1],[1.5,2],[3,4],[5,7],[3.5,5]], dtype=float)
labels, centroids, inertia = kmeans(X, K=2)
print("labels :", labels) # [0 0 1 1 1]
print("centroids:", centroids.round(2))
print("inertia :", round(inertia, 2))
Related concepts
- K-Means Clustering: source lesson: elbow method, silhouette score, K-Means++, limitations
- Gaussian Mixture Models: the soft probabilistic version; K-Means is the hard-assignment limit as variance → 0
- Hierarchical Clustering: an alternative that doesn't require choosing K upfront