Clustering refers to the process of extracting maximally coherent groups from a set of objects using pairwise, or high-order, similarities. Traditional approaches to this problem are based on the idea of partitioning the input data into a predetermined number of classes, thereby obtaining the clusters as a by-product of the partitioning process. In this chapter, we provide a brief review of our recent work which offers a radically different view of the problem and allows one to work directly on non-(geo)metric data. In contrast to the classical approach, in fact, we attempt to provide a meaningful formalization of the very notion of a cluster in the presence of non-metric (even asymmetric and/or negative) (dis)similarities and show that game theory offers an attractive and unexplored perspective that serves well our purpose. To this end, we formulate the clustering problem in terms of a non-cooperative “clustering game” and show that a natural notion of a cluster turns out to be equivalent to a classical (evolutionary) game-theoretic equilibrium concept. Besides the game-theoretic perspective, we exhibit also characterizations of our cluster notion in terms of optimization theory and graph theory. As for the algorithmic issues, we describe two approaches to find equilibria of a clustering game. The first one is based on the classical replicator dynamics from evolutionary game theory, the second one is a novel class of dynamics inspired by infection and immunization processes which overcome their limitations. Finally, we show applications of the proposed framework to matching problems, where we aim at finding correspondences within a set of elements. In particular, we address the problems of point-pattern matching and surface registration.

A game-theoretic approach to pairwise clustering and matching / Torsello, A.; Albarelli, A.; Rota Bulò, S.; Rodolà, E.; Pelillo, M.. - (2013), pp. 179-216. [10.1007/978-1-4471-5628-4].

A game-theoretic approach to pairwise clustering and matching

E. Rodolà;
2013

Abstract

Clustering refers to the process of extracting maximally coherent groups from a set of objects using pairwise, or high-order, similarities. Traditional approaches to this problem are based on the idea of partitioning the input data into a predetermined number of classes, thereby obtaining the clusters as a by-product of the partitioning process. In this chapter, we provide a brief review of our recent work which offers a radically different view of the problem and allows one to work directly on non-(geo)metric data. In contrast to the classical approach, in fact, we attempt to provide a meaningful formalization of the very notion of a cluster in the presence of non-metric (even asymmetric and/or negative) (dis)similarities and show that game theory offers an attractive and unexplored perspective that serves well our purpose. To this end, we formulate the clustering problem in terms of a non-cooperative “clustering game” and show that a natural notion of a cluster turns out to be equivalent to a classical (evolutionary) game-theoretic equilibrium concept. Besides the game-theoretic perspective, we exhibit also characterizations of our cluster notion in terms of optimization theory and graph theory. As for the algorithmic issues, we describe two approaches to find equilibria of a clustering game. The first one is based on the classical replicator dynamics from evolutionary game theory, the second one is a novel class of dynamics inspired by infection and immunization processes which overcome their limitations. Finally, we show applications of the proposed framework to matching problems, where we aim at finding correspondences within a set of elements. In particular, we address the problems of point-pattern matching and surface registration.
2013
Similarity-based pattern analysis and recognition
978-1-4471-5627-7
pairwise; clustering; non-metric similarities
02 Pubblicazione su volume::02a Capitolo o Articolo
A game-theoretic approach to pairwise clustering and matching / Torsello, A.; Albarelli, A.; Rota Bulò, S.; Rodolà, E.; Pelillo, M.. - (2013), pp. 179-216. [10.1007/978-1-4471-5628-4].
File allegati a questo prodotto
File Dimensione Formato  
Pelillo_Game-Theoretic_2013.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 1.16 MB
Formato Adobe PDF
1.16 MB Adobe PDF   Contatta l'autore

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/1252562
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact