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 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
Text
Meilă and Shi. "A Random Walks View of Spectral Segmentation." Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, 2001.Markdown
[Meilă and Shi. "A Random Walks View of Spectral Segmentation." Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics, 2001.](https://mlanthology.org/aistats/2001/meila2001aistats-random/)BibTeX
@inproceedings{meila2001aistats-random,
title = {{A Random Walks View of Spectral Segmentation}},
author = {Meilă, Marina and Shi, Jianbo},
booktitle = {Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics},
year = {2001},
pages = {203-208},
volume = {R3},
url = {https://mlanthology.org/aistats/2001/meila2001aistats-random/}
}