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 801–900 of 1,008
Short-Term Wind Power Forecasting Based on Clustering Pre-Calculated CFD Method
Wang, Y., Liu, Y., Li, L., Infield, D. G., & Han, S. (2018) · Energies · doi:10.3390/en11040854 · Cited by 42
“The K-means method [32,33] is an unsupervised learning algorithm widely used for data classification.”
MethodRouting Protocol LEACH-K Using K-Means Algorithm in Wireless Sensor Network
Gantassi, R., Gouissem, B. B., & Ben‐Othman, J. (2020) · Advances in intelligent systems and computing · doi:10.1007/978-3-030-44038-1_27 · Cited by 42
Task Classification and Scheduling Based on K-Means Clustering for Edge Computing
Ullah, I., & Youn, H. Y. (2020) · Wireless Personal Communications · doi:10.1007/s11277-020-07343-w · Cited by 44
The Millimeter-Wave Radar SLAM Assisted by the RCS Feature of the Target and IMU
Li, Y., Liu, Y., Wang, Y., Lin, Y., & Shen, W. (2020) · Sensors · doi:10.3390/s20185421 · Cited by 47
“Common clustering algorithms include partition-based clustering, such as k-means algorithm [3]; hierarchical clustering, such as BIRCH [4]; clustering based on probability distribution, of which the typical representative is the EM algorithm [5]; and density-based clustering, of which the typical representative is the…”
MethodAnalysis of big data job requirements based on K-means text clustering in China
Debao, D., Ma, Y., & Min, Z. (2021) · PLoS ONE · doi:10.1371/journal.pone.0255419 · Cited by 46
“Kanungo [26] and Wu [27] improved the k-means algorithm, enhanced its superiority and operation speed, and made this method more effective in the field of text mining.”
MethodSamsi, S., Krishnamurthy, A. K., & Gürcan, M. N. (2012) · Journal of Computational Science · doi:10.1016/j.jocs.2012.01.009 · Cited by 43
“The K-means clustering algorithm is a well studied approach to data clustering [37], [38], [39].”
MethodMaxdiff kd-trees for data condensation
Narayan, B. L., Murthy, C. A., & Pal, S. K. (2005) · Pattern Recognition Letters · doi:10.1016/j.patrec.2005.08.015 · Cited by 42
“Kanungo et al. (2002) , where the clustering process was faster if the chosen data set had well-separated clusters.”
BackgroundA FAST k-MEANS IMPLEMENTATION USING CORESETS
Frahling, G., & Sohler, C. (2008) · International Journal of Computational Geometry & Applications · doi:10.1142/s0218195908002787 · Cited by 42
Silhouette-based hand recognition on mobile devices
Sierra, A. D. S., Casanova, J. G., Ávila, C. S., & Vera, V. J. (2009) · IEEE International Carnahan Conference on Security Technology (ICCST) · doi:10.1109/ccst.2009.5335548 · Cited by 42
“This paper will focus on a color segmentation technique, based on k-means algorithm, [8], [16], which allows to isolate hands in the database with an outstanding accuracy.”
MethodClustering analysis of grid nanoindentation data for cementitious materials
Chen, X., Hou, D., Han, Y., Ding, X., & Hua, P. (2021) · Journal of Materials Science · doi:10.1007/s10853-021-05848-8 · Cited by 42
“When the Euclidean distance is adopted to measure the similarity, the clustering method is called K-means clustering, which is a classical partitional clustering algorithm and applied widely in machine learning field [18, 31].”
MethodA general framework of hierarchical clustering and its applications
Cai, R., Zhang, Z., Tung, A. K. H., Dai, C., & Hao, Z. (2014) · Information Sciences · doi:10.1016/j.ins.2014.02.062 · Cited by 44
“[29] gave a swapping based algorithm, achieving ð9þ Þ-approximation.”
MethodNguyen, D. D., Ngo, L. T., Pham, L. T., & Witold Pedrycz, C. (2015) · Fuzzy Sets and Systems · doi:10.1016/j.fss.2015.01.020 · Cited by 41
“Many clustering algorithms have been proposed including Boolean clustering such as k-Means and its variants [2, 3].”
MethodPHD filter based track-before-detect for MIMO radars
Habtemariam, B. K., Tharmarasa, R., & Kirubarajan, T. (2011) · Signal Processing · doi:10.1016/j.sigpro.2011.09.007 · Cited by 44
“Clustering After resampling, clustering [20] has to be done to extract peaks in a PHD filter.”
MethodFrancesquini, E., Castro, M., Penna, P. H., Dupros, F., de Freitas, H. C., Navaux, P. O. A., & Méhaut, J. (2014) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2014.11.002 · Cited by 41
“One of the most widely employed is the Lloyd’s algorithm [14], also known as K233 Means algorithm.”
MethodProbabilistic multiple model neural network based leak detection system: Experimental study
Abdulla, M., & Herzallah, R. (2015) · Journal of Loss Prevention in the Process Industries · doi:10.1016/j.jlp.2015.05.009 · Cited by 41
Sunardi, S., Yudhana, A., & Saifullah, S. (2017) · International Journal of Electrical and Computer Engineering (IJECE) · doi:10.11591/ijece.v7i1.pp200-208 · Cited by 41
“Segmentation has been done to the clustering process [22].”
MethodEnergy efficient clustering and routing in a wireless sensor networks
R., A., & Gowrishankar, G. (2018) · Procedia Computer Science · doi:10.1016/j.procs.2018.07.160 · Cited by 41
Huang, C., Lan, Y., Xu, G., Zhai, X., Wu, J., Lin, F., Zeng, N., Hong, Q., Ng, E. Y. K., Peng, Y., et al. (2020) · IEEE Transactions on Computational Biology and Bioinformatics · doi:10.1109/tcbb.2020.2973971 · Cited by 41
“mixture model [12], K-means clustering [13], support vector machine [14], logical regression [15], etc.”
MethodA Discriminative Deep Model With Feature Fusion and Temporal Attention for Human Action Recognition
Yu, J., Gao, H., Yang, W. H., Jiang, Y., Chin, W., Kubota, N., & Ju, Z. (2020) · IEEE Access · doi:10.1109/access.2020.2977856 · Cited by 41
“INTRODUCTION Human action recognition has gained more interest in the research community and has become a fundamental task in many applications, such as monitoring security [1], gaming entertainment [2], complex object movements [3], [4], smart indoor security systems [5], video streaming [6]–[8], and healthcare [9].”
BackgroundDistributed Fog Computing for Internet of Things (IoT) Based Ambient Data Processing and Analysis
Ahmed, M., Mumtaz, R., Zaidi, S. M. H., Hafeez, M., Zaidi, S. A. R., & Ahmad, M. (2020) · Electronics · doi:10.3390/electronics9111756 · Cited by 43
“In addition to this, the anomaly detection technique using K-means clustering is popular for years and it is applied in order to filter out the outliers or noise in the data [40–42].”
BackgroundInfluentialBerardicurti, O., Conforti, A., Iacono, D., Pantano, I., Caso, F., Emmi, G., Grembiale, R. D., Cantatore, F. P., Atzeni, F., Perosa, F., et al. (2020) · Rheumatology · doi:10.1093/rheumatology/keaa904 · Cited by 41
Rizvi, S. K. J., Aslam, W., Shahzad, M., Saleem, S., & Fraz, M. M. (2021) · Complex & Intelligent Systems · doi:10.1007/s40747-021-00560-1 · Cited by 50
Knowledge-Based Analysis for Detecting Key Signaling Events from Time-Series Phosphoproteomics Data
Yang, P., Zheng, X., Jayaswal, V., Hu, G., Yang, J. Y. H., & Jothi, R. (2015) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1004403 · Cited by 44
“While k-means clustering-based algorithms are computationally efficient and provide an intuitive separation and summarization of the temporal profiles [35,36], their performance can be strongly influenced by the user-selection of the parameter k, which dictates the partitioning of the data into exactly k clusters.”
MethodBoratto, L., & Carta, S. (2014) · Journal of Intelligent Information Systems · doi:10.1007/s10844-014-0346-z · Cited by 41
“The clusterings with k-means were created by using a testbed program, called KMlocal [16].”
MethodA case study of blade inspection based on optical scanning method
Li, W., Zhou, L., & Yan, S. (2014) · International Journal of Production Research · doi:10.1080/00207543.2014.974851 · Cited by 41
Bolla, M. (2011) · Physical Review E · doi:10.1103/physreve.84.016108 · Cited by 52
“[26] Kanungo,T.”
MethodAn hybrid clustering algorithm for optimal clusters in Wireless sensor networks
Kumar, G., Mehra, H., Seth, A. R., Radhakrishnan, P., Hemavathi, N., & Sudha, S. V. (2014) · IEEE Students Conference on Electrical, Electronics and Computer Science · doi:10.1109/sceecs.2014.6804442 · Cited by 41
“presented a simple and efficient implementation of Lloyd's k-means clustering algorithm [1].”
MethodEnergy-Efficient Hybrid K-Means Algorithm for Clustered Wireless Sensor Networks
Mahboub, A., Arioua, M., & En-Naimi, E. M. (2017) · International Journal of Electrical and Computer Engineering (IJECE) · doi:10.11591/ijece.v7i4.pp2054-2060 · Cited by 41
“K-Means is one of the promising and effective clustering algorithms [9].”
BackgroundQuCTS—Single-Flux Quantum Clock Tree Synthesis
Bairamkulov, R., Jabbari, T., & Friedman, E. G. (2021) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.2021.3123141 · Cited by 40
“Conversely, K-means is slower but consistently provides a more balanced tree.”
MethodInfluentialCortical waves mediate the cellular response to electric fields
Yang, Q., Miao, Y., Campanello, L., Hourwitz, M. J., Abubaker‐Sharif, B., Bull, A. L., Devreotes, P. N., Fourkas, J. T., & Losert, W. (2022) · eLife · doi:10.7554/elife.73198 · Cited by 40
Just, D. R., & Goddard, J. M. (2022) · Agribusiness · doi:10.1002/agr.21778 · Cited by 45
Jain, T., & Verma, K. (2024) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2024.109949 · Cited by 40
Sun, X., Cao, X., Zeng, B., Zhai, Q., Başar, T., & Guan, X. (2024) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2024.3451993 · Cited by 45
“By employing the KKT conditions of its lower-level minimization problem, SP s can be converted to a single-level problem as follows: Authorized licensed use limited to the terms of the applicable license agreement with IEEE.”
A 3-D Liver Segmentation Method with Parallel Computing for Selective Internal Radiation Therapy
Goryawala, M., Guillen, M. R., Cabrerizo, M., Barreto, A. B., Gulec, S., Barot, T. C., Suthar, R., Bhatt, R., McGoron, A. J., & Adjouadi, M. (2011) · IEEE Transactions on Information Technology in Biomedicine · doi:10.1109/titb.2011.2171191 · Cited by 43
“From this initialization process, the following automated steps are then clustering technique that tries to partition the given dataset points into various clusters whose means are similar [25], [26].”
MethodBlood microscopic image segmentation using rough sets
Mohapatra, S., Patra, D., & Kumar, K. (2011) · International Conference on Image Information Processing (ICIIP) · doi:10.1109/iciip.2011.6108977 · Cited by 40
An Optimized Version of the K-Means Clustering Algorithm
Poteraş, C. M., Mihăescu, M. C., & Mocanu, M. L. (2014) · Annals of Computer Science and Information Systems · doi:10.15439/2014f258 · Cited by 40
Pendharkar, G., Naik, G. R., & Nguyen, H. T. (2014) · Biomedical Signal Processing and Control · doi:10.1016/j.bspc.2014.02.009 · Cited by 40
An FPGA implementation of real-time K-means clustering for color images
Saegusa, T., & Maruyama, T. (2007) · Journal of Real-Time Image Processing · doi:10.1007/s11554-007-0055-8 · Cited by 40
“Figure 4 shows the outline of the filtering algorithm [ 5 ].”
MethodEnhanced RBF Network for Recognizing Noise-Riding Power Quality Events
Liao, C.-C. (2009) · IEEE Transactions on Instrumentation and Measurement · doi:10.1109/tim.2009.2027769 · Cited by 40
“Furthermore, a hybrid algorithm with KMA [11] and genetic algorithm (GA) [12], which is called genetic k-means algorithm (GKA) [13], is proposed to improve the effectiveness of the clusters from the training patterns by avoiding being trapped in a local minimum solution during the traditional k-means searching”
MethodImage Processing for Soybean Disease Classification and Severity Estimation
Gharge, S., & Singh, P. (2015) · Springer eBooks · doi:10.1007/978-81-322-2553-9_44 · Cited by 40
Ding, Y., Holmes, A., Javadi-Abhari, A., Franklin, D., Martonosi, M., & Chong, F. T. (2018) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1109/micro.2018.00072 · Cited by 55
“In particular, we use the KMeans clustering algorithm [43,44] to pinpoint the centroid of each cluster within a community and use them determine the scale of attraction force for joining them.”
MethodLin, B., Guo, J., Liu, X., Xiang, J., & Zhong, H. (2019) · Journal of Petroleum Science and Engineering · doi:10.1016/j.petrol.2019.106529 · Cited by 40
Time-Series Event Prediction with Evolutionary State Graph
Hu, W., Yang, Y., Cheng, Z., Yang, C., & Ren, X. (2021) · ACM International Conference on Web Search and Data Mining (WSDM) · doi:10.1145/3437963.3441827 · Cited by 40
“We compare the pooling method, GAT [42], GraphSAGE [22], GCN [15] and GGNN [27] for message passing, as well as SAX word [41], Shapelets [30], Kmeans [25] and GMM [7] for state recognition.”
MethodOmni-channel retailing in supply chains: a systematic literature review
Raza, S. A., & Govindaluri, S. M. (2021) · Benchmarking An International Journal · doi:10.1108/bij-10-2020-0547 · Cited by 45
Drip Irrigation Strategy for Tomatoes on the Basis of Fuzzy Borda and K-Means Analysis Method
Zhu, K., Zhao, Y., Ma, Y., Zhang, Q., Kang, Z., & Hu, X. (2022) · Agricultural Water Management · doi:10.1016/j.agwat.2022.107598 · Cited by 40
Kumar, N., & Kumar, H. (2022) · Data & Knowledge Engineering · doi:10.1016/j.datak.2022.102050 · Cited by 40
A comprehensive survey on computational learning methods for analysis of gene expression data
Bhandari, N., Walambe, R. A., Kotecha, K. V., & Khare, S. (2022) · Frontiers in Molecular Biosciences · doi:10.3389/fmolb.2022.907150 · Cited by 47
“In K-means clustering, an arbitrary K number of points from the data are selected as centroids, and all the genes are allocated to the nearest centroid (MacQueen, 1967; Kanungo et al., 2002).”
MethodFast Approximated Multiple Kernel K-Means
Wang, J., Tang, C., Zheng, X., Liu, X., Zhang, W., Zhu, E., & Zhu, X. (2023) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2023.3340743 · Cited by 40
Undersampled $$K$$ K -means approach for handling imbalanced distributed data
Santhosh Kumar, C., Rao, K. N., Govardhan, A., Reddy, K. S., & Mahmood, A. M. (2014) · Progress in Artificial Intelligence · doi:10.1007/s13748-014-0045-6 · Cited by 40
“[17] have presented a simple and efficient implementation of Lloyd’s K -means clustering algorithm, which stores the multi-dimensional data points in a kd-tree.”
MethodA nearest neighbour clustering approach for incipient fault diagnosis of power transformers
Islam, M. M., Lee, G., & Hettiwatte, S. N. (2016) · Electrical Engineering · doi:10.1007/s00202-016-0481-3 · Cited by 40
Detection of Diseases on Cotton Leaves Using K-Mean Clustering Method
Warne, P. P., & Ganorkar, S. R. (2015) · Cited by 40
Evolutionary radial basis function network for gestational diabetes data analytics
Moreira, M. W. L., Rodrigues, J. J. P. C., Kumar, N., Al-Muhtadi, J. F., & Korotaev, V. (2017) · Journal of Computational Science · doi:10.1016/j.jocs.2017.07.015 · Cited by 40
Microarray gene expression data association rules mining based on BSC-tree and FIS-tree
Jiang, X., & Gruenwald, L. (2004) · Data & Knowledge Engineering · doi:10.1016/j.datak.2004.06.011 · Cited by 40
Virok, D. P., Loboda, A. P., Kari, L., Nebozhyn, M., Chang, C., Nichols, C., Endrész, V., Gönczöl, É., Berencsi, K., Showe, M. K., et al. (2003) · The Journal of Infectious Diseases · doi:10.1086/379047 · Cited by 40
Cleaning Label Noise with Clusters for Minimally Supervised Anomaly DetectionPreprint
Zaheer, M. Z., Lee, J. H., Astrid, M., Mahmood, A., & Lee, S. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2104.14770 · Cited by 40
“Clustering: Given that anomaly detection is a binary problem, clustering algorithms such as k-means [2] can be employed to distribute all segments into two clusters.”
MethodConsumer Demand for Circular Products: Identifying Customer Segments in the Circular Economy
Boyer, R. H. W., Hunka, A. D., & Whalen, K. A. (2021) · Sustainability · doi:10.3390/su132212348 · Cited by 39
“The most common clustering method is k-means clustering, which uses distance between data points and a mean point (centroid) of each cluster as a datapoint defining a given cluster [49].”
MethodK-means implementation on FPGA for high-dimensional data using triangle inequality
Lin, Z., Lo, C., & Chow, P. (2012) · International Conference on Field Programmable Logic and Applications (FPL) · doi:10.1109/fpl.2012.6339141 · Cited by 39
“Unfortunately, the size of the data set and the dimensionality are increasing as the sensor technology and computational capability of computers develop.”
BackgroundLiu, R., Dey, D. K., Boss, D., Marquet, P. P., & Javidi, B. (2011) · Journal of the Optical Society of America A · doi:10.1364/josaa.28.001204 · Cited by 39
Fast Detection of Dense Subgraphs with Iterative Shrinking and Expansion
Liu, H., Latecki, L. J., & Yan, S. (2013) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2013.16 · Cited by 39
“We compare our method with k-means [35] and spectral clustering (SC) [36], two representative clustering methods, based on vectorial representation and affinity data, respectively.”
MethodAn Accurate GPU Performance Model for Effective Control Flow Divergence Optimization
Cui, Z., Liang, Y. E., Rupnow, K., & Chen, D. (2012) · IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2012.18 · Cited by 39
Review of image compression techniques
Singh, A., & Kirar, K. G. (2017) · International Conference on Recent Innovations in Signal Processing and Embedded Systems (RISE) · doi:10.1109/rise.2017.8378148 · Cited by 39
Vegetation Fires in the Asian Region: Satellite Observational Needs and Priorities
Vadrevu, K. P., & Justice, C. O. (2011) · Cited by 39
Zhang, W., Zhang, X., Zhao, J., Qiang, Y., Tian, Q. C., & Tang, X. (2017) · PLoS ONE · doi:10.1371/journal.pone.0184290 · Cited by 41
Wen, F., & Wang, Z. (2018) · Digital Signal Processing · doi:10.1016/j.dsp.2018.03.002 · Cited by 39
A feasible density peaks clustering algorithm with a merging strategy
Xu, X. W., Ding, S., Xu, H., Liao, H., & Xue, Y. (2018) · Soft Computing · doi:10.1007/s00500-018-3183-0 · Cited by 39
“K-means (Kanungo et al. 2002) is a popular partition-based clustering algorithm, but it is not only dependent on the initial cluster centers and initial partitions but also is unable to find clusters with arbitrary shape.”
Dissemination Practices of Construction Sites’ Technology Vendors in Technology Exhibitions
Sepasgozar, S. M. E., Davis, S., & Loosemore, M. (2018) · Journal of Management in Engineering · doi:10.1061/(asce)me.1943-5479.0000650 · Cited by 40
Bo, P., & Bartoň, M. (2019) · Computer Aided Geometric Design · doi:10.1016/j.cagd.2019.04.012 · Cited by 39
Li, Y., Zhu, Z., & Guo, X. (2019) · Sustainability · doi:10.3390/su11082256 · Cited by 39
Optimization of Multi-UAV-Aided Wireless Networking Over a Ray-Tracing Channel Model
Liu, A., & Lau, V. K. N. (2019) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2019.2926088 · Cited by 39
“Algorithm 2 Sparse Parallel Block SCA Initialization: Choose a feasible initial solution { x0 (n), m0 (n), η0, ρ0 } with ρ0n = 1 N , ∀n.”
MethodInfluentialAuto-weighted multi-view constrained spectral clustering
Chen, C., Qian, H., Chen, W., Zheng, Z., & Zhu, H. (2019) · Neurocomputing · doi:10.1016/j.neucom.2019.06.098 · Cited by 39
Feature Line Generation and Regularization From Point Clouds
Chen, X., & Yu, K. (2019) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2019.2929138 · Cited by 39
“4) The k-means clustering algorithm [27] is employed to cluster the unit normal vectors, and the fold points are then determined according to the optimal number of clusters.”
MethodA systematic literature review of closed-loop supply chains
Raza, S. A. (2020) · Benchmarking An International Journal · doi:10.1108/bij-10-2019-0464 · Cited by 42
An efficient Split-Merge re-start for the K-means algorithm
Capó, M., Pérez, A., & Lozano, J. A. (2020) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2020.3002926 · Cited by 39
Improved Transferability of Data‐Driven Damage Models Through Sample Selection Bias Correction
Wagenaar, D., Hermawan, T., den Homberg, M. J. C. V., Aerts, J. C. J. H., Kreibich, H., de Moel, H., & Bouwer, L. M. (2020) · Risk Analysis · doi:10.1111/risa.13575 · Cited by 43
Eye Blink Artifact Detection With Novel Optimized Multi-Dimensional Electroencephalogram Features
Wang, J., Cao, J., Hu, D., Jiang, T., & Gao, F. (2021) · IEEE Transactions on Neural Systems and Rehabilitation Engineering · doi:10.1109/tnsre.2021.3099232 · Cited by 39
Nguyen, M. D., Le, L. B., & Girard, A. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3138374 · Cited by 39
“These points are the centers of the corresponding network partitions computed using the k-means clustering algorithm [38] for given locations of the K GUs.”
MethodRaza, S. A., Govindaluri, S. M., & Bhutta, M. K. S. (2022) · Benchmarking An International Journal · doi:10.1108/bij-12-2021-0755 · Cited by 43
Fan, Y., Zhao, Z., Wang, X., Ai, H., Yang, C., Luo, Y., & Jiang, X. (2022) · La radiologia medica · doi:10.1007/s11547-022-01569-3 · Cited by 39
Liu, J. J., Yue, C. X., Hu, Y. D., & Wang, X. Z. (2010) · Computers & Chemical Engineering · doi:10.1016/j.compchemeng.2010.06.020 · Cited by 39
An FPGA Implementation of K-Means Clustering for Color Images Based on Kd-Tree
Saegusa, T., & Maruyama, T. (2006) · International Conference on Field Programmable Logic and Applications (FPL) · doi:10.1109/fpl.2006.311268 · Cited by 39
“We have shown that real-time k-means clustering can be achieved for large number of clusters (up to 256) and large size color images by employing the simplified version of the filtering algorithm[4] and the FEKM algorithm [5] in [6].”
MethodCombining interest points and edges for content-based image retrieval
Wang, J., Zha, H., & Cipolla, R. (2005) · Proceedings - International Conference on Image Processing · doi:10.1109/icip.2005.1530627 · Cited by 39
“Using the k-means algorithm [2], a visual vocabulary is constructed to realize the above ideas.”
MethodReplica inference approach to unsupervised multiscale image segmentation
Hu, D., Ronhovde, P., & Nussinov, Z. (2012) · Physical Review E · doi:10.1103/physreve.85.016101 · Cited by 43
Balancing effort and benefit of K-means clustering algorithms in Big Data realms
Pérez-Ortega, J., Almanza-Ortega, N. N., & Romero, D. (2018) · PLoS ONE · doi:10.1371/journal.pone.0201874 · Cited by 48
Text Backdoor Detection Using an Interpretable RNN Abstract Model
Fan, M., Si, Z., Xie, X., Liu, Y., & Liu, T. (2021) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2021.3103064 · Cited by 38
“Here, we rely on the widely-used clustering algorithm k-means [26].”
MethodLi, A., Wu, Z., Lu, H., Chen, D., & Sun, G. (2018) · IEEE Access · doi:10.1109/access.2018.2862159 · Cited by 38
“Without any label information, unsupervised image classification can be seen as a clustering problem, which is realized by some distance metric or knowledge transferring method in feature space [8]–[10].”
BackgroundChaudhary, P., Singh, A. K., & Gupta, B. B. (2025) · Computers & Electrical Engineering · doi:10.1016/j.compeleceng.2025.110226 · Cited by 46
An Effective Method of Pruning Support Vector Machine Classifiers
Liang, X. (2009) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2009.2033677 · Cited by 39
Chawla, S. (2016) · Applied Soft Computing · doi:10.1016/j.asoc.2016.04.042 · Cited by 38
An Insurance Recommendation System Using Bayesian Networks
Qazi, M., Fung, G., Meissner, K. J., & Fontes, E. (2017) · ACM Conference on Recommender Systems (RecSys) · doi:10.1145/3109859.3109907 · Cited by 38
“Some of the continuous features were manually discretized based on business logic because that made that most sense, but most were binned using the K-Means algorithm [10].”
MethodMechanobiological model of arterial growth and remodeling
Keshavarzian, M., Meyer, C. A., & Hayenga, H. N. (2017) · Biomechanics and Modeling in Mechanobiology · doi:10.1007/s10237-017-0946-y · Cited by 38
Ahn, J., Park, J. Y., Park, D., Paek, J., & Ko, J. (2018) · PLoS ONE · doi:10.1371/journal.pone.0196251 · Cited by 38
Segmentation of Crop Disease Images with an Improved K-means Clustering Algorithm
Wang, Z., Wang, K., Pan, S., & Han, Y. (2018) · Applied Engineering in Agriculture · doi:10.13031/aea.12205 · Cited by 38
Application of Parzen Window estimation for incipient fault diagnosis in power transformers
Islam, M. M., Lee, G., & Hettiwatte, S. N. (2018) · High Voltage · doi:10.1049/hve.2018.5061 · Cited by 38
Privacy Regulation Aware Process Mapping in Geo-Distributed Cloud Data Centers
Zhou, A. C., Xiao, Y., Gong, Y., He, B., Zhai, J., & Mao, R. (2019) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2019.2896894 · Cited by 37
“K-means clustering [11] is a popular unsu-”
MethodInfluentialDetermination of Customer Satisfaction using Improved K-means algorithm
Zare, H., & Emadi, S. (2020) · Soft Computing · doi:10.1007/s00500-020-04988-4 · Cited by 38
A systematic literature review of RFID in supply chain management
Raza, S. A. (2021) · Journal of Enterprise Information Management · doi:10.1108/jeim-08-2020-0322 · Cited by 43
Multiview Clustering by Consensus Spectral Rotation Fusion
Chen, J., Mao, H., Peng, D., Zhang, C., & Peng, X. (2023) · IEEE Transactions on Image Processing · doi:10.1109/tip.2023.3310339 · Cited by 38
Deep Learning in Single-cell Analysis
Molho, D., Ding, J., Tang, W., Li, Z., Wen, H., Wang, Y., Venegas, J., Jin, W., Liu, R., Su, R., et al. (2024) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3641284 · Cited by 49
“K-means Classical Iterative observation assignment to the cluster with the nearest mean Python K-means [260]”
MethodAung, H. H., & Tan, K. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13818-8_16 · Cited by 38
Nondegeneracy and Weak Global Convergence of the Lloyd Algorithm in $\mathbb{R}^d$
Emelianenko, M., Ju, L., & Rand, A. (2008) · SIAM Journal on Numerical Analysis · doi:10.1137/070691334 · Cited by 38
“The Lloyd algorithm also coincides with the simplest version of the k-means algorithm in clustering and quantization fields [10, 12, 18, 15].”
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.