La fouille de données est définie comme le traitement d'une grande quantité de données afin d'y extraire des connaissances non triviales et utiles. Cette analyse permet de dégager de la masse d'informations des tendances, des regroupements de données et de formuler des hypothèses. Un des domaines de la fouille de données est la recherche de règles d'association. Les algorithmes utilisés en recherche de règles d'association ont généralement l'inconvénient de ne pouvoir identifier des règles dont un des termes est infréquent, mais qui appartient à une catégorie qui, elle, l'est. Les règles d'association multi-niveaux permettent d'identifier les associations impliquant des termes dont les niveaux de généralisation/spécialisation diffèrent. Les algorithmes de recherche de règles d'association multi-niveaux présentés à ce jour ont en commun la génération d'un nombre souvent très grand de règles redondantes. Notre contribution dans cette étude est constituée de la conception de deux algorithmes de recherche de règles d'association mutli-niveaux basés sur l'analyse formelle de concepts, ce qui permet de restreindre la génération des règles d'association aux seules règles informatives maximales. Nous avons également réalisé l'implémentation de ces deux algorithmes, en plus de celle d'un autre algorithme utilisé aux fins de comparaison dans la littérature. Nous avons finalement comparé expérimentalement ces trois implémentations et les résultats obtenus confirment l'intérêt de l'approche basée sur l'analyse formelle de concepts, tout en illustrant l'effet des optimisations apportés au traitement. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Treillis de Galois (treillis de concepts), Analyse formelle de concepts, Fouille de données (data mining), Règles d'association, Base de règles, Règles d'association multi-niveaux (règles d'association généralisées), Base de règles multi-niveaux (bases de règles généralisées).

La fouille de données est l'extraction non triviale d'informations implicites, inconnues et utiles à partir des données (Piatetsky-Shapiro & Frawley, 1991). Plus récemment, la notion de systèmes de gestion de base de données inductive (SGBDI) propose l'union de la base de données traditionnelle à la fouille de données et d'une base de motifs ou patrons de données. Ces derniers sont les agents fondamentaux dans les SGBDI. Dans ce mémoire le motif examiné est le concept formel. Cependant, pour un ensemble de données (nommé contexte formel dans l'AFC) de grande taille où les données sont fortement corrélées, l'extraction peut être difficile à cause des problèmes de combinatoire inhérente à cette structure. Il est vrai que l'extraction de la collection des concepts formels fréquents, donc un iceberg plutôt qu'un treillis, est une solution. Cependant, d'une part, pour un seuil de fréquence trop faible, l'extraction des concepts formels fréquents peut demeurer difficile et la combinatoire de l'extraction demeure. D'autre part, les utilisateurs pourraient préférer conserver le treillis mais appliquer une certaine relaxation sur le formalisme des concepts formels. Cette relaxation se ferait en acceptant des exceptions dans les concepts dont les seuils sur les exceptions seraient choisis par l'utilisateur. En dernier lieu, le contexte formel pourrait bien avoir des erreurs dans ses transactions. Ces erreurs pourraient donc être la cause du nombre indu de concepts formels extraits. Une relaxation au niveau de l'extraction des concepts formels pourrait être une solution à ce problème. Notre contribution se situe au niveau d'un motif en particulier et de son mode d'extraction. Ce mémoire propose donc un concept tolérant des exceptions bornées par des seuils, soit les concepts denses et explore la possibilité d'extraire un tel motif par l'algorithme incrémentaI par cardinalité. En dépit du fait que le concept ne soit plus formel mais tolérant des exceptions, les principales notions de l'analyse formelle de concepts, (e.g. la relation de précédence, le treillis) sont fortement désirées. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Concepts formels, Concepts denses, Treillis de concepts formels, Analyse formelle de concepts, Concepts tolérant des exceptions, Algorithme d'extraction de concepts, Représentation condensée.

L'évolution rapide des techniques de génération et de stockage de données a permis à de nombreux organismes la création de bases de données volumineuses, pour stocker l'information nécessaire à leurs activités. Ces bases de données qui deviennent de plus en plus importantes sont réellement peu exploitées, alors qu'elles cachent des connaissances potentiellement utiles pour l'organisation. L'extraction de ces informations enfouies dans ces masses de données est traitée par la fouille de données ("Data Mining"). Ce projet de mémoire traite plus particulièrement le problème d'extraction des informations sous forme de règles d'associations. Le problème de la pertinence et de l'utilité des règles extraites est un problème majeur de l'extraction des règles d'associations. Ce problème est lié au nombre important de règles extraites et à la présence d'une forte proportion de règles redondantes. Nombreuses techniques de réduction de la famille de règles ont été publiées. Dans ce contexte, les résultats obtenus par l'analyse formelle des concepts (AFC) ont permis de définir un sous-ensemble de l'ensemble des règles d'associations valides appelés bases informatives. La génération de ces bases informatives se fait par une extraction efficace des itemsets fermés fréquents et leurs générateurs minimaux associés. Les générateurs minimaux composent les prémisses minimales de ces règles alors que leurs fermetures composent les conclusions maximales de ces règles. Cependant un survol de la littérature montre que les générateurs minimaux composant l'antécédent et la conséquence de ces bases, contiennent encore de la redondance. Une représentation réduite de ces générateurs minimaux est utile pour révéler la relation d'équivalence parmi les générateurs minimaux. Une étude a été menée dernièrement dans ce sens dans laquelle l'algorithme DSFS_MINER a été proposé et validé, permettant l'extraction d'une représentation succincte sans perte d'informations des générateurs minimaux. Notre contribution dans ce projet réside d'une part, dans l'étude et l'expérimentation d'approches de représentations succinctes des générateurs minimaux, et d'autre part, dans la proposition d'un algorithme d'expansion permettant la dérivation de tous les générateurs minimaux afin de constituer la famille entière des générateurs minimaux du contexte d'extraction. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Data Mining, Règles d'associations, Analyse formelle des concepts, Générateurs minimaux, Itemset fermés, Générateur minimal, Représentation succincte des générateurs minimaux.