Science Tribune

Science Tribune - Article - Octobre 1997 Connaissez-vous le data mining ?

Christophe Le Bret
PMSI, 52 rue Mouffetard, F 75005 Paris, France. Tel/Fax : 33 - 01 45 35 87 99
E-mail : pmsi@altern.com.

Data mining et statistiques
Le data mining est le descendant et, selon certains, le successeur des statistiques telles qu'elles sont utilisées actuellement. Statistiques et data mining ont le même but, qui est de réaliser des modèles compacts et compréhensibles rendant compte des relations liant la description d'une situation à un résultat (ou un jugement) concernant cette description. La différence essentielle est que les techniques de data mining construisent ledit modèle de manière automatique alors que les techniques statistiques "classiques" requièrent d'être maniées - et guidées - par un statisticien professionnel. Les techniques de data mining apportent un gain énorme tant en performance qu'en maniabilité ou en temps de travail. La possibilité de réaliser ses propres modèles statistiques par soi-même sans besoin de sous-traiter ou de se concerter avec un statisticien apporte une grande liberté aux utilisateurs opérationnels.

Pourquoi le data mining est une bonne idée
En construisant spontanément un modèle des dépendances au lieu de vérifier les hypothèses d'un statisticien, les techniques de data mining ramènent parfois des trésors à la surface, comme par exemple l'association entre le syndrome de Reyes et la prise d'aspirine chez les enfants, ou, moins sérieusement, la corrélation entre les achats de couches et de bière le samedi après-midi dans les supermarchés américains.

Ce dernier exemple illustre bien la nécessité de connaître son métier - mais rien que son métier - pour faire du data mining: seul un spécialiste connaissant sa clientèle peut interpréter une corrélation brute pour en faire le portrait d'un jeune couple faisant ses courses, la femme achetant des couches pendant que le père fait un stock de bière en prévision du match de foot du dimanche après-midi. Les techniques de data mining nous dispensent d'un statisticien, mais il reste indispensable de maîtriser son métier. Des corrélations-surprise telles que celle-ci n'arrivent quand même pas très souvent; les principaux avantages du data mining restent la vitesse et la simplicité.

Ces techniques permettent de plus de traiter de grandes quantités d'exemples (plusieurs millions) sans inconvénient. Elles sont également capables de faire face à un grand nombre de variables prédictives (jusqu'à plusieurs milliers). Ceci est extrêmement utile pour faire de la "sélection de variables" (déterminer les plus utiles pour un problème donné parmi une grande masse).

Plusieurs sortes de modèles statistiques
Comme pour tout ce qui est produit par des machines, les prédicteurs fabriqués par data mining doivent pouvoir être inspectés par les personnes familières avec le problème, pour comprendre et vérifier ce qui a été produit. Il est donc important que ces prédicteurs aient une forme aisément lisible et, si possible, déjà connue en dehors du domaine. Il existe un compromis entre la clarté du modèle et son pouvoir prédictif. Plus un modèle prend une forme simple, plus il sera facile à comprendre, mais moins il sera capable de prendre en compte des dépendances subtiles ou trop variées ("nonlinéaires"). Une représentation de ce compromis est dessinée dans la figure ci-dessous.

Les arbres de décision et les bases de règles sont très faciles à interpréter mais ne connaissent que les limites "dures" de comparaison à des seuils avec décision Oui-Non. Ils manquent de finesse prédictive.
Les grilles de score, linéaires ou à fonctions logistiques, sont un peu plus "fines" mais, de par leur caractère seulement additif, ne peuvent rendre compte de relations multivariables (exemple: le risque augmente en fonction de l'âge pour les propriétaires, il diminue en fonction de l'âge pour les locataires).
Les réseaux de neurones (a) sont les rois de la prédiction statistique (ayant également la capacité de s'accommoder de valeurs très bruitées ou même manquantes), mais ils sont complètement impossibles à inspecter - c'est comme si on voulait examiner le cerveau de quelqu'un pour savoir ce qu'il pense ! On ne peut qu'inspecter et visualiser les prédictions faites. Cependant, un bon outil de visualisation permet à l'utilisateur de reconstruire le "raisonnement" du réseau de neurones. Selon le prix à payer, et une fois la confiance en l'outil établie, l'utilisateur jugera souvent que la perte partielle de compréhension est plus que compensée par la qualité des prédictions.

Comment les modèles sont construits
Aucun des modèles statistiques présentés précédemment n'est nouveau. Les arbres de décision et de régression (classification and regression trees ou "CART") furent utilisés en sciences sociales dans les années 60; les bases de règles ont été popularisés lors de la vogue des "systèmes experts" dans les années 80; et les grilles de score sont familières aux banquiers depuis des décennies. Même les réseaux de neurones sont avec nous depuis les années 40, mais il a fallu les gains énormes en puissance de calcul de ces dernières années pour qu'ils deviennent enfin utilisables simplement.

La plupart de ces prédicteurs sont fabriqués, non pas par calcul direct à partir des données comme dans le passé, mais par des méthodes empruntées au domaine de l'intelligence artificielle Les deux techniques principales sont :
- l'apprentissage (partir d'un modèle "quelconque" et l'ajuster progressivement à la réalité)
- l'évolution (ou "vie artificielle", partir d'une population de plusieurs milliers de modèles "quelconques" et les faire "évoluer" de manière compétitive, "Darwinienne").
Traditionnellement, mais pas obligatoirement, l'apprentissage est appliqué seulement aux réseaux de neurones (quoique la technique de "rétropropagation de l'erreur" soit applicable à une grande variété d'objets), et les techniques d'évolution ("algorithme génétique" (b)) sont appliquées à la production de bases de règles, d'arbres de décision, et de grilles de score.

De plus, tous les outils permettent de déterminer l'importance de chaque variable pour la décision ("pertinences"). Ceci est extrêmement utile pour faire la sélection des variables. Une fois les variables les plus pertinentes déterminées avec précision, il est éventuellement possible de reprendre le problème avec des techniques plus conventionnelles si des contraintes d'exploitation l'imposent.

Text mining
Toutes les techniques évoquées jusqu'ici ne traitent que des données numériques ou qualitatives. Nous avons un autre problème, de plus en plus pressant, qui est d'extraire automatiquement de l'information à partir de masses de données textuelles. La quantité énorme de références ramenées lors d'une recherche sur Internet illustre très bien ce problème.

La recherche littérale simple a montré ses limites depuis longtemps; il y a de nombreux problèmes, notamment les fautes de frappe, la synonymie, les acceptions multiples, etc. En un mot, il est nécessaire d'insuffler à l'ordinateur un certain bon sens ou "connaissance du monde". Là encore, la mémoire et la puissance de calcul disponibles de nos jours permet certaines solutions pas forcément très élégantes, mais puissantes et rapides. Nos techniques de "fuzzy string matching" et de recherche de contexte donnent d'excellents résultats dans la pratique.

Conclusion
L'arrivée du data mining est seulement la dernière étape de l'introduction de méthodes quantitatives, scientifiques dans le monde du commerce, de l'industrie et des affaires. Maintenant tous les non-statisticiens - c'est-à-dire 99,5% d'entre nous - peuvent construire des modèles exacts de certaines de leurs activités, pour mieux les étudier, les comprendre et les améliorer.

Pour la première fois de leur histoire, les statistiques sortent des mains des spécialistes. L'art du spécialiste est remplacé par des méthodes nouvelles qui donnent des résultats aussi bons ou meilleurs sans demander de connaissances spécialisées.

Le data mining et le text mining sont certainement les applications les plus utiles de la puissance croissante des ordinateurs, et le domaine de recherche le plus intéressant de l'Informatique Avancée.

Notes
(a) Les réseaux de neurones sont un outil d'analyse statistique permettant de construire un modèle de comportement à partir d'un certain nombre d'exemples (constitués d'un certain nombre de "variables descriptives") de ce comportement. Le réseau de neurones, "ignorant" au départ, réalise un "apprentissage" à partir de ces exemples et devient, par modifications successives, un modèle rendant compte du comportement observé en fonction des variables descriptives.

La construction du modèle est automatique et directe à partir des données ; elle ne nécessite pas d'intermédiaire rare ou coûteux comme un expert ou un "cogniticien". Par exemple, en faisant apprendre à un réseau de neurones des descriptions d'emprunteurs d'argent (situation de famille, profession, etc.), avec leur comportement passé vis-à-vis du remboursement, on peut construire un modèle du risque associé aux descriptions des clients. Si maintenant on demande des prédictions à ce modèle sur des nouveaux dossiers, on constate que le réseau de neurones prédit correctement si l'emprunteur sera bon, ou bien mauvais payeur dans 80 à 95 % des cas. Il s'agit ici de ce que l'on appelle segmentation ou classification.

Dans tous les cas, le réseau de neurones construit est bel et bien un modèle sur mesures en fonction des exemples qu'il voit : il ne répète pas bêtement le passé. Il ne s'agit non plus d'aller chercher un modèle plus ou moins approprié parmi une bibliothèque. S'il existe effectivement une relation de cause à effet entre les descriptions en entrée (profil d'emprunteur, cours précédents d'une action, relevés de mesures, point de fonctionnement désiré) et les valeurs à prédire (risque de "casse" du prêt, cours de l'action dix jours plus tard, nature de la panne, variables de commande), le réseau la dénichera.

Le réseau de neurones est robuste. Il n'est pas handicapé par quelques exemples bruités ou faux : ceux-ci sont écartés car ils sont incohérents avec le reste. Les valeurs manquantes sont également gérées habilement et ne nuisent pas à la construction du modèle.

Dans un tout autre domaine, il est possible d'apprendre à associer des relevés de mesures sur une machine-outil à ses pannes: le prédicteur obtenu réalise une maintenance préventive en indiquant la possibilité de panne dès que les mesures prennent des valeurs qu'il estime suspectes (ou un diagnostic à partir des derniers relevés si on est arrivé trop tard). Ceci s'est beaucoup fait, par exemple pour le diagnostic vibratoire des machines tournantes. De même, en automatique et en commande, il est possible de modéliser le comportement d'un réacteur chimique ou d'un robot. Le réseau de neurones indique, pour le point de fonctionnement que vous désirez, quelles sont les valeurs nécessaires des variables de commande.

Cette capacité d'apprendre tout ce qui a un sens (approximateur universel) a été établie rigoureusement ("Théorème de Kolmogorov"). Les réseaux de neurones sont un outil rigoureux aux bases démontrées. Il ne s'agit pas d'un hack ou d'une "usine à gaz" dont "on ne sait pas pourquoi ça marche".

La raison pour laquelle cette méthode se popularise seulement maintenant est la puissance de calcul nécessaire pour la mettre en oeuvre : un apprentissage qui prend 30 mn sur un IBM-PC Pentium en 1997 aurait demandé 320 h sur un IBM-PC XT en 1982 - 13 jours et 13 nuits. Même les inventeurs de l'apprentissage des réseaux de neurones, dans les années 1970, auraient dû réquisitionner les ressources de la NASA pour construire un prédicteur neuronal sur 50 000 clients d'une banque. Une autre raison est que de plus en plus d'activités disposent d'enregistrements informatiques. Le proverbe "Les données ne sont pas données" est heureusement de moins en moins vrai.

(b) L'algorithme génétique permet d'obtenir des solutions à un problème n'ayant pas de méthode de résolution décrite précisément, ou dont la solution exacte, si elle est connue, est trop compliquée pour être calculée en un temps raisonnable. C'est notamment le cas quand des contraintes multiples et complexes - et parfois même en partie contradictoires - doivent être satisfaites simultanément, comme par exemple pour constituer des équipes de travail, planifier des tournées de livraison, implanter des points de vente de manière optimale, construire des modèles statistiques, etc.

Selon l'algorithme génétique, de nombreuses solutions, plus ou moins bonnes, au problème donné sont créées au hasard, selon une forme définie à l'avance: itinéraire, emploi du temps, base de règles de décision, grille de score, réseau de neurones, etc . Ces solutions sont représentées chacune par une chaîne de 0 et de 1 ou "chromosomes", qui sont alors soumis à une imitation de l'évolution des espèces: mutations et reproduction par hybridation. En favorisant la survie des plus "aptes" (les solutions les plus correctes), on provoque l'apparition d'hybrides meilleurs que chacun de leurs parents. Une "fonction de décodage" sert à "traduire" la représentation sous forme de chromosomes 0-1 en la forme qui nous intéresse. La population initiale donne ainsi naissance à des générations successives, mutés et hybridés à partir de leurs "parents". Le mécanisme de favorisation des éléments les plus aptes (pression de l'évolution) assure que les générations successives sont de plus en plus adaptées à la résolution du problème. Ce mécanisme surprenant a été rigoureusement validé mathématiquement.

Le mécanisme d'évolution et de sélection est indépendant du problème à résoudre: seules varient la fonction qui décode le génotype en une solution possible (tout décodage peut être utilisé, de préférence le plus simple possible) et celle qui évalue la justesse de la solution (dans le cas de prédicteurs, en les testant sur quelques centaines de cas). Cette technique est d'application générale.

L'algorithme génétique peut être appliqué à la production d'une variété d'objets, tant qu'il est possible d'avoir une note représentant la justesse de la solution. En particulier, il est possible de fabriquer des prédicteurs statistiques, non pas par calcul à partir des données comme dans les statistiques classiques, mais en les faisant évoluer par algorithme génétique ("induction"). Pour des problèmes de classification ou de segmentation, la justesse est tout simplement le taux de reclassements du prédicteur sur un ensemble d'exemples fourni. Le mécanisme d'encouragement du plus apte permet alors l'apparition du prédicteur reclassant le mieux les données. Ce type de construction de prédicteur fait partie des techniques dites de data mining.

Les prédicteurs produits peuvent avoir une variété de formes (voir texte principal): bases de règles, grilles de score, arbres de décision, même des réseaux de neurones. Les outils correspondants de PMSI sont Galvano Bases de règles, Galvano Score, Galvano Arbres de Décision et GalvaNeurones.

Pourquoi cette technique est intéressante : Il s'agit d'une approche un peu brutale, nécessitant une grande puissance de calcul, mais présentant l'immense avantage pratique de fournir des solutions pas trop éloignées de l'optimal, même si l'on ne connaît pas de méthode de résolution. L'algorithme génétique n'exige aucune connaissance de la manière dont résoudre le problème; il est seulement nécessaire de pouvoir évaluer la qualité d'une solution. Il est également léger à mettre en oeuvre (le "moteur" est commun, il y a peu de programmation spécifique au problème à faire).

La différence de rapidité entre une approche algorithmique (spécifique, très rapide) et la résolution du même problème par l'algorithme génétique (général mais plus lent) illustre une des différences entre les deux méthodes:

	Approche ad hoc (analytique, spécifique)	Approche génétique
Rapidité	Selon solution, en général bonne	Faible ou moyenne
Performance	Selon solution	Moyenne à bonne
Compréhension du problème	Nécessaire	Non nécessaire
Travail humain	De quelques minutes à quelques thèses	Quelques heures
Applicabilité	Faible*	Générale
Etapes intermédiaires	Ne sont pas des solutions (il faut attendre la fin des calculs)	Sont des solutions (le processus peut être interrompu à tout moment)

*La plupart des problèmes intéressants n'ont pas d'expression mathématique exploitable, ou sont non-calculables, ou "NP-complets" (trop de possibilités).