|Home|
<<Prev<<
<-Back--
Web mining : moteur de recommandations
1. Introduction
Pour aider les clients des sites de vente en ligne (et pour aider les ventes
de ces sites), beaucoup de marchands ont recours à ce qu'on appelle des
moteurs de recommandations. Ce sont des programmes qui analysent les achats des
clients (selon plusieurs paramètres -- moment de l'achat, état
(juste dans le chariot, juste regardé), etc.) et leur éventuelles
recommandations et qui essaient ensuite de proposer, de manière
pertinente, des choix supplémentaires pour d'autres achats.
Nous allons dans ce TP nous pencher sur quelques uns des algorithmes ainsi mis
en oeuvre, travaillant bien entendu sur leur implémentation, d'un point
de vue donc d'un site marchand qui vend des livres, cds, appareils
électroniques, etc., sur lequel les utilisateurs s'enregistrent et donc
qui peut garder la trace de leurs visites et achats.
2. Structures de données
Nous devons représenter les utilisateurs, les objets (livres, cds,
appareils, etc.) ainsi que les historiques d'achat et visite de site par les
utilisateurs. Pour faire simple, nous allons faire ceci à l'aide de
quelques fichiers texte :
recData/userList.txt
recData/itemList.txt
recData/data/user_0_ItemData.txt
recData/data/user_1_ItemData.txt
...
2.1 Numéros d'identification
Chaque utilisateur a un numéro d'identification (son rang dans le
fichier userList.txt), et chaque item en a un également (son
rang dans le fichier itemList.txt). Ainsi les implémentations
des algorithmes peuvent simplement manipuler ces numéros (en tant
qu'indices dans des tablaux, en tant que numéros de lignes, de colonnes,
etc.). Lors de la communication avec nous, on affichera par contre les
libellées correspondants.
2.2 Historique du parcours
Les fichiers comme recData/data/user_0_ItemData.txt contiennent
l'historique pour l'utilisateur dont le id est dans le nom du fichier, une
ligne par item :
0 2 ACHETE 24
5 5 ACHETE 2
6 1 CHARIOT 1
La première colonne contient l'id de l'item, la seconde colonne la note
d'appréciation (rating) que l'utilisateur a donné à cet
item, ensuite l'état, et enfin une donnée numérique qui
indique le temps (depuis quand il a été achété,
en jours, ou depuis quand il est dans le chariot, etc.). Nous allons
principalement utiliser les renseignements des deux premières colonnes.
On limite la note à un nombre entre 1 et 5.
3. Algorithmes
Le but du jeu est, lorsqu'on appelle une fonction recommendItems()
pour un utilisateur donné, de pouvoir suggérer intelligemment
quelques items parmi ceux que l'utilisateur n'a pas encore notés, mais
qui pourraient intéresser l'utilisateur en question. Il y a plusieurs
approches pour faire ceci ; une d'entre elles s'appelle en
anglais Collaborative filtering, et c'est celle que nous allons
étudier.
3.1 Idée
Les idées soujacentes sont du type "si mes amis aiment quelque chose, il
y a une chance que je l'aime aussi", et "plus je suis amis avec quelqu'un, plus il
y a des chances que j'aime autant que lui les mêmes choses". Le but sera
d'avoir quelqu'un qui "observe le groupe d'amis" et qui peut ensuite
prédire combien quelqu'un peut aimer une chose nouvelle pour lui, mais
déjà connue par certains de ses amis.
Être amis ici peut se traduire par avoir
une certaine similarité entre deux utilisateurs. Aimer, ce sera donner une
certaine note. Donc pour un utilisateur U donné, et pour un
item I que U n'a pas encore noté, on peut
récupérer les notes des autres
utilisateurs Vk, mais en pondérant chacune par la
similarité |Vk,U|, et en faire la somme (qu'on
divise par la somme des |Vk,U|):
prediction(U,I) = (somme (note(Vk,I) * |Vk,U|)) / (somme |Vk,U|)
Pour recommander alors des items, on les prend tous un par un, on leur calcule
cette note potentielle, on les trie dans l'ordre décroissant de la note
potentielle et on en rend autant que demandé.
On appellera cette idée la recommandation basée sur l'utilisateur.
3.2 Autre idée
Si j'aime plein d'objets et qu'il en existe des objets "similaires" (que je
ne connais pas), il y a une chance que je les aime aussi, quand je les
découvrirai.
Ici la partie plus délicate est celle qui décide combien deux
items sont similaires, mais ensuite, la formulation et la démarche sont
semblables:
prediction(U,I) = (somme (note(U,Jk) * |Jk,I|)) / (somme |Jk,I|)
On appellera cette idée la recommandation basée sur l'item.
3.3. Similarités
Pour nos implémentation d'algorithmes, on utilisera le coefficient
de Jaccard ainsi que la distance du cosinus. Pour calculer cette
dernière, les vecteurs représenteront bien entendu soit les
notes des utilisateuers pour un item donné (pour le 3.2), soit les notes
d'un utilisateur pour tous les items (pour le 3.1).
Pour le coefficient de Jaccard (cardinalité de l'intersection
divisée par celle de l'union), concrètement, on utilisera une petite
structure matricielle auxiliaire de cinq lignes et colonnes (car les notes sont
limitées entre 1 et 5), qui
- pour une paire d'utilisateurs (pour le 3.1), compte, parmi tous les items
qui ont une note de la part de chacun des utilisateurs, le nombre de chaque
paire de notes possibles.
- pour une paire d'items (pour le 3.2), compte, parmi tous les utilisateurs
qui ont noté les deux items, le nombre de chaque
paire de notes possibles.
3.4 Exemples
Considérons deux utilisateurs U et V qui ont
donné les notes suivantes aux douze items disponibles :
U = (0,2,1,2,0,1,0,3,2,1,0,1)
V = (1,2,3,1,0,1,4,2,2,1,2,1)
Autrement dit, note(U,0) = 0, note(U,1) = 2, note(U,2) =
1, etc., note(V,8) = 2. Les items vont de zéro à
11.
Travail à faire
- Comptez les paires d'items notés par les deux utilisateurs, et finissez
de remplir ainsi la matrice qui vous donne l'appariement des notes (les notes de U donneront
les lignes)
note V
/ 3 0 1 0 0 \
note U | 1 . . . . |
| 0 . . . . |
| 0 . . . . |
\ 0 . . . . /
Ici la ligne 1 est déjà remplie, et elle dit qu'il y a trois items
que les deux utilisateurs ont noté avec 1 tous le deux (les items
5,9,11 en numérotations de 0 à 11) et
également un item noté avec 1 par U et 3 par V. De même, la
colonne 1 dit qu'il y a un seul item que les deux utilisateurs ont noté
avec 1 tous le deux (le même dont on a déjà parlé
pour la ligne 1), ainsi qu'un seul item noté avec 2 par U et 1 par V.
- Calculez maintenant la similarité de Jaccard entre U
et V, en divisant la somme des coefficients de la diagonale par la
somme de tous les coefficients.
- Calculez enfin la similarité du cosinus (calculez d'abord les normes
des deux vecteurs -- racine carré de la somme des carrées des
notes --, et ensuite le produit scalaire -- la somme des produits des notes
de U respectivement V pour chaque item).
- Oublions maintenant l'utilisateur V, et considérons
dorénavant les utilisateurs suivants tous ayant
noté l'item d'id 6 (que U n'a pas noté -- il a un zéro)
note(V1,6) = 1
note(V2,6) = 2
note(V3,6) = 3
note(V4,6) = 4
Enfin, considérons que les similarités avec U sont les suivantes:
Avec les valeurs d'avant, on a donc également
|V1,U| = 2
|V2,U| = 0.5
|V3,U| = 1
|V4,U| = 0.25
Calculez alors avec ces valeurs combien vaut prediction(U,6) selon la formule du 3.1.
4. Classes et outils disponibles et nécessaires pour notre travail
Marche à suivre
L'archive avec le fichier source et les données se
trouve ici, t&aecute;l&aecute;chargez-la
et installez-la dans un sous-r&aecute;pertoire d&aecute;di&aecute; à ce
TP. Vous pouvez essayer de compiler (avec un simple make), le tout
doit pouvoir compiler, mais ne fera encore rien d'utile.
Vous allez donc devoir compléter le code source du
fichier SimpleRecommender.java, en faisant les exercices dans
l'ordre. Après chaque groupe de deux ou trois exercices vous allez
pouvoir recompiler (toujours avec un simple make), et puis essayer de
faire tourner le programme.
Éléments essentiels
La donnée-membre userItemDataList est une liste avec un
élément par utilisateur (c'est donc l'id de l'utilisateur qui
permet d'en retrouver l'"élément"). Cet élément en
question est en fait l'historique de cet utilisateur, donc une table de hachage
avec comme clé les ids des items, et comme valeurs,
des UserItemData. Cette dernière structure de données
représente l'information de chaque ligne de fichiers comme
recData/data/user_0_ItemData.txt: par exemple, la
donnée-membre rating donne la note de l'utilisateur en question
pour l'item en question.
La classe RatingCount est celle qui s'occupe de la structure
matricielle auxiliaire (attention au fait que les indices dans la matrice
vont de 0 à 4, donc sont la note moins un).
4.1 Exercice
Pour calculer la similarité Jaccard il nous faut la cardinalitué
de l'union, fournie par la méthode RatingCount.getTotalCount(),
et également celle de l'intersection, fournie par la méthode
RatingCount.getDiagCount(), qui calcule la somme sur la diagonale
(c'est-à-dire combien de paires de notes identiques).
Travail à faire
Écrire le corps de la
méthode RatingCount.getDiagCount(). Regardez comment est
écrite la méthode RatingCount.getTotalCount() pour vous
en inspirer.
On peut compiler, mais on ne peut pas encore tester.
4.2 Exercice
On doit encore écrire un peu de code et puis on pourra commencer
à tester le programme. Si on regarde le code à partir
du main(), pour une exécution avec arguments sur la ligne de
commande par exemple
Jaccard rec Andrew userCoFilt
on suit les appels et on voit que le main()
appelle recommendItems(), laquelle
appelle predictRating(). De même, juste avant,
le main() appelle bien entendu le
constructeur SimpleRecommender, qui lit tous les fichiers de notre
répositoire recData et qui apelle entre
autres computeUserSimilarity().
Travail à faire
Compléter le case JACCARD de la
méthode computeUserSimilarity()
// pour chaque utilisateur id U (entiers de 0 à nTotUsers (excluant nTotUsers))
///// pour chaque utilisateur id V (pareil)
////////// en instancier un RatingCount avec ObjType . USER
////////// en obtenir le compte total
////////// s'il est strictement positif
/////////////// obtenir également le compte diagonal
/////////////// mettre leur quotient dans l'élément userSimilarity[U][V]
////////// sinon mettre un zéro dans cet 'élément de la matrice de similaritélé
///// fin boucle pour
// fin boucle pour
Maintenant compilez et testez le programme avec
java -jar recomm.jar recData Jaccard rec Andrew userCoFilt
4.3 Exercice
Comme tout est maintenant en place pour la structure générale de
la recommandation basée sur l'utilisateur, on finit maintenant
complètement la même méthode computeUserSimilarity()
Travail à faire
Compléter le case COSINE de la
méthode computeUserSimilarity(). Attention pour la norme du
vecteur, il faudra bien utiliser la méthode
computeItemVectNorm(), qui prend bien un id d'utilisateur comme
argument. De même, avant de commencer, étudiez le code de la
méthode printUserItemData() (et gardez-la sous les yeux pendant
ce travail) pour savoir comment extraire tous les renseignements
nécessaires (vous pouvez refaire tourner le programme, pour avoir
à l'écrant le résultat de l'appel de cette méthode,
qui est déjà fait pour vous dans le constructeur).
// pour chaque utilisateur a
////// pour chaque utilisateur id b
////////// se prendre le double dotProd egal a zero
////////// récupérer la norme du vecteur d'item pour a (méthode computeItemVectNorm(a))
////////// récupérer la norme du vecteur d'item pour b
////////// récupérer les items de a (comme au début de printUserItemData()) -- appelons-le aItems
////////// récupérer les items de b (comme au début de printUserItemData()) -- appelons-le bItems
////////// obtenir l'Iterator pour pouvoir parcourir aItems (comme au début de printUserItemData())
////////////// pour chaque élément de aItems (à l'aide de l'itérateur)
///////////////// obtenir la paire (comme dans printUserItemData()) -- appelons-la 'pair'
///////////////// faites final int item = (Integer)pair . getKey(); pour obtenir l'item id
///////////////// si bItems contient cet item (méthode containsKey())
//////////////////// obtenir les ratings ainsi:
final int aRating = ((UserItemData)pair . getValue()) . rating;
final int bRating = ((UserItemData)bItems . get(item)) . rating;
//////////////////// s'ils sont strictement positifs, ajouter leur produit a 'dotProd'
///////////////// finsi
////////////// fin boucle pour
////////////// si les deux normes (obtenues initialement) sont strictement positives
/////////////////// mettre dans userSimilarity[a][b] le quotient de 'dotProd' par leur produit
////////////// sinon y mettre zéro
////// fin boucle pour
// fin boucle pour
Maintenant vous pouvez recompiler et retester, avec
java -jar recomm.jar recData cosine rec Andrew userCoFilt
4.4 Exercice
Nous allons maintenant passer aux recommandations basées sur les items. Tout d'abord on s'occupera
de la classe auxiliaire RatingCount.
Travail à faire
Compléter le case ITEM du constructeur de la classe RatingCount. Faites attention, ce constructeur
prend deux entiers en arguments, qui sont des ids. En fonction de la tâche qu'on lui donne (i.e. l'ObjType),
ces ids sont des ids d'utilisateur ou bien d'items. Dans notre cas, ils seront des ids d'items, donc le 'a'
et le 'b' de cette portion de code, dans notre case ITEM, représenten bien des item id. De même,
regardez attentivement comment est écrit le case USER du même switch(), pour vous
servir des éléments que vous y trouverez.
// pour chaque utilisateur
////// obtenir ses items (maintenant on sait comment -- comme dans printUserItemData() et comme on l'a fait plus haut)
////// si a et b sont parmi ses items (méthode containsKey() pour chacun)
/////////// obtenir leur notes (comme on l'a fait avant pour le cosinus)
/////////// si ces notes sont strictement positives,
///////////////// rajouter un à l'entrée correspondante dans 'm' (attention il faut faire -1 pour les indices)
On peut compiler, mais on ne peut pas encore tester.
4.5 Exercice
Maintenant il faut compléter le calcul du coefficient de Jaccard pour la similarité entre items. Encore un
exercice ensuite et on pourra tester.
Travail à faire
Compléter le case JACCARD de la méthode computeItemSimilarity() en regardant attentivement
comment est écrit le case JACCARD de la méthode computeUserSimilarity(). Tout est semblable.
On peut commencer par simplement copier le code, et puis par remplacer les utilisations d'user id avec des item id (et bien
entendu, la matrice qu'on rempli est itemSimilarity).
4.6 Exercice
Maintenant on n'a plus qu'à faire le calcul de la prédiction de note.
Travail à faire
Compléter le case ITEM_COFILT de la méthode predictRating(), en relisant le partie 3.2 et
en regardant comment est écrit le case USER_COFILT de la même méthode predictRating()
(ainsi que le 3.1 qui contient les explications de la formule pour USER_COFILT).
//// obtenir les items de 'user' (paramètre de la méthode)
//// pour chaque item id possible
//////// passer à l'itération suivante s'il s'agit de la valeur d' 'item' (paramètre de la méthode)
//////// passer à l'itération suivante s'il n'est pas noté par cet user (utiliser containsKey())
//////// en obtenir la note
//////// obtenir la similarité avec 'item' (matrice itemSimilarity)
//////// mettre à jour les sommes comme dans USER_COFILT
//// finir comme dans USER_COFILT
On peut maintenant compiler et tester avec
java -jar recomm.jar recData Jaccard rec Andrew itemCoFilt
4.7 Exercice
On va compléter le code pour pouvoir utiliser également la similarité du cosinus pour la recommandation
basée sur les items. Avant de faire effectivement cela, il nous faut pouvoir calculer les normes des vecteurs.
Travail à faire
Écrire la méthode computeUserVectNorm() qui prend un item id comme argument.
// pour chaque user id possible
///// obtenir ses items -- appelons-les uItems
///// si uItems contient i (containsKey())
////////// obtenir la note et rajouter son carré (produit avec elle-même) à 'theNorm'
// finir comme pour computeItemVectNorm()
Vous pouvez compiler, mais pas encore tester.
4.8 Exercice
Nous allons enfin terminer avec ce dernier exercice, en complétant la partie calcul de similarité
Travail à faire
Compléter le case COSINE de la méthode computeItemSimilarity(), en vous inspirant du
case COSINE de la méthode computeUserSimilarity() (et en vous souvenant comment vous avez
fait l'exercice 4.5).
Ensuite, compilez et testez
java -jar recomm.jar recData cosine rec Andrew itemCoFilt