Le Datamining

I- Petite histoire des bases de données

 

dataminingLes débuts

Dans les années 70, l’évolution des technologies de l’information a abouti au développement de techniques d’indexation, d’organisation et de manipulation des données. A la même époque, au centre IBM de San José, E.F. Codd inventait le modèle relationnel, qui devint vite un standard pour les bases de données. Peu à peu les interfaces s’améliorèrent et l’accès aux données fut facilité pour l’utilisateur grâce à l’introduction de langages de requêtes (SQL, System Query Langage).

Puis, avec l’apparition de l’OLTP (On-Line Transaction Processing), un type d’opération informatique où l’ordinateur répond immédiatement à la requête (par opposition au mode batch), les bases de données relationnelles ont été rapidement reconnues comme un outil majeur de stockage, de classement et de restitution des données.

OLAP et data warehouses

Au milieu des années 80, les bases de données relationnelles étaient déjà largement répandues. Leur succès, ainsi que l’émergence de systèmes d’information globaux comme le World-Wide Web, a motivé le développement de nouveaux systèmes de stockage des données, et surtout de méthodes pour les analyser.

L’une des architectures de bases de données les plus utilisées aujourd’hui est le data warehouse (entrepôt de données), qui réunit des données venant de sources multiples et hétérogènes, par exemple celles issues des différentes succursales d’une même entreprise. Les données sont automatiquement nettoyées, corrigées, datées et transformées sous un format unique qui les prépare à l’analyse. Celle-ci est effectuée en extrayant des blocs de données intéressantes sous forme de cubes, c’est à dire de tableaux structurés autour de 3 axes (par exemple employé, salaire, et ancienneté), ou d’hypercubes, des cubes de données à n dimensions, organisés autour de plus de trois axes. Les cubes et hypercubes sont manipulés grâce à l’OLAP (On-Line Analytical Processing), une technique qui permet une analyse multidimensionnelle et interactive.

Cependant, d’autres méthodes sont vite devenues nécessaires pour des analyses en profondeur, car l’accroissement prodigieux de la quantité de données a rendu impossible leur analyse sans outils très performants. Certaines entreprises doivent gérer des millions de transactions par jour, stockées dans des bases de données de plusieurs tera-octets ; de plus on estime que la quantité de données collectées par les entreprises double tous les 20 mois. De telles quantités sont impossibles à analyser à la main et même les outils de l’OLAP (ainsi que ses nombreux dérivés : ROLAP, MOLAP, etc…) se révèlent insuffisants.

Ainsi bien que très riche en données, notre monde est pauvre en information. Par manque d’outils permettant d’extraire les connaissances utiles à partir des données brutes, les bases de données sont inexploitables, et les décisions sont plus souvent prises sur la la base d’intuitions que d’informations valables.

 

L’émergence du data mining

Aujourd’hui, le gouffre qui sépare données et information est peu à peu comblé par le développement des techniques de data mining. Issu de la technologie des data warehouse, il était au départ destiné à aider à la découverte d’informations cachées (ou passées inaperçues) dans ces grands réservoirs. Mais le data mining se diversifie de plus en plus, et s’adapte maintenant à toutes sortes de bases de données.

Outre le fait que le data mining s’applique à des données plus diverses que l’OLAP, ce qui différencie les deux outils est surtout la capacité du data mining à incorporer des techniques de compréhension intelligente des données. L’OLAP doit être guidé étape par étape, il est entièrement contrôlé par l’utilisateur, qui doit poser des questions précises ( » a-t-on vendu plus d’eau minérale en Rhone-Alpes qu’en Aquitaine en 2003 ? « ) et indiquer sous quelle forme elles seront représentées. En revanche, avec le data mining l’utilisateur pose des questions plus générales, comme  » quelles sont les caractéristiques de l’achat d’eau minérale ? « . L’outil de data mining peut repérer seul les informations potentiellement utiles et choisir les représentations les plus adaptées.

 

II- Comment fonctionne le data mining ?

 

Data mining et KDD

Dans sa plus ancienne acception, le datamining est le processus central du KDD (Knowledge Discovery in Databases). Cette étape si importante que le terme de KDD est maintenant souvent remplacé par celui de Data mining, plus parlant. Le KDD peut être schématisé par une suite d’opérations de transformation et d’analyse des données :

Data cleaning : phase d’élimination du bruit et des données inutiles : filtrer, trier, homogénéiser, nettoyer. Les données peuvent être incomplètes, contradictoires, ou contenir des erreurs humaines ou informatiques. Lors du data cleaning les données sont comparées, pour tenter de combler automatiquement les lacunes et corriger les erreurs.

Data integration : phase d’association de multiples sources des données sous une forme unique, généralement dans le cadre de l’architecture d’une data warehouse. Cette étape sert à régler le problème des incompatibilités entre les différents systèmes informatiques et systèmes de stockage des données d’une même entreprise. Par exemple toutes les sommes indiquées dans des devises différentes peuvent être converties eu euros. Ou encore, le champ adresse peut être décomposé en champs ville, rue et pays. Les données sont aussi datées et résumées.

Data selection : les données ayant un rapport avec l’analyse demandée sont retrouvées dans la base.

Data transformation : les données sont regroupées, normalisées, et transformées dans un format qui les prépare au mining.

Data mining : un processus essentiel où des méthodes intelligentes sont appliquées pour extraire des éléments remarquables, des patterns. Il s’agit de configurations de données dont la structure est inhabituelle, qui présentent des corrélations imprévues, des écarts statistiques, ou tout ce qui sort de l’ordinaire.

Pattern evaluation : On identifie les patterns intéressants, ceux qui représentent de l’information. L’intérêt des patterns est évalué par les outils de data mining en utilisant des règles objectives basées sur la structure des patterns et les statistiques qui les sous-tendent, ainsi que des règles subjectives basées sur les croyances des utilisateurs (ce savoir est stocké dans une base de connaissances). Par exemple, une information est intéressante si elle contredit les croyances de l’utilisateur.

Knowledge présentation : des techniques de visualisation et de représentation sont utilisées pour présenter clairement à l’utilisateur le savoir extrait des données : tables, arbres, règles, graphiques, courbes, matrices, cubes, etc.

 

Les techniques et outils du data mining

Les outils de data mining ne sont pas tous basés sur les mêmes principes. Différentes méthodes peuvent être utilisées en fonction de la nature des données dont on dispose, et des informations recherchées. Voici quelques unes des techniques les plus couramment employées :

– Analyse du panier de la ménagère (APM) ou recherche d’associations,

– Statistiques,

– Raisonnement basé sur la mémoire (RBM),

– Découvertes de règles,

– Arbres de décision,

– Pattern recognition,

– Réseaux neuraux,

– Apprentissage automatique,

– Fuzzy set theory,

– Détection automatique des clusters,

– Analyse des liens,

– Algorithmes génétiques,

– Traitement analytique en ligne (TAEL),

– Réseaux bayesiens.

– Les systèmes de data mining les plus sophistiqués combinent plusieurs de ces techniques.

 

L’une des méthodes les plus importantes est l’analyse de clusters, qui consiste à segmenter une population hétérogène en sous-populations homogènes. Un cluster est un ensemble de données qui sont similaires aux autres dans le même cluster, et différents des objets dans les autres clusters. On appelle clustering le processus qui consiste à regrouper un ensemble d’éléments en classes d’objets similaires, sans modèle préconçu (ce en quoi ce concept se différencie de celui, plus large, de classification). En clair, différencier spontanément les chiens des chats dans la petite enfance, est de l’analyse de clusters.

 

Quelles informations peut-on découvrir grâce au data mining ?

 

Habituellement, on accède aux données relationnelles par le biais de questions formulées dans un langage de requêtes (SQL), ou grâce à une interface graphique. Le langage autorise des requêtes variées comme  » Montrez moi la liste de tous les objets vendus dans la dernière heure « ,  » Combien de transactions ont été réalisées dans l’année 2003 ? « , ou  » Quels vendeurs ont opéré le plus grand nombre de transactions ? « .

Quand le data mining est appliqué aux bases de données relationnelles, il est possible d’aller plus loin, en cherchant des corrélations inconnues ou d’autres types de données significatives. Les applications sont nombreuses :

– Faire des inférences à partir des données de la base, afin d’effectuer des prédictions. Par exemple analyser les données relatives aux clients pour prédire le risque d’offrir un crédit à un nouveau consommateur, sur la base de l’âge, des revenus et d’autres facteurs.

– Découvrir automatiquement certaines configurations de données particulières, structures ou relations qui seraient passées inaperçues autrement. Cela autorise des requêtes comme  » quels objets se vendent bien en même temps ? « , dans le but d’encourager le phénomène en plaçant ces produits côte à côte dans le magasin (ou offrir des promotions en vendant ces produits ensembles).

– Détecter automatiquement les déviations, comme les objets dont les ventes sont loin d’être celles auxquelles on aurait pu s’attendre par rapport aux ventes de l’année précédente.

– Analyser en profondeur de telles déviations, pour tenter d’en déterminer les causes (la baisse des ventes est elle corrélée à un changement dans le produit, le packaging ou le prix ?).

– Comparer différents types de clients pour déterminer leurs profils, ou identifier automatiquement des groupes de consommateurs homogènes.

 

Les informations ainsi obtenues sont automatiquement présentées sous les formes graphiques les plus adaptées à leur compréhension.

Le data mining est surtout adapté à des données numériques (âge, revenus, prix…) ou des champs de texte simples (nom, adresse, profession, etc…). Les grand blocs de données textuelles, comme des liste de mots ou des romans entiers, sont beaucoup plus difficiles à traiter. Mais le text mining, une branche du datamining dédiée à l’analyse de textes, arrive à des résultats de plus en plus probants. Par exemple, il est possible de corriger et compléter automatiquement des listes de mots en inférant les règles grammaticales qui les sous-tendent à partir de l’analyse de l’ensemble des mots de la base.

 

L’avenir du data mining

Directement lié aux technologies de l’information, le data mining est une technologie émergente en pleine expansion. On peut espérer de rapides améliorations, directement liées à l’intégration des nouvelles théories issues des disciplines sur lesquelles il s’appuie. Mais le data mining est encore un adolescent qui a encore beaucoup à apprendre, et plusieurs problèmes à surmonter.

L’un des défis les plus importants sera l’amélioration de l’évaluation intelligente des données. Il faudra incorporer plus d’informations pertinentes dans les bases de connaissances, qui contiennent le savoir nécessaire à l’estimation de l’intérêt des patterns. On y trouve par exemple les croyances de l’utilisateur, ou des hiérarchies de concepts. Une hiérarchie de concepts permet d’observer les données sous différents niveaux de détails : classer les clients par catégories d’âge (comme 15-25 ans, 26-45, etc.) plutôt que par âge, ou par continent plutôt que par ville ou par rue. Une telle hiérarchie de concepts ressemble à ça : rue < ville < région < pays < continent.

A l’avenir, les outils de data mining devraient aussi être capables de prédire le temps qu’il leur faut pour effectuer une tâche. Etant donné la vitesse phénoménale à laquelle s’accroît la quantité de données stockées, les algorithmes devront être assez performants pour rendre possibles la manipulation rapide de bases de données dont la taille se comptera en tera-octets.

On peut aussi espérer voir apparaître de nouveaux langages de requêtes, propres au data mining, permettant à l’utilisateur de définir des tâches de façon plus précise.

Mais le plus grand challenge sera certainement de réussir à créer des outils capables de découvrir des connaissances dans des données très différentes, comme celles circulant sur internet. Le web est le plus énorme réservoir de données au monde, mais aujourd’hui il est encore difficile d’analyser automatiquement des données multimédia ou des textes de nature et de formats très divers. L’avenir du data mining passe donc par de puissants outils de recherche et d’analyse du contenu d’internet