Skip to content

An efficient k-means clustering algorithm: analysis and implementation

Tapas Kanungo, David M. Mount, Nathan S. Netanyahu, Christine Piatko, Ruth Silverman, Angela Y. Wu

IEEE Transactions on Pattern Analysis and Machine Intelligence · 2002 · 5,752 citations

No retraction on record in OpenAlex.Check Crossref now

Cite this paper

Kanungo, T., Mount, D. M., Netanyahu, N. S., Piatko, C., Silverman, R., & Wu, A. Y. (2002). An efficient k-means clustering algorithm: analysis and implementation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24(7), 881–892. https://doi.org/10.1109/tpami.2002.1017616

In text: (Kanungo et al., 2002)

Ask a question about this research

One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.

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.

  1. Regression Shrinkage and Selection Via the Lasso1996
  2. Maximum Likelihood from Incomplete Data Via the EM Algorithm1977
  3. Latent dirichlet allocation2003
  4. A tutorial on hidden Markov models and selected applications in speech recognition1989
  5. Statistical Analysis With Missing Data1989

Metadata from OpenAlex (CC0). Citations are generated from the published record.