A Game-Theoretic Framework for Similarity-Based Data Clustering

The problem of clustering consists in organizing a set of objects into groups or clusters, in a way as to have similar objects grouped together and dissimilar ones organized into different groups. This problem is of wide interest in many contexts and has been addressed by researchers in many disciplines. Unfortunately, it is inherently ill-posed, since any given set of objects can be clustered in drastically different ways and due to the intrinsic ambiguity a vast collection of algorithms has spread in the literature over time in order to improve existing approaches on specific applications. In particular we distinguish two main classes of algorithms: feature-based, where objects are represented as points in a metric space with distances reflecting the dissimilarity relations, and similarity-based, where objects are described indi-rectly by their respective similarity relations. Recently, an interest around purely similarity-based techniques has grown considerably, because there are numerous ap-plication domains where it is not possible to find satisfactory features, but it is more natural to provide a measure of similarity