Dossier de Mathieu dans l’épisode #83.
Il existe des centaines d’algorithmes qui ont été utilisés pour l’implémentation de systèmes de recommandation. La plupart relève de concepts mathématiques avancés. Dans ce dossier, on va tenter d’analyser différentes approches et stratégies utilisées lors de la mise en place d’un système de recommandation.
Wikipedia définit un système de recommandation comme une forme spécifique de filtrage de l’information visant à présenter les éléments d’information (films, musique, livres, news, images, pages Web, etc) qui sont susceptibles d’intéresser l’utilisateur.
Dit autrement, un système de recommandation cherche à prédire la valorisation ou préférence qu’un utilisateur attribuerait à un objet (livre, musique, film…) ou à un élément social (personne, groupe, communauté) qu’il n’avait pas encore considéré.
Un système de recommandation requiert généralement 3 étapes:
- La première consiste à recueillir de l’information sur l’utilisateur.
- La deuxième consiste à bâtir une matrice ou un modèle utilisateur contenant l’information recueillie.
- La troisième consiste à extraire à partir de cette matrice une liste de recommandations.
Collecte d’Information
Pour être pertinent, un système de recommandation doit pouvoir faire des prédictions sur les intérêts des utilisateurs. Il faut donc pouvoir collecter un certain nombre de données sur ceux-ci afin d’être capable de construire un profil pour chaque utilisateur.
Une distinction peut être faite entre 2 formes de collecte de données:
- Collecte de données explicite – Filtrage actif: repose sur le fait que l’utilisateur indique explicitement au système ses intérêts.
- Exemple: demander à un utilisateur de commenter, taguer/étiqueter, noter, liker ou encore ajouter comme favoris des contenus (objets, articles…) qui l’intéressent. On utilise souvent une échelle de ratings allant de 1 étoile (je n’aime pas du tout) à 5 étoiles (j’aime beaucoup) qui sont ensuite transformées en valeurs numériques afin de pouvoir être utilisées par les algorithmes de recommandation.
- Avantage: capacité à reconstruire l’historique d’un individu et capacité à éviter d’agréger une information qui ne correspond pas à cet unique utilisateur (plusieurs personnes sur un même poste).
- Inconvénient: les informations recueillies peuvent contenir un biais dit de déclaration.
- Collecte de données implicite – Filtrage passif: repose sur une observation et une analyse des comportements de l’utilisateur effectuées de façon implicite dans l’application qui embarque le système de recommandation, le tout se fait en “arrière-plan” (en gros sans rien demander à l’utilisateur).
- Exemples:
- Obtenir la liste des éléments que l’utilisateur a écoutés, regardés ou achetés en ligne.
- Analyser la fréquence de consultation d’un contenu par un utilisateur, le temps passé sur une page.
- Monitorer le comportement en ligne de l’utilisateur.
- Analyser son réseau social.
- Avantage: Aucune information n’est demandée aux utilisateurs, toutes les informations sont collectées automatiquement. Les données récupérées sont a priori justes et ne contiennent pas de biais de déclaration.
- Inconvénient: Les données récupérées sont plus difficilement attribuables à un utilisateur et peuvent donc contenir des biais d’attribution (utilisation commune d’un même compte par plusieurs utilisateurs). Un utilisateur peut ne pas aimer certains livres qu’il a acheté, ou il peut l’avoir acheté pour quelqu’un d’autre.
- Exemples:
Modèle Utilisateur
Le modèle utilisateur se présente généralement sous forme de matrice. On peut se le représenter comme un tableau qui contient des données recueillies sur l’utilisateur associées aux produits disponibles sur le site web.
Un autre point important est comment le temps influence le profil de l’utilisateur. Les intérêts des utilisateurs, généralement, évoluent au cours du temps. Les données du modèle utilisateurs devraient donc constamment être réajustées pour rester conformes aux nouveaux centre d’intérêts de l’utilisateur.
Liste de recommandations
Pour extraire une liste de suggestions à partir d’un modèle utilisateur, les algorithmes utilisent la notion de mesure de similarité entre objets ou personnes décrits par le modèle utilisateur. La similarité a pour but de donner une valeur ou un nombre (au sens mathématique du terme) à la ressemblance entre 2 choses. Plus la ressemblance est forte, plus la valeur de la similarité sera grande. A l’inverse, plus la ressemblance est faible, et plus la valeur de la similarité sera petite. On verra plus tard dans le dossier quelques exemples.
Types de système de recommandation
On a l’habitude de présenter 4 approches possibles pour un système de recommandation:
- Recommandation Personnalisée
- Recommandation Objet (Content-Based filtering CB)
- Recommandation Sociale (Collaborative Filtering CF – Context Aware)
- Recommandation Hybride
Recommandation Personnalisée
Il s’agit de recommander des objets sur la base du comportement passé de l’utilisateur.
Exemples:
- Des produits achetés ou sélectionnés sur un site de e-commerce, ainsi qu’un certain nombre d’actions ou décisions effectuées par l’utilisateur qui permettent de prédire de nouveaux produits susceptibles de l’intéresser.
- Les annonces publicitaires (par ex. Adsense de Google) sont considérées comme des systèmes de recommandation personnalisée qui se basent sur le comportement passé de l’utilisateur (navigation, clics, historique de recherche…)
Recommandation Objet
Il s’agit de recommander des objets (ou contenus) en se basant sur les qualités et propriétés intrinsèques de l’objet lui-même et en les corrélant avec les préférences et intérêts de l’utilisateur. Ce type de système va donc extraire un certain nombre de caractéristiques et attributs propres à un contenu, afin de pouvoir recommander à l’utilisateur des contenus additionnels possédant des propriétés similaires. Cette méthode crée un profil pour chaque objet ou contenu, c’est-à-dire un ensemble d’attributs/propriétés qui caractérisent l’objet.
Exemples:
- La décision de sélection et recommandation ou non d’un document à un utilisateur peut se baser sur le contenu (les mots présents) dans celui-ci, c’est-à-dire sur une comparaison des thèmes abordés dans le document par rapport aux thèmes qui intéressent l’utilisateur.
- Pour décider la suggestion d’un article (news) ou non, un système de recommandation peut se baser sur les mot-clés principaux de l’article et les comparer avec les mot-clés apparaissant dans d’autres articles que l’utilisateur a évalués positivement dans le passé.
- Dans le cas d’un site de vente de livre en ligne, on va se baser sur les caractéristiques du livre pour effectuer des recommandations, comme par exemple le sujet que traite l’ouvrage, son genre, son auteur, l’éditeur, etc. On pourrait ainsi recommander le livre Harry Potter à un utilisateur, si on sait d’une part que ce livre est un roman fantastique et d’autre part que l’utilisateur aime les romans fantastiques. Un système de recommandation pourra donc accomplir cette tâche seulement s’il a à disposition 2 types d’information: 1) la description des caractéristiques du livre et 2) un profil utilisateur qui décrit les intérêts (passés) de celui-ci en termes de préférence de type de livre. La tâche de recommandation consiste donc à déterminer les livres qui correspondent le mieux aux préférences de l’utilisateur.
Les algorithmes de recommandation objet permettent de développer des modèles afin de trouver des patterns ou motifs semblables entre différentes données. Ils évaluent à quel point un contenu pas encore vu par l’utilisateur est similaire aux contenus que celui-ci a évalués positivement dans le passé. Pour ce faire, on utilise la notion de similarité qui peut être mesurée de plusieurs manières:
- Le système peut tout simplement vérifier si le livre se trouve dans la liste des genres préférés de l’utilisateur. Dans ce cas la similarité sera de 0 ou 1 (binaire/boolean).
- Une autre façon serait de ne pas se baser sur le genre du livre, mais sur les mot-clés qui caractérisent l’ouvrage, et calculer la similarité de chevauchement entre les mots-clés du livre qui va éventuellement être suggéré avec les mots-clés préférés de l’utilisateur. Un des indicateurs de mesure de similarité qu’on utilise dans le cas d’un objet avec des propriétés multi-valeurs (cas des mot-clés) est le coefficient de Dice. Si chaque livre est décrit par un ensemble de mot-clés, le coefficient de Dice permet de mesurer le degré de similarité entre 2 livres à partir de leurs mot-clés.
Dans le cas de documents de texte, on peut également imaginer que le contenu de chaque document soit décrit à partir d’une liste de tous les mots apparaissant dans le document, et décrire chaque document par un vecteur de valeurs binaires/booléennes, où un 1 indiquerait que le mot apparaît dans le document et un 0 indiquerait que le mot n’apparaît pas dans le document. Si le profil utilisateur est décrit par une liste similaire (un 1 indique un intérêt pour un mot-clé), on peut facilement associer et proposer des documents en mesurant le chevauchement entre les mot-clés qui intéressent l’utilisateur et les mots contenus dans le document. Le problème qui surgit avec une telle approche est qu’on assume que chaque mot a la même importance au sein d’un document. Or un mot qui apparaît très souvent ne caractérise pas forcément mieux un document. En plus, un plus large chevauchement entre les préférences de l’utilisateur et un document apparaîtera naturellement plus le document est long. En conséquence, le système de recommandation tendera à proposer des longs documents. Pour résoudre ces problèmes, on applique des techniques qui permettent de réduire le poids des mots qui apparaissent très souvent et d’augmenter le poids de ceux qui apparaissent plus rarement. Pour rendre encore plus compacte la liste des mots présents dans un document, on peut aussi quitter un certain nombre de mots qui sont sans intérêt, comme les prépositions, les articles… En normalisant aussi différentes variantes d’un même mot, par exemple les verbes conjugués sont remplacés par leur infinitif (volait par voler). On peut aussi décider de limiter la liste aux n mots les plus pertinents apparaissant dans les documents. Différents travaux ont montrés que le nombre optimum de mots à prendre en compte se trouve aux alentours de 100. Si trop peu de mots sont sélectionnées (moins de 50), on voit que d’importantes caractéristiques d’un document ne sont pas couvertes. Et si trop de mots sont inclus, certains ont peu d’importance et apportent plus de bruit qu’autre chose, ce qui réduit la qualité de la recommandation. On utilise aussi des base de connaissances lexicales externes pour éliminer des mots non pertinents.
De façon générale, les algorithmes de recommandation objet assignent un poids plus ou moins élevé aux attributs d’un contenu selon l’importance de ceux-ci. Le poids exprime donc l’importance de chaque attribut pour un utilisateur.
Un autre algorithme de recommandation objet couramment utilisé est la méthode de retour de pertinence de Rocchio (Rocchio’s relevance feedback) ou classification de Rocchio. L’idée de cette méthode est de prendre en compte le point de vue des utilisateurs sur les recommandations proposées. Le principe, simple, repose sur le fait que l’utilisateur est le seul à savoir exactement ce qu’il recherche et apprécie, il est donc le plus à même de juger de la pertinence des suggestions retournées par un système de recommandation. Partant de cette idée, les systèmes exploitant le retour de pertinence permettent de récupérer ces « jugements » utilisateurs et les exploitent pour améliorer et affiner les recommandations. Techniquement, l’idée est dans un premier temps de décomposer les contenus évalués par l’utilisateur en 2 groupes (vecteurs, clusters) D+ (contenus évalués positivement et pertinents) et D- (contenus évalués négativement et non pertinents). Par un procédé mathématique on calcule une moyenne (prototype) qui permet de déterminer le centre (centroid) de chacun des 2 groupes (vecteurs) D+ et D-. Lorsqu’un nouvelle requête est effectuée par l’utilisateur, les résultats à recommander sont pondérés en fonction des 2 groupes D+ et D-. C’est-à-dire, on ajoute au résutats de la requête la liste D+ et on soustrait (retire) la liste D-, le tout de façon pondérée. L’effet obtenu est que les résultats retournés se rapprochent à chaque itération un peu plus du centre (centroid) de la liste D+ des contenus évalués positivement par l’utilisateur. Avec cette technique, on voit qu’il est possible d’affiner la requête initiale des utilisateurs au fur et à mesure que ceux-ci fournissent des jugements de pertinence sur des documents consultés. Le système de recommandation est donc doté d’une boucle de retour qui permet au même système de reformuler des recommandations plus pertinente en favorisant ou écartant certains contenus.
Avantages et inconvénients
Avantage: ce type de recommandation objet n’a pas besoin d’une large communauté d’utilisateurs pour pouvoir effectuer des recommandations. Une liste de recommandations peut être générée même s’il n’y a qu’un seul utilisateur.
Inconvénients: certains attributs peuvent être extraits automatiquement d’un contenu, comme par exemple pour un document de texte, on peut relativement facilement déduire certaines propriétés sémantiques automatiquement. On voit aussi qu’en pratique, des caractéristiques et propriétés comme le genre d’un livre ou la liste des acteurs dans un film, sont généralement fournis pas les créateurs du livre ou du film et sont généralement offerts sous forme électronique. Ce qui reste plus problématique, c’est l’acquisition de caractéristiques subjectives et qualitatives… Des propriétés, comme par exemple le style, le design… peuvent difficilement être acquises automatiquement, et devront plutôt être introduites manuellement avec tout ce que ça implique, comme le coût, les éventuelles erreurs…
Recommandation Sociale
Recommander des choses sur la base du comportement passé des utilisateurs similaires, en effectuant une corrélation entre des utilisateurs ayant des préférences et intérêts similaires. On utilise des méthodes qui collectent et analysent des données sur le comportement, les activités, les préférences des utilisateurs et des algorithmes tentent de prédire ce que l’utilisateur aimera en cherchant des utilisateurs qui ont les mêmes comportements que l’utilisateur à qui l’on souhaite faire des recommandations. L’idée sous-jacente est de dire que si un personne A a la même opinion (ou les même goûts) qu’une personne B sur un objet x, alors la personne A a plus de chance d’avoir la même opinion que B sur un autre objet y, plutôt que d’avoir la même opinion que quelqu’un choisi au hasard pour l’objet y. L’idée de base est donc de dire que si des utilisateurs ont partagés des mêmes intérêts dans le passé, il y a de fortes chances qu’ils partagent aussi les mêmes goûts dans le futur.
Les techniques de recommandation sociale (filtrage collaboratif) sont classées en 2 sous-types:
- memory-based
- model-based
User-based nearest neighbor (user-centric / memory-based)
Les algorithmes de recommandation sociale utilisent généralement différentes variantes d’un mécanisme basé sur le voisinage proche (user-based nearest neighborhood approach). Dans cette approche, un nombre d’utilisateurs (peer users / nearest neighbors / plus proches voisins) est identifié et sélectionné sur la base de la similarité de leurs intérêts et préférences avec l’utilisateur actif. On utilise alors principalement les ratings (par ex: films) de ces utilisateurs “voisins” pour calculer des similarités avec l’utilisateur actif. Pour chaque produit p que l’utilisateur n’a pas encore vu, une prédicition est faite en se basant sur les ratings de p assignés par le panel d’utilisateurs voisins. Cette méthode suppose 2 conditions initiales (inconvénients):
- On assume que si des utilisateurs ont eu des goûts similaires dans le passé, ils auront aussi des goûts similaires dans le futur.
- Les préférences des utilisateurs restent stables et cohérentes dans le temps.
Pour bien comprendre, on peut imaginer un tableau ou matrice de ratings de films, avec sur un axe les utilisateurs et sur un autre les films. Chaque cellule de la matrice contient le rating donné par un utilisateur pour un film. Un signe “+” indique que l’utilisateur a aimé le film, un signe “-” qu’il ne l’a pas aimé, pas de signe signifie qu’il n’a pas d’avis particulier sur ce film. Pour pouvoir prédire si Ken apprécierait le film “Fargo” et éventuellement lui recommander ce film, on compare les ratings de Ken à ceux des autres utilisateurs sélectionnés. On peut alors voir que Ken et Mike ont des ratings identiques, et que Mike a aimé le film Fargo, on pourrait alors prédire que Ken aimera aussi ce film et lui faire cette suggestion (user-centric).
Au lieu de se baser uniquement sur l’utilisateur le plus semblable, la prédiction est normalement calculée à partir de la moyenne pondérée des ratings de plusieurs utilisateurs. Le poids donné au rating de chaque utilisateur est déterminé par le degré de corrélation entre cet utilisateur et l’utlisateur pour qui on désire faire la recommandation. Pour mesurer le degré de corrélation entre 2 utilisateurs, on fait appel généralement au coefficient de corrélation de Pearson r. D’autres indicateurs de mesure de la similarité ou proximité entre utilisateurs sont aussi utilisés comme la corrélation de Ringo, ou le coefficient de corrélation de Spearman. Le coefficient de corrélation de Pearson se calcule à partir des valeurs présentes dans la matrice et peut prendre une valeur allant de +1 (forte corrélation positive) à -1 (forte corrélation négative). Par exemple, un coefficient de corrélation 0.70 entre 2 utilisateurs indiquerait une bonne similarité de leurs intérêts. On introduit aussi souvent dans le calcul de la mesure de Pearson un facteur de pondération afin de prendre en compte et pondérer le fait que certains utilisateurs ont toujours tendance à donner seulement de bons ratings, ou que d’autres ne vont jamais donné le rating maximum à un produit.
Les systèmes de recommandation doivent généralement aussi gérer un grand nombre d’utilisateurs. Faire des recommandations à partir des ratings de millions d’utilisateurs peut avoir de sérieuses implications en termes de performance. Ainsi, qua
nd le nombre d’utilisateurs atteint un certain seuil, une sélection des “meilleurs” voisins doit être faite. Pour déterminer quels sont les voisins les plus pertinents à sélectionner, on utilise généralement l’algorithme du k-nearest neighbor (k-NN) qui permet de sélectionner seulement les k meilleurs voisins ayant la plus haute valeur de corrélation. Une autre approche (correlation-thresholding) serait de sélectionner seulement les voisins possédant une corrélation plus grande qu’un certain seuil. Le problème dans ces deux approches réside dans le fait de sélectionner le bon nombre k d’utilisateurs voisins à prendre en compte ou de déterminer la bonne valeur du seuil de corrélation. Si le nombre k est trop petit ou si le seuil de similarité est trop élevé, le nombre d’utilisateurs voisins pris en compte sera trop réduit pour effectuer une bonne prédiction (problème du reduced coverage/couverture réduite). Dans le cas contraire, lorsque que k est trop élevé ou que le seuil est trop faible, l’ensemble du panel de voisins est trop large (trop d’utilisateurs avec un degré de similarité limité), ce qui amène du bruit additionnel dans les prédictions. Plusieurs travaux et situations réelles ont montré qu’un panel composé de 20 à 50 voisins donne de bons résultats.
On n’est pas non plus limités aux ratings ou like/dislike, on peut aussi se baser sur des données plus implicites en observant le comportement de l’utilisateur sur le site, par opposition à la récolte de données explicite comme l’est le rating. On peut observer par exemple quelle musique il a écouté, quel article il a lu, et on croise ses infos avec celles du reste des utilisateurs afin de lui proposer de nouvelles suggestions.
La recommandation sociale user-centric a cependant ses limites. Lorsqu’il s’agit d’un gros site qui gère des millions d’utilisateurs et un catalogue de milliers de produits, il faut scanner un grand nombre de voisins potentiels, ce qui rend impossible la recommandation en temps réel. Pour palier ce problème, les gros sites implémentent souvent une technique différente plus apte au traitement préalable des données hors-ligne (offline preprocessing), la recommandation sociale item-centric (à ne pas confondre avec la recommandation objet).
Item-based nearest neighbor (item-centric / model-based)
Cette autre approche, appelée aussi item-to-item, propose une inversion de l’approche user-based nearest neighbor. Au lieu de mesurer la corrélation entre des utilisateurs, les ratings sont utilisés pour mesurer la corrélation entre les contenus (films), en s’aidant toujours du coefficient de corrélation de Pearson, mais cette fois-ci appliqué au contenu. Si par exemple les ratings des deux films “Fargo” et “Pulp Fiction” ont une parfaite corrélation, c’est-à-dire qu’ils ont reçu les mêmes ratings (positif, négatif ou nul) de la part des utilisateurs, on peut ainsi prédire que Ken aimera le film “Fargo” car il a aimé “Pulp Fiction” (les ratings des utilisateurs sur ces deux films sont parfaitement corrélés).
Pour le dire autrement, l’approche item-centric propose de rechercher en premier lieu des contenus similaires et ensuite de faire une recommandation à l’utilisateur. Cette approche permet de faire un traitement préalable sur la matrice pour déterminer les contenus similaires et ainsi pouvoir effectuer des prédictions en temps réel, contrairement à l’approche user-centric très gourmande en mémoire.
Autant le coefficient de corrélation de Pearson est très utilisé pour déterminer des utilisateurs similaires (cas de la recommandation sociale user-centric), dans l’approche item-centric, on utilise plutôt comme indicateur de mesure de similarité entre items un autre indicateur qu’on appelle de similarité cosinus ajustée. Les valeurs possibles pour cet indicateur vont comme dans le cas de mesure de Pearson de +1 (forte similarité positive) à -1 (forte similarité négative). Une fois que la similarité entre les items a été établie à l’aide de la similarité cosinus ajustée, on peut alors prédire un rating pour un item grâce aux ratings effectués par l’utilisateur sur les items similaires.
Dans l’approche item-centric, l’idée est donc de construire à l’avance la matrice de similarité entre items. Et en temps réel, on peut facilement ensuite déduire la prédiction de recommandation (le rating) d’un produit pour un utilisateur actif en déterminant depuis la matrice déjà construite quels sont les produits les plus similaires, et en calculant la valeur moyenne de ratings sur ces produits effectués par les utilisateurs voisins.
Avantages et inconvénients
Avantage: L’approche purement de recommandation sociale n’exploite pas ou ne demande aucune connaissance sur les contenus eux-même. Par exemple, dans le cas d’un magasin de vente de livres en ligne, le système de recommandation collaboratif n’a pas besoin de savoir le type de contenu du livre, son genre, qui en est l’auteur, etc… Pas besoin de se baser sur l’analyse des propriétés intrinsèques d’un livre ou d’un contenu, la recommandation sociale est capable de recommander des contenus sans avoir besoin de comprendre le sens ou la sémantique du contenu lui-même. Les informations propres au livre n’ont pas besoin d’être introduite dans le système.
Inconvénients:
- Scalability: souvent, les plate-formes sur lesquelles sont utilisés les filtres collaboratifs ont des millions d’utilisateurs, de produits et contenus. Ça demande donc beaucoup de puissance de calcul pour pouvoir proposer des suggestions aux utilisateurs. La recommandation sociale de type user-centric est aussi appelée memory-based, car la base de données des ratings est maintenue en permanence en mémoire dans le serveur et utilisée directement pour générer des recommandations à l’utilisateur actif. Bien que cette approche memory-based soit théoriquement plus précise, car elle a disposition en permanence et en temps réel toutes les données pour générer les recommandations, elle souffre de problèmes de scalability pour des bases de données de millions d’utilisateurs et de millions de contenus. Dans une approche item-centric ou model-based, les données sont préalablement traitées hors-ligne. Ensuite lors de l’exécution de l’application ou service web, le modèle “appris” ou pré-traité sera utilisé pour effectuer les prédictions. L’approche model-based permet d’éviter le problème de scalability.
- Cold Start: les systèmes de recommandation sociale ont besoin de beaucoup de données et beaucoup d’utilisateurs pour être performants. Le lancement d’un service de recommandation peut souffrir au début du manque d’utilisateurs et d’informations sur ceux-ci.
- Sparsity (Rareté): le nombre de produits ou contenus est énorme sur certaines plates-formes, et même les utilisateurs les plus actifs auront noté ou valorisé qu’un tout petit sous-ensembe de toute la base de données. Donc, même l’article le plus populaire n’aura que très peu de bonnes notes. Dans une telle situation, deux utilisateurs auront peu d’articles valorisés en commun, ce qui rend plus difficile la tâche de corrélation. C’est une situation qu’on retrouve lorsque le système dispose d’un ratio élevé de contenu par rapport aux utilisateurs, et qu’on retrouve aussi souvent au stade initial du lancement du service de recommandation, ce qui nous ramène au problème de cold start (qui peut être vu comme un cas spécial du problème de rareté).
Recommandation Hybride
Une combinaison des trois approches ci-dessus. Les méthodes hybrides sont de plus en plus utilisées, car elle permettent de résoudre des problèmes comme le cold start et la sparsity (rareté) qu’on retrouve dans une approche de recommandation uniquement sociale. D’autre part, si par exemple on considère 2 utilisateurs avec les mêmes goûts mais qui n’ont pas évalué ou “raté” des objets en commun, un filtrage collaboratif pur ne les considérera pas comme similaires ou voisins. Rappelons que la mesure de similarité standard ne prend en compte que les éléments pour lesquels l’utilisateur actif et l’utilisateur à comparer ont effectué un rating. L’idée est alors de pouvoir assigner une valeur par défaut aux éléments qui ont été “ratés” seulement par un des deux utilisateurs, afin d’améliorer la qualité de prédiction en cas de rareté (sparsity). En appliquant préalablement un algorithme de recommandation objet sur les contenus pour en exploiter leurs descriptions et caractéristiques, accompagné ensuite d’un algorithme de recommandation sociale pour effectuer les recommandations peut aider à résoudre ces limitations. Autrement dit, pour les cas de rareté (sparsity), lorsque peu d’items ont été évalués par les utilisateurs et qu’un filtrage collaboratif n’est pas possible, ce qu’on fait, c’est qu’on assigne en premier lieu un pseudo-rating ou vote artificiel par défaut à l’utilisateur sur les contenus disponibles en utilisant préalablement un algorithme objet, puis on applique ensuite sur la matrice (contenant peu de vrais rating et beaucoup de pseudo-ratings) un filtrage collaboratif.
Exemples:
Netflix est aussi un bon exemple de système hybride. Il propose des recommandations en comparant les habitudes de visionnage des films d’utilisateurs similaires (recommandation sociale) et suggère aussi des films qui partagent des caractéristiques avec des films que l’utilisateur a noté positivement (recommandation objet).
- Recommandation Personalisée:
- Google customise nos résultats de recherche, quand cela est possible, en se basant sur notre localisation et/ou nos dernières recherches.
- Lorsqu’on est connecté à notre compte Google, il propose un contenu encore plus pertinent en fonction de notre historique de recherche.
- Recommandation Sociale:
- L’algorithme du PageRank est de manière intrinsèque un outil basé sur de la recommandation sociale dans la mesure ou il utilise les liens entre les pages web.
- L’utilisation de contenus provenant de nos cercles de Google+ est aussi une forme de recommandation sociale.
- Recommandation Objet
- Google utilise aussi une approche sémantique pour sa fonction « Did you mean » de son moteur de recherche.
Pandora vs Last.fm
La différence entre les approches de recommandation objet et de recommandation sociale (collaborative) peut être illustrée en comparant deux services de radio en ligne que sont Pandora (seulement disponible aux USA) et Last.fm.
Pandora utilise principalement une approche de recommandation objet. Le système se base sur les propriétés de la chanson et/ou de l’artiste, c’est à dire il décompose dans un premier temps les morceaux de musique afin de mettre en évidence ses propriétés intrinsèques. Chaque morceau de musique disposerait de plus de 400 attributs, permettant de déterminer une sorte de code génétique de la chanson (Music Genome Project). En comparant les propriétés similaires entre différents morceaux, le système arrive alors à nous proposer de nouvelles chansons à écouter, c’est-à-dire une sorte de station radio qui diffuse de la musique avec des propriétés susceptibles de correspondre à nos goûts. L’utilisateur peut ensuite indiquer s’il aime ou pas le morceau en écoute, et permet ainsi à Pandora d’affiner son filtre de recommandation en privilégiant (ou pas) certains attributs selon l’information venue en retour de l’utilisateur.
Last.fm lui utilise un filtre de recommandation sociale (collaborative). Le service crée une station de radio personnalisée en observant quels sont les groupes, artistes et chansons que l’utilisateur a écouté régulièrement et les compare avec les comportements d’écoute d’autre utilisateurs. Last.fm va alors proposer des morceaux fréquemment écoutés par des utilisateurs ayant des goûts similaires.
Netflix Prize
De 2006 à 2009, Netflix a parrainé un concours, le Netflix prize, offrant un prix de $1’000’000 à celui qui à partir d’un set de données de plus de 100 millions de ratings de films pourrait offrir des recommandations 10% plus précises que celles générées par le système original de la compagnie Netflix. Le 21 septembre 2009, le prix a été attribué à une équipe appelée BellKor’s Pragmatic Chaos. Les gagnants avaient misé sur un mélange de centaines d’approches algorithmiques et méthodes prédictives qui réunies ensemble permettent d’être plus performant dans la prédiction. La solution la plus performante semble donc bien s’appuyer sur un ensemble de méthodes algorithmiques plutôt que sur le raffinement et l’optimisation d’une seule technique spécifique.
Pour l’anecdote, le Netflix prize n’a pas été renouvelé en 2010, car malgré le fait que le set de million de données fournies aux participants du concours aient été rendues anonymes pour préserver l’identité des clients, deux chercheurs de l’Université du Texas ont été capables d’identifier des utilsateurs présents dans le set de données utilisé lors du concours en associant et croisant ces données avec des ratings de films soumis sur l’Internet Movie Database (IMDb). Il s’en est suivi qu’en décembre 2009, un des utilisateurs anonymes du set de données a poursuivi Netflix pour violation de la législation américaine en terme de confidentialité.
Efficacité d’un algorithme de recommandation
On a vu que la recommandation sociale (filtrage collaboratif) a l’avantage contrairement à la recommandation objet de permettre d’effectuer des prédicitions même lorsqu’il y a peu de information associée au contenu à recommander ou lorsque que le contenu est difficile d’analyser automatiquement (idées, opinions…) Mais la recommandation sociale souffre aussi d’inconvénients comme le cold start et le problème de rareté (sparsity).
Evaluer l’efficacité des algorithmes de recommandation est loin d’être trivial. En premier lieu, parce que différents algorithmes peuvent être meilleurs ou moins bons en fonction du set de données sélectionné et sur lequel ils sont appliqués. D’autre part, les objectifs fixés par un système de recommandation peuvent être divers et variés. Un système de recommandation peut être mis en place pour estimer avec exactitude la note que donnerait un utilisateur à un élément, alors que d’autres auront comme objectif principal de ne pas proposer des recommandations erronées.
On peut donc légitimement se demander jusqu’à quel point ces différentes méthodes de recommandation sont réellement efficaces. Pour déterminer l’efficacité d’un système, des indicateurs comme la précision et le recall sont utilisés.
La précision est un indicateur qui représente la qualité de la recommandation, c’est-à-dire à quel point les suggestions proposées sont conformes aux intérêts de l’utilisateur:
précision = nbre de suggestions pertinentes / nbre de suggestions
Le recall indique combien de suggestions pertinentes ont été recommandées à l’utilisateur par rapport au nombre total de suggestions pertinentes disponibles dans le système.
recall = nbre de suggestions pertinentes proposées à l’utilisateur / nbre de suggestions pertinentes totale
L’indicateur de précision permet de déterminer la probabilité qu’un élément recommandé soit pertinent.
L’indicateur de recall permet de déterminer la probabilité qu’un élément pertinent soit recommandé.
On utilise aussi des techniques statistiques pour mesurer l’efficacité d’un algorithme de recommandation. L’idée c’est d’évaluer la précision de la prédiction effectuée par le système en comparant les prédicitions avec les choix qu’aurait fourni l’utilisateur dans un cas réel. On utilise par exemple l‘Erreur Moyenne Absolue (MAE) qui mesure la déviation des recommandation prédites avec les choix réels effectués par les utilisateurs. Plus l’erreur moyenne absolue est faible, meilleure est la prédicition.
Pour conclure, la meilleure mesure de l’efficacité d’un algorithme de recommandation et de la pertinence des suggestions c’est finalement la satisfaction de l’utilisateur, qui n’est pas toujours facile à bien identifier.
Sources:
http://www.readwriteweb.com/archives/recommendation_engines.php
http://fr.wikipedia.org/wiki/Syst%C3%A8me_de_recommandation
http://en.wikipedia.org/wiki/Recommender_system
http://en.wikipedia.org/wiki/Collaborative_filtering
http://recommender-systems.org/
http://www.it.uc3m.es/jvillena/irc/descarga.htm?url=practicas/06-07/31.pdf
http://www.docstoc.com/docs/35703482/Top-N-Recommendation-Algorithm-B
http://www.cs.utexas.edu/users/ml/papers/cbcf-aaai-02.pdf
http://www.amazon.es/Recommender-Systems-Introduction-Dietmar-Jannach/dp/0521493366