Chapitre 1
Fondements mathematiques pour
l'extraction de regles d'association
1.1 Introduction
Avec le développement des outils informatiques, nous
avons assisté ces dernières années a un véritable
déluge d'informations stockées dans de grandes bases de
données scientifiques, économiques, financières,
médicales, etc [42]. Le besoin d'interpréter et d'analyser ces
grandes masses de données a suscité beaucoup
d'intérêt. Ainsi, la mise au point de nouvelles techniques
d'analyse est devenue un réel défi pour la communauté
scientifique. Pour répondre a cette pénurie de connaissances sur
les données, de nouvelles méthodes d'extraction de l'information
ont vu le jour, regroupées sous le terme générique de
fouille de données [11]. La fouille de données est un domaine de
recherche en plein essor visant a exploiter les grandes quantités de
données collectées dans divers domaines d'application de
l'informatique. Ce domaine pluri-disciplinaire se situe au confluent de
différents domaines, tels que les statistiques, les bases de
données, l'algorithmique, les mathématiques, l'intelligence
artificielle, etc [54]. On lui donne d'autres appellations, comme par exemple
extraction de connaissances dans les bases de données, traitement de
motifs de données ou encore exploration de données [54]. Selon
Frawley et al. [25] : L'Extraction de Connaissances dans les Bases de
Données (ou Knowledge Discovery in Databases)
désigne le processus interactif et itératif non trivial
d'extraction de connaissances implicites, précédemment inconnues
et potentiellement utiles a partir de données stockées dans les
bases de données.
Ce domaine de recherche a commencé a être
distingué en 1989, quand G. Piatetsky-
Shapiro a organisé la premiere réunion de
chercheurs et d'utilisateurs sur l'extraction automatique de connaissances dans
les grandes bases de données. Une autre étape marquante a
été la création du projet QUEST par IBM en 1993, source de
nombreux algorithmes et méthodes [4].
L'idée sous-jacente de la fouille de données est
donc d'extraire les connaissances cachées A partir d'un ensemble de
données. Le terme fouille de données regroupe un certain nombre
de tAches, telles que la prédiction, le regroupement par similitude, la
classification, l'analyse des clusters, etc [11]. Ces tAches sont elles
mêmes divisées en plusieurs techniques, telles que les regles
d'association, les arbres de décisions, les réseaux de neurones,
etc [24, 42].
Dans ce mémoire, nous allons nous intéresser aux
regles d'association [1]. L'extraction des regles d'association est l'un des
principaux problemes de la fouille de données. Ce probleme, introduit
par Agrawal et al. [1], fut développé pour l'analyse de bases de
données de transactions de ventes. Chaque transaction est
constituée d'une liste d'articles achetés, afin d'identifier les
groupes d'articles achetés le plus fréquemment ensemble [47].
L'analyse d'associations, appliquée aux données des points de
vente, est alors appelée analyse du panier de la ménagère.
L'analyse des associations part des données les plus fines qui composent
une transaction : les ventes des articles élémentaires. La
recherche des associations vise alors a retrouver les corrélations qui
pourraient exister entre n produits (par exemple, les acheteurs de
salade et de tomates achetent de l'huile dans 80% des cas), mais aussi entre
les comportements de produits (quand les ventes de X augmentent alors
les ventes de Y augmentent dans 80% des cas) [42]. L'extraction de
regles d'association a donc pour intérêt l'identification de
corrélations significatives, cachées entre les données
d'une base de données. Les corrélations obtenues peuvent
être utiles pour les utilisateurs finaux (experts, décideurs,
etc.) qui peuvent les exploiter pour différents objectifs.
Dans ce chapitre, nous allons présenter la
problématique d'extraction des regles d'association basée sur les
itemsets fréquents. Ensuite, nous allons présenter les fondements
mathématiques de l'analyse formelle de concepts et leur connexion avec
la dérivation de bases génériques de regles
d'association.
|
