English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  A Sober Look at Clustering Stability

Ben-David, S., von Luxburg, U., & Pal, D. (2006). A Sober Look at Clustering Stability. In G. Lugosi, & H. Simon (Eds.), Learning Theory: 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006 (pp. 5-19). Berlin, Germany: Springer.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0013-D03D-2 Version Permalink: http://hdl.handle.net/21.11116/0000-0004-9A93-8
Genre: Conference Paper

Files

show Files

Locators

show
hide
Description:
-

Creators

show
hide
 Creators:
Ben-David, S, Author
von Luxburg, U1, Author              
Pal, D, Author
Affiliations:
1External Organizations, ou_persistent22              

Content

show
hide
Free keywords: -
 Abstract: Stability is a common tool to verify the validity of sample based algorithms. In clustering it is widely used to tune the parameters of the algorithm, such as the number k of clusters. In spite of the popularity of stability in practical applications, there has been very little theoretical analysis of this notion. In this paper we provide a formal definition of stability and analyze some of its basic properties. Quite surprisingly, the conclusion of our analysis is that for large sample size, stability is fully determined by the behavior of the objective function which the clustering algorithm is aiming to minimize. If the objective function has a unique global minimizer, the algorithm is stable, otherwise it is unstable. In particular we conclude that stability is not a well-suited tool to determine the number of clusters - it is determined by the symmetries of the data which may be unrelated to clustering parameters. We prove our results for center-based clusterings and for spectral clustering, and support our conclusions by many examples in which the behavior of stability is counter-intuitive.

Details

show
hide
Language(s):
 Dates: 2006-09
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: DOI: 10.1007/11776420_4
BibTex Citekey: 4109
 Degree: -

Event

show
hide
Title: 19th Annual Conference on Learning Theory (COLT 2006)
Place of Event: Pittsburgh, PA, USA
Start-/End Date: 2006-06-22 - 2006-06-25

Legal Case

show

Project information

show

Source 1

show
hide
Title: Learning Theory: 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006
Source Genre: Proceedings
 Creator(s):
Lugosi, G, Editor
Simon, HU, Editor
Affiliations:
-
Publ. Info: Berlin, Germany : Springer
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 5 - 19 Identifier: ISBN: 978-3-540-35294-5