# Centroid-based clustering

> Source: https://aiwiki.ai/wiki/centroid-based_clustering
> Updated: 2026-07-13
> Categories: Machine Learning
> License: CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/)
> From AI Wiki (https://aiwiki.ai), the free encyclopedia of artificial intelligence. Reuse freely with attribution to "AI Wiki (aiwiki.ai)".

*See also: [Machine learning terms](/wiki/machine_learning_terms)*

Centroid-based clustering is a family of [machine learning](/wiki/machine_learning) algorithms that group data by representing each cluster with a single prototype point, called a centroid, and assigning every point to whichever cluster has the nearest centroid under some distance measure. The approach falls within [unsupervised learning](/wiki/unsupervised_learning), since the algorithms infer structure from features alone without labelled targets. Its canonical example is [k-means clustering](/wiki/k-means_clustering), which partitions a dataset into K groups by minimising the sum of squared distances between each point and the mean of its assigned cluster. Because finding the exact optimum is NP-hard, these methods rely on fast iterative heuristics, most famously Lloyd's algorithm, that converge to a local optimum in time proportional to $$n$$ times $$K$$ times $$d$$ per pass. k-means was ranked among the "top 10 algorithms in data mining" in a 2008 survey of the field's most influential methods [20], a measure of how widely centroid-based clustering is used.

Variants such as k-medoids, k-medians, k-modes, k-prototypes, fuzzy c-means, mini-batch k-means, and bisecting k-means change the prototype, distance function, or optimisation strategy, but all share the same idea: describe each cluster by one summary point and assign data based on proximity to that summary.

Centroid-based methods are popular because they are simple, easy to explain, and fast on moderate-sized data. Weaknesses include a tendency to find roughly spherical clusters of similar size and a strong dependence on K and the initial centroid placement.

## How does centroid-based clustering work?

Given n points in some feature space, a centroid-based algorithm chooses K prototype points (the centroids) and assigns every data point to one of them so that points in the same cluster are as close to their centroid as possible. The standard objective for k-means is the within-cluster sum of squares (WCSS), also called the inertia. For a partition into clusters with centroids $$m_1, \ldots, m_K$$, the WCSS is the sum over all clusters of the squared Euclidean distances between each point and its centroid.

Minimising WCSS exactly is NP-hard. Aloise, Deshpande, Hansen, and Popat (2009) proved the problem NP-hard even for only two clusters ($$K = 2$$) when the dimension is part of the input [21], and Mahajan, Nimbhorkar, and Varadarajan (2009) proved it NP-hard in the plane (two dimensions) for a general number of clusters [12]. In practice, algorithms use heuristic iterative procedures that converge to a local minimum. The most widely used is Lloyd's algorithm.

### Voronoi tessellation

Once centroids are fixed, assigning every point in feature space to its nearest centroid defines a Voronoi tessellation: the space is partitioned into K convex regions, one per centroid. When each region's centroid is also the mean of the points it covers, the result is a centroidal Voronoi tessellation. Lloyd's algorithm can be viewed as iteratively building such a tessellation by recomputing the Voronoi regions and moving each centroid to the mean of its region [17].

This explains why standard k-means produces clusters with straight, flat boundaries. The decision surface between any two clusters is a hyperplane bisecting the line between their centroids, so clusters are always convex, roughly globe-shaped regions. Datasets with curved or interlocking shapes are usually a poor fit.

## How does the k-means algorithm work?

Stuart P. Lloyd of Bell Labs proposed the standard procedure in a 1957 internal memorandum on pulse-code modulation. The work circulated informally and was not published until 1982 in IEEE Transactions on Information Theory [1]. Joel Max independently published a similar quantisation procedure in 1960 (hence "Lloyd-Max"), and Edward W. Forgy presented the same clustering scheme in 1965 ("Lloyd-Forgy") [3]. The term "k-means" was coined by James MacQueen in 1967 [2], though the basic idea traces back to Hugo Steinhaus in 1956.

### Algorithm steps

Lloyd's algorithm for k-means proceeds as follows:

1. Choose an initial set of K centroids, often by randomly picking K data points or by using k-means++.
2. Assignment step: assign every data point to the cluster whose centroid is nearest under squared Euclidean distance.
3. Update step: recompute each centroid as the arithmetic mean of the points currently assigned to it.
4. Repeat steps 2 and 3 until assignments no longer change, the centroids move by less than some tolerance, or a maximum iteration count is reached.

Each iteration runs in time proportional to $$n$$ times $$K$$ times $$d$$, where $$d$$ is the number of features. The WCSS decreases monotonically with each step, so the algorithm always converges in finite time to a stationary point that is only guaranteed to be a local minimum [15]. Most implementations run the algorithm several times with different initial centroids and keep the run with the lowest WCSS.

K-means assumes clusters are convex, roughly equal in size and variance, and shaped like spheres in the feature space. When these assumptions hold, the algorithm is fast and produces interpretable clusters; when they do not, k-means can give visibly wrong results, for example splitting one elongated cluster or merging two adjacent clusters of unequal size. The worst-case number of iterations is in fact exponential: Arthur and Vassilvitskii (2006) constructed inputs that force $$2^{\Omega(\sqrt{n})}$$ iterations, and Vattani (2011) showed that k-means can require $$2^{\Omega(n)}$$ iterations even in the plane [22]. On realistic data, however, the number of iterations is usually well under fifty, with most of the improvement happening in the first handful.

## What is k-means++ initialisation?

Plain random initialisation can produce clusterings arbitrarily worse than the optimal partition [18]. In 2007, David Arthur and Sergei Vassilvitskii proposed k-means++, a seeding scheme that spreads the initial centroids out probabilistically [4]:

1. Pick the first centroid uniformly at random from the data.
2. For each remaining point $$x$$, compute $$D(x)$$, the distance from $$x$$ to the nearest centroid already chosen.
3. Pick the next centroid with probability proportional to $$D(x)^2$$, so points far from existing centroids are more likely to be selected.
4. Repeat until K centroids are chosen, then run standard Lloyd k-means.

Arthur and Vassilvitskii proved that k-means++ gives an expected approximation ratio of $$O(\log K)$$ relative to the optimal WCSS. As their paper states, "by augmenting k-means with a very simple, randomized seeding technique, we obtain an algorithm that is $$\Theta(\log k)$$-competitive with the optimal clustering" [4]. Their experiments cut the average WCSS potential by up to 99.96% on a synthetic 25-Gaussian dataset, and on the Spam and Intrusion benchmarks k-means++ "achieved potentials 20 to 1000 times smaller than those achieved by standard k-means," with each run completing two to three times faster [4]. Scikit-learn uses k-means++ as the default initialiser [19]. A scalable variant called k-means|| (Bahmani et al., 2012) keeps the theoretical guarantees while reducing the number of sequential passes through the data [14].

## What are k-medoids and PAM?

The k-medoids algorithm replaces the cluster mean with a medoid, an actual data point that minimises the sum of dissimilarities to other points in its cluster. Leonard Kaufman and Peter Rousseeuw introduced Partitioning Around Medoids (PAM) in 1987 [5]. Because medoids are drawn from the data and dissimilarities can be arbitrary, k-medoids works with any distance function, including non-Euclidean ones such as Manhattan distance, cosine dissimilarity, or domain-specific measures for strings and graphs [16].

PAM has two phases. The BUILD phase greedily selects K data points as initial medoids to minimise total dissimilarity from each non-medoid to its nearest medoid. The SWAP phase then iteratively swaps each medoid with each non-medoid and performs the swap that reduces cost the most, until no swap improves the objective.

PAM has a runtime of $$O(K (n - K)^2)$$ per iteration, which limits it to small datasets. CLARA runs PAM on multiple random samples and keeps the best clustering; CLARANS restricts the SWAP phase to a random subset of candidate swaps. Schubert and Rousseeuw's FastPAM and FasterPAM (2019-2021) cut the cost of each SWAP step to $$O(n^2)$$, an $$O(K)$$ speedup that leaves the results unchanged; on real data with K = 100 and K = 200 they reported speedups of 458 times and 1191 times over the original PAM SWAP phase [6]. BanditPAM (Tiwari et al., 2020) used multi-armed bandit techniques to focus computation on the most promising swaps, reducing the per-iteration cost from $$O(n^2)$$ to $$O(n \log n)$$ and performing up to 200 times fewer distance computations while returning the same medoids as PAM [23].

K-medoids is more robust to outliers than k-means: a single far-away point cannot pull a medoid the way it pulls a mean. The trade-off is higher computational cost and, on clean data, a slightly worse WCSS.

## What other centroid-based variants exist?

A number of related algorithms keep the centroid-based skeleton but change the prototype, the distance, or the optimisation strategy.

| Algorithm | Prototype | Notes |
| --- | --- | --- |
| [K-means](/wiki/k-means) | Arithmetic mean | Minimises squared Euclidean distance; default for numeric data |
| K-medoids (PAM) | Actual data point (medoid) | Works with arbitrary dissimilarities; more robust to outliers |
| K-medians | Coordinate-wise median | Optimises sum of L1 distances; less affected by extreme values |
| K-modes | Mode of each attribute | Designed for categorical data; uses simple matching dissimilarity |
| K-prototypes | Mixed mean and mode | Handles datasets with both numeric and categorical features |
| Fuzzy c-means | Weighted mean | Each point has membership weights in all clusters |
| Mini-batch k-means | Running average mean | Centroids updated from small random batches; scales to huge data |
| Bisecting k-means | Arithmetic mean | Repeatedly splits one cluster at a time using 2-means |
| Spherical k-means | Unit-norm mean | Uses cosine similarity; popular for text and embedding data |
| Hartigan-Wong | Arithmetic mean | Local search variant that often finds better minima than Lloyd |

Fuzzy c-means, introduced by J. C. Dunn in 1973 and refined by James C. Bezdek in 1981, assigns each point a degree of membership in every cluster rather than a hard assignment [9]. A fuzziness parameter $$m$$ (typically 2) controls how soft the assignments are.

Mini-batch k-means (Sculley, WWW 2010) draws a small random sample of points at each iteration and uses a running average to update centroids [7]. It loses a little accuracy but reduces computation by orders of magnitude, making it practical for clustering millions of points and for streaming settings.

Bisecting k-means (Steinbach, Karypis, and Kumar, 2000) starts with all data in one cluster and repeatedly applies 2-means to split the cluster with the highest variance until K leaves are produced [8]. It yields a hierarchy as a side effect and is often more stable than flat k-means.

## How do you choose the number of clusters (K)?

All centroid-based methods require choosing K in advance. Several heuristics help, but none is foolproof.

The elbow method plots WCSS against K and looks for the point where the curve bends from steep to shallow. Beyond the elbow, adding clusters yields little extra reduction in within-cluster variance. The method works when clusters are clearly separated and fails when the curve is smooth.

The silhouette score, introduced by Peter Rousseeuw in 1987, measures how tightly each point fits inside its assigned cluster relative to its distance from the next nearest cluster [10]. Scores range from minus one to one; values close to one indicate good separation. The average silhouette across all points, computed for each candidate K, gives a single number to maximise. Unlike the elbow method, it considers both within-cluster compactness and between-cluster separation.

The gap statistic, proposed by Tibshirani, Walther, and Hastie in 2001, compares the observed WCSS at each K with the expected WCSS under a null reference distribution generated by uniform sampling [11]. The chosen K is the smallest value where the gap statistic is within one standard error of the gap at the next value.

Analysts often compute all three. Other approaches include the Calinski-Harabasz and Davies-Bouldin indexes and the BIC-based X-means algorithm (Pelleg and Moore, 2000).

## How does centroid-based clustering compare with hierarchical and density-based clustering?

Centroid-based clustering is typically taught alongside [hierarchical clustering](/wiki/hierarchical_clustering) and [density-based clustering](/wiki/density-based_clustering).

Hierarchical methods such as agglomerative clustering build a tree of nested partitions. They do not require K up front; the user picks a cut height after the fact. They scale poorly (typically $$O(n^2)$$ or worse) but offer a richer view of the data and can produce non-spherical clusters depending on the linkage criterion.

Density-based methods such as [DBSCAN](/wiki/dbscan) (Ester, Kriegel, Sander, and Xu, 1996) and OPTICS define clusters as regions of high density separated by low density [13]. They find clusters of arbitrary shape, treat low-density points as noise, and do not require K. The trade-off is two parameters (a neighbourhood radius and a minimum point count) and difficulty when clusters have very different densities.

Centroid-based methods sit between these in scalability and shape flexibility. They are usually the fastest on large numeric datasets and the easiest to explain, but impose strong assumptions about cluster geometry. [Gaussian mixture models](/wiki/gaussian_mixture_model) are closely related, generalising k-means to allow elliptical clusters and probabilistic assignments via the EM algorithm.

## Practical considerations

Feature scaling matters. Because k-means uses Euclidean distance, features with larger numeric ranges dominate the objective, so standardising or normalising before clustering is standard practice.

High-dimensional data brings the curse of dimensionality: as d grows, Euclidean distances become more uniform and the contrast between near and far neighbours fades. A common remedy is to reduce dimensionality first using [principal component analysis](/wiki/principal_component_analysis), [t-SNE](/wiki/t-sne), [UMAP](/wiki/umap), or autoencoders. Outliers can pull a cluster mean off its true centre; k-medoids, k-medians, and robust pre-processing reduce this effect.

Multiple restarts are recommended, because a single run only reaches a local optimum. There is a versioning subtlety worth knowing: since scikit-learn 1.4 the KMeans n_init parameter defaults to "auto", which runs the algorithm only once when the default k-means++ initialiser is used, whereas earlier versions ran ten restarts by default [19]. Set n_init explicitly for several restarts and keep the partition with the lowest inertia. R has kmeans plus the cluster package for PAM, CLARA, and silhouettes. Apache Spark MLlib includes KMeans, BisectingKMeans, and Gaussian mixture models. ELKI offers many k-means variants for research benchmarks.

## What is centroid-based clustering used for?

Centroid-based clustering appears across many fields: customer segmentation, document clustering using bag-of-words or embedding vectors, colour quantisation and image segmentation, vector quantisation in speech coding and deep learning systems such as VQ-VAE, anomaly detection (points far from any centroid are flagged), feature learning, bioinformatics (gene expression, single-cell analysis), astronomy (stellar populations from spectroscopic features), and recommender systems where embeddings are pre-clustered for fast retrieval.

## Explain like I'm 5

Imagine a playground full of kids and you want to split them into a few groups. You pick spots on the ground as "meeting spots" and ask each kid to run to the nearest one. Then you look at each group, find the average position of the kids, and move the meeting spot to that average. Some kids might now be closer to a different spot, so you let them switch. Keep moving spots and letting kids switch until nothing changes. That is centroid-based clustering: the meeting spots are the centroids, and each group is one cluster.

## References

1. Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129-137.
2. MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proc. 5th Berkeley Symposium on Mathematical Statistics and Probability.
3. Forgy, E. W. (1965). Cluster analysis of multivariate data. Biometrics 21, 768-769.
4. Arthur, D., and Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding. Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, 1027-1035.
5. Kaufman, L., and Rousseeuw, P. J. (1987). Clustering by means of medoids. In Statistical Data Analysis Based on the L1 Norm.
6. Schubert, E., and Rousseeuw, P. J. (2021). Fast and eager k-medoids clustering: O(k) runtime improvement of the PAM, CLARA, and CLARANS algorithms. Information Systems, 101, 101804.
7. Sculley, D. (2010). Web-scale k-means clustering. Proc. 19th International Conference on World Wide Web, 1177-1178.
8. Steinbach, M., Karypis, G., and Kumar, V. (2000). A Comparison of Document Clustering Techniques. KDD Workshop on Text Mining.
9. Bezdek, J. C. (1981). Pattern Recognition with Fuzzy Objective Function Algorithms. Plenum Press.
10. Rousseeuw, P. J. (1987). Silhouettes: a graphical aid to the interpretation and validation of cluster analysis. Journal of Computational and Applied Mathematics, 20, 53-65.
11. Tibshirani, R., Walther, G., and Hastie, T. (2001). Estimating the number of clusters in a data set via the gap statistic. JRSS Series B, 63(2), 411-423.
12. Mahajan, M., Nimbhorkar, P., and Varadarajan, K. (2009). The planar k-means problem is NP-hard. WALCOM, 274-285.
13. Ester, M., Kriegel, H. P., Sander, J., and Xu, X. (1996). A density-based algorithm for discovering clusters in large spatial databases with noise. KDD, 226-231.
14. Bahmani, B., et al. (2012). Scalable k-means++. PVLDB, 5(7), 622-633.
15. Wikipedia. k-means clustering. https://en.wikipedia.org/wiki/K-means_clustering
16. Wikipedia. k-medoids. https://en.wikipedia.org/wiki/K-medoids
17. Wikipedia. Lloyd's algorithm. https://en.wikipedia.org/wiki/Lloyd%27s_algorithm
18. Wikipedia. k-means++. https://en.wikipedia.org/wiki/K-means%2B%2B
19. Scikit-learn documentation. KMeans. https://scikit-learn.org/stable/modules/generated/sklearn.cluster.KMeans.html
20. Wu, X., Kumar, V., Quinlan, J. R., et al. (2008). Top 10 algorithms in data mining. Knowledge and Information Systems, 14(1), 1-37.
21. Aloise, D., Deshpande, A., Hansen, P., and Popat, P. (2009). NP-hardness of Euclidean sum-of-squares clustering. Machine Learning, 75(2), 245-248.
22. Vattani, A. (2011). k-means requires exponentially many iterations even in the plane. Discrete and Computational Geometry, 45(4), 596-616.
23. Tiwari, M., Zhang, M. J., Mayclin, J., Thrun, S., Piech, C., and Shomorony, I. (2020). BanditPAM: Almost Linear Time k-Medoids Clustering via Multi-Armed Bandits. Advances in Neural Information Processing Systems 33.