Clustering Stability: An Overview

By Ulrike von Luxburg. 2010

333 citations recorded by the source corpus.

A popular method for selecting the number of clusters is based on stability arguments: one chooses the number of clusters such that the corresponding clustering results are "most stable". In recent years, a series of papers has analyzed the behavior of this method from a theoretical point of view. However, the results are very technical and difficult to interpret for non-experts. In this monograph we give a high-level overview about the existing literature on clustering stability. In addition to presenting the results in a slightly informal but accessible way, we relate them to each other and discuss their different implications.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistical and Nonlinear Physics

Citations in the corpus

Is data clustering in adversarial settings secure? (2013, background): “It is worth noting that results from the literature of clustering stability [29] can not be directly exploited to this end, since the noise induced by adversarial manipulations is not generally stochastic but specifically targeted against the clustering algorithm.”
A systematic performance evaluation of clustering methods for single-cell RNA-seq data (2018, background): “These subsamples can be created in several ways, e.g., by random subsampling with or without replacement, by adding noise to the original data 50 or by simulating technical replicates 51 .”
Self-Supervised Representation Learning: Introduction, advances, and challenges (2021, neutral): “An example of how further work could address gaps in our current understanding is to extend theoretical frameworks analyzing (shallow) clustering methods [51] to the deep SSRL paradigm.”
K-variates++: More Pluses in the K-means++ (2016, background): “We do expect further applications of these results, in particular to address several other key clustering problems: stability, generalisation and smoothed analysis (Arthur et al., 2011; von Luxburg, 2010); (ii) we provide two examples of application.”
Clustering trees: a visualization for evaluating clusterings at multiple resolutions (2018, background): “This has led to a range of cluster stability measures [9], many of which rely on clustering of perturbed or subsampled datasets.”
How much can k-means be improved by using better initialization and repeats? (2019, methodology): “Two standalone algorithms are also considered: Luxburg [50] and Split algorithm.”
Clustering: Science or Art? (2009, background): “See von Luxburg (2010) for a large list of references.”
ABX-Discriminability Measures and Applications. (Mesures de discriminabilité ABX et applications) (2016, positive): “Some approaches to characterizing theoretically this instability have been developed essentially in the particular case of K-means clustering (see mainly [32] and for a high-level review and discussion [33]), but it is observed in practice for all clustering techniques.”