A Random Walks View of Spectral Segmentation

Marina Meilă, Jianbo Shi
Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, PMLR R3:203-208, 2001.

Abstract

We present a new view of clustering and segmentation 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 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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR3-meila01a, title = {A Random Walks View of Spectral Segmentation}, author = {Meil\u{a}, Marina and Shi, Jianbo}, booktitle = {Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics}, pages = {203--208}, year = {2001}, editor = {Richardson, Thomas S. and Jaakkola, Tommi S.}, volume = {R3}, series = {Proceedings of Machine Learning Research}, month = {04--07 Jan}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/r3/meila01a/meila01a.pdf}, url = {https://proceedings.mlr.press/r3/meila01a.html}, abstract = {We present a new view of clustering and segmentation 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 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.}, note = {Reissued by PMLR on 31 March 2021.} }
Endnote
%0 Conference Paper %T A Random Walks View of Spectral Segmentation %A Marina Meilă %A Jianbo Shi %B Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2001 %E Thomas S. Richardson %E Tommi S. Jaakkola %F pmlr-vR3-meila01a %I PMLR %P 203--208 %U https://proceedings.mlr.press/r3/meila01a.html %V R3 %X We present a new view of clustering and segmentation 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 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. %Z Reissued by PMLR on 31 March 2021.
APA
Meilă, M. & Shi, J.. (2001). A Random Walks View of Spectral Segmentation. Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research R3:203-208 Available from https://proceedings.mlr.press/r3/meila01a.html. Reissued by PMLR on 31 March 2021.

Related Material