K-means Clustering
- Introduced by
- MacQueen, J. B.; Lloyd, S. P.
- Year
- 1967 (formalized 1982)
- Type
- Partitional clustering
- Family
- Machine learning
What does it do?
K-means is a classic unsupervised partitional clustering algorithm that divides a dataset into K non-overlapping groups by iteratively assigning each observation to its nearest centroid and updating centroids as the mean of their assigned points.
It is one of the most widely used exploratory tools in machine learning and data analysis.
The intuition behind the method
Imagine dropping K magnets on a map of data points. Each point is drawn to its nearest magnet, and then each magnet moves to the center of gravity of the points it attracted. Repeat this pull-and-move cycle until nothing moves: the magnets have found K natural groupings. K-means formalizes exactly this idea, minimizing the total squared distance from every point to its cluster center, called the within-cluster sum of squares (WCSS or inertia).
History
The k-means idea was independently introduced by MacQueen in 1967, who coined the term, and formalized as an efficient iterative algorithm by Stuart Lloyd at Bell Labs in the 1950s (published 1982). The k-means++ initialization improvement by Arthur and Vassilvitskii in 2007 addressed the local-minimum sensitivity problem. Today k-means remains a cornerstone unsupervised learning method taught in virtually every data science curriculum.
When to use it
K-means suits exploratory clustering of large, purely numeric datasets when you need fast, scalable partitioning and are comfortable specifying K in advance or searching for it with the elbow or silhouette method. It works well for customer segmentation, image compression, document topic grouping, and pre-processing before supervised learning. Avoid it when clusters are non-spherical, have widely varying sizes or densities, when features are categorical or ordinal (use k-modes or k-prototypes instead), when the number of clusters is entirely unknown and varying K experiments are not feasible, or when the data contain many outliers (use DBSCAN or robust variants instead).
Limitations and considerations
- Requires K to be specified in advance; choosing K poorly produces meaningless clusters.
- Assumes spherical, similarly sized clusters; elongated, irregular, or differently scaled clusters are split or merged incorrectly.
- Sensitive to outliers: a single extreme point can pull a centroid far from the bulk of the cluster.
- Only works with numeric continuous features; categorical data requires a different algorithm (k-modes).
- Converges to a local minimum; results can vary across runs with different random seeds unless k-means++ or multiple restarts are used.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- Fast and scalable: O(nKdi) per iteration, practical on millions of observations with moderate K and dimensions.
- Simple to implement, widely available in every major ML framework, and easy to explain to non-technical audiences.
- Works well on large, well-separated, roughly spherical clusters of similar size.
- The k-means++ initialization substantially reduces sensitivity to starting conditions compared to random initialization.
- Deterministic within a fixed random seed, making results reproducible.
Applications
- Customer segmentation for marketing and personalization based on behavioral or demographic features.
- Image compression by quantizing pixel colors to K representative values (color quantization).
- Document and text clustering as a step in topic modeling pipelines after vectorization.
- Anomaly detection pre-processing: points far from any centroid are candidate outliers.
- Initialization step for more complex algorithms such as Gaussian mixture models or hierarchical clustering.
- Gene expression analysis to group genes or samples with similar expression profiles.
How it works
How it works
K cluster centroids are placed in the feature space, either by randomly selecting K data points (Forgy) or by the smarter k-means++ strategy that spreads initial centroids to reduce the chance of poor local minima. The choice of initialization matters: k-means++ typically yields faster convergence and better final solutions.
Every observation is assigned to the cluster whose centroid is nearest according to Euclidean distance. This hard assignment creates K non-overlapping partitions of the data. Formally, each point x_i is assigned to cluster c_i = argmin_k ||x_i - mu_k||^2.
Formula
c_i = \arg\min_k \|x_i - \mu_k\|^2
Each centroid is recalculated as the arithmetic mean of all points currently assigned to that cluster: mu_k = (1/|C_k|) times the sum of all x_i in C_k. This step guarantees that the new centroid minimizes WCSS within each cluster given the current assignment.
Formula
\mu_k = \frac{1}{|C_k|} \sum_{x_i \in C_k} x_iThe assign and update steps alternate until centroid positions stop changing (or change by less than a tolerance threshold) or a maximum number of iterations is reached. The algorithm is guaranteed to converge to a local minimum of WCSS, though not necessarily the global minimum.
Solution quality is assessed with the total WCSS (inertia) J = sum over clusters of sum over assigned points of ||x_i - mu_k||^2. Choosing K is a separate concern addressed by the elbow method, silhouette scores, or gap statistics, as the algorithm itself requires K to be specified in advance.
Formula
J = \sum_{k=1}^{K} \sum_{x_i \in C_k} \|x_i - \mu_k\|^2Common pitfalls
- Forgetting to standardize features before clustering — variables on large scales will dominate distance calculations.
- Selecting K by inspecting in-sample WCSS alone without the elbow plot or silhouette validation, leading to trivially small or large K.
- Running only one initialization and accepting the first result without multiple restarts to guard against poor local minima.
- Including categorical or ordinal variables in the feature matrix without appropriate encoding or switching to k-modes.
- Treating cluster labels as meaningful group identities without external validation, especially when clusters are not well-separated.
Frequently asked questions
How do I choose the right number of clusters K?
Run k-means for a range of K values, plot the within-cluster sum of squares against K, and look for an 'elbow' where the rate of decrease slows sharply. Supplement this with silhouette scores, which measure how similar each point is to its own cluster versus neighboring clusters; higher average silhouette indicates better-defined clusters.
Why do I get different results each run?
K-means is sensitive to initialization and converges to a local rather than global minimum of WCSS. Use k-means++ initialization and set a fixed random seed for reproducibility. Running the algorithm multiple times with different seeds and keeping the solution with the lowest inertia is good practice.
Does k-means work with categorical data?
No. K-means relies on Euclidean distance and centroid means, which are undefined for categorical variables. For purely categorical data use k-modes; for mixed numeric and categorical data use k-prototypes.
When should I prefer DBSCAN or GMM over k-means?
Use DBSCAN when clusters have irregular shapes or you need automatic outlier detection without specifying K. Use Gaussian Mixture Models (GMM) when you want soft (probabilistic) cluster assignments or clusters of different sizes and orientations, at the cost of higher computational complexity.
Do I need to scale my features?
Yes, almost always. K-means uses Euclidean distance, so features with large numeric ranges will dominate the clustering. Apply z-score standardization or min-max scaling before fitting k-means, unless all features are already on the same scale.
Related methods
Sources
Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.
Open DOI referenceCopied.MacQueen, J. B. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the 5th Berkeley Symposium on Mathematical Statistics and Probability, 1, 281–297.
Open publication referenceCopied.