Theoretical Analysis of the $k$-Means Algorithm - A Survey

The k-means algorithm is one of the most widely used clustering heuristics. Despite its simplicity, analyzing its running time and quality of approximation is surprisingly difficult and can lead to deep insights that can be used to improve the algorithm. In this paper we survey the recent results in this direction as well as several extension of the basic k-means method.

cs.DS cs.LG Computer Science Mathematics

View graph Source

Paper

Similar papers

The k-means Algorithm: A Comprehensive Survey and Performance EvaluationMohiuddin Ahmed, Raihan Seraj, Syed Mohammed Shamsul Islam2020 · Electronics · 1.6k citations In Library

The K-Means Algorithm EvolutionJ. Pérez-Ortega, N. N. Almanza-Ortega, Andrea Vega-Villalobos et al.2019 · Introduction to Data Science and Machine Learning · 60 citations In Library

Asymptotics for The $k$-meansTonglin Zhang2022 · arXiv (Cornell University) In Library

Computational Improvements to the Kernel k$$ k $$‐Means Clustering AlgorithmJoshua D. Berlinski, Ranjan Maitra2025 · Statistical Analysis and Data Mining The ASA Data Science Journal · 1 citation In Library

K-means clustering algorithm: a brief review<p>Bao Chong</p>2021 · Academic Journal of Computing & Information Science · 88 citations In Library

The Systematic Review of K-Means Clustering AlgorithmArdavan Ashabi, Shamsul Sahibuddin, Mehdi Salkhordeh Haghighi2020 · International Conference on Network, Communication and Computing · 64 citations In Library

A Geometric Approach to $k$-meansJia-Yu Hong, Wei Qian, Yudong Chen et al.2022 · IEEE Transactions on Knowledge and Data Engineering · 3 citations In Library

Fast k-means algorithm clusteringR. Salman, V. Kecman, Qi Li et al.2011 · arXiv.org · 25 citations In Library

An Improvement in K-mean Clustering Algorithm Using Better Time and AccuracyN. Chaturvedi, A. Rajavat2013 · 15 citations In Library

An Improvement in K-mean Clustering Algorithm Using Better Time and AccuracyEr. Nikhil Chaturvedi, Er. Anand Rajavat2021 · Zenodo (CERN European Organization for Nuclear Research) In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal