An efficient k-means clustering algorithm: analysis and implementation
The DOI matches its Crossref record; 60 of the 60 references it cites were found in a registry or an index.
Abstract
In k-means clustering, we are given a set of n data points in d-dimensional space R/sup d/ and an integer k and the problem is to determine a set of k points in Rd, called centers, so as to minimize the mean squared distance from each data point to its nearest center. A popular heuristic for k-means clustering is Lloyd's (1982) algorithm. We present a simple and efficient implementation of Lloyd's k-means clustering algorithm, which we call the filtering algorithm. This algorithm is easy to implement, requiring a kd-tree as the only major data structure. We establish the practical efficiency of the filtering algorithm in two ways. First, we present a data-sensitive analysis of the algorithm's running time, which shows that the algorithm runs faster as the separation between clusters increases. Second, we present a number of empirical studies both on synthetically generated data and on real data sets from applications in color quantization, data compression, and image segmentation.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
(1979) · Cited by 43,841
An introduction to probability theory and its applications
(1958) · Journal of the Franklin Institute · doi:10.1016/0016-0032(58)90688-4 · Cited by 29,269
(1967) · Cited by 23,719
Least squares quantization in PCM
Lloyd, S. (1982) · IEEE Transactions on Information Theory · doi:10.1109/tit.1982.1056489 · Cited by 15,836 · cited 1×
“(More accurately, it should be called the generalized Lloyd’s algorithm since Lloyd’s original result was for scalar data [37].)”
BackgroundJain, A. K., Murty, M. N., & Flynn, P. J. (1999) · ACM Computing Surveys · doi:10.1145/331499.331504 · Cited by 13,199 · cited 1×
“For further information on clustering and clustering algorithms, see [34], [11], [28], [30], [29].”
Background(1973) · CERN Document Server (European Organization for Nuclear Research) · Cited by 12,895
Introduction to Statistical Pattern Recognition
(1990) · Elsevier eBooks · doi:10.1016/c2009-0-27872-x · Cited by 11,031
Finding groups in data: an introduction to cluster analysis
(1991) · Choice Reviews Online · doi:10.5860/choice.28-4558 · Cited by 10,474
Self-Organization and Associative Memory
Kohonen, T. (1989) · Springer Series in Information Sciences · doi:10.1007/978-3-642-88163-3 · Cited by 8,740
Algorithms for Clustering Data
Sarle, W. S. (1990) · Technometrics · doi:10.1080/00401706.1990.10484648 · Cited by 7,865 · cited 3×
“For further information on clustering and clustering algorithms, see [34], [11], [28], [30], [29].”
BackgroundMethodMultidimensional binary search trees used for associative searching
Bentley, J. L. (1975) · Communications of the ACM · doi:10.1145/361002.361007 · Cited by 7,520 · cited 3×
“As mentioned earlier, the algorithm is based on storing the multidimensional data points in a kd-tree [7].”
BackgroundMethodVector Quantization and Signal Compression
Gersho, A., & Gray, R. M. (1992) · Springer eBooks · doi:10.1007/978-1-4615-3626-0 · Cited by 7,003 · cited 2×
“C LUSTERING problems arise in many different applications, such as data mining and knowledge discovery [19], data compression and vector quantization [24], and pattern recognition and pattern classification [16].”
BackgroundStatistical pattern recognition: a review
Jain, A. K., Duin, P. W., & Mao, J. (2000) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/34.824819 · Cited by 6,767 · cited 1×
“For further information on clustering and clustering algorithms, see [34], [11], [28], [30], [29].”
BackgroundAlgorithms for clustering data
Flury, B. (1989) · Journal of Statistical Planning and Inference · doi:10.1016/0378-3758(89)90033-5 · Cited by 6,432
Pattern Classification and Scene Analysis
Thompson, M., Duda, R. O., & Hart, P. E. (1974) · Leonardo · doi:10.2307/1573081 · Cited by 4,495 · cited 1×
“C LUSTERING problems arise in many different applications, such as data mining and knowledge discovery [19], data compression and vector quantization [24], and pattern recognition and pattern classification [16].”
BackgroundComputational Geometry--An Introduction.
Atallah, M. J., Preparata, F. P., & Shamos, M. I. (1986) · Mathematics of Computation · doi:10.2307/2008200 · Cited by 4,238
Wiley Series in Probability and Statistics
(2008) · Wiley series in probability and statistics · doi:10.1002/series1345 · Cited by 4,217
Introduction to statistical pattern recognition (2nd ed.)
Fukunaga, K. (1990) · Academic Press Professional, Inc. eBooks · Cited by 3,797
Preparata, F. P., & Shamos, M. I. (1985) · Springer eBooks · doi:10.1007/978-1-4612-1098-6 · Cited by 3,655
Finding Groups in Data: An Introduction to Cluster Analysis.
Sarle, W. S., Kaufman, L., & Rousseeuw, P. J. (1991) · Journal of the American Statistical Association · doi:10.2307/2290430 · Cited by 3,539
Advances in knowledge discovery and data mining
(1996) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(96)90007-3 · Cited by 2,971
An optimal algorithm for approximate nearest neighbor searching fixed dimensions
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1998) · Journal of the ACM · doi:10.1145/293347.293348 · Cited by 2,300
Self-citationX-means: Extending K-means with Efficient Estimation of the Number of Clusters
Pelleg, D., & Moore, A. (2000) · Cited by 2,245
Centroidal Voronoi Tessellations: Applications and Algorithms
Du, Q., Faber, V., & Gunzburger, M. (1999) · SIAM Review · doi:10.1137/s0036144599352836 · Cited by 2,244 · cited 1×
“Lloyd’s algorithm is based on the simple observation that the optimal placement of a center is at the centroid of the associated cluster (see [18], [15]).”
BackgroundCluster analysis of multivariate data : efficiency versus interpretability of classifications
Forgy, E. W. (1965) · Biometrics · Cited by 2,093
Efficient and Effective Clustering Methods for Spatial Data Mining
Ng, R. T., & Han, J. (1994) · Cited by 1,778
Self-organization and associative memory: 3rd edition
Kohonen, T. (1989) · Springer eBooks · Cited by 1,223
K-Means-Type Algorithms: A Generalized Convergence Theorem and Characterization of Local Optimality
Selim, S. Z., & Ismail, M. A. (1984) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.1984.4767478 · Cited by 1,212 · cited 1×
“See [8],[40],[47],[49]for furtherdiscussionofitsstatisticalandconvergenceproper-ties.”
Refining Initial Points for K-Means Clustering
Bradley, P. S., & Fayyad, U. M. (1998) · Cited by 1,031
An Introduction to Probability Theory and its Applications
Grubbs, F. E. (1967) · Technometrics · doi:10.1080/00401706.1967.10490472 · Cited by 1,017
BIRCH: A New Data Clustering Algorithm and Its Applications
Zhang, T., Ramakrishnan, R., & Livny, M. (1997) · Data Mining and Knowledge Discovery · doi:10.1023/a:1009783824328 · Cited by 888 · cited 4×
“These studies, as well as a comparison we ran against the popular clustering scheme, BIRCH 1 [50], are reported in Section4.”
MethodResultInfluentialScaling clustering algorithms to large databases
Bradley, P., Fayyad, U. M., & Reina, C. (1998) · Cited by 716
An optimal algorithm for approximate nearest neighbor searching
Arya, S., Mount, D. M., Netanyahu, N. S., Silverman, R., & Wu, A. Y. (1994) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · doi:10.5555/314464.314652 · Cited by 594
Self-citationLearning mixtures of Gaussians
Dasgupta, S. (2003) · 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039) · doi:10.1109/sffcs.1999.814639 · Cited by 588 · cited 2×
“This sort of approach has been applied recently by Dasgupta [13] and Dasgupta and Shulman [14] in the context of clustering data sets that are generated by mixtures of Gaussians.”
MethodAn efficient k-means clustering algorithm
Alsabti, K., Ranka, S., & Singh, V. K. (1997) · Syracuse University Libraries (Syracuse University) · Cited by 516
Convergence Properties of the K-Means Algorithms
Bottou, L., & Bengio, Y. (1994) · Cited by 398
Accelerating exact k-means algorithms with geometric reasoning
Pelleg, D., & Moore, A. (1999) · Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/312129.312248 · Cited by 377 · cited 4×
“These results confirm the general trend reported in [45], but the filtering algorithm’s performance in moderate dimensions 10 to 20 is considerably better.”
MethodResultInfluentialApproximation schemes for Euclidean k-medians and related problems
Arora, S., Raghavan, P., & Rao, S. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276718 · Cited by 341 · cited 1×
“These include the Euclidean k - medians (or the multisource Weber problem ) [3], [36] in which the objective is to minimize the sum of distances to the nearest center and the geometric k - center problem [1] in which the objective is to minimize the maximum distance from every point to its closest…”
BackgroundInaba, M., Katoh, N., & Imai, H. (1994) · Proceedings of the tenth annual symposium on Computational geometry - SCG '94 · doi:10.1145/177424.178042 · Cited by 321
Exact and Approximation Algorithms for Clustering
Agarwal, P. K., & Procopiuc, C. M. (2002) · Algorithmica · doi:10.1007/s00453-001-0110-y · Cited by 242 · cited 1×
“…the Euclidean k - medians (or the multisource Weber problem ) [3], [36] in which the objective is to minimize the sum of distances to the nearest center and the geometric k - center problem [1] in which the objective is to minimize the maximum distance from every point to its closest center.”
BackgroundA Central Limit Theorem for $k$-Means Clustering
Pollard, D. (1982) · The Annals of Probability · doi:10.1214/aop/1176993713 · Cited by 240 · cited 1×
“See [8], [40], [ 47 ], [49] for further discussion of its statistical and convergence properties.”
BackgroundA spatial filtering approach to texture analysis
Coggins, J. M., & Jain, A. K. (1985) · Pattern Recognition Letters · doi:10.1016/0167-8655(85)90053-4 · Cited by 223 · cited 1×
“It is also similar to the separation measure for cluster i of Coggins and Jain [12], defined to be min j 6(cid:136) i j (cid:22) (cid:133) i (cid:134) (cid:255) (cid:22) (cid:133) j (cid:134) j =(cid:27) (cid:133) i (cid:134) .”
ResultANN: library for approximate nearest neighbor searching
Arya, S., & Mount, D. M. (1998) · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · Cited by 209
Self-citationApplication of weighted Voronoi diagrams and randomization to variance-based k-clustering
Inaba, M. (1994) · Annual Symposium on Computational Geometry (SoCG) · Cited by 189
On Approximate Geometric k -Clustering
Matoušek, J. (2000) · Discrete & Computational Geometry · doi:10.1007/s004540010019 · Cited by 180
Analysis of approximate nearest neighbor searching with clustered point sets
Maneewongvatana, S., & Mount, D. M. (2002) · DIMACS series in discrete mathematics and theoretical computer science · doi:10.1090/dimacs/059/06 · Cited by 171 · cited 1×
“The data structure implemented was a kd-tree that was constructed from the ANN library [43] using the sliding midpoint rule [39].”
MethodSelf-citationVery Fast EM-Based Mixture Model Clustering Using Multiresolution Kd-Trees
Moore, A. (1998) · Cited by 153
The analysis of a simple k -means clustering algorithm
Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C., Silverman, R., & Wu, A. Y. (2000) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/336154.336189 · Cited by 149
Self-citationA Two-round Variant of EM for Gaussian MixturesPreprint
Dasgupta, S., & Schulman, L. J. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.3850 · Cited by 141 · cited 1×
“This sort of approach has been applied recently by Dasgupta [13] and Dasgupta and Shulman [14] in the context of clustering data sets that are generated by mixtures of Gaussians.”
MethodArya, S., & Mount, D. M. (2000) · Computational Geometry · doi:10.1016/s0925-7721(00)00022-5 · Cited by 135
Self-citationMathematical Programming in Data Mining
Mangasarian, O. L. (1997) · Data Mining and Knowledge Discovery · doi:10.1023/a:1009735908398 · Cited by 129 · cited 1×
“See [8],[40],[47],[49]for furtherdiscussionofitsstatisticalandconvergenceproper-ties.”
A database interface for clustering in large spatial databases
Ester, M., Kriegel, H., & Xu, X. (1995) · Cited by 127
A Nearly Linear-Time Approximation Scheme for the Euclidean k -Median Problem
Kolliopoulos, S. G., & Rao, S. B. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539702404055 · Cited by 126
Capoyleas, V., Rote, G., & Woeginger, G. J. (1991) · Journal of Algorithms · doi:10.1016/0196-6774(91)90007-l · Cited by 98
A Nearly Linear-Time Approximation Scheme for the Euclidean k-median Problem
Kolliopoulos, S. G., & Rao, S. B. (1999) · Lecture notes in computer science · doi:10.1007/3-540-48481-7_33 · Cited by 91 · cited 1×
“These include the Euclidean k-medians (or the multisource Weber problem) [3], [ 36 ] in which the objective is to minimize the sum of distances to the nearest center and the geometric k-center problem [1] in which the objective is to minimize the maximum distance from every point to its closest center.”
BackgroundAn Efficient Clustering Algorithm
Bhat, M. V., & Haupt, A. (1976) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1976.5408399 · Cited by 62
Analysis of approximate nearest neighbor searching with clustered point setsPreprint
Maneewongvatana, S., & Mount, D. M. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/9901013 · Cited by 58 · cited 1×
“The data structure implemented was a kd-tree that was constructed from the ANN library [43] using the sliding midpoint rule [39].”
MethodSelf-citationComputing nearest neighbors for moving points and applications to clustering
Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C., Silverman, R., & Wu, A. Y. (1999) · Cited by 21
Self-citationAn efficient clustering algorithm
Zhang, Y., Mao, J.-L., & Xiong, Z. (2004) · International Conference on Machine Learning and Cybernetics · doi:10.1109/icmlc.2003.1264483 · Cited by 19
Experimental results of randomized clustering algorithm
Inaba, M., Imai, H., & Katoh, N. (1996) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/237218.237406 · Cited by 14 · cited 1×
“This measure is often called the squared-error distortion [28], [24] and this type of clustering falls into the general category of variance-based clustering [27], [26].”
Background
Research works printed but not linked: 3
- Ball, Some Fundamental Concepts and Synthesis Procedures for Pattern Recognition Preprocessors
- Faber, 1994, Clustering and the Continuous $\big. k\hbox{-}{\rm{means}}\bigr.$ Algorithm, Los Alamos Science, 22, 138
- Forgey, 1965, Cluster Analysis of Multivariate Data: Efficiency vs. Interpretability of Classification, Biometrics, 21, 768,
Cited by
Data mining: concepts and techniques
(2012) · Choice Reviews Online · doi:10.5860/choice.49-3305 · Cited by 28,531
Survey of Clustering Algorithms
Xu, R., & WunschII, D. (2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2005.845141 · Cited by 6,197
Ikotun, A. M., Ezugwu, A. E., Abualigah, L., Abuhaija, B., & Heming, J. (2023) · Information Sciences · doi:10.1016/j.ins.2022.11.139 · Cited by 2,272
The k-means Algorithm: A Comprehensive Survey and Performance Evaluation
Ahmed, M., Seraj, R., & Islam, S. M. S. (2020) · Electronics · doi:10.3390/electronics9081295 · Cited by 1,717
Introduction to Machine Learning
Yu, F. R., & He, Y. (2019) · SpringerBriefs in Electrical and Computer Engineering · doi:10.1007/978-3-030-10546-4_1 · Cited by 1,594
Metadata
- Authors
- Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., & Wu, A. Y.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2002-07
- Volume
- 24
- Issue
- 7
- Pages
- 881-892
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2161160262
- Cited by
- 5,660
- References
- 60
- Citations by year
- 2026: 127 · 2025: 206 · 2024: 270 · 2023: 290 · 2022: 349 · 2021: 415 · 2020: 405 · 2019: 443 · 2018: 429 · 2017: 375 · 2016: 327 · 2015: 303 · 2014: 294 · 2013: 272 · 2012: 273
- FWCI
- 30.44
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Pattern Analysis and Machine Intelligence (publishedVersion)
- Funders
- National Science Foundation
- U.S. Department of Defense
- Army Research Laboratory
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Clustering Algorithms Research
- Physical Sciences › Computer Science › Information Systems › Data Mining and Machine Learning Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Methods and Mixture Models
- Keywords
- K-means clustering, Lloyd's algorithm, filtering algorithms, k-d tree, cluster separation, color quantization, data compression, image segmentation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.