nips nips2002 nips2002-100 nips2002-100-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Chakra Chennubhotla, Allan D. Jepson
Abstract: Using a Markov chain perspective of spectral clustering we present an algorithm to automatically find the number of stable clusters in a dataset. The Markov chain’s behaviour is characterized by the spectral properties of the matrix of transition probabilities, from which we derive eigenflows along with their halflives. An eigenflow describes the flow of probability mass due to the Markov chain, and it is characterized by its eigenvalue, or equivalently, by the halflife of its decay as the Markov chain is iterated. A ideal stable cluster is one with zero eigenflow and infinite half-life. The key insight in this paper is that bottlenecks between weakly coupled clusters can be identified by computing the sensitivity of the eigenflow’s halflife to variations in the edge weights. We propose a novel E IGEN C UTS algorithm to perform clustering that removes these identified bottlenecks in an iterative fashion.
[1] P. Felzenszalb and D. Huttenlocher Efficiently Computing a Good Segmentation Internation Journal on Computer Vision, 1999.
[2] R. Kannan, S. Vempala and A. Vetta On clusterings–good, bad and spectral. Proc. 41st Annual Symposium on Foundations of Computer Science , 2000.
[3] J. R. Kemeny and J. L. Snell Finite Markov Chains. Van Nostrand, New York, 1960.
[4] M. Meila and J. Shi A random walks view of spectral segmentation. Proc. International Workshop on AI and Statistics , 2001.
[5] A. Ng, M. Jordan and Y. Weiss On Spectral Clustering: analysis and an algorithm NIPS, 2001.
[6] A. Ng, A. Zheng, and M. Jordan Stable algorithms for link analysis. Proc. 24th Intl. ACM SIGIR Conference, 2001.
[7] A. Ng, A. Zheng, and M. Jordan Link analysis, eigenvectors and stability. Proc. 17th Intl. IJCAI, 2001.
[8] P. Perona and W. Freeman A factorization approach to grouping. European Conference on Computer Vision, 1998.
[9] A. Pothen Graph partitioning algorithms with applications to scientific computing. Parallel Numerical Algorithms, D. E. Keyes et al (eds.), Kluwer Academic Press, 1996.
[10] G. L. Scott and H. C. Longuet-Higgins Feature grouping by relocalization of eigenvectors of the proximity matrix. Proc. British Machine Vision Conference, pg. 103-108, 1990.
[11] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transaction on Pattern Analysis and Machine Intelligence , 2000.
[12] N. Tishby and N. Slonim Data clustering by Markovian Relaxation and the Information Bottleneck Method. NIPS, v 13, MIT Press, 2001.
[13] Y. Weiss Segmentation using eigenvectors: a unifying view. International Conference on Computer Vision, 1999. Appendix We compute the derivative of the log of half-life of an eigenvalue with respect to an element of the affinity matrix . Half-life is defined as the power to which must be raised to reduce the eigenvalue to half, i.e., . What we are interested is in seeing significant changes in those half-lives which are relatively large compared to some minimum half-life . So eigenvectors with half-lives smaller than are effectively ignored. It is easy to show that, 2 o t y t y ¢ Y h A 2 o ¢ f h ¢ t ( A 2 o ¢ is the modified affinity matrix (7) ` R ) 2 2 8 6 4 d 2e 1753 A r R 2 ! ( p A 1 ` n 0 ( 1 ) r p R ( I q 1 1 2 o r S i gp t f P h t y y § ¥ ¡¦£ § ¥ £ r t gp ¨ ©y r Wy ( t Y A d b wcD d b wcD !