Université du Québec à Montréal, Canada
9/6/2000 à 9h30
Grand amphithéatre, INRIA Rhône-Alpes, Montbonnot
Abstract
La théorie des treillis de Galois a débuté dans les années 70 avec les travaux de Barbut et Monjardet en France. A l'origine, il s'agissait de découvrir les fermés d'une relation binaire entre deux ensembles d'entités. Plus tard, l'algébriste allemand R. Wille a proposé une version orienté vers la construction explicite du treillis que les fermés forment qu'il a nommé ``formal concept analysis'' (FCA). Depuis, le domaine s'est largement étendu et aujourd'hui il constitue une approche puissante vers la hiérarchisation de grandes volumes de données et d'extraction de connaissances avec de multiples applications dans la construction et la réorganisation de hiérarchie de classes en génie logiciel à objets, la découverte des règles d'association pour l'analyse du panier du consommateur, la structuration de grandes bases de connaissances, etc.
La découverte d'une correspondance de Galois entre deux ensembles et des jeux respectifs de sous-ensembles fermés se retrouve à la base d'un bon nombre de problèmes abstraits dans de domaines aussi variés que l'algèbre linéaire, la recherche opérationnelle, la spécification et vérification formelle de logiciels, etc. Cela explique la variété d'algorithmes qui peuvent être utilisés pour la construction des fermés et/ou de leur treillis. Avec l'arrivée des applications de plus en plus exigeantes, faisant apparaître des grands volumes de données, il est légitime de s'interroger sur les performances de chacun des algorithmes afin de pouvoir en choisir un, le plus adapté à la situation concernée. Cependant, ces algorithmes se distinguent par leur résultat : alors qu'un bon nombre se limitent à la découverte des fermés, les autres construisent également le graphe du treillis (le diagramme de Hasse).
Les études comparatives précédentes ont soit ignoré les aspects divergentes et restent donc incomplètes, soit elles ont utilisée, dans le souci de rendre tous les algorithmes comparables selon leur résultat, des complétions inefficaces (elles ne sont donc pas équitables). Une des prémisses pour une comparaison complête et équitable est la définition d'un algorithme efficace de construction du diagramme de Hasse à partir de l'ensemble de tous les fermés.
Durant mon séjour post-doctorale à Montréal, j'ai été à l'origine de la conception d'un tel algorithme. Contrairement aux algorithmes existants qui construisent le treillis en considérant chaque fermé séparément, notre algorithme se base sur une vision incrémentale sur le treillis en construction. Ainsi, les fermés sont considérés dans un ordre qui est extension linéaire de l'ordre dans le treillis. A chaque étape, un fermé est ``inséré'' dans la structure partielle constituée par les fermés préalablement traités, moyennant une comparaison avec les éléments minimaux de cette structure qui révèle ses successeurs immédiats. Des propriétés fondamentales des treillis de Galois sont utilisées pour rendre cet insertion la plus efficace possible.
L'étude analytique de la complexité de la procédure montre qu'assymptotiquement, elle est bornée par le produit du nombre des fermés, la taille du plus petit des deux ensembles d'entités et la largeur du treillis (taille d'une anti-chaîne maximale).
Travail effectué avec Rokia Missaoui
|
http://exmo.inria.fr/seminars/2000valtchev.html
|