Mangaki Data Challenge et l'affaire KNN.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Mangaki Data Challenge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Featured on University of Big Data: https://bit.ly/mangakidatachallenge"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Load the data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import os, csv\n",
    "\n",
    "DATA_DIR = '../data/mdc/'  # Here is the folder containing {train, test, watched}.csv\n",
    "\n",
    "with open(os.path.join(DATA_DIR, 'watched.csv')) as f:\n",
    "    next(f)\n",
    "    triplets = [[int(user_id), int(work_id), rating] for user_id, work_id, rating in csv.reader(f)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "\n",
    "watched = pd.DataFrame(triplets, columns=['user_id', 'work_id', 'choice'])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's add a column that contains a numeric value for the rating. It will be used for matrix factorization (SVD)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "rating_values = {'like': 2, 'love': 4, 'dislike': -2, 'neutral': 0.1}\n",
    "\n",
    "watched['value'] = watched['choice'].map(rating_values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>user_id</th>\n",
       "      <th>work_id</th>\n",
       "      <th>choice</th>\n",
       "      <th>value</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>717</td>\n",
       "      <td>8025</td>\n",
       "      <td>dislike</td>\n",
       "      <td>-2.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1106</td>\n",
       "      <td>1027</td>\n",
       "      <td>neutral</td>\n",
       "      <td>0.1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1970</td>\n",
       "      <td>3949</td>\n",
       "      <td>neutral</td>\n",
       "      <td>0.1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1685</td>\n",
       "      <td>9815</td>\n",
       "      <td>like</td>\n",
       "      <td>2.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1703</td>\n",
       "      <td>3482</td>\n",
       "      <td>like</td>\n",
       "      <td>2.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   user_id  work_id   choice  value\n",
       "0      717     8025  dislike   -2.0\n",
       "1     1106     1027  neutral    0.1\n",
       "2     1970     3949  neutral    0.1\n",
       "3     1685     9815     like    2.0\n",
       "4     1703     3482     like    2.0"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "watched.head()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(198970, 2)"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "import numpy as np\n",
    "\n",
    "X = np.array(watched[['user_id', 'work_id']])\n",
    "X.shape"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We indeed have 198k rows and 2 columns (`user_id` and `work_id`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "nb_users = max(X[:, 0]) + 1  # Because users are numbered starting from 0\n",
    "nb_works = max(X[:, 1]) + 1  # Because works are numbered starting from 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "y = np.array(watched['value'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Computing M: (1983 × 9897)\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/jin/Sites/mangaki/mangaki/mangaki/utils/svd.py:36: RuntimeWarning: invalid value encountered in double_scalars\n",
      "  means[i] = np.sum(matrix[i]) / np.sum(matrix[i] != 0)\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Chrono: fill and center matrix [0q, 647ms]\n",
      "Shapes (1983, 20) (20,) (20, 9897)\n",
      "Chrono: factor matrix [0q, 1796ms]\n"
     ]
    }
   ],
   "source": [
    "from mangaki.utils.svd import MangakiSVD\n",
    "\n",
    "svd = MangakiSVD(20)\n",
    "svd.set_parameters(nb_users, nb_works)\n",
    "svd.fit(X, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now will user 1 like work 42? Let's figure out."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 2.28275862])"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "svd.predict(np.array([(1, 42)]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Apparently, yes. Did we predict correctly the training data?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-0.87987414,  0.08310813,  2.05496013,  2.07300611,  0.99431617,\n",
       "        2.        ,  0.83510865,  2.        ,  2.41003277,  1.13191826])"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "svd.predict(X[:10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-2. ,  0.1,  0.1,  2. ,  2. ,  2. , -2. ,  2. ,  2. ,  2. ])"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Not so well. Let's try a different algorithm."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Computing M: (1983 × 9897)\n",
      "Chrono: fill and center matrix [0q, 887ms]\n",
      "Shapes (1983, 20) (20, 9897)\n",
      "Chrono: factor matrix [0q, 9472ms]\n"
     ]
    }
   ],
   "source": [
    "from mangaki.utils.als import MangakiALS\n",
    "\n",
    "als = MangakiALS(20)\n",
    "als.set_parameters(nb_users, nb_works)\n",
    "als.fit(X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.63438461,  0.0385696 ,  1.5584425 ,  2.02189355,  0.87137735,\n",
       "        2.        ,  0.48637334,  2.        ,  1.90309226,  1.7083744 ])"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "als.predict(X[:10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-2. ,  0.1,  0.1,  2. ,  2. ,  2. , -2. ,  2. ,  2. ,  2. ])"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's compute the error of training."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.1507216969289222"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_pred_svd = svd.predict(X)\n",
    "svd.compute_rmse(y_pred_svd, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.87333921830246342"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y_pred_als = als.predict(X)\n",
    "svd.compute_rmse(y_pred_als, y)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "ALS fits the data better."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Mais nous comme on est à Mangaki on a des objets plus simples"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from mangaki.utils.data import Dataset\n",
    "\n",
    "dataset = Dataset()\n",
    "dataset.load_csv('ratings20170627.csv', convert=str, title_filename='works20170627.csv')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9897"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(dataset.titles)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "AnonymizedData(X=array([[717, 8025],\n",
       "       [658, 8263],\n",
       "       [1224, 1892],\n",
       "       ..., \n",
       "       [1509, 3637],\n",
       "       [299, 4184],\n",
       "       [802, 8844]], dtype=object), y=array(['dislike', 'wontsee', 'willsee', ..., 'willsee', 'wontsee', 'like'], dtype=object), nb_users=1983, nb_works=9897)"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dataset.anonymized"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Who has the most ratings in the dataset?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(316, 3068), (985, 2483), (1940, 2179), (802, 2026), (1550, 1953)]"
      ]
     },
     "execution_count": 72,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "from collections import Counter\n",
    "\n",
    "nb_ratings_of_user = Counter(dataset.anonymized.X[:, 0])\n",
    "nb_ratings_of_user.most_common(5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Which means user 316 has 3068 ratings!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import numpy as np\n",
    "\n",
    "ratings = pd.DataFrame(np.column_stack([dataset.anonymized.X, dataset.anonymized.y]), columns=['user_id', 'work_id', 'choice'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "rating_values = {'love': 4, 'like': 2, 'dislike': -2, 'neutral': 0.1, 'willsee': 0.5, 'wontsee': -0.5}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "ratings['value'] = ratings['choice'].map(rating_values)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>user_id</th>\n",
       "      <th>work_id</th>\n",
       "      <th>choice</th>\n",
       "      <th>value</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>717</td>\n",
       "      <td>8025</td>\n",
       "      <td>dislike</td>\n",
       "      <td>-2.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>658</td>\n",
       "      <td>8263</td>\n",
       "      <td>wontsee</td>\n",
       "      <td>-0.5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1224</td>\n",
       "      <td>1892</td>\n",
       "      <td>willsee</td>\n",
       "      <td>0.5</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1106</td>\n",
       "      <td>1027</td>\n",
       "      <td>neutral</td>\n",
       "      <td>0.1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1468</td>\n",
       "      <td>2743</td>\n",
       "      <td>wontsee</td>\n",
       "      <td>-0.5</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "  user_id work_id   choice  value\n",
       "0     717    8025  dislike   -2.0\n",
       "1     658    8263  wontsee   -0.5\n",
       "2    1224    1892  willsee    0.5\n",
       "3    1106    1027  neutral    0.1\n",
       "4    1468    2743  wontsee   -0.5"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ratings.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Computing the neighbors"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "from mangaki.utils.knn import MangakiKNN\n",
    "\n",
    "knn = MangakiKNN(20)\n",
    "knn.set_parameters(dataset.anonymized.nb_users, dataset.anonymized.nb_works)\n",
    "knn.fit(X, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 87,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[array([ 716, 1263, 1683,   57, 1462,   19, 1272, 1655, 1433,  753,  179,\n",
       "        1184,  767,  212, 1613,   39,  418, 1071,  856,  346])]"
      ]
     },
     "execution_count": 87,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knn.get_neighbors([316])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([ 0.10828723,  0.        ,  0.        ,  2.17506037,  1.25183908,\n",
       "        2.47958984,  1.28476562,  1.43611111,  1.88993939,  1.75133929])"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knn.predict(X[:10])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-2. ,  0.1,  0.1,  2. ,  2. ,  2. , -2. ,  2. ,  2. ,  2. ])"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "y[:10]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## L'affaire KNN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si je me connecte sur le site en tant qu'utilisateur qui a plus de 3000 ratings, voici ce qui se passe lorsque je cherche à obtenir des recommandations KNN.\n",
    "\n",
    "    Chrono: get rated works [4q, 18ms]\n",
    "    Chrono: make first anonymous data with 303214 ratings [5q, 3113ms]\n",
    "    Chrono: prepare first fit [5q, 5286ms]\n",
    "    Chrono: get neighbors [5q, 266ms]\n",
    "    Chrono: fit knn-20 [6q, 221ms]\n",
    "    Chrono: remove already rated [6q, 1ms]\n",
    "    Chrono: compute every prediction [6q, 4ms]\n",
    "    Chrono: get bulk [7q, 15ms]\n",
    "\n",
    "Et ces valeurs sont évidemment plus longues sur la prod."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Plusieurs raisons sont en cause.\n",
    "\n",
    "- Les algorithmes [`MangakiXXX`](https://github.com/mangaki/mangaki/tree/master/mangaki/mangaki/utils) (ex. `knn.py`, `als.py`) ont besoin de clés entre 0 et X-1. Or la prod a des trous dans les ID. C'est pour ça qu'on fait une conversion. Notez que les algos SVD et ALS vont directement puiser dans un backup dans le dossier `pickles`, c'est pour ça que ces algos sont plus rapides. Mais lorsqu'un nouvel utilisateur arrive sur le site, on n'a pas encore calculé sa SVD/ALS. Donc il faut recourir à KNN.\n",
    "- Or, l'opération [`make_anonymous_data`](https://github.com/mangaki/mangaki/blob/master/mangaki/mangaki/utils/data.py#L89) est coûteuse. Elle fait deux boucles sur triplets, qui contient ici 300k éléments. En fait, réécrire la fonction `make_anonymous_data` en pandas serait plus rapide, j'ai l'impression.\n",
    "- préparer first fit, c'est long aussi puisque ça parcourt les 300k ratings pour remplir la `lil_matrix` (cf. la fonction [`fit`](https://github.com/mangaki/mangaki/blob/master/mangaki/mangaki/utils/knn.py#L60) dans `knn.py`).\n",
    "\n",
    "Une solution consisterait à stocker un objet qui a précalculé la matrice. Du coup, pour déterminer les plus proches voisins de quelqu'un on n'a plus qu'à faire une opération matricielle (cf. [`cosine_similarity`](https://github.com/mangaki/mangaki/blob/master/mangaki/mangaki/utils/knn.py#L36) dans `get_neighbors` de `knn.py`).\n",
    "\n",
    "C'est votre mission."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Django Shell-Plus",
   "language": "python",
   "name": "django_extensions"
  },
  "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}