Comparaison de deux clusterings par couplage entre clusters de clusters - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

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.
Fichier principal
Vignette du fichier
algotel.pdf (291.18 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01774440 , version 1 (23-04-2018)

Identifiants

  • HAL Id : hal-01774440 , version 1

Citer

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⟩
236 Consultations
575 Téléchargements

Partager

Gmail Facebook X LinkedIn More