HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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. 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 spanning-tree based efficient algorithms for general graphs. Our experiments illustrate the role of D as a scale parameter providing information on the relationship between clusters within a clustering and in-between two clusterings. They also show the advantages of our built-in mapping over classical cluster comparison measures such as the variation of information (VI).
Complete list of metadata

Cited literature [49 references]  Display  Hide  Download

https://hal.inria.fr/hal-01514872
Contributor : Romain Tetley Connect in order to contact the contributor
Submitted on : Tuesday, July 16, 2019 - 2:33:09 PM
Last modification on : Thursday, January 20, 2022 - 5:32:48 PM

File

RR-9063-family-matching.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01514872, version 4

Collections

Citation

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, pp.1-45. ⟨hal-01514872v4⟩

Share

Metrics

Record views

479

Files downloads

3875