nips nips2004 nips2004-61 nips2004-61-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Massimiliano Pavan, Marcello Pelillo
Abstract: Dominant sets are a new graph-theoretic concept that has proven to be relevant in pairwise data clustering problems, such as image segmentation. They generalize the notion of a maximal clique to edgeweighted graphs and have intriguing, non-trivial connections to continuous quadratic optimization and spectral-based grouping. We address the problem of grouping out-of-sample examples after the clustering process has taken place. This may serve either to drastically reduce the computational burden associated to the processing of very large data sets, or to efficiently deal with dynamic situations whereby data sets need to be updated continually. We show that the very notion of a dominant set offers a simple and efficient way of doing this. Numerical experiments on various grouping problems show the effectiveness of the approach. 1
[1] Y. Bengio, J.-F. Paiement, P. Vincent, O. Delalleau, N. Le Roux, and M. Ouimet. Out-of-sample extensions for LLE, Isomap, MDS, eigenmaps, and spectral clustering. In: S. Thrun, L. Saul, and B.Sch¨ lkopf (Eds.), Advances in Neural Information Processing Systems 16, MIT Press, o Cambridge, MA, 2004.
[2] C. Fowlkes, S. Belongie, F. Chun, and J. Malik. Spectral grouping using the Nystr¨ m method. o IEEE Trans. Pattern Anal. Machine Intell. 26:214–225, 2004.
[3] T. Hofmann and J. M. Buhmann. Pairwise data clustering by deterministic annealing. IEEE Trans. Pattern Anal. Machine Intell. 19:1–14, 1997.
[4] D. Luenberger. Linear and Nonlinear Programming. Addison-Wesley, Reading, MA, 1984.
[5] T. S. Motzkin and E. G. Straus. Maxima for graphs and a new proof of a theorem of Tur´ n. a Canad. J. Math. 17:533–540, 1965.
[6] A. Y. Ng, M. I. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In: T. G. Dietterich, S. Becker, and Z. Ghahramani (Eds.), Advances in Neural Information Processing Systems 14, MIT Press, Cambridge, MA, pp. 849–856, 2002.
[7] M. Pavan and M. Pelillo. A new graph-theoretic approach to clustering and segmentation. In Proc. IEEE Conf. Computer Vision and Pattern Recognition, pp. 145–152, 2003.
[8] M. Pavan, M. Pelillo. Unsupervised texture segmentation by dominant sets and game dynamics. In Proc. 12th Int. Conf. on Image Analysis and Processing, pp. 302–307, 2003.
[9] M. Pavan and M. Pelillo. Dominant sets and hierarchical clustering. In Proc. 9th Int. Conf. on Computer Vision, pp. 362–369, 2003.
[10] P. Perona and W. Freeman. A factorization approach to grouping. In: H. Burkhardt and B. Neumann (Eds.), Computer Vision—ECCV’98, pp. 655–670. Springer, Berlin, 1998.
[11] V. Roth, J. Laub, M. Kawanabe, and J. M. Buhmann. Optimal cluster preserving embedding of nonmetric proximity data. IEEE Trans. Pattern Anal. Machine Intell. 25:1540–1551, 2003.
[12] S. Sarkar and K. Boyer. Quantitative measures of change based on feature organization: Eigenvalues and eigenvectors. Computer Vision and Image Understanding 71:110–136, 1998.
[13] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Machine Intell. 22:888–905, 2000.
[14] J. W. Weibull. Evolutionary Game Theory. MIT Press, Cambridge, MA, 1995.
[15] Y. Weiss. Segmentation using eigenvectors: A unifying view. In Proc. 7th Int. Conf. on Computer Vision, pp. 975–982, 1999.