Dominant sets are a new graph-theoretic concept that has proven to be relevant in partitional (flat) clustering as well as image segmentation problems. However, in many computer vision applications, such as the organization of an image database, it is important to provide the data to be clustered with a hierarchical organization, and it is not clear how to do this within the dominant set framework. We address precisely this problem, and present a simple and elegant solution to it. To this end, we consider a family of (continuous) quadratic programs, which contain a parameterized regularization term that controls the global shape of the energy landscape. When the regularization parameter is zero the local solutions are known to be in one-to-one correspondence with dominant sets, but when it is positive an interesting picture emerges. We determine bounds for the regularization parameter that allow us to exclude from the set of local solutions those inducing clusters of size smaller than a prescribed threshold. This suggests a new (divisive) hierarchical approach to clustering, which is based on the idea of properly varying the regularization parameter during the clustering process. Straightforward dynamics from evolutionary game theory are used to locate the solutions of the quadratic programs at each level of the hierarchy. We apply the proposed framework to the problem of organizing a shape database. Experiments with three different similarity matrices (and databases) reported in the literature have been conducted, and the results confirm the effectiveness of our approach.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    Dominant sets and hierarchical clustering


    Contributors:
    Pavan, (author) / Pelillo, (author)


    Publication date :

    2003-01-01


    Size :

    464211 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Dominant Sets and Hierarchical Clustering

    Pavan, M. / Pelillo, M. / IEEE | British Library Conference Proceedings | 2003


    Abnormal behavior detection using dominant sets

    Alvar, M. / Torsello, A. / Sanchez-Miralles, A. et al. | British Library Online Contents | 2014


    Unsupervised Texture Segmentation by Dominant Sets and Game Dynamics

    Pavan, M. / Pelillo, M. / IEEE | British Library Conference Proceedings | 2003



    Hierarchical Learning of Dominant Constellations for Object Class Recognition

    Mekuz, Nathan / Tsotsos, John K. | Springer Verlag | 2007