%0 Book Section %1 NIPS2006_780 %A Narayanan, Hariharan %A Belkin, Mikhail %A Niyogi, Partha %B Advances in Neural Information Processing Systems 19 %C Cambridge, MA %D 2007 %E Schölkopf, B. %E Platt, J. %E Hoffman, T. %I MIT Press %K 2006 spectral clustering nips %T On the Relation Between Low Density Separation, Spectral Clustering and Graph Cuts %U http://books.nips.cc/papers/files/nips19/NIPS2006_0780.pdf %X One of the intuitions underlying many graph-based methods for clustering and semi-supervised learning, is that class or cluster boundaries pass through areas of low probability density. In this paper we provide some formal analysis of that notion for a probability distribution. We introduce a notion of weighted boundary volume, which measures the length of the class/cluster boundary weighted by the density of the underlying probability distribution. We show that sizes of the cuts of certain commonly used data adjacency graphs converge to this continuous weighted volume of the boundary.

@incollection{NIPS2006_780, abstract = {One of the intuitions underlying many graph-based methods for clustering and semi-supervised learning, is that class or cluster boundaries pass through areas of low probability density. In this paper we provide some formal analysis of that notion for a probability distribution. We introduce a notion of weighted boundary volume, which measures the length of the class/cluster boundary weighted by the density of the underlying probability distribution. We show that sizes of the cuts of certain commonly used data adjacency graphs converge to this continuous weighted volume of the boundary.}, added-at = {2007-01-29T15:55:00.000+0100}, address = {Cambridge, MA}, author = {Narayanan, Hariharan and Belkin, Mikhail and Niyogi, Partha}, biburl = {https://www.bibsonomy.org/bibtex/25a6f3a1596960d21c499aca3e72ab384/seandalai}, booktitle = {Advances in Neural Information Processing Systems 19}, editor = {Sch\"{o}lkopf, B. and Platt, J. and Hoffman, T.}, interhash = {9f01395b25492f6f047a1fcf99037042}, intrahash = {5a6f3a1596960d21c499aca3e72ab384}, keywords = {2006 spectral clustering nips}, publisher = {MIT Press}, timestamp = {2007-01-29T15:55:00.000+0100}, title = {On the Relation Between Low Density Separation, Spectral Clustering and Graph Cuts}, url = {http://books.nips.cc/papers/files/nips19/NIPS2006_0780.pdf}, year = 2007 }