Soutenance mémoire
Les progrès des technologies de l’information de la dernière décennie offrent de nombreux moyens pour collecter et stocker une quantité de données extrêmement importante et véhiculent une quantité d’informations prodigieuses dans plusieurs secteurs d’activité, tels que Commerce, Finance, Télécommunication, Agriculture, Médecine, Contrôle de qualité, etc. Cependant, l’exploitation optimale de ces masses de données reste encore difficile. C’est pourquoi, au carrefour de thèmes de recherche variés, des différents travaux (Guillet et Hamilton, 2007 [GH07a, GH07b] ; Massaglia et al., 2007 [MPTM07, PTM07] ; Baqueiro et al., 2009 [BWMC09] ; Toussain, 2011 [Tou11] ; Han et Kamber, 2012 [HKP12] ; Bertrand et Diatta, 2013 [BD13] ; Serrano, 2014 [Ser14] ; Ruiz, 2014 [Rui14]) se sont intéressés à l’extraction de ce flot d’information, en intégrant des techniques de fouille des masses de données. Dans ce mémoire, nous nous intéressons principalement au problème de l’extraction des règles d’association, l’une des techniques les plus utilisées en fouille de données, et ses applications en didactique des mathématiques.
Une règle d’association est une quasi-implication entre deux motifs de la forme X→Y , où X et Y sont des motifs disjoints (X, Y ⊆ I, X ∩Y = ∅), appelés respectivement la prémisse (ou l’antécédent) et le conséquent (ou la conclusion) de la règle. Cela peut se traduire par « si X, alors Y ». Notons que X et Y peuvent être composés de plusieurs attributs, mais un attribut ne peut pas figurer simultanément dans les deux parties de la règle. Un exemple souvent cité de ce sujet concerne l’analyse du panier de la ménagère permettant d’analyser les tickets de caisse des clients afin de comprendre leurs habitudes de consommation, d’agencer les rayons du magasin, d’organiser les promotions, de gérer les stocks, dans le naturel but d’améliorer le profit.
Extraction de connaissances à partir de données – ECD
Sur les processus de l’ECD
Au début des années 90, Piatetsky-Shapiro [PSF91, FPSM92] introduit le terme de « Knowledge Discovery from Databases », abrégé par la suite en KDD, dont l’équivalent français est Extraction de Connaissances à partir de Données (ECD). Celui-ci est une discipline qui recoupe les domaines des bases de données, des statistiques, de l’intelligence artificielle et de l’interface homme/machine. Son objectif est de découvrir automatiquement des informations généralisables en connaissances nouvelles sous le contrôle des experts des données. Cela nécessite la conception et la mise au point de méthodes pour extraire les informations essentielles et cachées qui seront interprétées par les experts afin de les transformer, si possible, en connaissances. Il y a plusieurs définitions pour l’ECD, parmi lesquelles les suivantes sont les plus utilisées par la communauté scientifique.
Définition 1. L’ECD désigne le processus non trivial d’extraction des informations implicites, de structures inconnues, valides et potentiellement utiles ou exploitables dans des bases de données [PS91, FPSS96b].
Définition 2. L’ECD est définie comme un processus interactif et itératif d’analyse d’un grand ensemble de données brutes afin d’en extraire des connaissances exploitables par l’utilisateur [KNZ01]).
Définition 3. L’ECD désigne le processus global de découverte de connaissances qui permet de passer de données brutes à des connaissances [Tou11].
Fayyad [FPSS96a] décrit le processus d’extraction de connaissances à partir de bases de données comme un processus itératif composé de plusieurs étapes. Ce processus suscite un fort intérêt industriel, notamment pour son champ d’application très large, pour son coût de mise en œuvre relativement faible, et surtout pour l’aide qu’il peut apporter à la prise de décision. Cependant, il est rarement possible d’appliquer directement la technique de fouille de données sur les données brutes. Il faut tout d’abord sélectionner parmi l’ensemble des données à notre disposition le sous-ensemble des données qui peuvent être effectivement intéressantes. L’étape de prétraitement des données vise à corriger des données manquantes ou erronées. Ensuite, il faut transformer les données pour qu’elles soient utilisables par l’algorithme de fouille choisi, celui-ci génère un certain nombre de motifs qu’il faut interpréter pour enfin obtenir de nouvelles connaissances sur les données de départ.
Sélection de données
La sélection de données, première étape du processus de l’ECD, permet d’élaborer un jeu d’essai adapté au cadre de l’étude, c’est-à-dire les bases de données qui serviront à l’extraction sont sélectionnées. En effet, il est possible que les données proviennent de diverses sources et soient enregistrées sous différents formats. Cette phase d’acquisition comprend diverses tâches d’intégration et de nettoyage : repérer lors de la sélection les inconsistances, les données trop bruitées, les nettoyer avant de les stocker dans les bases de données ciblées.
Prétraitement de données
La seconde étape est une étape de prétraitement en vue de fabriquer les jeux de données adéquats à l’étape de la fouille. Il s’agira dans ce cas de sélectionner les items appropriés au processus décisionnel en cours, normaliser les données, les agréger, réduire le nombre de dimensions etc… Cela aura pour conséquence de réduire la taille de la base de données, et donc d’augmenter les chances de succès de l’algorithme de fouille.
Transformation des données
La transformation des variables, troisième étape du processus, présente les données sous la forme exigée par l’algorithme d’extraction de connaissances. Plusieurs algorithmes de data mining sont contraignants sur la forme des données qu’ils acceptent. Cette étape consiste à préparer les données brutes et à les convertir en données appropriées afin de les représenter dans un codage adéquat pour l’application de méthodes de fouille de données.
Fouille de données
La fouille de données est l’étape centrale du processus d’extraction de connaissance. Elle consiste à découvrir de nouveaux modèles au sein de grandes quantités de données. Les différentes tâches de fouille de données peuvent être classées en trois catégories.
Classification supervisée Le modèle de classification est construit en choisissant un échantillon significatif d’objets de la base de données dans lequel chaque objet va être associé à un nom de classe. Le processus de classification se décompose en deux étapes. La première consiste à construire un modèle modélisant l’ensemble d’apprentissage « instances → classes ». La seconde correspond à l’utilisation du modèle ainsi construit, c’est-à-dire tester la prédiction du modèle en ciblant le taux d’erreur, puis prédire des nouvelles instances construites. Ce modèle peut être appliqué dans de nombreux domaines, entre autres, en statistiques [AGI+92, HCC92, MST94, EP96, FPSSU96], en réseaux de neurones [Lip87, LSL95].
Classification non supervisée La classification non supervisée (ou segmentation), en anglais « Clustering » consiste à trouver, dans l’ensemble hétérogène d’objets de la base de données, des groupes relativement homogènes appelés « clusters ». Il s’agit de grouper les données ayant un haut degré de similitudes au sein de classes. Contrairement à la classification supervisée, les classes y sont construites en fonction d’un ensemble d’observation, mais ne sont pas connues initialement [HK01]. La segmentation se décompose en deux étapes. Il faut tout d’abord découvrir les classes appropriées, puis classifier les données selon les classes découvertes. Ce modèle a couramment été étudié en statistiques [EP96, MST94], en apprentisage numérique [MS83, Fis87], et en analyse de données spatiales [BKSS90, EKX95].
Recherche de règles d’association Introduit par Agrawal et al. [AIS93], la recherche des règles d’association est l’un des sérieux problèmes du KDD. Le principe est de trouver des règles dans les données de types « si Condition, alors Résultats », notées Conditions→ Résultats. Cette technique permet la découverte de règles intelligibles et exploitables dans un ensemble de données volumineux, règles exprimant des associations entre items ou attributs dans une base de données. Cetta approche fut développée pour l’analyse de base de données de transactions de ventes, chacune constituée d’une liste d’articles achetés, afin d’identifier les groupes d’articles achetés le plus fréquemment ensemble. Une règle d’association permettra alors de définir une stratégie commerciale ou de marketing dans le but de promouvoir les ventes, en plaçant par exemple l’ordinateur et l’imprimante dans le même rayonnage du magasin.
Interprétation et évaluation des résultats
L’interprétation et l’évaluation des informations extraites, dernière étape du processus, a pour objectif de produire des connaissances sur le domaine d’études en s’assurant que les conclusions émises correspondent à des phénomènes réels. Cette phase est l’ultime étape de l’ECD. Elle est constituée de l’évaluation, qui mesure l’intérêt des motifs extraits, et de la présentation des résultats à l’utilisateur grâce aux différentes techniques de visualisation. Il s’agit d’une étape de la suppression des connaissances inutiles ou redondantes, et la transformation des connaissances intéressantes en connaissances compréhensibles par l’utilisateur. L’interprétation conduit à la validation ou à la réfutation qui pourrait remettre en cause tous les processus ou une partie du processus de l’ECD [LT04]. Diverses méthodes de validation sont alors envisageables. Les modèles issus d’une classification pourront être vérifiés en premier lieu par un expert, puis la validation sera complétée par des tests statistiques sur des bases de cas existant. Pour des techniques d’apprentissage non supervisées, la détermination de la pertinence des modèles obtenus est essentiellement une affaire d’expertise. Pour ce qui est de la classification supervisée, une validation croisée est récommandable à partir de trois ensembles de données, c’est-à-dire un ensemble d’apprentisage, un ensemble de tests et un ensemble de validations.
|
Table des matières
1 Introduction générale
1.1 Contexte et problématique
1.2 Contributions
1.3 Organisation du mémoire
I Etat de l’art autour de l’extraction de règles d’association
2 Extraction de connaissances à partir de données – ECD
2.1 Introduction
2.2 Sur les processus de l’ECD
2.2.1 Sélection de données
2.2.2 Prétraitement de données
2.2.3 Transformation des données
2.2.4 Fouille de données
2.2.5 Interprétation et évaluation des résultats
2.3 Sur les règles d’association
2.3.1 Contexte d’extraction de règles d’association
2.3.2 Différents domaines d’applications
2.4 Conclusion partielle
3 Extraction de règles d’association
3.1 Introduction
3.2 Extraction d’itemsets fréquents
3.2.1 Algorithmes d’extraction d’itemsets fréquents
3.2.2 Algorithmes d’extraction d’itemsets fréquents maximaux
3.2.3 Algorithmes d’extraction d’itemsets fermés fréquents
3.3 Génération des règles d’association
3.3.1 Algorithme de génération des règles d’association
3.4 Conclusion partielle
II Contributions de la thèse
4 Extraction optimisée des motifs fréquents
4.1 Introduction et Motivations
4.2 Extraction optimisée des motifs fréquents
4.2.1 Cadre théorique de comptage des supports
4.2.2 Structure de données utilisée
4.3 Algorithme EOMF
4.3.1 Stratégie d’élagage adoptée
4.3.2 Présentation de l’algorithme
4.3.3 Exemple d’exécution d’EOMF sur B, à un minsupp = 2/6
4.3.4 Complexité de l’algorithme EOMF
4.4 Evaluation expérimentale
4.5 Conclusion partielle et perspectives
5 Génération de règles d’association à l’aide du couple support-MGK
5.1 Introduction et motivations
5.2 Définitions et limites de support-confiance
5.3 Modélisation de l’approche
5.3.1 Propriétés théoriques de l’approche
5.3.2 Parcours heuristique de l’espace de recherche
5.4 Présentation de l’algorithme GenPNR
5.4.1 Complexité de GenPNR
5.5 Evaluation expérimentale
5.6 Conclusion partielle et perspectives
6 Graphes implicatifs selon la mesure MGK
6.1 Introduction et motivations
6.2 Définitions de base et notations
6.3 Recherche des chemins implicatifs
6.3.1 Résultats théoriques de l’approche
6.3.2 Méthode de génération
6.4 Présentation de l’algorithme
6.4.1 Complexité de l’algorithme 25
6.4.2 Exemple d’exécution de l’algorithme 25
6.5 Evaluation expérimentale
6.6 Conclusion partielle et perspectives
7 Outil CHIC-MGK, Applications en didactique des mathématiques
7.1 Introduction et motivations
7.2 Description de l’outil CHIC-MGK
7.2.1 Fonctionnalités
7.2.2 Discrétisation de règles d’association
7.2.3 Mise en forme des données
7.2.4 Représentation d’un graphe implicatif
7.2.5 Arbre de similarités et arbre cohésitif
7.3 Applications en didactique des mathématiques
7.3.1 Pourquoi enseigner la statistique ?
7.3.2 Contexte du système éducatif à Madagascar
7.3.3 Méthodologie de recherche
7.3.4 Description des résultats
7.4 Conclusion partielle et perspectives
8 Conclusion générale et perspectives
Bibliographie
