|
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']
|
|
|
|