TPMovie (Projet)

étudiants M2ILC
FRIGUI Rassil
LANSELLE Maurice

Question 1) Aperçu des données

  • On s'intéresse maintenant aux données D1. Lire le README et comprendre la structure des fichiers plats movies.dat, users.dat et ratings.dat
    • a) Quel est le nombre moyen de notes par utilisateur ?
    • b) En moyenne quel est le pourcentage de films notés par un utilisateur ?

Réponses

Question 1, a : 1000209 ratings / 6040 users = 165.59 ratings/user Question 1, b : 165.59 ratings / 3900 filmes =4.25% des filmes notés par utilisateur moyen

Question 2) Analyse des données

  • Proposer une solution pour calculer les histogrammes de distribution suivants:
    1. H1: le nombre de notes par film
    2. H2: le nombre de notes par mois, sur toute la période pour laquelle on dispose de notes.
    3. H3: le nombre de notes par tranche d'age (il y a 7 tranches d'age)
    4. H4: le nombre d'utilisateurs par note (une note allant de 1 à 5)
    5. H5: le nombre de notes par utilisateurs
  • Implémenter H2 en java. Le résultat doit être textuel. Chaque ligne du résultat contient 2 valeurs séparées par un espace.

Réponses

  • H1: le nombre de notes par film
    • créer une liste H1(movieId,compteur) à partir de movies, avec compteur initialisé à 0.
    • parcourir ratings.dat
    • lire movieId dans chaque ligne lu
    • incrémenter compteur dans H1(movieId,compteur)
  • H2: le nombre de notes par mois, sur toute la période pour laquelle on dispose de notes.
    • creer une liste (year-month, count) de 2000-01 à aujourd'hui
    • parcourir ratings.dat
    • lire timestamp dans chaque ligne lu
    • convertir timestanm en nombre de mois depuis 2000-01
    • incrémenter compteur du mois-année correspondant au timestamp
  • H3: le nombre de notes par tranche d'age (il y a 7 tranches d'age)
    • lire ratings et accumuler nombre de rating par userId dans utilisateur-ratings ⇒ H5
    • lire utilisateur-ratings
    • pour chaque utilisateur dans utilisateur-ratings,
    • lire age du userId dans users
    • incrementer (age,count)
  • H4: le nombre d'utilisateurs par note (une note allant de 1 à 5)
    • créer une liste H4(userID, rating1, rating2, rating3, rating4, rating5) à partir de users, avec les ratings initialisés à 0.
    • parcourir ratings.dat
    • lire userID et rating dans ratings
    • dans H4(userID, 1,2,3,4,5) Marquer par 1 le rating effectué par le user
    • construire une liste (count) dont les indices sont les différents ratings (1–>5)
    • pour chaque ligne de H4 incrémenter les counter par H4[ratingX]
  • H5: le nombre de notes par utilisateurs
    • lire ratings et accumuler nombre de rating par userId dans liste (userId, count)

Vous trouverez ci-joint la classe main de notre code Java.

Question 3) Similarité entre les utilisateurs

On veut compléter les données avec la similarité entre utilisateurs. Pour chaque utilisateur, on veut connaitre les 100 utilisateurs les plus similaires. La similarité entre deux utilisateurs U1 et U2 est :

  • Sim(U1,U2) = (nombre de films distincts notés par U1 et U2) / (nombre de films distincts notés par U1 ou U2)
    • a) Implémenter la fonction Sim en java.
      • Solution : ajouter leurs filmes à un hashtree, dont le size() représentera la union et un compteur de collisions donnera la cardinalité de l'intersection.
    • b) Proposer, en java, un algorithme pour calculer et stocker Sim pour tous les utilisateurs.
      • Solution :
        • parcours des utilisateurs, on compare chaque user avec ses successeurs
        • on stock les résultats dans un fichier
    • c) facultatif. Prendre en compte, dans le calcul de la similarité, la valeur de la note attribuée à un film par U1 et U2. Pour calculer le numérateur, on se restreint aux films distincts notés par U1 ET U2 tels que la valeur absolue de la différence entre les 2 notes soit inférieure ou égale à 2. Par exemple, si U1 et U2 ont noté le même film F, mais que U1 a mis une note=5 et U2 a mis une note=1, alors on ignore F. non inclus dans notre fonction.

Question 4) Calcul d'une recommandation

On veut définir une formule top5(u, d) pour recommander 5 films à un utilisateur u à une date d donnée.

  • On prend en compte les notes déjà attribuées (avant la date d) par les 100 utilisateurs les plus similaires à u. Pour simplifier, on suppose que la similarité entre deux utilisateurs est fixe et indépendante de d.
  • Proposer une formule pour affecter un score à un film déjà noté par des utilisateurs similaires, mais pas encore noté par U.
  • Implémenter la fonction top5 en java.

Réponses

On veut recommander 5 films pour UserID avant la date timestamp

  • On prend les 100 users les plus similaires à userID
  • On les divise en 4 groupes de 25, pour chaque groupe en attribue un coef, le premier groupe de 25 a le coef le plus fort.
  • On récupère les 5 meilleurs filmes de chaque user dans les 100 similaires, avant d et que User n'a pas vu
  • Pour chaque filme récupéré on lui attribut un score temporaire égal à son rating par le user qui l'a noté * coef du groupe de ce user.

Exemple :

Film1 User1 Rating1 Coef1 => R1*C1
Film1 User2 Rating2 Coef2 => R2*C2
  • On récupère donc une liste de 500 filmes résultat, on les parcours à nouveau pour calculer le score final par filme, on faisant la somme des scores temporaires par filme

Exemple :

Filme1 => R1*C1 + R2*C2
  • Dans la liste finale dans un TreeSet (trié) on ne récupère que les 5 premiers filmes qui sont le résultat du Top5.

Remarques : On attribuant des coefficients aux groupes d'utilisateurs, on favorise les filmes notés par les utilisateurs les plus similaires à notre utilisateur « client ». Il ne faut surtout pas diviser la somme des scores par filme pour retrouver une moyenne de notes par filme tout simplement car l'objectif des coefficients est de créer un trou entre les scores des filmes notés par chaque groupe d'utilisateurs.

Exemple :

UserID Groupe Filme Rating
U1 G1 (C=3) F1 2 => 6
U2 G1 (C=3) F1 2 => 6
U3 G2 (C=1) F1 3 => 3
U4 G2 (C=1) F1 5 => 5
U5 G2 (C=1) F1 4 => 4
U1 G1 (C=3) F2 4 => 12
U2 G1 (C=3) F2 4 => 12
U3 G2 (C=1) F2 2 => 2
U4 G2 (C=1) F2 2 => 2
U5 G2 (C=1) F2 2 => 2

on obtient :

F1 = 24
F2 = 30

Alors qu'un calcul par moyenne aurait mis en avant F1 qui n'est pas un filme préféré par les plus similaires, au contraire on a créer un « Gap » entre les deux notes pour mettre en avant les filmes notés par G1 et handicapé les filmes mal noté par ce groupe.

Question 5) Stockage des données avec AWS

On s'intéresse au stockage réparti des données. L'objectif est d'accélérer le calcul des similarités et des recommandations en répartissant le calcul sur N machines.
  • Proposer une fragmentation horizontale des données pour les utilisateurs et les notes. Les films sont-ils fragmentés ? si oui décrire leur fragmentation , sinon expliquer pourquoi.
  • Proposer une fragmentation des données pour les stocker dans S3. Préciser le nombre de buckets et leur contenu. Préciser ce que représente un objet.
  • Proposer une fragmentation des données pour les stocker dans SimpleDB. Préciser le nombre de domaines et quels sont les attributs des objets stockés.
  • Implémenter le chargement des données dans SimpleDB.

Réponses

Fragmentation horizontale des données

La fragmentation horizontale des données permettrait de répartir les données à utilisations indépendantes, et à répartir des données à fort volume sur plusieurs machines. Dans le contexte de nos fichiers, les utilisations indépendantes ne sont pas évidentes, car les utilisateurs peuvent avoir besoin de tous les autres utilisateurs et tous les filmes. La seule motivation est de répartir les Ratings.

  • notes : aligner avec fragmentation des utilisateurs, plus timestamp. Facilite des calculs par période mobile, juste sur une ou deux années (2007-2010, par exemple).
  • variante : fragmenter par Rating (en plus de l'alignement avec les utilisateurs).
  • utilisateurs : C'est très arbitraire. Des possibilités sont, par exemple
  • tranche d'âge : pour avoir des groupes homogènes, possibilité de recommander des filmes par tranche d'age.
  • compteurs (blocs de 200k par exemple) : on n'a pas de raison hormis la répartition, on va comparer tout le monde avec tout le monde.
  • sexe : comme tranche d'age, mais plus grands blocs.
  • filmes : il est possible de faire une fragmentation par date d'introduction à la base (supposant que les plus anciens seront les moins consultés). Cependant, tous les filmes peuvent figurer dans les notes de tous les blocs d'utilisateurs et devront être consultes par tous les fragments d'utilisateurs (autant stocker le ficher entier partout).

Fragmentation pour S3

La fragmentation pour S3 vise à stocker des objets dans des buckets pour accès sans la necéssité (ni la possibilité) de faire des recherches par attributs. Ainsi, il faudrait soit stocker des objets de type enregistrement et stocker des pointeurs vers ces objets et des clés de recherche dans SimpleDB, soit stocker des tables complètes. C'est ce deuxième choix retenu, avec juste une fragmentation horizontale de Notes pour réduire la taille de l'objet contenant les notes les plus récentes :

  • utilisateurs :
    • garder tous les utilisateurs dans un seul fichier puisqu'on a besoin de tous les utilisateurs pour calculer la similarité
  • notes :
    • fragmentés horizontalement sur le timestamp et la date d'introduction des filmes dans la base
  • filmes :
    • fragmentés horizontalement sur la date d'introduction dans la base
  • Le nombre de buckets qu'on pourrait utiliser est de 2
    • Récents : utilisateurs + filmes récents + Notes des filmes récents
    • Archive : filmes archivés + notes des filmes archivés
  • Un objet représentera un fichier fragment + les métadonnées relatives

Fragmentation des données pour les stocker dans SimpleDB

Un fragmentation des users est envisageable, mais ne présente pas d'avantages évidents. Cependant, on pourrait en réaliser une pour répartir la charge des notes associées sur plusieurs machines. Un domaine de notes par jour pourrait être intéressant, mais SimpleDB ne permet pas de disposer d'autant. Parmi d'autres manières de fragmenter Ratings, la fragmentation par Rating peut avoir un intérêt pour rendre plus efficaces des traitements visant les filmes bien notées. Ceci permet aussi un stockage plus compacte dans la mesure où la valeur de la note n'est pas stockée dans le domaine mais connue par le nom du domaine :

  • total : 7 (ou 8) domaines, auquels il faudra rajouter des domaines pour le stockage persistant de résultats :
    • 1 Pour utilisateurs,
    • 1 pour filmes,
    • 5 pour notes (cf. tableaux en Question 6) : NotesParUtilisateur_Rn : où les objets (items) sont les utilisateurs et les attributs sont movie-timestamp, un domain par Rating (1-5) qui prend la place de n dans le nom du domaine.

Question 6) Calcul pro-actif du top5.

On considère le système de recommandation suivant. Un utilisateur demande une liste de 5 films (top5) au système. Le système répond en envoyant le résultat du top5. L'utilisateur choisit un film parmi le top5, le regarde et le note. Puis, l'utilisateur envoie sa note au système.

Afin de minimiser le temps de réponse lorsqu'un utilisateur demande qu'une recommandation (top5) lui soit fournie, on veut pré-calculer le top5 de chaque utilisateur dès qu'une nouvelle note est arrive dans le système. Autrement dit, l'arrivé d'une nouvelle note envoyé par l'utilisateur U déclenche le calcul du top5 pour tous les utilisateurs V tels que U soit parmi les 100 utilisateurs les plus similaires à V. Pour simplifier, on suppose que la similarité entre deux utilisateurs est fixe, on n'actualise pas la similarité lorsque une nouvelle note arrive.

  • a) Proposer une structure de données adéquate pour contenir toutes les données nécessaires au calcul du top5. Expliquer sous quelle forme cette structure peut être stocker dans SimpleDB.
  • b) On suppose que les utilisateurs (et leurs demandes) sont répartis en nombre égal sur N machines. Expliquer comment s'effectue le calcul du top5.
  • c) A faire avant le 10 mai. Implémenter le calcul réparti des top5.

a) Structure SimpleDB Pour Top5

Il y a trois aspects à prendre en compte, l'initialisation, la mise à jour, et la répartition des données sur plusieurs machines.

  • Pour calculer une liste Top5 initiale, on a besoin de
    • la liste des CentSimilaires (évidement)
    • la liste des filmes candidats figurant parmi les filmes les mieux notés par les CentSimilaires de chaque user, avec les notes par filme, par date (initialement, mais peut être pas après) par user dans la liste des CentSimilaires.
    • des informations sur les affinités entre chacun des CentSimilaires pour pondérer l'agrégation des notes
    • la liste des filmes déjà notés par l'utilisateur (afin de les exclure) si ce n'est pas assuré par la requête des filmes candidats

La solution étudiée suppose que la liste des CentSimilaires est stocké, car il est indiqué que la liste change rarement. Cette liste peut contenir l'identifiant de chaque Similaire et plusieurs statistiques concernant des mesures de similarité. La gestion de la liste des filmes candidats, filmes qu'un Similaire a bien noté et que l'User n'a pas noté, peut être stockée et mise à jour par des pushes lorsque le Similaire note un nouveau filme mieux, ou demandée seulement lorsqu'on recalcule un Top5; la première alternative est choisie ici pour favoriser la rapidité de la mise à jour des Top5.

  • Pour la mise à jour de la liste Top5, les procédures doivent
    1. enlever des listes Top5 (et candidats notés par ses similaires) les filmes au fur et à mesure que l'utilisateur les note. Ces listes servent au calcul de son Top5 et la présence de filmes déjà notés parmi les candidats fausse le résultat.
      1. si le système de calcul de Top5 suppose un nombre fixe de candidats par Similaire, demander au Similaire une nouvelle liste de la bonne longueur après la suppression.
    2. remplacer le filme noté dans Top5 le cas echéant.
    3. ajuster les indicateurs de pertinence des CentSimilaires qui l'avaient noté en fonction de la concordance ou pas des notes, éventuellement.
  1. ajouter les filmes notés par les CentSimilaires au fur et à mesure de la saisie des notes
    1. ne pas les ajouter si déjà vus, mais ajuster les indicateurs de pertinence du CentSimilaires qui l'a noté en fonction de la concordance ou pas des notes, éventuellement.

Cela suggère

  • un domaine CentSimilaires où sont listés
    • pour chaque UserID (item)
      • dates bornes pour les ratings prise en compte pour calculer la similarité (à enlever ou ignorer après la phase de mise ne place?): à partir de et pas après
      • pour chacun des CentSimilaires (qui sont des attributs) : l'UserID sert de clef, la valeur est la liste des statistiques de similarité.
  • un ou des domaines pour stocker les filmes et ratings des filmes candidats. Cette liste est fonction du client, car il ne doit contenir que des filmes que le Similaire a bien noté mais que User n'a pas noté. Il y aura plusieurs de ces domaine, pour que le domaine signale la note par son nom et non par des attributs.
    • pour chaque UserID (item)
      • pour chacun des CentSimilaires (qui sont des attributs) : l'UserID sert de clef, la valeur est la liste des filmes qu'il a bien noté.
  • Pour construire les listes des CentSimilaires, il faudrait une requête à envoyer aux autres machines avec un UserId et sa liste de MovieIDs (pour calculer les similarités), avec en retour UserID et les CentSimilaires de chaque machine, puis tri et synthèse à faire avec les retours.
  • un domaine fans sur chaque machine avec la liste de diffusion des notes pour chaque utilisateur “local”.
    • Cette liste est à établir de la manière suivante : lorsqu'on place un utilisateur dans une liste CentSimilaires, on ajoute en fan le propriétaire de la liste CentSimilaires : un abonnement.

Sur chaque machine, on aura :

  1. la liste movies en entier : MovieID→[Title, Genre]
  2. une partie –critère de fragmentation à définir, peut être zip-code, age, sexe, etc. – de users : UserID, Name, Occupation, Age, Sex, Zip-code, plus pointeurs sur ses CentSimilaires (Similitude, FilmesNotés1, FilmesNotés2,…,FilmesNotés5)
  3. la partie de ratingsUserID est dans le fragment local : serial→UserID, MovieID, Rating, Timestamp (ou Jour?). Cette liste est utilisée pour produire
    1. une liste par jour de ratings par UserID pour pouvoir fournir les ratings d'un utilisateur dans un intervalle de dates donnée : UserID→[MovieID, Rating]
    2. ceci n'étant pas possible (nombre limité de domains), on devra se contenter d'un domain principal pour les Ratings avec un bloc (item) par UserID, avec attributs ayant MovieID pour clef et le couple Rating, Timestamp pour valeur. Alternativement, on pourrait –comme pour les CentSimilaires – en faire cinq : un par rating, avec (toujours) item=UserID, MovieID→Timestamp pour attributs.
  4. une liste fans pour les UserID dans le fragment local : UserID→UserID[]
  5. une liste Top5 locale : UserID →[liste de 5 MovieID→Rating]

Les données en entrée seront organisées de la manière suivante :

Domain Items Attribut
NotesUserParJourEtParFilm User couples MovieID::(Rating, DayCode)
Users UserID couples avec clés (
Gender,
Age,
Occupation,
Zip-code)
Movies MovieID couples avec clés (
Title,
Genre)
Notes ? couples avec clés (
UserID,
MovieID,
Rating,
Timestamp)
Alternative (pour Ratings)
Domain Items Attribut
NotesUserParJourEtParFilm_R1 User MovieID → Timestamp
NotesUserParJourEtParFilm_R2 User MovieID → Timestamp
NotesUserParJourEtParFilm_R3 User MovieID → Timestamp
NotesUserParJourEtParFilm_R4 User MovieID → Timestamp
NotesUserParJourEtParFilm_R5 User MovieID → Timestamp

Compte tenu de la limite du nombre de domains qu'une application peut utiliser, on ne peut pas avoir un domain par UserID pour les CentSimilaires. Il faudra compenser en répartissant les informations CentSimilaires en six domaines: un pour Similarité, un par Rating pour listes des Movies. Ainsi, on pourra rapidement savoir quels filmes un Similaire a noté en 1, 2, 3, 4 ou 5, sans mélanger MovieID et Rating dans les listes de valeurs d'un attribut.

Les données produites seront organisées ainsi :

Domain Items Attributs
Fans User [fans] → [liste des UserID des fans]
Top5 User Rang :: Movie-ID
CentSimilairesSimilarité UserID UserID(d'un similaire) → Similarité )
CentSimilairesFilmes_R1 UserID UserID(d'un similaire) → [MovieID_1, … ,MovieID_k1]
CentSimilairesFilmes_R2 UserID UserID(d'un similaire) → [MovieID_1, … ,MovieID_k2]
CentSimilairesFilmes_R3 UserID UserID(d'un similaire) → [MovieID_1, … ,MovieID_k3]
CentSimilairesFilmes_R4 UserID UserID(d'un similaire) → [MovieID_1, … ,MovieID_k4]
CentSimilairesFilmes_R5 UserID UserID(d'un similaire) → [MovieID_1, … ,MovieID_k5]

b) Propagation des Calculs de Mise à Jour Top5

Les utilisateurs envoient leurs demandes de top 5 dans la FileTop5, le système récupère les demandes une par une et suivant le ID de l'utilisateur, envoie la requête au serveur qui héberge ce user (on suppose qu'on a un indexe sur le serveur frontal), le serveur hébergeur récupère directement la liste Top5 en se basant sur le ID de l'utilisateur ayant initier la demande et la lui renvoie.

Les utilisateurs envoient leurs demandes de notation d'un filme, le système récupère les demandes une par une et les transmets au serveur hébergeur de l'utilisateur qui a initié la requête, ce dernier :

  • enlever le filme des listes de filmes candidats de ses CentSimilaires
  • enlever le filme et recalculer son Top5, s'il s'agit d'un de ces filmes
  • diffuser le rating (UserID, MovieID, Rating, Timestamp) à l'attention de tous les UserID dans sa liste de fans.

Lorsqu'un serveur reçoit un rating pour un fan qu'il héberge, il doit,

  • si l'UserID destinataire (le fan) n'a pas déjà noté le filme,
    • ajouter le MovieID dans la liste des Movies pour UserID (expéditeur) dans le bloc du UserID du fan du domaine correspondand au Rating donnée.
    • recalculer le Top5 de l'UserID du fan (destinataire).
    • informer le fan ?
  • ajuster les indicateurs de pertinence des CentSimilaires qui l'avaient noté en fonction de la concordance ou pas des notes, éventuellement.

N. B.

On peut aussi envisager une requête similaire pour recenser les “Semblables” sur d'autres serveurs lorsqu'on a un nouvel utilisateur :

  • envoyer (N=100, UserID, MovieID's) pour demander la liste des N Users hébergés sur chaque machine
  • recevoir les retours (UserID, date_debut=0, date_fin=999999, liste[(UserID, IntersectionCount, UnionCount)])
  • fusionner les retours pour constituer les CentSimilaires pour UserID.
  • Lorsqu'il reçoit une telle requête, il calcule les N utilisateurs et les renvoye.

c) Implémentation

 
m2ilc/fouille_dist_tp_rapport.txt · Dernière modification: 2011/05/10 17:55 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki