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].”
BackgroundMethod
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
Vision based hand gesture recognition for human computer interaction: a survey
Rautaray, S. S., & Agrawal, A. (2015) · Artificial Intelligence Review · doi:10.1007/s10462-012-9356-9 · Cited by 1,526
“The most commonly used algorithm for solving this problem is the Lloyd’s k-means algorithm (Lloyd 1982; Kanungo et al. 2002) which iteratively assigns the patterns to clusters and computes the cluster centers.”
MethodConvergence of Edge Computing and Deep Learning: A Comprehensive Survey
Wang, X., Han, Y., Leung, V. C. M., Niyato, D., Yan, X., & Chen, X. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2020.2970550 · Cited by 1,498
“k-means clustering [236] and binary classification algorithms are used to determine which contents, already cached in edge nodes, should be further downloaded and cached from edge”
MethodA comparative study of efficient initialization methods for the k-means clustering algorithm
Celebi, M. E., Kingravi, H. A., & Vela, P. A. (2013) · Expert Systems with Applications · doi:10.1016/j.eswa.2012.07.021 · Cited by 1,214
“Furthermore, numerous sequential [11, 12] and parallel [13] acceleration techniques are available in the literature.”
BackgroundMethodK‐means clustering: A half‐century synthesis
Steinley, D. (2006) · British Journal of Mathematical and Statistical Psychology · doi:10.1348/000711005x48266 · Cited by 1,120
Statistical Mechanics: Theory and Molecular Simulation
Tuckerman, M. E. (2023) · doi:10.1093/oso/9780198825562.001.0001 · Cited by 973
Machine learning in wireless sensor networks: Algorithms, strategies, and applications
Alsheikh, M. A., Lin, S., Niyato, D., & Tan, H.-P. (2014) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2014.2320099 · Cited by 965
“1) K-means clustering: The k-means algorithm [61] is used to recognize data into different classes (known as clusters ).”
MethodResearch on K-Value Selection Method of K-Means Clustering Algorithm
Yuan, C., & Yang, H. (2019) · J · doi:10.3390/j2020016 · Cited by 846
“Two algorithms which extend the k-means algorithm to categorical domains and domains are reported in Reference [6], through the pattern mixing algorithm, the combination of the e ff ectiveness measure, in order to solve the problem of complex data and more noise in the real world.”
MethodInfluentialFadlullah, Z. M., Tang, F., Mao, B., Kato, N., Akashi, O., Inoue, T., & Mizutani, K. (2017) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2017.2707140 · Cited by 810
“Among the most frequently used clustering methods in WSNs, the K-means clustering [156] is notable.”
MethodAn IoT based smart irrigation management system using Machine learning and open source technologies
Goap, A., Sharma, D., Shukla, A. K., & Rama Krishna, C. (2018) · Computers and Electronics in Agriculture · doi:10.1016/j.compag.2018.09.040 · Cited by 676
SurroundSense: mobile phone localization via ambience fingerprinting
Azizyan, M., Constandache, I., & Roy Choudhury, R. (2009) · Proceedings of the 15th annual international conference on Mobile computing and networking · doi:10.1145/1614320.1614350 · Cited by 723
“On this scatterplot, we ran the K-means clustering algorithm [14] for increasing values of K.”
MethodA Brief Survey of Text Mining: Classification, Clustering and Extraction Techniques
Allahyari, M., Pouriyeh, S., Assefi, M., Safaei, S., Trippe, E. D., Gutiérrez, J. B., & Kochut, K. J. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1707.02919 · Cited by 509
Machine learning algorithms for wireless sensor networks: A survey
Praveen Kumar, D., Amgoth, T., & Annavarapu, C. S. R. (2019) · Information Fusion · doi:10.1016/j.inffus.2018.09.013 · Cited by 687
Xie, J., Yu, F. R., Huang, T., Xie, R., Liu, J., Wang, C., & Liu, Y. (2019) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2018.2866942 · Cited by 700
“For a more insightful discussion on k-means, please refer to [78] and [117].”
BackgroundHalder, R. K., Uddin, M. N., Uddin, M. A., Aryal, S., & Khraisat, A. (2024) · Journal of Big Data · doi:10.1186/s40537-024-00973-y · Cited by 520
A Survey on Machine Learning for Data Fusion
Meng, T., Jing, X., Yan, Z., & Pedrycz, W. (2020) · Information Fusion · doi:10.1016/j.inffus.2019.12.001 · Cited by 677
Selection of K in K-means clustering
Pham, D. T., Dimov, S. S., & Nguyen, C. D. (2005) · Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science · doi:10.1243/095440605x8298 · Cited by 597
Internal curing by superabsorbent polymers in ultra-high performance concrete
Justs, J., Wyrzykowski, M., Bajare, D., & Lura, P. (2015) · Cement and Concrete Research · doi:10.1016/j.cemconres.2015.05.005 · Cited by 602
Critical assessment of automated flow cytometry data analysis techniques
The FlowCAP Consortium, Aghaeepour, N., The DREAM Consortium, Finak, G., Hoos, H., Mosmann, T. R., Brinkman, R., Gottardo, R., & Scheuermann, R. H. (2013) · Nature Methods · doi:10.1038/nmeth.2365 · Cited by 598
“We have applied the K-means algorithm incorporating the following two techniques to achieve better separation of the K-means clusters and faster computation: i) the seeds of the K-means algorithm are generated by the kmeans++ [40]; ii) the algorithm is implemented by using k-d tree [41] to speed up computation.”
Thirty Years of Machine Learning: The Road to Pareto-Optimal Wireless Networks
Wang, J., Jiang, C., Zhang, H., Ren, Y., Chen, K.-C., & Hanzo, L. (2020) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2020.2965856 · Cited by 486
“One of the popular low-complexity iterative refinement algorithms suitable for K-means clustering is Lloyd’s algorithm [242], which often yields satisfactory performance after a low number of iterations.”
BackgroundComparative Analysis of K-Means and Fuzzy C-Means Algorithms
Ghosh, S., & Kumar, S. (2013) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2013.040406 · Cited by 536
“The time complexity of K-means [15] is O(ncdi) and time complexity of FCM [4] is O(ndc2i).”
BackgroundData Mining for the Internet of Things: Literature Review and Challenges
Chen, F., Deng, P., Wan, J., Zhang, D., Vasilakos, A. V., & Rong, X. (2015) · International Journal of Distributed Sensor Networks · doi:10.1155/2015/431047 · Cited by 528
Taylor, R. A., Pare, J. R., Venkatesh, A. K., Mowafi, H., Melnick, E. R., Fleischman, W., & Hall, M. K. (2016) · Academic Emergency Medicine · doi:10.1111/acem.12876 · Cited by 491
“31 K-means clustering aims to divide data into k clusters in which each data point belongs to the cluster with the closest mean.”
BackgroundFast approximate spectral clustering
Yan, D., Huang, L., & Jordan, M. I. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557118 · Cited by 474
“Recently a variety of approaches have been proposed for the initializa tion of k-means [22, 1, 31, 25, 6].”
BackgroundA local search approximation algorithm for k-means clustering
Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., & Wu, A. Y. (2002) · Proceedings of the eighteenth annual symposium on Computational geometry · doi:10.1145/513400.513402 · Cited by 474
“These include the Euclidean k-medians and the Weber problem [3, 25], in which the objective is to minimize the sum of distances to the nearest center, and the Euclidean k-center problem [1], in which the objective is to minimize the maximum distance.”
BackgroundSelf-citationMedical Image Segmentation Using K-Means Clustering and Improved Watershed Algorithm
Ng, H. P., Ong, S. H., Foong, K. W. C., Goh, P. S., & Nowinski, W. L. (2006) · 2006 IEEE Southwest Symposium on Image Analysis and Interpretation · doi:10.1109/ssiai.2006.1633722 · Cited by 458
“K-means clustering algorithm [9], [10], on the other hand, is a simple clustering method with low computational complexity as compared to FCM.”
MethodLiu, Z., Bessa, M. A., & Liu, W. K. (2016) · Computer Methods in Applied Mechanics and Engineering · doi:10.1016/j.cma.2016.04.004 · Cited by 463
An efficient hybrid approach based on PSO, ACO and k-means for cluster analysis
Niknam, T., & Amiri, B. (2010) · Applied Soft Computing · doi:10.1016/j.asoc.2009.07.001 · Cited by 433
Nick, M., Cherkaoui, R., & Paolone, M. (2014) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2014.2302020 · Cited by 429
Academics job satisfaction and job stress across countries in the changing academic environments
Shin, J. C., & Jung, J. (2014) · Higher Education · doi:10.1007/s10734-013-9668-y · Cited by 323
“clustering is a method of cluster analysis that aims to partition n observations into k clusters and in which each observation belongs to the cluster with the nearest mean (Kanungo et al. 2002).”
MethodK-means with Three different Distance Metrics
Singh, A., Yadav, A., & Rana, A. (2013) · International Journal of Computer Applications · doi:10.5120/11430-6785 · Cited by 380
Robust human activity recognition from depth video using spatiotemporal multi-fused features
Jalal, A., Kim, Y.-H., Kim, Y.-J., Kamal, S., & Kim, D. (2017) · Pattern Recognition · doi:10.1016/j.patcog.2016.08.003 · Cited by 384
Zhou, T., Song, Z., & Sundmacher, K. (2019) · Engineering · doi:10.1016/j.eng.2019.02.011 · Cited by 384
“The most popular clustering algorithms are k-means [48], hierarchical clustering [49], and hidden Markov modeling [50].”
How much can behavioral targeting help online advertising?
Yan, J., Liu, N., Wang, G., Zhang, W., Jiang, Y., & Chen, Z. (2009) · Proceedings of the 18th international conference on World wide web · doi:10.1145/1526709.1526745 · Cited by 365
Faroux, S., Kaptué Tchuenté, A. T., Roujean, J.-L., Masson, V., Martin, E., & Le Moigne, P. (2013) · Geoscientific Model Development · doi:10.5194/gmd-6-563-2013 · Cited by 319
“Printer-friendly Version Interactive Discussion D iscssion P aper | D iscssion P aper | D iscssion P aper | D iscssion P aper | objective function minimum (Kanungo et al., 2002).”
BackgroundMachine Learning and Deep Learning in smart manufacturing: The Smart Grid paradigm
Kotsiopoulos, T., Sarigiannidis, P., Ioannidis, D., & Tzovaras, D. (2021) · Computer Science Review · doi:10.1016/j.cosrev.2020.100341 · Cited by 341
Contextual classification with functional Max-Margin Markov Networks
Munoz, D., Bagnell, J. A., Vandapel, N., & Hebert, M. (2009) · 2009 IEEE Conference on Computer Vision and Pattern Recognition · doi:10.1109/cvpr.2009.5206590 · Cited by 306
“For the high-order models the cliques are defined to be the resulting clusters from two k-means segmentations [9] over each nodes’ spectral features and locations.”
MethodDai, H.-N., Wang, H., Xu, G., Wan, J., & Imran, M. (2020) · Enterprise Information Systems · doi:10.1080/17517575.2019.1633689 · Cited by 248
Reinforcement Learning in Multiple-UAV Networks: Deployment and Movement Design
Liu, X., Liu, Y., & Chen, Y. (2019) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2019.2922849 · Cited by 342
“As the K-means algorithm is very sensitive to the initial center, the performance of the K-means algorithm is deterministic over runs [46].”
MethodRahaman, M. M., Li, C., Yao, Y., Kulwa, F., Wu, X., Li, X., & Wang, Q. (2021) · Computers in Biology and Medicine · doi:10.1016/j.compbiomed.2021.104649 · Cited by 320
“Then, cell nuclei are extracted using k-means [14], clustering [15] or super-pixel [16] methods.”
MethodHan, W., Zhang, X., Wang, Y., Wang, L., Huang, X., Li, J., Wang, S., Chen, W., Li, X., Feng, R., et al. (2023) · ISPRS Journal of Photogrammetry and Remote Sensing · doi:10.1016/j.isprsjprs.2023.05.032 · Cited by 303
Clustering: A neural network approach
Du, K.-L. (2010) · Neural Networks · doi:10.1016/j.neunet.2009.08.007 · Cited by 325
“The LBG has been implemented by storing the data points via a kd tree, achieving typically an order of magnitude faster than the LBG (Kanungo et al., 2002).”
InfluentialA local search approximation algorithm for k-means clustering
Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., & Wu, A. Y. (2004) · Computational Geometry · doi:10.1016/s0925-7721(04)00021-5 · Cited by 460
Self-citationA model for early prediction of diabetes
Mahboob Alam, T., Iqbal, M. A., Ali, Y., Wahab, A., Ijaz, S., Imtiaz Baig, T., Hussain, A., Malik, M. A., Raza, M. M., Ibrar, S., et al. (2019) · Informatics in Medicine Unlocked · doi:10.1016/j.imu.2019.100204 · Cited by 295
Convergence of the Lloyd Algorithm for Computing Centroidal Voronoi Tessellations
Du, Q., Emelianenko, M., & Ju, L. (2006) · SIAM Journal on Numerical Analysis · doi:10.1137/040617364 · Cited by 305
“CVTs are indeed special as they enjoy very natural optimization properties which make them very popular in diverse scientific and engineering applications that include art design, astronomy, clustering, geometric modeling, image and data analysis, resource optimization, quadrature design, sensor networks, and numerica…”
BackgroundImproved Nyström low-rank approximation and error analysis
Zhang, K., Tsang, I. W., & Kwok, J. T. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390311 · Cited by 299
“Recent advances in speeding up the k-means algorithms (Elkan, 2003; Kanungo et al., 2001) also make this k-means-based sampling strategy particularly suitable for large-scale problems.”
BackgroundLi, Y., Kou, G., Li, G., & Peng, Y. (2022) · European Journal of Operational Research · doi:10.1016/j.ejor.2022.03.040 · Cited by 300
Correlation clustering in general weighted graphs
Demaine, E. D., Emanuel, D., Fiat, A., & Immorlica, N. (2006) · Theoretical Computer Science · doi:10.1016/j.tcs.2006.05.008 · Cited by 283
“(k-clustering) [11], minimizing the average distance between pairs of clustered points (k-clustering sum) [24], minimizing the maximum distance to a “centroid object’’ chosen for each cluster (k-center) [11], minimizing the average distance to such a centroid object (k-median) [13], minimizing the average squared dist…”
BackgroundAgricultural robots for field operations. Part 2: Operations and systems
Bechar, A., & Vigneault, C. (2017) · Biosystems Engineering · doi:10.1016/j.biosystemseng.2016.11.004 · Cited by 281
Twitter sentiment analysis using hybrid cuckoo search method
Chandra Pandey, A., Singh Rajpoot, D., & Saraswat, M. (2017) · Information Processing & Management · doi:10.1016/j.ipm.2017.02.004 · Cited by 299
A Similarity Measure for Text Classification and Clustering
Lin, Y.-S., Jiang, J.-Y., & Lee, S.-J. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2013.19 · Cited by 291
“Such highdimensionality and sparsity can be a severe challenge for similarity measure which is an important operation in text processing algorithms [5], [6], [10], [11], [23], [24], [28], [30], [33], [34], [37], [41], [42], [47], [49], [50].”
BackgroundConvolutional Discriminative Feature Learning for Induction Motor Fault Diagnosis
Sun, W., Zhao, R., Yan, R., Shao, S., & Chen, X. (2017) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2017.2672988 · Cited by 295
“Random generation [20] or unsupervised feature learning such as clustering [21] and au-”
BackgroundData mining for yield enhancement in semiconductor manufacturing and an empirical study
Chien, C.-F., Wang, W.-C., & Cheng, J.-C. (2007) · Expert Systems with Applications · doi:10.1016/j.eswa.2006.04.014 · Cited by 292
“Clustering problems arise in many different applications (Kanungo et al., 2002), such as data mining and knowledge discovery, data compression, vector quantization, pattern recognition and pattern classification.”
Background(2019) · NORA - Norwegian Open Research Archives · Cited by 291
Multilevel Cloud Detection in Remote Sensing Images Based on Deep Learning
Xie, F., Shi, M., Shi, Z., Yin, J., & Zhao, D. (2017) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2017.2686488 · Cited by 288
“We compare our cloud detection framework with K-means [30], Mean-shift [31], Chan-Vese [32], [33], and two cloud detection methods in [11] and [12].”
MethodCheng, G., Guo, L., Zhao, T., Han, J., Li, H., & Fang, J. (2013) · International Journal of Remote Sensing · doi:10.1080/01431161.2012.705443 · Cited by 281
“clustering) technique to cluster the keypoint descriptors in their feature space into a large number of clusters using the k-means clustering algorithm (Kanungo et al. 2002) and encode each keypoint descriptor by the index of the cluster to which it belongs.”
MethodToward Intelligent Vehicular Networks: A Machine Learning Framework
Liang, L., Ye, H., & Li, G. Y. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2018.2872122 · Cited by 240
“Classic clustering algorithms include k-means [47], hierarchical clustering [48], spectrum clustering [49], and Dirichlet process [50].”
MethodSelf-organizing Maps as Substitutes for K-Means Clustering
Bação, F., Lobo, V., & Painho, M. (2005) · Lecture Notes in Computer Science · doi:10.1007/11428862_65 · Cited by 266
“K-means is an iterative procedure, to place cluster centers, which quickly converges to a local minimum of its objective function (Bradley and Fayyad 1998; Kanungo, Mount et al. 2002).”
MethodThe Effectiveness of Lloyd-Type Methods for the k-Means Problem
Ostrovsky, R., Rabani, Y., Schulman, L., & Swamy, C. (2006) · 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06) · doi:10.1109/focs.2006.75 · Cited by 261
Computer-aided diagnosis of breast cancer based on fine needle biopsy microscopic images
Kowal, M., Filipczuk, P., Obuchowicz, A., Korbicz, J., & Monczak, R. (2013) · Computers in Biology and Medicine · doi:10.1016/j.compbiomed.2013.08.003 · Cited by 274
“The presented segmentation approach based on adaptive thresholding and clustering was implemented with four clustering algorithms: K-Means (KM) [27, 28, 29], Fuzzy C-Means (FCM) [30], Competitive Neural Network (CNN) [31, 32] and Gaussian Mixture Model (GMM) [33].”
MethodA review on particle swarm optimization algorithms and their applications to data clustering
Rana, S., Jasola, S., & Kumar, R. (2011) · Artificial Intelligence Review · doi:10.1007/s10462-010-9191-9 · Cited by 271
On data processing required to derive mobility patterns from passively-generated mobile phone data
Wang, F., & Chen, C. (2018) · Transportation Research Part C: Emerging Technologies · doi:10.1016/j.trc.2017.12.003 · Cited by 247
“For example, popular methods such as k-means and DBSCAN (Ester et al., 1996; Kanungo et al., 2002) require the number of clusters or density-related parameters be known, which cannot be specifically identified because of the variety of mobile phone usage and travel behaviors that exist across…”
BackgroundMethodNg, S. Y.-M., Yoshida, T., Zhang, J., & Georgopoulos, K. (2009) · Immunity · doi:10.1016/j.immuni.2009.01.014 · Cited by 247
“Clusters were categorized into twelve groups based on patterns of expression to derive nine molecular signatures associated with each stem and progenitor population (Kanungo et al., 2002).”
Palette-based photo recoloring
Chang, H., Fried, O., Liu, Y., DiVerdi, S., & Finkelstein, A. (2015) · ACM Transactions on Graphics · doi:10.1145/2766978 · Cited by 249
“Researchers have identified various opportunities to accelerate k -means, for example by organizing the data in K-D trees [Kanungo et al. 2002].”
Method3D-FUTURE: 3D Furniture Shape with TextURE
Fu, H., Jia, R., Gao, L., Gong, M., Zhao, B., Maybank, S., & Tao, D. (2021) · International Journal of Computer Vision · doi:10.1007/s11263-021-01534-z · Cited by 198
“For theme color and real-world size, we first adopt k-Means Clustering (Kanungo et al., 2002) to discretize real values and then transform them into one-hot vectors.”
MethodReal-Time Hyperbola Recognition and Fitting in GPR Data
Dou, Q., Wei, L., Magee, D. R., & Cohn, A. G. (2017) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2016.2592679 · Cited by 243
“The previous clustering algorithms are either based on the distance between points [22], [23] or the density of points within a”
Waltersmann, L., Kiemel, S., Stuhlsatz, J., Sauer, A., & Miehe, R. (2021) · Sustainability · doi:10.3390/su13126689 · Cited by 213
“It is one of the most frequently used algorithms for the clustering of objects [47].”
MethodAI-Based Two-Stage Intrusion Detection for Software Defined IoT Networks
Li, J., Zhao, Z., Li, R., & Zhang, H. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2018.2883344 · Cited by 240
The (black) art of runtime evaluation: Are we comparing algorithms or implementations?
Kriegel, H.-P., Schubert, E., & Zimek, A. (2017) · Knowledge and Information Systems · doi:10.1007/s10115-016-1004-2 · Cited by 229
“[9] and known as blacklisting [60] or filtering [48]) did not yieldmajor performance gains in theHubMiner implementation.”
BackgroundServerless Computing: State-of-the-Art, Challenges and Opportunities
Li, Y., Lin, Y., Wang, Y., Ye, K., & Xu, C. (2023) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2022.3166553 · Cited by 211
“, K-means clustering [69]) need to share states among multiple tasks.”
BackgroundMillimeter-Wave NOMA With User Grouping, Power Allocation and Hybrid Beamforming
Zhu, L., Zhang, J., Xiao, Z., Cao, X., Wu, D. O., & Xia, X.-G. (2019) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2019.2932070 · Cited by 230
“We use the K-means clustering algorithm to implement the user grouping, where the normalized channel correlation is defined as the measure [41].”
MethodXu, X.-H., Du, Z.-J., Chen, X.-H., & Cai, C.-G. (2019) · Information Sciences · doi:10.1016/j.ins.2018.10.058 · Cited by 234
An improved neural network-based approach for short-term wind speed and power forecast
Chang, G. W., Lu, H. J., Chang, Y. R., & Lee, Y. D. (2017) · Renewable Energy · doi:10.1016/j.renene.2016.12.071 · Cited by 233
Mittal, H., Pandey, A. C., Saraswat, M., Kumar, S., Pal, R., & Modwel, G. (2022) · Multimedia Tools and Applications · doi:10.1007/s11042-021-10594-9 · Cited by 192
“It applies PAM on complete data and considers only a subset of the possible swaps between the selected objects and unselected objects.”
MethodScalable learning of collective behavior based on sparse social dimensions
Tang, L., & Liu, H. (2009) · Proceedings of the 18th ACM conference on Information and knowledge management · doi:10.1145/1645953.1646094 · Cited by 233
“More complicated data structures such as kd-tree [1, 8] can be exploited to accelerate the process.”
BackgroundRadiomics in breast cancer: Current advances and future directions
Qi, Y.-J., Su, G.-H., You, C., Zhang, X., Xiao, Y., Jiang, Y.-Z., & Shao, Z.-M. (2024) · Cell Reports Medicine · doi:10.1016/j.xcrm.2024.101719 · Cited by 181
An Integrated Cluster Detection, Optimization, and Interpretation Approach for Financial Data
Li, T., Kou, G., Peng, Y., & Yu, P. S. (2022) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2021.3109066 · Cited by 221
“One limitation of k-Means is that hyperspheres are only appropriate when the variance of each feature is identical and no linear correlation exists [20].”
BackgroundMulti-source information fusion: Progress and future
LI, X., DUNKIN, F., & DEZERT, J. (2024) · Chinese Journal of Aeronautics · doi:10.1016/j.cja.2023.12.009 · Cited by 204
How do gamblers start gambling: identifying behavioural markers for high-risk internet gambling
Braverman, J., & Shaffer, H. J. (2012) · The European Journal of Public Health · doi:10.1093/eurpub/ckp232 · Cited by 210
Yao, X., Han, J., Zhang, D., & Nie, F. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2017.2694222 · Cited by 230
“, k-means [46] and spectral clustering [47] ) and SRCC algorithm proposed”
Zhang, Y., Li, X., Gao, L., Wang, L., & Wen, L. (2018) · Journal of Manufacturing Systems · doi:10.1016/j.jmsy.2018.04.005 · Cited by 226
An efficient approximation to the K-means clustering for massive data
Capó, M., Pérez, A., & Lozano, J. A. (2017) · Knowledge-Based Systems · doi:10.1016/j.knosys.2016.06.031 · Cited by 218
Machine learning in cybersecurity: A review
Handa, A., Sharma, A., & Shukla, S. K. (2019) · WIREs Data Mining and Knowledge Discovery · doi:10.1002/widm.1306 · Cited by 187
“It is a combination of the OCSVM method and K-means clustering method (Kanungo et al., 2002).”
MethodSpatiotemporal Patterns in Large-Scale Traffic Speed Prediction
Asif, M. T., Dauwels, J., Goh, C. Y., Oran, A., Fathi, E., Xu, M., Dhanya, M. M., Mitrovic, N., & Jaillet, P. (2014) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2013.2290285 · Cited by 211
“We use the k-means clustering to find the roads with similar performance [35].”
MethodSpatial-Spectral Structured Sparse Low-Rank Representation for Hyperspectral Image Super-Resolution
Xue, J., Zhao, Y.-Q., Bu, Y., Liao, W., Chan, J. C.-W., & Philips, W. (2021) · IEEE Transactions on Image Processing · doi:10.1109/tip.2021.3058590 · Cited by 217
“For a given MSI Y , we divide it into overlapped full band patches (FBPs) of size q × q × b, and then group all FBPs extracted from the input Y into K clusters as Yk ∈ Rq(2)×b×mk (k = 1, · · · , K ) by k-means algorithm [60], where mk is the number of similar FBPs in the K -th group.”
MethodDecision-making techniques in supplier selection: Recent accomplishments and what lies ahead
Chai, J., & Ngai, E. W. T. (2020) · Expert Systems with Applications · doi:10.1016/j.eswa.2019.112903 · Cited by 199
Cai, X., Chan, R., & Zeng, T. (2013) · SIAM Journal on Imaging Sciences · doi:10.1137/120867068 · Cited by 219
Minimum spanning tree partitioning algorithm for microaggregation
Laszlo, M., & Mukherjee, S. (2005) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2005.112 · Cited by 223
“To further investigate the performance of our algorithm, we also test it with 29 simulated data sets generated using the process described in [8]: c random cluster centers are generated uniformly over the d-dimensional hypercube ½ 1; 1 d.”
MethodOptimal UAV Caching and Trajectory in Aerial-Assisted Vehicular Networks: A Learning-Based Approach
Wu, H., Lyu, F., Zhou, C., Chen, J., Wang, L., & Shen, X. (2020) · IEEE Journal on Selected Areas in Communications · doi:10.1109/jsac.2020.3005469 · Cited by 213
“In this work, a widely used clustering method, K-means clustering [34], is adopted to cluster the vehicles by considering the following similarities: 1) Cellular Performance Similarity: When a UAV is dispatched into the system, the throughput gain increases if it serves vehicles with poor cellular performance [35].”
MethodAn Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP
Deng, Y., Liu, Y., & Zhou, D. (2015) · Mathematical Problems in Engineering · doi:10.1155/2015/212794 · Cited by 213
“More details about the concepts and description of k-means clustering can be found in a lot of literature [26–28].”
BackgroundClustered Nyström Method for Large Scale Manifold Learning and Dimension Reduction
Zhang, K., & Kwok, J. T. (2010) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2010.2064786 · Cited by 219
“1 For example, in [45] and [ 43 ], the k-means algorithm has been used on datasets with 262 K and 400 K samples.”
BackgroundMethodA FAST IMPLEMENTATION OF THE ISODATA CLUSTERING ALGORITHM
MEMARSADEGHI, N., MOUNT, D. M., NETANYAHU, N. S., & LE MOIGNE, J. (2007) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195907002252 · Cited by 209
“We also introduce an approximate version of this algorithm, in which points may be assigned, not to their nearest neighbor, but to an approximate nearest neighbor.”
MethodSelf-citationUAV-Aided Projection-Based Compressive Data Gathering in Wireless Sensor Networks
Ebrahimi, D., Sharafeddine, S., Ho, P.-H., & Assi, C. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2018.2878834 · Cited by 212
“The clustering subproblem can be represented as an updated version of K-means clustering [36].”
MethodToward optimal fragment generations for ab initio protein structure assembly
Xu, D., & Zhang, Y. (2013) · Proteins: Structure, Function, and Bioinformatics · doi:10.1002/prot.24179 · Cited by 201
“We use two clustering algorithms, SPICKER42 and k - means,43 to generate the nonredundant (phi, psi) pairs at each position.”
MethodRobust and Scalable Graph-Based Semisupervised Learning
Liu, W., Wang, J., & Chang, S.-F. (2012) · Proceedings of the IEEE · doi:10.1109/jproc.2012.2197809 · Cited by 196
Adaptive fuzzy-K-means clustering algorithm for image segmentation
Sulaiman, S., & Mat Isa, N. (2010) · IEEE Transactions on Consumer Electronics · doi:10.1109/tce.2010.5681154 · Cited by 197
“It has been extensively used in many areas, including in the statistics [1], [2], machine learning [3]-[5], pattern recognition [6]-[8], data mining [9][14], and image processing [15], [16].”
Background
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.