k-Means Clustering on Toy Data

Partition points into k groups by alternating between assigning points to nearest centers and recomputing those centers.

The objective

k-means seeks k cluster centers that minimize the total squared distance from each point to its nearest center. The problem is NP-hard in general, but Lloyd's algorithm finds a good local optimum by a simple two-step iteration.

Lloyd's algorithm

• Initialize k centers (e.g. random points).
• Assign: label each point by its nearest center.
• Update: move each center to the mean of its assigned points.
• Repeat until assignments stop changing.

import numpy as np
rng=np.random.default_rng(1)
X=np.vstack([rng.normal(c,0.4,(100,2)) for c in [(0,0),(3,0),(1.5,3)]])
k=3; C=X[rng.choice(len(X),k,replace=False)]
for it in range(50):
    d=((X[:,None,:]-C[None,:,:])**2).sum(2)
    lab=d.argmin(1)
    newC=np.array([X[lab==j].mean(0) for j in range(k)])
    if np.allclose(newC,C): break
    C=newC
print('centers:\n',np.round(C,2),'converged in',it,'iters')

Pitfalls

k-means converges to a local optimum that depends on initialization; a bad start can give poor clusters. The k-means++ seeding, which spreads initial centers apart, greatly improves results. You must also choose k in advance - the elbow method or silhouette score help - and the method assumes roughly spherical, similarly sized clusters.

When it fails

Because it minimizes squared Euclidean distance, k-means struggles with elongated, nested, or very different-density clusters, and it is sensitive to outliers and feature scaling - always standardize features first. For non-spherical structure, density-based or spectral clustering are better tools. Still, k-means is fast, simple, and the right first attempt.