Foundations and Trends® in Machine Learning > Vol 2 > Issue 3

Clustering Stability: An Overview

Ulrike von Luxburg, Max Planck Institute for Biological Cybernetics, Germany, ulrike.luxburg@tuebingen.mpg.de
 
Suggested Citation
Ulrike von Luxburg (2010), "Clustering Stability: An Overview", Foundations and TrendsĀ® in Machine Learning: Vol. 2: No. 3, pp 235-274. http://dx.doi.org/10.1561/2200000008

Published: 21 Apr 2010
© 2010 U. von Luxburg
 
Subjects
Clustering
 

Free Preview:

Article Help

Share

Download article
In this article:
1 Introduction
2 Clustering Stability: Definition and Implementation
3 Stability Analysis of the K-Means Algorithm
4 Beyond K-Means
5 Outlook
References

Abstract

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.

DOI:10.1561/2200000008
ISBN: 978-1-60198-344-2
48 pp. $50.00
Buy book
 
ISBN: 978-1-60198-345-9
48 pp. $100.00
Buy E-book
Table of contents:
1: Introduction
2: Clustering stability: definition and implementation
3: Stability analysis of the K-means algorithm
4: Beyond K-means
5: Outlook
References

Clustering Stability

Clustering Stability: An Overview provides a high-level overview about the existing literature on clustering stability. It reviews different protocols for how clustering stability is computed and used for model selection. The main body of the text goes on to examine theoretical results for the K-means algorithm and discuss their various relations. Finally, it looks at results for more general clustering algorithms. In addition to presenting the results in a slightly informal but accessible way, Clustering Stability: An Overview relates them to each other and discusses their different implications.

 
MAL-008