Datamining et Vie privée

Les technologies informatiques ont mené à la création d’une énorme industrie d’analyse, d’entreposage et de fouille de données. Cette industrie repose sur le besoin toujours croissant des sociétés et des gouvernements de se procurer des renseignements détaillés sur des personnes, telles que des clients, des patients, des citoyens, et sur des menaces potentielles pour la sécurité. Les sociétés veulent en savoir le plus possible sur les consommateurs de façon à pouvoir mieux cibler leurs stratégies de marketing et augmenter ainsi leurs profits. Les gouvernements veulent repérer les menaces pour la sûreté publique et la sécurité nationale afin de prévenir des catastrophes publiques. Les chercheurs en soins de santé souhaitent améliorer leur capacité de prédire, de diagnostiquer, de prévenir et de traiter des maladies en recueillant des données cliniques et en surveillant de près des cas particuliers. Dans tous ces exemples, le Datamining est utilisé pour recueillir, trier et extraire des renseignements détaillés sur des personnes. Si la technologie de l’information continue de se développer sans entrave, l’utilisation de la représentation numérique d’une personne aura inévitablement des effets opprimants sur ces personnes. C’est pourquoi la recherche doit s’intéresser spécifiquement à ces menaces et évaluer la mesure dans laquelle la réglementation suffira à les prévenir ou à y faire face. Ce chapitre est organisé en deux grande sections à savoir l’état de l’art sur le datamining et l’état de l’art sur le datamining intégrant la contrainte de la vie privée. Mémoire de DEA d’Informatique 2 I.2 Etat de l’Art sur le Datamining 2 Etat de l’Art sur le Datamining Le Datamining est un terme générique englobant toute une famille d’outils facilitant l’analyse des données contenues au sein d’une base décisionnelle de type Data Warehouse ou DataMart. Certains considèrent cette technique comme « l’art » voire la « science » de l’extraction d’informations significatives de grandes quantités de données. En peu de mots, le Datamining présente l’avantage de trouver des structures originales et des corrélations informelles entre les données. Il permet de mieux comprendre les liens entre des phénomènes en apparence distincts et d’anticiper des tendances encore peu discernables. A contrario des méthodes classiques d’analyse statistique, le Datamining est particulièrement adapté au traitement de grands volumes de données. Ce traitement se déroule en plusieurs étapes comme l’illustre la figure I.1. Avec l’augmentation de la capacité de stockage des supports informatiques, un maximum de renseignements sera capté, ordonné et rangé au sein du Data Warehouse. Le comportement des acheteurs, les caractéristiques des produits, l’historisation de la production, désormais plus rien n’échappe à la collecte. Avec les techniques de Datamining, ces « tera-nesque » bases de données sont devenues exploitables. Figure I.1 –Etapes du processus de Datamining 3 Ou s s e y n ou S A N E Chapitre I. Datamining et vie privée 2.1 Définition et Motivation 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. 2.2 Les Techniques de Datamining Les outils de datamining proposent différentes techniques à choisir en fonction de la nature des données et du type d’étude que l’on souhaite entreprendre. Les principales techniques du datamining sont la classification, l’extraction de règles associatives, le regroupement (clustering) et la recherche de motifs séquentiels. 

La Classification

La classification consiste à assigner à de nouveaux objets une ou plusieurs classes prédéfinies, en recherchant un ensemble de prédicats caractérisant une classe d’objets qui peut être appliquée à des objets inconnus pour prévoir leur classe d’appartenance. C’est une technique qui s’applique à divers domaines, comme la finance, la détection de fraudes, le diagnostic médical, etc. Par exemple, une banque peut vouloir classer ses clients pour savoir si elle doit leur accorder un prêt ou non. La classification est un processus composé de deux étapes : Mémoire de DEA d’Informatique

Etat de l’Art sur le Datamining

1. Construction du modèle à partir de l’ensemble d’apprentissage, appelé (training set), 2. Utilisation du modèle pour la classification des nouvelles données. La validité du modèle, construit dans l’étape 1, doit être testée dans cette étape, avant même son utilisation. Ainsi plusieurs techniques de validation ont été proposées, à savoir la validation sur l’ensemble de données ayant servi à l’apprentissage, la validation sur un autre ensemble de données et la validation croisée, qui consiste à diviser les données en n groupes. On construit les modèles sur les n-1 groupes et on les teste sur le n-ième groupe. Puis on change de groupe de test et on répète le même procédé jusqu’à réaliser toutes les combinaisons. A la fin, on considère alors la moyenne des validations comme étant la validation finale. Plusieurs techniques de classification ont été proposées, parmi lesquelles nous pouvons citer : – Les arbres de décision qui sont une représentation graphique d’une procédure de classification. L’arbre de décision est un arbre où chaque nœud interne est un attribut, chaque branche est un test sur un attribut et les feuilles sont les étiquettes de classes. – La classification bayésienne qui est un apprentissage probabiliste basé sur les probabilités conditionnelles. Elle nécessite une hypothèse d’indépendance qui est rarement satisfaite en pratique, étant donné que les attributs (variables) sont souvent corrélés. Pour contourner cette limitation, les réseaux bayésiens ont été proposés afin de combiner le raisonnement bayésien et la relation causale entre attributs. – Les réseaux de neurones qui permettent de découvrir automatiquement des modèles complexes avec un taux d’erreur généralement bon. Un réseau de neurones est composé de plusieurs neurones (unités de calcul élémentaires) interconnectés. Un poids est associé à chaque arc. Contrairement aux arbres de décision et aux réseaux bayésiens, la phase d’apprentissage des réseaux de neurones est évolutive dans le temps. En effet, un réseau de neurones peut apprendre et changer son comportement en fonction de toute nouvelle expérience. La classification est un problème largement étudié dans le domaine du datamining. Elle est, avec ses nombreuses extensions, probablement la technique de datamining la plus utilisée actuellement. Aujourd’hui les directions de recherche dans ce domaine sont plus orientées sur la classification de données non relationnelles (données textuelles, multimédia, etc.). En particulier, elle est de plus en plus utilisée pour classifier des documents 5 Ousseynou SANE Chapitre I. Datamining et vie privée XML. Par exemple, dans [3], les auteurs combinent plusieurs fonctions d’affectation (classifier) pour classer des documents XML multimédia. D’autres travaux, étudient le problème de la classification dans un contexte distribué. 

Les Règles d’Association

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 [4] et FP-Growth [5]. 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 pas 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 [6], Max-Miner [7], MAFIA [8], etc. 

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 [9], CLOSET [10], CHARM [11], 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 .