nips nips2003 nips2003-152 nips2003-152-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Noam Shental, Assaf Zomet, Tomer Hertz, Yair Weiss
Abstract: Significant progress in clustering has been achieved by algorithms that are based on pairwise affinities between the datapoints. In particular, spectral clustering methods have the advantage of being able to divide arbitrarily shaped clusters and are based on efficient eigenvector calculations. However, spectral methods lack a straightforward probabilistic interpretation which makes it difficult to automatically set parameters using training data. In this paper we use the previously proposed typical cut framework for pairwise clustering. We show an equivalence between calculating the typical cut and inference in an undirected graphical model. We show that for clustering problems with hundreds of datapoints exact inference may still be possible. For more complicated datasets, we show that loopy belief propagation (BP) and generalized belief propagation (GBP) can give excellent results on challenging clustering problems. We also use graphical models to derive a learning algorithm for affinity matrices based on labeled data. 1
[1] M. Blatt, S. Wiseman, and E. Domany. Data clustering using a mode lgranular magnet. Neural Computation, 9:1805–1842, 1997.
[2] Y. Gdalyahu, D. Weinshall, and M. Werman. Self organization in vision: Stochastic clustering for image segmentation, perceptual grouping, and image database organization. IEEE Trans. on Pattern Analysis and Machine Intelligence, 23(10):1053–1074, 2001.
[3] T. Hofmann and J. M. Buhmann. Pairwise data clustering by deterministic annealing. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(1):1–14, 1997.
[4] M. Meila and J. Shi. Learning segmentation by random walks. In Advances in Neural Information Processing Systems 14, 2001.
[5] T. Minka and Y. Qi. Tree-structured approximations by expectation propagation. In Advances in Neural Information Processing Systems 16, 2003.
[6] A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing 14, 2001.
[7] N. Shental, A. Zomet, T. Hertz, and Y. Weiss. Learning and inferring image segmentations using the gbp typical cut. In 9th International Conference on Computer Vision, 2003.
[8] J. Shi and J. Malik. Normalized cuts and image segmentation. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pages 731–737, 1997.
[9] J.S. Wang and R.H Swendsen. Cluster monte carlo algorithms. Physica A, 167:565–579, 1990.
[10] J. Yedidia, W. Freeman, and Y. Weiss. Understanding belief propagation and its generalizations. In G. Lakemeyer and B. Nebel, editors, Exploring Artificial Intelligence in the New Millennium. Morgan Kaufmann, 2003.