étudiants M2ILC |
---|
FRIGUI Rassil |
LANSELLE Maurice |
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
Vous trouverez ci-joint la classe main de notre code Java.
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 :
On veut définir une formule top5(u, d)
pour recommander 5 films à un utilisateur u à une date d donnée.
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
.On veut recommander 5 films pour UserID avant la date timestamp
Exemple :
Film1 User1 Rating1 Coef1 => R1*C1 Film1 User2 Rating2 Coef2 => R2*C2
Exemple :
Filme1 => R1*C1 + R2*C2
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.
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.
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.
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 :
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 :
n
dans le nom du domaine.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.
Il y a trois aspects à prendre en compte, l'initialisation, la mise à jour, et la répartition des données sur plusieurs machines.
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.
Cela suggère
CentSimilaires
où sont listésitem
)à partir de
et pas après
item
)fans
sur chaque machine avec la liste de diffusion des notes pour chaque utilisateur “local”. fan
le propriétaire de la liste CentSimilaires : un abonnement.Sur chaque machine, on aura :
movies
en entier : MovieID→[Title, Genre]users
: UserID, Name, Occupation, Age, Sex, Zip-code, plus pointeurs sur ses CentSimilaires
(Similitude, FilmesNotés1, FilmesNotés2,…,FilmesNotés5)ratings
où UserID
est dans le fragment local : serial
→UserID, MovieID, Rating, Timestamp (ou Jour?). Cette liste est utilisée pour produire ratings
par UserID pour pouvoir fournir les ratings
d'un utilisateur dans un intervalle de dates donnée : UserID→[MovieID, Rating]fans
pour les UserID
dans le fragment local : UserID→UserID[]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] |
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 :
fans
.
Lorsqu'un serveur reçoit un rating pour un fan
qu'il héberge, il doit,
fan
) n'a pas déjà noté le filme,On peut aussi envisager une requête similaire pour recenser les “Semblables” sur d'autres serveurs lorsqu'on a un nouvel utilisateur :
N
utilisateurs et les renvoye.