Soutenance mémoire
Datamining : Motivations et définition
Les nouvelles technologies de l’information ont contribué à la croissance exponentielle des données. Face au problème de la surabondance d’informations, le datamining offre un certain nombre d’outils pour traiter ces masses de données, afin d’en extraire l’information cruciale. Celle-ci sera ensuite exploitée pour prendre des décisions. Le datamining se situe à la croisée des statistiques, de l’intelligence artificielle, des bases de données, de la théorie de l’information, etc. Contrairement à la méthode statistique qui est une technique confirmatoire, le datamining représente une technique exploratoire. Cette exploration se fait à travers un processus itératif (nécessitant plusieurs passes sur une base) et interactif (participation de l’utilisateur au processus d’extraction de la connaissance) de découverte de modèles valides, nouveaux (non prévisibles), utiles (permettant à l’utilisateur de prendre des décisions) et compréhensibles par un utilisateur, et ce à partir de larges volumes de données. Il est utilisé dans des domaines très variés aussi bien par des entreprises, des individus, que par des administrations : impôts, commerce, grandes distributions, bibliothèques, hôpitaux, etc. Le datamining a deux objectifs essentiels :
1. La prédiction, qui consiste à construire un modèle capable de prédire les valeurs d’attributs qu’on juge intéressants, à partir de valeurs connues d’autres domaines.
2. La description, qui consiste à trouver des motifs, compréhensibles par les humains, qui décrivent les données.
Les principales techniques du datamining
Les principales techniques du datamining sont l’extraction de règles associatives, la recherche de motifs séquentiels, la classification, le regroupement (clustering) et la sélection d’attributs.
L’extraction de règles associatives
Cette technique consiste à découvrir, dans une base de données de transactions, les ensembles d’attributs apparaissant simultanément et les règles qui existent entre eux. Prenons l’exemple d’un supermarché où les articles achetés, par chaque client, sont enregistrés dans une base de données comme une transaction. A partir de cet exemple, nous pouvons trouver une règle associative de la forme : « 90 % des utilisateurs qui achètent du thé et du sucre, achètent aussi de la menthe ». Trois grandes familles d’algorithmes sont utilisées pour générer des règles associatives à partir de larges volumes de données :
1. les algorithmes qui énumèrent tous les itemsets fréquents (ensemble d’attributs qui apparaissent fréquemment dans une base). Ils ont l’inconvénient de produire des règles associatives redondantes. C’est le cas des algorithmes Apriori [5] et FP Growth [6].
2. les algorithmes qui génèrent seulement les itemsets fréquents maximaux. Ils réduisent le nombre d’itemsets fréquents, mais ne donnent la valeur de leur fréquence (support). Pour cela, la génération des règles associatives nécessitera un surcoût de calcul. C’est le cas des algorithmes MaxEclat [7], Max-Miner [8], MAFIA [9], etc.
3. les algorithmes qui énumèrent les itemsets fermés fréquents. Ils réduisent de manière significative le nombre d’itemsets fréquents, tout en fournissant les informations nécessaires pour la génération de règles associatives. C’est le cas des algorithmes A-Close [10], CLOSET [11], CHARM [12], etc.
Dans l’ensemble des travaux existants, l’extraction de règles d’association est décomposée en deux sous-problèmes qui sont : (i) la recherche des itemsets fréquents ; et, (ii) la génération des règles d’association à partir de ces itemsets. Le premier sous-problème, dont la complexité est exponentielle en la taille de la base de données et qui nécessite plusieurs accès à la base, constitue la phase la plus coûteuse en terme de temps d’exécution et d’espace mémoire. C’est ainsi que plusieurs algorithmes parallèles d’extraction de règles associatives ont été proposés pour réduire ce coût de calcul :
– Parallélisme de données : Les algorithmes utilisant ce type de parallélisme [13] [14] [15] [16] diffèrent par l’utilisation ou non de techniques d’élimination d’itemsets candidats (itemsets potentiels à devenir fréquents). Les algorithmes les plus représentatifs de cette classe d’algorithmes sont Count Distribution [13], PDM (Parallel Data Mining) [14], DMA (Distributed Mining Algorithm) [15], et CCPD (Common Candidate Partitioned Database) [16].
– Parallélisme de tâches : Les algorithmes basés sur ce type de parallélisme partitionnent aussi bien l’ensemble des itemsets candidats que la base de données sur un ensemble de processeurs. Ils diffèrent dans la façon dont les candidats et la base de données sont partitionnés. Parmi les algorithmes associés à cette classe, nous pouvons mentionner l’algorithme DD (Data Distribution) [13], IDD (Intelligent Data Distribution) [17], HPA (Hash-based Parallel mining of Association rules) [18] et PAR (Parallel Association Rules) [19].
Toutes ces familles d’algorithmes commencent leur exploration par un noyau composé des 1-itemsets (itemsets fréquents de taille 1). Ainsi, selon la technique adoptée pour l’exploration de l’espace de recherche, nous pouvons distinguer deux types d’algorithmes :
1. Les algorithmes basés sur la technique « Tester-et-générer « . Ces algorithmes parcourent l’espace de recherche par niveau. A chaque niveau k, un ensemble de candidats de taille k est généré. Cet ensemble de candidats est, généralement, élagué par la conjonction d’une métrique statistique (i.e. le support minimal) et des heuristiques basées essentiellement sur les propriétés structurelles des itemsets fermés, comme dans le cas de l’algorithme APRIORI [5], l’algorithme CHARM [12], etc.
2. Les algorithmes basés sur la technique « Diviser-pour-régner « . Ces algorithmes essaient de diviser le contexte d’extraction (base de données) en des sous-contextes et d’appliquer le processus de découverte des itemsets récursivement sur ces souscontextes. Ce processus de découverte repose sur un élagage du contexte basé essentiellement sur l’utilisation d’une métrique statistique (le support minimal) et d’heuristiques, comme le font les algorithmes FP-Growth [6], CLOSET [11], etc.
La recherche de motifs séquentiels
Cette technique est une extension de celle qui permet de générer les règles d’association, en ajoutant une nouvelle composante, à savoir le temps. Cette recherche met en évidence des associations inter-transactions, contrairement à celle des règles d’association qui extrait des combinaisons intra-transactions. Comme exemple de motif séquentiel, nous pouvons citer l’exemple suivant : « 60% des gens qui achètent un téléviseur, achètent un magnétoscope dans les deux ans qui suivent ».
Problématique de la recherche de motifs séquentiels
Une transaction constitue, pour un client C, l’ensemble des items achetés par C à une même date. Dans une base de données client, une transaction s’écrit sous la forme d’un ensemble :id-client, iddate, itemset. Un itemset est un ensemble d’items non vide, noté (i1,…, in). Une séquence est une liste ordonnée, non vide, d’itemsets notée <s1s2…sn>, où sj est un itemset. Une séquence de données est une séquence représentant les achats d’un client. Soit T1,…,Tn les transactions d’un client, ordonnées par dates d’achat croissantes et soit l’itemset({Ti}) l’ensemble des items correspondant à Ti . Alors la séquence de données de ce client s’écrit comme suit :
<itemset(T1),…,itemset(Tn)> . Un client supporte une séquence S si S est incluse dans la séquence de données de ce client. Le support d’une séquence S est calculé comme étant le pourcentage des clients qui supportent S. Soit σ le support minimum fixé par l’utilisateur. Une séquence qui vérifie le support minimum (i.e. dont le support est supérieur ou égal à σ) est une séquence fréquente. Soit une base de données DB de séquence de données ; le problème de la recherche de motifs séquentiels consiste à extraire toutes les séquences fréquentes qui respectent la contrainte de support minimal. Pour résoudre un tel problème, plusieurs approches ont été proposées [20] [21] [22] [23] [24] [25].
Les approches basées sur Apriori
La méthode GSP (Generalized Sequential Patterns) [20] a été l’une des premières propositions pour résoudre la problématique des motifs séquentiels (ce travail fait suite à [21]). Elle est destinée à effectuer un nombre de passes raisonnable sur la base de données. Pour cela, elle procède à une factorisation de l’ensemble des candidats basée sur leur préfixe.
Les approches basées sur le principe « Depth-fisrt »
La prise en compte de la temporalité dans les transactions a conduit de nombreux auteurs à privilégier des méthodes de recherche dites « en profondeur d’abord » pour extraire les motifs séquentiels. C’est le cas de PSP [22], qui met en place et exploite un arbre de préfixes pour gérer les candidats. C’est aussi le principe adopté par [23] avec l’algorithme FREESPAN et amélioré par [24] avec l’algorithme PREFIXSPAN. PREFIXSPAN implémente de plus un principe de réécriture de la base de données en fonction des préfixes des motifs séquentiels fréquents découverts (ou d’une indexation en fonction de la mémoire disponible). Nous présentons dans cette section une sélection de méthodes basées sur ce principe de la recherche « en profondeur d’abord ».
|
Table des matières
Introduction générale
1 Contexte et problématique
2 Objectifs et contributions
3 Organisation de la thèse
A Etat de la l’art
I Etat de l’art sur le Datamining
1 Datamining : Motivations et définition
2 Les principales techniques du datamining
3 Conclusion
II L’algorithme RFE-SVM
1 Les machines à vecteurs supports (SVM)
2 Coefficients de classement d’un SVM
3 L’élimination récursive d’attributs par SVM
4 Conclusion
III Etat de l’art sur la préservation de la vie privée dans le Datamining Distribué
1 Le Datamining Distribué
2 Le calcul distribué sécuritaire multi-parties
3 Conclusion
B CONTRIBUTION
IV Un nouveau protocole de calcul sécurisé du produit scalaire
1 Définitions préliminaires
2 Définition du problème
3 Algorithme
4 Analyse du coût de communication et de calcul
5 Analyse de la sécurité
6 Travaux relatifs
7 Conclusion
V Une approche distribuée de l’algorithme RFE-SVM pour la sélection de gènes dans des bases de données médicales distribuées
1 Définitions préliminaires
2 Définition du problème
3 Validation expérimentale
4 Résultats et discussion
5 Conclusion
Conclusion générale et perspectives
Références bibliographiques
