Recommandations en ligne : comment ça marche ?

Recommandations en ligne : comment ça marche ?

Les recommandations en ligne ont un petit côté magique. Ne vous êtes-vous jamais demandé comment Amazon pouvait vous proposer un livre aussi proche de vos centres d’intérêts ou comment Facebook arrivait à vous suggérer des amis que vous n’aviez plus vus depuis des lustres ? Les mécaniques sous-jacentes ne sont finalement pas si complexes, au moins dans leurs principes. L’objectif de ce billet est de les démystifier en en détaillant le fonctionnement général.

Les recommandations en ligne ont un petit côté magique. Ne vous êtes-vous jamais demandé comment Amazon pouvait vous proposer un livre aussi proche de vos centres d’intérêts ou comment Facebook arrivait à vous suggérer  des amis que vous n’aviez plus vus depuis des lustres ? Les mécaniques sous-jacentes ne sont finalement pas si complexes, au moins dans leurs principes. L’objectif de ce billet est de les démystifier en détaillant le fonctionnement général.

Encore et toujours des recommandations

Nous sommes constamment exposés sur le web à des recommandations en ligne : sur Amazon ou la FNAC, on vous propose des produits qui « peuvent vous intéresser ». Sur Facebook ou Linkedin, on vous suggère des amis que vous « pourriez connaître ». Sur Trip Advisor, on vous liste des restaurants ou des hôtels que vous « pourriez aimer ».  Google news vous propose des « articles similaires »…

Dans le domaine du e-commerce, nous avons mesuré que ces recommandations contribuent à augmenter les ventes de 5 à 15 % et que les taux de clics croissent d’un facteur dix, comparés à des recommandations non personnalisées. Ces recommandations ne sont donc pas simplement un phénomène de mode mais bien un réel levier pour augmenter la stickiness du site, la taille du panier,  et la fréquence de visite. Qui plus, est avec le développement de l’omni-canal, ces techniques de recommandations peuvent également améliorer la performance des magasins traditionnels en détectant des combinaisons de produits ou des profils affinitaires afin d’adapter l’offre produit, le merchandising ou les ventes dans des contextes d’expérience client multicanal.

Calquer sur les mécaniques de recommandations de la vraie vie

Le principe de ces recommandations en ligne est calqué sur 2 cheminements commerciaux classiques qu’utilisent les vendeurs pour conseiller leurs clients dans les processus de vente simple.

  1. Centré sur les personnes (user-based) : dans ce cas, l’hypothèse retenue est que 2 personnes proches auront probablement des goûts similaires ou, plus précisément, que s’ils ont de nombreux intérêts en commun, alors ils peuvent être intéressés par les intérêts qu’ils n’ont pas en commun. La question posée se résume à : « Quels clients ressemblent à ce client et qu’aiment-ils ? ».
  2. Centré sur les objets (item-based) : les recommandations centrées sur les objets (des produits, des pages, des amis…) s’appuient sur les similarités entre objets. On part donc des objets et on recherche les objets semblables du point de vue des préférences des clients pour répondre à la question « Quels sont les produits similaires à ceux qu’aime ce client ? ».

En général, pour des considérations de temps de traitement, s’il y a beaucoup plus de personnes que d’objets, on préférera se centrer sur les objets et vice-versa. Dans les deux cas, le principe reste semblable et avant tout basé sur la recherche de similarité.

Principe général de fonctionnement

Les algorithmes de recommandations prennent en entrée des « préférences ». Prosaïquement, ces préférences sont souvent représentées sous la forme : utilisateur, objet, poids. Imaginons que Jean Dupont, utilisateur numéro 5, ait noté le livre « Les fables de Lafontaine », ISBN 1010, quatre étoiles, le fichier des préférences contiendrait alors une ligne ayant la forme suivante : 5, 1010, 4. A ce stade, notons que les objets peuvent être des produits, des pages vues, des personnes … et que les poids peuvent être des notes, ou simplement un top selon que la page ou le produit a été vu, cliqué…

En sortie, ces algorithmes produisent pour chaque client considéré, une liste de recommandations (des objets) avec un poids pour chacune d’elle, permettant ainsi un tri par ordre décroissant d’intérêt avant qu’elles ne soient présentées au client. Ainsi 5, 1012,2 signifiera que le client 5 devrait avoir un intérêt de niveau 2 pour l’objet 1012.

En termes de traitements sur ces préférences en entrée, la logique générale de recommandations suit 3 étapes :

    1. Calcul des utilisateurs voisins : il s’agit de déterminer un ensemble d’utilisateurs « proches » afin d’éviter que le périmètre de calcul des similarités entre objets ne soit trop énorme.

Pour chaque utilisateur V
Calculer la similarité SU entre U et V

    1. Calcul des similarités entre objets : pour le sous-ensemble des utilisateurs « voisins », il s’agit de calculer une similarité entre objets.

Pour chaque objet O pour lequel l’utilisateur U n’a pas de préférence
Pour chaque utilisateur « voisin de U » V qui a une préférence pour 0
Calculer la similarité SO entre U et V
Incrémenter la préférence de V pour O, pondéré par SO à la moyenne des préférences

  1. Recommandations : la recommandation consiste simplement pour un utilisateur donné à trier par ordre décroissant les objets dans les préférences en sortie de l’étape précédente.

Comme on le voit, le cœur du sujet est le calcul d’une similarité. Il existe de nombreuses méthodes pour calculer des similarités, distances euclidiennes, Pearson, Tanimoto … Le voisinage peut également s’exprimer de différentes manières : en distance absolue, en proportion … Qui plus est, ces méthodes peuvent ou non s’appuyer sur des pondérations des différents « objets ». Elles ont toutes des avantages et des inconvénients tant en termes d’efficacité que de temps de traitement. L’expérience montre que le choix des méthodes se fera de manière empirique à partir d’une mesure de l’efficacité des différentes méthodes et paramètres.

Note : voici quelques papiers pour approfondir les métriques de similarité :

http://nebc.nerc.ac.uk/courses/GeneSpring/GS_Mar2006/Measures%20of%20Similarity.pdf
http://mines.humanoriented.com/classes/2010/fall/csci568/portfolio_exports/sphilip/similarity.html

Un exemple simpliste

Exprimer des calculs par des phrases n’est jamais simple. Prenons un exemple concret ultra-simplifié avec 5 utilisateurs et 7 objets pour rechercher des recommandations centrées sur les objets. Imaginons que les préférences soient les suivantes :

Utilisateur Objet
Alex Objet1
Alex Objet2
Alex Objet3
Enzo Objet1
Enzo Objet2
Enzo Objet3
Enzo Objet4
Lisa Objet1
lisa Objet4
Lisa Objet5
Lisa Objet7
Nicolas Objet1
Nicolas Objet3
Nicolas Objet4
Nicolas Objet6
Natacha Objet1
Natacha Objet2
Natacha Objet3
Natacha Objet4
Natacha Objet5
Natacha Objet6

On va calculer les cooccurrences des différents objets, c’est-à-dire le nombre de fois où 2 objets apparaissent pour un même utilisateur, afin d’obtenir une matrice objet*objet symétrique :

Objet1 Objet2 Objet3 Objet4 Objet5 Objet6 Objet7
Objet1 5 3 4 4 2 1 1
Objet2 3 3 3 2 1 1 0
Objet3 4 3 4 3 1 2 0
Objet4 4 2 3 4 2 2 1
Objet5 2 1 1 2 2 1 1
Objet6 1 1 2 2 1 2 0
Objet7 1 0 0 1 1 0 1

On va ensuite, pour chaque utilisateur, calculer le produit de cette matrice par le vecteur de l’utilisateur. Par exemple, pour Alex, on obtiendra le résultat suivant :

Objet1 Objet2 Objet3 Objet4 Objet5 Objet6 Objet7 Alex Préférence
Objet1 5 3 4 4 2 1 1 5,0 44,0
Objet2 3 3 3 2 1 1 0 3,0 31,5
Objet3 4 3 4 3 1 2 0 2,5 39,0
Objet4 4 2 3 4 2 2 1 33,5
Objet5 2 1 1 2 2 1 1 15,5
Objet6 1 1 2 2 1 2 0 13,0
Objet7 1 0 0 1 1 0 1 5,0

 

Rappel : un produit d’une matrice avec un vecteur consiste à sur une ligne donnée de la matrice à additionner les produits des colonnes j de la matrice par les lignes j du vecteur utilisateur.

Considérant les préférences, on sélectionnera parmi les objets non notés par Alex, ceux qui ont la plus grande préférence, soit dans ce cas l’objet4.

Mesure de l’efficacité d’une recommandation

Comme on l’a vu, il existe de nombreuses méthodes et de nombreux paramètres tant pour analyser les similarités que pour déterminer les voisins et donc les recommandations. La validation manuelle est une vue de l’esprit compte tenu de la combinatoire et de l’aspect fortement évolutif des objets et des utilisateurs.

Il est donc essentiel de disposer de mesures de l’efficacité des recommandations afin de pouvoir comparer différents jeux de méthodes et paramètres et d’optimiser ainsi, empiriquement, les résultats. Pour cela, la première étape consiste, en amont du processus de recommandation, à isoler une partie des utilisateurs pour l’apprentissage et en garder une partie pour tester les résultats. Une fois l’apprentissage terminé, les recommandations obtenues sur les utilisateurs tests sont comparées aux préférences réelles de ces utilisateurs par exemple en calculant la moyenne des différences en valeur absolue.

Lorsque l’objectif est simplement de sortir une liste triée de recommandations, l’évaluation de la note (le poids de la préférence) n’est pas tant le problème que la pertinence de la recommandation. Pour cela, il est possible de calculer deux indicateurs en comparant les résultats et la réalité : 1/ la précision qui est la proportion des recommandations qui sont dans les préférences des utilisateurs test et 2/ le recall (le rappel en français) qui est la proportion des préférences des utilisateurs test qui sont recommandées.  Pour ceux qui veulent en savoir plus sur ces indicateurs, un article intéressant sur le sujet.

L’explosion combinatoire

Au minimum, les algorithmes vont croiser tous les utilisateurs voisins avec tous les objets d’une manière ou d’une autre ; au maximum, certains calculs nécessiteront même plusieurs itérations ! Intuitivement, on se retrouve donc à la fois avec des matrices rapidement gigantesques et des quantités d’itérations à donner le vertige.

La taille des matrices est un premier problème. La mémoire adressable physiquement sur un système 32 bits (le cas général pour un pc) est de l’ordre de 4 Go tandis qu’elle atteint 192 Go sur un système 64 bits (le cas général pour un serveur). Au-delà de ces valeurs, il est nécessaire soit de découper le sujet en tranche de telle sorte que ces seuils ne soient pas dépassés, soit de basculer sur une gestion sur disque, avec une base de données par exemple, auquel cas les temps de traitement deviennent relativement prohibitifs.

La quantité d’itération est également un écueil. Si l’on considère qu’une itération coûte par exemple deux centièmes de secondes, il faudra une seconde pour traiter cinquante itération et … 24 heures pour en traiter 4.3 millions. Pour mémoire, les acteurs de la grande distribution française travaillent sur des centaines de milliers de références produits et des millions de clients. Pour 5 millions de clients et 300.000 références, un croisement exhaustif des clients et des produits à raison de 2 centièmes de seconde par cellule durerait un millier d’années ; bien entendu, si on restreint le nombre de voisins ou on élimine les produits très peu consommés, on doit pouvoir faire mieux mais ça restera vertigineux. Je vous laisse faire le calcul si les objets représentent des mots de la langue française et que l’objectif est de trouver des similarités entre documents pour pousser du contenu éditorial par exemple.

L’apport du big data

C’est typiquement sur ce genre de problématiques de très haute volumétrie qu’interviennent les technologies usuellement regroupées sous le terme Big Data. Ces technologies, issues des travaux de Google, Facebook ou Yahoo pour traiter d’énormes volumes, partent du constat suivant : le coût d’une somme de petits serveurs sera toujours moindre que celui d’un gros serveur. Il s’agit donc de trouver des solutions pour distribuer et paralléliser le stockage et le traitement de très gros volumes afin de réduire à la fois les coûts et les temps de calcul.

Pour le stockage, HDFS (pour Hadoop Distributed File System) est la solution la plus fréquente. Un nœud maître gère un index qui distribue les tâches de stockage des données, sous la forme « id, valeur », entre différents nœuds esclaves et tient à jour un index qui localise les données ainsi distribuées.

Pour le traitement, Hadoop intègre Map Reduce dont la vocation est de découper les traitements de telle sorte qu’ils puissent être distribués entre différents nœuds, afin de les paralléliser et donc de les accélérer. En gros, une première étape de Map découpe le problème en sous-problèmes simples de transformation d’entrées sous forme (id, valeur) en sortie de même forme.  Ces sous-problèmes sont ensuite sous-traités aux différents nœuds puis les résultats remontent au nœud supérieur et passent par l’étape de Reduce qui effectue une synthèse pour chaque id, par exemple une somme, avant de restituer le résultat final du traitement.

Ainsi, au prix d’un peu d’over Head, les recommandations qui auraient pris 100 jours pour être calculées sur un serveur pourront être entièrement recalculées en une journée sur un cluster de 100 nœuds, ouvrant ainsi des possibilités inimaginables sans parallélisation.

Les sciences connexes

Les moteurs de recommandations, parfois dénommés collaborative filtering, s’inscrivent dans le domaine plus général des systèmes d’auto-apprentissages ou de machine-learning pour les anglo-saxons, eux-mêmes intégrés au champ de l’intelligence artificielle en général. On y retrouver également d’autres techniques dont les résultats sont également assez impressionnants : les algorithmes génétiques pour l’optimisation sous contraintes, les algorithmes de classification ou de segmentations ainsi que la détection de formes récurrentes. Combinés notamment avec des techniques de traitement du langage naturel, ils constituent les bases pour le fonctionnement des outils de recherche et de classification tels que Google.

Pour en savoir plus, Coursera propose des modules de formation, ou si vous n’avez pas des semaines à y consacrer, consultez Wikipédia sur le sujet.

Quelques exemples d’outils

Le sujet captive les chercheurs et fait l’objet de nombreuses publications et open-source. Quelques pistes pour démarrer :

http://mymediaproject.codeplex.com/

http://www.duineframework.org/

http://www.certona.com/

http://mahout.apache.org/

http://www.attivio.com/products/add-on-modules/recommendation-engine.html

Pour vous entraîner, vous pouvez aussi récupérer des jeux de données réels, du plus léger au plus volumineux, que ce soient des notations de films, des liens Wikipédia ou des fréquences de mots dans des ouvrages : http://www.grouplens.org/node/12

Autres applications

En termes d’applications, on pense en premier lieu à la recommandation de produits sur des sites commerçants. Mais de nombreuses autres applications sont possibles ou déjà mis en œuvre. A l’instar de Facebook qui a généralisé le notion de « like » pour aboutir à un graphe de relations de toutes sortes entre des utilisateurs ou des objets, on peut ouvrir de même les moteurs de recommandations pour traiter par exemple des goûts musicaux, des pages intéressantes, des sondages politiques, des sites de rencontres,…Fondamentalement, les techniques employées savent reconnaître des similarités dans des matrices n*m. A vous de déterminer le sens de ces dimensions pour trouver de nouveaux champs d’applications au-delà de la classique recommandation de produits.

Ecrire un commentaire

* Name, Email, Comment are Required