Télécharger le MovieLens 100K dataset et dézippez les fichiers dans votre répertoire que vous aurez créé pour le projet. Comme son nom l'indique, lisez le fichier README.

Lancez un notebook python (où une session ptyhon en ligne de commande). Vous pourrez avoir besoin des packages suivants:

import csv
import numpy as np
%matplotlib inline # pour ipython notebook 
import matplotlib as plt
import pylab as pl

Importez les fichiers du MovieLens 100K dataset suivants: u1.base, u1.test, u1.user, u1.item, u1.genre, u1.occupation. Vous pouvez utiliser les codes suivant pour les imports des fichiers base et test.

with open(baseFileName, 'rb') as f:
    fieldnames=['user','movie','rating','datestamp']
    reader = csv.DictReader(f, delimiter = '\t', fieldnames=fieldnames)
    # create a dict out of reader, converting all values to integers
    baseUserItem =  [dict([key, int(value)] for key, value in row.iteritems()) for row in list(reader)]

Pour les autre fichiers non-numériques, vous pouvez utiliser le code suivant, en adaptant pour fieldnames pour les différents fichiers.

with open('u.user', 'rb') as f:
    reader = csv.DictReader(f, delimiter = '|', fieldnames=['user','age','sex','occupation','zipcode'])
    User = list(reader)

A partir des données utilisateur-item, créez une matrice $R$ avec coefficients R[u-1,i-1] le rating de l'utilisateur avec ID u pour le film avec ID i, si le film a été noté et 0 sinon. Vérifiez que la taille de $R$ est bien m x n, avec m le nombre total d'utilisateurs dans la base u.data et n le nombre total de films dans la base u.data. Ce sera important pour la tâche de prédiction.

27/11/2017 Pour remplir la matrice $R$, vous pouvez par exemple utiliser le code suivant

# Remplir la matrice utilisateur-item 
R = np.zeros( (nu,ni) )
for row in baseUserItem:
    R[row['user']-1,row['movie']-1] = row['rating']

Pour compléter la matrice $R$, deux approches naïves s'offrent à nous: compléter les notes de chaque item par leur note moyenne, ou compléter les notes de chaque utilisateur par leur notes moyennes. Calculer les notes moyennes de film $\bar c$ et des utilisateurs $\bar r$. Attention, les zéros de $R$ ne sont pas des notes ! On mettra une note moyenne 0 si aucune note n'est disponible pour un film ou un utilisateur.

Considérez deux matrice complétées $R_C$, la matrice complétée des moyennes de film et $R_R$, la matrice complétée des moyennes utilisateurs. Afficher les deux matrices normalisées à l'aide de la commande pl.imshow(<matrice>, interpolation='none').

Ecrivez une routine pour calculer la décomposition en valeurs singulières des matrices $R_R$ et $R_C$ pour obtenir trois matrices $U, S, V'$ telles que $$R_{\{R,C\}} = U S V'.$$

Pour un entier $k \geq 1$ fixé on assigne $S_{j,j} = 0$ pour $j>k$ et on note cette matrice réduite de valeur singulières $S_k$. Donnez la forme des matrices réduites $U_k$ et $V_k'$ telles que $$U_k S_k V_k' = U S_k V'.$$ Quelles sont les tailles de matrice réduites $U_k$, $S_k$ et $V_k'$? On note $R_k$ l'approximation bas-rang $U_k S_k V_k'$ de la matrice $R_{\{R,C\}}$.

Bonus: essayez de calculer matrice $U_k$ $S_k$ et $V_k'$ à l'aide des codes vus en classe.

Donnez une interprétation de $X_k(u,)$ et de $Y_k(,i)$ dans le contexte utilisateur/film.

Calculer les MAE des predictions basées sur les matrices $R_C$ et $R_R$ pour $k = 1,...,30$. Quelle matrice donne les meilleures prédictions ?

Maintenant, comparez les prédictions basées sur la SVD avec une prédiction naïve, celle obtenue directement de $R_C$ ou de $R_R$. Quels sont les avantages de l'approximation bas-rang par rapport à l'utilisation de la matrice de rang plein? Répondez en terme de qualité de prédiction, de coût en calcul et de coût en stockage.

27/11/2017 Vous pouvez vous inspirer des codes ci-dessous pour calculer la MAE.

# Calculer la qualite de la prediction: MAE
# testFileName = 'u1.test' # par exemple 
with open(testFileName, 'rb') as f:
    fieldnames=['user','movie','rating','datestamp']
    reader = csv.DictReader(f, delimiter = '\t', fieldnames=fieldnames)
    # create a dict out of reader, converting all values to integers
    testUserItem =  [dict([key, int(value)] for key, value in row.iteritems()) for row in list(reader)]

trueRating = [r['rating'] for r in testUserItem]
# definir la liste de predictions des couples utilisateur-item de testUserItem dans: prediction
errorRating = np.asmatrix(prediction) - np.asmatrix(trueRating)
MAE = np.mean(np.abs(errorRating))

Nous avons vu que toute matrice $A$ admettait une décomposition en valeurs singulières. Montrez que si $A$ est réelle, alors elle admet une décomposition réelle: $A = U \Sigma V^*$, avec $U$ et $V$ des matrices à coefficients réels.

(Question complètement théorique, à traiter indépendament des autres questions. Pour la preuve, utiliser le fait que les matrice $U$ et $V$ contiennent les vecteurs propres associées à $A^{} A^*$ et ${A}^* A^{}$.)

Etablissez les problèmes linéaires de moindres carrés pour la méthode des moindres carrés alternés: écrivez les équations normales pour le problème de moindres carrés $$ \min F(X_u) \; \text{et} \; \min G(Y_i),$$ pour $i = 1,..., m$ et $u = 1,...,n$. Pour cela, notez que $x_u$ minimisera $|| r_{u,i} - x_u^*y_i||^2 + \lambda ||x_u||^2$ si les dérivées partielles par rapport au coefficient de $x_u$ sont nulles, c.-à-d. si le gradient est nul. Calculer le gradient, en utilisant les identités suivantes: $$\frac{d x^*Ax}{ d x} = \bigl( A + A^* ) x$$ et posez le à zéro.

Cette question est le coeur du projet. Dans le problème de moindres carrés ci-haut, on a deux matrices inconnues $X$ et $Y$. On a vu en classe que le problème d'approcher un vecteur $b$ par l'image d'une application linéaire $Ax$ au sens des moindres carrés pouvait s'écrire avec les équations normales. Le problème sur-déterminé $Ax = b$ possède une solution au sens des moindres carrés $x$ si $x$ satisfait les équations normales $A^*(Ax) = A^*b$. Ici, on n'a pas les problème linéaire sur-déterminé mais on sa représentation en terme de carrés de l'erreur. Pour résoudre le problème de moindres carrés, on peut écrire les équations normales associées et résoudre le système linéaire.

La question est donc, comment ré-écrire le problème $\min F(X_u)$ comme un problème de la forme $A^*(A X_u^*) = A^*b$. Entre d'autres termes, déterminer $A, b$ le couple matrice vecteur tel que la solution $X_u^*$ corresponde à la solution du problème de moindres carrés. Prenez les expressions à minimiser, dérivez-les par rapport au vecteurs à minimiser et posez la dérivée à zéro, vous devriez retomber sur les équations normales.

En plus de la formule de différentiation ci-dessus, on a $$\frac{d x^* A^* b}{d x} = A^*b.$$ Notez que vous aurez des équations normales similaires pour le problème $\min G(Y_i)$. Si vous obtenez des résultats sans avoir besoin de la formule de différentiation ci-dessus, vous avez soit fait une erreur quelque part, soit une bonne intuition. La deuxième hypothèse est possible. En ce cas vous avez obtenu les équations normales qui dépendent de $\lambda, R, W$ et $Y$ ou $X$. Sinon, vérifiez que les prédictions que vous avez obtenues sont de bonne qualité.

Ecrivez un code pour itérer un nombre nbrIter de fois la méthode des moindres carrés alternés. A chaque itération, calculer et afficher la MAE de l'itération courante.

Posez lambda_, k, nbrIter
Initialisez X, Y
for j in range(nbrIter):
    for u in range(m):
        Resoudre le problème de moindres carrés pour X[u]
    for i in range(n):
        Resoudre le problème de moindre carrés pour Y[:,i]
    Calculer la prediction pour chaque rating du jeu de données test
    Calculer la MAE
    Afficher la MAE 

Vous pouvez utiliser np.linalg.solve ou bien une des méthodes vue en classe (en bonus).

Explorez les solutions pour differentes valeurs de $\lambda$, differents nombres de features $k$, et différentes conditions initiales pour $X$ et $Y$. Commencez par un petit nombre d'itérations, les calculs peuvent être longs.

Comment se comporte la MAE au cours des itérations? Est-ce qu'on converge ? Est-ce que la MAE converge vers une valeur minimale ?

Quel est le rôle de $\lambda$ et par extension, pourquoi introduire des termes $\lambda ||X_u||^2$ et $\lambda ||Y_i||^2$?

En fonction de $m, n$ et $k$, combien de systèmes linéaires doivent être résolus à chaque itération, et quelle sont leurs tailles?

Pour tester vos codes, en prenant les paramètres de simulation suivants, vous devriez obtenir un score MAE = 0.758687648419.

baseFileName = 'u1.base' # training dataset
testFileName = 'u1.test' # test dataset (complement of the test dataset)
nbrIter = 10 # nombre d'iterations
nbrFeatures = 3 # k
lmbd = 0.02 # parametre lambda
X = np.ones( (m, nbrFeatures) ) # matrice initiale X
Y = np.ones( (nbrFeatures, n) ) # matrice initiale Y

Comparez les méthodes de SVD et de moindres carrés selon les critères suivants:

• Temps de calcul des matrices de prédiction bas-rang $X$ et $Y$.
• Temps de calcul pour obtenir un prédiction.
• Qualité de la prédiction.

Vous êtes libres d'utiliser les méthodes que vous voulez pour comparer et présenter les résultats. Si vous utilisez des graphiques, pensez à bien identifier les axes, courbes, etc.

Comment pourriez-vous améliorer la qualité des prédictions? Discutez et si possible implémentez et testez ces idées.

Rajoutez un utilisateur: vous ! Notez quelques films parmi les films du jeu de données. Prenez disons 50% de ces ratings aléatoirement et mettez-les au bout du jeu de donnée u.data. Mettez le reste de vos ratings dans un fichier jeu test. A partir de la meilleure méthode que vous avez trouvée, effectuez une prédiction pour chaque rating du jeu test. Comment sont les prédictions ? Quels films vous recommanderiez-vous ?