chapter  8
Spectral Clustering
ByJialu Liu, Jiawei Han
Pages 24

In this chapter, we introduce the family of spectral clustering algorithms which have seen increasing popularity over the past few years. Starting with the seminal works in [37] and [43], a large number of papers has been published along this line of work. As opposed to “traditional clustering algorithms” such as k-means and generative mixture models which always result in clusters with convex geometric shape, spectral clustering can solve problems in much more complex scenarios, such as intertwined spirals, or other arbitrary nonlinear shapes, because it does not make assumptions on the shapes of clusters. Another disadvantage of the previous algorithms is related to the inherent challenges in the Expectation Maximization (EM) framework, which is often used to learn 178a mixture model for clustering. This framework is essentially an iterative process of finding local minima, and therefore multiple restarts are required to find a good solution. Self-tuning spectral clustering on toy datasets. (From Zelnik-Manor and Perona, Advances in Neural Information Processing Systems, 17:1601–1608, 2004.)