How the initialization affects the stability of the k-means algorithm

2009/07/31 by Sébastien Bubeck, Marina Meilă, Bubeck, Sebastien +3 · 1 citation
Computer Science · #Advanced Clustering Algorithms Research #Bayesian Methods and Mixture Models #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning (stat.ML)

paper · pdf · doi:10.48550/arxiv.0907.5494

openalex publication_date 2009/07/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We investigate the role of the initialization for the stability of the k-means clustering algorithm. As opposed to other papers, we consider the actual k-means algorithm and do not ignore its property of getting stuck in local optima. We are interested in the actual clustering, not only in the costs of the solution. We analyze when different initializations lead to the same local optimum, and when they lead to different local optima. This enables us to prove that it is reasonable to select the number of clusters based on stability scores.

Cited by

• Silhouette-Driven Instance-Weighted k-means

Related

• Linear, Deterministic, and Order-Invariant Initialization Methods for the K-Means Clustering Algorithm
• Theoretical Analysis of the k-Means Algorithm - A Survey
• Adaptive Initialization Method for K-means Algorithm
• Clustering under Local Stability: Bridging the Gap between Worst-Case and Beyond Worst-Case Analysis
• On the Local Structure of Stable Clustering Instances