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 401–500 of 1,008
Automatic Background Construction and Object Detection Based on Roadside LiDAR
Zhang, Z., Zheng, J., Xu, H., Wang, X., Fan, X., & Chen, R. (2019) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2019.2936498 · Cited by 82
“Many clustering algorithms, such as k-means, densitybased, and fuzzy algorithms, can be used [28]–[31].”
MethodFast large-scale trajectory clustering
Wang, S., Bao, Z., Culpepper, J. S., Sellis, T., & Qin, X. (2019) · Proceedings of the VLDB Endowment · doi:10.14778/3357377.3357380 · Cited by 94
“[31] have earlier used a k-d tree and a perpendicular bisector to prune a group of points in nodes of the k-d tree in Euclidean space, and showed that the index can greatly improve performance for k-means, especially in low dimensional space [28].”
MethodUnsupervised Deep Spectrum Sensing: A Variational Auto-Encoder Based Approach
Xie, J., Fang, J., Liu, C., & Yang, L. (2020) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2020.2982203 · Cited by 93
“The kernel K-means (KKM) [49] algorithm is an extension of the famous K-means (KM) [50] clustering algorithm which uses a non-linear function to map the clustering data into a latent space to avoid the requirement for linearly separable data by the KM algorithm.”
MethodCai, W., Wang, Y., Wang, W., Shu, N., Hou, Q., Tang, F., Shan, C., Yang, X., & Guo, Z. (2022) · Journal of Analytical Methods in Chemistry · doi:10.1155/2022/4614330 · Cited by 82
“In order to explore the regularity of aroma profiles in different SFB, GC-IMS characteristic peak intensities were selected as the feature variables, and K-means clustering algorithm was performed [30].”
MethodReddy, M. J. B., Chandra, B., & Mohanta, D. K. (2013) · IEEE Transactions on Dielectrics and Electrical Insulation · doi:10.1109/tdei.2013.6508770 · Cited by 82
“The detailed information on K-means algorithm is given in the following references [8, 13].”
MethodFast color/texture segmentation for outdoor robots
Blas, M. R., Agrawal, M., Sundaresan, A., & Konolige, K. (2008) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2008.4651086 · Cited by 90
“In the K-means iterations, reclassification attempts are not made for points that lie less than half the mean absolute distance away from their currently classified center (similar to [22]).”
BackgroundHand Gesture Recognition based on Radar Micro-Doppler Signature Envelopes
Amin, M. G., Zeng, Z., & Shan, T. (2019) · IEEE Radar Conference (RadarConf) · doi:10.1109/radar.2019.8835661 · Cited by 81
“In the training process, the K-means algorithm is used to cluster a central time-frequency trajectory [40].”
MethodLearning automata based energy-efficient AI hardware design for IoT applications
Wheeldon, A., Shafik, R., Rahman, T., Lei, J., Yakovlev, A., & Granmo, O. (2020) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.2019.0593 · Cited by 81
“We chose kMC as it is a fast and scalable method, which can progressively adapt to cluster centroids starting with a random datapoint [23].”
MethodFrom Twitter to traffic predictor: Next-day morning traffic prediction using social media data
Yao, W., & Qian, S. (2021) · Transportation Research Part C Emerging Technologies · doi:10.1016/j.trc.2020.102938 · Cited by 81
“Clustering methods such as K-means (Kanungo et al., 2002), Gaussian Mixture Model or GMM (Banfield and Raftery, 1993), Density-Based Spatial Clustering of Applications with Noise or DBSCAN (Ester et al., 1996) and Mean-Shift (Comaniciu and Meer, 2002) are the most popular choices for identifying…”
MethodInfluentialBorgwardt, K. M., Ghisu, E., Llinares-López, F., O’Bray, L., & Rieck, B. (2020) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000076 · Cited by 103
Ahmed, N., Ngadi, M. A., Sharif, J. M., Hussain, S., Uddin, M., Rathore, M. S., Iqbal, J., Abdelhaq, M., Alsaqour, R. A., Ullah, S. S., et al. (2022) · Sensors · doi:10.3390/s22207896 · Cited by 97
“In [53,54], the k-means algorithm is explaine in full detail.”
MethodForecasting crude oil price with a new hybrid approach and multi-source data
Yang, Y., Guo, J., Sun, S., & Li, Y. (2021) · Engineering Applications of Artificial Intelligence · doi:10.1016/j.engappai.2021.104217 · Cited by 86
Offline and Online UAV-Enabled Data Collection in Time-Constrained IoT Networks
Ghdiri, O., Jaafar, W., Alfattani, S., Abderrazak, J. B., & Yanıkömeroğlu, H. (2021) · IEEE Transactions on Green Communications and Networking · doi:10.1109/tgcn.2021.3104801 · Cited by 80
Smart Grid Cyber Security Enhancement: Challenges and Solutions—A Review
Alsuwian, T., Shahid Butt, A., & Amin, A. A. (2022) · Sustainability · doi:10.3390/su142114226 · Cited by 71
Unsupervised Clustering for Deep Learning: A tutorial survey
Karoly, A. I., Fuller, R. C., & Galambos, P. (2018) · Acta Polytechnica Hungarica · doi:10.12700/aph.15.8.2018.8.2 · Cited by 80
Accelerating K-Means clustering with parallel implementations and GPU computing
Bhimani, J., Leeser, M. E., & Mi, N. (2015) · IEEE High Performance Extreme Computing Conference · doi:10.1109/hpec.2015.7322467 · Cited by 80
“like using dormant bins, skip frequency and hierarchical structure of k-d tree data structure [3]–[5].”
BackgroundSingh, V., Gupta, I., & Jana, P. K. (2017) · Future Generation Computer Systems · doi:10.1016/j.future.2017.09.054 · Cited by 80
Application of machine learning to accidents detection at directional drilling
Gurina, E., Klyuchnikov, N., Zaytsev, A., Romanenkova, E., Antipova, K., Simon, I., Макаров, В. А., & Koroteev, D. A. (2019) · Journal of Petroleum Science and Engineering · doi:10.1016/j.petrol.2019.106519 · Cited by 83
“After the introduction of any distance, the whole database of time-series can be split into several groups with different clustering techniques, for example, K-means algorithm (Kanungo et al., 2002), mean-shift clustering (Cheng, 1995), agglomerative hierarchical clustering (Day and Edelsbrunner, 1984).”
MethodAyhan, B., Dao, M., Kwan, C., Chen, H.-M., Bell, J. F., & Kidd, R. D. (2017) · IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing · doi:10.1109/jstars.2017.2716923 · Cited by 79
“Tables V and VI demonstrate these cluster validity analysis of the six MS data versions using the five indicators for K-means and GMM methods.”
MethodSurrogate modeling: tricks that endured the test of time and some recent developments
Viana, F. A. C., Gogu, C., & Goel, T. (2021) · Structural and Multidisciplinary Optimization · doi:10.1007/s00158-021-03001-2 · Cited by 82
“With small to medium datasets, using clustering algorithms, such as k-means (Kanungo et al. 2002), improves robustness.”
MethodRecognizing Gaits on Spatio-Temporal Feature Domain
Kusakunniran, W. (2014) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2014.2336379 · Cited by 82
“In the histogram quantization step, the k−means clustering [43] is applied to all STIP descriptors D j,n, 1 ≤ j ≤ N, 1 ≤ n ≤ N j , from the gallery dataset.”
Who Deserves Solidarity? Unequal Treatment of Immigrants in Swiss Welfare Policy Delivery
Thomann, E., & Rapp, C. H. (2017) · Policy Studies Journal · doi:10.1111/psj.12225 · Cited by 109
Intrusion detection system using hybrid binary PSO and K-nearest neighborhood algorithm
Syarif, A. R., & Gata, W. (2017) · 2017 11th International Conference on Information & Communication Technology and System (ICTS) · doi:10.1109/icts.2017.8265667 · Cited by 74
“Although less cost-efficient in terms of time and cost, the solution of both in the IDS is the use of data mining [5][11].”
BackgroundParking Availability Prediction with Long Short Term Memory Model
Shao, W., Zhang, Y., Guo, B., Qin, A. K., Chan, J., & Salim, F. D. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-15093-8_9 · Cited by 78
Non-probabilistic polygonal convex set model for structural uncertainty quantification
Cao, L., Liu, J., Xie, L., Jiang, C., & Bi, R. (2020) · Applied Mathematical Modelling · doi:10.1016/j.apm.2020.07.025 · Cited by 78
Maximum margin clustering made practical
Zhang, K., Tsang, I. W.-H., & Kwok, J. T.-Y. (2007) · International Conference on Machine Learning · doi:10.1145/1273496.1273637 · Cited by 87
“Moreover, there are also several recent advances on scaling up the -means algorithm [12], [ 19 ], [25].”
BackgroundMulti-objective three stage design optimization for island microgrids
Sachs, J., & Sawodny, O. (2016) · Applied Energy · doi:10.1016/j.apenergy.2015.12.059 · Cited by 78
Ji, H., Wang, C., Li, P., Song, G., Yu, H., & Wu, J. (2019) · Applied Energy · doi:10.1016/j.apenergy.2019.02.008 · Cited by 79
Anomaly Detection in High-Dimensional Data
Talagala, P. D., Hyndman, R. J., & Smith‐Miles, K. (2020) · Journal of Computational and Graphical Statistics · doi:10.1080/10618600.2020.1807997 · Cited by 85
Lee, K. S., Pereira, F. C., Palatinszky, M., Behrendt, L., Alcolombri, U., Berry, D., Wagner, M., & Stocker, R. (2020) · Nature Protocols · doi:10.1038/s41596-020-00427-8 · Cited by 78
Κοψιδάς, Α., Milioti, C. P., Kepaptsoglou, K. L., & Vlahogianni, E. I. (2021) · Transportation Letters · doi:10.1080/19427867.2021.1901029 · Cited by 77
“For calculating this distance, an n-dimensional space was exploited, where n is the number of variables selected for clustering (Kanungo et al. 2002).”
MethodTransmission Defense Hardening Against Typhoon Disasters Under Decision-Dependent Uncertainty
Zhang, W., Shao, C., Hu, B., Xie, K., Siano, P., Li, M., & Cao, M. (2022) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2022.3194307 · Cited by 77
“Usually, the clustering technique [16] and scenario reduction technique [17] are utilized to reduce the computational complexity.”
MethodNeighborhoods and adolescent health-risk behavior: An ecological network approach
Browning, C. R., Soller, B., & Jackson, A. L. (2014) · Social Science & Medicine · doi:10.1016/j.socscimed.2014.06.028 · Cited by 88
“The k-means clustering algorithm selects random coordinates to serve as base points (i.e., centroids) to which other data points are assigned (Kanungo et al., 2002).”
BackgroundMethodDensity-Weighted Nyström Method for Computing Large Kernel Eigensystems
Zhang, K., & Kwok, J. T.-Y. (2008) · Neural Computation · doi:10.1162/neco.2009.11-07-651 · Cited by 77
“There are also several recent advances on scaling up the k-means algorithm (Pelleg & Moore, 1999; Elkan, 2003; Kanungo et al., 2002).”
BackgroundChen, Z., Jia, K., Xiao, C., Wei, D., Zhao, X. H., Lan, J., Wei, X., Yao, Y., Wang, B., Sun, Y., et al. (2020) · Remote Sensing · doi:10.3390/rs12132110 · Cited by 79
“K-means is a simply and efficient iterative clustering algorithm that can be used as the dimensional reduction algorithm without label information [67,68].”
MethodLocalization of RFID-equipped assets during the operation phase of facilities
Motamedi, A., Soltani, M. M., & Hammad, A. (2013) · Advanced Engineering Informatics · doi:10.1016/j.aei.2013.07.001 · Cited by 76
“The proposed method for clustering uses combination of two criteria for selecting members of each cluster: (1) closeness of reference tags: by selecting the reference tags that are spatially close to each other using algorithms such as k-means [14] and (2) similarity”
DPCG: an efficient density peaks clustering algorithm based on grid
Xu, X. W., Ding, S., Du, M., & Xue, Y. (2016) · International Journal of Machine Learning and Cybernetics · doi:10.1007/s13042-016-0603-2 · Cited by 76
“To demonstrate the operating efficiency of the DPCG algorithms, we compare it with other algorithms (such as DPC algorithm, DBSCAN algorithm [31], K-means algorithm [32] and SC algorithm) on both artificial data sets and UCI data sets.”
MethodAn analysis of MapReduce efficiency in document clustering using parallel K-means algorithm
Sardar, T. H., & Ansari, Z. (2018) · Future Computing and Informatics Journal · doi:10.1016/j.fcij.2018.03.003 · Cited by 76
On recommendation of learning objects using Felder–Silverman learning style model
Nafea, S. M., Siewe, F., & He, Y. (2019) · IEEE Access · doi:10.1109/access.2019.2935417 · Cited by 75
“The K-means algorithm [65] is one of the most popular clustering algorithms due to its simplicity and intuitive interpretation.”
MethodMovie recommender system with metaheuristic artificial bee
Katarya, R. (2018) · Neural Computing and Applications · doi:10.1007/s00521-017-3338-4 · Cited by 75
“The k-mean algorithm has been widely used clustering approach in data mining [46, 47].”
MethodMulti-UAV Data Collection Framework for Wireless Sensor Networks
Alfattani, S., Jaafar, W., Yanıkömeroğlu, H., & Yongaçoğlu, A. (2019) · Globecom · doi:10.1109/globecom38437.2019.9014306 · Cited by 75
“Algorithm 1 Determining the number and locations of CHs 1: Initialize K ′ = 1 2: Initialize d s using (2) 3: Run K-means [10], get H and D1 4: Calculate dmax = maxs∈C1 ‖gs − h1‖ 5: while dmax > d th s and K ′ < K do 6: K ′ = K ′ + 1 7: Run K-means [10], get H and Di (i = 1, .”
MethodTime-aware Path Reasoning on Knowledge Graph for Recommendation
Zhao, Y., Wang, X., Chen, J., Wang, Y., Tang, W., He, X., & Xie, H. (2022) · ACM Transactions on Information Systems · doi:10.1145/3531267 · Cited by 95
“We leave the exploration of other clustering methods, such as K-means [17], DBSCAN [7], and Mean-shift [4], in future work.”
MethodFast approximate k-means via cluster closures
Wang, J., Wang, J., Ke, Q., Zeng, G., & Li, S. (2012) · IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings · doi:10.1109/cvpr.2012.6248034 · Cited by 81
A look at Gaussian mixture reduction algorithms
Crouse, D. F., Willett, P., Pattipati, K. R., & Svensson, L. (2011) · Chalmers Publication Library (Chalmers University of Technology) · Cited by 75
A Review on Automated Brain Tumor Detection and Segmentation from MRI of BrainPreprint
Roy, S. S., Nag, S., Maitra, I. K., & Bandyopadhyay, S. K. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1312.6150 · Cited by 86
Ai, X., Zheng, X., Zhang, Y., Liu, Y., Ou, X., Xia, C., & Liu, L. (2024) · The Science of The Total Environment · doi:10.1016/j.scitotenv.2024.173828 · Cited by 74
Vehicle Detection and Tracking in Complex Traffic Circumstances with Roadside LiDAR
Zhang, Z., Zheng, J., Xu, H., & Wang, X. (2019) · Transportation Research Record Journal of the Transportation Research Board · doi:10.1177/0361198119844457 · Cited by 79
Abushiba, W., Johnson, P., Alharthi, S., & Wright, C. (2017) · International Computer Engineering Conference · doi:10.1109/icenco.2017.8289762 · Cited by 73
“The centralized kMeans [4], finding the mean of the locations of the nodes and then decided on the centroid of the layout cluster area.”
MethodInfluentialAnalysis and Visualization of Spatial Transcriptomic Data
Liu, B., Li, Y., & Zhang, L. (2022) · Frontiers in Genetics · doi:10.3389/fgene.2021.785290 · Cited by 80
Hong, G., Liu, S., Liu, W., & Wu, X. (2024) · Sustainable Cities and Society · doi:10.1016/j.scs.2024.105253 · Cited by 74
Lane-changing behavior on urban streets: A focus group-based study
Sun, D., & Elefteriadou, L. (2010) · Applied Ergonomics · doi:10.1016/j.apergo.2010.11.001 · Cited by 73
“To classify drivers into groups, the K-means algorithm (Kanungo et al., 2002) was used to cluster n (n1⁄4 17) participants based on overall aggressiveness into k (k1⁄4 1, 2, 3, 4, or 5) partitions, k < n.”
MethodClustering techniques and their applications in engineering
Pham, D. T., & Afify, A. (2007) · Proceedings of the Institution of Mechanical Engineers Part C Journal of Mechanical Engineering Science · doi:10.1243/09544062jmes508 · Cited by 82
Music similarity-based approach to generating dance motion sequence
Lee, M., Lee, K., & Park, J. (2012) · Multimedia Tools and Applications · doi:10.1007/s11042-012-1288-5 · Cited by 73
“1, are classified into 137 clusters using the K-means clustering algorithm [9, 11].”
MethodZhao, M., Shi, J., & Lin, C. W. (2019) · Applied Energy · doi:10.1016/j.apenergy.2019.03.195 · Cited by 76
Wang, B.-C., & Li, H. (2018) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2018.2859444 · Cited by 72
“The famous K-means clustering method [28] is utilized to seek the centers, i.”
MethodTime-Series Clustering for Home Dwell Time during COVID-19: What Can We Learn from It?
Huang, X., Li, Z., Lu, J., Wang, S., Wei, H., & Chen, B. (2020) · ISPRS International Journal of Geo-Information · doi:10.3390/ijgi9110675 · Cited by 72
Biswas, M., Saba, L., Omerzu, T., Johri, A. M., Khanna, N. N., Višković, K., Mavrogeni, S. I., Laird, J. R., Pareek, G., Miner, M. M., et al. (2021) · Journal of Imaging Informatics in Medicine · doi:10.1007/s10278-021-00461-2 · Cited by 75
On the Influence of Description Logics Ontologies on Conceptual Similarity
d’Amato, C., Staab, S., & Fanizzi, N. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-87696-0_7 · Cited by 72
“The notion of similarity has been active, prominent and seminal in the areas of cognitive psychology [29, 16, 14], knowledge acquisition [25], data management and information organization [15, 22, 17] for a long time.”
BackgroundPositive unlabeled learning for time series classification
Nguyen, M. N., Li, X., & Ng, S.-K. (2011) · doi:10.5591/978-1-57735-516-8/ijcai11-240 · Cited by 72
Strain and charge carrier coupling in epitaxial graphene
Schmidt, D. A., Ohta, T., & Beechem, T. E. (2011) · Physical Review B · doi:10.1103/physrevb.84.235422 · Cited by 72
Stacked LSTM Deep Learning Model for Traffic Prediction in Vehicle-to-Vehicle Communication
Du, X., Zhang, H., Nguyen, H. V., & Han, Z. (2017) · IEEE Vehicular Technology Conference · doi:10.1109/vtcfall.2017.8288312 · Cited by 72
“Also for data that don’t contain labels, unsupervised learning approaches, such as K-Means clustering [21] and Support Vector Machine (SVM) [22], can be utilized to cluster data which are statistically similar.”
MethodAn efficient K-means clustering algorithm for tall data
Capó, M., Pérez, A., & Lozano, J. A. (2020) · Data Mining and Knowledge Discovery · doi:10.1007/s10618-020-00678-9 · Cited by 72
Chen, T.-S., Tsai, T., Chen, Y., Lin, C.-C., Chen, R.-C., Li, S.-Y., & Chen, H. (2005) · International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS) · doi:10.1109/ispacs.2005.1595432 · Cited by 72
Automated Body Parts Estimation and Detection using Salient Maps and Gaussian Matrix Model
Arif, A., & Jalal, A. (2021) · International Bhurban Conference on Applied Sciences and Technology (IBCAST) · doi:10.1109/ibcast51254.2021.9393268 · Cited by 71
Low-rank representation with adaptive dictionary learning for subspace clustering
Chen, J., Mao, H., Wang, Z., & Zhang, X. (2021) · Knowledge-Based Systems · doi:10.1016/j.knosys.2021.107053 · Cited by 71
Data-Driven Partitioning of Power Networks Via Koopman Mode Analysis
Raak, F., Susuki, Y., & Hikihara, T. (2015) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2015.2464779 · Cited by 76
“When the -means clustering algorithm [27] is applied to the”
MethodSemantic Labeling of Mobile LiDAR Point Clouds via Active Learning and Higher Order MRF
Luo, H., Wang, C., Wen, C., Chen, Z., Zai, D., Yu, Y., & Li, J. (2018) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2018.2802935 · Cited by 71
“More specifically, all the pairwise supervoxels, which are the inputs to Algorithm 2, are clustered into several groups by applying k-means clustering [39].”
MethodShan, P., Lv, H. P., Yu, L., Ge, H., Li, Y., & Gu, L. (2020) · IEEE Sensors Journal · doi:10.1109/jsen.2020.2980868 · Cited by 71
“fault diagnosis: 1) SVM; 2) K-means [20]; 3)Naive Bayes; 4) Decision Tree; 5) Random forest [21]; 6) BPNN [22]; 7) DCNN [22]; 8) MB-CNN [23]; 9) LSTM [24].”
Duquesnoy, M., Boyano, I., Ganborena, L., Cereijo, P., Ayerbe, E., & Franco, A. A. (2021) · Energy and AI · doi:10.1016/j.egyai.2021.100090 · Cited by 70
Faust, O., Yu, W., & Kadri, N. A. (2013) · Journal of Mechanics in Medicine and Biology · doi:10.1142/s0219519413500334 · Cited by 70
Automated wound identification system based on image segmentation and Artificial Neural Networks
Song, B., & Saçan, A. (2012) · IEEE International Conference on Bioinformatics and Biomedicine (BIBM) · doi:10.1109/bibm.2012.6392633 · Cited by 84
“With the new centroids, the iteration continues until the new centroids are same as the centroids in the last iteration, representing the convergence of the algorithm [8, 17].”
Scaling and automation of a high-throughput single-cell-derived tumor sphere assay chip
Cheng, Y.-H., Chen, Y., Brien, R., & Yoon, E. (2016) · Lab on a Chip · doi:10.1039/c6lc00778c · Cited by 70
Scalable Tucker Factorization for Sparse Tensors - Algorithms and Discoveries
Oh, S., Park, N., Lee, S., & Kang, U. (2018) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2018.00104 · Cited by 70
“Thus, we can apply K-means clustering algorithm [31] on factor matrices to discover hidden concepts.”
MethodA DATA MINING APPLICATION IN A STUDENT DATABASE
Erdoğan, Ş. Z., & Timor, M. (2005) · Havacılık ve uzay teknolojileri dergisi · Cited by 70
Wang, P., Fu, Y., Zhang, J., Li, X., & Lin, D. (2018) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3209686 · Cited by 94
“For (i), we applied k-means [31] to cluster the communities into five groups.”
MethodMachine Learning for Forecasting Mid-Price Movements Using Limit Order Book Data
Nousi, P., Tsantekidis, A., Passalis, N., Ntakaris, A., Kanniainen, J., Tefas, A., Gabbouj, M., & Iosifidis, A. (2019) · IEEE Access · doi:10.1109/access.2019.2916793 · Cited by 69
Du, Q., & Wang, D. (2005) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2004.12.008 · Cited by 69
“, [1,3-7].”
Process control in CNC manufacturing for discrete components: A STEP-NC compliant framework
Kumar, S., Nassehi, A., Newman, S. T., Allen, R. D., & Tiwari, M. (2007) · Robotics and Computer-Integrated Manufacturing · doi:10.1016/j.rcim.2007.02.015 · Cited by 69
Chen, W., Hu, X., Chen, W., Hong, Y.-F., & Yang, M. (2018) · Remote Sensing · doi:10.3390/rs10071078 · Cited by 69
“The k-means clustering is so simple as to be easy to implement and apply, even on large datasets; however, one of its biggest drawbacks is that k, the number of clusters, is a predefined parameter, and an inappropriate choice of k may yield poor clustering results [21].”
MethodA Study on Container Vulnerability Exploit Detection
Tunde-Onadele, O., He, J., Dai, T., & Gu, X. (2019) · IEEE International Conference on Cloud Engineering · doi:10.1109/ic2e.2019.00026 · Cited by 69
“, clustering [12], k nearest neighbor [13], self-organizing map [14]).”
BackgroundHuang, J. L., Yang, X., & Peng, K. (2020) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2020.3019499 · Cited by 70
A Data Science and Engineering Solution for Fast K-Means Clustering of Big Data
Dierckens, K. E., Harrison, A. B., Leung, C. K.-S., & Pind, A. V. (2017) · IEEE International Conference on Trust, Security and Privacy in Computing and Communications (TrustCom) · doi:10.1109/trustcom/bigdatase/icess.2017.332 · Cited by 68
A Study of Machine-Learning Classifiers for Hypertension Based on Radial Pulse Wave
Luo, Z.-Y., Cui, J. W., Hu, X., Tu, L., Liu, H.-D., Jiao, W., Zeng, L.-Z., Jing, C., Qiao, L., Ma, X., et al. (2018) · BioMed Research International · doi:10.1155/2018/2964816 · Cited by 73
“Clustering analysis [20] is a classical method of unsupervised learning, and its most representative algorithm is Kmeans.”
MethodSuperpixel Contracted Neighborhood Contrastive Subspace Clustering Network for Hyperspectral Images
Cai, Y., Zhang, Z., Ghamisi, P., Ding, Y., Liu, X., Cai, Z., & Gloaguen, R. (2022) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2022.3179637 · Cited by 84
“can be further subdivided into centroid-based methods, such as k-Means [32] and fuzzy c-Means (FCM) [33], graphbased methods, e.”
MethodZhou, G., Zhang, Z., Yin, W., Chen, H., Wang, L., Wang, D., & Ma, H. (2023) · Nondestructive Testing And Evaluation · doi:10.1080/10589759.2023.2191954 · Cited by 68
“The classical image segmentation algorithms include the K-mean clustering algo-rithm [39] and the region growing algorithm [40].”
MethodFiddes, J., & Gruber, S. (2012) · Geoscientific model development · doi:10.5194/gmd-5-1245-2012 · Cited by 68
“…can be proven that the procedure will always terminate, the K -means algorithm is sensitive to the initial configuration of cluster seeds and does not necessarily find the optimal configuration (Kanungo et al., 2002), corresponding to the global objective function minimum (as opposed local minima).”
Data clustering with modified K-means algorithm
Singh, R. V., & Bhatia, M. P. S. (2011) · International Conference on Recent Trends in Information Technology · doi:10.1109/icrtit.2011.5972376 · Cited by 68
Wang, X., Chai, S. M., Isnardi, M. A., Lim, S., & Karri, R. (2016) · ACM Transactions on Architecture and Code Optimization · doi:10.1145/2857055 · Cited by 68
“For a more comprehensive analysis, the classification algorithms, such as k-means clustering [Kanungo et al. 2002] and adaptive boosting [Lin 2008], can be applied.”
MethodRundo, L., Militello, C., Russo, G. I., Garufi, A., Vitabile, S., Gilardi, M. C., & Mauri, G. (2017) · Information · doi:10.3390/info8020049 · Cited by 71
“In contrast to the K-Means algorithm [70] that yields a “hard” clustering output, where each feature vector is assigned to exactly one group, the FCM algorithm defines a fuzzy partition P using a fuzzy set family P = {Y1, Y2, .”
MethodA Unified Collaborative Multikernel Fuzzy Clustering for Multiview Data
Zeng, S., Wang, X., Cui, H., Zheng, C., & Feng, D. D. (2017) · IEEE Transactions on Fuzzy Systems · doi:10.1109/tfuzz.2017.2743679 · Cited by 70
“The conventional clustering algorithms, such as k-means [1], fuzzy c-means (FCM) [2]–[3], spectral clustering [4], maximum entropy clustering [5] and possibilistic fuzzy c-means [6]–[7] receive tremendous popularity due to their simplicity and rapid computation.”
MethodJia, X., & Meng, M. Q. ‐. (2017) · Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC) · doi:10.1109/embc.2017.8037526 · Cited by 68
“we apply k-means clustering method [13] to summarize the information of each image into a 2-D histogram, where the x-axis represents the index of the cluster centroids and the yaxis denotes the number of pixels belonging to each cluster.”
MethodThe K -Means Algorithm Evolution
Pérez-Ortega, J., Almanza-Ortega, N. N., Vega-Villalobos, A., Pazos-Rangel, R. A., Zavala-Díaz, C., & Martínez, A. (2020) · IntechOpen eBooks · doi:10.5772/intechopen.85447 · Cited by 97
“Another remarkable improvement to the work in [82] is presented in [83].”
BackgroundMethodExtreme clustering – A clustering method via density extreme points
Wang, S., Li, Q., Zhao, C., Xingquan Zhu, A., Yuan, H., & Dai, T. (2020) · Information Sciences · doi:10.1016/j.ins.2020.06.069 · Cited by 67
Torrens, P. M., Li, X., & Griffin, W. A. (2011) · Transactions in GIS · doi:10.1111/j.1467-9671.2011.01261.x · Cited by 73
“To resolve equivalencies in simulation, we apply the K-Means Clustering (KMC) algorithm (Kanungo et al. 2002) as selection logic.”
MethodOn Feature Matching and Image Registration for Two‐dimensional Forward‐scan Sonar Imaging
Aykin, M. D., & Negahdaripour, S. (2013) · Journal of Field Robotics · doi:10.1002/rob.21461 · Cited by 67
“To identify the object, ground, and cast shadow regions, we apply the well-known k-means segmentation and clustering algorithm (with k = 3) Kanungo et al., 2002; MacKay, 2003.”
MethodA review of Nyström methods for large-scale machine learning
Sun, S., Zhao, J., & Zhu, J. (2015) · Information Fusion · doi:10.1016/j.inffus.2015.03.001 · Cited by 90
“Recent advances in speeding up the K-means algorithm [54, 55] also make it particularly suitable for large-scale problems.”
BackgroundA DOST based approach for the condition monitoring of 11 kV distribution line insulators
Reddy, M. J. B., Chandra, B., & Mohanta, D. K. (2011) · IEEE Transactions on Dielectrics and Electrical Insulation · doi:10.1109/tdei.2011.5739465 · Cited by 67
“Update step: Calculate the new means to be the centroid of the observations in the cluster [15, 23].”
BackgroundMethodInfluentialComprehensive Evaluation of AIMS Texture, Angularity, and Dimension Measurements
Mahmoud, E. M., Gates, L., Masad, E. A., Erdoğan, S. T., & Garboczi, E. J. (2009) · Journal of Materials in Civil Engineering · doi:10.1061/(asce)mt.1943-5533.0000033 · Cited by 67
FiDoop-DP: Data Partitioning in Frequent Itemset Mining on Hadoop Clusters
Xun, Y., Zhang, J., Qin, X., & Zhao, X. (2016) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2016.2560176 · Cited by 67
“K-means clustering aims to partition n objects into k clusters [20], [21].”
MethodPipe Failure Prediction in Water Distribution Systems Considering Static and Dynamic Factors
Farmani, R., Kakoudakis, K. I., Behzadian, K., & Butler, D. (2017) · Procedia Engineering · doi:10.1016/j.proeng.2017.03.217 · Cited by 67
“Kmeans is an unsupervised learning algorithm popular due to its simplicity and efficiency [18].”
Background
Metadata
- Authors
- Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C. D., Silverman, R., & Wu, A. Y.
- Venue
- IEEE Transactions on Pattern Analysis and Machine Intelligence
- Published
- 2002-07
- Volume
- 24
- Issue
- 7
- Pages
- 881-892
- ISSN
- 0162-8828 (ISSN-L)
- OpenAlex
- W2161160262
- Cited by
- 5,660
- References
- 60
- Citations by year
- 2026: 127 · 2025: 206 · 2024: 270 · 2023: 290 · 2022: 349 · 2021: 415 · 2020: 405 · 2019: 443 · 2018: 429 · 2017: 375 · 2016: 327 · 2015: 303 · 2014: 294 · 2013: 272 · 2012: 273
- FWCI
- 30.44
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Pattern Analysis and Machine Intelligence (publishedVersion)
- Funders
- National Science Foundation
- U.S. Department of Defense
- Army Research Laboratory
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Advanced Clustering Algorithms Research
- Physical Sciences › Computer Science › Information Systems › Data Mining and Machine Learning Applications
- Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Methods and Mixture Models
- Keywords
- K-means clustering, Lloyd's algorithm, filtering algorithms, k-d tree, cluster separation, color quantization, data compression, image segmentation
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.