CSAIL Event Calendar: Previous Series

Spectral clustering as optimization

Speaker: Marina Meila , University of Washington
Date: November 13 2003
Time: 4:00pm
Location: NE43-941

Spectral clustering methods, i.e methods that use eigenvectors of a suitably chosen matrix to partition the data, have recently become popular. This talk will analyze from a novel perspective why spectral clustering works. In particular, we show that spectral algorithms work in a wider and more interesting range of cases than it is generally believed. In the vicinity of some special points called perfect, spectral clustering optimizes simultaneously two criteria: a dissimilarity measure akin to the isoperimetric number (that we call the multiway normalized cut) and a cluster coherence measure (that we call the gap).

Based on these results, we demonstrate that several popular clustering algorithms are equivalent near perfect points, we propose new methods for selecting the number of clusters and show their superior performance in experiments.

Joint work with: Jianbo Shi, Deepak Verma, Liang Xu

See other events that are part of AI Colloquium Series Fall 2003

See other events happening in November 2003