Skip to Main content Skip to Navigation
Conference papers

Comparaison de deux clusterings par couplage entre clusters de clusters

Résumé : Le clustering est une tâche essentielle en analyse de données. La variété des méthodes disponibles rend celle-ci ardue. Diverses stratégies ont été proposées pour analyser la stabilité d'un clustering en fonction des paramètres de l'algorithme l'ayant généré, ou pour comparer des clusterings produits par des algorithmes différents. Dans cet article, nous proposons une nouvelle classe de méthodes formant des groupes de clusters (meta-clusters) dans chaque clustering, et établissant une correspondance entre ceux-ci. Nous définissons le graphe d'intersection de deux clusterings en associant à chaque cluster un sommet et en reliant deux clusters dont l'intersection est non nulle par une arête pondérée par le poids de leur intersection. Étant donné une borne supérieure D sur le diamètre du graphe induit par les clusters des meta-clusters, nous formalisons et analysons le problème D-family-matching. Nous montrons que ce problème est NP-complet, développons des algorithmes de programmation dynamique pour certaines classes de graphes (arbres en particulier), et concevons des algorithmes efficaces basés sur des arbres couvrants pour des graphes généraux. Nous illustrons à travers des expériences le rôle de D comme un paramètre d'échelle apportant des informations sur la relation entre deux clusters. Nous montrons également les avantages de notre appariement face aux méthodes classiques de comparaison de clusters telles que la variation d'information (VI). Enfin, pour des clusterings générés par K-means, nous montrons que notre algorithme de programmation dynamique permet d'estimer le nombre effectif de clusters.
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/hal-01774440
Contributor : Dorian Mazauric <>
Submitted on : Monday, April 23, 2018 - 3:53:25 PM
Last modification on : Monday, October 12, 2020 - 10:28:55 AM
Long-term archiving on: : Wednesday, September 19, 2018 - 1:16:10 AM

File

algotel.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01774440, version 1

Citation

Frédéric Cazals, Dorian Mazauric, Romain Tetley, Rémi Watrigant. Comparaison de deux clusterings par couplage entre clusters de clusters. ALGOTEL 2018 - 20èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2018, Roscoff, France. ⟨hal-01774440⟩

Share

Metrics

Record views

201

Files downloads

406