Find the clumps.
On this page
Given unlabeled points, k-means sorts them into k clusters the way your eye finds clumps: guess k centers, let every point join its nearest center, move each center to the middle of its members, and repeat until the centers stop moving. This assign-move loop is Lloyd’s algorithm (Lloyd 1982).
There is no network, no gradient and no learning rate; the centers just walk, round by round, until they stop moving.
k-means outputs k centers and one cluster per point, and both steps of the loop lower the same score.
If a center loses every point, it stays put rather than dividing by zero.
This snippet runs the whole loop on three blobs of 100 points each and prints the three centers it settles on, near (0, 0), (4, 0) and (2, 3).
import numpy as np
rng = np.random.default_rng(0)
centers = [[0, 0], [4, 0], [2, 3]]
X = np.vstack([rng.normal(m, 0.5, size=(100, 2)) for m in centers])
k, tol, max_iter = 3, 0.01, 100
mu = X[rng.choice(len(X), k, replace=False)]
for _ in range(max_iter):
c = ((X[:, None, :] - mu) ** 2).sum(axis=2).argmin(axis=1)
new_mu = mu.copy()
for j in np.unique(c):
new_mu[j] = X[c == j].mean(axis=0)
moved = np.linalg.norm(new_mu - mu, axis=1).max()
mu = new_mu
if moved <= tol:
break
print(mu.round(2))Each point joins its nearer center, so two centers split the plane where the two distances tie.
A compact cluster is round, its points spread about equally in every direction; an elongated cluster is stretched much longer in one direction. k-means fits compact clusters, but the straight boundary of Section 4 passes through the midpoint between two centers, so it cuts each elongated cluster in half.
Figure 3. Compact clusters work; elongated clusters get cut in half.
A random start can waste rounds or trap the loop in a lopsided split. k-means++ (Arthur and Vassilvitskii 2007) changes only the seeding: the first center is a point chosen uniformly at random, each next one is drawn like this.
The centers start spread out and the loop itself never changes, so bad starts and wasted rounds get rarer.
Choosing k is up to you; two rules of thumb help: the elbow method looks for the bend in WCSS as k grows, and the silhouette score, from −1 to 1, is high when each point is much closer to its own cluster than to the next one.
This snippet fits 2 to 6 clusters on the same 300 points and prints WCSS and the silhouette score for each k; Figure 4 plots the printed values.
import numpy as np
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
rng = np.random.default_rng(0)
centers = [[0, 0], [4, 0], [2, 3]]
X = np.vstack([rng.normal(m, 0.5, size=(100, 2)) for m in centers])
for k in range(2, 7):
km = KMeans(n_clusters=k, n_init=10, random_state=0)
km.fit(X)
print(k, km.inertia_, silhouette_score(X, km.labels_)) # WCSS, silhouetteIn scikit-learn, k-means sits after a scaler, since it measures squared distance; fit runs the rounds once on the training points, and predict sends each new point to its nearest center.
import numpy as np
from sklearn.cluster import KMeans
from sklearn.pipeline import make_pipeline
from sklearn.preprocessing import StandardScaler
rng = np.random.default_rng(0)
centers = [[0, 0], [4, 0], [2, 3]]
X = np.vstack([rng.normal(m, 0.5, size=(100, 2)) for m in centers])
model = make_pipeline(StandardScaler(), KMeans(n_clusters=3, random_state=0))
model.fit(X)
print(model.predict([[0.1, 0.2], [3.9, 0.1]])) # nearest center
print(model[-1].n_iter_, model[-1].inertia_) # rounds run, WCSSStandardScaler with KMeans for k = 3.| step | when, on what, and its cost |
|---|---|
fit | Once, in rounds; each round compares all n points with all k centers, so the average cost is k·n·T for T rounds. |
predict | Per new point, one distance per center; no center moves. |
| state | The k centers (cluster_centers_). |
| setting | raise it, lower it | default |
|---|---|---|
n_clusters, k in WCSS | Up always lowers WCSS; k = n gives every point its own center and WCSS 0. Down merges clumps; k = 1 puts one center at the mean. | 8 |
init, the seeding card | "k-means++" spreads the starting centers; "random" picks k points. | "k-means++" |
n_init | More restarts, best WCSS kept, lower the risk of a bad split at a proportional cost. | "auto": 1 with k-means++, 10 with random |
tol, max_iter, the stop card | Smaller tol runs more rounds; it measures the relative center change, not this page’s 0.01 move. max_iter caps the rounds. | 1e-4, 300 |
Defaults and the k·n·T cost are from the scikit-learn KMeans docs, which also warn that the result is a local minimum, hence the restarts. Where it fails is in Section 5.
When clusters overlap or tilt, a point deserves a share in several clusters whose labels are hidden. Maximum Likelihood and EM shows how to fit that, and Gaussian Mixture Models make it a soft k-means with tilted clusters.