Classification, analyse de la similitude et hypergraphes

Résumé du livre

L'un des objectifs de la classification est d'expliciter les relations entre éléments et classes. Les modèles usuels sont les hiérarchies, les pyramides et les systèmes de classes arborés, classiques en biologie. Ils nécessitent de faire le choix d'une structure pour approcher les données, et la plupart mènent à des problèmes NP-difficiles. Dans le cadre de l'analyse de la similitude (Flament 'et al.',1962-1981) nous cherchons un 'graphe de rigidité' le plus petit possible, tel que les classes d'un système donné en soient des classes connexes. Il existe plusieurs méthodes pour engendrer un système de classes à partir d'une dissimilarité : cliques maximales, boules, 2-boules, réalisations (Brucker, 2003). Le problème est NP-difficile dans le cas général et pour les trois premières méthodes ; il existe un algorithme en O(n4) pour les réalisations. Nous identifions les 'hypercycles', dont un graphe de rigidité est un cycle, en O(n4) opérations et analysons les dissimilarités circulaires, dont les classes forment un hypercycle, en relation avec le modèle de Hubert 'et al.' (1998). Nous appliquons ces méthodes à des données issues de la psychologie de la mémoire, de l'analyse de données textuelles et de la génétique.