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 101–200 of 1,008
A move/step model for methods sections: Demonstrating Rigour and Credibility
Cotos, E., Huffman, S., & Link, S. (2017) · English for Specific Purposes · doi:10.1016/j.esp.2017.01.001 · Cited by 162
“Finally, a k-means clustering algorithm (Kanungo, 2002) was applied to differentiate clusters of disciplines based on how authors used the steps.”
MethodIslam, M. K., Ali, M. S., Miah, M. S., Rahman, M. M., Alam, M. S., & Hossain, M. A. (2021) · Machine Learning with Applications · doi:10.1016/j.mlwa.2021.100044 · Cited by 185
Machine Learning-Based Anomaly Detection for Load Forecasting Under Cyberattacks
Cui, M., Wang, J., & Yue, M. (2019) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2018.2890809 · Cited by 187
“Compared with mixture models and hierarchical clustering, the k-means clustering method is easy to implement [19].”
MethodSelvakumar, J., Lakshmi, A. R., & Arivoli, T. (2012) · IEEE-International Conference On Advances In Engineering, Science And Management · Cited by 197
Niknam, T., Taherian Fard, E., Pourjafarian, N., & Rousta, A. (2011) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2010.10.001 · Cited by 195
Zhang, X., Han, L., Han, L., & Zhu, L. (2020) · Remote Sensing · doi:10.3390/rs12030417 · Cited by 186
“Two most frequently used unsupervised classification algorithms are ISODATA [62] and k-means [63].”
MethodHamerly, G. (2010) · Proceedings of the 2010 SIAM International Conference on Data Mining · doi:10.1137/1.9781611972801.12 · Cited by 190
“Several tree-based accelerations have also been proposed, such as Moore’s anchors hierarchy [15], which is effective in high dimensions, and k-d tree algorithms [17, 12], which are very fast on lowdimensional data.”
BackgroundMethodInfluentialThe effectiveness of lloyd-type methods for the k-means problem
Ostrovsky, R., Rabani, Y., Schulman, L. J., & Swamy, C. (2012) · Journal of the ACM · doi:10.1145/2395116.2395117 · Cited by 179
“Researchers concerned with the runtime of Lloyd’s method bemoan the need forn nearest-neighbor computations in each descent step [28] ! Interestingly, the last reference provides a dat a structure that provably speeds up the nearest-neighbor cal culations of Lloyd descent steps, under the condition that the optimal cl…”
BackgroundMethodInfluentialWen, Z., Pei, H., Liu, H., & Yue, Z. (2016) · Reliability Engineering & System Safety · doi:10.1016/j.ress.2016.05.002 · Cited by 187
“Besides, the K-means clustering [14,15], a method for classifying data points into groups, is also introduced as”
MethodEarly warning system for shallow landslides using rainfall threshold and slope stability analysis
Naidu, S., Sajinkumar, K. S., Oommen, T., Anuja, V. J., Samuel, R. A., & Muraleedharan, C. (2018) · Geoscience Frontiers · doi:10.1016/j.gsf.2017.10.008 · Cited by 184
“K-means clustering is the most popular and efficient clustering method which uses prototypes (centroids) to represent clusters by optimizing the squared error function (Kanungo et al., 2002).”
MethodKlatt, C. G., Wood, J. M., Rusch, D. B., Bateson, M. M., Hamamura, N., Heidelberg, J. F., Grossman, A. R., Bhaya, D., Cohan, F. M., Kühl, M., et al. (2011) · The ISME Journal · doi:10.1038/ismej.2011.73 · Cited by 190
Improving the performance of k-means for color quantization
Celebi, M. E. (2011) · Image and Vision Computing · doi:10.1016/j.imavis.2010.10.002 · Cited by 179
“Furthermore, numerous acceleration techniques are available in the literature [53, 54, 55, 56, 57, 58].”
BackgroundMethodAttribute Inference Attacks in Online Social Networks
Gong, N. Z., & Liu, B. (2018) · ACM Transactions on Privacy and Security · doi:10.1145/3154793 · Cited by 128
“, k-means [33]) to group the votes that our attack produces for all candidate attribute values into two clusters.”
BackgroundA Systematic Literature Review of Intelligent Data Analysis Methods for Smart Sport Training
Rajšp, A., & Fister, I. (2020) · Applied Sciences · doi:10.3390/app10093013 · Cited by 166
“, Decision Trees (DT) [23], adaptive boosting [24], Random Forests (RF) [25], Gradient Boosting (GB) [26], K-Nearest Neighbors [27] (k-NN), Support Vector Machine (SVM) [28], Artificial Neural Networks [29] (ANN), hierarchical clustering [30], and k-means clustering [31].”
BackgroundUnsupervised Visual Hashing with Semantic Assistant for Content-Based Image Retrieval
Zhu, L., Shen, J., Xie, L., & Cheng, Z. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2016.2562624 · Cited by 186
“We first leverage k-means [45] to partition texts into L groups.”
MethodROSE: Robustness Strategy for Scale-Free Wireless Sensor Networks
Qiu, T., Zhao, A., Xia, F., Si, W., & Wu, D. O. (2017) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2017.2713530 · Cited by 185
An SVM-based approach for stock market trend prediction
Lin, Y., Guo, H., & Hu, J. (2013) · The 2013 International Joint Conference on Neural Networks (IJCNN) · doi:10.1109/ijcnn.2013.6706743 · Cited by 160
“In order to obtain partitions along the separation boundary, a separation boundary detection method is first applied to detect the separation boundary; then, a k-means clustering [25] is used to partition the selected samples into subsets for estimating local data center, local width and the number of basis function M…”
MethodA Survey of Partitional and Hierarchical Clustering Algorithms
Reddy, C. K. A., & Vinzamuri, B. (2018) · Chapman & Hall/CRC eBooks · doi:10.1201/9781315373515-4 · Cited by 204
“An improvement to the original Lloyd’s K-Means clustering using a kd-tree data structure to store the data points was proposed in [24].”
MethodÜnal, E., & Shao, J. (2019) · Journal of Cleaner Production · doi:10.1016/j.jclepro.2018.11.291 · Cited by 162
Jalal, A., & Mahmood, M. (2019) · Education and Information Technologies · doi:10.1007/s10639-019-09892-5 · Cited by 172
A Unified Form of Fuzzy C-Means and K-Means algorithms and its Partitional Implementation
Borlea, I.-D., Precup, R.-E., Borlea, A.-B., & Iercan, D. (2021) · Knowledge-Based Systems · doi:10.1016/j.knosys.2020.106731 · Cited by 172
GAPS: A clustering method using a new point symmetry-based distance measure
Bandyopadhyay, S., & Saha, S. (2007) · Pattern Recognition · doi:10.1016/j.patcog.2007.03.026 · Cited by 176
“[9] presented an improved K-means algorithm which can speed up the time performance while preserving the same clustering result as in the K-means algorithm.”
MethodHybrid prediction model with missing value imputation for medical data
Purwar, A., & Singh, S. K. (2015) · Expert Systems with Applications · doi:10.1016/j.eswa.2015.02.050 · Cited by 168
A genetic algorithm with gene rearrangement for K-means clustering
Chang, D.-X., Zhang, X.-D., & Zheng, C.-W. (2009) · Pattern Recognition · doi:10.1016/j.patcog.2008.11.006 · Cited by 170
Hybrid Learning Algorithm of Radial Basis Function Networks for Reliability Analysis
Zhang, D., Zhang, N., Ye, N., Fang, J., & Han, X. (2021) · IEEE Transactions on Reliability · doi:10.1109/tr.2020.3001232 · Cited by 169
Zahmatkesh, H., & Al-Turjman, F. (2020) · Sustainable Cities and Society · doi:10.1016/j.scs.2020.102139 · Cited by 169
An Effective and Efficient Algorithm for K-Means Clustering With New Formulation
Nie, F., Li, Z., Wang, R., & Li, X. (2022) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2022.3155450 · Cited by 190
“In addition, some algorithms use binary coding [35] or data structure [36], [37] to accelerate the k-means clustering algorithms.”
Alkhayrat, M., Aljnidi, M., & Aljoumaa, K. (2020) · Journal Of Big Data · doi:10.1186/s40537-020-0286-0 · Cited by 195
“There are two famous feature-based techniques among the current algorithms, K-means [12] and Gaussian Mixture Models (GMM) [13].”
MethodDynamics based 3D skeletal hand tracking
Melax, S., Keselman, L., & Orsten, S. (2013) · Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games · doi:10.1145/2448196.2448232 · Cited by 172
“Given that the user’s hands are the foremost objects in the scene, we use a k-means clustering algorithm [17], to cluster the point cloud into two hand clusters; we assume the left cluster to be the left hand, and the right cluster to be the right hand.”
MethodBleeding Frame and Region Detection in the Wireless Capsule Endoscopy Video
Yuan, Y., Li, B., & Meng, M. Q.-H. (2016) · IEEE Journal of Biomedical and Health Informatics · doi:10.1109/jbhi.2015.2399502 · Cited by 167
Han, J., Kamber, M., & Pei, J. (2012) · Elsevier eBooks · doi:10.1016/b978-0-12-381479-1.00010-1 · Cited by 194
Hybrid CNN and Dictionary-Based Models for Scene Recognition and Domain Adaptation
Xie, G.-S., Zhang, X.-Y., Yan, S., & Liu, C.-L. (2017) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2015.2511543 · Cited by 168
“do K -means clustering [56] to get the class-specific (CS) part dictionary and the class-mixture (CM) part dictionary, denoted by Dcs ∈ Rd×K and Dcm ∈ Rd×K , respectively.”
BackgroundChoosing DBSCAN Parameters Automatically using Differential Evolution
Karami, A., & Johansson, R. (2014) · International Journal of Computer Applications · doi:10.5120/15890-5059 · Cited by 164
Traffic Management for Emergency Vehicle Priority Based on Visual Sensing
Nellore, K., & Hancke, G. (2016) · Sensors · doi:10.3390/s16111892 · Cited by 158
Li, Z., Zhang, J., Tan, T., Teng, X., Sun, X., Zhao, H., Liu, L., Xiao, Y., Lee, B., Li, Y., et al. (2020) · IEEE Journal of Biomedical and Health Informatics · doi:10.1109/jbhi.2020.3039741 · Cited by 184
“In sub-datasets fusion: the dataset was divided into three sub-datasets by k-means algorithm [57].”
MethodAUTOMATIC IDENTIFICATION OF EPILEPTIC AND BACKGROUND EEG SIGNALS USING FREQUENCY DOMAIN PARAMETERS
FAUST, O., ACHARYA, U. R., MIN, L. C., & SPUTH, B. H. C. (2010) · International Journal of Neural Systems · doi:10.1142/s0129065710002334 · Cited by 165
“26 estimates of the parameters of the training data using as K-means.”
MethodRecent advances in quantum machine learning
Zhang, Y., & Ni, Q. (2020) · Quantum Engineering · doi:10.1002/que2.34 · Cited by 149
“(34) Compare the control qubit state 1 √ 2n ∑2n−1 k=0 e 2 i k2 n 2n |k⟩ with the form of Fourier-transformed state |j⟩ = 1 √ N N−1 ∑”
An effective collaborative movie recommender system with cuckoo search
Katarya, R., & Verma, O. P. (2016) · Egyptian Informatics Journal · doi:10.1016/j.eij.2016.10.002 · Cited by 179
Vita: A Crowdsensing-Oriented Mobile Cyber-Physical System
Hu, X., Chu, T. H. S., Chan, H. C. B., & Leung, V. C. M. (2013) · IEEE Transactions on Emerging Topics in Computing · doi:10.1109/tetc.2013.2273359 · Cited by 162
“Besides, considering the computationally extensive nature of GA-based algorithm, we also adopt a K-means-clusteringbased algorithm in social vector.”
MethodFuzzy clustering with the entropy of attribute weights
Zhou, J., Chen, L., Chen, C. L. P., Zhang, Y., & Li, H.-X. (2016) · Neurocomputing · doi:10.1016/j.neucom.2015.09.127 · Cited by 160
Enabling AI in Future Wireless Networks: A Data Life Cycle Perspective
Nguyen, D. C., Cheng, P., Ding, M., Lopez-Perez, D., Pathirana, P. N., Li, J., Seneviratne, A., Li, Y., & Poor, H. V. (2021) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2020.3024783 · Cited by 160
“use cases, such as estimation for parameters in Hidden Markov Models, finding the missing data in the data sample space, or support for clustering tasks [50].”
MethodBearing Fault Diagnosis Based on Statistical Locally Linear Embedding
Wang, X., Zheng, Y. G., Zhao, Z., & Wang, J. (2015) · Sensors · doi:10.3390/s150716225 · Cited by 164
“The K -means clustering algorithm [25] was selected due to its efficiency and easy implementation.”
MethodCommunity Detection and Visualization of Networks with the Map Equation Framework
Bohlin, L., Edler, D., Lancichinetti, A., & Rosvall, M. (2014) · Springer eBooks · doi:10.1007/978-3-319-10377-8_1 · Cited by 183
“We now live in the era of Big Data and fortunately we have several tools for classifying data from many different sources, including point clouds, images, text documents (1–3), and networks.”
MethodIn situ detection of welding defects: a review
Madhvacharyula, A. S., Pavan, A. V. S., Gorthi, S., Chitral, S., Venkaiah, N., & Kiran, D. V. (2022) · Welding in the World · doi:10.1007/s40194-021-01229-6 · Cited by 172
Applications of Artificial Intelligence in Ophthalmology: General Overview
Lü, W., Tong, Y., Yu, Y., Xing, Y., Chen, C., & Shen, Y. (2018) · Journal of Ophthalmology · doi:10.1155/2018/5278196 · Cited by 173
“Existing CML algorithms used in AI diagnosis include decision trees [17], random forests (RF) [18], support vector machines (SVM) [19], Bayesian classifiers [20], k-nearest neighbors [21], k-means [22], linear discriminant analysis [23], and neural networks (NN) [24] (Table 1).”
MethodGait Recognition Under Various Viewing Angles Based on Correlated Motion Regression
Kusakunniran, W., Wu, Q., Zhang, J., & Li, H. (2012) · IEEE Transactions on Circuits and Systems for Video Technology · doi:10.1109/tcsvt.2012.2186744 · Cited by 156
“, k-mean clustering [33]) on gait features (i.”
BackgroundMethodMoghaddas‐Tafreshi, S. M., Jafari, M., Mohseni, S., & Kelly, S. (2019) · International Journal of Electrical Power & Energy Systems · doi:10.1016/j.ijepes.2019.04.040 · Cited by 160
Internal curing with lightweight aggregate produced from biomass-derived waste
Lura, P., Wyrzykowski, M., Tang, C., & Lehmann, E. H. (2014) · Cement and Concrete Research · doi:10.1016/j.cemconres.2014.01.025 · Cited by 156
Khanzadeh, M., Rao, P., Jafari-Marandi, R., Smith, B. K., Tschopp, M. A., & Bian, L. (2018) · Journal of Manufacturing Science and Engineering · doi:10.1115/1.4038598 · Cited by 146
“main clusters, which causes an increase in the magnitude of deviation ( Dj ), which in turn is directly related to overall geometric deviation (n) [44].”
BackgroundDing, Y., Zhang, Z., Yang, A., Cai, Y., Xiao, X., Hong, D., & Yuan, J. (2025) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2025.3604954 · Cited by 156
A fast MPEG-7 dominant color extraction with new similarity measure for image retrieval
Yang, N.-C., Chang, W.-H., Kuo, C., & Li, T.-H. (2007) · Journal of Visual Communication and Image Representation · doi:10.1016/j.jvcir.2007.05.003 · Cited by 172
Adaptive fuzzy moving K-means clustering algorithm for image segmentation
Isa, N. A. M., Salamah, S. A., & Ngah, U. K. (2009) · IEEE Transactions on Consumer Electronics · doi:10.1109/tce.2009.5373781 · Cited by 155
“One of the most important and widely used algorithm is the k-means clustering [25].”
MethodExtensions of vector quantization for incremental clustering
Lughofer, E. D. (2007) · Pattern Recognition · doi:10.1016/j.patcog.2007.07.019 · Cited by 160
Confocal Raman Imaging Study Showing Macrophage Mediated Biodegradation of Graphene In Vivo
Girish, C. M., Sasidharan, A., Gowd, G. S., Nair, S. V., & Koyakutty, M. (2013) · Advanced Healthcare Materials · doi:10.1002/adhm.201200489 · Cited by 154
Data-driven cost estimation for additive manufacturing in cybermanufacturing
Chan, S. L., Lu, Y., & Wang, Y. (2017) · Journal of Manufacturing Systems · doi:10.1016/j.jmsy.2017.12.001 · Cited by 161
Multisensor Fusion and Integration: Theories, Applications, and its Perspectives
Luo, R. C., Chang, C. C., & Lai, C.-C. (2011) · IEEE Sensors Journal · doi:10.1109/jsen.2011.2166383 · Cited by 152
“Frequently used methods include support vector machines (SVM), cluster analysis, -means clustering [ 19 ], [20], Kohonen feature map, and learning vector quantization (LVQ).”
MethodLiu, M., Zhang, D., Adeli, E., & Shen, D. G. (2015) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2015.2496233 · Cited by 159
A Fast Adaptive k-means with No Bounds
Xia, S., Peng, D., Meng, D., Zhang, C., Wang, G., Giem, E., Wei, W., & Chen, Z. (2020) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2020.3008694 · Cited by 149
Optimized big data K-means clustering using MapReduce
Cui, X., Zhu, P., Yang, X., Li, K., & Ji, C. (2014) · The Journal of Supercomputing · doi:10.1007/s11227-014-1225-7 · Cited by 156
“[16] made use of kd-tree to get a filtering algorithm over K-means.”
MethodOjaghi, M., & Mohammadi, V. (2017) · IEEE Transactions on Power Delivery · doi:10.1109/tpwrd.2017.2749321 · Cited by 148
“points in the same space, called centers, so as to minimize the distance from each data point to its nearest center [24].”
BackgroundLow-rank representation with adaptive graph regularization
Wen, J., Fang, X., Xu, Y. D., Tian, C., & Fei, L. (2018) · Neural Networks · doi:10.1016/j.neunet.2018.08.007 · Cited by 148
Over-the-Air Computation for 6G: Foundations, Technologies, and Applications
Wang, Z., Zhao, Y., Zhou, Y., Shi, Y., Jiang, C., & Letaief, K. B. (2024) · IEEE Internet of Things Journal · doi:10.1109/jiot.2024.3405448 · Cited by 165
“To promote the aggregation efficiency, the authors in [94] propose a k -means algorithm [111] based grouping method to minimize the sum distance from the grouped sensors to the UAV, along with the shortest path scheme based on ant colony optimization [112] for UAV trajectory manipulation, which…”
MethodPreserving Privacy with Probabilistic Indistinguishability in Weighted Social Networks
Liu, Q., Wang, G., Li, F., Yang, S., & Wu, J. (2016) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2016.2615020 · Cited by 147
“The main idea is based on the classical heuristic clustering algorithm, K-means [10].”
MethodExploiting Clustering Manifold Structure for Hyperspectral Imagery Super-Resolution
Zhang, L., Wei, W., Bai, C., Gao, Y., & Zhang, Y. (2018) · IEEE Transactions on Image Processing · doi:10.1109/tip.2018.2862629 · Cited by 147
“To this end, we adopt the conventional K-means algorithm [35] to divide all FBPs extracted from the input Y in to K clusters.”
A genetic algorithm that exchanges neighboring centers for k-means clustering
Laszlo, M. J., & Mukherjee, S. (2007) · Pattern Recognition Letters · doi:10.1016/j.patrec.2007.08.006 · Cited by 146
“These data sets were generated using the method described in (Kanungo et al., 2002, Laszlo and Mukherjee, 2006): Fifty cluster centers were randomly selected from the hypercube [ 1,1]d.”
MethodFair Clustering Through FairletsPreprint
Chierichetti, F., Kumar, R., Lattanzi, S., & Vassilvitskii, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.05733 · Cited by 441
“To solve the k -median problem we use the single swap algo-rithm due to Arya et al. (2004), which also gets a 5-approximation in the worst case, but performs much better in practice (Kanungo et al. , 2002).”
MethodTea leaf disease detection using multi-objective image segmentation
Mukhopadhyay, S., Paul, M., Pal, R., & De, D. (2020) · Multimedia Tools and Applications · doi:10.1007/s11042-020-09567-1 · Cited by 155
“The value of K should be predefined [21].”
BackgroundData Clustering: Algorithms and Its Applications
Oyelade, J. O., Isewon, I., Oladipupo, O. O., Emebo, O., Omogbadegun, Z. O., Aromolaran, O., Uwoghiren, E., Olaniyan, D., & Olawole, O. O. (2019) · International Conference on Computational Science and Its Applications · doi:10.1109/iccsa.2019.000-1 · Cited by 159
“Lloyd's k-means clustering method was implemented by [51], this is a filtering algorithm that require kd-tree as its main data structure and also minimizes the mean square distance from each point to the nearest distance.”
MethodSpatial pattern of arable land-use intensity in China
Ye, S., Song, C., Shen, S., Gao, P., Cheng, C., Feng, C., Wan, C., & Zhu, D. (2020) · Land Use Policy · doi:10.1016/j.landusepol.2020.104845 · Cited by 143
Wang, P. E., Yang, Y., & Moghaddam, N. S. (2021) · Journal of Manufacturing Processes · doi:10.1016/j.jmapro.2021.11.037 · Cited by 150
A new grouping genetic algorithm for clustering problems
Agustín-Blas, L. E., Salcedo‐Sanz, S., Jiménez-Fernández, S., Carro‐Calvo, L., Ser, J. D., & Portilla-Figueras, A. (2012) · Expert Systems with Applications · doi:10.1016/j.eswa.2012.02.149 · Cited by 152
“K-means (Chang et al., 2009; Kanungo et al., 2002; Likas, Vlassis, & Verbeek, 2003), and other approaches such as model-based clustering (Mclachlan & Basford, 1988).”
A Feature-Reduction Multi-View k-Means Clustering Algorithm
Yang, M., & Sinaga, K. P. (2019) · IEEE Access · doi:10.1109/access.2019.2934179 · Cited by 148
Energy and Exergy Analysis of a Cruise Ship
Baldi, F., Ahlgren, F., Nguyen, T.-V., Thern, M., & Andersson, K. (2018) · Energies · doi:10.3390/en11102508 · Cited by 141
“The one selected in this work is the Lloyd’s (k-means) algorithm [37], which is a non-deterministic method computationally faster than conventional hierarchical tools.”
MethodQRSF: QoS-aware resource scheduling framework in cloud computing
Singh, S., & Chana, I. (2014) · The Journal of Supercomputing · doi:10.1007/s11227-014-1295-6 · Cited by 152
“Based on these distances workload is allocated to the nearest cluster [66] and the result of first iteration as shown in Table 8.”
BackgroundKhan, Z. A., & Sohn, W. (2011) · IEEE Transactions on Consumer Electronics · doi:10.1109/tce.2011.6131162 · Cited by 141
“The k-means [24] clustering algorithm is used to generate an optimal codebook of 32 after experimentation.”
MethodFu, X., Guo, Q., & Sun, H. (2020) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2020.2974021 · Cited by 141
“To fully verify the validity of the proposed method, in addition to Monte Carlo, the principal component analysis (PCA), as in [8], and the k-means, as in [28], are also used to estimate the PPF, and their results are compared with those of this paper.”
MethodDu, C., & Sun, D. (2004) · Journal of Food Engineering · doi:10.1016/j.jfoodeng.2004.05.044 · Cited by 140
Identifying driving safety profiles from smartphone data using unsupervised learning
Mantouka, E. G., Barmpounakis, E., & Vlahogianni, E. I. (2019) · Safety Science · doi:10.1016/j.ssci.2019.01.025 · Cited by 148
Ye, S., Ren, S., Song, C., Du, Z., Wang, K., Du, B., Feng, C., & Zhu, D. (2024) · Land Use Policy · doi:10.1016/j.landusepol.2024.107070 · Cited by 142
An Automatic GPR B-Scan Image Interpreting Model
Zhou, X., Chen, H., & Li, J. (2018) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2018.2799586 · Cited by 144
“Previous algorithms conduct clustering mostly based on the distance between points [24], [25], the density of points within a selected area [26]–[28], or horizontal scanning [22], in which the geometric characteristics of hyperbolas are not taken into account.”
BackgroundLuo, L., Tang, Y., Lu, Q., Chen, X., Zhang, P., & Zou, X. (2018) · Computers in Industry · doi:10.1016/j.compind.2018.03.017 · Cited by 138
Guo, J., Zhang, X., Гу, Ф., Zhang, H., & Fan, Y. (2019) · Journal of Cleaner Production · doi:10.1016/j.jclepro.2019.119372 · Cited by 142
Coarse-to-fine vision-based localization by indexing scale-Invariant features
Wang, J., Zha, H., & Cipolla, R. (2006) · IEEE Transactions on Systems Man and Cybernetics Part B (Cybernetics) · doi:10.1109/tsmcb.2005.859085 · Cited by 137
“The SIFT is sampled over a 4 4 grid in the neighborhood of an interest point.”
Chen, C., Liao, Z., Ju, Y., He, C., Yu, K., & Wan, S. (2022) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2022.3199191 · Cited by 137
“That is, the improved k-means was adopted to cluster the switch nodes to determine the number of controllers at different levels; then, the parameters obtained by k-means were used as an input for the heuristic algorithm GA to solve the multiobjective optimization problem, thereby determining the correspondence betwee…”
MethodThe Application of Artificial Intelligence in Project Management Research: A Review.
Ruiz, J. G., Martínez, J. M., & Crespo, R. A. G. (2021) · International Journal of Interactive Multimedia and Artificial Intelligence · doi:10.9781/ijimai.2020.12.003 · Cited by 136
Ge, Y., & Sealfon, S. C. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts300 · Cited by 155
Accelerating Lloyd’s Algorithm for k-Means Clustering
Hamerly, G., & Drake, J. (2014) · Springer eBooks · doi:10.1007/978-3-319-09259-1_2 · Cited by 159
“Just a few are: • clustering the pixels of an image for image color quantization [19, 7], • post-processing to decide the memberships in spectral clustering [29], • selecting the codewords for vector quantization, enabling lossy compression of audio or image data [23], • image segmentation [19,…”
BackgroundMethodInfluentialData-driven root cause diagnosis of faults in process industries
Li, G., Qin, S. J., & Yuan, T. (2016) · Chemometrics and Intelligent Laboratory Systems · doi:10.1016/j.chemolab.2016.09.006 · Cited by 135
Martinussen, L. M., Møller, M., & Prato, C. G. (2014) · Transportation Research Part F Traffic Psychology and Behaviour · doi:10.1016/j.trf.2014.06.008 · Cited by 134
Machine Learning-Based Load Balancing Algorithms in Future Heterogeneous Networks: A Survey
Güreş, E., Shayea, I. A. M., Ergen, M., Azmi, M. H., & El‐Saleh, A. A. (2022) · IEEE Access · doi:10.1109/access.2022.3161511 · Cited by 134
“We recommend that readers who want to know more about the k-Means algorithm should take a look at [98], [107].”
BackgroundChen, M., Zhang, Z., Wang, T., Backes, M., Humbert, M., & Zhang, Y. (2022) · Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3548606.3559352 · Cited by 133
“With respect to clustering, we rely on the widely used k-means algorithm[30], which consists of three phases: Initialization, nodes reassignment, and centroids updating.”
MethodSurvey of contemporary trends in color image segmentation
Vantaram, S. R., & Saber, E. S. (2012) · Journal of Electronic Imaging · doi:10.1117/1.jei.21.4.040901 · Cited by 144
“Among recent advances, Kanungo et al.(10) proposed an efficient version of the algorithm called the “filtering algorithm,””
MethodComprehensive Review of K-Means Clustering Algorithms
Oti, E. U., Olusola, M. O., Eze, F. C., & Enogwe, S. U. (2021) · International Journal of Advances in Scientific Research and Engineering · doi:10.31695/ijasre.2021.34050 · Cited by 171
“Kanungo et al. [35] presented a simple and efficient implementation of Lloyd’s k-means clustering algorithm which they called the filtering algorithm.”
MethodDing, Y., Zhang, Z., Zhao, X., Cai, Y., Li, S., Deng, B., & Cai, W. (2022) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2022.3198842 · Cited by 150
“To verify the clustering accuracy and real-time performances of the proposed L2GCC, we consider ten baselines for comparison, including k-means [15], FCM [17], FCM-S1 [22], SC [16], SSSC [24], S5C [25], DS3C-Net [11], AE [46] + k-means, DEC [30], and CC [34].”
MethodGAtor: A First-Principles Genetic Algorithm for Molecular Crystal Structure Prediction
Curtis, F., Li, X., Rose, T., Vázquez-Mayagoitia, Á., Bhattacharya, S., Ghiringhelli, L. M., & Marom, N. (2018) · Journal of Chemical Theory and Computation · doi:10.1021/acs.jctc.7b01152 · Cited by 130
Guan, R., Li, Z., Tu, W., Wang, J., Liu, Y., Li, X., Tang, C., & Feng, R. (2024) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2024.3370633 · Cited by 180
“1) k -means [17] is an outstanding representative of traditional unsupervised learning.”
BackgroundMethodA Novel Semisupervised Active-Learning Algorithm for Hyperspectral Image Classification
Wang, Z., Du, B., Zhang, L., Zhang, L., & Jia, X. (2017) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2017.2650938 · Cited by 131
“such as kernel k-means [31], [49], [50].”
Marketing analytics: Methods, practice, implementation, and links to other fields
France, S. L., & Ghose, S. (2018) · Expert Systems with Applications · doi:10.1016/j.eswa.2018.11.002 · Cited by 154
A systematic literature review on vision based gesture recognition techniques
Al‐Shamayleh, A. S., Ahmad, R. B., Abushariah, M. A. M., Alam, K. A., & Jomhari, N. (2018) · Multimedia Tools and Applications · doi:10.1007/s11042-018-5971-z · Cited by 142
“Table 7 Overview of demographic data Identifier References Citation RQ1 RQ2 RQ3 RQ4 S1 [83] 766 × × ✓ × S2 [80] 231 ✓ × × × S3 [136] 1273 ✓ × ✓ × S4 [23] 502 ✓ × ✓ × S5 [158] 133 ✓ × ✓ × S6 [109] 021 ✓ × ✓ × S7 [15] 137 ✓ × ✓ × S8 [21] 051 ✓ × × × S9 [3] 044 ✓ × × × S10 [62] 084 ✓ × × × S11 [51] 028 ✓ × × × S12 [61] 0…”
MethodInfluentialA 3D Laser Profiling System for Rail Surface Defect Detection
Xiong, Z., Li, Q., Mao, Q., & Zou, Q. (2017) · Sensors · doi:10.3390/s17081791 · Cited by 138
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.