Discrete Mathematics and Optimization Seminar
Jan. 5th, 2009
The Dominant-Set Framework for Pairwise Data Clustering
Marcello Pelillo
Ca' Foscari University, Venice, Italy
In this talk I'll provide an overview of the work we have been doing in my group on pairwise data clustering. We have developed a graph-theoretic framework for pairwise clustering which is motivated by the analogies between the intuitive concept of a cluster and that of a "dominant set" of vertices, a novel notion that generalizes that of a maximal clique to edge-weighted graphs. We established a correspondence between dominant sets and the extrema of a quadratic form over the standard simplex, thereby allowing us to use straightforward continuous optimization techniques such as replicator dynamics from evolutionary game theory. We have also addressed the problem of grouping out-of-sample examples after the clustering process has taken place: as it turns out, the very notion of a dominant set offers a simple and efficient way of doing this. Finally, we have provided a generalization of the dominant-set notion to the case of arbitrary (i.e., negative and/or asymmetric) affinities which is based on the notion of a Nash equilibrium, a fundamental concept fron noncooperative game theory. The approach has been tested extensively on on image segmentation and perceptual grouping problems.
[joint work with M. Pavan, A. Torsello, S. Rota Bulo']