Abstract
Pairwise (or graph-based) clustering algorithms typically assume the existence of a single affinity matrix, which describes the similarity between the objects to be clustered. In many practical applications, however, several similarity relations might be envisaged and the problem arises as to how properly select or combine them. In this paper we offer a solution to this problem for the case of dominant sets, a well-known formalization of the notion of a cluster, which generalizes the notion of maximal clique to edge-weighted graphs and has intriguing connections to evolutionary game theory. Specifically, it has been shown that dominant sets can be bijectively related to Evolutionary Stable Strategies (ESS) - a classic notion of equilibrium in the evolutionary game theory field - of a so-called “clustering game”. The clustering game is a non-cooperative game between two-players, where the objects to cluster form the set of strategies, while the affinity matrix provides the players’ payoffs. The proposed approach generalizes dominant sets to multiple affinities by extending the clustering game, which has a single payoff, to a multi-payoff game. Accordingly, dominant sets in the multi-affinity setting become equivalent to ESSs of a corresponding multi-payoff clustering game, which can be found by means of so-called Biased Replicator Dynamics. Experiments conducted over standard benchmark datasets consistently show that the proposed combination scheme allows one to substantially improve the performance of dominant-set clustering over its single-affinity counterpart.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Alata, E., Dacier, M., Deswarte, Y., Kaaâniche, M., Kortchinsky, K., Nicomette, V., Pham, V.H., Pouget, F.: Collection and analysis of attack data based on honeypots deployed on the internet. In: Gollmann, D., Massacci, F., Yautsiukhin, A. (eds.) Quality of Protection. Advances in Information Security, vol. 23, pp. 79–91. Springer, USA (2006)
Albarelli, A., Bulò, S.R., Torsello, A., Pelillo, M.: Matching as a non-cooperative game. In: ICCV 2009, pp. 1319–1326 (2009)
Blackwell, D.: An analog of the minimax theorem for vector payoffs. Pac. J. Math. 6(11), 1–8 (1956)
Contini, B.M.: A decision model under uncertainty with multiple objectives. In: Mensch, A. (ed.) Theory of Games: Techniques and Applications. Elsevier, New York (1966)
Ehrgott, M.: Multicriteria Optimization, 2nd edn. Springer, Heidelberg (2005)
Frommlet, F.: Tag snp selection based on clustering according to dominant sets found using replicator dynamics. Adv. Data Anal. Classif. 4(1), 65–83 (2010)
Gönen, M., Alpaydin, E.: Multiple kernel learning algorithms. J. Mach. Learn. Res. 12, 2211–2268 (2011)
Hamid, R., Johnson, A.Y., Batta, S., Bobick, A.F., Isbell, C.L., Coleman, G.: Detection and explanation of anomalous activities: representing activities as bags of event n-grams. In: CVPR (1), pp. 1031–1038 (2005)
Harary, F.: Graph Theory. Addison Wesley, Reading (1969)
Hérault, L., Horaud, R.: Figure-ground discrimination: a combinatorial optimization approach. IEEE Trans. Pattern Anal. Mach. Intell. 15(9), 899–914 (1993)
Hung, H., Kröse, B.J.A.: Detecting f-formations as dominant sets. In: Proceedings of the 13th International Conference on Multimodal Interfaces, ICMI 2011, November 14–18 2011, Alicante, Spain, pp. 231–238 (2011). http://doi.acm.org/10.1145/2070481.2070525
Kawamura, T., Kanazawa, T., Ushio, T.: Evolutionarily and neutrally stable strategies in multicriteria games. IEICE Trans. Fundam. Electr. Commun. Comput. Sci. E96–A(4), 814–820 (2013)
Lozovanu, D., Solomon, D., Zelikovsky, A.: Multiobjective games and determining Pareto-Nash equilibria. Bul. Acad. Stiinte Rep. Moldova Mat. 3(49), 115–122 (2005)
Martin, D., Fowlkes, C., Tal, D., Malik, J.: A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: Proceedings of the 8th International Conference Computer Vision, vol. 2, pp. 416–423, July 2001
Pavan, M., Pelillo, M.: A new graph-theoretic approach to clustering and segmentation. In: Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 145–152 (2003)
Pavan, M., Pelillo, M.: Dominant sets and pairwise clustering. IEEE Trans. Pattern Anal. Mach. Intell. 29(1), 167–172 (2007)
Pelillo, M.: What is a cluster? Perspectives from game theory. In: Proceedings of the NIPS Workshop on Clustering Theory (2009)
Rota Bulò, S., Pelillo, M.: A game-theoretic approach to hypergraph clustering. IEEE Trans. Pattern Anal. Mach. Intell. 35(6), 1312–1327 (2013)
Shapley, L.S.: Equilibrium points in games with vector payoffs. Naval Res. Logistics Q. 1, 57–61 (1959)
Somasundaram, K., Baras, J.S.: Pareto nash replies for multiobjective games. In: Technical report, Institute for Systems Research (2008)
Somasundaram, K., Baras, J.S.: Achieving symmetric Pareto Nash equilibria using biased replicator dynamics. In: Proceedings of the 48th IEEE Conference Decision and Control, pp. 7000–7005 (2009)
Topchy, A.P., Law, M.H.C., Jain, A.K., Fred, A.L.N.: Analysis of consensus partition in cluster ensemble. In: Proceedings of the 4th IEEE International Conference on Data Mining (ICDM 2004), November 1–4 2004, Brighton, UK, pp. 225–232 (2004). http://dx.doi.org/10.1109/ICDM.2004.10100
Torsello, A., Rota Bulò, S., Pelillo, M.: Grouping with asymmetric affinities: a game-theoretic perspective. In: Proceedings of the IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 292–299 (2006)
Torsello, A., Pelillo, M.: Hierarchical pairwise segmentation using dominant sets and anisotropic diffusion kernels. In: Cremers, D., Boykov, Y., Blake, A., Schmidt, F.R. (eds.) EMMCVPR 2009. LNCS, vol. 5681, pp. 182–192. Springer, Heidelberg (2009)
Vascon, S., Mequanint, E.Z., Cristani, M., Hung, H., Pelillo, M., Murino, V.: A game-theoretic probabilistic approach for detecting conversational groups. In: Cremers, D., Reid, I., Saito, H., Yang, M.-H. (eds.) ACCV 2014. LNCS, vol. 9007, pp. 658–675. Springer, Heidelberg (2015)
Wang, M., Ye, Z.L., Wang, Y., Wang, S.X.: Dominant sets clustering for image retrieval. Signal Process. 88, 2843–2849 (2008)
Weibull, J.W.: Evolutionary Game Theory. MIT Press, Cambridge (2005)
Zeleny, M.: Games with multiple payoffs. Int. J. Game Theor. 4(4), 179–191 (1975)
Zhou, Z.H.: Ensemble Methods: Foundations and Algorithms. Chapman & Hall, Boca Raton (2012)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Zemene, E., Bulò, S.R., Pelillo, M. (2015). Dominant-Set Clustering Using Multiple Affinity Matrices. In: Feragen, A., Pelillo, M., Loog, M. (eds) Similarity-Based Pattern Recognition. SIMBAD 2015. Lecture Notes in Computer Science(), vol 9370. Springer, Cham. https://doi.org/10.1007/978-3-319-24261-3_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-24261-3_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-24260-6
Online ISBN: 978-3-319-24261-3
eBook Packages: Computer ScienceComputer Science (R0)