Classification, analyse de la similitude et hypergraphes

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.A classical purpose of clustering is to make explicit the relationship between elements, and between the clusters, 'i.e.' sets of elements. Partitions and hierarchies are often used. Clusters of a pyramid are parts of some path; trees and arboreal set systems are common in biology. Most of these models require an 'a priori' structure choice and lead to NP-hard problems. Within similarity analysis (Flament 'et al.', 1962-1981), we search a smallest 'rigidity graph' of a given hypergraph, such that hyperedges are connected classes of the graph. Many methods are classical to generate a set system from a dissimilarity : maximal cliques, balls, 2-balls, realizations (Brucker, 2003). We prove our problem is NP-hard in general and with the first three methods; there is an algorithm in O(n4) operations for realisations. We identify hypercycles - admitting a cycle as graph of rigidity - O(n4) operations and study circular dissimilarities, whose clusters form a hypercycle, in relation with the model of Hubert 'et al.' (1998). We apply these methods to memory psychology, text analysis and genetic data.PARIS3-BU (751052102) / SudocSudocFranceF