K-Means is the workhorse of clustering: fast, simple, and good enough whenever clusters are compact and roughly round. This page covers the objective, the algorithm, how to pick k, where it breaks, and the variants that fix those breaks.
K-Means partitions n points into k clusters by minimizing the within-cluster sum of squares (inertia):
J = Σi || xi - μc(i) ||2
where μc(i) is the centroid of the cluster point i belongs to. Lloyd's algorithm alternates two steps that each can only lower J: assign every point to its nearest centroid, then update each centroid to the mean of its points. It stops when assignments stop changing. Each iteration costs O(n·k·d), which is why K-Means scales to millions of rows, and mini-batch variants scale further.
Convergence is guaranteed but only to a local minimum. The answer depends on initialization, so implementations run several starts (n_init) and keep the lowest inertia, and use k-means++ seeding, which picks each new initial centroid with probability proportional to its squared distance from the existing ones.
K-Means needs k up front. Common tools:
k.(b - a)/max(a, b) where a is mean intra-cluster distance and b the mean distance to the nearest other cluster. Ranges from -1 to 1; higher is better.k is often the number of segments a team can act on.import numpy as np
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans, MiniBatchKMeans
from sklearn.metrics import silhouette_score
X, _ = make_blobs(n_samples=3000, centers=4, cluster_std=1.2, random_state=0)
X = StandardScaler().fit_transform(X) # K-Means is distance based: scale first
for k in range(2, 8):
km = KMeans(n_clusters=k, init="k-means++", n_init=10, random_state=0).fit(X)
print(k, round(km.inertia_, 1), round(silhouette_score(X, km.labels_), 3))
best = KMeans(n_clusters=4, n_init=10, random_state=0).fit(X)
print(best.cluster_centers_)
new_labels = best.predict(X[:5]) # assign new points to nearest centroid
# For very large data
mb = MiniBatchKMeans(n_clusters=4, batch_size=4096, n_init=3, random_state=0).fit(X)Unlike DBSCAN or hierarchical clustering, a fitted K-Means model has a natural predict for new points, which makes it convenient as a production segmenter or as a vector quantizer (for example, the coarse quantizer in IVF vector indexes).
K-Means implicitly assumes clusters are roughly spherical, of similar size and similar density, because it uses Euclidean distance to a single center. It draws Voronoi boundaries, which are always straight lines between centroids. Consequences:
| Variant | Change | Use when |
|---|---|---|
| Mini-batch K-Means | Updates centroids from small random batches | Millions of rows, streaming |
| K-Medoids (PAM) | Centers must be actual data points; any distance | Outliers, non-Euclidean metrics |
| Spherical K-Means | Cosine similarity on unit vectors | Text embeddings, TF-IDF |
| Gaussian Mixture Model | Soft assignments, per-cluster covariance | Elliptical clusters, need probabilities |
| Bisecting K-Means | Recursively splits the worst cluster | Hierarchical-ish result at K-Means cost |
Cluster the six values 1, 2, 3, 10, 11, 12 with k = 2, starting from the poor initial centroids 1 and 2.
Even from a bad start, two iterations reached the obvious answer, and inertia fell monotonically (89.2 to 4). k-means++ would very likely have avoided the bad start: after picking the first centroid, a point near 10–12 is many times more likely to be chosen next than 2 or 3, because selection is proportional to squared distance.
| Method | Needs k? | Cluster shape | Outliers | Scales to |
|---|---|---|---|---|
| K-Means | Yes | Convex, similar size | Forced into clusters | Millions (mini-batch: more) |
| Gaussian Mixture | Yes | Ellipsoids, soft membership | Low-probability, but still assigned | Hundreds of thousands |
| DBSCAN / HDBSCAN | No (density parameters) | Arbitrary | Labelled as noise | Large with spatial indexes |
| Agglomerative | Cut the tree afterwards | Depends on linkage | Single linkage chains through them | Tens of thousands (O(n²) memory) |
| Spectral | Yes | Arbitrary connected shapes | Sensitive | Thousands to tens of thousands |
K-Means is a special case of the Gaussian mixture model's EM algorithm in the limit where every component has the same tiny spherical covariance and assignments become hard. If you need probabilities of membership or elliptical clusters, a GMM is the natural next step; if you need to discover the number of clusters and reject noise, use a density method. See the Clustering overview for the full landscape.
Most real deployments are customer or product segmentation, colour quantization, building visual "bag of words" vocabularies, and the coarse quantizer inside IVF vector indexes for embedding search. The engineering details that matter:
Time cost is linear in n, k, d and the number of iterations. scikit-learn's default algorithm="lloyd" is generally fastest; Elkan's variant uses the triangle inequality to skip distance computations and can help on well-separated data with low dimensionality. For hundreds of millions of vectors on GPU, FAISS provides a K-Means implementation used to train its quantizers.