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.
- Initialization: choose k starting centroids, usually with the k-means++ seeding rule.
- Assignment step: attach every point to the centroid with the smallest squared Euclidean distance.
- Update step: move each centroid to the arithmetic mean of the points assigned to it.
- 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.
| Parameter | Typical setting | What it affects |
|---|---|---|
| Number of clusters k | 2 to 20 for exploratory work | Granularity of the grouping |
| Initialization method | k-means++ | Quality and stability of the local optimum |
| Number of restarts | 10 or more runs | Chance of escaping a poor local optimum |
| Maximum iterations | 100 to 300 | Runtime limit on difficult data |
| Tolerance | About 1e-4 relative change | When the algorithm declares convergence |
| Distance measure | Squared Euclidean only | Shape of the clusters it can find |
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.
| Method | What it measures | Main limitation |
|---|---|---|
| Elbow method | Point where WCSS stops dropping sharply | The elbow is often ambiguous |
| Silhouette score | Cohesion versus separation, from -1 to 1 | Costly on very large datasets |
| Gap statistic | WCSS compared with random reference data | Requires many simulated datasets |
| Davies-Bouldin index | Average similarity between nearest clusters | Favors compact, spherical clusters |
| Domain constraint | Business or physical requirement for k | Ignores structure in the data |
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.
| Algorithm | Cluster shape | Needs k in advance | Handles noise |
|---|---|---|---|
| k-means | Spherical, similar size | Yes | No, every point is assigned |
| Gaussian mixture model | Elliptical, varied size | Yes | Partly, through soft probabilities |
| DBSCAN | Arbitrary, density-based | No | Yes, labels outliers as noise |
| Hierarchical clustering | Depends on linkage | No, cut the dendrogram later | Weakly |
| Spectral clustering | Non-convex, graph-based | Yes | Weakly |
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.
| Situation | Recommended choice | Reason |
|---|---|---|
| Large dataset, compact groups | Standard k-means | Fast and easy to explain |
| Tens of millions of rows | Mini-batch k-means | Bounded memory and time |
| Overlapping or elongated groups | Gaussian mixture model | Models covariance and soft membership |
| Irregular shapes with outliers | DBSCAN | Finds density regions and flags noise |
| Unknown number of groups | Hierarchical clustering | Inspect the dendrogram before choosing k |
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.
| Symptom | Likely cause | Fix |
|---|---|---|
| One feature drives every cluster | Unscaled features | Standardize before clustering |
| Results change between runs | Poor initialization | Use k-means++ and multiple restarts |
| Centroids pulled toward extremes | Outliers in the mean | Remove outliers or use k-medoids |
| Ring or crescent shapes split badly | Non-convex clusters | Use DBSCAN or spectral clustering |
| Small groups absorbed by large ones | Unequal cluster sizes | Try a Gaussian mixture model |
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.