A Random Walks View of Spectral Segmentation.

Abstract

We present a new view of clustering and segmentation by pairwise similarities. We interpret the similarities as edge ows 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 and segmentation 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. 1 Introduction This paper focuses on pairwise (or similarity-based) clustering and image segmentation. In contrast to statistical clustering methods, that assume a probabilistic model that generates the observed data points (or pixels) , pairwise clustering denes a similarity function between pairs of points and then formulates a criterion (e.g. maxi...