Partie 1

Chapitr e (I) Introduction Générale

1 Motivations : L’`un des principaux moteurs due développement de la science de l’`informatique a étéest le besoin de stocker et de gérer des masses d`informationsde données dont la taille n`ea cesscesseé de croitre. En effet, Dèsdans les années 60 apparait la notion de base de données simultanément avec le , et la simultanéité du développement des réseaux informatiques ce qui permettrava rapidement permettre un partage de ces l’informations entre les plusieurs utilisateurs. L`’architecture typique sera est alors constitué d’un serveur (mainframe) stockant l`’information et auquel sont reliésde différents terminaux "passifs" qui y sont reliés, permettant de consulter l`’information. Les années 70 verront le développement du modèle relationnel pour le stockage et la gestion des collections de données. Ce modèle, qui s`’imposera rapidement comme étant un modèle de référencestandard. S`’en suivra une forte activité chez les éditeurs de logiciels pour proposer des Systèmes de Gestion des Bases de Données Relationnel (SGBDR) implémentant ces principes modèle. L`existence de techniques de modélisation efficaces contribua largement a la large adoption du modèle relationnel par les utilisateurs dans les années qui suivirent. Puis dans les années 80, de nouveaux modèles furent proposés, et des SGBD propres à des besoins spécifiques firent leurs apparitions. On Nous pouvonspeut ainsi, entre autres, associer des méthodes aux objets stockés dans la base de données. L`’une des raisons de l`’évolution des méthodes et des techniques de stockage est l`’explosion de la quantité d`’information à stocker. Dans de nombreux domaines, les besoins ont rapidement évolués : de "l`’informatisation" de l`’existant, on nous sommesest passés a la nécessité d`’automatiser l`’acquisition de données. Cette évolution, liée au progrès technologique, a été particulièrement sensible dans certains domaines. En sciences expérimentales, par

exemple, les mesures sont aujourd`’hui réalisés par des capteurs capables d`’enregistrer la les valeurs de plusieurs centaines de paramètres à des intervalles de temps très courts. Ceci permet, entre autres, de construire des modèles mathématiques de plus en plus précis pour les phénomènes étudiés. Dans le domaine de grande distribution également, on nous dispose disposons aujourd`’hui de systèmes qui enregistrent en direct temps réel tous les produits achetés par les clients lors de leur passage en caisse. Ces données peuvent ensuite être traitées pour essayer de cibler des offres sur des catégories de clients (marketing ciblé). Enfin, dans le domaine médical, l`’historique des différents examens et diagnostics des patients, est lui aussi numérisé, conduisant la encore a à une explosion de la quantité d`es donnéesinformation stockées. Cette explosion du volume de données a rapidement conduit les utilisateurs vers de nouveaux besoins. En sciences expérimentales, les chercheurs se sonton s`est rapidement interrogés sur la possibilité d`’obtenir des connaissances a à partir de la masse de données collectées. De telles connaissances peuvent se matérialiserprendre sous des formes très différentes : par exemple, cela peut consister en la découverte de régularités parmi certains enregistrements ou de dépendances entre certaines valeurs. Elles peuvent également permettre de faciliter la description desdécrire les données, expliquer des phénomènes, prévoir des comportements etc.. Mais l`information extraite peut aussi avoir un rôle explicatif des données. L`utilisation d`outils de classification supervisée comme les arbres de décision peut ainsi permettre de prédire la valeur de certains attributs grâce a des modèles compréhensibles par l`utilisateur. De même, les techniques de classification non supervisée, comme "clustering", permettent de regrouper des enregistrements similaires, afin de mieux comprendre les données. Deux grandes familles de techniques sont apparues autour des années 90 pour étendre les SGBD classiques avec des outils d`’analyse de données : -

OLAP (On-Line Analytical Processing) : on désigne par ce nom une catégorie d`’outils permettant de faire l`’analyse "en ligne" d`’informations stockées dans des bases ou entrepôts de

-

données. Cette technologie est surtout orientée vers l`’analyse de données multidimensionnelles. Une de ses caractéristiques est qu`’elle permet de manipuler des hiérarchies sur les dimensions. Il est ainsi possible de suivre les ventes de familles de produits par magasin et par période de l`’année avec des niveaux de granularité différentes. ECD (Extraction des Connaissances dans les Données) : ce terme sera définit dans la section suivante.

2 L`’Extraction des Connaissances à partir des Données 2.1 Définition : L'utilisation de plus en plus généralisée de l'informatique permet de récolter de plus en plus de données de manière automatique. Ainsi, en sciences expérimentales, les mesures, autrefois faites à la main, sont recueillies par des appareils qui les enregistrent directement sous forme informatiquenumérique. Ce n'est pas le seul domaine touché. Du fait de L'informatisation a touché aussirapide des les administrations, ldes entreprises, du commerce, lades télécommunication etc.s, la quantité de données disponibles sous forme informatique augmente très rapidement. Cependant, l'analyse et l'exploitation de ces données restent très difficiles et problématiques. Les techniques d'extraction de connaissances dans lesà partir des données ont été conçues pour répondre à ce besoin [BJ02]. Dans les sciences expérimentales, il n'est pas rare de consacrer plusieurs années à l'analyse des résultats d'une expérience. Il suffit de songer aux données issues de recensements, d'enquêtes épidémiologiques, d'observations spatiales, du décryptage du génome, etc. Dans le cas des données récoltées automatiquement issues du commerce (en particulier électronique), des

télécommunications, ... on ne sait pas toujours comment les exploiter une fois qu'elles ont remplit leur rôle principal (par exemple la facturation). Pourtant, les propriétaires de ce type de données hésitent souvent à les détruire pour au moins deux raisons. D'une part le coût de stockage, d'autre part, ils supposent que ces données contiennent peut être des connaissances d'une grande valeur (par ex. sur le comportement de leurs clients, sur la survenue d'erreurs dans un réseau de communication...). C'est en fait le postulat principal qui motive l'extraction de connaissances dans à partir desles données (ECD) : ces masses de données contiennent sûrement des connaissances d'une grande valeur commerciale ou scientifique. Il faut noter que ce postulat n'a évidemment pas été « démontré ».

L`’ECD est devenu un domaine de recherche à part entière à partir de 1989, quand Gregory Piatetsky-Shapiro a organisé la première réunion de chercheurs sur l`’extraction automatique des connaissances dans les grandes bases de données .données. L`’Extraction des Connaissances a à partir des Donnés (ECD, en anglais ou KDD pour "Knowledge Discovery in Databases") a été définie par Piatetsky-Shapiro et Frawley comme étant « le "processus non trivial d`’extraction d`’informations potentiellement utiles, implicites et inconnues auparavant a partir d`’un ensemble de données" [PSF91]. C`’est un domaine multidisciplinaire et au croisement de nombreuses thématiques relevant des mathématiques et de l`’informatique. Selon (Fayyad, 1996)Fayyad, l`’ECD est un "Processus nontrivial d’identification de structures inconnues, valides et potentiellement exploitables dans les bases de données "(Fayyad, 1996).

Fig.1. Processus non-trivial d`’identification de structures inconnues, .(valides et potentiellement exploitables dans les bases de données (Fayyad, 1996

Une définition plus détaillée est donnée dans [ZR03] : « l’ECD vise à transformer des données (volumineuses, multiformes, stockées sous différents formats sur des supports pouvant être distribués) en connaissances. Ces connaissances peuvent s’exprimer sous forme d’un concept général qui enrichit le champ sémantique de l’usager par rapport à une question qui le préoccupe. Elles peuvent prendre la forme d’un rapport ou d’un graphique. Elles peuvent s’exprimer comme un modèle mathématique ou logique pour la prise de décision. Les modèles explicites quelle que soit leur forme, peuvent alimenter un système à base de connaissances ou un système expert ». L`’ECD repose sur l`’existence d`’algorithmes de fouilles de données (voir [JA03]), de tels algorithmes travaillent opèrent souvent sur des données qui doivent avoir un format bien particulier généralement adapté au type de connaissance que l`’on cherche à extraire; une telle représentation des données est le contexte d`’extraction.

2.2

Processus d`’ECD :

Une fois ce postulat admis, la question se pose de savoir comment des connaissances peuvent être extraites de ces données. Cela ne peut pas être fait directement par un operateur humain. En effet, le cerveau humain n'est pas adapté pour traiterau traitement de telles masses de données volumineuses. Par contre, seul un expert humain est capable d'évaluer si le résultat d'une analyse des données apporte vraiment une nouvelle connaissance. Cette évaluation fait en effet intervenir tellement de paramètres subjectifs (connaissances du domaine, contexte économique ou scientifique ...) qu'il n'est pas possible de la faire automatiquement. Le processus d'extraction de connaissances ne se limite donc pas à une extraction automatique, il comporte plusieurs étapes pendant lesquelles l'expert humain a un rôle important. Il faut tout d'abord récupérer les données qui peuvent être issues de plusieurs sources différentes et les mettre dans un format commun pour pouvoir les fusionner. Il faut ensuite prétraiter les données, par exemple résoudre le problème posé par les valeurs manquantes ou aberrantes, et sélectionner les données sur lesquelles vaont être appliqué l'algorithme d'extraction de connaissances proprement dit. Ensuite, il faut post-traiter les résultats de cet algorithme et les interpréter. Ce post-traitement peut consisterconsiste à sélectionner les résultats les plus prometteurs, à les trier ou à vérifier leur pertinence à l'aide d'outils statistiques.

Fig.2. Le processus d`’Extraction de Connaissances à partir des Données. [CM].

Dans chacune de ces étapes, l'expert doit faire des choix et évaluer les résultats obtenus en fonction de ses objectifs. Il peut alors décider de passer aà l'étape suivante ou de recommencer une ou plusieurs des étapes précédentes en utilisant une technique différentes. Ce processus est donc naturellement itératif et interactif. 2.2.1 La sélection de données :

Cette étape suit directement le besoin d’un utilisateur pour un ensemble de connaissances qui l’aideront à prendre une ou plusieurs décisions. Cet aspect est très important, car on ne peut appliquer le processus d’ECD sur toutes les données que l’on a. Le besoin exprimé par l’utilisateur fait naître chez lui un objectif. C’est cet objectif qui le guidera dans la sélection des données. Ainsi, si on veut extraire des corrélations entre des produits qu’on vend dans une entreprise commerciale, il est inutile de consulter les données du personnel travaillant dans l’entreprise, ou

encore de télécharger des pages Web qui parlent de Marketing; il s’agit d’explorer les données transactionnelles archivées, concernant les achats des clients. Cette phase concerne donc le filtrage de données. Par filtrage, nous voulons dire la réduction de la dimensionnalité des données (élimination d’attributs sans intérêt, ou ayant beaucoup de valeurs erronées et manquantes), ainsi que la réduction la taille des données (des enregistrements). La deuxième réduction peut être faite par des techniques statistiques d’échantillonnage, s’il s’avère que la masse de données est trop grande, et que l’application du Data Mining serait ainsi très coûteuse en terme de temps CPU et d’espace mémoire. Plusieurs outils nous permettent de sélectionner les données ; le plus puissant d’entre eux estreste sans doute le langage SQL. Ce langage peut opérer sur les BD relationnelles,, ainsi que les BD relationnellesobjets à travers ses fameuses requêtessa fameuse requête « SELECT ». 2.2.2 Le prétraitement des données :

Le prétraitement des données concerne le nettoyage des données, c.-à-d. l’élimination des bruits susceptibles de réduire l’exactitude des modèles à extraire. Le prétraitement concerne aussi le traitement des valeurs manquantes, ou erronées. Il faudrait alors définir les méthodes à utiliser pour le remplacement de ces valeurs. De nombreuses solutions existent pour ce problème. On peut remplacer les valeurs manquantes par la valeur la plus fréquente de l’attribut en question. On peut estimer ces valeurs à partir des enregistrements complets à travers la régression ou les réseaux de neurones. Pour les données erronées, il faudrait tout d’abord les identifier (comment juge t-on qu’une valeur est erronée ?). On peut définir uUne valeur erronée , commepeut être définie comme étant une valeur qui s’écarte de la moyenne de deux fois l’écart type [ZR03].

Si les données sur lesquelles on veut appliquer lae Data Mining ne sont pas de qualité, les résultats de l’exercice ne seront pas de qualité aussi. 2.2.3 La transformation de données :

Plusieurs algorithmes de Data Mining sont contraignants sur quant à la forme des données qu’ils acceptentopèrent. Cette étape consiste à préparer les données brutes et à les convertir en données appropriées. La transformation se fait par attribut (toutes les valeurs d’un attribut doivent être transformées). Ainsi, un attribut C est transformé en C’ qui serait traitable par une la méthode de Data Mining. La discrétisation de variables continues est un exemple de transformation d’attributs. Il s’agit de transformer un attribut continu en divisant son domaine en intervalles finis. Ainsi, le domaine de l’attribut transformé devient un ensemble de valeurs discrètes. Il y a beaucoup de méthodes de discrétisation dans la littérature. Le Data Miner doit choisir celle qui ne fait pas perdre aux données leur exactitude. L’agrégation de données est un autre type de transformation. L’agrégat d’un attribut est la transformation de ce dernier par une règle ou équation. Imaginons que l’ont veut analyser les salaires annuels des employés, et que l’on dispose seulement des salaires mensuels. Un nouvel attribut agrégat serait le salaire multiplié par douze. 2.2.4 Le Data Mining :

C’est l’étape cœur du processus d’ECD. Elle consiste à dégager un ensemble de connaissances brutes à partir des données prétraitées. Il existe plusieurs tâches de Data Mining, comme par exemple la prédiction, l’analyse de liens (règles d’association), la description de données etc. A chaque tâche est allouée une multitude d’algorithmes et de méthodes de Data Mining. Le choix d’un algorithme de Data Mining doit tenir compte du domaine d’application, de la nature et la

structure des données et finalement de l’objectif du Data Miner. Les étapes qui précèdent le Data Mining sont très importantes, car la qualité des connaissances extraites, ainsi que leur coût d’extraction en dépendent directement.

Fig. 4. Les sources de données : Spécificité du Data Mining. [RR].

2.2.5 Evaluation et interprétation des connaissances :

Les connaissances extraites au terme de la précédente étape sont dans la plupart du temps inexploitables. En effet, il est difficile d’avoir directement des connaissances valides, utilisables par le Data Miner. Il existe, pour la plupart des techniques de Data Mining, des méthodes d’évaluation des modèles ou patterns extraits. Ces méthodes peuvent aussi aider à corriger affiner les modèles, et à les ajuster aux données. Selon le degré d’exactitude retourné par ces méthodes, le Data Miner pourrait déciderdécide d’arrêter le

processus d’ECD, ou au contraire de reprendre à partir de l’une des étapes antérieures (le processus est étant itératif). Les connaissances obtenues devraient être interprétables, nouvelles, valides et utiles au Data Miner. Ce dernier peut les utiliser directement, ou les incorporer dans un système de gestion de connaissances. La figure ci-dessous3 est célèbre, elle montre surtout l’aspect itératif du processus, i.e., la possibilité de retourner à n’importe quelle étape afin d’obtenir des connaissances de qualité. Ces retours sont des décisions prises par l’ingénieur de connaissancesle Data Miner (Data Miner), ce qui montre aussi l’aspect interactif du processus. C’est la quatrième étape qui est centrale, et d’ailleurs la plupart des travaux de recherche la concernent.

Fig. 3. Processus d`’Extraction des Connaissances a partir des Données. [FPS96].

2.3

-

Emergence de l`’ECD : Domaines d`’application : Domaine des assurances : Analyse des risques (caractérisation des clients a haut risques, etc.), Automatisation du traitement des

-

demandes (diagnostic des dégâts et détermination automatique du montant des indemnités). Services financiers : consentement de prêts automatisés, support a la décision de crédit, détection des fraudes. Grande distribution : profits de consommateurs et modèles d`’achats, constitution des rayonnages, marketing ciblé. [RR].

3 Contribution :

4 Organisation :

Chapitr e (II) Les Bases de Données Inductives

: Références BJ02] Baptiste Jeudy. Optimisation de requêtes inductives:]

application a extraction sous contraints de règles .d`’association.2002 CM] Mémoire de ThèseThèse de doctorat, Institut National des] Sciences Appliquées de Lyon, Contribution au cadre des bases de données inductives : Formalisation et .évaluation de scenarios d`’Extraction de Connaissances Jérôme aze. Extraction de connaissances a partir des données numériques et textuelles. Doctorat de l`’université Paris-Sud.2003. [JA03]

PSF91] Gregory Piatetsky-Shapiro and William J. Frawley.] Knowledge Discovery in Databases. Menlo Park: AAAI .Press, 1991. 525 pages Fayyad, U., Piatetsky-Shapiro, G., et Smyth, P. « From Data Mining to Knowledge Discovery: An Overview ». In Fayyad, U., Piatetsky-Shapiro, G, Amith, Smyth, P., and Uthurnsamy, R. (eds.), Advances in Knowledge Discovery and Data Mining, MIT Press, 1-36, Cambridge, 1996. [RR] Ricco Rakotomalala, Universite Lumiere Lyon 2, Laboratoire ERIC, Introduction au Data Mining. [FPS96]

[ZR03] Zighed D.A., Rakotomalala R., « Extraction de connaissances à partir de données (ECD) », in Techniques de l'Ingénieur, H 3 744, 2003.

[ZZY03]

Zhang, S., Zhang, C., Yan, X. " Post-Mining : Maintenance Of Association Rules by Weighting". Information Systems, .2003