Les systèmes de recommandations

Institut Mines-Télécom

Les systèmes de

recommandations

Romain Picot-Clémente


Introduction

21/07/2015 Les systèmes de recommandations 2


Origines

• Personnalisation de la présentation (feuille de style, disposition des éléments, etc.)

• Personnalisation de la navigation (modification du graphe hypermédia)

• Personnalisation du contenu (modification de la complexité du contenu selon contexte, profil, etc.)

21/07/2015 Les systèmes de recommandations - Introduction 3

Systèmes hypermédia adaptatifs

Systèmes de recommandations

Systèmes hypermédia adaptatifs (Brusilovsky et al., 1996)

Introduit initialement

pour le e-learning


Origines

Personnalisation de la navigation (modification du graphe hypermédia)


Systèmes hypermédia adaptatifs



Institut Mines-Télécom 21/07/2015 Les systèmes de recommandations - Introduction 5

Pour l’utilisateur

Pour le fournisseur

Intérêt utilisateur

Systèmes de recommandations :

A quoi ça sert ?

• Réduire le temps de recherche d’information

• Découvrir des produits difficiles à trouver

• …

𝐴𝑚é𝑙𝑖𝑜𝑟𝑒𝑟 𝑙′𝑒𝑥𝑝é𝑟𝑖𝑒𝑛𝑐𝑒 𝑢𝑡𝑖𝑙𝑖𝑠𝑎𝑡𝑒𝑢𝑟

Institut Mines-Télécom 21/07/2015 Les systèmes de recommandations - Introduction 6

Pour l’utilisateur

Pour le fournisseur

Intérêt pour fournisseur du service

Systèmes de recommandations :

A quoi ça sert ?

• Garder/engager/fidéliser les clients

• Orienter les clients

• Augmenter les bénéfices

• …


Applications


Exemples de domaines d’application

• Films (Netflix, Allocine, …)

• Musiques (Deezer, …)

• Jeux vidéo (Steam, Microsoft Xbox Live, ...)

• Livres (Amazon, Fnac, …)

• « Amis » (Facebook, Twitter, Google+, …)

• Tourisme (Expedia, …)

• e-Shopping (Cdiscount, eBay, Amazon, Fnac, …)

• Publicité ciblée (Criteo, …)

• Nutrition/sport/bien-être (Withings, Fitnext, …)

• Médical

• …


Définitions, types de

systèmes de recommandation



• Utilisateurs : individus cibles de la recommandation

• Items : ensemble des éléments possiblement recommandables aux utilisateurs

Items, utilisateurs, matrice d’usage


Deux classes d’entités

Matrice d’usage

Items et utilisateurs


Items, utilisateurs, matrice d’usage


Deux classes d’entités

Matrice d’usage

Matrice d’usage : relie utilisateurs et items par une matrice de score

HP1 HP2 HP3 TW SW1 SW2 SW3

A 4 5 1

B 5 5 4

C 2 4 5

D 3 3

Valeur inconnue

Utilis

ate

urs

Items

Le score peut représenter

différents types d’interaction : une

note, un nombre d’utilisation, une

durée, un « like », etc.


Deux grands groupes de systèmes de

recommandations


Basé sur la similarité du profil de l’utilisateur avec le profil des items

Basé sur le contenu (content-based)

Filtrage collaboratif (collaborative filtering)

Systèmes de recommandations basés sur le contenu


Deux grands groupes de systèmes de

recommandations


Basé sur la similarité de comportement (achats, visites, clics, notes, etc.) entre les utilisateurs

Basé sur le contenu (content-based)

Filtrage collaboratif (collaborative filtering)

Systèmes de recommandations par filtrage collaboratif



basés sur le contenu



Principe général de la recommandation

basée sur le contenu


Profilage items et utilisateur

Recommandation par distance

• Profil items : vecteur de scores sur des attributs/descripteurs

• Profilage utilisateurs :

─ Implicite (selon les interactions avec les items)

─ Explicite (question directe)

Utilisateur

Profil

utilisateur

(vecteur

d’attributs)

Items

Profilage

items Profils

items

(vecteurs

d’attributs)

Profilage

utilisateur

Interactions

Faire attention aux échelles entres attributs


Principe général de la recommandation

basée sur le contenu


Profilage items et utilisateur

Recommandation par distance

Utilisateur

Profil

utilisateur

(vecteur

d’attributs)

Items

Profilage

items Profils

items

(vecteurs

d’attributs)

Calcul de

distances

Les items avec

des profils

proches sont

recommandés

Profilage

utilisateur

Interactions

• Calcul de distances entre profils utilisateur-items (distance cosinus, jaccard (pour 0-1 scores), Pearson, …)

• Recommandation des items les plus proches


• Bob a aimé A et C

─ Vecteur utilisateur :

• Profilage de Bob

─ Vecteur profil :

• Recommandation

─ Distance de Pearson entre 𝑝 et chaque vecteur film/genre (ligne de 𝐼)

─ Recommandation des films dont les distances avec 𝑝 sont les plus proches


Approche classique

Horreur Epouvante Action Romance Comédie Animation Sci-Fi Film

d’auteur

A 1 1 1

B 1 1 1

C 1 1 1

D 1 1

E 1 1

Film

s

Genre

Matrice 𝐼 =

𝑢 = 1 0 1 0 0

𝑝 = 𝑢. 𝐼 = 1 0 2 0 2 1 0 0

Horreur Epouvante Action Romance Comédie Animation Sci-Fi Film

d’auteur

A B C D E

Autres approches

Approche classique : exemple

Approches pour la recommandation basée

sur le contenu

Institut Mines-Télécom 21/07/2015 Les systèmes de recommandations 17

Approches pour la recommandation basée

sur le contenu

Approche classique

Autres approches

• Passage dans un espace latent de dimensions plus faibles, pour augmenter la densité de la matrice item-attribut (classification non-supervisée des items). Calcul de distance utilisateur-item dans cet espace.

• Réduction de dimension par utilisation d’ontologies pour relier des attributs dont les concepts sont plus ou moins éloignés (ex: maths et physiques en sciences). Toujours dans le but d’augmenter la densité de la matrice item-attribut.

• Modèle d’apprentissage pour chaque utilisateur (réseau de neurones, arbre de décision, forêt aléatoire, SVM, etc.) pour prédire si un item va correspondre à l’utilisateur ou non.

Autres approches


Système de recommandation

basé sur le filtrage collaboratif



Principe de base de la recommandation par

filtrage collaboratif


Interaction utilisateurs sur items

Matrice d’usage

Similarités entre les utilisateurs

sim(Alice, Bob) > sim(Chris, Bob)

Recommandation basée sur la similarité des usages entre utilisateurs

Matrice d’usage

1 11 1

0 −1−1 1

0 −11 0

1 0−1 0

Les recommandations pour un utilisateur U sont les items qui sont aimés par les utilisateurs qui lui sont similaires


Approches pour la recommandation par




A 4 5 1

B 5 5 4

C 2 4 5

D 3 3

Utilis

ate

urs

Films


A 2/3 5/3 -7/3

B 1/3 1/3 -2/3

C -5/3 1/3 4/3

D 0 0

Utilis

ate

urs

Films

A savoir: Il existe aussi le

filtrage collaboratif par voisinage item

Approche classique : voisinage utilisateur

Factorisation matricielle

Exemple 1 : filtrage collaboratif par voisinage utilisateur

• Matrice d’usage

• Utilisateur cible 𝐴

• Normalisation par ligne (soustractions de la valeur moyenne)

• Similarités de Pearson 𝑠𝑖𝑚(𝐴, 𝐵) = 0,06 ; 𝑠𝑖𝑚(𝐴, 𝐶) = −0,69 ; 𝑠𝑖𝑚(𝐴, 𝐷) = 0

• Recommandations : 𝑠𝑐𝑜𝑟𝑒 𝐴, 𝑖𝑡𝑒𝑚 = sim A,u × score u,itemu∈utilisateurs

sim A,uu∈utilisateurs

𝑠𝑐𝑜𝑟𝑒 𝐴,𝐻𝑃2 = 0,03 ; 𝑠𝑐𝑜𝑟𝑒 𝐴, 𝐻𝑃3 = −0,05 ; 𝑠𝑐𝑜𝑟𝑒(𝐴, 𝑆𝑊2) = −1,23 ; 𝑠𝑐𝑜𝑟𝑒(𝐴, 𝑆𝑊3) = 0

Inconvénients - Temps de calcul important s’il y a beaucoup d’utilisateurs/items - Difficile de trouver des similarités dans des matrices d’usage peu dense (ce qui est généralement le cas)

Clustering

Autres







Exemple 2 : filtrage collaboratif par regroupement (clustering)

• Matrice d’usage

• Regroupement des items

• Le score d’un utilisateur pour un item est le score pour son cluster. Exemple : 𝑠𝑐𝑜𝑟𝑒(𝐴, 𝐻𝑃2) = 4

• S’il n’y a aucune valeur (ou 𝑠𝑐𝑜𝑟𝑒 = 0) alors calcul du score basé sur similarité des utilisateurs (comme exemple précédent) sur la matrice de utilisateurs- clusters

Clustering

Autres


A 4 5 1

B 5 5 4

C 2 4 5

D 3 3 U

tilis

ate

urs

Films

Le clustering peut se faire sur les

utilisateurs et/ou items, et plusieurs fois

si besoin

HP TW SW

A 4 5 1

B 4,67

C 2 4,5

D 3 3 Utilis

ate

urs

Cluster de films







Exemple 3: filtrage collaboratif par factorisation matricielle SVD

• Soit une matrice d’usage 𝑀 ∶ 𝑈𝑡𝑖𝑙𝑖𝑠𝑎𝑡𝑒𝑢𝑟𝑠 × 𝐼𝑡𝑒𝑚𝑠

• Factorisation matricielle 𝑆𝑉𝐷 (singular value decomposition) 𝑀 = 𝑈𝑆𝑉𝑇

• Les 𝑛 premières valeurs singulières de 𝑆 sont gardées et donne une nouvelle matrice diagonale 𝑆’

• Nouvelle matrice de score selon les valeurs singulières sélectionnées 𝑀’ = 𝑈𝑆′ 𝑉𝑇

• Les items avec les plus grands scores sont recommandés à l’utilisateur

Clustering

Autres

Il existe de nombreux autres types de

factorisation matricielle







Clustering

Autres

De nombreuses autres approches

• Règles d’association

• Parcours de graphe

• Modèle d’apprentissage


Avantages et inconvénients

des deux approches



Avantages et inconvénients des deux

approches


SR basé sur le contenu

• Avantages

─ Permet des recommandations de nouveaux items

─ Un nouvel utilisateur peut recevoir des recommandations dés ses premières interactions avec le système

• Inconvénient

─ Nécessite une quantité importante de descripteurs sur les items et/ou utilisateurs

Systèmes de recommandations basés sur le contenu

SR basé sur le filtrage collaboratif



• Avantage

─ Pas besoin de descripteurs sur les items/utilisateurs

• Inconvénient

─ Problème de démarrage à froid, pas de recommandations possibles s’il n’y a pas eu suffisamment d’interactions utilisateurs/items

Systèmes de recommandations basés sur le filtrage collaboratif



approches




Ces deux approches ne sont pas disjointes et sont la plupart du temps

combinées


approches


Recommandation tenant compte

d’informations additionnelles



De nombreuses informations additionnelles


Sur utilisateurs/items

Informations additionnelles sur utilisateurs/items

• Informations personnels (âge, métier, genre, …)

• Réseau social

• Tags

• Positions géographiques

• Commentaires, avis textuels

Sur interactions U-I






Informations contextuelles associées aux interactions U-I

• Temps (Heure)

• Météo

• Humeur

• Position géographique






Vers des systèmes de plus en plus sensibles au contexte, au temps, aux habitudes, aux interactions sociales, aux sentiments, …


Approches tenant compte d’informations

additionnelles sur utilisateurs/items


Matrice

U-I

Voisinage

utilisateur/item

Informations

additionnelles

utilisateurs

Voisinage

utilisateur

Voisinage

item

Information

additionnelles

items

Recommandations

Approches par voisinages

Voisinages

Modèles à facteurs latents

Modèles d’apprentissage

Graphes





Voisinages



Graphes

Matrice

U-I Paramètres

Informations

additionnelles

utilisateurs

Informations

additionnelles

items

Apprentissage d’un

modèle prédictif

basé sur les

paramètres

Paramètres

Paramètres

Recommandations

Approches par modèles d’apprentissage





Voisinages


Graphes

Approches par modèles à facteurs latents

Modèle prédictif

Matrice

U-I U

Informations

additionnelles

utilisateurs

Informations

additionnelles

items

Recommandations

V

U P

V Q

Factorisation de U-I sous contrainte des informations additionnelles






Voisinages


Graphes

Approches par graphes


Matrice

U-I

Informations

additionnelles

utilisateurs

Informations

additionnelles

items

Approches par

exploration du

graphe

Recommandations

Graphe incluant

utilisateurs, items,

entités issues des

informations

additionnelles, et

leurs relations


Approches Complexité du

modèle

Complexité

spatiale

Complexité

temporelle

Explicabilité

des résultats

Voisinages Moyenne Importante Importante Importante

Modèles Importante Faible Importante Faible

Graphes Faible Moyenne Importante Moyenne



Propriétés succinctes des approches



contextuelles liées aux interactions U-I


Dépendantes du temps

« Factorization Machines »

Factorisation tensorielle

Graphes

Méthodes par filtrage collaboratif dépendantes du temps

Méthodes qui favorisent les interactions plus récentes afin de proposer des recommandations plus en phase avec les profils courants.

Méthodes très spécifiques à l’information temporelle, ne sont

pas généralisable aux autres données contextuelles








Graphes

Méthodes par factorisation tensorielle

Matrice

U-I

Informations

contextuelles

liées aux

interactions

Tenseur

Utilis

ate

urs

Items

U

V

Modèle

prédictif

Recommandations








Graphes

Méthodes par « Factorization Machines » [Rendle, 2010]

• Est une généralisation des méthodes à base de factorisation

• Permet de considérer à la fois les informations de contexte et les informations en rapport avec items/utilisateurs

« one-hot encoding »

Où il s’agit de déterminer

Factorization machine de degré 2:








Graphes

Méthodes par graphes

Matrice

U-I

Informations

additionnelles

Approches par

exploration du

graphe

Recommandations

Graphe incluant

utilisateurs, items,

entités issues des

informations

additionnelles, et

leurs relations

Permet de considérer à la fois les informations de contexte et les informations en rapport avec

items/utilisateurs


Approches Complexité du

modèle

Complexité

spatiale

Complexité

temporelle

Explicabilité

des résultats

Tenseurs Importante Faible Importante Faible

Factorization

machines Importante Faible Importante Faible

Graphes Faible Moyenne Importante Moyenne

Les méthodes FC dépendantes du temps ne sont pas pertinentes dans cette comparaison elles ne représentent pas un framework général d’utilisation d’information contextuelle pour la recommandation, elles se limitent à l’utilisation du temps

Propriétés succinctes des approches




Quelques contributions



Recommandation de lieux pour des réseaux

sociaux géographiques


Informations géographiques

Réseau social

Réseau social de partage de lieux (Location-Based Social Network)

Réseau social géographique ?


Graph-based approach for location

recommendation in LBSNs using Katz Centrality


𝑪 =𝜶𝑺 𝜷𝑭

𝜷𝑭𝑻 𝜸𝑮

Places

Places

Users

Users

F=

⋯ ⋯ ⋯⋮ ⋱ ⋮⋯ ⋯ ⋯

Users

Places Graphe de fréquentation (matrice d’usage)

S=0 ⋯ ⋯⋮ ⋱ ⋮⋯ ⋯ 0

Users

Users Graphe social

Graphe géographique?

Graphe considérant frequentations, social et positions géographiques (des lieux)


𝑪 =𝜶𝑺 𝜷𝑭

𝜷𝑭𝑻 𝜸𝑮

Places

Places

Users Users


G =

0 ⋯⋯ 0

⋯ ⋯ ⋯⋯ ⋯ ⋯

⋯ ⋯⋯ ⋯⋯ ⋯

0 ⋯ ⋯⋯⋯

0⋯

⋯0

Places

Places

𝑓(𝑥) = 𝑎𝑥𝑏

𝑓(𝑑𝑖𝑠𝑡𝑎𝑛𝑐𝑒(𝑃𝑙𝑎𝑐𝑒𝑖 , 𝑃𝑙𝑎𝑐𝑒𝑗))

Global distribution of all users visits according to the mutual distances

Low distances between places gives high values in G, and inversely Scores are computed according to

the distances between places



Graphe géographique


𝐾𝑎𝑡𝑧 𝐶 = 𝛽𝐶 + 𝛽2𝐶2 + 𝛽3𝐶3 +⋯ converge pour 0 ≤ 𝛽 <

1

max ( 𝜆 𝐶 )

max ( 𝜆 𝐶 ) est la plus grande valeur propre de 𝐶 (appelé rayon spectral)

𝐾𝑎𝑡𝑧(𝐶) = ⋯ 𝐹′⋯ ⋯

Matrice des scores de prédiction après propagation de Katz

Users

Users

Places

Places

Complexité algorithmique:

𝑂 𝑁𝑢 × 𝑛𝑛𝑧 , avec 𝑁𝑢, le nombre de

d’utilisateurs et 𝑛𝑛𝑧, le nombre de

« non-zero » dans 𝐹𝐹𝑇 𝑘

𝐾𝑎𝑡𝑧 𝐶 12 = 𝛽 𝐹 + 𝛽2 𝑆𝐹 + 𝐹𝐺+ 𝛽3 𝑆2𝐹 + 𝐹𝐹𝑇𝐹 + 𝑆𝐹𝐺 + 𝐹𝐺2 +⋯



Centralité de Katz [Katz, 1953] Permet d’identifier des relations distantes entre des nœuds d’un graphe


𝐾𝑎𝑡𝑧 𝐶 12 = 𝛽 𝐹 + 𝛽2 𝑆𝐹 + 𝐹𝐺+ 𝛽3 𝑆2𝐹 + 𝐹𝐹𝑇𝐹 + 𝑆𝐹𝐺 + 𝐹𝐺2 +⋯

Places visited by friends Places close to the

visited places

Places visited by friends of friends

Places visited by users that have visited the

same places

Places close to places visited by friends

Places close to places close to the visited

places



Les chemins considérés dans 𝑲𝒂𝒕𝒛 𝑪 𝟏𝟐


Context and social based recommender

system using association rules


DB History

Learning partOffline

Recommendation partOnline

Association rules mining

All users' past visiting sessions

Rules selection

DB Association

Rules

Rules scoringItems selection

- visiting session- position- desired TOR- friends

Profile

selected ruleswith scores

recommendations

Recommandation contextuelle et sociale de lieux qui dépend du type de recommandation désiré par l’utilisateur

• Contexte :

─ Session de visites

─ Position courante

─ Type de recommandation désiré (veut-il des recommandations évidentes ? surprenantes ? rares ? populaires ?)

• Visites passées des amis





Partie hors-ligne, apprentissage de règles d’association

Learning part

Recommendation part

• Transaction : session de visites (ensemble de lieux)

• Extraction de toutes les règles d’association





Partie en-ligne, temps-réelle, moteur de recommandation

Learning part

Recommendation part

• Sélection de règles correspondantes à la session de visites de l’utilisateur

• Calcul de scores de pertinences pour chaque règles sélectionnées selon une mesure de pertinence

• Pondération et sélection des items à recommander

𝑀𝑝 𝑟𝑖 = 𝑀𝑔 𝑟𝑖 𝛼𝑀𝑖 𝑟𝑖 + 1 − 𝛼 𝑀𝑠 𝑟𝑖

• 𝑴𝒊 dépend du type de recommandation désiré:

Confiance, Surprise, Rareté, Popularité

• 𝑴𝐠 dépend de la position géographique courante de

l’utilisateur. Elle met en avant les règles dont le lieu conséquent n’est pas trop éloigné de l’utilisateur.

• 𝑴𝐬 dépend des visites des utilisateurs amis. Elle met en avant les règles qui se sont vérifiées souvent chez les amis de l’utilisateur courant.


Evaluation de la qualité des

recommandations



Hors ligne

Evaluation hors ligne

• Jeux d’apprentissage et de test

─ Pas de convention pour définir ces jeux

• Algorithme de recommandation sur jeu d’apprentissage

• Matrice de score prédis ou k-recommandations

• Mesures de qualité

─ RMSE entre scores prédis et scores réels

─ Rappel, Précision, F1-Score, ROC

En ligne

Problème Chercher à « améliorer la prédiction des futures scores/actions des utilisateurs », diffère de « améliorer la qualité des recommandations »

Evaluation de la qualité des recommandations


Evaluation de la qualité des recommandations


Hors ligne

Evaluation en ligne

• A/B testing

─ Test de recommandations différentes sur un groupe A et un groupe B d’individus

─ Validation méthode dont les recommandations ont amélioré une fonction objectif (augmentation du nombre d’achat, du bénéfice, du temps passé par les utilisateurs sur les pages, satisfaction des utilisateur, etc.)

En ligne

Problème Très couteux à mettre en place


Quelques perspectives du

domaine

Quelles pistes pour améliorer les

recommandations ?



Quelques perspectives du domaine

o Social • Identification d’utilisateurs plus enclins à la recommandation sociale • Quelle est la nature exacte de la corrélation entre les intérêts utilisateurs et les relations sociales ?

Quel impact sur les recommandations ? • Recommandation considérant les relations sociales négatives

o Recommandation pour un groupe • Etude de la structure/dynamique d’un groupe pour la recommandation (qui est le chef ? qui est

influençable ? comment se propage l’information ?)

o Recommandations interactives • Profilage interactif de l’utilisateur par des questions/propositions explicites

o Profilage plus précis par analyse textuelle o Intégration des interactions textuelles, analyse de sentiments o Acquisition et intégration des tendances relatives aux habitudes

o Méthodes à apprentissage profond, deep learning o Formalisation des conditions d’évaluation des systèmes de

recommandation selon les caractéristiques du jeu de données et les objectifs de recommandation

o Recommandation combinatoire (cf. ma thèse) o Est-ce que les recommandations fournies par mon modèle tendent à

uniformiser les profils des utilisateurs ? Quelle est sa convergence ? o Plus généralement : systèmes de recommandation sensibles au temps

(TARS) et sensibles au contexte (CARS)



Conclusion



Conclusion

o Un système de recommandation demande un(e): • Analyse/modélisation des interactions, comportements

• Analyse/profilage des utilisateurs, items

• Méthode/algorithme de recommandation basé sur ces analyses/modèles et dépendante des contraintes, objectifs de recommandation

• Méthode d’évaluation détaillée, comparaison avec d’autres méthodes dans les mêmes conditions

o De nombreuses pistes à développer dans le domaine


Technology

Les systèmes de recommandations