Exploration de données - Définition

Algorithmes

Classement des 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 d'algorithmes différents plus ou moins faciles à comprendre et à utiliser. On peut distinguer deux grandes familles d'algorithmes: les méthodes descriptives et les méthodes prédictives.

Méthodes descriptives

Repérer les données aberrantes et les éliminer.

Ce sont des méthodes qui permettent d'organiser, de simplifier, d'aider à comprendre l'information sous-jacente à un ensemble important de données. Elles permettent de travailler sur un ensemble de données dans lequel aucune des variables explicatives des individus n'a d'importance particulière par rapport aux autres. 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)...

Parmi les techniques disponibles on peut utiliser:

• Les analyses factorielles: elles permettent de dégager les variables cachées (les facteurs) dans un ensemble de mesures. Dans les analyses factorielles on part du principe que si les données sont dépendantes c'est parce qu'elles sont liées à des facteurs qui leur sont communs. Les techniques factorielles se décomposent en analyse en composantes principales, analyse en composantes indépendantes, analyse factorielle des correspondances, analyse des correspondances multiples, positionnement multidimensionnel...

• La Classification (non supervisée) : ce sont des méthodes qui permettent de regrouper des individus en classes, dont la caractéristique est que les individus d'une même classe se ressemblent, tandis que ceux de deux classes différentes sont dissemblables. Les classes de la classification ne sont pas connues au préalable, elles sont découvertes par le processus. D'une manière générale, les méthodes de classification servent à rendre homogènes des données qui ne le sont pas à priori, et ainsi permettent de traiter chaque classe avec des algorithmes sensibles aux données 'aberrantes'. Dans cette optique, les méthodes de classification forment une première étape du processus d'analyse. On distingue notamment:

• le partitionnement: il s'agit par exemple des méthodes des centres mobiles,« k-means » (les nuées dynamiques en français), les « k-medoids », k-modes et k-prototypes, les réseaux de Kohonen; l'algorithme EM, AdaBoost et la classification par agrégation des similarités.
• la classification hiérarchique: parmi les méthodes hiérarchiques on trouve les méthodes ascendantes où on part des individus qu'on agrège en classes, et des méthodes descendantes où on part du tout et par divisions successives on arrive aux individus qui composent les classes.
• le recouvrement à logique floue

• Les Associations: 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 APriori, GRI, Carma, méthode ARD, PageRank...
• Corrélation: les analyses de liens

Méthodes prédictives

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 a 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. En exploration de données prédictive, il y a deux types d'opérations : la discrimination (ou classement) et la régression (ou prédiction) tout dépend du type de variable à expliquer. La discrimination s’intéresse aux variables qualitatives, tandis que la régression s’intéresse aux variables continues.

• Classement (classification supervisée) et Prédiction

Les méthodes de classement (et de prédiction) permettent de séparer des individus en plusieurs classes. Si la classe est connue au préalable et que l'opération de classement consiste à analyser les caractéristiques des individus pour les placer dans une classe, alors on a à faire à une méthode supervisée. Dans le cas contraire, les anglo-saxons parlent de méthodes non-supervisées. La différence entre les méthodes descriptives de classification et les méthodes prédictives de classement provient du fait que les premières « réduisent, résument, synthétisent les données » alors que les secondes expliquent une ou plusieurs variables.

• exemples de méthodes prédictives

• Arbre de décision : CART, CHAID, ECHAID, QUEST, C5, C4.5, les forêts d'arbres décisionnels, le Raisonnement par cas...

• Statistiques : Techniques 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, Loi log-logistique, 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)

• Réseau de neurones : les perceptrons mono ou multicouches avec ou sans rétropropagation des erreurs, les Neurones à base radiale...

• Algorithmes génétiques : certains en appui des Réseaux Bayésiens , d'autres comme Timeweaver en recherche d'évènements rares
• Inférence bayésienne : Réseau bayésien
• Aide à la décision  : L'Exploration Hypercubique
• Marketing  : Le Filtrage collaboratif

Pour connaitre les conditions dans lesquelles on peut employer ces algorithmes, voici un tableau qui quelles sont les algorithmes à employer en fonction des types de variables explicatives et celui des variables à expliquer :

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 le paragraphe traitant du problème de sur-ajustement des modèles dans l'article Arbre de décision). 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. L'ICDM-IEEE a fait en 2006 un classement des 10 algorithmes qui ont le plus d'influence dans le monde du Data mining : ce classement est une aide efficace au choix et à la compréhension de ces algorithmes.

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.

Avec la qualité des moyens modernes de l'informatique l'une ou l'autre de ces deux solutions peut s'envisager dans chaque projet.