Source-linked AI summary
Stop using the elbow criterion for k-means and how to choose the number of clusters instead
Erich Schubert
TL;DR
Choosing k for k-means is difficult, and the elbow method can produce misleading conclusions because its geometric heuristics lack strong theoretical support. The paper examines this problem and recommends established alternatives, while emphasizing that data preprocessing and problem structure also matter.
Problem
Choosing the number of clusters k is difficult when the application does not specify it, and elbow plots can look similar for clustered and unclustered data.
Method
The paper analyzes the elbow criterion’s geometric heuristics and discusses variance-based alternatives including VRC, BIC, and Gap statistics.
Results
The normal distribution never scores below 1 and the uniform distribution remains close to 1 under the proposed score, allowing these data sets to be recognized as unclustered.
Takeaways & Limitations
The authors recommend preferring VRC, BIC, or Gap statistics over the elbow method and paying attention to k-means data preprocessing.
Takeaways & Limitations
Elbow-based geometric decisions can change when the data are rescaled or when the analyzed range of k changes.
Abstract
from arXiv · showhide
A major challenge when using k-means clustering often is how to choose the parameter k, the number of clusters. In this letter, we want to point out that it is very easy to draw poor conclusions from a common heuristic, the "elbow method". Better alternatives have been known in literature for a long time, and we want to draw attention to some of these easy to use options, that often perform better. This letter is a call to stop using the elbow method altogether, because it severely lacks theoretic support, and we want to encourage educators to discuss the problems of the method -- if introducing it in class at all -- and teach alternatives instead, while researchers and reviewers should reject conclusions drawn from the elbow method.
1. INTRODUCTION
Cluster analysis seeks data subgroups that are internally similar and distinct from the rest, but no universally best cluster definition exists. K-means is widely used and taught partly because its standard algorithm is simple to describe.
- Cluster analysis identifies subgroups with high within-group similarity and differences from the remainder of the data.
- No single cluster definition is best in every general sense, so data sets and use cases may require different clustering properties and algorithms.
- K-means is currently the most used and most taught clustering method despite the variety of available approaches.
- Its standard algorithm repeatedly assigns each point to the nearest center and recomputes cluster centers until assignments stop changing.
2. K-MEANS CLUSTERING
K-means treats clustering as least-squares data quantization using k centers and optimizes assignments and centers through alternating updates. The problem is computationally hard for multiple clusters and higher-dimensional data, so the standard heuristic may settle at a local fixpoint.
- K-means approximates N objects in a continuous d-dimensional space using k centers, viewing clustering as data quantization.
- Its quantization error is called inertia, within-cluster sum of squares (WCSS), or sum of squared errors (SSE).
- The standard heuristic alternates between assigning points to nearest centers and updating centers to the assigned-point centroids until assignments stop changing.
- The multi-cluster, higher-dimensional optimization problem is NP-hard, so heuristics generally find only a local fixpoint.
- The standard algorithm has complexity O(Nkdi), where i is the number of iterations.
3. THE ELBOW CRITERION
The elbow criterion chooses k from apparent diminishing returns in SSE, but similar-looking curves arise across well-clustered, uniform, and other data sets. Its geometric formalizations lack theoretical support and can be sensitive to scaling and the tested k range, motivating variance-based alternatives.
- The elbow plot places SSE on the y-axis against k on the x-axis and seeks a visible bend where additional clusters yield diminishing returns.For three well-separated clusters, the plot shows a clear inflection at k = 3.
- Figure 1 shows that elbow plots can look very similar for well-separated clusters, uniform data, and data containing a single cluster.This undermines interpreting a visually apparent bend as evidence for a meaningful number of clusters.
- Formalized elbow detectors include the jump method, L-method, Kneedle, modified curvature, elbow length, angle-based rules, and AutoElbow.These methods operationalize visual or geometric properties such as curvature, angles, distances, slopes, or proximity to a corner.
- Several elbow measures change when the analyzed k range changes, even when added candidate values perform poorly.The paper argues that these heuristics do not model the process generating the measured SSE curve.
- Geometric methods can select different optima after rescaling the data because SSE changes by α^2, although the clustering decision should not depend on that scaling.The paper also questions geometric operations on a graph whose axes have different scales.
- The paper proposes interpreting SSE through variance-like quantities and recommends established criteria such as VRC, BIC, or the Gap statistic instead of the elbow method.Its variance-based analysis can identify uniform and normally distributed data as unclustered, while different structural improvements may favor k = 8 or k = 25 on the many-blobs data.
4. THETRUECHALLENGESOFK-MEANS
Meaningful k-means results are harder to obtain than choosing k alone suggests because k-means assumes equally shaped spherical clusters, while preprocessing and data geometry can make other methods more appropriate.
- Model assumptions: K-means assumes all clusters have the same spherical shape because its sum-of-squared-errors objective lacks cluster- or axis-specific weights.The paper relates this assumption to k-means as a limiting case of Gaussian mixture modeling.
- Alternative algorithms: K-means may be inappropriate when clusters differ in shape, density, or geometry, motivating Gaussian mixture modeling or density-based alternatives.The paper specifically identifies Gaussian mixture modeling for several cases and DBSCAN for geographically shaped data.
- Preprocessing: Naive preprocessing can destroy clustering signal, such as when PCA on sparse input data captures overall vector length in its first component.The paper describes this as a common combination of preprocessing techniques and warns that the resulting signal may be unsuitable for clustering.
5. CONCLUSION
The paper argues that the elbow method is too unreliable to support conclusions about the number of clusters and urges the use of established alternatives instead.
- Conclusion: The authors recommend preferring VRC, BIC, or Gap statistics over the elbow method because the elbow lacks reliable theoretical support.They frame these as established alternatives that should be preferred in education, data analysis, and research.
- Conclusion: Educators should omit the elbow method or explain its problems alongside better alternatives.The recommendation responds to the method’s prevalence in education and online media.
- Conclusion: Researchers and reviewers should avoid accepting conclusions based on an “optimal” k selected with the elbow method.The authors characterize the method as too unreliable for such conclusions.