Soutenance mémoire
Les nouvelles technologies de l’information permettent à la fois un stockage de larges volumes de données et une contribution à leur croissance exponentielle. Ceci a pour conséquence de créer une disproportion entre les volumes de données et les moyens matériels et humains pour les exploiter. Face à ces problèmes, les technologies du datamining permettent de traiter ces ensembles de données en vue d’extraire de la connaissance, qui sera déterminante pour la prise de décisions.
Cependant, l’application de ces technologies sur des données à caractère personnel permet de découvrir des connaissances confidentielles sur des individus ou des entreprises. Ainsi, il serait possible de définir des profils d’individus, de prédire leurs comportements et d’agir en conséquence. Pour des entreprises, il serait possible de rassembler des données à caractère commercial, financier et autres, pour ensuite les utiliser dans un cadre illégal (concurrence déloyale, rachat d’entreprises en difficultés, etc.). Ces deux exemples simples montrent que ce type de connaissances est en contradiction avec les droits des personnes, entreprises, institutions, etc., qui veulent préserver les données relatives à leur vie privée. Récemment, de nouvelles lois ont été mises en place pour mettre en place des contraintes sur la confidentialité des données, afin de préserver la vie privée des personnes. Parmi ces lois, nous pouvons citer la loi HIPAA (Health Insurance Portability and Accountability Act) [2], qui instaure un régime de protection des renseignements personnels en matière de santé aux Etats-Unis. Ce type de lois est maintenant adopté par de nombreux pays tels que l’Australie, la Chine, le Japon, les pays de l’Union Européenne, etc., qui ont mis en place tout un arsenal juridique pour cadrer l’exploitation des données stockées dans différentes bases.
Etat de l’art sur le Datamining
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 ».
|
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
