Décomposition de graphes comme outil de regroupement et de visualisation en fouille de données

La fouille de données est un domaine largement étudié et les méthodes utilisées pour l'aborder ont fait le sujet de nombreux travaux. Ces méthodes reposent en général sur les outils de classification classiques supervisés et non supervisés. Ces méthodes forment des clusters disjoints, attribuant les éléments à un seul groupe. Dans de nombreux cas réels, les éléments à classer peuvent appartenir à plusieurs groupes. Nous abordons cette problématique avec une nouvelle approche basée sur la décomposition des graphes. Cette décomposition est basée sur les séparateurs minimaux complets qui sont des ensembles de sommets formant des cliques dont le retrait déconnecte le graphe en une ou plusieurs composantes et pour lesquels des résultats en théorie des graphes donnent des outils algorithmiques puissants. Cette décomposition fournit des groupes d'éléments recouvrants. Nous dérivons de cette décomposition un outil de visualisation permettant de mettre en évidence la structure du graphe formé par ces données. Nous avons travaillé sur des données issues de 2 domaines (bioinformatique et fouille de données textuelles) afin de valider cette approche de décomposition. 1. Bioinformatique : Les mesures de l'activité génique des cellules vivantes par des biopuces fournissent des données sous forme de matrices symétriques. Nous construisons des graphes de gènes en fixant des seuils sur ces matrices. Nous examinons la stucture de ces graphes afin de mettre en évidence des groupes de gènes qui ont des profils d'expression similaires et dont on peut estimer la probabilité de participation à des fonctions similaires. 2. Fouille de données textuelles : les relations entre données textuelles d'un corpus donné sont modélisées par un graphe de termes. Ces relations sont fondées soit sur la cooccurence, soit sur des variations linguistiques. Nous proposons une méthode de visualisation basée sur la décomposition de graphes en atomes (sous-graphes recouvrants sans séparateurs minimaux complets). Ces atomes sont structurés dans un graphe appelé graphe des atomes. Ce graphe des atomes met en évidence les thématiques donnant une vue globale sur l'ensemble des documents contenus dans un corpusCLERMONT FD-BCIU Sci.et Tech. (630142101) / SudocSudocFranceF