L'extraction de connaissances dans les bases de données, également appelé data mining, désigne le processus non trivial permettant d'extraire des informations et des connaissances utiles qui sont enfouies dans les bases de données, les entrepôts de données (data warehouse) ou autres sources de données. Les recherches en ce domaine sont motivées par la croissance très rapide des volumes de données stockées et le potentiel de telles informations pour l'aide à la décision dans de nombreux domaines. Dans ce mémoire, nous traitons du problème de la génération efficace des règles d'association. Une règle d'association est une implication conditionnelle entre ensembles d'attributs binaires appelés items. Dans l'ensemble des travaux existants, ce problème est décomposé en deux sous-problèmes qui sont la recherche des ensembles fréquents d'items et la génération des règles d'association à partir de ces ensembles. Le premier sous-problème a une complexité exponentielle dans la taille de la relation en entrée et nécessite de parcourir à plusieurs reprises la totalité de la relation. L'extraction des ensembles fréquents d'items constitue donc la phase la plus coûteuse en termes de temps d'exécution et d'espace mémoire pour les algorithmes d'extraction des règles d'association. Nous proposons une nouvelle sémantique pour le problème de l'extraction des règles d'association basée sur la connexion de Galois d'une relation binaire finie. Utilisant cette sémantique, nous démontrons que les ensembles fermés fréquents d'items constituent une base, c'est à dire un ensemble générateur non redondant, pour les ensembles fréquents d'items et les règles d'association. Nous proposons deux nouveaux algorithmes, nommés Close et A-Close, permettant l'extraction des ensembles fermés fréquents d'items, à partir desquels les ensembles fréquents d'items et les règles d'association peuvent être dérivés sans accéder au jeu de données. Les résultats expérimentaux démontrent que ces algorithmes permettent de réduire les temps d'extraction des règles d'association dans le cas de jeux de données constitués de données denses ou corrélées. Utilisant la sémantique définie, nous proposons d'améliorer la pertinence et l'utilité des règles d'association extraites en limitant l'extraction à des bases pour les règles d'association. Nous adaptons pour cela les bases pour les règles d'implication définies en analyse de données et nous définissons de nouvelles bases constituées des règles non redondantes d'antécédents minimaux et de conséquences maximales à partir des ensembles fermés fréquents. Nous proposons également des algorithmes efficaces de génération de ces bases.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00467764 |
| Date | 31 January 2000 |
| Creators | Pasquier, Nicolas |
| Publisher | Université Blaise Pascal - Clermont-Ferrand II |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.002 seconds