[DevoxxFR 2014] Attaquez le Mahout de face pour exploiter vos Téraoctets d’historique !

13 mai 2014

double_xx_texte

Lors de Devoxx France 2014, Sidi Mohammed RAMDANI (@smramdani) de la société Palo IT a réalisé une présentation visant à vulgariser l’utilisation de la librairie open-source Java Apache Mahout ainsi que les concepts se cachant derrière les termes “Machine Learning”, “Classification”, “Collaborative Filtering”, “Clustering”, …

En effet, à l’heure du Big Data, les sociétés collectent de plus en plus d’informations nous concernant et la mise en place d’outils de recommandation basés sur des algorithmes de Machine Learning constituent une utilisation plus que naturelle de ces données.

Le but de cette présentation n’étant pas de nous abreuver de formules mathématiques, Sidi Mohammed s’est basé sur un exemple de société de vente de vidéos en ligne qui déciderait de booster ses ventes en mettant en avant ses produits.

La solution envisagée : s’appuyer sur les historiques de vente et ainsi exploiter les données collectées depuis la mise en ligne du service.

Quelle technique ?

Le Machine Learning (ML) est un sous-ensemble de l’intelligence artificielle dont le but est d’étudier des systèmes capables d’adapter leur comportement grâce à un processus d’apprentissage à partir des données reçues, les historiques de ventes ou les notations des produits dans le cas de notre exemple.

L’idée est de mettre en place des algorithmes de ML et plus particulièrement de filtrage collaboratif (Collaborative Filtering (CF)) afin de pouvoir utiliser les données des clients du site pour recommander à un client spécifique des produits en adéquation avec ce qui est susceptible de l’intéresser.

collaborative_filteringIdéalement, ces recommandations personnalisées peuvent être générées en temps réel.

Il est à noter qu’une fois recommandé, le client va lui-même participer au processus d’enrichissement des données en fournissant ses propres évaluations ou en réalisant des achats via le site.

Qui recommande ?

Aujourd’hui sur le web, de nombreux sites utilisent des algorithmes de recommandation pour enrichir l’expérience utilisateur avec des fonctionnalités “intelligentes” :

  • sites e-commerce : amazon, e-bay, fnac …
  • réseaux sociaux : facebook, twitter, viadeo, linkedIn, foursquare …
  • plateformes multimédia : deezer, imdb, netflix, spotify, flickr …

Nul doute que vous avez déjà été confronté à ce genre de fonctionnalités. Les recommandations qui vous sont faites sont généralement en adéquation avec vos attentes.

Ainsi une étude a révélé que près de 30% du CA total d’Amazon était généré grâce à son système de recommandation, les utilisateurs naviguant sur le site au gré des recommandations basées sur les achats réalisés précédemment par des acheteurs intéressés par des produits similaires.

amazon

Les moteurs de recherche s’enrichissent eux aussi de fonctionnalités de Machine Learning pour vous proposer des résultats de recherche de plus en plus pertinents et personnalisés.

Toutes ces sociétés contribuent souvent activement aux développements des outils de Machine Learning en reversant leurs propres algorithmes à la communauté open-source.

Une anecdote ?

Pour mettre en évidence l’importance accordée au Machine Learning par les sociétés du net, Sidi Mohammed nous a rappelé l’initiative de Netflix qui en 2006 a mis en place un concours de type crowdsourcing, le Netflix Prize.

Le but de ce concours était de développer un algorithme de recommandation capable de surclasser le propre algorithme de Netflix visant à prédire les évaluations des utilisateurs du site à partir d’un historique de notations des différents films.

Ce concours fut un véritable succès avec la participation de nombreuses équipes à travers le monde. Il a pris fin en 2009, l’équipe gagnante empochant la somme de 1M de $ … et fournissant ainsi un nouvel algorithme à Netflix.

Les algorithmes développés lors de ce concours sont aujourd’hui encore d’actualité et la plupart d’entre eux sont disponibles dans des librairies open-source telles que Apache Mahout.

Quels outils ?

Différents types d’outils de Machine Learning peuvent être utilisés :

  • outils mathématiques : Matlab, Mathematica, Maple, …
  • logiciels d’analyses statistiques : Scilab, SPSS, Stata, …
  • librairies open-source :
    • Python : Pandas, StatsModels, scikit-learn…
    • Java : Weka, Apache Mahout, …

Si pour quelques Ko ou Mo de données, de simples outils mathématiques permettent aisément de réaliser du prototypage, il en va tout autrement avec des Go ou des Tos de données.

Ainsi, avec l’avènement du Big Data, les systèmes de recommandation doivent s’appuyer sur des systèmes distribués, tout en utilisant des algorithmes de Machine Learning eux-mêmes distribués.

Pourquoi choisir Mahout ?

Pour Sidi Mohammed, divers arguments plaident en faveur de l’utilisation d’Apache Mahout pour répondre à notre besoin de mise en place d’un moteur de recommandation pour notre site :

  • Librairie complète de Machine Learning qui couvre les principaux algorithmes, notamment les 3C :
    • Collaborative Filtering : mahoutalgorithmes permettant de  recommander des items à un utilisateur en identifiant des similarités
    • Clustering : algorithmes permettant de découvrir des groupements parmi un ensemble de données (ex : profilage d’utilisateurs, analyse de tendances, …)
    • Classification : algorithmes permettant de classifier automatiquement des documents à partir de documents déjà classifiés (ex : association automatique de tags à des documents, filtrage des mails de type spams, …)
  • Algorithmes bien testés et supportés
  • Open-source (licence Apache)
  • S’appuie sur Hadoop MapReduce, ce qui répond à des problématiques de scalabilité (stockage répartis redondants) et de parallélisme (calculs distribués de type MapReduce) pour être utilisé avec de gros volumes de données
  • Communauté active et dynamique qui assure une croissance rapide
  • Java
  • Librairie extensible avec la possibilité d’ajout de nouvelles collections d’algorithmes

Aujourd’hui, Mahout est en version 0.9 (stable) et le projet s’oriente vers la mise à en place d’un DSL Scala pour l’écriture des algorithmes ainsi que vers l’utilisation d’Apache Spark offrant des performances de calculs bien plus importantes que celles d’Hadoop MapReduce, ce qui devrait être très prometteur pour l’avenir de Mahout.

Mise en œuvre du filtrage collaboratif (CF) avec Mahout

Rentrons maintenant dans le vif du sujet en utilisant Apache Mahout pour mettre en place notre moteur de recommandation.

Le DataModel de Mahout s’appuie sur différentes données :

  • Les Users modélisant les utilisateurs ayant consulté ou acheté via le site
  • Les Items qui correspondent aux différents produits du catalogue
  • Les Ratings qui peuvent être des notations, des visualisations de page produit, des achats concrets, …

Ces données peuvent être stockées dans des bases de type relationnel ou NoSQL et de volumétrie variable.

mahout_cf_userPour réaliser ses recommandations, Apache Mahout s’appuie ensuite sur :

  • des algorithmes de similarité pour déterminer les utilisateurs les plus proches en utilisant par exemple la distance euclidienne, la corrélation de Pearson, la similarité cosinus, …
  • des algorithmes de voisinage pour déterminer un ensemble d’utilisateurs proches selon la règle de similarité choisie. On distingue des algorithmes de type Nearest (les X utilisateurs les plus similaires) ou Threshold (tous les utilisateurs dépassant un certain seuil de similarité)

Outre le filtrage collaboratif basé sur les utilisateurs (User Recommender) vu ci-dessus, il est également possible de mettre en place des moteurs de recommandation se basant uniquement sur les items (Item Recommender) et les similarités entre ceux-ci.

mahout_cf_itemCeci permet par exemple de proposer à un utilisateur des articles similaires à ceux qu’il a déjà consultés ou achetés en analysant son profil.

Sidi Mohammed insiste ici sur le fait que pour obtenir le moteur de recommandation le plus efficace, il est primordiale de tester ces différents algorithmes et ainsi de rechercher celui qui sera le mieux adapté à notre modèle et à nos données. Il est même courant de combiner ces différents algorithmes pour assembler les différentes briques d’un moteur de recommandation optimal.

Si les concepts mathématiques se cachant derrière ces algorithmes semblent plutôt compliqués, leur mise en œuvre avec Apache Mahout s’avère assez simple comme le prouve le code que Sidi Mohammed nous présente ensuite dans le cadre de son exemple de mise en place de moteur de recommandation pour son site de vente de vidéos.

En effet, en seulement quelques lignes de codes, il est possible de spécifier le DataModel à utiliser (ici un fichier de données brutes), puis de définir la similarité (UserSimilarity) à utiliser et enfin le voisinage (UserNeighborhood) associé avant de créer le UserRecommender souhaité :

DataModel model = new FileDataModel(new File("user-item-rating-dataset.dat"));

double threshold = 0.1d;
UserSimilarity similarity = new PearsonCorrelationSimilarity(model);
UserNeighborhood neighborhood = new ThresholdUserNeighborhood(threshold, similarity, model);

Recommender userRecommender = new GenericUserBasedRecommender(model, neighborhood, similarity);

Idem pour un ItemRecommender en utilisant cette fois-ci simplement un ItemSimilarity :

DataModel model = new FileDataModel(new File("user-item-rating-dataset.dat"));

ItemSimilarity similarity = new PearsonCorrelationSimilarity(model);

Recommender itemRecommender = new GenericItemBasedRecommender(model, similarity);

Une fois le Recommender prêt, il suffit de l’interroger pour qu’il nous fournisse une liste de recommandations pour un utilisateur (dans notre exemple, la valeur de la recommandation  est une note de 1 à 5 conformément aux ratings fournis en entrée) :

int userId = 1;
int nbRecommendations = 5;

List<RecommendedItem> recommendedItems = userRecommender.recommend(userId, nbRecommendations);
for (RecommendedItem recommendedItem : recommendedItems) {
    System.out.println("Item: " + recommendedItem.getItemID());
    System.out.println(" (Value: " + recommendedItem.getValue() + "/5)");
}

Dans le cas d’un ItemRecommender, récupérer une liste d’articles similaires à un article donné est tout aussi aisé :

int itemId = 3;
int nbRecommendations = 5;

List<RecommendedItem> similarItems = itemRecommender.mostSimilarItems(itemId, nbRecommendations);

Sur les différents exemples utilisés lors de la présentation, les résultats semblent plutôt cohérents, mais bien sur, comme le souligne Sidi Mohammed, plus l’on veut des réponses fiables, plus il nous faut de données en entrée.

Même l’ItemRecommender, où le processus de calcul est plus léger car les algorithmes moins complexes, donnent de bons résultats.

Niveau performance, Sidi Mohammed nous assure que le principal point de contention reste le chargement des données et non le calcul des recommandations lui-même. Malheureusement, nous n’avons pas eu l’occasion de valider cela lors de la présentation, Sidi Mohammed n’ayant pas opté pour du live-coding. Dommage …

Evaluez-vous !

Dernier aspect de la présentation, l’évaluation de la précision et de la pertinence des recommandations.

Une nouvelle fois Sidi Mohammed insiste sur le caractère itératif du processus de mise en place d’un moteur de recommandation, de la “data-science en mode agile” comme il le dit lui-même.

amelioration_continuePour évaluer un moteur de recommandation, il est possible de s’appuyer directement sur les données disponibles (historique des notations par exemple) en utilisant 90% de celles-ci pour le calcul de recommandation pour ensuite tester l’algorithme avec les 10% restants. Il s’agit de la règle des 90% apprentissage / 10% test.

En testant différents algorithmes avec le même jeu de données, il est donc possible d’établir des scores en calculant les différences entre les prédictions et les notes réelles des 10% (taux d’erreur).

Mahout permet également d’évaluer directement les Recommenders mis en place, avec par exemple l’utilisation de la classe AverageAbsoluteDifferenceRecommenderEvaluator comme dans l’exemple ci-dessous où on s’appuie sur la règle des 90/10 pour partitionner les données disponibles (trainingPercentage = 0.9) :

DataModel model = new FileDataModel(new File("user-item-rating-dataset.dat"));

RecommenderEvaluator evaluator = new AverageAbsoluteDifferenceRecommenderEvaluator();
RecommenderBuilder builder = new MyRecommenderBuilder();

double trainingPercentage = 0.9d;
double evaluationPercentage = 1.0d;
double score = evaluator.evaluate(builder, null, model, trainingPercentage, evaluationPercentage);

Différents ratios sont également utilisés pour rechercher l’algorithme optimal :

  • la précision :     precision
  • le rappel ou  “recall” : rappel

Un algorithme parfait fournira des recommandations dont la précision et le rappel sont égaux à 1 en trouvant la totalité des items pertinents (rappel = 1) et ne faisant aucune erreur (précision = 1).

Mais cela n’est que pure théorie car en pratique, les algorithmes sont plus ou moins précis et plus ou moins pertinents :

  • Par exemple, en mettant en place un algorithme très précis avec une précision de l’ordre de 99%, celui-ci pourrait s’avérer peu performant en ne trouvant que très peu de réponses possibles (10% par exemple avec un rappel de 0.10). On écarte ainsi à tort des faux négatifs susceptibles d’intéresser l’utilisateur.
  • A contrario, en favorisant un rappel élevé permettant d’obtenir par exemple 99% de recommandations pertinentes, on risque de se heurter à une précision trop faible de l’ordre de 10% et ainsi d’obtenir de nombreuses recommandations erronées (faux positifs) en plus de celles pertinentes, rendant les résultats totalement inexploitables.

Conclusion

En conclusion, Sidi Mohammed nous rappelle qu’aucun algorithme n’est performant dans 100% des cas et qu’il faut par conséquent envisager de les combiner, par exemple en utilisant des algorithmes de catégorisation des utilisateurs (profilage, géolocalisation, …) en amont du calcul des similarités.

Il est également envisageable de rajouter des critères métiers pour favoriser différents items par rapport à d’autres, par exemple en privilégiant la mise en avant de produits récents, …

Un moteur de recommandation est donc un ensemble complexe articulé autour de différentes briques en perpétuelle évolution pour garantir une efficacité maximale.

Pour ma part, j’ai trouvé cette présentation très intéressante car elle permettait de voir en quoi le Machine Learning pouvait apporter des fonctionnalités à forte valeur ajoutée telle que les moteurs de recommandation qui sont aujourd’hui monnaie courante sur de nombreux sites.

Dans ce domaine, nul doute qu’Apache Mahout, de par son accessibilité et la richesse de ses algorithmes, a un bel avenir devant lui et qui sait, peut-être qu’un jour vous aussi vous aurez l’occasion de l’utiliser et non plus seulement en tant qu’internaute mais aussi en tant que développeur …

Stay tuned: @ApacheMahout !

Jérôme Valloire (2 Posts)


Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *

Vous pouvez utiliser ces balises et attributs HTML : <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>