Comparing two clusterings using matchings between clusters of clusters

Abstract : Clustering is a fundamental problem in data science, yet, the variety of clustering methods and their sensitivity to parameters make clustering hard. To analyze the stability of a given clustering algorithm while varying its parameters, and to compare clusters yielded by different algorithms, several comparison schemes based on matchings, information theory and various indices (Rand, Jaccard) have been developed. We go beyond these by providing a novel class of methods computing meta-clusters within each clustering-- a meta-cluster is a group of clusters, together with a matching between these. Altogether, these pieces of information help assessing the coherence between two clusterings. More specifically, let the intersection graph of two clusterings be the edge-weighted bipartite graph in which the nodes represent the clusters, the edges represent the non empty intersection between two clusters, and the weight of an edge is the number of common items. We introduce the so-called D-family-matching problem on intersection graphs, with D the upper-bound on the diameter of the graph induced by the clusters of any meta-cluster. First we prove NP-completeness results and unbounded approximation ratio of simple strategies. Second, we design exact polynomial time dynamic programming algorithms for some classes of graphs (in particular trees). Then, we prove efficient algorithms, based on spanning trees, for general graphs. Practically, we illustrate the ability of our algorithms to identify relevant meta-clusters between a given clustering and an edited version of it. By comparing our scores against the Variation of Information, we also show the insights yielded by parameter D.
Type de document :
[Research Report] RR-9063, INRIA Sophia Antipolis - Méditerranée; Universite Cote d'Azur. 2017
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger
Contributeur : Dorian Mazauric <>
Soumis le : vendredi 29 septembre 2017 - 08:37:44
Dernière modification le : jeudi 11 janvier 2018 - 16:54:47
Document(s) archivé(s) le : samedi 30 décembre 2017 - 12:44:46


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01514872, version 2



Frédéric Cazals, Dorian Mazauric, Romain Tetley, Rémi Watrigant. Comparing two clusterings using matchings between clusters of clusters. [Research Report] RR-9063, INRIA Sophia Antipolis - Méditerranée; Universite Cote d'Azur. 2017. 〈hal-01514872v2〉



Consultations de la notice


Téléchargements de fichiers