k-means clustering

Also known as: k-means

On this page 7

k-means clustering is an unsupervised learning algorithm that partitions a dataset into k disjoint clusters so that each point belongs to the cluster with the nearest mean, called the centroid. In machine learning and the wider field of artificial intelligence, k-means is the reference method for centroid-based clustering: it needs no labels, scales to millions of points and produces groups that are easy to interpret.

The algorithm minimizes the within-cluster sum of squares (WCSS), also called inertia, which is the total squared Euclidean distance between every point and its assigned centroid. Because this objective is hard to optimize exactly, k-means uses a fast iterative heuristic that converges to a local optimum rather than a guaranteed global one.

How k-means assigns points and moves centroids

k-means works by alternating two steps until the cluster assignments stop changing. The standard procedure is known as Lloyd’s algorithm, and each iteration can only lower or keep the WCSS, which is why it always converges in a finite number of steps.

  1. Initialization: choose k starting centroids, usually with the k-means++ seeding rule.
  2. Assignment step: attach every point to the centroid with the smallest squared Euclidean distance.
  3. Update step: move each centroid to the arithmetic mean of the points assigned to it.
  4. Convergence check: stop when assignments no longer change, when centroid movement falls below a tolerance or when a maximum iteration count is reached.

Each iteration costs roughly O(n · k · d) operations for n points, k clusters and d features, so the method is linear in the number of points. In practice, most datasets converge within 10 to 100 iterations, although adversarial cases can take far longer.

The following table summarizes the parameters that most strongly shape the result.

ParameterTypical settingWhat it affects
Number of clusters k2 to 20 for exploratory workGranularity of the grouping
Initialization methodk-means++Quality and stability of the local optimum
Number of restarts10 or more runsChance of escaping a poor local optimum
Maximum iterations100 to 300Runtime limit on difficult data
ToleranceAbout 1e-4 relative changeWhen the algorithm declares convergence
Distance measureSquared Euclidean onlyShape of the clusters it can find
Core parameters of k-means clustering

Initialization and choosing the number of clusters

The starting centroids decide which local optimum k-means reaches, so initialization matters as much as the iterations. Random seeding can place two centroids inside one natural group and leave another group without any centroid, which produces a visibly wrong partition.

k-means++ seeding fixes most of this problem: it picks the first centroid at random and then selects each following centroid with probability proportional to its squared distance from the nearest chosen centroid. This spreads the seeds out and gives a provable O(log k) approximation guarantee on the expected WCSS. Running the whole algorithm several times and keeping the lowest-inertia solution adds further protection.

k-means cannot learn k by itself, because WCSS always falls as k grows and reaches zero when every point is its own cluster. Practitioners therefore use model selection heuristics, compared below.

MethodWhat it measuresMain limitation
Elbow methodPoint where WCSS stops dropping sharplyThe elbow is often ambiguous
Silhouette scoreCohesion versus separation, from -1 to 1Costly on very large datasets
Gap statisticWCSS compared with random reference dataRequires many simulated datasets
Davies-Bouldin indexAverage similarity between nearest clustersFavors compact, spherical clusters
Domain constraintBusiness or physical requirement for kIgnores structure in the data
Common methods for choosing k

k-means compared with other clustering methods

k-means is the fastest general-purpose clustering method, but its speed comes from strong assumptions about cluster shape. It implicitly assumes convex, roughly spherical clusters of similar size and variance, and it assigns every point to some cluster, including noise.

The table below places k-means next to neighboring algorithms in the same family of classic methods.

AlgorithmCluster shapeNeeds k in advanceHandles noise
k-meansSpherical, similar sizeYesNo, every point is assigned
Gaussian mixture modelElliptical, varied sizeYesPartly, through soft probabilities
DBSCANArbitrary, density-basedNoYes, labels outliers as noise
Hierarchical clusteringDepends on linkageNo, cut the dendrogram laterWeakly
Spectral clusteringNon-convex, graph-basedYesWeakly
How k-means relates to other clustering algorithms

Formally, k-means is a hard-assignment special case of the expectation-maximization algorithm applied to a Gaussian mixture with equal, isotropic covariances. A Gaussian mixture model relaxes those restrictions and returns membership probabilities, at a higher computational cost.

Preparing data and running k-means in practice

Because k-means relies on Euclidean distance, feature scaling is mandatory whenever features use different units. A feature measured in thousands, such as annual income, will otherwise dominate a feature measured in single digits, such as household size, and the clusters will simply reflect the larger scale.

  • Standardize numeric features to zero mean and unit variance, or use robust scaling when outliers are present.
  • Treat categorical variables with care: one-hot encoding works poorly with Euclidean distance, and k-modes or k-prototypes are better suited to mixed data.
  • Apply dimensionality reduction such as principal component analysis when d is large, because distances lose contrast in high dimensions.
  • Use Mini-batch k-means for very large or streaming datasets; it updates centroids from small random samples and trades slight accuracy for large speed gains.

Decision guidance helps decide when k-means is the right first tool and when another method should replace it.

SituationRecommended choiceReason
Large dataset, compact groupsStandard k-meansFast and easy to explain
Tens of millions of rowsMini-batch k-meansBounded memory and time
Overlapping or elongated groupsGaussian mixture modelModels covariance and soft membership
Irregular shapes with outliersDBSCANFinds density regions and flags noise
Unknown number of groupsHierarchical clusteringInspect the dendrogram before choosing k
When to use k-means and when to switch

Limitations and common mistakes with k-means

The most frequent failures of k-means come from violated assumptions, not from bugs. The algorithm always returns k clusters, even when the data contains no real cluster structure, so a clean-looking output is not evidence that meaningful groups exist.

SymptomLikely causeFix
One feature drives every clusterUnscaled featuresStandardize before clustering
Results change between runsPoor initializationUse k-means++ and multiple restarts
Centroids pulled toward extremesOutliers in the meanRemove outliers or use k-medoids
Ring or crescent shapes split badlyNon-convex clustersUse DBSCAN or spectral clustering
Small groups absorbed by large onesUnequal cluster sizesTry a Gaussian mixture model
Typical problems, causes and fixes

A further caution concerns interpretation: clusters are descriptive summaries, not causal categories. Validating them with silhouette analysis, stability checks on resampled data and domain review protects against presenting arbitrary partitions as discoveries.

A non-technical view

Imagine pouring a box of mixed buttons on a table and asking someone to sort them into five piles. They would place five markers, put each button next to the closest marker, then move each marker to the middle of its pile and repeat. That repeated sort-and-recenter loop is k-means.

The person must decide in advance how many piles to make, and the method works best when the natural piles are round and similar in size. k-means groups similar items quickly, but it cannot tell whether the groups truly mean something.

A concrete example

A regional grocery chain wants to tailor promotions to its 400,000 loyalty card members. An analyst builds six features per customer, including visit frequency, average basket value, share of fresh produce and share of discounted items, and standardizes every feature before clustering.

Testing k from 2 to 10, the analyst finds that the silhouette score peaks at k = 5 and the elbow plot bends at the same point. Ten k-means++ restarts produce nearly identical centroids, which shows the solution is stable rather than accidental.

The five segments include frequent small-basket shoppers, weekly family stock-up customers and price-sensitive bargain hunters. The marketing team designs a separate offer for each segment, and a controlled test shows higher coupon redemption than the previous one-size-fits-all campaign, confirming that the clusters capture real differences in behavior.