Jean Creusefond (GREYC, Caen)

La question de l’évaluation des algorithmes de détection de communauté (ou algorithmes de clustering) est épineuse. La définition d’une communauté étant floue, l’évaluation des méthodes de détections est elle-même hautement dépendante du contexte et sujette à conflits et confusions.

Il y a essentiellement deux manières d’évaluer un algorithme de clustering :

  • Comparaison entre les résultats et une vérité de terrain via des fonctions de comparaison entre clustering;
  • Quantification de la qualité via des fonctions de qualité mesurant des caractéristiques topologiques des clusters jugées essentielles.

L’évaluation expérimentale est coûteuse sur plusieurs points : les jeux de données sont rares et parfois privatifs et les fonctions de comparaison ont souvent une complexité importante. Il semble essentiel de fixer une méthodologie qui mesure expérimentalement la pertinence des dites fonctions de qualité afin de faire le pont entre les deux méthodes d’évaluation.

Dans cette optique, nous avons cherché des corrélations entre l’évaluation fournie par différentes fonctions de qualité et celle des vérités de terrain afin d’identifier les cas où une fonction de qualité est pertinente. L’application de cette méthodologie sur un jeu de données public a apporté des conclusions intéressantes

  • Il existe des ensembles de vérités de terrain où les fonctions de qualité ont le même comportement. Nous appelons ces ensembles des contextes, car ils correspondent à des types de données spécifiques (sites web de réseaux sociaux, graphe bipartite d’appartenance à des groupes, réseaux de citation)
  • Dans chaque contexte on peut préconiser des fonctions de qualité qui fournissent des résultats proches des vérités de terrain considérées.

Ainsi, il est maintenant possible de justifier le choix d’une fonction de qualité en explicitant le contexte visé, et d’éviter le processus coûteux de comparaison avec des données expérimentales.