8. und 9. Vorlesung: Clustering

The "traditional" approaches (which are described in many machine learning and data mining books, for example in Hastie/Tibshirani/Friedman: Elements of statistical Learning)

• k-means
• linkage algorithms
• model based algorithms

How can we determine the number of clusters?

• gap statistic: Robert Tibshirani1, Guenther Walther1 & Trevor Hastie1: Estimating the number of clusters in a data set via the gap statistic. 2000
• stability approach: see eg Volker Roth, Tilman Lange, Mikio Braun, Joachim Buhmann: A Resampling Approach to Cluster Validation, 2002. or A. Ben-Hur, A Elisseeff, I Guyon: A stability based method for discovering structure in clustered data, 2002. And for some criticism about the stability approach: Ben-David,Luxburg,Pal: A sober look at clustering stability. 2006.

Clustering from a formal viewpoint: What is clustering after all? (for an extensive discussion aobut this topic see talks at the workshop "Theoretical Foundations of Clustering", 2005)

• clustering as minimizer of certain objective functions
• clustering as density level set estimation
• axiomatic approaches to clustering (here we will in particular discuss Kleinberg's Impossibility theorem)

Spectral clustering

Short introduction to spectral graph theory and random walks on graphs. The standard reference for the first topic is the book "Chung: Spectral Graph Theory", but it is not exactly an introductory book... For basic facts about random walks on graphs, any introductory text about markov chains will do it. For more special and more advanced questions there are some online references, such as Lovasz: Random walks on graphs, a survey, 1993 or D.Aldous and Fill: Reversible Markov Chains and Random Walks on Graphs (book in preparation).

Spectral clustering from different viewpoints:

• Explanation by balanced cuts (see J. Shi and J. Malik: Normalized Cuts and Image Segmentation. and Section 2 of Luxburg et al: Consistency of spectral clustering)
• Explanation by random walks (see Meila/Shi: Random walks view on spectral clustering )
• Normalized vs. unnormalized spectral clustering

Demos for both lectures:

• demo_clustering.m: compare several clustering algorithms.
• demo_spectral_clustering.m: see step by step how it works, on a toy example. You will also need spectral_ule.m to run it.
• demo_clustering_choose_k.m: gap statistics and stability approach to choose the number of clusters.