What Is a Cluster: Perspectives from Game Theory

author: Marcello Pelillo, University Ca' Foscari
published: Jan. 19, 2010,   recorded: December 2009,   views: 718


Related Open Educational Resources

Related content

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.
Lecture popularity: You need to login to cast your vote.


Instead of insisting on the idea of determining a partition of the input data, and hence obtaining the clusters as a by-product of the partitioning process, in this presentation I propose to reverse the terms of the problem and attempt instead to derive a rigorous formulation of the very notion of a cluster. Clearly, the conceptual question “what is a cluster?” is as hopeless, in its full generality, as is its companion “what is an optimal clustering?” which has dominated the literature in the past few decades, both being two sides of the same coin. An attempt to answer the former question, however, besides shedding fresh light into the nature of the clustering problem, would allow us, as a consequence, to naturally overcome the major limitations of the partitional approach alluded to above, and to deal with more general problems where, e.g., clusters may overlap and clutter elements may get unassigned, thereby hopefully reducing the gap between theory and practice.

In our endeavor to provide an answer to the question raised above, we found that game theory offers a very elegant and general perspective that serves well our purposes. Hence, in the second, constructive part of the presentation I will describe a game-theoretic framework for clustering [21, 25, 22] which has found applications in fields as diverse as computer vision and bioinformatics. The starting point is the elementary observation that a “cluster” may be informally defined as a maximally coherent set of data items, i.e., as a subset of the input data C which satisfies both an internal criterion (all elements belonging to C should be highly similar to each other) and an external one (no larger cluster should contain C as a proper subset). We then formulate the clustering problem as a non-cooperative clustering game. Within this context, the notion of a cluster turns out to be equivalent to a classical equilibrium concept from (evolutionary) game theory, as the latter reflects both the internal and external cluster conditions mentioned above.

See Also:

Download slides icon Download slides: nipsworkshops09_pelillo_cpg_01.pdf (4.9 MB)

Help icon Streaming Video Help

Link this page

Would you like to put a link to this lecture on your homepage?
Go ahead! Copy the HTML snippet !

Write your own review or comment:

make sure you have javascript enabled or clear this field: