• Directeur de thèse :
  • Engelbert Mephu Nguifo
  • Thèse soutenue le :
  • 2005-02-14

Résumé

Dans cette thèse, nous nous intéressons à la structure du treillis de concepts (ou treillis de Galois) et à ses applications à la fouille de données. Plusieurs travaux antérieurs ont montré l’intérêt des treillis de concepts à l’analyse de données, la classification supervisée ou non supervisée, à la recherche documentaire, et plus récemment à la recherche des règles d’association. Cependant devant la taille des bases de données utilisées en fouille de données, l’usage des systèmes basés sur les treillis de concepts est rendu difficile à cause des problèmes de combinatoire inhérente à cette structure.

L’algorithmique de génération des concepts formels et du treillis des concepts joue un rôle essentiel dans l’utilité pratique de cet outil mathématique. Afin de compléter les travaux comparatifs précédents utilisant généralement des contextes de données générés aléatoirement et de petite taille, nous avons donc entrepris dans cette thèse un travail de comparaisons de plusieurs algorithmes sur les données de la base de l’University of California Irvine (UCI). Les données de l’University of California Irvine (UCI) sont une base de référence pour les comparaison de systèmes de fouille de données, et permettent ainsi d’étudier l’adaptabilité des algorithmes sur ces données.

Au cours de cette étude, nous avons analysé le phénomène de la dualité objets/attributs sur les performances des algorithmes, en utilisant systématiquement le contexte de données et puis sa transposée pour engendrer les concepts formels. En effet, l’application d’un algorithme à un contexte formel ou à sa transposée peut avoir ou non une importance sur ses perfomances en pratique.

Cette étude comparative a permis de retrouver des résultats précédents montrant l’efficacité de l’algorithme de Ganter et celui de Bordat. Néanmoins sur certains contextes de grande taille, les temps d’exécution restent très élevés, et parfois aucun algorithme ne produit de résultat à cause de l’espace mémoire. En nous focalisant sur l’algorithme NextClosure et en utilisant le principe ``Diviser-pour-régner’’, nous proposons un nouvel algorithme de génération de concepts formels, nommé ScalingNextClosure. ScalingNextClosure décompose l’espace de recherche en partitions, et génère de manière indépendante les concepts pour chaque partition. Cette technique de décomposition et d’indépendance des partitions lui permet de gérer efficacement la mémoire centrale et les entrées/sorties pour être capable de traiter efficacement des contextes de données volumineux, bien évidemment à condition que le contexte de données tienne en mémoire centrale.

Une comparaison expérimentale sur une machine séquentielle montre en général un gain d’un facteur en moyenne égal à 10, par rapport à NextClosure. L’indépendance des partitions est un atout pour la mise en oeuvre de ScalingNextClosure dans un environnement parallèle et distribué.

En fouille de données, la problématique d’extraction des itemsets fermés fréquents pour la recherche de règles d’association, se prête bien à une mise en oeuvre de ScalingNextClosure. Nous avons donc étendu ScalingNextClosure pour traiter ce problème. Le nouvel algorithme, nommé PFC, utilise la mesure du support pour élaguer l’espace de recherche dans une partition. Une comparaison expérimentale avec une des méthodes les plus efficaces actuellement, a été réalisée sur une architecture séquentielle, et donne des résultats encourageants.

Une plateforme VLDMining a été réalisée en Java, et contient l’ensemble des outils développés dans le cadre de cette thèse.

Mots-Clés : treillis de concepts, treillis de Galois, analyse de concepts formels, algorithme, partitionnement, dualité, transposé, règles d’association, fouille de données, extraction de connaissances, itemsets fermés.