Data mining

L’exploration de données, aussi connue sous les noms fouille de données, data mining (forage de données) ou encore Extraction de Connaissances à partir de Données (ECD en français, KDD en Anglais), a pour objet l’extraction d'un savoir ou d'une connaissance à partir de grandes quantités de données, par des méthodes automatiques ou semi-automatiques, et l'utilisation industrielle ou opérationnelle de ce savoir.

Elle est utilisée dans le monde professionnel pour résoudre des problématiques très diverses, allant de la gestion de relation client à la maintenance préventive, en passant par la détection de fraudes ou encore l'optimisation de sites web.

Sommaire 1 Définition générale 2 Exemples d'applications 3 Principe et spécificité 3.1 Principe 3.2 Le data mining est un processus 3.3 Méthode 3.4 Anecdotes 4 Algorithmes 4.1 Les méthodes non-supervisées 4.2 Les méthodes supervisées 4.3 Les méthodes de réduction de données 4.4 Pourquoi tant d'algorithmes ? 4.5 Chercher d'autres algorithmes, ou bien enrichir les données ? 5 Voir aussi 5.1 Liens internes 5.2 Références 5.3 Bibliographie

Définition générale

Le data mining est un processus d'extraction de connaissances valides et exploitables à partir de grands volumes de données.

Il a vocation à être utilisé dans un environnement professionnel et se distingue de l'analyse de données et de la statistique par les points suivants :

• Contrairement à la méthode statistique, le data mining ne nécessite jamais que l'on établisse une hypothèse de départ qu'il s'agira de vérifier. Ce sont des données elles-mêmes que sont déduites les corrélations intéressantes, le logiciel n'étant là que pour les découvrir (le data mining se situe à la croisée des statistiques, de l'intelligence artificielle, des bases de données).
• Les connaissances extraites par le data mining ont vocation à être intégrées dans le schéma organisationnel de l'entreprise ou de l'entité considérée. Le data mining impose donc d'être capable d'utiliser de manière opérationnelle les résultats des analyses effectuées, souvent dans des délais très courts. Le processus d'analyse doit permettre à l'organisation une réactivité (très) importante.
• Les données traitées sont issues des systèmes de stockage en place dans l'organisation et sont ainsi hétérogènes, multiples, plus ou moins structurées. Leur raison d'être n'est donc a priori pas l'analyse (sauf dans le cas d'un entrepôt de données). Cela impose de disposer de systèmes performants de préparation ou de manipulation de données.

Le data mining se propose de transformer en information, ou en connaissance, de grands volumes de données qui peuvent être stockées de manière diverse, dans des bases de données relationnelles, dans un (ou plusieurs) entrepôt de données (datawarehouse), mais qui peuvent aussi être récupérées de sources riches plus ou moins structurées comme internet, ou encore en temps réel (appel à un call center, retrait d'argent dans un distributeur à billets...).

Lorsque la source n’est pas directement un entrepôt de données, il s'agit très souvent de construire une base de données ou un datamart dédié à l'analyse et aux analystes. Cela suppose d'avoir à sa disposition une palette d'outils de gestion de données (data management). On peut également structurer les données de l’entrepôt sous forme d’un hypercube OLAP, même si cela est assez rare en matière de data mining.

Exemples d'applications

On peut relever parmi les utilisations du data mining les exemples suivants :

• Analyser les comportements des consommateurs : ventes croisées (voir l’anecdote de Wal-Mart ci-après), similarités de comportements, cartes de fidélité, …
• Prédire le taux de réponse à un mailing ou à une opération de marketing direct (par exemple pour en optimiser les coûts)
• Prédire l’attrition (ou churn) des clients : quels sont les indices de comportement permettant de détecter la probabilité qu’un client a de quitter son fournisseur (sa banque, son opérateur de téléphonie mobile, …)
• Détecter des comportements anormaux ou frauduleux (transactions financières, escroquerie aux assurances, distribution d’énergie, …)
• Rechercher des critères qui permettront d’établir ensuite une évaluation pour repérer les « bons » clients sans facteur de risque (Évaluation des risques-clients) et leur proposer peut-être une tarification adaptée (par exemple pour une banque ou une compagnie d’assurance).
• Suggérer lors d’un appel à un call center, en temps réel, une réponse de l’opérateur qui soit adaptée

Les outils de text mining (fouille de textes) associent en complément aux principes du data mining, l’analyse lexicographique et/ou linguistique multilingue des données non structurées comme les courriels, les réponses à des questionnaires ou à des enquêtes, les réclamations clients, les blogs Internet, les news en ligne, les tchats… en tentant de déterminer par exemple le degré de satisfaction (ou d’insatisfaction) de la clientèle. Ses applications les plus rudimentaires sont la lutte contre le spam, ou pourriel, ainsi que l’analyse de contenu. De plus ambitieuses concernent l’évaluation par analyse de dépêches de presse, de l’image d’une société, d’un climat politique ou boursier, ou la catégorisation automatique d’informations.

Principe et spécificité

Principe

Le data mining est un processus d'analyse dont l'approche est différente de celle utilisée en statistique. Cette dernière présuppose en général que l'on se fixe une hypothèse que les données permettent ou non de confirmer. Au contraire, le data mining adopte une démarche sans a priori (approche pragmatique) et essaie ainsi de faire émerger, à partir des données brutes, des inférences que l'expérimentateur peut ne pas soupçonner, et dont il aura à valider la pertinence.

Le data mining tente alors de réaliser un arbitrage entre validité scientifique, interprétabilité des résultats et facilité d'utilisation, dans un environnement professionnel où le temps d'étude joue un rôle majeur et où les analystes ne sont pas toujours des statisticiens.

Le data mining est un processus

Plus qu'une théorie normalisée, le data mining est un processus d'extraction de connaissances métiers comportant les étapes principales suivantes :

• Formaliser un problème que l'organisation cherche à résoudre en termes de données
• Accéder aux données appropriées quelles qu'elles soient
• Préparer ces données en vue des traitements et utilisations futurs
• Modéliser les données en leur appliquant des algorithmes d'analyse
• Évaluer et valider les connaissances ainsi extraites des analyses
• Déployer les analyses dans l'entreprise pour une utilisation effective

Ce processus est cyclique et permanent; le data mining rend dès lors plus compréhensible, "visible", l'activité de l'organisation, et permet de rationaliser le stockage de l'information et des données. Le data mining ne consiste pas en une succession d'études ad hoc mais a pour objectif de capitaliser des connaissances acquises sous forme de connaissances explicites.

Il conduit donc à mieux structurer les contenus nécessaires à l'ingénierie des connaissances. C'est sa principale raison d'être ; on peut comparer de façon lointaine cette activité à celle de conceptualisation au cours de l'apprentissage humain : « Une bonne compréhension est intimement liée à une bonne compression » explique Donald Knuth^[1], l'une comme l'autre utilisant une connaissance de corrélations pour représenter - et donc manier - l'information sous forme plus concise.

Méthode

Le data mining se propose d'utiliser un ensemble d'algorithmes (voir infra) issus de disciplines scientifiques diverses (statistiques, intelligence artificielle, base de données) pour construire des modèles à partir des données, c'est-à-dire trouver des schémas « intéressants » (des patterns ou motifs en français) selon des critères fixés au départ, et extraire de ces données un maximum de connaissances utiles à l'entreprise.

Voir par exemple les articles :

• Motif de conception
• algorithmes génétiques,
• Arbre de décision

Anecdotes

Les premiers essais de fouilles de données se firent historiquement sur des dépouillements de millions de tickets de caisse de supermarché tels que mémorisés par les caisses enregistreuses.

À l’origine de la vulgarisation des méthodes et des algorithmes de la fouille de données (en l’occurrence, l’analyse des associations), il y aurait eu la mise en évidence par les magasins Wal-Mart d’une corrélation très forte entre l’achat de couches pour bébés et de bière le samedi après-midi^[2]. Les analystes s'aperçurent alors qu'il s'agissait des messieurs envoyés au magasin par leur compagne pour acheter les volumineux paquets de couches pour bébé. Les rayons furent donc réorganisés pour présenter côte à côte les couches et les packs de bière ... dont les ventes grimpèrent en flèche ! Cette image plus ou moins véridique illustre le retour sur investissement (ROI) des travaux de data mining et plus généralement d'informatique décisionnelle.

D’autres analyses, en particulier d’indices précurseurs de modification des habitudes d’achat, se montrèrent d’un plus grand intérêt dans la pratique.

Un autre exemple souvent cité est le suivant : si on baisse le prix du Coca-Cola de 5%, on va par exemple en augmenter les ventes de 15%, ce que l'on savait sans data mining. Mais le data mining révèle l'élément inattendu (bien qu'évident a posteriori), à savoir que les ventes des cacahuètes vont augmenter dans une proportion voisine (sans doute suite à l'association d'idées : « Puisque j'achète du Coca, il me faut aussi des cacahuètes » ; le data mining ne fait pas d'hypothèse sur le sujet). Si la marge sur le Coca-Cola est relativement faible, et celle sur les cacahuètes importante, la conclusion s'impose d'elle-même : baisser le prix du Coca-Cola est un moyen de vendre davantage de cacahuètes.

Par le côté quasi-déterministe qu'elle présente du comportement du consommateur, cette approche provoque souvent une réaction de septicisme, mais dès lors que les résultats de sa mise en œuvre sont au rendez-vous, ce qui est quelquefois le cas, son adoption ne pose ensuite pas de problème particulier.

Algorithmes

Résoudre une problématique avec un processus de data mining impose généralement l'utilisation d'un grand nombre de méthodes et algorithmes différents. On peut distinguer 3 grandes familles d'algorithmes :

Les méthodes non-supervisées

Elles permettent de travailler sur un ensemble de données dans lequel aucune des données ou des variables à disposition n'a d'importance particulière par rapport aux autres, c'est-à-dire un ensemble de données dans lequel aucune variable n'est considérée individuellement comme la cible, l'objectif de l'analyse. On les utilise par exemple pour dégager d'un ensemble d'individus des groupes homogènes (typologie), pour construire des normes de comportements et donc des déviations par rapport à ces normes (détection de fraudes nouvelles ou inconnues à la carte bancaire, à l'assurance maladie...), pour réaliser de la compression d'informations (compression d'image)...

Voici une liste non exhaustive des techniques disponibles :

• Techniques à base de Réseau de neurones : carte de Kohonen (SOM/TOM) (carte auto adaptative)...
• Techniques utilisées classiquement dans le monde des statistiques : classification ascendante hiérarchique, k-means et les nuées dynamiques (Recherche des plus proches voisins), les classification mixtes (Birch...), les classifications relationnelles...
• Les techniques dites de recherche d'associations (elles sont à l'origine utilisées pour faire de l'analyse dite de panier d'achats ou de séquences, c'est-à-dire pour essayer de savoir parmi un ensemble d'achats effectués par un très grand nombre de clients et de produits possibles, quels sont les produits qui sont achetés simultanément (pour un supermarché par exemple ; elles sont également appliquées à des problèmes d'analyse de parcours de navigation de site web). Ces techniques peuvent donc être utilisées de manière supervisées) : algorithmes a priori, GRI, Carma, méthode ARD...
• Analyses de liens

Les méthodes supervisées

Leur raison d'être est d'expliquer et/ou de prévoir un ou plusieurs phénomènes observables et effectivement mesurés. Concrètement, elles vont s'intéresser à une ou plusieurs variables de la base de données définies comme étant les cibles de l'analyse. Par exemple, on utilisera ce type de méthode lorsque l'on cherchera à comprendre pourquoi un individu a acheté un produit plutôt qu'un autre, pourquoi un individu à répondu favorablement à une opération de marketing direct, pourquoi un individu a contracté une maladie particulière, pourquoi un individu a visité une page d'un site web de manière répétée, pourquoi la durée de vie après la contraction d'une maladie varie selon les malades... Voici une liste non exhaustive des techniques disponibles :

• Techniques à base d'arbres de décision (Arbre de décision) : CART, CHAID, ECHAID, QUEST, C5, C4.5, les forêts d'arbres...
• Techniques statistiques de régressions linéaires et non linéaires au sens large : Régression linéaire, Régression linéaire multiple, Régression logistique binaire ou multinomiale, Probit binaire, multinomial ou ordonné, Tobit, Cauchit, modèle Gamma, binomial négatif, log-log, Analyse discriminante linéaire ou quadratique, régression de cox, modèle linéaire généralisé, régression PLS, régressions non paramétrique, équations structurelles ... (voir aussi économétrie)
• Techniques à base de Réseau de neurones : perceptron mono ou multicouches avec ou sans rétropropagation des erreurs, les réseaux à fonction radiale de base...
• Techniques à base d'algorithme génétique.
• Techniques à base d'Inférence bayésienne (Réseau bayésien).
• Le Raisonnement par cas
• Le Filtrage collaboratif
• L'Exploration Hypercubique

Les méthodes de réduction de données

Elles permettent de réduire un ensemble de données volumineux à un ensemble de taille plus réduite, épuré de ce que l'on considérera comme de l'information non pertinente ou non signifiante, comme du bruit. Elles sont ainsi très souvent, mais pas systématiquement, utilisées en amont des techniques supervisées ou non supervisées. Elles sont notamment très complémentaires des techniques non supervisées classiquement utilisées dans le domaine de la statistique.

• Techniques d'Analyse factorielle : Analyse en composantes principales, Analyse en composantes indépendantes, analyse factorielle des correspondances, analyse des correspondances multiples, analyses factorielles (maximum de vraisemblance, moindres carrés non pondérés, avec ou sans rotation orthogonale ou oblique)...
• Techniques de positionnement : positionnement multidimensionnel...

Pourquoi tant d'algorithmes ?

Parce que nous venons de voir qu'ils n'ont pas tous le même objet, parce qu'aucun n'est optimal dans tous les cas, parce qu'ils s'avèrent en pratique complémentaires les uns des autres et parce qu'en les combinant intelligemment (en construisant ce que l'on appelle des modèles de modèles ou métamodèles) il est possible d'obtenir des gains de performance très significatifs, si l'on prend bien garde d'éviter des problèmes de sur-ajustement des modèles ainsi obtenus (voir à ce sujet l'article Arbre de décision et son paragraphe traitant du problème de sur-ajustement des modèles). Encore faut-il être en mesure de réaliser ces combinaisons facilement, ce que permettent les logiciels ateliers de Data Mining, par opposition aux outils de statistiques classiques dans lesquels l'opération est beaucoup plus délicate en pratique.

Chercher d'autres algorithmes, ou bien enrichir les données ?

L'université de Stanford a mis en concurrence à sa rentrée d'automne 2007 deux équipes sur le projet suivant : en s'appuyant sur la base de films visualisés par chaque client d'un réseau de distribution (abonnement avec carte magnétique) déterminer l'audience la plus probable d'un film qui n'a pas encore été vu. Une équipe s'est orientée sur une recherche d'algorithme extrêmement fin à partir des informations de la base, une autre au contraire a pris des algorithmes extrêmement simples, mais a combiné la base fournie par le distributeur au contenu de l'Internet Movie Database (IMDB) pour enrichir ses informations. La seconde équipe a obtenu des résultats nettement plus précis. Un article écrit à ce sujet suggère que de la même façon l'efficacité de Google tient bien moins à son algorithme de page rank qu'à la très grande quantité d'information que Google peut corréler par croisement des historiques de requête, de la correspondance et du comportement de navigation sur ses sites de ses utilisateurs. (lien vers l'article en instance)

Voir aussi

Liens internes

• Fouille de textes
• Fuite d'information
• Datawarehouse et Datamart
• Arbre de décision
• Traitement automatique du langage naturel
• IMSL Bibliothèques Numériques
• Recherche d'information
• Linguistique calculatoire
• Apprentissage artificiel

Références

Bibliographie

• Dean W. Abbott, I. Philip Matkovsky, and John Elder IV, Ph.D. An Evaluation of High-end Data Mining Tools for Fraud Detection, 1998 IEEE International Conference on Systems, Man, and Cybernetics, San Diego, CA, October 12-14, 1998.
• Alain Baccini et Philippe Besse, Data mining I - Exploration Statistique, Université de Toulouse : cours au format pdf
• Philippe Besse, Data mining II - Modélisation Statistique et Apprentissage, Université Pde Toulouse : cours au format pdf
• Phiroz Bhagat, Pattern Recognition in Industry, Elsevier, ISBN 0-08-044538-1
• Richard O. Duda, Peter E. Hart, David G. Stork, Pattern Classification, Wiley Interscience, ISBN 0-471-05669-3, (voir aussi Présentation Powerpoint)
• Yike Guo and Robert Grossman, editors: High Performance Data Mining: Scaling Algorithms, Applications and Systems, Kluwer Academic Publishers, 1999.
• Mierswa, Ingo and Wurst, Michael and Klinkenberg, Ralf and Scholz, Martin and Euler, Timm: YALE: Rapid Prototyping for Complex Data Mining Tasks, in Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-06), 2006.
• Daniel T. Larose (adaptation française T. Vallaud): Des données à la connaissance² : Une introduction au data-mining (1Cédérom), Vuibert, 2005
• René Lefébure et Gilles Venturi, Data Mining : Gestion de la relation client, personnalisations de site web, Eyrolles, mars 2001
• Pascal Poncelet, Florent Masseglia and Maguelonne Teisseire (Editors). Data Mining Patterns: New Methods and Applications, Information Science Reference, ISBN 978-1599041629, (October 2007).
• Ricco Rakotomalala, Supports de cours Data Mining, cours au format pdf
• Ricco Rakotomalala, Tutoriels Data Mining, description et données pour plusieurs logiciels
• Pang-Ning Tan, Michael Steinbach and Vipin Kumar, Introduction to Data Mining (2005), ISBN 0-321-32136-7 (companion book site)
• Kurt Thearling, An Introduction to Data Mining (voir également le tutorial correspondant en ligne)
• Stéphane Tufféry, Data Mining et Statistique Décisionnelle, Technip, nouvelle édition revue et enrichie, juin 2007
• Stéphane Tufféry, The Data mining Page, mars 2007 : cours au format pdf
• Ian H. Witten and Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques, Morgan Kaufmann, 2005. Site web
• Ian Witten and Eibe Frank, Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations (2000), ISBN 1-55860-552-5, (voir aussi Free Weka Software)

• Portail de l’informatique
• Portail des probabilités et des statistiques