Department of Statistics, University of Washington - Department of Mathematics Optimization Seminar
In a similarity based clustering task, one defines a "similarity function" between pairs of points and then formulates a criterion (e.g. maximum intracluster similarity) that the clustering must optimize. The optimality criterion quantifies the intuitive notion that points in the same clusters should be similar while points in different clusters should be dissimilar. Most sensible criteria are NP hard to optimize. An alternative view that has been successful in recent years is represented by spectral methods, where clustering is based on the first few eigenvectors of a matrix. This talk discusses such a method (the Normalized Cut method) and presents a new view of clustering by pairwise similarities. We interpret the similarities as edge flows in a Markov random walk and study the eigenvalues and eigenvectors of the walk's transition matrix. This view shows that spectral methods for clustering have a probabilistic foundation. We prove that the Normalized Cut method arises naturally from our framework and we provide a complete characterization of the cases when the Normalized Cut algorithm is exact. Then we discuss other spectral segmentation and clustering methods showing that several of them are essentially the same as NCut.