nips nips2006 nips2006-80 nips2006-80-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Boaz Nadler, Meirav Galun
Abstract: Spectral clustering methods are common graph-based approaches to clustering of data. Spectral clustering algorithms typically start from local information encoded in a weighted graph on the data and cluster according to the global eigenvectors of the corresponding (normalized) similarity matrix. One contribution of this paper is to present fundamental limitations of this general local to global approach. We show that based only on local information, the normalized cut functional is not a suitable measure for the quality of clustering. Further, even with a suitable similarity measure, we show that the first few eigenvectors of such adjacency matrices cannot successfully cluster datasets that contain structures at different scales of size and density. Based on these findings, a second contribution of this paper is a novel diffusion based measure to evaluate the coherence of individual clusters. Our measure can be used in conjunction with any bottom-up graph-based clustering method, it is scale-free and can determine coherent clusters at all scales. We present both synthetic examples and real image segmentation problems where various spectral clustering algorithms fail. In contrast, using this coherence measure finds the expected clusters at all scales. Keywords: Clustering, kernels, learning theory. 1
[1] J. Shi and J. Malik. Normalized cuts and image segmentation, PAMI, Vol. 22, 2000.
[2] R. Kannan, S. Vempala, A. Vetta, On clusterings: good, bad and spectral, J. ACM, 51(3):497-515, 2004.
[3] D. Cheng, R. Kannan, S. Vempala, G. Wang, A divide and merge methodology for clustering, ACM SIGMOD/PODS, 2005.
[4] F.R.K. Chung, Spectral Graph Theory, Regional Conference Series in Mathematics Vol. 92, 1997.
[5] Y. Weiss, Segmentation using eigenvectors: a unifying view, ICCV 1999.
[6] A.Y. Ng, M.I. Jordan, Y. Weiss, On Spectral Clustering: Analysis and an algorithm, NIPS Vol. 14, 2002.
[7] N. Cristianini, J. Shawe-Taylor, J. Kandola, Spectral kernel methods for clustering, NIPS, Vol. 14, 2002.
[8] M. Belkin and P. Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering, NIPS Vol. 14, 2002.
[9] S. Yu and J. Shi. Multiclass spectral clustering. ICCV 2003.
[10] L. Zelnik-Manor, P. Perona, Self-Tuning spectral clustering, NIPS, 2004.
[11] M. Saerens, F. Fouss, L. Yen and P. Dupont, The principal component analysis of a graph and its relationships to spectral clustering. ECML 2004.
[12] M. Meila, J. Shi. A random walks view of spectral segmentation, AI and Statistics, 2001.
[13] B. Nadler, S. Lafon, R.R. Coifman, I.G. Kevrekidis, Diffusion maps spectral clustering and eigenfunctions of Fokker-Planck operators, NIPS, 2005.
[14] S. Lafon, A.B. Lee, Diffusion maps and coarse graining: a unified framework for dimensionality reduction, graph partitioning, and data set parameterization, PAMI, 28(9):1393-1403, 2006.
[15] D. Harel and Y. Koren, On Clustering Using Random Walks, FST TCS, 2001.
[16] I. Fischer, J. Poland, Amplifying the block matrix structure for spectral clustering, Proceedings of the 14th Annual Machine Learning Conference of Belgium and the Netherlands, pp. 21-28, 2005.
[17] J. Malik, S. Belongie, T. Leung, J. Shi, Contour and texture analysis for image segmentation, Int. J. Comp. Vis. 43(1):7-27, 2001.
[18] E. Sharon, A. Brandt, R. Basri, Segmentation and Boundary Detection Using Multiscale Intensity Measurements, CVPR, 2001.
[19] M. Galun, E. Sharon, R. Basri and A. Brandt, Texture Segmentation by Multiscale Aggregation of Filter Responses and Shape Elements, ICCV, 2003.
[20] C.W. Gardiner, Handbook of stochastic methods, third edition, Springer NY, 2004.
[21] N. Tishby, N. Slonim, Data clustering by Markovian relaxation and the information bottleneck method, NIPS, 2000.
[22] C. Chennubhotla, A.J. Jepson, Half-lives of eigenflows for spectral clustering, NIPS, 2002.
[23] E. Sharon, A. Brandt, R. Basri, Fast multiscale image segmentation, ICCV, 2000.
[24] T. Cour, F. Benezit, J. Shi. Spectral Segmentation with Multiscale Graph Decomposition. CVPR, 2005.