Dominant Sets and Pairwise Clustering
|
We develop a new graph-theoretic approach for pairwise data clustering which is motivated by the analogies between the intuitive concept of a cluster and that of a dominant set of vertices, a notion introduced here which generalizes that of a maximal complete subgraph to edge-weighted graphs. We establish a correspondence between dominant sets and the extrema of a quadratic form over the standard simplex, thereby allowing the use of straightforward and easily implementable continuous optimization techniques from evolutionary game theory. Numerical examples on various point-set and image segmentation problems confirm the potential of the proposed approach.
[1] 167 J.G. Auguston and J. Minker, “An Analysis of Some Graph Theoretical Clustering Techniques,” J. ACM, vol. 17, no. 4, pp. 571-588, 1970.
[2] R.O. Duda, P.E. Hart, and D.G. Stork, Pattern Classification. J. Wiley & Sons, 2000.
[3] B. Fischer and J.M. Buhmann, “Path-Based Clustering for Grouping Smooth Curves and Texture Segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 25, no. 4, pp. 513-518, Apr. 2003.
[4] Y. Gdalyahu, D. Weinshall, and M. Werman, “Self-Organization in Vision: Stochastic Clustering for Image Segmentation, Perceptual Grouping, and Image Database Organization,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 23, no. 10, pp. 1053-1074, Oct. 2001.
[5] L.E. Gibbons, D.W. Hearn, P.M. Pardalos, and M.V. Ramana, “Continuous Characterizations of the Maximum Clique Problem,” Math. Operations Research, vol. 22, pp. 754-768, 1997.
[6] C.C. Gotlieb and S. Kumar, “Semantic Clustering of Index Terms,” J. ACM, vol. 15, no. 4, pp. 493-513, 1968.
[7] T. Hofmann and J. Buhmann, “Pairwise Data Clustering by Deterministic Annealing,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 19, no. 1, pp. 1-14, Jan. 1997.
[8] A.K. Jain and R.C. Dubes, Algorithms for Clustering Data. Prentice Hall, 1988.
[9] D.G. Luenberger, Linear and Nonlinear Programming. Addison-Wesley, 1984.
[10] M. Ester, H.-P. Kriegel, J. Sander, and X. Xu, “A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise,” Proc. Second Int'l Conf. Knowledge Discovery and Data Mining, pp. 226-231, 1996.
[11] T.S. Motzkin and E.G. Straus, “Maxima for Graphs and a New Proof of a Theorem of Turán,” Canadian J. Math., vol. 17, pp. 533-540, 1965.
[12] M. Pavan, “A New Graph-Theoretic Approach to Clustering, with Applications to Computer Vision,” PhD thesis, Università Ca' Foscari di Venezia, Italy, 2004.
[13] M. Pavan and M. Pelillo, “A New Graph-Theoretic Approach to Clustering and Segmentation,” Proc. IEEE Conf. Computer Vision and Pattern Recognition, vol. 1, pp. 145-152, 2003.
[14] M. Pavan and M. Pelillo, “Dominant Sets and Hierarhical Clustering,” Proc. IEEE Int'l Conf. Computer Vision, vol. 1, pp. 362-369, 2003.
[15] M. Pavan and M. Pelillo, “Efficient Out-of-Sample Extension of Dominant-Set Clusters,” Advances in Neural Information Processing Systems 17, L.K.Saul, Y. Weiss, and L. Bottou, eds., pp. 1057-1064, 2005.
[16] M. Pelillo and A. Jagota, “Feasible and Infeasible Maxima in a Quadratic Program for Maximum Clique,” J. Artificial Neural Networks, vol. 2, pp. 411-420, 1995.
[17] P. Perona and W. Freeman, “A Factorization Approach to Grouping,” Proc. European Conf. Computer Vision, H. Burkhardt and B. Neumann, eds., pp.655-670, 1998.
[18] V.V. Raghavan and C.T. Yu, “A Comparison of the Stability Characteristics of Some Graph Theoretic Clustering Methods,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 3, pp. 393-402, 1981.
[19] S. Sarkar and K.L. Boyer, “Quantitative Measures of Change Based on Feature Organization: Eigenvalues and Eigenvectors,” Computer Vision and Image Understanding, vol. 71, no. 1, pp. 110-136, 1998.
[20] J. Shi and J. Malik, “Normalized Cuts and Image Segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 22, no. 8, pp. 888-905, Aug. 2000.
[21] J.W. Weibull, Evolutionary Game Theory. MIT Press, 1995.
[22] Z. Wu and R. Leahy, “An Optimal Graph Theoretic Approach to Data Clustering: Theory and Its Application to Image Segmentation,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 15, no. 11, pp. 1101-1113, Nov. 1993.
[23] C.T. Zahn, “Graph-Theoretic Methods for Detecting and Describing Gestalt Clusters,” IEEE Trans. Computers, vol. 20, pp. 68-86, 1971.
Index Terms:
Clustering, quadratic optimization, evolutionary game dynamics, image segmentation, perceptual organization.
Citation:
Massimiliano Pavan, Marcello Pelillo, "Dominant Sets and Pairwise Clustering," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 29, no. 1, pp. 167-172, Jan. 2007, doi:10.1109/TPAMI.2007.10
PURCHASE ARTICLE: $19
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb