Mahout: explorez vos données (en plus de les stocker)

Apache Mahout est un nouveau projet (version 0.9 au moment où on rédige ce post) de data-mining. Le but de l’article est de vous présenter les techniques de data-mining, puis ce que Mahout propose.

Ce que le data-mining permet

En résumé, la problématique est d’extraire un peu de connaissance de beaucoup de données, et ceci de manière la plus automatisée possible. Par exemple, votre site de e-commerce vous suggère des articles en fonction de vos achats précédents, ou votre banque a détecté des opérations suspectes sur votre compte. L’exploration de données, donc, permet de répondre aux familles de problèmes suivants :

La recherche d’éléments anormaux : vous avez un compte bancaire, vous réalisez chaque semaine des opérations et la banque ne s’y oppose pas. Un jour, vous décidez de vous offrir un voyage à Hawaï, et l’ordre passe. La banque estime que ces opérations sont normales, même si c’est la première fois que vous voyagez. En revanche, un retrait de 15000€ en Russie sera considéré comme anormal, et donc vous recevrez un appel. La recherche d’éléments anormaux porte exactement sur ce genre de problématique : ce qui est normal, même nouveau, et ce qui nécessite une vérification pour comprendre ou une action pour protéger.
La description de classes et de concepts : On se donne des classes à l’avance, et on aimerait savoir classer une donnée non encore « étiquetée », ce qui est un problème de caractérisation. La caractérisation consiste à établir ce qui forme l’unité d’une classe. Par exemple, une banque peut lister les clients qui ne sont jamais à découvert, et chercher à comprendre ce qui les distingue intrinsèquement des autres clients. La discrimination porte sur la comparaison entre plusieurs classes, pour établir les différences fondamentales entre ces groupes. La différence avec la caractérisation est qu’on discrimine plusieurs classes et que l’étude ne porte pas sur les caractéristiques propres à une classe en particulier.
La recherche de liens consiste à essayer d’expliciter et de synthétiser des règles liant les variables qu’on analyse. Par exemple, expliquer la performance passée d’un indice boursier par la situation économique du secteur. Ainsi, la recherche de motifs fréquents et la recherche de règles d’association consistent à analyser des groupes de données pour isoler celles qui reviennent fréquemment ensemble. Les sites de e-commerce sont friands de ce genre de liens pour les conseils d’achats. La recherche de corrélations vise à produire un modèle plus simple mais plus approximatif d’un ensemble de données. Par exemple, la corrélation linéaire cherche à trouver une fonction linéaire qui approche « au mieux » des données en deux dimensions.
L’analyse prédictive part de classes connues et essaie de prédire le comportement ou les caractéristiques de nouvelles données. Ainsi, l’interpolation vise à prévoir le comportement futur d’une courbe (de ventes, de cours, de taux, de…) en fonction de situations passées. L’apprentissage constitue l’autre grande branche de l’analyse prédictive. L’apprentissage supervisé consiste à entrainer la machine sur un jeu de tests et sur des classes connues. Elle trouve une série de règles qui, appliquées à de nouvelles données, permettront de classer celles-ci dans la classe la plus vraisemblable. L’apprentissage non supervisé ne part pas de classes connues, celles-ci sont inférées en fonction de données. Contrairement au clustering (recherche de groupes non préalablement connus), le but est de classer de nouveaux éléments à partir de ce qu’on a compris sur les anciens.
Et enfin, le clustering, de son nom français regroupement, vise à grouper des données par vraisemblance, sans que l’on ait fourni des classes à l’avance. Et là, vous allez hurler: mais comment est-ce possible?! C’est à dire, comment peut-on classer des données sans connaitre les groupes à l’avance? Il y a plusieurs algorithmes, nous allons présenter celui des K-Moyennes. Sans mathématiques, parce qu’on aime les défis. Le principe consiste à avoir initialement autant de groupes que de données. A chaque étape de l’algorithme, on essaie de trouver des données similaires suivant une certaine métrique, et on fusionne des groupes si les données sont assez proches. Au final, il ne reste que quelques grands groupes, tous avec une forte cohésion interne (des caractéristiques proches), et une faible ressemblance avec les données des autres groupes. Les grands groupes sont ceux cherchés, et on renvoie les groupes, avec pour chacun ses membres.

Alors, il y a le bon modèle, et le mauvais modèle. Le bon modèle…

Dans tous les cas, l’efficacité de la solution se mesure suivant plusieurs axes:

• la solution trouvée doit évidemment être valide. Elle peut cependant paraître contradictoire avec ce que le business peut savoir. Elle doit être nouvelle, et apporter de la connaissance, donc elle doit être pertinente.
• viser une connaissance complète est vain, parce que l’algorithme peut générer des milliers de règles. Les corrélations les plus folles peuvent être trouvées. Il y a donc une différence entre la synchronicité et la corrélation. Il peut pleuvoir chaque fois que vous mettez une cravate verte, mais c’est un hasard.
• la solution doit être suffisamment simple pour être utilisable par des humains, mais avoir un taux d’erreur le plus bas possible. Ce compromis se comprend bien, par exemple, avec l’application d’une régression linéaire. Si les données sont fortement corrélées, l’interpolation linéaire est pertinente. Sinon, le calcul reste possible, mais le taux d’erreur sera trop élevé pour que le modèle soit utilisable. Une interpolation polynomiale sera peut être envisagée: elle est plus complexe, mais peut réduire le taux d’erreur.
• la solution devrait être peu sensible au choix des données initiales. C’est une question de représentativité de l’échantillon initial sur les problèmes d’apprentissage. Là aussi, il s’agit d’une question de compromis entre la taille des données initiales et la possibilité de trouver des liens.

Ce que Mahout offre

Apache Mahout implémente quatre familles d’algorithmes et un outil de traitement des données. Tout est résumé dans ce schéma :

Mahout applique des outils de data-mining à des vecteurs, c’est-à-dire, fondamentalement, des listes de nombres réels. Les données peuvent être distribuées, et Mahout s’interface avec Hadoop. D’autres sources comme un fichier sont tout à fait possibles par ailleurs. L’outil dispose également d’un parser de texte pour avoir une représentation numérique. Ceci réalisé, on peut faire face à un problème simple : au sein des vecteurs, on peut avoir des composantes qui sont liées les unes aux autres. Elles n’apportent fondamentalement pas de nouvelle information puisqu’elles répliquent celle d’autres composantes. On applique alors des algorithmes de réduction de dimension, dont un des buts est de supprimer les composantes qui sont fortement liées à d’autres. Par exemple, on peut passer d’un problème à 20 dimensions à un, plus simple, portant sur 4 ou 5 dimensions beaucoup plus pertinentes et non liées entre elles. Et on raisonne en général mieux en 4 dimensions qu’en 20. On a, à ce stade, des données « propres », et on peut commencer à utiliser les algorithmes de data-mining fournis par Mahout :

1. Fabriquer des vecteurs depuis les sources de données
2. Réduire les dimensions pour avoir des vecteurs c
   oncis et pertinents
3. Appliquer les algorithmes de data-mining

Quelques algorithmes proposés par Mahout (et leur but)

Evidemment, on ne peut pas ici rentrer dans tous les détails de l’utilisation de la logique floue chez Mahout. Mais, voici un premier aperçu de ce que la version 0.9 propose :

Recommandations :

Pour proposer aux clients ce qui serait le plus susceptible de les intéresser, Mahout propose deux grandes familles de techniques :

• Recommandations par comparaison avec les autres utilisateurs, ou recommandations en comparant les éléments achetés ensemble (donc, du point de vue du produit). Par exemple, si un groupe d’utilisateurs a de nombreux produits en commun avec vous, il est probable que vous achetiez ce que vous n’avez pas mais que le groupe a déjà consommé.
• La factorisation de matrices : l’idée, malgré un nom un peu déconcertant, reste simple : la matrice a en lignes les utilisateurs, et en colonnes les produits. On a donc les préférences de chaque client, et les valeurs de la matrice en mesurent l’intensité. Ces matrices se composent pour extrapoler ce que vous pourriez aimer.

Regroupement :

Un problème que rencontre la presse, ou les moteurs de recherche. Dans un texte, on peut avoir des thèmes communs, comme Agilité et Zenika, Gayet et Hollande, etc. Le regroupement peut aider à guider un utilisateur sur des articles qui peuvent l’intéresser au vu de ce que cette personne a déjà lu. Evidemment, la machine apprend les corrélations, personne n’aurait le temps de saisir manuellement toutes les combinaisons pertinentes. Mahout propose plusieurs algorithmes de clustering, tous basés, sur les techniques par k-moyennes et variantes dont la base vous a déjà été présentée plus haut. Une variante se base sur la logique floue. Au lieu de postuler qu’un élément appartient à un groupe et un seul, on attribue à chaque couple (élément, groupe) un pourcentage d’appartenance. De la même manière que personne n’est grand ou petit dans l’absolu, l’élément Tony Parker, par exemple, aura un degré d’appartenance au groupe « grand » élevé.

Classification :

Mahout propose des techniques assez variées, basées sur :

• Les réseaux de neurones, qui ont l’avantage de donner de très bons résultats. Inconvénient : on ne peut absolument pas comprendre les règles de classification en l’état. On doit faire confiance à l’outil. Plus exactement, c’est encore un domaine de recherche, mais il existe des algorithmes (bien au-delà de ce qu’on peut expliquer dans cet article) pour extraire des règles depuis un réseau de neurones.
• Les régressions : souvent efficace, simple. Un classique.
• Les algorithmes basés sur les probabilités : Bayes et Markov, donc. La formule de Bayes a trait aux probabilités du type : « A sachant que B s’est réalisé ». Par exemple, la probabilité que vous achetiez une poussette si vous avez un enfant, etc. Les gros volumes de données sont alors très utiles pour mesurer les probabilités conditionnelles, puisque sur un grand nombre d’éléments, une probabilité est un ratio : probabilité qu’un client achète une poussette = nombre de clients ayant acheté une poussette divisé par le nombre de clients. Les modèles de Markov poussent plus loin encore l’idée de probabilité conditionnelle. On peut prédire le comportement statistique moyen d’un client en fonction des actions passées au fil du temps. C’est la base théorique des modèles d’évaluation des ratings des clients en finance (Moody, Fitch, Standard and Poors).

Mahout et le Map-Reduce

Au tout début fut Lucene, d’Apache. En 2008, le projet Mahout vit le jour pour isoler les fonctionnalités d’exploration de données du projet Lucene. Une autre propriété forte du projet était de parfaitement s’interfacer avec Hadoop, d’où l’existence de beaucoup d’algorithmes basés sur Map-Reduce. Mais, revirement de situation en avril 2014 : Map-Reduce ne sera plus utilisé sur les nouvelles fonctionnalités, au profit de SPARK, plus rapide et plus intuitif. Le site officiel annonce également l’utilisation d’un DSL basé sur SCALA.

Conclusion

Nous aimerions faire passer deux idées dans cet article :

1. A présent que les solutions de stockage permettent de sauver de gros volumes, il nous parait évident qu’on peut l’utiliser, en extraire de la connaissance business. Ce qui, mécaniquement, met en avant l’exploration de données dont c’est exactement le but.
2. Le data-mining n’est pas seulement l’affaire de data-scientists. Mahout s’inscrit dans cette lignée : un outil dédié, couplé à Hadoop, pour les principales fonctionnalités dont la communauté a besoin : recommandations, classification, regroupement.

Et si vous voulez en savoir plus:
SPARK et Mahout: pourquoi:
Rien de mieux que le site officiel
Et un livre: Mahout in action, Sean Owen, Robin Anil, Ted Dunning, Ellen Friedman chez Manning