Algorithmes de construction et maintien de treillis de Galois


La construction de treillis de Galois, appelée encore analyse de concepts formels (ACF), offre de techniques de découverte d'abstraction potentiellement utiles dans des ensembles de données concrètes. Ces techniques consistent à extraire d'une collection d'individus des groupes décrits en intention, appelés concepts, et de les ordonne dans un treillis. Pour ce faire, elle s'appuient sur les notions algébriques de correspondance de Galois entre deux ensembles (ici un ensemble d'objets et un autre d'attributs) et de couple fermé (cf. annexe). Par rapport au reste des techniques de hiérarchisation l'ACF se distingue par sa simplicité, par son fondement mathématique et par les propriétés structurelles intéressantes de son résultat (l'existence d'un infimum et d'un supremum dans le treillis). Son atout principal est d'être complètement générique. En effet, un concept formel peut se substituer, selon le contexte, à un concept d'un domaine modélisé (au sein d'une ontologie), à une classe d'objets (en programmation par objets) ou à une catégorie d'individus (en segmentation d'une population).

L'utilisation des treillis de Galois en tant qu'outil de hiérarchisation a démarré au début des années 80 avec les travaux, entre autres, de R. Godin à Montréal. Les développements théoriques, à l'origine de l'ACF en tant que domaine scientifique, sont dûs à l'algébriste R. Wille de Darmstadt, en Allemagne.
 

Directions de recherche:

Sujets de Maîtrise et Doctorat: