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

We investigate the role of the initialization for the stability of the қ-means clustering algorithm. As opposed to other papers, we consider the actual қ-means algorithm (also known as Lloyd algorithm). In particular we leverage on the property that this algorithm can get stuck in local optima of the қ-means objective function. 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.

• Publication year

  2009

• Venue

  Esaim: Probability and Statistics

• Publication date

  2009-07-31

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1051/ps/2012013arXiv 0907.5494
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Stability-based Validation of Clustering

  2009cited by this paper
• Relating Clustering Stability to Properties of Cluster Boundaries

  2008cited by this paper
• On the Reliability of Clustering Stability in the Large Sample Regime

  2008cited by this paper
• Estimating local optimums in EM algorithm over Gaussian mixture model

  2008cited by this paper
• Model Selection and Stability in k-means Clustering

  2008cited by this paper
• A Probabilistic Analysis of EM for Mixtures of Separated, Spherical Gaussians

  2007influential reference
• k-means++: the advantages of careful seeding

  2007cited by this paper
• Cluster Stability for Finite Samples

  2007cited by this paper
• Stability of k -Means Clustering

  2007cited by this paper
• An investigation of computational and informational limits in Gaussian mixture clustering

  2006cited by this paper
• The Effectiveness of Lloyd-Type Methods for the k-Means Problem

  2006cited by this paper
• A Sober Look at Clustering Stability

  2006cited by this paper
• Stability-Based Validation of Clustering Solutions

  2004cited by this paper
• Foundations of Quantization for Probability Distributions

  2000cited by this paper
• Convergence Properties of the K-Means Algorithms

  1994cited by this paper
• A Best Possible Heuristic for the k-Center Problem

  1985cited by this paper

• Assigning Confidence: K-partition Ensembles

  2026cites this paper
• Multi-objective Bayesian optimization with enhanced features for adaptively improved glioblastoma partitioning and survival prediction

  2024cites this paper
• Consensus based phase connectivity identification for distribution network with limited observability

  2023cites this paper
• Differentiable Clustering with Perturbed Spanning Forests

  2023cites this paper
• Impact of new seed and performance criteria in proposed rough k-means clustering

  2023cites this paper
• Initializing FWSA K-Means With Feature Level Constraints

  2022cites this paper
• Cluster analysis: A modern statistical review

  2022cites this paper
• Hierarchical Unsupervised Partitioning of Large Size Data and Its Application to Hyperspectral Images

  2021cites this paper
• Distribution free optimality intervals for clustering

  2021influential citation
• Tangent Space Least Adaptive Clustering

  2021cites this paper
• Selecting the Number of Clusters K with a Stability Trade-off: an Internal Validation Criterion

  2020cites this paper
• A new initialization and performance measure for the rough k-means clustering

  2020cites this paper
• Effificent Language Modeling of Long-Term Dependencies

  2020cites this paper
• Performance-enhanced rough k\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k$$\end{document}-means clustering algorit

  2020cites this paper
• The k-means Algorithm: A Comprehensive Survey and Performance Evaluation

  2020cites this paper
• Voting-based Approach in Consensus Clustering through q-fold cross-validation

  2019cites this paper
• An improved path-based clustering algorithm

  2019cites this paper
• Fuzzy Clustering of Maize Plant-Height Patterns Using Time Series of UAV Remote-Sensing Images and Variety Traits

  2019cites this paper
• Continuous greedy randomized adaptive search procedure for data clustering

  2018cites this paper
• Algorithms For Clustering Problems: Theoretical Guarantees and Empirical Evaluations

  2018cites this paper
• Clustering stability-based Evolutionary K-Means

  2018cites this paper
• How to tell when a clustering is (approximately) correct using convex relaxations

  2018cites this paper
• Exploratory Analysis of Clustering Problems Using a Comparison of Particle Swarm Optimization and Differential Evolution

  2017cites this paper
• L10: Spectral Clustering

  2016influential citation
• Inferring Individual-Level Variations in the Functional Parcellation of the Cerebral Cortex

  2016cites this paper
• A k-core Decomposition Framework for Graph Clustering

  2016cites this paper
• Inferring Individual-Level Variations in the Functional Parcellation of the Cerebral Cortex

  2016cites this paper
• Improving the Accuracy of Multispectral Image Clustering by Means of a New Initializing Method

  2016cites this paper
• Clustering Mixed Datasets Using Homogeneity Analysis with Applications to Big Data

  2016cites this paper
• Unsupervised and stable LBG algorithm for data classification: application to aerial multicomponent images

  2015cites this paper
• An intelligent architecture for legged robot terrain classification using proprioceptive and exteroceptive data

  2015cites this paper
• Retinal vessel segmentation using multi-scale textons derived from keypoints

  2015cites this paper
• Better understanding of water quality evolution in water distribution networks using data clustering.

  2015cites this paper
• Apolar and polar transitions drive the conversion between amoeboid and mesenchymal shapes in melanoma cells

  2015cites this paper
• Clustering algorithm selection by meta-learning systems: A new distance-based problem characterization and ranking combination methods

  2015cites this paper
• Stable and unsupervised fuzzy C-means method and its validation in the context of multicomponent images

  2015cites this paper
• A stable and unsupervised Fuzzy C-Means for data classification

  2015cites this paper
• Clustering stability and ground truth: Numerical experiments

  2015cites this paper
• Handbook of Cluster Analysis

  2015cites this paper
• Visual stability analysis for model selection in graded possibilistic clustering

  2014cites this paper
• SWIFT—Scalable Clustering for Automated Identification of Rare Cell Populations in Large, High-Dimensional Flow Cytometry Datasets, Part 2: Biological Evaluation

  2014cites this paper
• Further heuristics for $k$-means: The merge-and-split heuristic and the $(k, l)$-means

  2014cites this paper
• An in-depth study of forecasting household electricity demand using realistic datasets

  2014cites this paper
• Convex Optimization Procedure for Clustering: Theoretical Revisit

  2014cites this paper
• On data mining applications in mobile networking and network security

  2014cites this paper
• Notes on using Determinantal Point Processes for Clustering with Applications to Text Clustering

  2014cites this paper
• Data Mining-based Fragmentation for Query Optimization

  2014cites this paper
• Robustness and Stability Analysis of Factor PD-Clustering on Large Social Data Sets

  2014cites this paper
• Unsupervised cooperative partitioning approach of hyperspectral images for decision making

  2014cites this paper
• Scaling up Lloyd’s algorithm: stochastic and parallel block-wise optimization perspectives

  2014influential citation
• Identifying environmentally important supply chain clusters in the automobile industry

  2013cites this paper
• Towards Theoretical Foundations of Clustering

  2012cites this paper
• About recommender-like systems using co-clustering criteria

  2012cites this paper
• Weighted Clustering

  2011cites this paper
• Clustering Stability: An Overview

  2010influential citation
• A Complete Bibliography of Publications in ESAIM: Probability and Statistics

  year unknowncites this paper
• Virtual Nodes Go Temporal

  year unknowncites this paper