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 901–1,000 of 1,008
An adaptive system for modelling and simulation of electrical arc furnaces
Janabi‐Sharifi, F., & Jorjani, G. (2009) · Control Engineering Practice · doi:10.1016/j.conengprac.2009.05.006 · Cited by 38
Local tone mapping using the K-means algorithm and automatic gamma setting
Lee, J. W., Park, R., & Chang, S. (2011) · IEEE Transactions on Consumer Electronics · doi:10.1109/tce.2011.5735504 · Cited by 38
Data mining in mining engineering: results of classification and clustering of shovels failures data
Dindarloo, S. R., & Siami-Irdemoosa, E. (2016) · International Journal of Mining Reclamation and Environment · doi:10.1080/17480930.2015.1123599 · Cited by 38
“In cases that the number of objects is small, as in here where there are only 10 shovels to be clustered, the clustering will lose its meaning if a very large or very small value of K is selected [39].”
BackgroundMethodVisual inspection of railroad tracks.
Babenko, P. (2011) · Journal of International Crisis and Risk Communication Research · Cited by 38
An Efficient Fuzzy-Based Hybrid System to Cloud Intrusion Detection
Raja, S., & Ramaiah, S. (2016) · International Journal of Fuzzy Systems · doi:10.1007/s40815-016-0147-3 · Cited by 38
“K-means clustering [21] achieves better accuracy than other clustering techniques.”
MethodCentroidal Voronoi tessellation based algorithms for vector fields visualization and segmentation
Du, Q., & Wang, X. (2005) · Visualization · doi:10.1109/visual.2004.13 · Cited by 38
“The costs of both Algorithms 1 and 2 may be reduced at the price of increased storage [Kanungo et al. 2002].”
BackgroundCharacterizing Software Engineering Work with Personas Based on Knowledge Worker Actions
Ford, D., Zimmermann, T., Bird, C., & Nagappan, N. (2017) · 2017 ACM/IEEE International Symposium on Empirical Software Engineering and Measurement (ESEM) · doi:10.1109/esem.2017.54 · Cited by 37
“Step 3: We used k-means clustering [21] to iteratively group respondents who reported similar relative time spent for each knowledge worker action into groups.”
MethodAugmented Sparse Representation for Incomplete Multiview Clustering
Chen, J., Yang, S., Peng, X., Peng, D., & Wang, Z. (2022) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2022.3201699 · Cited by 37
Robust Adaptive Time-Frequency Filtering for Frequency Shift Jamming Suppression
Huang, Q., Wei, S., & Zhang, L. (2023) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2023.3297559 · Cited by 37
Advances in Machine Learning Processing of Big Data from Disease Diagnosis Sensors
Lu, S., Yang, J., Gu, Y., He, D., Wu, H., Sun, W., Xu, D. M., Li, C. M., & Guo, C. (2024) · ACS Sensors · doi:10.1021/acssensors.3c02670 · Cited by 37
Machine learning algorithms for FPGA Implementation in biomedical engineering applications: A review
Altman, M. B., Wan, W., Hosseini, A. S., Nowdeh, S. A., & Alizadeh, M. (2024) · Heliyon · doi:10.1016/j.heliyon.2024.e26652 · Cited by 47
“Covington et al. [177] implemented k-means clustering using the Cosine Theta Distance Metric for document clustering.”
MethodData clustering approaches survey and analysis
Ahalya, G., & Pandey, H. M. (2015) · International Conference on Futuristic Trends on Computational Analysis and Knowledge Management · doi:10.1109/ablaze.2015.7154919 · Cited by 37
Analysis of cellular objects through diffraction images acquired by flow cytometry
Zhang, J., Feng, Y., Moran, M. S., Lu, J. Q., Yang, L. V., Sa, Y., Zhang, N., Dong, L., & Hu, X. (2013) · Optics Express · doi:10.1364/oe.21.024819 · Cited by 37
Li, C., Wang, X., Eberl, S., FULHAM, M. J., Yin, Y., & Feng, D. D. (2014) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2014.2344660 · Cited by 38
“The region-based level set energy functional is often derived from different classification models [6, 12], which include the K-means [13], fuzzy C-means [14] and Gaussian mixture models [15].”
MethodTopic segmentation via community detection in complex networks
de Arruda, H. F., Costa, L. D. F., & Amancio, D. R. (2016) · Chaos An Interdisciplinary Journal of Nonlinear Science · doi:10.1063/1.4954215 · Cited by 37
Extreme waves in New Zealand waters
Godoi, V. A., Bryan, K. R., Stephens, S. A., & Gorman, R. M. (2017) · Ocean Modelling · doi:10.1016/j.ocemod.2017.08.004 · Cited by 37
Cardioventilatory Control in Preterm-born Children and the Risk of Obstructive Sleep Apnea
Domany, K. A., Hossain, M. M., Nava-Guerra, L., Khoo, M. C. K., McConnell, K. B., Carroll, J. L., Xu, Y., DiFrancesco, M. W., & Amin, R. S. (2018) · American Journal of Respiratory and Critical Care Medicine · doi:10.1164/rccm.201708-1700oc · Cited by 37
“(32, 33) One of the main advantages of this modeling framework over traditional clustering approaches such as K-means clustering (34) or classification tree (CART) based methods (35), is that the cluster membership is mainly derived from a set of covariates.”
BackgroundTian, T., Li, C., Xu, J., & Ma, J. (2018) · Sensors · doi:10.3390/s18030904 · Cited by 37
“In our pipeline, pre-trained DCNNs are employed to extract deep features on the training data first, and then, K-means clustering is applied on the feature vectors to produce the visual words, which will construct the visual dictionary for the following detection steps.”
InfluentialHeterogeneity Analysis and Diagnosis of Complex Diseases Based on Deep Learning Method
Li, X., Liu, L.-Y., Zhou, J., & Wang, C. (2018) · Scientific Reports · doi:10.1038/s41598-018-24588-5 · Cited by 26
“Various applications have proved that K -means clustering is a simple yet powerful tool 30 .”
BackgroundMaity, D., & Ciezobka, J. (2019) · SPE Reservoir Evaluation & Engineering · doi:10.2118/194496-pa · Cited by 37
An investigation of biases in web search engine query suggestions
Bonart, M., Samokhina, A., Heisenberg, G., & Schaer, P. (2019) · Online Information Review · doi:10.1108/oir-11-2018-0341 · Cited by 37
“The k-means clustering algorithm was chosen here (Kanungo et al., 2002).”
MethodA bibliometric analysis of revenue management in airline industry
Raza, S. A., Ashrafi, R., & Akgündüz, A. (2020) · Journal of Revenue and Pricing Management · doi:10.1057/s41272-020-00247-1 · Cited by 40
Energy-Efficient Multi-UAV Data Collection for IoT Networks with Time Deadlines
Ghdiri, O., Jaafar, W., Alfattani, S., Abderrazak, J. B., & Yanıkömeroğlu, H. (2020) · Globecom · doi:10.1109/globecom42002.2020.9322626 · Cited by 37
“, Kmeans [12], density-based spatial clustering, and hierarchical cluster analysis (HCA) [13].”
MethodUnsupervised Machine Learning for Clustering in Political and Social Research
Waggoner, P. (2020) · Cambridge University Press eBooks · doi:10.1017/9781108883955 · Cited by 37
Huang, J., Li, S., Zi, Y., Qian, Y., Cai, W., Aldén, M., & Li, Z. (2020) · Measurement Science and Technology · doi:10.1088/1361-6501/abd7aa · Cited by 37
“More details on the K -means algorithm can be found in Kanungo et al [49].”
CELOF: Effective and fast memory efficient local outlier detection in high-dimensional data streams
Chen, L., Wang, W., & Yang, Y. (2021) · Applied Soft Computing · doi:10.1016/j.asoc.2021.107079 · Cited by 40
Contrastive Adversarial Learning for Person Independent Facial Emotion Recognition
Kim, D. H., & Song, B. C. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v35i7.16743 · Cited by 46
“Grouping of emotion samples : To verify that Otsu algo-rithm is nearly optimal for grouping emotional samples, we calculated k cluster centers per domain using k -means clustering (Kanungo et al. 2002), and averaged them to determine the decision threshold.”
MethodSuburban greening and suburbanization changing surface urban heat island intensity in China
Liu, S., Shi, K., Wu, Y., & Cui, Y. (2022) · Building and Environment · doi:10.1016/j.buildenv.2022.109906 · Cited by 40
Zhang, T., & Lee, B. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-31588-6_65 · Cited by 37
Mining sustainability indicators to classify hydrocarbon development
Shaheen, M., Shahbaz, M., Guergachi, A., & Rehman, Z. U. (2011) · Knowledge-Based Systems · doi:10.1016/j.knosys.2011.04.016 · Cited by 37
Tracking People Motion Based on Extended Condensation Algorithm
García, J., Gardel, A., Bravo, I., Galilea, J. L. L., & Martínez, M. (2013) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmca.2012.2220540 · Cited by 37
“This process is based on a standard K-means algorithm [31], which groups particles into clusters, minimizing the quadratic distance between each position of a particle and the cluster centroid.”
MethodA fast divisive clustering algorithm using an improved discrete particle swarm optimizer
Feng, L., Qiu, M., Wang, Y., Xiang, Q.-L., Yang, Y., & Liu, K. (2010) · Pattern Recognition Letters · doi:10.1016/j.patrec.2010.04.001 · Cited by 37
Occupancy Mapping and Surface Reconstruction Using Local Gaussian Processes With Kinect Sensors
Kim, S., & Kim, J. (2013) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2013.2272592 · Cited by 37
Continuous k-Means Monitoring over Moving Objects
Zhang, Z., Yang, Y., Tung, A. K. H., & Dimitris Papadias, C. (2008) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2008.54 · Cited by 37
“Since the minimum element in the heap can be extracted in O(log n) time, the total construction cost of Pactive is small. m'm d p σ σ p d'p Figure 3.4 Illustration of dp and d'p After HC* converges, TKM computes the new thresholds.”
BackgroundInfluentialVariational 3D Shape Segmentation for Bounding Volume Computation
Lü, L., Choi, Y., Wang, W., & Kim, M. (2007) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2007.01055.x · Cited by 37
Vision-based Global Localization Using a Visual Vocabulary
Wang, J., Cipolla, R., & Zha, H. (2006) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2005.1570770 · Cited by 37
“We use the k-means algorithm [5] to learn a visual vocabulary where each term is a cluster of descriptors with similar appearance.”
BackgroundMethodInfluentialLeung, B. H. K., Poon, C. C. Y., Zhang, R., Zheng, Y., Chan, C. K. W., Chiu, P. W. Y., Lau, J. Y. W., & Sung, J. J. �. (2016) · IEEE Transactions on Biomedical Engineering · doi:10.1109/tbme.2016.2591060 · Cited by 38
“These pixels were first divided into m clusters by k-means clustering [20] and the cluster means were gathered to form a color feature pool of m in size, which represents the typical colors of blood or bloodlike pixels.”
Content Adaptive Mesh Representation of Images Using Binary Space Partitions
Sarkis, M., & Diepold, K. J. (2009) · IEEE Transactions on Image Processing · doi:10.1109/tip.2009.2016148 · Cited by 37
“The second is based on the kmeans clustering technique which splits a triangle by finding the centers of the two main clusters of the pixels [24].”
MethodTensor-Based 2-D DOA Estimation for L-Shaped Nested Array
Xu, F., Zheng, H., & Vorobyov, S. A. (2023) · IEEE Transactions on Aerospace and Electronic Systems · doi:10.1109/taes.2023.3326793 · Cited by 36
Cluster-based ordinary kriging of piezometric head in West Texas/New Mexico – Testing of hypothesis
Abedini, M. J., Nasseri, M., & Ansari, A. (2008) · Journal of Hydrology · doi:10.1016/j.jhydrol.2007.12.030 · Cited by 36
“In the literature, there are some efforts to improve the traditional k-mean algorithm (Pelleg and Moore, 1999; Kanungo et al., 2002).”
BackgroundTubular Surface Segmentation for Extracting Anatomical Structures From Medical Imagery
Mohan, V., Sundaramoorthi, G., & Tannenbaum, A. (2010) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2010.2050896 · Cited by 36
Refining Geometry from Depth Sensors using IR Shading Images
Choe, G., Park, J., Tai, Y., & Kweon, I. S. (2016) · International Journal of Computer Vision · doi:10.1007/s11263-016-0937-y · Cited by 37
A fast and accurate algorithm for unsupervised clustering around centroids
Mazzeo, G. M., Masciari, E., & Zaniolo, C. (2017) · Information Sciences · doi:10.1016/j.ins.2017.03.002 · Cited by 36
Steering the Craft: UI Elements and Visualizations for Supporting Progressive Visual Analytics
Badam, S. K., Elmqvist, N., & Fekete, J. (2017) · Computer Graphics Forum · doi:10.1111/cgf.13205 · Cited by 42
Fuger, S., Schimpf, R., Füller, J., & Hutter, K. (2017) · Information Technology for Development · doi:10.1080/02681102.2017.1353947 · Cited by 43
“For each possible case we conducted a k-means clustering analysis searching for the best cluster size, by considering the number of iterations needed to create each cluster solution (Lloyd’s algorithm) until convergence conditions are met (Kanungo et al., 2002).”
MethodUmapathy, S., Vasu, S., & Gupta, N. (2017) · Journal of Medical and Biological Engineering · doi:10.1007/s40846-017-0338-x · Cited by 36
Zhou, T., Ishibuchi, H., & Wang, S. (2017) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2017.2761915 · Cited by 36
“[16], [22], FCM and its variants [17], [18], Gath-Geva [19], Gustafson-Kessel [20] and so on.”
BackgroundRobust Reflection Removal Based on Light Field Imaging
Li, T., Lun, D. P.-K., Chan, Y., & Budianto (2018) · IEEE Transactions on Image Processing · doi:10.1109/tip.2018.2880510 · Cited by 39
Hassanzadeh-Nazarabadi, Y., Küpçü, A., & Özkasap, Ö. (2019) · IEEE Transactions on Parallel and Distributed Systems · doi:10.1109/tpds.2019.2960018 · Cited by 36
“In our implementation of the cluster-based replication, the data owner performs an r-mean clustering [46] of the nodes based on their piggy-”
MethodART: group recommendation approaches for automatically detected groups
Boratto, L., & Carta, S. (2015) · International Journal of Machine Learning and Cybernetics · doi:10.1007/s13042-015-0371-4 · Cited by 38
“The clusterings with k-means were created by the KMlocal [23] program, which contains a variant of the k-means algorithm, called EZ Hybrid.”
MethodA Cheap Feature Selection Approach for the K -Means Algorithm
Capó, M., Pérez, A., & Lozano, J. A. (2020) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2020.3002576 · Cited by 36
“INTRODUCTION Cluster analysis is an essential task for analyzing the evergrowing quantity of high dimensional data from different areas, such as artificial intelligence and pattern recognition [1]–[3].”
BackgroundEfficient Liver Segmentation from Computed Tomography Images Using Deep Learning
Ahmad, M., Qadri, S. F., Ashraf, M. U., Subhi, K., Khan, S., Zareen, S. S., & Qadri, S. (2022) · Computational Intelligence and Neuroscience · doi:10.1155/2022/2665283 · Cited by 37
“In the first step, a modified K-mean algorithm [54] is used to divide the slice into five pieces from the CT image that is liver, peripheral muscles, surrounding organs, ribs, and outside of the body.”
MethodRetractedRodríguez, P. C., Martí-Puig, P., Caiafa, C. F., Serra-Serra, M., Cusidó, J., & Solé‐Casals, J. (2023) · Machines · doi:10.3390/machines11020270 · Cited by 36
The Application of Artificial Intelligence in Alzheimer's Research
Zhao, Q., Xu, H., Li, J., Akhtar, F., & Qiao, L. (2023) · Tsinghua Science & Technology · doi:10.26599/tst.2023.9010037 · Cited by 42
Real-time K-Means Clustering for Color Images on Reconfigurable Hardware
Maruyama, T. (2006) · Proceedings - International Conference on Pattern Recognition/Proceedings/International Conference on Pattern Recognition · doi:10.1109/icpr.2006.961 · Cited by 36
“Figure 3 shows the outline of the filtering algorithm [ 4 ].”
MethodInfluentialBoratto, L., Carta, S., & Fenu, G. (2016) · Information Sciences · doi:10.1016/j.ins.2016.07.060 · Cited by 37
“The clusterings with k-means were created by using a testbed program called KMlocal [25].”
MethodPathak, S., & Kumar, B. (2016) · Electronics · doi:10.3390/electronics5030057 · Cited by 36
“Later an individual mean value of these three cases, as per the doctor’s opinion, were found using K-Means clustering technique [19].”
MethodTopaloglu, R. O. (2016) · doi:10.1145/2966986.2980073 · Cited by 36
“[16] implement a k-means based clustering algorithm.”
Pore structure of mortars with cellulose ether additions – Study of the air-void structure
Wyrzykowski, M., Kiesewetter, R., Münch, B., Baumann, R., & Lura, P. (2015) · Cement and Concrete Composites · doi:10.1016/j.cemconcomp.2015.04.016 · Cited by 36
Person Re-Identification With Hierarchical Discriminative Spatial Aggregation
Zhang, M., Xiao, Y., Xiong, F., Li, S., Cao, Z., Fang, Z., & Zhou, J. T. (2022) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2022.3146773 · Cited by 37
Goryawala, M., Güleç, S., Bhatt, R., McGoron, A. J., & Adjouadi, M. (2014) · BioMed Research International · doi:10.1155/2014/198015 · Cited by 43
New Efficient Strategy to Accelerate k-Means Clustering Algorithm
Al-Zoubi, M. B., Hudaib, A. A., Huneiti, A., & HAMMO, B. H. (2008) · American Journal of Applied Sciences · doi:10.3844/ajassp.2008.1247.1250 · Cited by 35
“In addition, the number of distance calculations increases exponentially with the increase of the dimensionality of the data [5-7] .”
BackgroundMethodContext-aware stream processing for distributed IoT applications
Akbar, A., Carrez, F., Moessner, K., Sancho, J., & Rico, J. (2015) · IEEE World Forum on Internet of Things (WF-IoT) · doi:10.1109/wf-iot.2015.7389133 · Cited by 35
“We have implemented k-means clustering algorithm which is an iterative algorithm which forms the clusters by finding centroids such that the sum of the squares of distance from centroids to data is minimized [17].”
MethodAwad, M., & Qasrawi, I. (2016) · Neural Computing and Applications · doi:10.1007/s00521-016-2779-5 · Cited by 35
“placed in an intelligent way because a different location causes a different result, and then it takes each point related to a given data set and associates it to the nearest centroid [24, 25].”
BackgroundAn iterated greedy heuristic for a market segmentation problem with multiple attributes
Huerta‐Muñoz, D. L., Ríos‐Mercado, R. Z., & Ruíz, R. (2017) · European Journal of Operational Research · doi:10.1016/j.ejor.2017.02.013 · Cited by 35
“A new improvement to consider is the one proposed by Kanungo et al. (2002); Likas et al. (2003); Z̆alik (2008).”
BackgroundPhan, T. V., Bao, N. K., & Park, M. (2017) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2017.04.016 · Cited by 35
Enhancing Mastcam Images for Mars Rover Mission
Dao, M., Kwan, C., Ayhan, B., & Bell, J. F., III (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-59081-3_24 · Cited by 35
Mulia, I. E., Inazu, D., Waseda, T., & Gusman, A. R. (2017) · Journal of Geophysical Research Oceans · doi:10.1002/2017jc012695 · Cited by 35
Parallel Tracking and Verifying
Fan, H., & Ling, H. (2019) · IEEE Transactions on Image Processing · doi:10.1109/tip.2019.2904789 · Cited by 37
“Afterwards, k-means clustering [59] is applied on Sd to obtain new clusters”
MethodDevelopment of smart data analytics tools to support wastewater treatment plant operation
Chow, C. W. K., Liu, J., Li, J., Swain, N., Reid, K., & Saint, C. P. (2018) · Chemometrics and Intelligent Laboratory Systems · doi:10.1016/j.chemolab.2018.03.006 · Cited by 35
Intracluster Structured Low-Rank Matrix Analysis Method for Hyperspectral Denoising
Wei, W., Zhang, L., Jiao, Y., Tian, C., Wang, C., & Zhang, Y. (2018) · IEEE Transactions on Geoscience and Remote Sensing · doi:10.1109/tgrs.2018.2862384 · Cited by 36
When to Learn What: Deep Cognitive Subspace Clustering
Jiang, Y., Yang, Z., Xu, Q., Cao, X., & Huang, Q. (2018) · ACM International Conference on Multimedia (ACM MM) · doi:10.1145/3240508.3240582 · Cited by 35
“These eigenvectors are fed into a k-means algorithm [17] to derive the final group labels”
MethodWu, T., Yang, L., Zhou, J. H., Lai, D. C., & Zhong, N. (2019) · Computers and Electronics in Agriculture · doi:10.1016/j.compag.2019.01.039 · Cited by 35
Nonhomogeneous Noise Removal From Side-Scan Sonar Images Using Structural Sparsity
Jin, Y., Ku, B., Ahn, J., Kim, S., & Ko, H. (2019) · IEEE Geoscience and Remote Sensing Letters · doi:10.1109/lgrs.2019.2895843 · Cited by 35
“The patches are clustered into K clusters using K-means [10] with covariance matrix descriptors (9).”
MethodTraffic Engineering With Three-Segments Routing
Pereira, V., Rocha, M., & Sousa, P. (2020) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2020.2993207 · Cited by 35
“first alternative, dividing a set M of TMs into two clusters using K-means [41] clustering algorithm (k = 2), and the traffic matrices Di , i = 1, 2, are the cluster’s centroids.”
MethodPrzybył, K., Gawałek, J., & Koszela, K. (2020) · Journal of Food Science and Technology · doi:10.1007/s13197-020-04537-9 · Cited by 35
“Above all, it includes learning algorithms such as the fastest neighbor method, conjugate gradient method, Broyden–Fletcher–Goldfarb– Shanno (BFGS) method, Kohonen method, used for example in forming clusters and visualization of relations and k-means method for RBF networks (Kanungo et al. 2002).”
Campano, C., Lopez-Exposito, P., González‐Aguilera, L., Blanco, Á., & Negro, C. (2020) · Carbohydrate Polymers · doi:10.1016/j.carbpol.2020.117271 · Cited by 35
Zhou, C., Gu, Y., Fang, G., & Lin, Z. (2022) · The Astronomical Journal · doi:10.3847/1538-3881/ac4245 · Cited by 35
Multiview Deep Graph Infomax to Achieve Unsupervised Graph Embedding
Zhou, Z., Hu, Y., Zhang, Y., Chen, J., & Cai, H. (2022) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2022.3163721 · Cited by 38
“After extracting the node representations, we feed them into the K-means algorithm, and the resulting ACC, NMI, and ARI are reported in Table IV.”
InfluentialBayesian Nonlocal Patch Tensor Factorization for Hyperspectral Image Super-Resolution
Ye, F., Wu, Z., Jia, X., Chanussot, J., Xu, Y., & Wei, Z. (2023) · IEEE Transactions on Image Processing · doi:10.1109/tip.2023.3326687 · Cited by 35
Sahu, L., & Mohan, B. R. (2014) · IEEE International Conference on Industrial and Information Systems (ICIIS) · doi:10.1109/iciinfs.2014.7036661 · Cited by 35
“K-means with Euclidean distance measure performs well up to moderately high dimension approximately 10 to 20 [6].”
MethodCOMPARATIVE STUDY OF K-MEANS AND K-MEANS++ CLUSTERING ALGORITHMS ON CRIME DOMAIN
Aubaidan, B. (2014) · Journal of Computer Science · doi:10.3844/jcssp.2014.1197.1206 · Cited by 35
“Many works have been proposed to improve the efficiency of the original k-means (Kanungo et al ., 2002; Jain and Dubes, 1988) defines that clus-ter analysis is the process of classifying objects into groups of similar objects based on a similarity/distance measure.”
BackgroundSpeeding up k-means by approximating Euclidean distances via block vectors
Bottesch, T., Bühler, T., & Kächele, M. (2016) · International Conference on Machine Learning · Cited by 35
Wang, D., Huang, W., Garcia, H. A., & Ratilal, P. (2016) · Remote Sensing · doi:10.3390/rs8110881 · Cited by 35
“A combination of extracted features from pitch-tracking, orthogonalized via Principle Component Analysis (PCA) [67], were used to optimize the vocalization species classification employing k-means [68] and Bayesian-based Gaussian mixture model clustering approaches [1].”
MethodRecommending Pick-up Points for Taxi-drivers Based on Spatio-temporal Clustering
Zhang, M., Liu, J., Liu, Y., Hu, Z., & Yi, L. Z. (2012) · International Conference on Cloud and Green Computing · doi:10.1109/cgc.2012.34 · Cited by 34
A Case for Work-stealing on FPGAs with OpenCL Atomics
Ramanathan, N., Wickerson, J., Winterstein, F., & Constantinides, G. A. (2016) · ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA) · doi:10.1145/2847263.2847343 · Cited by 34
“In this paper, we consider an efficient algorithm for KMC [11] that uses a kdtree data structure instead of working directly on the point set X.”
MethodA New Variational Method for Bias Correction and Its Applications to Rodent Brain Extraction
Chang, H., Huang, W., Wu, C., Huang, S., Guan, C., Sekar, S., Bhakoo, K. K., & Duan, Y. (2016) · IEEE Transactions on Medical Imaging · doi:10.1109/tmi.2016.2636026 · Cited by 34
“We adopt the k-means method [45] as an example for automatically computing the thresholds.”
MethodSMOPAT: Mining semantic mobility patterns from trajectories of private vehicles
Wan, C., Zhu, Y., Yu, J., & Shen, Y. (2017) · Information Sciences · doi:10.1016/j.ins.2017.10.043 · Cited by 34
Kwedlo, W., & Czochanski, P. J. (2019) · IEEE Access · doi:10.1109/access.2019.2907885 · Cited by 38
“The latter presents an implementation of the KD-tree based filtering algorithm [26] for low-dimensional data.”
BackgroundMethodKoren, O., Hallin, C. A., Perel, N., & Bendet, D. (2019) · Journal of Artificial Intelligence and Soft Computing Research · doi:10.2478/jaiscr-2019-0010 · Cited by 36
“Further studies on K-means can be found in [21] and in [17].”
BackgroundZheng, L., Dong, X., Chen, L., & Sun, D. (2019) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2019.2940724 · Cited by 34
“According to the model parameters, wmove, wcongest ion, wstay , all links were classified into three categories by K-MEANS algorithm [49].”
MethodAutomatic digital ECG signal extraction and normal QRS recognition from real scene ECG images
Wang, S., Zhang, S., Li, Z., Huang, L., & Wei, Z. (2019) · Computer Methods and Programs in Biomedicine · doi:10.1016/j.cmpb.2019.105254 · Cited by 34
Javadpour, A., Wang, G., Rezaei, S., & Li, K. (2020) · The Journal of Supercomputing · doi:10.1007/s11227-019-03136-6 · Cited by 34
RetractedHuang, Z., Lin, S., Long, L.-L., Cao, J., Luo, F., Qin, W., Sun, D., & Gregersen, H. N. (2020) · International Journal of Medical Informatics · doi:10.1016/j.ijmedinf.2020.104141 · Cited by 34
Wang, Y., & Gao, Z. (2020) · Continental Shelf Research · doi:10.1016/j.csr.2020.104173 · Cited by 36
KNN-SC: Novel Spectral Clustering Algorithm Using k-Nearest Neighbors
Kim, J.-H., Choi, J.-H., Park, Y., Leung, C. K.-S., & Nasridinov, A. (2021) · IEEE Access · doi:10.1109/access.2021.3126854 · Cited by 34
“Finally, the existing clustering algorithms (e.g., k -means [20]), are applied to the spectral embedding set 𝐻 to discover the final clusters.”
MethodCohort-based federated learning services for industrial collaboration on the edge
Hießl, T., Lakani, S. R., Kemnitz, J., Schall, D., & Schulte, S. (2022) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2022.04.021 · Cited by 35
Spanning Tree Method for Over-the-Air Channel Calibration in 6G Cell-Free Massive MIMO
Xu, S., Cao, Y., Li, C., Wang, D., & Yang, L. (2023) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2023.3235355 · Cited by 34
“Specifically, grouped LS method is referred to [17], where we use K-means algorithm [35] to partition all APs into two clusters based on their distance information.”
MethodContinuous occupancy maps using overlapping local Gaussian processes
Kim, S., & Kim, J. (2013) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2013.6697034 · Cited by 34
“Instead, we first divide hit points with the k-means clustering [22] and then assign line segments to the clusters including corresponding hit points.”
MethodAutomated assembly of shredded pieces from multiple photos
Cao, S., Liu, H., & Yan, S. (2010) · IEEE International Conference on Multimedia and Expo (ICME) · doi:10.1109/icme.2010.5582544 · Cited by 34
“Then the k-means method [24] can well separate these clusters, with each cluster corresponding to a true photo.”
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.