Path-Based Dominant-Set Clustering

Although off-the-shelf clustering algorithms, such as those based on spectral graph theory, do a pretty good job at finding clusters of arbitrary shape and structure, they are inherently unable to satisfactorily deal with situations involving the presence of cluttered backgrounds. On the other hand, dominant sets, a generalization of the notion of maximal clique to edge-weighted graphs, exhibit a complementary nature: they are remarkably effective in dealing with background noise but tend to favor compact groups. In order to take the best of the two approaches, in this paper we propose to combine path-based similarity measures, which exploit connectedness information of the elements to be clustered, with the dominant-set approach. The resulting algorithm is shown to consistently outperform standard clustering methods over a variety of datasets under severe noise conditions.