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
Items 201–300 of 1,008
Lyu, K., Garboczi, E. J., She, W., & Miao, C. (2019) · Cement and Concrete Composites · doi:10.1016/j.cemconcomp.2019.03.001 · Cited by 129
A Survey of Autonomous Human Affect Detection Methods for Social Robots Engaged in Natural HRI
McColl, D., Hong, A., Hatakeyama, N., Nejat, G., & Benhabib, B. (2015) · Journal of Intelligent & Robotic Systems · doi:10.1007/s10846-015-0259-2 · Cited by 145
“These focus points were learned through an unsupervised pattern matching strategy called Self Adaptive Winner takes all (SAW) [123], and a combination of log-polar transform and Gabor filters were applied to extract visual features.”
MethodDEPRESSION DIAGNOSIS SUPPORT SYSTEM BASED ON EEG SIGNAL ENTROPIES
FAUST, O., ANG, P. C. A., PUTHANKATTIL, S. D., & JOSEPH, P. K. (2014) · Journal of Mechanics in Medicine and Biology · doi:10.1142/s0219519414500353 · Cited by 124
Higher-Order Correlation Clustering for Image Segmentation
Kim, S., Nowozin, S., Kohli, P., & Yoo, C. D. (2011) · Cited by 127
Image Segmentation UsingHigher-Order Correlation Clustering
Kim, S., Yoo, C. D., Nowozin, S., & Kohli, P. (2014) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2014.2303095 · Cited by 127
“segmentation algorithm [11]) and non-graph based (examples include K-means [6], mean-shift [7], and EM [8]).”
BackgroundImage processing based rice plant leaves diseases in Thanjavur, Tamilnadu
Devi, T. G., & Neelamegam, P. (2018) · Cluster Computing · doi:10.1007/s10586-018-1949-x · Cited by 127
“K-means clustering technique is a frequently used method for segmentation [13] which is utilized in this research.”
MethodHuman Body Parts Estimation and Detection for Physical Sports Movements
Jalal, A., Nadeem, A., & Bobasu, S. (2019) · International Conference on Communication, Computing and Digital Systems (C-CODE) · doi:10.1109/c-code.2019.8680993 · Cited by 127
“Some of its applications are 3D games [1,2], health exercise systems [3-5], virtual reality, activity recognition, scene analyzing, security surveillance [6] and detecting human abnormal behavior [7-9], Recently, this research has received various directions such as extracting angle movements related to the full body,…”
BackgroundZhang, Q., Zhang, L. Y., Jin, C., Wang, Y. M., & Lin, F. (2019) · Ultramicroscopy · doi:10.1016/j.ultramic.2019.04.007 · Cited by 127
Validity index for clusters of different sizes and densities
Žalik, K. R., & Žalik, B. (2010) · Pattern Recognition Letters · doi:10.1016/j.patrec.2010.08.007 · Cited by 137
Complex Non-rigid Motion 3D Reconstruction by Union of Subspaces
Zhu, Y., Huang, D., la Torre, F. D., & Lucey, S. (2014) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2014.200 · Cited by 125
“Kmeans clustering was then applied to the affinity matrices to obtain the final group/clusters [6].”
MethodStatistical Textural Distinctiveness for Salient Region Detection in Natural Images
Scharfenberger, C., Wong, A. M., Fergani, K., Zelek, J., & Clausi, D. A. (2013) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2013.131 · Cited by 133
“Given the aforementioned model, a simple and efficient strategy employed in the proposed method to learning the sparse texture model of an image is to assert a L2-norm criteria and solve for Tr using the k-means algorithm [15].”
MethodSparsity-Driven Micro-Doppler Feature Extraction for Dynamic Hand Gesture Recognition
Li, G., Zhang, R., Ritchie, M., & Griffiths, H. (2017) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2017.2761229 · Cited by 128
Does deep learning help topic extraction? A kernel k-means clustering method with word embedding
Zhang, Y., Lü, J., Liu, F., Liu, Q., Porter, A. L., Chen, H., & Zhang, G. (2018) · Journal of Informetrics · doi:10.1016/j.joi.2018.09.004 · Cited by 125
“…parameter configuration (e.g., the number of clusters) and local optimization issues in k-means algorithms have attracted criticism; however, they achieve acceptable performance on large-scale data analytics and adapt well to a variety of real-world data sources (Kanungo et al. 2002; Jain 2010).”
BackgroundFlexible Body Partition-Based Adversarial Learning for Visible Infrared Person Re-Identification
Wei, Z., Yang, X., Wang, N., & Gao, X. (2021) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2021.3059713 · Cited by 125
“Since K-means algorithm [20] is an effective clustering method and easy to implement, we exploit it to cluster the feature maps.”
MethodPolat, K. (2012) · International Journal of Systems Science · doi:10.1080/00207721.2011.581395 · Cited by 120
“Among these clustering methods, the FCM clustering is chosen in weighting process since FCM is the extended version of KCM and is mostly used in applications and literature (MacQueen 1967; Kanungo et al. 2002).”
MethodOnboard contextual classification of 3-D point clouds with learned high-order Markov Random Fields
Munoz, D., Vandapel, N., & Hebert, M. (2009) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2009.5152856 · Cited by 141
“We used publicly available implementations of k-means clustering [19] and maxflow-mincut [20] performing inference.”
MethodEfficient manifold ranking for image retrieval
Xu, B., Bu, J., Chen, C., Cai, D., He, X., Liu, W., & Luo, J. (2011) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/2009916.2009988 · Cited by 123
“Note that we don’t have to update the anchors frequently, because informative anchors for a large data set are relatively stable (e.g., the cluster centers), even if a few new samples are added.”
BackgroundCircuit Tolerance Design Using Belief Rule Base
Xu, X., Liu, Z., Chen, Y., Xu, D., & Wen, C. (2015) · Mathematical Problems in Engineering · doi:10.1155/2015/908027 · Cited by 123
“Note that, in practice, there may be more than one acceptability region in the parameter space 𝑆 𝑢 ; in this case, some available clustering analysis methods (e.g., 𝑘 -means clustering [24]) can be used to recognize every disconnected acceptability region.”
Methodk-Means Has Polynomial Smoothed Complexity
Arthur, D., Manthey, B., & Röglin, H. (2009) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2009.14 · Cited by 146
“Despite its simplicity, the k-means method itself and variants thereof are still the subject of research [16], [4], [22].”
MethodCloud detection of remote sensing images by deep learning
Shi, M., Xie, F., Zi, Y., & Yin, J. (2016) · IEEE International Geoscience and Remote Sensing Symposium (IGARSS) · doi:10.1109/igarss.2016.7729176 · Cited by 123
“(a) Original image (b) Ground truth (c) K-means (d) Mean-shift (e) ChanVase (f) method[3] (g) the proposed method To evaluate the efficiency of our cloud detection algorithm, we compare our method with other four methods including three segmentation methods of K-means [9], Meanshift [10]and Chan–Vese [11], one cloud d…”
MethodZhou, H.-Y., Wang, F., & Tao, P. (2018) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.8b00652 · Cited by 128
Zhong, X., Xu, X., & Pan, B. (2021) · Information Fusion · doi:10.1016/j.inffus.2021.07.006 · Cited by 123
Huang, C., He, R., Ai, B., Molisch, A. F., Lau, B. K., Haneda, K., Liu, B., Wang, C., Yang, M., Oestges, C., et al. (2022) · IEEE Transactions on Antennas and Propagation · doi:10.1109/tap.2022.3149663 · Cited by 130
“A K-power-means (KPM) algorithm is proposed in [94] based on the classic K-means algorithm [95], which iteratively groups the MPCs based on the power-weighted MCD between each MPC and each cluster centroid.”
MethodSurvey on Exact kNN Queries over High-Dimensional Data Space
Ukey, N., Yang, Z., Li, B., Zhang, G., Hu, Y., & Zhang, W. (2023) · Sensors · doi:10.3390/s23020629 · Cited by 134
“It helps to improve the performance of many applications, such as k means clustering [55,56], outlier detection [57,58], kNN classification [59,60], k distance diagrams, missing value computation, etc.”
MethodUnsafe Diffusion: On the Generation of Unsafe Images and Hateful Memes From Text-To-Image Models
Qu, Y., Shen, X., He, X., Backes, M., Zannettou, S., & Zhang, Y. (2023) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3576915.3616679 · Cited by 274
“In this section, under the scope of unsafe images, we conduct a safety measurement on Text-to-Image models.”
MethodMaximum Margin Clustering Made Practical
Zhang, K., Tsang, I. W.-H., & Kwok, J. T.-Y. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2008.2010620 · Cited by 130
InferCode: Self-Supervised Learning of Code Representations by Predicting Subtrees
Bui, N. D. Q., Yu, Y., & Jiang, L. (2021) · 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE) · doi:10.1109/icse43902.2021.00109 · Cited by 102
A survey of data mining and social network analysis based anomaly detection techniques
Kaur, R., & Singh, S. (2016) · Egyptian Informatics Journal · doi:10.1016/j.eij.2015.11.004 · Cited by 118
Zhao, W., Deng, C.-H., & Ngo, C. (2018) · Neurocomputing · doi:10.1016/j.neucom.2018.02.072 · Cited by 136
Advances in Studies and Applications of Centroidal Voronoi Tessellations
Du, Q., Gunzburger, M., & Ju, L. (2010) · Numerical Mathematics Theory Methods and Applications · doi:10.4208/nmtma.2010.32s.1 · Cited by 150
Yinyang K-Means: A Drop-In Replacement of the Classic K-Means with Consistent Speedup
Ding, Y., Zhao, Y., Shen, X., Musuvathi, M., & Mytkowicz, T. (2015) · Cited by 120
Robust Bi-stochastic Graph Regularized Matrix Factorization for Data Clustering
Wang, Q., He, X., Xu, J., & Li, X. (2020) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2020.3007673 · Cited by 120
“1) k-means [44]: the most commonly used clustering method.”
MethodA Self-Reasoning Framework for Anomaly Detection Using Video-Level Labels
Zaheer, M. Z., Mahmood, A., Shin, H., & Lee, S. (2020) · IEEE Signal Processing Letters · doi:10.1109/lsp.2020.3025688 · Cited by 131
“Clustering Based Self-Reasoning: Given that anomaly detection is a binary problem, clustering algorithms such as kmeans [17] can be employed to distribute all fragments into two clusters.”
MethodDing, Y., Zhang, Z., Zhao, X., Cai, W., Yang, N., Hu, H., Huang, X., Cao, Y., & Cai, W. (2022) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2022.3202865 · Cited by 154
“, k-means [18], 623 FCM [22], FCM-S1 [25], SC [21], FSECSGL [46], S5C 624 [47], SGCNR [48], AE [49] +k-means, DEC [41], and 625 DS3C-Net [37], are considered for comparison.”
MethodIntelligent integrated sensing and communication: a survey
Zhang, J., Lu, W., Xing, C., Zhao, N., Al‐Dhahir, N., Karagiannidis, G. K., & Yang, X. (2024) · Science China Information Sciences · doi:10.1007/s11432-024-4205-8 · Cited by 131
Correlation Clustering with Partial Information
Demaine, E. D., & Immorlica, N. (2003) · Lecture notes in computer science · doi:10.1007/978-3-540-45198-3_1 · Cited by 140
Modular design of mechatronic systems with function modeling
van Beek, T. J., Erden, M. S., & Tomiyama, T. (2010) · Mechatronics · doi:10.1016/j.mechatronics.2010.02.002 · Cited by 120
Health Big Data Analytics: A Technology Survey
Harerimana, G., Jang, B., Kim, J. W., & Park, H. K. (2018) · IEEE Access · doi:10.1109/access.2018.2878254 · Cited by 119
“The K-means clustering technique is one of the most popular unsupervised learning techniques [81]–[83].”
MethodLasker, K., Topf, M., Sali, A., & Wolfson, H. J. (2009) · Journal of Molecular Biology · doi:10.1016/j.jmb.2009.02.031 · Cited by 119
Path-sensitive code embedding via contrastive learning for software vulnerability detection
Cheng, X. Y., Zhang, G., Wang, H., & Sui, Y. (2022) · ACM SIGSOFT International Symposium on Software Testing and Analysis (ISSTA) · doi:10.1145/3533767.3534371 · Cited by 151
“These twomatrices are trained using a joint reconstruction loss [45] by minimizing the distance between (1) H and the reconstructed matrix QH, (2) the cluster centroid matrix C, which is obtained using K-means clustering [39] on H, and the reconstructed matrix PH, and (3) H and the decoder outputs G.”
MethodCloud implementation of the K-means algorithm for hyperspectral image analysis
Haut, J. M., Paoletti, M. E., Plaza, J., & Plaza, A. (2016) · The Journal of Supercomputing · doi:10.1007/s11227-016-1896-3 · Cited by 118
“Clustering can be defined as a segmentation process in which pixels are assigned into a group that represents a specific land-cover class [5].”
BackgroundMethodInfected Fruit Part Detection using K-Means Clustering Segmentation Technique
Dubey, S. R., Dixit, P., Singh, N. K., & Gupta, J. P. (2013) · International Journal of Interactive Multimedia and Artificial Intelligence · doi:10.9781/ijimai.2013.229 · Cited by 117
“K-means method is an unsupervised clustering method that classifies the input data objects into multiple classes on the basis of their inherent distance from each other [16].”
MethodAdaptive weighted nonnegative low-rank representation
Wen, J., Zhang, B., Xu, Y. D., Yang, J. J., & Han, N. (2018) · Pattern Recognition · doi:10.1016/j.patcog.2018.04.004 · Cited by 117
Healthcare Techniques Through Deep Learning: Issues, Challenges and Opportunities
Nisar, D.-E.-M., Amin, R., Shah, N.-U.-H., Ghamdi, M. A. A., Almotiri, S. H., & Alruily, M. (2021) · IEEE Access · doi:10.1109/access.2021.3095312 · Cited by 135
“Deep learning techniques are widely used these days to help and understand healthcare-related matters [8].”
BackgroundBaseline wander and power line interference removal from ECG signals using eigenvalue decomposition
Sharma, R. R., & Pachori, R. B. (2018) · Biomedical Signal Processing and Control · doi:10.1016/j.bspc.2018.05.002 · Cited by 116
An Overview of Fairness in Clustering
Chhabra, A., Masalkovaite, K., & Mohapatra, P. (2021) · IEEE Access · doi:10.1109/access.2021.3114099 · Cited by 87
Audio-based human activity recognition using Non-Markovian Ensemble Voting
Stork, J. A., Spinello, L., Silva, J., & Arras, K. O. (2012) · IEEE RO-MAN · doi:10.1109/roman.2012.6343802 · Cited by 127
“,XM are clustered in K clusters by using k-means [12].”
MethodPost-training 4-bit quantization of convolution networks for rapid-deployment
Banner, R., Nahshan, Y., Hoffer, E., & Soudry, D. (2018) · arXiv · doi:10.48550/arxiv.1810.05723 · Cited by 115
Berg, C. J., Haardöerfer, R., Escoffery, C., Zheng, P., & Kegler, M. C. (2014) · Nicotine & Tobacco Research · doi:10.1093/ntr/ntu103 · Cited by 121
Ecological Networks and Neighborhood Social Organization
Browning, C. R., Calder, C. A., Soller, B., Jackson, A. L., & Dirlam, J. (2017) · American Journal of Sociology · doi:10.1086/691261 · Cited by 131
“…which is an iterative procedure that finds the k distinct subsets/clusters of activity locations that minimize the within-cluster sum of squared distances between the locations and the cluster centroid (mean of the locations within the cluster) for a prescribed value of k (Kanungo et al. 2002).”
BackgroundMethodHasnat, M. M., & Hasan, S. (2018) · Transportation Research Part C Emerging Technologies · doi:10.1016/j.trc.2018.09.006 · Cited by 119
Ultrafast manipulation of mirror domain walls in a charge density wave
Zong, A., Shen, X., Kogar, A., Ye, L., Marks, C. A., Chowdhury, D., Rohwer, T., Freelon, B., Weathersby, S. P., Li, R., et al. (2018) · Science Advances · doi:10.1126/sciadv.aau5501 · Cited by 114
K-means Clustering Algorithm with Improved Initial Center
Zhang, C., & Xia, S. (2009) · Workshop on Knowledge Discovery and Data Mining · doi:10.1109/wkdd.2009.210 · Cited by 122
“Other variations exist[4], but Lloyd's algorithm has remained popular because it converges extremely quickly in practice.”
BackgroundIntegrated Spectral and Spatial Information Mining in Remote Sensing Imagery
Li, J., & Narayanan, R. M. (2004) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2004.824221 · Cited by 114
“sufficient statistics at its nodes [35].”
Ghasemzadeh, H., & Jafari, R. (2011) · IEEE Sensors Journal · doi:10.1109/jsen.2010.2048205 · Cited by 109
A driving intention prediction method based on hidden Markov model for autonomous driving
Liu, S., Zheng, K., Zhao, L., & Fan, P. (2020) · Computer Communications · doi:10.1016/j.comcom.2020.04.021 · Cited by 121
A genetic algorithm using hyper-quadtrees for low-dimensional k-means clustering
Laszlo, M. J., & Mukherjee, S. (2006) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2006.66 · Cited by 112
“To evaluate the performance of our GA on more difficult clustering problems, we generated simulated data sets using the scheme described in [15].”
MethodLuo, X., Liu, Z., Shang, M., Lou, J., & Zhou, M. (2020) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2020.3040407 · Cited by 135
“f) For M3 and M4, we adopt K-means according to [44] to cluster the learnt node representations for community detection.”
MethodChen, C., Sun, F., Zhang, M., & Ding, B. (2022) · Proceedings of the ACM Web Conference 2022 · doi:10.1145/3485447.3511997 · Cited by 110
“Following the setting of k-means [34], the Euclidean distance is employed in this work, which is Algorithm 1 User-based Balanced Partition algorithm (UBP)”
MethodInfluentialA wearable system that knows who wears it
Cornelius, C. T., Peterson, R., Skinner, J., Halter, R. J., & Kotz, D. F. (2014) · International Conference on Mobile Systems, Applications, and Services · doi:10.1145/2594368.2594369 · Cited by 110
“clustering [17], where k was set to the desired number of Gaussian densities.”
BackgroundRaman Based Molecular Imaging and Analytics: A Magic Bullet for Biomedical Applications!?
Bocklitz, T. W., Guo, S., Ryabchykov, O., Vogler, N., & Popp, J. (2016) · Analytical Chemistry · doi:10.1021/acs.analchem.5b04665 · Cited by 104
Jalal, A., Mahmood, M., & Hasan, A. S. (2019) · 2019 16th International Bhurban Conference on Applied Sciences and Technology (IBCAST) · doi:10.1109/ibcast.2019.8667145 · Cited by 100
“Generally, the recognition of humanly actions involves detection of subjects [1], extraction of features [2], and classification [3].”
BackgroundClauß, T., Bouncken, R. B., Laudien, S. M., & Kraus, S. (2019) · International Journal of Innovation Management · doi:10.1142/s1363919620500152 · Cited by 123
A survey on parallel clustering algorithms for Big Data
Dafir, Z., Lamari, Y., & Slaoui, S. C. (2020) · Artificial Intelligence Review · doi:10.1007/s10462-020-09918-2 · Cited by 115
Applications of Artificial Intelligence Algorithms in the Energy Sector
Szczepaniuk, H., & Szczepaniuk, E. K. (2022) · Energies · doi:10.3390/en16010347 · Cited by 124
High-level synthesis of dynamic data structures: A case study using Vivado HLS
Winterstein, F., Bayliss, S., & Constantinides, G. A. (2013) · International Conference on Field-Programmable Technology (FPT) · doi:10.1109/fpt.2013.6718388 · Cited by 109
“We consider two K-means algorithms: Lloyd’s algorithm exhaustively computes Euclidean distances between data points and candidate centres to assign a closest centre to each point, whereas the filtering algorithm [6] uses a tree data structure (kd-tree, [6]) to prune unfavourable candidates early in the search process.”
MethodDeepCluster: A General Clustering Framework Based on Deep Learning
Tian, K., Zhou, S., & Guan, J. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-71246-8_49 · Cited by 135
“Among the existing algorithms, K-means [12] and Gaussian Mixture Models (GMM) [4] are two popular feature-based methods.”
MethodLiu, B., Li, L., Wang, X., & Cheng, S. (2018) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2018.2815518 · Cited by 109
“The basic principle of K-means algorithm is: the clustering could be realized through calculating the Euclidean distance to evaluate the degree of similarity among different data samples [27], and the clustering centers are updated continuously in the clustering process until the exit condition is satisfied [28].”
MethodCommodity single board computer clusters and their applications
Johnston, S. J., Basford, P. J., Perkins, C. S., Herry, H., Tso, F. P., Pezaros, D. P., Mullins, R., Yoneki, E., Cox, S., & Singer, J. (2018) · Future Generation Computer Systems · doi:10.1016/j.future.2018.06.048 · Cited by 109
Robust Spatio-Temporal Features for Human Interaction Recognition Via Artificial Neural Network
Mahmood, M., Jalal, A., & Sidduqi, M. A. (2018) · International Conference on Frontiers of Information Technology (FIT) · doi:10.1109/fit.2018.00045 · Cited by 109
“Usually, these interactions are represented by bodily actions and sentiments between person to person or group interactions [3-5].”
BackgroundSurviving or thriving: The role of learning for the resilient performance of small firms
Battisti, M., Beynon, M. J., Pickernell, D. G., & Deakins, D. (2019) · Journal of Business Research · doi:10.1016/j.jbusres.2019.03.006 · Cited by 123
“FCM (Bezdek, 1980; 1981) is a development of the well-known crisp k -means technique (MacQueen, 1967; Kanungo et al., 2002), which allows objects to have degrees of association (membership) to all individual clusters.”
Safaee, M. M., Gravely, M., & Roxbury, D. (2021) · Advanced Functional Materials · doi:10.1002/adfm.202006254 · Cited by 112
VCells: Simple and Efficient Superpixels Using Edge-Weighted Centroidal Voronoi Tessellations
Wang, J., & Wang, X. (2012) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2012.47 · Cited by 112
“In this paper, we propose a novel approach to solve superpixel problems based on a generalized concept of Centroidal Voronoi Tessellations (CVTs) (e.g., [27], [6], [7], [11], [13], [8], [14]).”
MethodTracking people in 3D using a bottom-up top-down detector
Spinello, L., Luber, M., & Arras, K. O. (2011) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2011.5980085 · Cited by 117
“289, 415 descriptors are collected and clustered using kmeans with an implementation optimized for large data sets [23].”
MethodNew fuzzy C-means clustering method based on feature-weight and cluster-weight learning
Hashemzadeh, M., Oskouei, A. G., & Farajzadeh, N. (2019) · Applied Soft Computing · doi:10.1016/j.asoc.2019.02.038 · Cited by 107
High temperature oxidation of corrosion resistant alloys from machine learning
Taylor, C. D., & Tossey, B. M. (2021) · npj Materials Degradation · doi:10.1038/s41529-021-00184-3 · Cited by 116
Boikova, T., Zeverte-Rivza, S., Rivza, P., & Rivza, B. (2021) · Sustainability · doi:10.3390/su132111689 · Cited by 86
“The aim of this method is to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean (cluster centers), serving as a prototype of the cluster [54,55].”
MethodLane‐Changing Behavior on Urban Streets: An “In‐Vehicle” Field Experiment‐Based Study
Sun, D., & Elefteriadou, L. (2012) · Computer-Aided Civil and Infrastructure Engineering · doi:10.1111/j.1467-8667.2011.00747.x · Cited by 107
“Level 5: Generally conduct (>90%, strong) To classify drivers into groups, the K-means algorithm (Kanungo et al., 2002) was used to cluster n (n = 40) participants based on overall aggressiveness into k (k = 1, 2, 3, 4, or 5) partitions, k n.”
MethodManhattan hashing for large-scale image retrieval
Kong, W., Li, W.-J., & Guo, M. (2012) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/2348283.2348293 · Cited by 110
Adaptive Wireless Video Streaming Based on Edge Computing: Opportunities and Approaches
Wang, D., Peng, Y., Ma, X., Ding, W., Jiang, H., Chen, F., & Liu, J. (2019) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2018.2828426 · Cited by 103
“Therefore, we consider to use a clustering algorithm to group users, and we adopt the widely used k-means clustering [38] algorithm, which aims to minimize the maximum distance”
MethodImproved object recognition results using SIFT and ORB feature detector
Gupta, S., Kumar, M., & Garg, A. (2019) · Multimedia Tools and Applications · doi:10.1007/s11042-019-08232-6 · Cited by 119
Kulin, M., Kazaz, T., Poorter, E. D., & Moerman, I. (2021) · Electronics · doi:10.3390/electronics10030318 · Cited by 132
DeepSafe: A Data-Driven Approach for Assessing Robustness of Neural Networks
Gopinath, D., Katz, G., Păsăreanu, C. S., & Barrett, C. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-01090-4_1 · Cited by 128
“Here we focus on a particularly popular clustering algorithm called kMeans [9] (although our approach could be implemented using different clustering algorithms as well).”
MethodClustering analysis using a novel locality-informed grey wolf-inspired clustering approach
Aljarah, I., Mafarja, M. M., Heidari, A. A., Faris, H., & Mirjalili, S. (2019) · Knowledge and Information Systems · doi:10.1007/s10115-019-01358-x · Cited by 105
“In addition, we compare the results of GWOTS with those computed by commonly used methods such as the well-regarded K -means [36], K -medoids [59], hierarchical clustering (HC) [75], and furthest first (FF) [11] techniques.”
MethodAnomaly Detection and Classification using Distributed Tracing and Deep Learning
Nedelkoski, S., Cardoso, J., & Kao, O. (2019) · 2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID) · doi:10.1109/ccgrid.2019.00038 · Cited by 84
“[21] T.”
Ding, Y., Zhang, Z., Kang, W., Yang, A., Zhao, J., Feng, J., Hong, D., & Zheng, Q. (2025) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2025.3556276 · Cited by 105
“Prophase, some clustering methods initially developed for natural images have been adopted for HSI, including K - means clustering [13], possibilistic C-means (PCMs) [14], spectral clustering [15], fuzzy C-means (FCMs) [16], and density peak clustering [17].”
Human and computer recognition of regional accents and ethnic groups from British English speech
Hanani, A. A., Russell, M. J., & Carey, M. J. (2012) · Computer Speech & Language · doi:10.1016/j.csl.2012.01.003 · Cited by 104
“Particularly in the NIST LREs, 2048 to 4096 components are usually used and the GMM parameters are initialized with several iterations of the k-means cluster algorithm [77].”
Bouyer, A., & Hatamlou, A. (2018) · Applied Soft Computing · doi:10.1016/j.asoc.2018.03.011 · Cited by 104
Gao, J., Yu, Z., Wang, L., & Vejre, H. (2019) · Ecological Indicators · doi:10.1016/j.ecolind.2019.105579 · Cited by 113
Unsupervised quadratic surface support vector machine with application to credit risk assessment
Luo, J., Yan, X., & Tian, Y. (2019) · European Journal of Operational Research · doi:10.1016/j.ejor.2019.08.010 · Cited by 104
Park, J. E., Kim, H. S., Kim, N., Park, S. Y., Kim, Y., & Kim, J. H. (2020) · Clinical Cancer Research · doi:10.1158/1078-0432.ccr-20-2156 · Cited by 106
“Alternatively, the clustering of voxels is advantageous because it requires no prior assumption (30) and is not affected by acquisitions that are normalized by the normal brain tissue.”
BackgroundThe Manumeter: A Wearable Device for Monitoring Daily Use of the Wrist and Fingers
Friedman, N., Rowe, J. B., Reinkensmeyer, D. J., & Bachman, M. (2014) · IEEE Journal of Biomedical and Health Informatics · doi:10.1109/jbhi.2014.2329841 · Cited by 100
“We locate center positions for the 25 RBFs using a k-means algorithm to identify cluster centers within our differential measurement data [35].”
MethodEEG Patterns in Mild Cognitive Impairment (MCI) Patients
Baker, M. C., Akrofi, K., Schiffer, R. W., & ́Boyle, M. O. (2008) · The Open Neuroimaging Journal · doi:10.2174/1874440000802010052 · Cited by 118
“Channel locations and frequency bands showing significant differences between control and AD participants (henceforth referred to as the feature set) were subsequently used as inputs for a k-means clustering algorithm [26].”
MethodBui, N. D. Q., Yu, Y., & Jiang, L. (2021) · Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval · doi:10.1145/3404835.3462840 · Cited by 103
Harnessing big data to rethink land heterogeneity in Earth system models
Chaney, N. W., Huijgevoort, M. H. J. V., Shevliakova, E., Malyshev, S. L., Milly, P. C. D., Gauthier, P. P. G., & Sulman, B. N. (2018) · Hydrology and earth system sciences · doi:10.5194/hess-22-3311-2018 · Cited by 106
“This challenge is analogous to image compression where the goal is to maximize an image’s information content while minimizing disk storage (e.g., clustering) (Kanungo et al., 2002).”
Clustering by Local Gravitation
Wang, Z., Yu, Z., Chen, C. L. P., You, J., Gu, T., Wong, H.-S., & Zhang, J. (2017) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2017.2695218 · Cited by 105
An integrated data-driven framework for urban energy use modeling (UEUM)
Abbasabadi, N., Ashayeri, M., Azari, R. S., Stephens, B., & Heidarinejad, M. (2019) · Applied Energy · doi:10.1016/j.apenergy.2019.113550 · Cited by 105
“The k-means clustering algorithm, which represents an efficient clustering method [54], was applied to define the typology (archetype) of buildings from the real urban context.”
MethodHybrid Dynamic Contrast and Probability Distillation for Unsupervised Person Re-Id
Cheng, D., Zhou, J., Wang, N., & Gao, X. (2022) · IEEE Transactions on Image Processing · doi:10.1109/tip.2022.3169693 · Cited by 104
Chromosome territories and the global regulation of the genome
Fritz, A. J., Sehgal, N., Pliss, A., Xu, J., & Berezney, R. (2019) · Genes Chromosomes and Cancer · doi:10.1002/gcc.22732 · Cited by 106
Rahim, T., Usman, M. A., & Shin, S. Y. (2020) · Computerized Medical Imaging and Graphics · doi:10.1016/j.compmedimag.2020.101767 · Cited by 111
“Using k-means clustering algorithm [114] that get input represented image pixel vectors in the color space, consistent cluster centers are calculated.”
Method
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.