{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TP Reco n°1 : Introduction au filtrage collaboratif"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le filtrage collaboratif constitue une famille de modèles centraux pour les systèmes de recommandation. Historiquement, ce sont les premiers modèles que l'on a implémentés, que ce soit avec une vision \"orienté utilisateurs\" ou \"orienté articles\". Ils ont été améliorés progressivement au cours des années, que ce soit par l'industrie (Amazon et Netflix les ont adoptés très tôt) ou le monde académique. Si des modèles concurrents les complètent aujourd'hui, les modèles de filtrage collaboratif restent encore très communs, comme des briques de bases de systèmes plus complexes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans cette séance, nous allons utiliser un jeu de données appelé `ml-100k`, provenant du groupe de recherche MovieLens (pionniers dans l'étude des systèmes de recommandation). Ces données constituent un jeu standard sur lequel sont évalués de nombreux systèmes de recommandation. Les données \"100k\" comportent 100 000 évaluations données par des utilisateurs (environ 1000) sur un peu plus de 1600 films. Il existe des versions des données à plus large échelle (1 ou 10 millions de notes). Les notes sont des notes explicites, sur une échelle entre 1 et 5 (meilleure note)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Après avoir pris en main les données, nous allons construire la matrice des interactions (*ratings*), avant d'examiner des manières élémentaires de faire des prédictions, en cherchant les utilisateurs similaires à l'utilisateur courant, puis en pondérant les avis pour prédire. On regardera ces prédictions, avant d'évaluer l'erreur commise. On explorera ensuite l'influence du biais des utilisateurs et on tâchera de limiter la taille du groupe de utilisateurs similaires (paramètre *k*), avant de tenter de combiner le tout. Enfin, on regardera si des corrélations entre items ressortent.  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Le jeu de données MovieLens100k"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le jeu de données s'obtient ici : [MovieLens](http://files.grouplens.org/datasets/movielens/ml-100k.zip). Il faut ensuite le dézipper, ce qui devrait créer un dossier `ml-100k`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Entrons dans le dossier et regardons un peu les données :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "cd ml-100k/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ls"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vous pouvez lire (au moins partiellement) le README, qui décrit les données.\n",
    "\n",
    "On s'intéresse surtout au fichier `u.data` qui contient l'entièreté des données, c'est-à-dire 100 000 évaluations. les données comportent 4 colonnes : `userid`, `itemid`, `rating`, `timestamp`.\n",
    "\n",
    "Regardons les données :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!head u.data # 10 premières lignes du fichier\n",
    "!echo # line break\n",
    "!wc -l u.data # nombre de lignes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Chargeons cela dans un dataframe pandas."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import warnings\n",
    "warnings.simplefilter(action='ignore', category=FutureWarning) # éviter des Warnings de dépréciation\n",
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "names = ['user_id', 'item_id', 'rating', 'timestamp']\n",
    "df = pd.read_csv('u.data', sep='\\t', names=names)\n",
    "df.head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vérifions que l'on a bien les statistiques annoncées :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_users = df.user_id.unique().shape[0]\n",
    "n_items = df.item_id.unique().shape[0]\n",
    "print(str(n_users) + ' utilisateurs')\n",
    "print(str(n_items) + ' films')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "itemscols=['item_id', 'movie title', 'release date', 'video release date', 'IMDb URL', 'unknown', 'Action', 'Adventure', 'Animation', 'Children\\'s', 'Comedy', 'Crime', 'Documentary', 'Drama', 'Fantasy', 'Film-Noir', 'Horror', 'Musical', 'Mystery', 'Romance', 'Sci-Fi', 'Thriller', 'War', 'Western']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "wtitles = pd.read_csv('u.item', sep='|', names=itemscols, encoding=\"latin-1\")\n",
    "wtitles.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "withtitles = df.merge(wtitles, on = 'item_id')\n",
    "withtitles.head(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "## Construction de la matrice d'interactions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous disposons dans les données MovieLens d'évaluations explicites, nous allons donc proposer un filtrage collaboratif reposant sur ces notes. Nous allons d'abord construire la matrice `ratings` (array NumPy). Comme les données sont indicées à partir de 1 (et que Python indice à partir de 0), un simple décalage suffit."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "ratings = np.zeros((n_users, n_items))\n",
    "for row in df.itertuples():\n",
    "    ratings[row[1]-1, row[2]-1] = row[3]\n",
    "ratings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculons à quel point cette matrice est creuse :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sparsity = float(len(ratings.nonzero()[0]))\n",
    "sparsity /= (ratings.shape[0] * ratings.shape[1])\n",
    "sparsity *= 100\n",
    "print('Sparsity: {:4.2f}%'.format(sparsity))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que pensez-vous de ce chiffre ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "Dans ce dataset, chaque utilisateur a noté au moins 20 films, ce qui donne 6,3% de \"sparsity\", que 6.3% des couples utilisateur-item possibles ont une valeur. Souvent, on travaille dans des contextes où il y a moins de données (1 pour mille, par exemple)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "Attention toutefois : ici, on a identifié \"valeurs manquantes\" et \"valeur 0\" (hors échelle de notes), en première approximation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Créons les jeux de données `train` et `test`, en retirant 10 notes par utilisateur, pour les placer dans le jeu de validation (test)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def train_test_split(ratings):\n",
    "    test = np.zeros(ratings.shape)\n",
    "    train = ratings.copy()\n",
    "    for user in range(ratings.shape[0]):\n",
    "        test_ratings = np.random.choice(ratings[user, :].nonzero()[0], \n",
    "                                        size=10, \n",
    "                                        replace=False)\n",
    "        train[user, test_ratings] = 0.\n",
    "        test[user, test_ratings] = ratings[user, test_ratings]\n",
    "        \n",
    "    assert(np.all((train * test) == 0)) # on vérifie que train et test sont disjoints\n",
    "    return train, test"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train, test = train_test_split(ratings)\n",
    "train,test"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Filtrage collaboratif"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Similarité Cosinus"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Le filtrage collaboratif, qu'il soit orienté utilisateur (*user-based*) ou article (*item-based*), se fonde sur des calculs de similarité. Dans le cas *user based*, on calcule des similarités entre paires d'utilisateurs, en vue d'estimer la proximité de leurs manières de noter.\n",
    "\n",
    "Une mesure de distance assez commune est la similarité cosinus. Si l'on considère qu'un utilisateur est une ligne (ou une colonne) de la matrice d'interactions, c'est-à-dire un vecteur, la similarité avec un autre utilisateur consiste à calculer l'angle formé par leurs deux vecteurs. Formellement, cela se calcule ainsi :\n",
    "\n",
    "$$\n",
    "sim(u, u') = \n",
    "cos(\\theta{}) = \n",
    "\\frac{\\textbf{r}_{u} \\dot{} \\textbf{r}_{u'}}{\\| \\textbf{r}_{u} \\| \\| \\textbf{r}_{u'} \\|} = \n",
    "\\sum_{i} \\frac{r_{ui}r_{u'i}}{\\sqrt{\\sum\\limits_{i} r_{ui}^2} \\sqrt{\\sum\\limits_{i} r_{u'i}^2} }\n",
    "$$\n",
    "\n",
    "Les notes étant positives, la similarité cosinus aura une valeur entre 0 (pas de similarité) et 1 (similarité maximale)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut écrire une version lente (avec boucles `for`) et une version rapide du calcul, cette dernière reposant sur une vision matricielle et les optimisations des bibliothèques (numpy). La version lente est surtout présentée pour mémoire, elle est *très* lente. On propose une version \"user\" et une version \"item\" dans ces fonctions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def slow_user_similarity(ratings, kind='user'):\n",
    "    if kind == 'user':\n",
    "        axmax = 0\n",
    "        axmin = 1\n",
    "    elif kind == 'item':\n",
    "        axmax = 1\n",
    "        axmin = 0\n",
    "    sim = np.zeros((ratings.shape[axmax], ratings.shape[axmax]))\n",
    "    for u in range(ratings.shape[axmax]):\n",
    "        for uprime in range(ratings.shape[axmax]):\n",
    "            rui_sqrd = 0.\n",
    "            ruprimei_sqrd = 0.\n",
    "            for i in range(ratings.shape[axmin]):\n",
    "                sim[u, uprime] = ratings[u, i] * ratings[uprime, i]\n",
    "                rui_sqrd += ratings[u, i] ** 2\n",
    "                ruprimei_sqrd += ratings[uprime, i] ** 2\n",
    "            sim[u, uprime] /= rui_sqrd * ruprimei_sqrd\n",
    "    return sim\n",
    "\n",
    "def fast_similarity(ratings, kind='user', epsilon=1e-9):\n",
    "    # epsilon -> small number for handling dived-by-zero errors\n",
    "    if kind == 'user':\n",
    "        sim = ratings.dot(ratings.T) + epsilon\n",
    "    elif kind == 'item':\n",
    "        sim = ratings.T.dot(ratings) + epsilon\n",
    "    norms = np.array([np.sqrt(np.diagonal(sim))])\n",
    "    return (sim / norms / norms.T)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#%timeit slow_user_similarity(train)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%timeit fast_similarity(train, kind='user')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "user_similarity = fast_similarity(train, kind='user')\n",
    "item_similarity = fast_similarity(train, kind='item')\n",
    "print(user_similarity[:10, :10])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Question : cherchez l'utilisateur le plus similaire à l'utilisateur 1 (indicé 0 dans `train`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def most_similar_user(userid):\n",
    "    return user_similarity[userid][1:].argmax()+1\n",
    "\n",
    "print(\"L'utilisateur le plus similaire à user\",0,\"est le :\",most_similar_user(0), \"avec\",user_similarity[0][most_similar_user(0)])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Premières prédictions de notes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous allons maintenant pouvoir proposer de premières prédictions de notes pour les évaluations non présentes dans la matrice initiale. On pourra ensuite comparer ces notes avec les données placées dans `test`, pour évaluer la qualité de notre modèle de recommandation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On prédit une note d'un utilisateur $u$ pour un item $i$ par la moyenne pondérée des notes des autres utilisateurs, avec les poids égaux aux similarités cosinus entre les autres utilisateurs et $u$, normalisée par le nombre ${r_{u'i}}$ de notes :\n",
    "\n",
    "$$\\hat{r}_{ui} = \\frac{\\sum\\limits_{u'} sim(u, u') \\cdot r_{u'i}}{\\sum\\limits_{u'}|sim(u, u')|}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "À nouveau, on utilise les optimisations NumPy pour accélerer les calculs. Le calcul \"rapide\" n'est (évidemment) pas instantané."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict_slow_simple(ratings, similarity, kind='user'):\n",
    "    pred = np.zeros(ratings.shape)\n",
    "    if kind == 'user':\n",
    "        for i in range(ratings.shape[0]):\n",
    "            for j in range(ratings.shape[1]):\n",
    "                pred[i, j] = similarity[i, :].dot(ratings[:, j])\\\n",
    "                             /np.sum(np.abs(similarity[i, :]))\n",
    "        return pred\n",
    "    elif kind == 'item':\n",
    "        for i in range(ratings.shape[0]):\n",
    "            for j in range(ratings.shape[1]):\n",
    "                pred[i, j] = similarity[j, :].dot(ratings[i, :].T)\\\n",
    "                             /np.sum(np.abs(similarity[j, :]))\n",
    "\n",
    "        return pred\n",
    "\n",
    "def predict_fast_simple(ratings, similarity, kind='user'):\n",
    "    if kind == 'user':\n",
    "        return similarity.dot(ratings) / np.array([np.abs(similarity).sum(axis=1)]).T\n",
    "    elif kind == 'item':\n",
    "        return ratings.dot(similarity) / np.array([np.abs(similarity).sum(axis=1)])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#%timeit predict_slow_simple(train, user_similarity, kind='user')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%timeit predict_fast_simple(train, user_similarity, kind='user')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prédictions pour un utilisateur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pred = predict_fast_simple(train, user_similarity, kind='user')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Calculer les recommandations pour l'utilisateur 1 :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pred[0][0:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "indice : utilisez `nump.argpartition`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "indices = pred[0].argpartition(-5)[-5:]\n",
    "indices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def liste_reco(ligne_user,nb=5):\n",
    "    indices = ligne_user.argpartition(-nb)[-nb:]\n",
    "    return indices\n",
    "\n",
    "keys = liste_reco(pred[0])\n",
    "recodic = dict(zip(keys,pred[0][keys]))\n",
    "sortedreco = {k: v for k, v in sorted(recodic.items(), key=lambda item: item[1], reverse=True)}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def note_user_item(user,item):\n",
    "    return ratings[user-1][item-1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut regarder les titres de films."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "colonnes = ['movie id', 'movie title', 'release date', 'video release date', 'IMDb URL', 'unknown', 'Action', 'Adventure', 'Animation', 'Children', 'Comedy', 'Crime', 'Documentary', 'Drama', 'Fantasy', 'Film-Noir', 'Horror', 'Musical', 'Mystery', 'Romance', 'Sci-Fi', 'Thriller', 'War', 'Western'\n",
    "]\n",
    "films = pd.read_csv('u.item', sep='|', names=colonnes, index_col =\"movie id\", encoding='latin-1')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def titre_film(movieid):\n",
    "    return films.loc[movieid][\"movie title\"]\n",
    "\n",
    "titre_film(49)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut ensuite essayer de comparer aux notes initiales de l'utilisateur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Voici le top des éléments pour l'user 0\")\n",
    "for ind,val in sortedreco.items():\n",
    "    print(\"Élément %.3i, note prédite : %.2f\"%(ind,val))\n",
    "    print(\"--            note réelle :\",note_user_item(1,ind))\n",
    "    print(titre_film(ind))\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Évaluation : MSE"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut quantifier l'erreur globale sur le jeu de données, une pratique courante qui permet de comparer des algorithmes de recommandation. On peut utiliser la version MSE (*mean squared error*) ou RMSE (*root mean squared error*)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.metrics import mean_squared_error"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.metrics import mean_squared_error\n",
    "\n",
    "def get_mse(pred, actual):\n",
    "    # Keep only nonzero terms.\n",
    "    pred = pred[actual.nonzero()].flatten()\n",
    "    actual = actual[actual.nonzero()].flatten()\n",
    "    # ou squared = False pour la MSE\n",
    "    return mean_squared_error(pred, actual)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "item_prediction = predict_fast_simple(train, item_similarity, kind='item')\n",
    "user_prediction = predict_fast_simple(train, user_similarity, kind='user')\n",
    "\n",
    "print('User-based CF MSE: ' + str(get_mse(user_prediction, test)))\n",
    "print('Item-based CF MSE: ' + str(get_mse(item_prediction, test)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Que pensez-vous de ce chiffre ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'erreur est un peu plus élevée en Item-based, ce qui n'est pas forcément le cas usuel. Puisque, rappelons-le, en item-based on travaille à partir des notes de l'utilisateur, alors qu'en user-based on travaille avec les notes des autres (d'où : biais). \n",
    "\n",
    "Il faudrait calculer les RMSE pour avoir une valeur d'erreur comparable aux notes. Ces valeurs sont assez élevées, les prédictions calculées ne sont pas \"excellentes\". Mais on a pour le moment utilisé \"tout le monde\", sans restriction."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Influence des $k$ plus proches utilisateurs\n",
    "\n",
    "Nous avons pour le moment utilisé *tous* les utilisateurs pour calculer les notes. Comme indiqué en cours, il est beaucoup plus fréquent de calculer des groupes de pairs (*peer group*), *i.e.*, des groupes restreints de *k* utilisateurs très similaires à l'utilisateur pour lequel on veut prédire. L'idée sera ensuite de ne calculer notre somme pondérée qu'avec ces utilisateurs :\n",
    "\n",
    "$$\\hat{r}_{ui} = \\frac{\\sum\\limits_{u'} sim(u, u') r_{u'i}}{\\sum\\limits_{u'}|sim(u, u')|}$$\n",
    "\n",
    "(le calcul est ici implémenté en version \"lente\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "def predict_topk(ratings, similarity, kind='user', k=40):\n",
    "    pred = np.zeros(ratings.shape)\n",
    "    if kind == 'user':\n",
    "        for i in range(ratings.shape[0]):\n",
    "            top_k_users = [np.argsort(similarity[:,i])[:-k-1:-1]]\n",
    "            for j in range(ratings.shape[1]):\n",
    "                pred[i,j] = similarity[i,:][top_k_users].dot(ratings[:, j][top_k_users].T) \n",
    "                pred[i,j] /= np.sum(np.abs(similarity[tuple((i, slice(None)))][top_k_users]))\n",
    "    if kind == 'item':\n",
    "        for j in range(ratings.shape[1]):\n",
    "            top_k_items = [np.argsort(similarity[:,j])[:-k-1:-1]]\n",
    "            for i in range(ratings.shape[0]):\n",
    "                pred[i, j] = similarity[j, :][top_k_items].dot(ratings[i, :][top_k_items].T) \n",
    "                pred[i, j] /= np.sum(np.abs(similarity[j, :][top_k_items]))        \n",
    "    \n",
    "    return pred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pred = predict_topk(train, user_similarity, kind='user', k=40)\n",
    "print('Top-k User-based CF MSE: ' + str(get_mse(pred, test)))\n",
    "\n",
    "pred = predict_topk(train, item_similarity, kind='item', k=40)\n",
    "print('Top-k Item-based CF MSE: ' + str(get_mse(pred, test)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question :** Que pensez-vous de ces chiffres ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a amélioré significativement les erreurs, en utilisant des groupes restreints d'utilisateurs/items similaires pour faire les prédictions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "L'idée est évidemment de chercher une valeur de $k$ qui soit la plus satisfaisante possible. Nous allons essayer de visualiser ce qui se passe pour quelques valeurs de $k$ (attention, calcul un peu long)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "#k_array = [5, 15, 30, 50, 100, 200]\n",
    "k_array = [5,15, 30]\n",
    "user_train_mse = []\n",
    "user_test_mse = []\n",
    "item_test_mse = []\n",
    "item_train_mse = []\n",
    "\n",
    "def get_mse(pred, actual):\n",
    "    pred = pred[actual.nonzero()].flatten()\n",
    "    actual = actual[actual.nonzero()].flatten()\n",
    "    return mean_squared_error(pred, actual)\n",
    "\n",
    "for k in k_array:\n",
    "    print(k)\n",
    "    user_pred = predict_topk(train, user_similarity, kind='user', k=k)\n",
    "    item_pred = predict_topk(train, item_similarity, kind='item', k=k)\n",
    "    \n",
    "    user_train_mse += [get_mse(user_pred, train)]\n",
    "    user_test_mse += [get_mse(user_pred, test)]\n",
    "    \n",
    "    item_train_mse += [get_mse(item_pred, train)]\n",
    "    item_test_mse += [get_mse(item_pred, test)]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!pip install matplotlib seaborn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "sns.set()\n",
    "\n",
    "pal = sns.color_palette(\"Set2\", 2)\n",
    "\n",
    "plt.figure(figsize=(8, 8))\n",
    "plt.plot(k_array, user_train_mse, c=pal[0], label='User-based train', alpha=0.5, linewidth=5)\n",
    "plt.plot(k_array, user_test_mse, c=pal[0], label='User-based test', linewidth=5)\n",
    "plt.plot(k_array, item_train_mse, c=pal[1], label='Item-based train', alpha=0.5, linewidth=5)\n",
    "plt.plot(k_array, item_test_mse, c=pal[1], label='Item-based test', linewidth=5)\n",
    "plt.legend(loc='best', fontsize=20)\n",
    "plt.xticks(fontsize=16);\n",
    "plt.yticks(fontsize=16);\n",
    "plt.xlabel('k', fontsize=30);\n",
    "plt.ylabel('MSE', fontsize=30);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question :** Que concluez-vous ? "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les valeurs de $k=15$ ou $k=30$ semblent produire les meilleurs résultats pour les ensembles de test, en item et user-based (respectivement). En testant d'autres valeurs de $k$, cf code supra, on constate que 50 est un minimum. On pourrait optimiser encore en affinant la recherche."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Biais des utilisateurs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Nous pouvons proposer une version débiaisée des notes des utilisateurs. En effet, certains utilisateurs ont une tendance à ne mettre que des bonnes (ou des mauvaises) évaluations. On peut supposer cependant que les différences, pour chaque utilisateur, sont significatives. Si quelqu'un \"note bas\", ses notes seront (par exemple) entre 1 et 3. On suppose qu'il préfère les films notés 3 aux films notés 1. En revanche, ses 3 ne seront pas comparables à ceux de quelqu'un qui \"note haut\" (pour lequel les notes seraient entre 3 et 5, 3 étant alors une \"mauvaise note\")."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour débiaiser, nous allons retirer des notes de chaque utilisateur la moyenne de ses notes (avant prédiction). On rajoutera cette moyenne à la fin, pour obtenir une prédiction.\n",
    "\n",
    "$$\\hat{r}_{ui} = \\bar{r_{u}} + \\frac{\\sum\\limits_{u'} sim(u, u') (r_{u'i} - \\bar{r_{u'}})}{\\sum\\limits_{u'}|sim(u, u')|}$$\n",
    "\n",
    "où $\\bar{r_{u}}$ est la moyenne des notes de $u$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict_nobias(ratings, similarity, kind='user'):\n",
    "    if kind == 'user':\n",
    "        user_bias = ratings.mean(axis=1)\n",
    "        ratings = (ratings - user_bias[:, np.newaxis]).copy()\n",
    "        pred = similarity.dot(ratings) / np.array([np.abs(similarity).sum(axis=1)]).T\n",
    "        pred += user_bias[:, np.newaxis]\n",
    "    elif kind == 'item':\n",
    "        item_bias = ratings.mean(axis=0)\n",
    "        ratings = (ratings - item_bias[np.newaxis, :]).copy()\n",
    "        pred = ratings.dot(similarity) / np.array([np.abs(similarity).sum(axis=1)])\n",
    "        pred += item_bias[np.newaxis, :]\n",
    "        \n",
    "    return pred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "user_pred = predict_nobias(train, user_similarity, kind='user')\n",
    "print('Bias-subtracted User-based CF MSE: ' + str(get_mse(user_pred, test)))\n",
    "\n",
    "item_pred = predict_nobias(train, item_similarity, kind='item')\n",
    "print('Bias-subtracted Item-based CF MSE: ' + str(get_mse(item_pred, test)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question :** Que pensez-vous de ces chiffres ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "Là encore, cette technique permet de faire baisser l'erreur par rapport à nos prédictions initiales."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Combiner prédictions débiaisées et top-$k$\n",
    "\n",
    "Enfin, nous pouvons proposer une version combinée (débiaisée et top-$k$) de notre recommandation simple."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predict_topk_nobias(ratings, similarity, kind='user', k=40):\n",
    "    pred = np.zeros(ratings.shape)\n",
    "    if kind == 'user':\n",
    "        user_bias = ratings.mean(axis=1)\n",
    "        ratings = (ratings - user_bias[:, np.newaxis]).copy()\n",
    "        for i in range(ratings.shape[0]):\n",
    "            top_k_users = [np.argsort(similarity[:,i])[:-k-1:-1]]\n",
    "            for j in range(ratings.shape[1]):\n",
    "                pred[i, j] = similarity[i, :][top_k_users].dot(ratings[:, j][top_k_users].T) \n",
    "                pred[i, j] /= np.sum(np.abs(similarity[i, :][top_k_users]))\n",
    "        pred += user_bias[:, np.newaxis]\n",
    "    if kind == 'item':\n",
    "        item_bias = ratings.mean(axis=0)\n",
    "        ratings = (ratings - item_bias[np.newaxis, :]).copy()\n",
    "        for j in range(ratings.shape[1]):\n",
    "            top_k_items = [np.argsort(similarity[:,j])[:-k-1:-1]]\n",
    "            for i in range(ratings.shape[0]):\n",
    "                pred[i, j] = similarity[j, :][top_k_items].dot(ratings[i, :][top_k_items].T) \n",
    "                pred[i, j] /= np.sum(np.abs(similarity[j, :][top_k_items])) \n",
    "        pred += item_bias[np.newaxis, :]\n",
    "        \n",
    "    return pred"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "k_array = [5, 15, 30, 50, 100, 200]\n",
    "k_array = [5, 15, 50, 200]\n",
    "user_train_mse = []\n",
    "user_test_mse = []\n",
    "item_test_mse = []\n",
    "item_train_mse = []\n",
    "\n",
    "for k in k_array:\n",
    "    print(k)\n",
    "    user_pred = predict_topk_nobias(train, user_similarity, kind='user', k=k)\n",
    "    item_pred = predict_topk_nobias(train, item_similarity, kind='item', k=k)\n",
    "    \n",
    "    user_train_mse += [get_mse(user_pred, train)]\n",
    "    user_test_mse += [get_mse(user_pred, test)]\n",
    "    \n",
    "    item_train_mse += [get_mse(item_pred, train)]\n",
    "    item_test_mse += [get_mse(item_pred, test)]  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "pal = sns.color_palette(\"Set2\", 2)\n",
    "\n",
    "plt.figure(figsize=(8, 8))\n",
    "plt.plot(k_array, user_train_mse, c=pal[0], label='User-based train', alpha=0.5, linewidth=5)\n",
    "plt.plot(k_array, user_test_mse, c=pal[0], label='User-based test', linewidth=5)\n",
    "plt.plot(k_array, item_train_mse, c=pal[1], label='Item-based train', alpha=0.5, linewidth=5)\n",
    "plt.plot(k_array, item_test_mse, c=pal[1], label='Item-based test', linewidth=5)\n",
    "plt.legend(loc='best', fontsize=20)\n",
    "plt.xticks(fontsize=16);\n",
    "plt.yticks(fontsize=16);\n",
    "plt.xlabel('k', fontsize=30);\n",
    "plt.ylabel('MSE', fontsize=30);"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question :** Que concluez-vous ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "editable": true,
    "slideshow": {
     "slide_type": ""
    },
    "tags": []
   },
   "source": [
    "De façon un peu surprenante, il semble que la combinaison des deux modèles soit moins performante que le top-k seul."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Corrélations entre items ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comme nous travaillons avec des films, nous pouvons essayer de regarder si des corrélations simples entre les colonnes de la matrices nous paraissent \"sensées\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!head -2 u.item"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Avec les fonctions de similarités construites plus haut, on peut écrire une fonction retournant les films les plus similaires pour un film donné. Le film entré est le premier de la liste (il est le plus similaire à lui-même)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Load in movie data\n",
    "idx_to_movie = {}\n",
    "with open('u.item', 'r', encoding=\"utf8\", errors='ignore') as f:\n",
    "    for line in f.readlines():\n",
    "        info = line.split('|')\n",
    "        idx_to_movie[int(info[0])-1] = info[1]\n",
    "        \n",
    "def top_k_movies(similarity, mapper, movie_idx, k=6):\n",
    "    return [mapper[x] for x in np.argsort(similarity[movie_idx,:])[:-k-1:-1]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx = 0 # Toy Story\n",
    "movies = top_k_movies(item_similarity, idx_to_movie, idx)\n",
    "for movie in enumerate(movies):\n",
    "    print(movie)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ça ne semble pas extraordinaire. Peut-on avoir mieux ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx = 1 # GoldenEye\n",
    "movies = top_k_movies(item_similarity, idx_to_movie, idx)\n",
    "for movie in enumerate(movies):\n",
    "    print(movie)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx = 20 # Muppet Treasure Island\n",
    "movies = top_k_movies(item_similarity, idx_to_movie, idx)\n",
    "for movie in enumerate(movies):\n",
    "    print(movie)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question :** Que pensez-vous de ces listes ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Certaines recommandations paraissent assez lointaines (Toy Story proche de Star Wars, pas d'autre film de James Bond proche de Golden Eye), la similarité qu'on utilise pourrait peut-être différente. Le biais de popularité semble aussi assez clair, nous pouvons essayer de le limiter avec une autre mesure."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Autre mesure de similarité"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sklearn.metrics import pairwise_distances\n",
    "item_correlation = 1 - pairwise_distances(train.T, metric='correlation')\n",
    "item_correlation[np.isnan(item_correlation)] = 0."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Regardons les mêmes listes :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx = 0 # Toy Story\n",
    "movies = top_k_movies(item_correlation, idx_to_movie, idx)\n",
    "for movie in enumerate(movies):\n",
    "    print(movie)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx = 1 # GoldenEye\n",
    "movies = top_k_movies(item_correlation, idx_to_movie, idx)\n",
    "for movie in enumerate(movies):\n",
    "    print(movie)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx = 20 # Muppet Treasure Island\n",
    "movies = top_k_movies(item_correlation, idx_to_movie, idx)\n",
    "for movie in enumerate(movies):\n",
    "    print(movie)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "idx = 40 # Billy Madison\n",
    "movies = top_k_movies(item_correlation, idx_to_movie, idx)\n",
    "for movie in enumerate(movies):\n",
    "    print(movie)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Question :** Que concluez-vous ?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quoique l'ordre ait un peu changé, on retrouve encore souvent les mêmes films. Des modèles plus complexes permettraient sans doute d'améliorer ces prédictions."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.7"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": true,
   "title_cell": "Sommaire",
   "title_sidebar": "Sommaire",
   "toc_cell": false,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "191.3px"
   },
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}