K-means Clustering
Also known as: k-means clustering, Lloyd's algorithm, k-means partitioning, hard k-means
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.
Key highlights
- 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.
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
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).
Strengths & limitations
- 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.
- 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.
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
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.
Sources
- 1.Lloyd, S. P. (1982). Least squares quantization in PCM. IEEE Transactions on Information Theory, 28(2), 129–137.
- 2.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.
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). K-means. ScholarGate. https://scholargate.app/machine-learning/k-means