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 701–800 of 1,008
A review on deep learning techniques for cloud detection methodologies and challenges
Li, L., Li, X., Jiang, L., Su, X., & Chen, F. (2021) · Signal Image and Video Processing · doi:10.1007/s11760-021-01885-7 · Cited by 52
Learning from Miscellaneous Other-Class Words for Few-shot Named Entity Recognition
Tong, M., Wang, S., Xu, B., Cao, Y., Liu, M., Hou, L., & Li, J. (2021) · doi:10.18653/v1/2021.acl-long.487 · Cited by 48
“WS detects undefined classes by performing KMeans (Kanungo et al., 2002) in O words based on word similarity.”
MethodNguyen, M. D., Le, L. B., & Girard, A. (2023) · IEEE Transactions on Cloud Computing · doi:10.1109/tcc.2023.3339394 · Cited by 56
K-Means clustering technique applied to availability of micro hydro power
Adhau, S. P., Moharil, R. M., & Adhau, P. G. (2014) · Sustainable Energy Technologies and Assessments · doi:10.1016/j.seta.2014.09.001 · Cited by 48
Ihesiulor, O. K., Shankar, K., Zhang, Z., & Ray, T. (2013) · Composites Part B Engineering · doi:10.1016/j.compositesb.2013.09.032 · Cited by 48
Inter-context control-flow and data-flow test adequacy criteria for nesC applications
Lai, Z., Cheung, S.-C., & Chan, W. K. (2008) · ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE) · doi:10.1145/1453101.1453115 · Cited by 48
“To study the average fault-detection rate of each criterion with respect to different faulty versions, we used the k-means clustering algorithm [18] to partition the faults into three categories.”
MethodImage stylization by interactive oil paint filtering
Semmo, A., Limberger, D., Kyprianidis, J. E., & Döllner, J. (2016) · Computers & Graphics · doi:10.1016/j.cag.2015.12.001 · Cited by 48
A Data Analytic Approach to Automatic Fault Diagnosis and Prognosis for Distribution Automation
Wang, X., McArthur, S. D. J., Strachan, S. M., Kirkwood, J. D., & Paisley, B. (2017) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2017.2707107 · Cited by 48
Zhao, P., Wu, H., Gu, C., & Hernando‐Gil, I. (2019) · IET Renewable Power Generation · doi:10.1049/iet-rpg.2018.6169 · Cited by 48
Han, G., Wu, J., Wang, H., Guizani, M., Ansere, J. A., & Zhang, W. (2019) · IEEE Internet of Things Journal · doi:10.1109/jiot.2019.2928557 · Cited by 48
“Compared with k-means algorithm [30], [31], the mean-shift algorithm does not need to specify the number of categories k in advance and can distinguish the high-density region of node distribution.”
A novel clustering technique for efficient clustering of big data in Hadoop Ecosystem
Kumar, S., & Singh, M. (2019) · Big Data Mining and Analytics · doi:10.26599/bdma.2018.9020037 · Cited by 53
“Every cluster has a centroid, or cluster representative, from which the distance of all data points is measured and data points at the minimum distance from the centroid are kept under one cluster[15, 16].”
BackgroundZhang, C., Wang, Z., Ding, K., Chan, F. T. S., & Ji, W. (2020) · International Journal of Production Research · doi:10.1080/00207543.2020.1748904 · Cited by 50
Zhu, S., Hu, X., Huang, K., & Yuan, Y. (2020) · European Journal of Operational Research · doi:10.1016/j.ejor.2020.08.024 · Cited by 48
Identification of concrete aggregates using K-means clustering and level set method
Chen, L., Shan, W., & Liu, P. Z. (2021) · Structures · doi:10.1016/j.istruc.2021.08.048 · Cited by 48
Dynamic portfolio optimization with inverse covariance clustering
Wang, Y., & Aste, T. (2022) · Expert Systems with Applications · doi:10.1016/j.eswa.2022.118739 · Cited by 54
Clustering and selecting suppliers based on simulated annealing algorithms
Che, Z. H. (2011) · Computers & Mathematics with Applications · doi:10.1016/j.camwa.2011.11.014 · Cited by 48
Metaheuristic Algorithms Applied to Color Image Segmentation on HSV Space
Giuliani, D. (2022) · Journal of Imaging · doi:10.3390/jimaging8010006 · Cited by 47
“In partitional clustering, segmentation is carried out by partitioning the data into a defined number of clusters; K-means and Fuzzy C-Means algorithms belong to this class [10,11].”
MethodLiu, Y., Pan, H., Sun, G., Wang, A., Li, J., & Liang, S. (2021) · IEEE Internet of Things Journal · doi:10.1109/jiot.2021.3132015 · Cited by 47
“The main steps of the K-means operator are described in [57].”
MethodHeterformer: Transformer-based Deep Node Representation Learning on Heterogeneous Text-Rich Networks
Jin, B., Zhang, Y., Zhu, Q., & Han, J. (2023) · ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD) · doi:10.1145/3580305.3599376 · Cited by 69
“For node clustering, we utilize KMeans [19] to cluster the nodes based on their representations generated by the models.”
MethodA graph-based approach to developing adaptive representations of complex reaction mechanisms
He, K., Ierapetritou, M., & Androulakis, I. P. (2008) · Combustion and Flame · doi:10.1016/j.combustflame.2008.05.004 · Cited by 47
Coding-Aided K-Means Clustering Blind Transceiver for Space Shift Keying MIMO Systems
Liang, H.-W., Chung, W., & Kuo, S. (2015) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2015.2467394 · Cited by 47
“In [26], a k-d tree is used to store the observations (samples); in [35], the divide-and-”
BackgroundMethodInternet traffic classification based on flows' statistical properties with machine learning
Vlăduţu, A., Comăneci, D., & Dobre, C. (2016) · International Journal of Network Management · doi:10.1002/nem.1929 · Cited by 49
Automatic fitting of conical envelopes to free-form surfaces for flank CNC machining
Bo, P., Bartoň, M., & Pottmann, H. (2017) · Computer-Aided Design · doi:10.1016/j.cad.2017.06.006 · Cited by 47
Garcia, H. A., Zhu, C., Schinault, M. E., Kaplan, A. I., Handegard, N. O., Godø, O. R., Ahonen, H., Makris, N. C., Wang, D., Huang, W., et al. (2018) · ICES Journal of Marine Science · doi:10.1093/icesjms/fsy127 · Cited by 47
“A combination of extracted features from pitch-tracking, orthogonalized via principle component analysis (PCA) (Jolliffe, 2002), were used to optimize the vocalization classification employing k-means (Kanungo et al., 2002) and Bayesian-based Gaussian mixture model clustering approaches (Richard et al.”
MethodOmrani, H., Parmentier, B., Helbich, M., & Pijanowski, B. C. (2018) · Environmental Modelling & Software · doi:10.1016/j.envsoft.2018.10.004 · Cited by 48
Wang, Z., Zhou, Q., & Shuang, Y. (2019) · Measurement · doi:10.1016/j.measurement.2019.107114 · Cited by 47
Zhang, S., & Liu, Y. (2020) · Structural Health Monitoring · doi:10.1177/1475921719895955 · Cited by 47
The k-means range algorithm for personalized data clustering in e-commerce
Papamichail, G. P., & Papamichail, D. P. (2005) · European Journal of Operational Research · doi:10.1016/j.ejor.2005.04.011 · Cited by 52
Pramod, C. P., & Pillai, G. N. (2021) · Knowledge-Based Systems · doi:10.1016/j.knosys.2021.106750 · Cited by 46
Clustering: Hierarchical, k-Means, DBSCAN
Fuchs, M., & Höpken, W. (2022) · Tourism on the verge · doi:10.1007/978-3-030-88389-8_8 · Cited by 61
Wang, Y., Sun, W., Jin, J., Kong, Z., & Yue, X. (2022) · Journal of Manufacturing Science and Engineering · doi:10.1115/1.4056005 · Cited by 51
Eigenvalues of Quaternion Tensors with Applications to Color Video Processing
He, Z., Wang, X., & Zhao, Y.-F. (2022) · Journal of Scientific Computing · doi:10.1007/s10915-022-02058-5 · Cited by 46
Khedairia, S., & Khadir, M. T. (2012) · Atmospheric Research · doi:10.1016/j.atmosres.2012.05.002 · Cited by 46
Context-Based Energy Disaggregation in Smart Homes
Paradiso, F., Paganelli, F., Giuli, D., & Capobianco, S. (2016) · Future Internet · doi:10.3390/fi8010004 · Cited by 50
“This type of technique usually fails in the general categories of clustering that are based on the variance [46].”
BackgroundSegmentation of melanocytic skin lesions using feature learning and dictionaries
Flores, E. S., & Scharcanski, J. (2016) · Expert Systems with Applications · doi:10.1016/j.eswa.2016.02.044 · Cited by 50
Predicting the Outcome of NBA Playoffs Based on the Maximum Entropy Principle
Cheng, G., Zhang, Z., Kyebambe, M. N., & Kimbugwe, N. (2016) · Entropy · doi:10.3390/e18120450 · Cited by 46
“al [27] presented a simple and efficient implementation of K-means clustering algorithm and so on.”
MethodMorphological Neuron Classification Using Machine Learning
Vasques, X., Vanel, L., Villette, G., & Cif, L. (2016) · Frontiers in Neuroanatomy · doi:10.3389/fnana.2016.00102 · Cited by 52
A Machine Learning Based Framework for Verification and Validation of Massive Scale Image Data
Ding, J., Hu, X., & Gudivada, V. N. (2017) · IEEE Transactions on Big Data · doi:10.1109/tbdata.2017.2680460 · Cited by 50
“If an event is closer to a center c1 than the others, it is assigned to the cluster represented by the center c1 [25].”
BackgroundHuang, J. L., Ersoy, O. K., & Yan, X. (2018) · ISA Transactions · doi:10.1016/j.isatra.2018.10.016 · Cited by 46
Han, X., Xu, C., Xie, W., & Meng, S. (2019) · Composite Structures · doi:10.1016/j.compstruct.2019.03.053 · Cited by 46
Hossain, T. M., Watada, J., Aziz, I. A., & Hermana, M. (2020) · Applied Sciences · doi:10.3390/app10175940 · Cited by 47
“K-means clustering [40] is a distance-based clustering method for finding clusters and cluster centres in a set of unlabelled data.”
MethodYao, J., & Li, J. (2022) · Computers in Industry · doi:10.1016/j.compind.2021.103588 · Cited by 46
Introduction to Data Mining and Knowledge Discovery
Chakraborty, S., Islam, S. H., & Samanta, D. (2022) · EAI/Springer Innovations in Communication and Computing · doi:10.1007/978-3-030-93088-2_1 · Cited by 46
Frezza-Buet, H. (2008) · Neurocomputing · doi:10.1016/j.neucom.2007.12.024 · Cited by 46
“Some methods proceed minimization from a given finite set of examples, chosen from PX , and minimizes the distortion measured on this set [15,11].”
MethodMulti-target Unsupervised Domain Adaptation without Exactly Shared CategoriesPreprint
Yu, H., Hu, M.-L. M., & Chen, S. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1809.00852 · Cited by 52
“In detail, SLMC uses the encoding for the predefined C cluster labels, and acquires result by the decision function and the soft membership.”
BackgroundMethodInfluentialEnergy Storage Capacity Optimization for Improving the Autonomy of Grid-Connected Microgrid
Ma, G., Li, J., & Zhang, X. (2023) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2022.3233910 · Cited by 45
Cheng, Y., Zhang, W., Zhang, Z., Kang, J., Xu, Q. M., Wang, S., & Niyato, D. T. (2025) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2025.3529487 · Cited by 45
Filipczuk, P., Kowal, M., & Obuchowicz, A. (2011) · Advances in intelligent and soft computing · doi:10.1007/978-3-642-23154-4_33 · Cited by 48
“responsible for. Detailed expressions for iterative updating the cluster centers and pixel assignments can be found in the following papers [ 11 , 13, 14].”
BackgroundThe MEI Robot: Towards Using Motherese to Develop Multimodal Emotional Intelligence
Lim, A., & Okuno, H. G. (2014) · IEEE Transactions on Autonomous Mental Development · doi:10.1109/tamd.2014.2317513 · Cited by 53
“We therefore describe here a developmental robot system with the goal of: 1) advancing computational models of emotion in both developmental psychology and autonomous robotics; and 2) using infant development as a clue to develop a robot with a powerful emotion system.”
MethodNo NAT'd User Left Behind: Fingerprinting Users behind NAT from NetFlow Records Alone
Verde, N. V., Ateniese, G., Gabrielli, E., Mancini, L. V., & Spognardi, A. (2014) · IEEE International Conference on Distributed Computing Systems (ICDCS) · doi:10.1109/icdcs.2014.30 · Cited by 45
Tracking and counting vehicles in traffic video sequences using particle filtering
Bouvié, C., Scharcanski, J., Barcellos, P., & Escouto, F. L. (2013) · IEEE International Instrumentation and Measurement Technology Conference · doi:10.1109/i2mtc.2013.6555527 · Cited by 49
“This paper aims at providing an alternative method, using simple and familiar clustering techniques of such as k-means [2] and particle filtering, and features like the Harris corners [3].”
MethodA Parallel Clustering Algorithm with MPI – MKmeans
Zhang, J., Wu, G., Hu, X., Li, S., & Hao, S. (2013) · Journal of Computers · doi:10.4304/jcp.8.1.10-17 · Cited by 45
“• Communication contexts • Process topologies • Bindings for FORTRAN 77 and C • Environmental management and inquiry • Profiling interface”
BackgroundHard versus fuzzy c-means clustering for color quantization
Wen, Q., & Celebi, M. E. (2011) · EURASIP Journal on Advances in Signal Processing · doi:10.1186/1687-6180-2011-118 · Cited by 45
“This is because HCM uses hard memberships, which makes possible various computational optimizations that do not affect accuracy of the algorithm [51-55].”
Statistical Analysis and Predicting Kidney Diseases using Machine Learning Algorithms
Baby, P. S., & Terlapu, P. V. (2015) · International Journal of Engineering Research and · doi:10.17577/ijertv4is070234 · Cited by 45
“[10,13] Hence the value’s selected as random.”
An intelligent decision computing paradigm for crowd monitoring in the smart city
Kumar, S., Datta, D., Singh, S. K., & Sangaiah, A. K. (2018) · Journal of Parallel and Distributed Computing · doi:10.1016/j.jpdc.2017.03.002 · Cited by 43
“For the performance analysis, we use multi-label classification technique to validate the K-means clustering [44] [45] of the individual features (shown in Fig.”
MethodAn Effective Algorithm Based on Density Clustering Framework
Lu, J., & Zhu, Q. (2017) · IEEE Access · doi:10.1109/access.2017.2688477 · Cited by 45
“For example, partitioning-based clusteringmethod k-means [2] is fragile to noises because the noises make the mean value of the cluster change greatly.”
BackgroundAutomatic extractive text summarization using K-means clustering
Shetty, K., & Kallimani, J. S. (2017) · International Conference on Electrical, Electronics, Communication, Computer and Optimization Techniques (ICEECCOT) · doi:10.1109/iceeccot.2017.8284627 · Cited by 53
Hosoda, Y., Miyake, M., Yamashiro, K., Ooto, S., Takahashi, A., Oishi, A., Miyata, M., Uji, A., Muraoka, Y., & Tsujikawa, A. (2020) · Scientific Reports · doi:10.1038/s41598-020-75451-5 · Cited by 45
Dao, P. D., Mantripragada, K., He, Y., & Qureshi, F. Z. (2020) · ISPRS Journal of Photogrammetry and Remote Sensing · doi:10.1016/j.isprsjprs.2020.11.013 · Cited by 48
Underwater Docking Approach and Homing to Enable Persistent Operation
Page, B. R., Lambert, R., Chavez‐Galaviz, J., & Mahmoudian, N. (2021) · Frontiers in Robotics and AI · doi:10.3389/frobt.2021.621755 · Cited by 45
“More advanced processing algorithms have been attempted including a k-means tracker (Kanungo et al., 2002), Hough circularity transform (Yuen et al.”
MethodFarrahi, V., Kangas, M., Kiviniemi, A. M., Puukka, K. S., Korpelainen, R., & Jämsä, T. J. (2021) · Scandinavian Journal of Medicine and Science in Sports · doi:10.1111/sms.13958 · Cited by 45
Bandwidth Adaptive Hardware Architecture of K-Means Clustering for Video Analysis
Chen, T.-W., & Chien, S. (2009) · IEEE Transactions on Very Large Scale Integration (VLSI) Systems · doi:10.1109/tvlsi.2009.2017543 · Cited by 45
“Many issues of K-Means, including the initialization of cluster centroids [9], acceleration of speed [10], evaluation of the cluster number [11]–[13], search of the globally optimal partition [14], are explored.”
Boosting topic-based publish-subscribe systems with dynamic clustering
Milo, T., Zur, T., & Verbin, E. (2007) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/1247480.1247563 · Cited by 45
“Surprisingly, although K-means operates in a centralized manner and can utilize full knowledge about the network state, it nevertheless achieves less good OC cost than Tamara.”
MethodInfluentialSungheetha, A., & Rajesh Sharma, R. (2020) · Journal of Soft Computing Paradigm · doi:10.36548/jscp.2020.2.004 · Cited by 44
On the efficiency of K-means clustering: evaluation, optimization, and algorithm selection
Wang, S., Sun, Y., & Bao, Z. (2020) · Proceedings of the VLDB Endowment · doi:10.14778/3425879.3425887 · Cited by 44
“Most of the existing acceleration methods focus on how to reduce intensive distance computations, which can be broadly divided into two categories: 1) the index-based methods that group and prune points in batch [27, 45, 51, 58], and 2) the”
MethodResultInfluentialEvent Camera Based Real-Time Detection and Tracking of Indoor Ground Robots
Iaboni, C., Patel, H. J., Lobo, D., Choi, J.-W., & Abichandani, P. (2021) · IEEE Access · doi:10.1109/access.2021.3133533 · Cited by 50
“K-Means and Agglomerative algorithms cannot process an unknown and dynamic number of clusters [83].”
BackgroundAutomatic iterative algorithm for image segmentation using a modified pulse-coupled neural network
Gao, C., Zhou, D., & Guo, Y. (2013) · Neurocomputing · doi:10.1016/j.neucom.2013.03.025 · Cited by 44
Liu, Y.-S., Ramani, K., & Liu, M. (2011) · IEEE Transactions on Pattern Analysis and Machine Intelligence · doi:10.1109/tpami.2011.116 · Cited by 44
Using acetowhite opacity index for detecting cervical intraepithelial neoplasia
Li, W., Venkataraman, S., Gustafsson, U. P., Oyama, J., Ferris, D. G., & Lieberman, R. W. (2009) · Journal of Biomedical Optics · doi:10.1117/1.3079810 · Cited by 44
Godoi, V. A., Bryan, K. R., & Gorman, R. M. (2016) · Journal of Geophysical Research Oceans · doi:10.1002/2015jc011572 · Cited by 45
Improved characterization of multi-stage voltage dips based on the space phasor model
Bagheri, A., Bollen, M., & Gu, I. Y. (2017) · Electric Power Systems Research · doi:10.1016/j.epsr.2017.09.004 · Cited by 44
A multiscale shear-transformation-zone (STZ) model and simulation of plasticity in amorphous solids
Urata, S., & Li, S. (2018) · Acta Materialia · doi:10.1016/j.actamat.2018.05.058 · Cited by 44
Operation strategy of a hybrid solar and biomass power plant in the electricity markets
Wang, Y., Lou, S., Wu, Y., Miao, M., & Wang, S. (2018) · Electric Power Systems Research · doi:10.1016/j.epsr.2018.10.035 · Cited by 44
Automatic and fast segmentation of breast region-of-interest (ROI) and density in MRIs
Pandey, D. B., Yin, X., Wang, H., Su, M., Chen, J., Wu, J., & Zhang, Y. (2018) · Heliyon · doi:10.1016/j.heliyon.2018.e01042 · Cited by 44
“During BROI segmentation, first, we aim to de-noise the MR image and precisely remove air-background using pixelwise adaptive wiener filtering (PAWF) technique [38, 39] and k-means clustering [40].”
MethodMachine Learning Tips and Tricks for Power Line Communications
Tonello, A. M., Letizia, N. A., Righini, D., & Marcuzzi, F. (2019) · IEEE Access · doi:10.1109/access.2019.2923321 · Cited by 48
Insights into the polymorphism in HLA‐DRA and its evolutionary relationship with HLA haplotypes
Matern, B. M., Olieslagers, T. I., Voorter, C. E. M., Groeneweg, M., & Tilanus, M. G. J. (2019) · HLA · doi:10.1111/tan.13730 · Cited by 49
Viewpoint-Aware Progressive Clustering for Unsupervised Vehicle Re-Identification
Zheng, A., Sun, X., Li, C., & Tang, J. (2021) · IEEE Transactions on Intelligent Transportation Systems · doi:10.1109/tits.2021.3103961 · Cited by 47
Self-Sorting Map: An Efficient Algorithm for Presenting Multimedia Data in Structured Layouts
Strong, G., & Gong, M. (2014) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2014.2306183 · Cited by 44
“Careful readers may notice the similarity between the above iterative process and the k-means clustering algorithm [15].”
BackgroundSpatial heterogeneity of edema region uncovers survival-relevant habitat of Glioblastoma
Yang, Y., Han, Y., Zhao, S., Xiao, G., Guo, L., Zhang, X., & Cui, G. (2022) · European Journal of Radiology · doi:10.1016/j.ejrad.2022.110423 · Cited by 45
Machine Learning on Fault Diagnosis in Wind Turbines
Ng, E. Y. K., & Lim, J. T. (2022) · Fluids · doi:10.3390/fluids7120371 · Cited by 43
An Empirical Case of a Context-Aware Mobile Recommender System in a Banking Environment
Gallego, D., & Huecas, G. (2012) · FTRA International Conference on Mobile, Ubiquitous, and Intelligent Computing (MUSIC) · doi:10.1109/music.2012.11 · Cited by 43
“It also summarizes the flow of the data involved in the recommendation process in 5 steps that are going to be explained in the following subsections.”
BackgroundLanouette, S., Davey, J. A., Elisma, F., Ning, Z., Figeys, D., Chica, R. A., & Couture, J. (2014) · Structure · doi:10.1016/j.str.2014.11.004 · Cited by 43
“Substitution fitness was computed as the Boltzmann weighted average of scores across the 180members of the PertMin ensemble at 300 K and these fitness values were clustered using the k-means theorem (Kanungo et al., 2002).”
MethodThesaurus-based 3D Object Retrieval with Part-in-Whole Matching
Ferreira, A., Marini, S., Attene, M., Fonseca, M. J., Spagnuolo, M., Jorge, J. A., & Falcidieno, B. (2009) · International Journal of Computer Vision · doi:10.1007/s11263-009-0257-6 · Cited by 43
“Therefore, in our approach we used a k-means clustering algorithm based on a combination of local search and Lloyd's algorithm (Lloyd 1982) proposed by Kanungo et al. (2002).”
Automatic knowledge extraction of any Chatbot from conversation
Arsovski, S., Osipyan, H., Muniru, I. O., & Cheok, A. D. (2019) · Expert Systems with Applications · doi:10.1016/j.eswa.2019.07.014 · Cited by 43
A Survey on Representation Learning Efforts in Cybersecurity Domain
Usman, M., Jan, M. A., He, X., & Chen, J. (2019) · ACM Computing Surveys · doi:10.1145/3331174 · Cited by 50
DIC: Deep Image Clustering for Unsupervised Image Segmentation
Zhou, L., & Wei, W. (2020) · IEEE Access · doi:10.1109/access.2020.2974496 · Cited by 43
“The unsupervised methods, such as K-means [1], EM [2], FH segmentation [3], Active contour [4], normalized cut [5], meanshift clustering [6], MLSS [7] or SAS [8], are implemented without prior knowledge about the images.”
MethodReview of online source apportionment research based on observation for ambient particulate matter
Wang, F., Yu, H., Wang, Z., Liang, W., Shi, G., Gao, J. G., Li, M., & Feng, Y. (2020) · The Science of The Total Environment · doi:10.1016/j.scitotenv.2020.144095 · Cited by 43
Detecting and tracking regional outliers in meteorological data
Lu, C., Kou, Y., Zhao, J., & Chen, L. (2006) · Information Sciences · doi:10.1016/j.ins.2006.09.013 · Cited by 43
“Their algorithm has the time complexity of at least O(n log n) since a kd-tree is required [23].”
BackgroundAutomated encoding of footwear patterns for fast indexing
Pavlou, M., & Allinson, N. M. (2008) · Image and Vision Computing · doi:10.1016/j.imavis.2008.06.003 · Cited by 43
Kline, J. A., Novobilski, A. J., Kabrhel, C., Richman, P. B., & Courtney, D. M. (2005) · Annals of Emergency Medicine · doi:10.1016/j.annemergmed.2004.08.036 · Cited by 43
Plaku, E., Stamati, H., Clementi, C., & Kavraki, L. E. (2007) · Proteins: Structure, Function, and Bioinformatics · doi:10.1002/prot.21337 · Cited by 43
A Rule Based Technique for Extraction of Visual Attention Regions Based on Real-Time Clustering
Yu, Z., & Wong, H. (2007) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2007.893351 · Cited by 46
“RTCA is a variant of the K-means algorithm [21]–[23], in a low dimensional space, and its objective is to reduce the number of iterations and distance computational cost in K-means.”
MethodImproving Quality-of-Service in Cluster-Based UAV-Assisted Edge Networks
Bose, T., Aala, S., Pandey, O. J., Cenkeramaddi, L. R., & Hegde, R. M. (2022) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2021.3139892 · Cited by 42
Assaf, G., & Assaad, R. H. (2023) · Journal of Infrastructure Systems · doi:10.1061/jitse4.iseng-2225 · Cited by 42
Automated Assembly of Shredded Pieces From Multiple Photos
Liu, H., Cao, S., & Yan, S. (2011) · IEEE Transactions on Multimedia · doi:10.1109/tmm.2011.2160845 · Cited by 42
“Then the k-means method [ 24 ] can well separate these clusters, with each clustercorrespondingtoatruephoto.Whentheverticesforeach subgraph are fixed, we can reconstruct the photo for this particular multi-edge subgraph.”
MethodAccurate lithography hotspot detection based on PCA-SVM classifier with hierarchical data clustering
Gao, J.-R., Yu, B., & Pan, D. Z. (2014) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.2045888 · Cited by 42
“The imbalance between hotspot and non-hotspot data is called imbalanced populations, which critically affect the success of SVM learning.(19) In addition, since we decompose the layout patterns as fragments and represent them by FV s, the size of the training data increases rapidly.”
BackgroundIn-Camera Automation of Photographic Composition Rules
Banerjee, S., & Evans, B. L. (2007) · IEEE Transactions on Image Processing · doi:10.1109/tip.2007.898992 · Cited by 42
“Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org.”
BackgroundAnalysis and Visualization of Seismic Data Using Mutual Information
Machado, J. A. T., & Lopes, A. M. (2013) · Entropy · doi:10.3390/e15093892 · Cited by 42
“Among others [53] Lloyd’s algorithm, described in the sequel, is one of the most popular.”
Effectual recommendations using artificial algae algorithm and fuzzy c-mean
Katarya, R., & Verma, O. P. (2017) · Swarm and Evolutionary Computation · doi:10.1016/j.swevo.2017.04.004 · Cited by 42
A new kernel method for hyperspectral image feature extraction
Zhao, B. C., Gao, L., Liao, W., & Zhang, B. (2017) · Geo-spatial Information Science · doi:10.1080/10095020.2017.1403088 · Cited by 42
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.