Clustering stability revealed by matchings between clusters of clusters

Frédéric Cazals 1 Dorian Mazauric 1 Romain Tetley 1
1 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
Résumé : Le clustering est une tâche essentielle en analyse de données, mais 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 bien comparer des clusterings produits par des algorithmes différents. Nous allons au delà de celles-ci, en proposant une nouvelle classe de méthodes formant des groupes de clusters (meta-clusters) dans chaque clustering, et établissant une correspondance entre ceux-ci. Plus spécifiquement, définissons le graphe intersection de deux clusterings comme le graphe biparti dont les sommets sont les clusters, chaque arête étant pondérée par le nombre de points communs à deux clusters. Nous définissons les (k,D) et D-family-matching problèmes à partir du graphe intersection, avec k le nombre de meta-clusters et D une borne supérieure sur le diamètre du graphe induit par les clusters des meta-clusters. Dans un premier temps, nous établissons des résultats de difficulté et d'inaproximabilité. Dans un second temps, nous développons des algorithmes de programmation dynamique pour certaines classes de graphes (arbres en particulier). Enfin, nous concevons des algorithmes efficaces, basés sur des arbres couvrants, pour des graphes généraux. Des résultats expérimentaux sont présentés dans deux directions. D'une part, nous montrons comment nos algorithmes peuvent identifier des parties stables entre un clustering et une version éditée de celui-ci. D'autre part, nous utilisons cette faculté pour identifier des instabilités notoires de l'algorithme k-means.
Type de document :
Rapport
[Research Report] RR-8992, Inria Sophia Antipolis; Université Côte d'Azur. 2016, pp.51
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01410396
Contributeur : Dorian Mazauric <>
Soumis le : mardi 6 décembre 2016 - 16:28:42
Dernière modification le : jeudi 11 janvier 2018 - 16:48:50
Document(s) archivé(s) le : mardi 21 mars 2017 - 09:54:11

Fichier

RR-8992-partition-matching.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01410396, version 1

Collections

Citation

Frédéric Cazals, Dorian Mazauric, Romain Tetley. Clustering stability revealed by matchings between clusters of clusters. [Research Report] RR-8992, Inria Sophia Antipolis; Université Côte d'Azur. 2016, pp.51. 〈hal-01410396〉

Partager

Métriques

Consultations de la notice

235

Téléchargements de fichiers

93