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 301–400 of 1,008
Best-effort parallel execution framework for Recognition and mining applications
Meng, J., Chakradhar, S., & Raghunathan, A. (2009) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2009.5160991 · Cited by 101
“For example, efficient algorithms to reduce the amount of computation in K-means clustering have been proposed in [1, 12, 9].”
MethodWheat grain classification by using dense SIFT features with SVM classifier
Olgun, M., Onarcan, A. O., Özkan, K., Işık, Ş., Sezer, O., Özgişi, K., Ayter, N. G., Başçiftçi, Z. B., Ardıç, M., & Koyuncu, O. (2016) · Computers and Electronics in Agriculture · doi:10.1016/j.compag.2016.01.033 · Cited by 101
“Specifically, k-means clustering algorithm (Jain, 2010; Kanungo et al., 2002) is a popular and unsupervised learning algorithm as the label of groups is unknown.”
MethodTheoretical Analysis of the k-Means Algorithm – A Survey
Blömer, J., Lammersen, C., Schmidt, M., & Sohler, C. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-49487-6_3 · Cited by 125
“Different algorithms based on this idea are given in [10, 54, 69].”
MethodZhang, Q., Zhao, X., & Tang, H. (2018) · Climate and Development · doi:10.1080/17565529.2018.1442808 · Cited by 107
“The K-means clustering method (Kanungo et al., 2002) was used to divide the sample into three classes: low-income”
MethodLabel Distribution Learning with Label Correlations on Local Samples
Jia, X., Li, Z., Zheng, X., Li, W., & Huang, S.-J. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2943337 · Cited by 100
“For easy implementation, k-means [27] is utilized as the clustering method.”
MethodMulti-objective green meal delivery routing problem based on a two-stage solution strategy
Liao, W., Zhang, L., & Wei, Z. (2020) · Journal of Cleaner Production · doi:10.1016/j.jclepro.2020.120627 · Cited by 100
Cooperative Caching Strategy With Content Request Prediction in Internet of Vehicles
Wang, R., Kan, Z., Cui, Y., Wu, D., & Zhen, Y. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3056084 · Cited by 100
“parts that are vehicle clustering based on K-means [31], content request prediction based on LSTM, and the reinforcement learning-based algorithm for CCCRP.”
MethodMultiview Subspace Clustering Using Low-Rank Representation
Chen, J., Yang, S., Mao, H., & Fahy, C. (2021) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2021.3087114 · Cited by 109
“A number of subspace clustering methods aim to identify groups and achieve impressive performance for singleview data [22].”
Classification of pulsed eddy current GMR data on aircraft structures
Kim, J. J., Yang, G., Удпа, Л., & Udpa, S. S. (2009) · NDT & E International · doi:10.1016/j.ndteint.2009.10.003 · Cited by 100
Architectural Tactics for Big Data Cybersecurity Analytics Systems: A Review
Ullah, F., & Babar, M. A. (2019) · Journal of Systems and Software · doi:10.1016/j.jss.2019.01.051 · Cited by 113
A Collaborative Fuzzy Clustering Algorithm in Distributed Network Environments
Zhou, J., Chen, C. L. P., Chen, L., & Li, H. (2014) · IEEE Transactions on Fuzzy Systems · doi:10.1109/tfuzz.2013.2294205 · Cited by 99
Learning Discriminative Key Poses for Action Recognition
Liu, L., Shao, L., Zhen, X., & Li, X. (2013) · IEEE Transactions on Cybernetics · doi:10.1109/tsmcb.2012.2231959 · Cited by 105
“, K-means clustering [14], are employed to construct a codebook on which all the features from a video sequence are mapped to form a histogram representation; the final representation is then fed to a classifier, e.”
MethodK*-Means: An Effective and Efficient K-Means Clustering Algorithm
Qi, J., Yu, Y., Wang, L., & Liu, J. (2016) · doi:10.1109/bdcloud-socialcom-sustaincom.2016.46 · Cited by 99
“al [18] propose an efficient filtering k-means method by using kd-tree to store data points and then utilizing the”
MethodAn efficient k-means clustering filtering algorithm using density based initial cluster centers
Kumar, K. M., & Reddy, A. R. M. (2017) · Information Sciences · doi:10.1016/j.ins.2017.07.036 · Cited by 108
Jooshaki, M., Nad, A., & Michaux, S. P. (2021) · Minerals · doi:10.3390/min11080816 · Cited by 110
Huang, Q., & Wong, D. W. S. (2015) · Annals of the Association of American Geographers · doi:10.1080/00045608.2015.1081120 · Cited by 99
“For most clustering methods, such as the popular K -mean algorithm in activity pattern analysis (Shaw and Yu 2009; Chen et al. 2011), the number of clusters has to be predetermined (Kanungo et al. 2002).”
MethodA collaborative recommender system enhanced with particle swarm optimization technique
Katarya, R., & Verma, O. P. (2016) · Multimedia Tools and Applications · doi:10.1007/s11042-016-3481-4 · Cited by 103
“According to [2, 9, 15, 21, 24, 30, 36, 44], the simplest clustering algorithm used is k-means, which categorizes items into k clusters.”
MethodLarge Graph Clustering With Simultaneous Spectral Embedding and Discretization
Wang, Z., Li, Z., Wang, R., Nie, F., & Li, X. (2020) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2020.3002587 · Cited by 98
Alsayat, A. (2022) · Neural Computing and Applications · doi:10.1007/s00521-022-07992-x · Cited by 98
EMR: A Scalable Graph-Based Ranking Model for Content-Based Image Retrieval
Xu, B., Bu, J., Chen, C., Wang, C., Cai, D., & He, X. (2014) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2013.70 · Cited by 97
“Some fast k-means algorithms [38] can speed up the computation.”
MethodLocal descriptors for soybean disease recognition
Pires, R. D. L., Gonçalves, D. N., Oruê, J. P. M., Kanashiro, W. E. S., Junior, J. F. R., Machado, B. B., & Gonçalves, W. N. (2016) · Computers and Electronics in Agriculture · doi:10.1016/j.compag.2016.04.032 · Cited by 97
Model-based evolutionary algorithms: a short survey
Cheng, R., He, C., Jin, Y., & Yao, X. (2018) · Complex & Intelligent Systems · doi:10.1007/s40747-018-0080-1 · Cited by 97
“the K-means [15]), classification models”
Structural and developmental principles of neuropil assembly in C. elegans
Moyle, M. W., Barnes, K. M., Kuchroo, M., Gonopolskiy, A., Duncan, L. H., Sengupta, T., Shao, L., Guo, M., Santella, A., Christensen, R., et al. (2021) · Nature · doi:10.1038/s41586-020-03169-5 · Cited by 89
DUAL: Acceleration of Clustering Algorithms using Digital-based Processing In-Memory
Imani, M., Pampana, S., Gupta, S., Zhou, M., Kim, Y., & Rosing, T. (2020) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1109/micro50266.2020.00039 · Cited by 120
“generated cluster centers [61].”
Intelligent Diagnosis and Prognosis of Tool Wear Using Dominant Feature Identification
Zhou, J., Pang, C. K., Lewis, F. L., & Zhong, Z. W. (2009) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2009.2023318 · Cited by 96
“…works that have been devoted to tool wear monitoring in the machining process include tool wear sensing and metal-removing rate control [1], using of acoustic emission signal to detect abnormal event in the machining process [2], and using current-sensor-based feed cutting force estimates [3].”
MethodEfficient registration of multi-view point sets by K-means clustering
Zhu, J., Jiang, Z., Evangelidis, G., Zhang, C., Pang, S., & Li, Z. (2019) · Information Sciences · doi:10.1016/j.ins.2019.03.024 · Cited by 96
Applying data mining in investigating money laundering crimes
Zhang, Z. M., Salerno, J. J., & Yu, P. S. (2003) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/956750.956851 · Cited by 95
Robust Intratumor Partitioning to Identify High-Risk Subregions in Lung Cancer: A Pilot Study
Wu, J., Gensheimer, M. F., Dong, X., Rubin, D. L., Napel, S. A., Diehn, M., Loo, B. W., & Li, R. (2016) · International Journal of Radiation Oncology*Biology*Physics · doi:10.1016/j.ijrobp.2016.03.018 · Cited by 98
“For patientlevel tumor oversegmentation, the k-means clustering algorithm with spatial constraint (23) was used to group voxels with similar features together for each tumor, with squared Euclidean distance as the distance measure.”
MethodVoronoi Tessellations and Their Application to Climate and Global Modeling
Ju, L., Ringler, T. D., & Gunzburger, M. (2011) · Lecture notes in computational science and engineering · doi:10.1007/978-3-642-11640-7_10 · Cited by 111
“context and in its simplest form, CVT reduces to the well-known k-means clustering algorithm (Gersho and Gray 1992; Hartigan 1975; Kanungo et al. 2002 ).”
BackgroundRoullier, V., Lézoray, O., Ta, V., & Elmoataz, A. (2011) · Computerized Medical Imaging and Graphics · doi:10.1016/j.compmedimag.2011.02.005 · Cited by 94
An Edge-Weighted Centroidal Voronoi Tessellation Model for Image Segmentation
Wang, J., Ju, L., & Wang, X. (2009) · IEEE Transactions on Image Processing · doi:10.1109/tip.2009.2021087 · Cited by 95
Smoothed Analysis of the k-Means Method
Arthur, D., Manthey, B., & Röglin, H. (2011) · Journal of the ACM · doi:10.1145/2027216.2027217 · Cited by 118
Farooq, A., Jalal, A., & Kamal, S. (2015) · KSII Transactions on Internet and Information Systems · doi:10.3837/tiis.2015.05.017 · Cited by 93
“These feature vectors are symbolized in the form of codebook which are generated based on k-mean clustering algorithm ( k =32) [35] and each feature’s patch is assigned to it’s nearest neighbor in the codebook.”
MethodVisualization and Visual Analytics Approaches for Image and Video Datasets: A Survey
Afzal, S., Ghani, S., Hittawe, M. M., Rashid, S. F., Knio, O., Hadwiger, M., & Hoteit, I. (2023) · ACM Transactions on Interactive Intelligent Systems · doi:10.1145/3576935 · Cited by 105
Automatic image segmentation based on PCNN with adaptive threshold time constant
Wei, S., Qu, H., & Hou, M. (2011) · Neurocomputing · doi:10.1016/j.neucom.2011.01.005 · Cited by 93
“The first column shows the original image; the other four columns show the corresponding segmentation results by our PCNN, Otsu, GMM and K-means, respectively.”
MethodInfluentialThe Multiple Unmanned Air Vehicle Persistent Surveillance Problem: A Review
Nigam, N. (2014) · Machines · doi:10.3390/machines2010013 · Cited by 93
“[74] uses an asynchronous distributed version of the Lloyd’s algorithm [134] for multi-robot coordination, similar to Ref.”
MethodAn Incremental K-means algorithm
Pham, D. T., Dimov, S., & Nguyen, C. D. (2004) · Proceedings of the Institution of Mechanical Engineers Part C Journal of Mechanical Engineering Science · doi:10.1243/0954406041319509 · Cited by 93
Who uses web search for what: and how
Weber, I., & Jaimes, A. (2011) · Proceedings of the fourth ACM international conference on Web search and data mining · doi:10.1145/1935826.1935839 · Cited by 91
“cussed next was computed using a k-means clustering algorithm [15, 16] for the topic distributions for each user.”
MethodA new subset based deep feature learning method for intelligent fault diagnosis of bearing
Zhang, Y., Li, X., Gao, L., & Li, P. (2018) · Expert Systems with Applications · doi:10.1016/j.eswa.2018.05.032 · Cited by 92
Zhang, H., Chen, H., Guo, Y., Wang, J., Li, G., & Shen, L. (2019) · Applied Thermal Engineering · doi:10.1016/j.applthermaleng.2019.114098 · Cited by 91
Wyrzykowski, M., Trtik, P., Münch, B., Weiss, J., Vontobel, P., & Lura, P. (2015) · Cement and Concrete Research · doi:10.1016/j.cemconres.2015.03.013 · Cited by 90
Xu, H., Croot, P. L., & Zhang, C. (2021) · Environment International · doi:10.1016/j.envint.2021.106456 · Cited by 92
A fast k-means implementation using coresets
Frahling, G., & Sohler, C. (2006) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/1137856.1137879 · Cited by 90
A fast -means clustering algorithm using cluster center displacement
Lai, J. Z. C., Huang, T.-J., & Liaw, Y. (2009) · Pattern Recognition · doi:10.1016/j.patcog.2009.02.014 · Cited by 90
“[13] developed a filtering algorithm on a kd-tree to speed up the generation of new cluster centers.”
MethodAnomaly Detection for Road Traffic: A Visual Analytics Framework
Riveiro, M., Lebram, M., & Elmer, M. (2017) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2017.2675710 · Cited by 90
“This measure is normally called the squared-error distortion and this type of clustering falls into the general category of variance-based clustering [23].”
BackgroundAn efficient cluster-based power saving scheme for wireless sensor networks
Chang, J.-Y., & Ju, P.-H. (2012) · EURASIP Journal on Wireless Communications and Networking · doi:10.1186/1687-1499-2012-172 · Cited by 89
“We modify k-means algorithm to make an ideal distribution for sensor node clusters by using the information of location and residual energy for all sensor nodes [12,13].”
MethodAutomatic Clustering via Outward Statistical Testing on Density Metrics
Wang, G., & Song, Q. (2016) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2016.2535209 · Cited by 89
“It has been widely used in different disciplines and applications, such as machine learning, pattern recognition [2], data compression [3], image segmentation [4], [5], time series analysis [6], [7], information retrieval [8], [9], spatial data analysis [10], [11], [12] and biomedical research [13].”
MethodDistance and density based clustering algorithm using Gaussian kernel
Güngör, E., & Özmen, A. (2016) · Expert Systems with Applications · doi:10.1016/j.eswa.2016.10.022 · Cited by 89
Application of machine learning in rheumatic disease research
Kim, K., & Tagkopoulos, I. (2019) · The Korean Journal of Internal Medicine · doi:10.3904/kjim.2018.349 · Cited by 95
“Gene-expression-driven subgrouping was explored by k-means clustering, in which n objects are partitioned into k clusters, with each object belonging to the cluster with the nearest mean [88].”
MethodLiao, C., Wang, S., Zhang, Y., Song, D., & Zhang, C. (2019) · Journal of Cleaner Production · doi:10.1016/j.jclepro.2019.118026 · Cited by 89
Zhu, Y., Wu, Z., Hartley, W. D., Sietins, J. M., Williams, C. B., & Yu, H. Z. (2020) · Additive manufacturing · doi:10.1016/j.addma.2020.101183 · Cited by 106
DeepSafe: A Data-driven Approach for Checking Adversarial Robustness in Neural Networks
Gopinath, D., Katz, G., Păsăreanu, C. S., & Barrett, C. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1710.00486 · Cited by 55
“Here we focus on a particularly popular clustering algorithm called kMeans [10] (although our approach could be implemented using different clustering algorithms as well).”
MethodAn ADMM Approach to Masked Signal Decomposition Using Subspace Representation
Minaee, S., & Wang, Y. (2019) · IEEE Transactions on Image Processing · doi:10.1109/tip.2019.2894966 · Cited by 88
Qi, H., Xu, T., Wang, G., Cheng, Y., & Chen, C. (2020) · Computers in Industry · doi:10.1016/j.compind.2020.103303 · Cited by 88
Unsupervised Feature Learning by Cross-Level Instance-Group Discrimination
Wang, X., Liu, Z., & Yu, S. X. (2021) · 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/cvpr46437.2021.01240 · Cited by 112
Ren, Q., zhang, H., Zhang, D., Zhao, X. Y., Yan, L., & Rui, J. (2021) · Journal of Petroleum Science and Engineering · doi:10.1016/j.petrol.2021.109681 · Cited by 90
Application of K-Means method to pattern recognition in on-line cable partial discharge monitoring
Peng, X., Zhou, C., Hepburn, D. M., Judd, M. D., & Siew, W. H. (2013) · IEEE Transactions on Dielectrics and Electrical Insulation · doi:10.1109/tdei.2013.6518945 · Cited by 98
“K-Means is an unsupervised clustering algorithm that is applied in many fields, including pattern classification, multimedia analysis and information retrieval [12-14].”
MethodEfficient Algorithm for Localized Support Vector Machine
Cheng, H., Tan, P., & Jin, R. (2009) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2009.116 · Cited by 98
“In this paper, we propose the “MagKmeans” algorithm, which extends regular k-means [20] by considering the class distribution of training examples within each cluster.”
MethodFast exact k nearest neighbors search using an orthogonal search tree
Liaw, Y., Leou, M., & Wu, C.-M. (2010) · Pattern Recognition · doi:10.1016/j.patcog.2010.01.003 · Cited by 88
Yang, S., Yoon, J. W., Kim, K., & Park, Y. (2017) · Cytometry Part A · doi:10.1002/cyto.a.23110 · Cited by 88
A Taxonomy of Queries for E-commerce Search
Sondhi, P., Sharma, M. K., Kolari, P., & Zhai, C. (2018) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/3209978.3210152 · Cited by 104
“We used the k -Means clustering algorithm [2] for generating the clusters.”
MethodA k-means based co-clustering (kCC) algorithm for sparse, high dimensional data
Hussain, S. F., & Haris, M. (2018) · Expert Systems with Applications · doi:10.1016/j.eswa.2018.09.006 · Cited by 87
A new data clustering strategy for enhancing mutual privacy in healthcare IoT systems
Guo, X., Lin, H., Wu, Y., & Peng, M. (2020) · Future Generation Computer Systems · doi:10.1016/j.future.2020.07.023 · Cited by 84
A Walk into Metaheuristics for Engineering Optimization: Principles, Methods and Recent Trends
Xiong, N., Molina, D., Ortiz, M. L., & Herrera, F. (2015) · International Journal of Computational Intelligence Systems · doi:10.1080/18756891.2015.1046324 · Cited by 90
Data Mining Applications in Engineering and Medicine
Adem Karahoca, A. (2012) · InTech eBooks · doi:10.5772/2616 · Cited by 90
ACODF: a novel data clustering approach for data mining in large databases
Tsai, C.-F., Tsai, C.-W., Wu, H., & Yang, T. (2003) · Journal of Systems and Software · doi:10.1016/s0164-1212(03)00216-4 · Cited by 87
ACIQ: Analytical Clipping for Integer Quantization of neural networksPreprint
Banner, R., Nahshan, Y., Hoffer, E., & Soudry, D. (2018) · arXiv (Cornell University) · Cited by 124
K-Means on Commodity GPUs with CUDA
Hong-tao, B., He, L., Dan-tong, O., Li, Z., & He, L. (2009) · doi:10.1109/csie.2009.491 · Cited by 86
Learning of Social Signatures Through Imitation Game Between a Robot and a Human Partner
Boucenna, S., Anzalone, S. M., Tilmont, E., Cohen, D., & Chétouani, M. (2014) · IEEE Transactions on Autonomous Mental Development · doi:10.1109/tamd.2014.2319861 · Cited by 94
Customer Segmentation Using Clustering and Data Mining Techniques
Kashwan, K. R., & Velu, C. M. (2013) · International Journal of Computer Theory and Engineering · doi:10.7763/ijcte.2013.v5.811 · Cited by 86
Du, Z., Yu, S., & Xu, X. (2020) · Information Sciences · doi:10.1016/j.ins.2020.03.100 · Cited by 86
Meister, K., Schmidt, D. A., Bründermann, E., & Havenith, M. (2010) · The Analyst · doi:10.1039/b927012d · Cited by 86
Human Motion Segmentation via Robust Kernel Sparse Subspace Clustering
Xia, G., Sun, H., Feng, L., Zhang, G., & Liu, Y. (2017) · IEEE Transactions on Image Processing · doi:10.1109/tip.2017.2738562 · Cited by 87
“However, many commonly used clustering methods [7]–[9] cannot be directly applied to motion capture data because of the following characteristics.”
MethodKumar, S., Mamun, K. A., & Sharma, A. K. (2017) · Computers in Biology and Medicine · doi:10.1016/j.compbiomed.2017.10.025 · Cited by 86
Pinkham, R., Zeng, S., & Zhang, Z. (2020) · IEEE International Symposium on High-Performance Computer Architecture (HPCA) · doi:10.1109/hpca47549.2020.00024 · Cited by 99
“k-means clustering [31] is another way to partition the search space.”
BackgroundCoordinate Descent Method for k-means
Nie, F., Xue, J., Wu, D., Wang, R., Li, H., & Li, X. (2021) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2021.3085739 · Cited by 125
Recognition of Brand and Models of Cell-Phones From Recorded Speech Signals
Hanilçi, C., Ertaş, F., Ertaş, T., & Eskidere, Ö. (2011) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2011.2178403 · Cited by 90
“For each cell phone, we have used 120 sentences for training and the remaining 120 sentences for testing (a total of 1680 individual tests).”
MethodAn Adaptive K-means Clustering Algorithm for Breast Image Segmentation
Patel, B. C., & Sinha, G. R. (2010) · International Journal of Computer Applications · doi:10.5120/1467-1982 · Cited by 85
“,mk , which may be specified randomly or by some heuristic, the algorithm proceeds by alternating between two steps[14].”
BackgroundA Bayes-Based Region-Growing Algorithm for Medical Image Segmentation
Pan, Z., & Lu, J. (2007) · Computing in Science & Engineering · doi:10.1109/mcse.2007.67 · Cited by 85
A Two-Stage Image Segmentation Method for Blurry Images with Poisson or Multiplicative Gamma Noise
Chan, R. H., Yang, H., & Zeng, T. (2014) · SIAM Journal on Imaging Sciences · doi:10.1137/130920241 · Cited by 90
“…in [57] the authors suggested to take w = log u and change the objective functional (3.3) to∫ Ω fe−w + wdx+ β ∫ Ω |∇w|dx. (3.4) In [58], the authors employed the objective functional (3.2) to restore images corrupted by multiplicative Gamma noise and they justified their selection as follows.”
MethodInfluentialA Bayesian approach to unsupervised multiscale change detection in synthetic aperture radar images
Çelik, T. (2009) · Signal Processing · doi:10.1016/j.sigpro.2009.10.018 · Cited by 85
An Automated Recommender System for Course Selection
Al-Badarenah, A., & Alsakran, J. (2016) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2016.070323 · Cited by 103
“One of the ways to overcome this problem is to filter out high-relevance items if they are too similar to the user profile [47].”
BackgroundKwong, P. W.-H., & Ng, S. S. M. (2019) · Archives of Physical Medicine and Rehabilitation · doi:10.1016/j.apmr.2019.01.027 · Cited by 90
Ali, M. A., Umer, R., Khan, K. A., & Cantwell, W. J. (2019) · Composites Science and Technology · doi:10.1016/j.compscitech.2019.107828 · Cited by 84
Luo, J., Fang, H., Shao, F., Zhong, Y., & Hua, X. (2020) · Defence Technology · doi:10.1016/j.dt.2020.10.006 · Cited by 88
Shrifan, N. H. M. M., Jawad, G. N., Isa, N. A. M., & Akbar, M. F. (2020) · IEEE Access · doi:10.1109/access.2020.3048147 · Cited by 84
“The k-means clustering algorithm is one of the simplest unsupervised machine learning techniques to solve the clustering problem [42].”
MethodPredicting Student Dropout in Self-Paced MOOC Course Using Random Forest Model
Dass, S. S., Gary, K. A., & Cunningham, J. (2021) · Information · doi:10.3390/info12110476 · Cited by 89
“K-means clustering was then performed using Lloyd’s algorithm [60].”
MethodPartitioning hard clustering algorithms based on multiple dissimilarity matrices
de Carvalho, F. D. A. T., Yves Lechevallier, B., & de Melo, F. M. (2011) · Pattern Recognition · doi:10.1016/j.patcog.2011.05.016 · Cited by 84
“Partitioning methods can be divided into hard clustering [13] [14] [15] [16] [17] and fuzzy clustering [18] [19] [20] [21] [22].”
MethodBubble size statistics during reionization from 21-cm tomography
Giri, S. K., Mellema, G., Dixon, K. L., & Iliev, I. T. (2017) · Monthly Notices of the Royal Astronomical Society · doi:10.1093/mnras/stx2539 · Cited by 96
“It has been shown that the algorithm always converges to the solution in a finite time (e.g. Bottou & Bengio 1995; Kanungo et al. 2002), which makes it an apt choice for our case.”
BackgroundMethodSong, Y., Long, Y., Wu, P., & Wang, X. (2018) · International Journal of Geographical Information Systems · doi:10.1080/13658816.2018.1511793 · Cited by 87
“…and fixed value k, computation objective is minimising the sum of squared errors (SSE), variables should be of spherical distribution, all variables have the same variance or importance for clustering, and all k clusters have the same prior probability (Hartigan and Wong 1979, Kanungo et al. 2002).”
BackgroundFair Coresets and Streaming Algorithms for Fair k-means
Schmidt, M., Schwiegelshohn, C., & Sohler, C. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-39479-0_16 · Cited by 125
Trust-based distributed Kalman filtering for target tracking under malicious cyber attacks
Chen, L., Wen, F., & Wang, Z. (2018) · Information Fusion · doi:10.1016/j.inffus.2018.04.002 · Cited by 83
“Meanwhile, K-means clustering is utilized to classify the trusted and untrusted nodes, it is one of the simplest unsupervised learning algorithms to solve the clustering problem [46].”
MethodOptic disc and optic cup segmentation from retinal images using hybrid approach
Thakur, N., & Juneja, M. (2019) · Expert Systems with Applications · doi:10.1016/j.eswa.2019.03.009 · Cited by 83
The Promise of AI in Detection, Diagnosis, and Epidemiology for Combating COVID-19: Beyond the Hype
Abdulkareem, M., & Petersen, S. E. (2021) · Frontiers in Artificial Intelligence · doi:10.3389/frai.2021.652669 · Cited by 96
“…Adversarial Networks (GANs) (Goodfellow et al., 2014) • Gated Recurrent Unit (GRU) recurrent neural network (Cho et al., 2014; Chung et al., 2014) • k-mean clustering (Kanungo et al., 2002) • k-nearest neighbor (Cover and Hart, 1967) • Least Absolute Shrinkage and Selection Operator (LASSO)…”
BackgroundStock Market Analysis Using Time Series Relational Models for Stock Price Prediction
Zhao, C., Hu, P., Liu, X., Lan, X., & Zhang, H. (2023) · Mathematics · doi:10.3390/math11051130 · Cited by 83
Human gesture recognition through a Kinect sensor
Gu, Y., Do, H., Ou, Y., & Sheng, W. (2012) · IEEE International Conference on Robotics and Biomimetics (ROBIO) · doi:10.1109/robio.2012.6491161 · Cited by 83
“It is characterized by the following components: the number of state in the model, the number of distinct observation symbols per state, the state transition probability distribution, the observation symbol probability distribution and the initial state distribution.”
BackgroundA Fuzzy Qualitative Framework for Connecting Robot Qualitative and Quantitative Representations
Liu, H. (2008) · IEEE Transactions on Fuzzy Systems · doi:10.1109/tfuzz.2008.2005004 · Cited by 84
“We combine the well known k-means clustering and aggregation methods to understand local density distribution in a reasonable computational cost [ 34 ].”
MethodAn Efficient Global K-means Clustering Algorithm
Xie, J., Jiang, S., Xie, W., & Gao, X. (2011) · Journal of Computers · doi:10.4304/jcp.6.2.271-279 · Cited by 83
“As the most well known technique for performing nonhierarchical clustering, the K-means clustering [4] iteratively finds the k centroids and assigns each sample to the nearest centroid, where the coordinate of each centroid is the mean of the coordinates of the objects in the cluster.”
MethodBerry, M. W., & Castellanos, M. (2007) · Springer eBooks · doi:10.1007/978-1-84800-046-9 · Cited by 93
Fraga, F. J., Mamani, G. Q., Johns, E. K., Tavares, G., Falk, T. H., & Phillips, N. A. (2018) · Computer Methods and Programs in Biomedicine · doi:10.1016/j.cmpb.2018.06.011 · Cited by 87
“the well-known k-means clustering algorithm [79] with the rule of thumb of one cluster per each subject participating in the study.”
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.