notebooks/00_quick_start/sar_movielens.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<i>Copyright (c) Microsoft Corporation. All rights reserved.</i>\n",
    "\n",
    "<i>Licensed under the MIT License.</i>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SAR Single Node on MovieLens (Python, CPU)\n",
    "\n",
    "Simple Algorithm for Recommendation (SAR) is a fast and scalable algorithm for personalized recommendations based on user transaction history. It produces easily explainable and interpretable recommendations and handles \"cold item\" and \"semi-cold user\" scenarios. SAR is a kind of neighborhood based algorithm (as discussed in [Recommender Systems by Aggarwal](https://dl.acm.org/citation.cfm?id=2931100)) which is intended for ranking top items for each user. More details about SAR can be found in the [deep dive notebook](../02_model/sar_deep_dive.ipynb). \n",
    "\n",
    "SAR recommends items that are most ***similar*** to the ones that the user already has an existing ***affinity*** for. Two items are ***similar*** if the users that interacted with one item are also likely to have interacted with the other. A user has an ***affinity*** to an item if they have interacted with it in the past.\n",
    "\n",
    "### Advantages of SAR:\n",
    "- High accuracy for an easy to train and deploy algorithm\n",
    "- Fast training, only requiring simple counting to construct matrices used at prediction time. \n",
    "- Fast scoring, only involving multiplication of the similarity matrix with an affinity vector\n",
    "\n",
    "### Notes to use SAR properly:\n",
    "- Since it does not use item or user features, it can be at a disadvantage against algorithms that do.\n",
    "- It's memory-hungry, requiring the creation of an $mxm$ sparse square matrix (where $m$ is the number of items). This can also be a problem for many matrix factorization algorithms.\n",
    "- SAR favors an implicit rating scenario and it does not predict ratings.\n",
    "\n",
    "This notebook provides an example of how to utilize and evaluate SAR in Python on a CPU."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 0 Global Settings and Imports"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "System version: 3.7.3 | packaged by conda-forge | (default, Jul  1 2019, 21:52:21) \n",
      "[GCC 7.3.0]\n",
      "Pandas version: 0.23.4\n"
     ]
    }
   ],
   "source": [
    "# set the environment path to find Recommenders\n",
    "import sys\n",
    "sys.path.append(\"../../\")\n",
    "\n",
    "import logging\n",
    "import numpy as np\n",
    "import pandas as pd\n",
    "import papermill as pm\n",
    "\n",
    "from reco_utils.common.timer import Timer\n",
    "from reco_utils.dataset import movielens\n",
    "from reco_utils.dataset.python_splitters import python_stratified_split\n",
    "from reco_utils.evaluation.python_evaluation import map_at_k, ndcg_at_k, precision_at_k, recall_at_k\n",
    "from reco_utils.recommender.sar import SAR\n",
    "\n",
    "print(\"System version: {}\".format(sys.version))\n",
    "print(\"Pandas version: {}\".format(pd.__version__))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1 Load Data\n",
    "\n",
    "SAR is intended to be used on interactions with the following schema:\n",
    "`<User ID>, <Item ID>,<Time>,[<Event Type>], [<Event Weight>]`. \n",
    "\n",
    "Each row represents a single interaction between a user and an item. These interactions might be different types of events on an e-commerce website, such as a user clicking to view an item, adding it to a shopping basket, following a recommendation link, and so on. Each event type can be assigned a different weight, for example, we might assign a “buy” event a weight of 10, while a “view” event might only have a weight of 1.\n",
    "\n",
    "The MovieLens dataset is well formatted interactions of Users providing Ratings to Movies (movie ratings are used as the event weight) - we will use it for the rest of the example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "tags": [
     "parameters"
    ]
   },
   "outputs": [],
   "source": [
    "# top k items to recommend\n",
    "TOP_K = 10\n",
    "\n",
    "# Select MovieLens data size: 100k, 1m, 10m, or 20m\n",
    "MOVIELENS_DATA_SIZE = '100k'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.1 Download and use the MovieLens Dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "100%|██████████| 4.81k/4.81k [00:02<00:00, 1.90kKB/s]\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>userID</th>\n",
       "      <th>itemID</th>\n",
       "      <th>rating</th>\n",
       "      <th>timestamp</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>196</td>\n",
       "      <td>242</td>\n",
       "      <td>3.0</td>\n",
       "      <td>881250949</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>186</td>\n",
       "      <td>302</td>\n",
       "      <td>3.0</td>\n",
       "      <td>891717742</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>22</td>\n",
       "      <td>377</td>\n",
       "      <td>1.0</td>\n",
       "      <td>878887116</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>244</td>\n",
       "      <td>51</td>\n",
       "      <td>2.0</td>\n",
       "      <td>880606923</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>166</td>\n",
       "      <td>346</td>\n",
       "      <td>1.0</td>\n",
       "      <td>886397596</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   userID  itemID  rating  timestamp\n",
       "0     196     242     3.0  881250949\n",
       "1     186     302     3.0  891717742\n",
       "2      22     377     1.0  878887116\n",
       "3     244      51     2.0  880606923\n",
       "4     166     346     1.0  886397596"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = movielens.load_pandas_df(\n",
    "    size=MOVIELENS_DATA_SIZE\n",
    ")\n",
    "\n",
    "# Convert the float precision to 32-bit in order to reduce memory consumption \n",
    "data['rating'] = data['rating'].astype(np.float32)\n",
    "\n",
    "data.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2 Split the data using the python random splitter provided in utilities:\n",
    "\n",
    "We split the full dataset into a `train` and `test` dataset to evaluate performance of the algorithm against a held-out set not seen during training. Because SAR generates recommendations based on user preferences, all users that are in the test set must also exist in the training set. For this case, we can use the provided `python_stratified_split` function which holds out a percentage (in this case 25%) of items from each user, but ensures all users are in both `train` and `test` datasets. Other options are available in the `dataset.python_splitters` module which provide more control over how the split occurs."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "train, test = python_stratified_split(data, ratio=0.75, col_user='userID', col_item='itemID', seed=42)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Train:\n",
      "Total Ratings: 74992\n",
      "Unique Users: 943\n",
      "Unique Items: 1649\n",
      "\n",
      "Test:\n",
      "Total Ratings: 25008\n",
      "Unique Users: 943\n",
      "Unique Items: 1444\n",
      "\n"
     ]
    }
   ],
   "source": [
    "print(\"\"\"\n",
    "Train:\n",
    "Total Ratings: {train_total}\n",
    "Unique Users: {train_users}\n",
    "Unique Items: {train_items}\n",
    "\n",
    "Test:\n",
    "Total Ratings: {test_total}\n",
    "Unique Users: {test_users}\n",
    "Unique Items: {test_items}\n",
    "\"\"\".format(\n",
    "    train_total=len(train),\n",
    "    train_users=len(train['userID'].unique()),\n",
    "    train_items=len(train['itemID'].unique()),\n",
    "    test_total=len(test),\n",
    "    test_users=len(test['userID'].unique()),\n",
    "    test_items=len(test['itemID'].unique()),\n",
    "))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2 Train the SAR Model"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.1 Instantiate the SAR algorithm and set the index\n",
    "\n",
    "We will use the single node implementation of SAR and specify the column names to match our dataset (timestamp is an optional column that is used and can be removed if your dataset does not contain it).\n",
    "\n",
    "Other options are specified to control the behavior of the algorithm as described in the [deep dive notebook](../02_model/sar_deep_dive.ipynb)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "logging.basicConfig(level=logging.DEBUG, \n",
    "                    format='%(asctime)s %(levelname)-8s %(message)s')\n",
    "\n",
    "model = SAR(\n",
    "    col_user=\"userID\",\n",
    "    col_item=\"itemID\",\n",
    "    col_rating=\"rating\",\n",
    "    col_timestamp=\"timestamp\",\n",
    "    similarity_type=\"jaccard\", \n",
    "    time_decay_coefficient=30, \n",
    "    timedecay_formula=True\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.2 Train the SAR model on our training data, and get the top-k recommendations for our testing data\n",
    "\n",
    "SAR first computes an item-to-item ***co-occurence matrix***. Co-occurence represents the number of times two items appear together for any given user. Once we have the co-occurence matrix, we compute an ***item similarity matrix*** by rescaling the cooccurences by a given metric (Jaccard similarity in this example). \n",
    "\n",
    "We also compute an ***affinity matrix*** to capture the strength of the relationship between each user and each item. Affinity is driven by different types (like *rating* or *viewing* a movie), and by the time of the event. \n",
    "\n",
    "Recommendations are achieved by multiplying the affinity matrix $A$ and the similarity matrix $S$. The result is a ***recommendation score matrix*** $R$. We compute the ***top-k*** results for each user in the `recommend_k_items` function seen below.\n",
    "\n",
    "A full walkthrough of the SAR algorithm can be found [here](../02_model/sar_deep_dive.ipynb)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Took 0.3302565817721188 seconds for training.\n"
     ]
    }
   ],
   "source": [
    "with Timer() as train_time:\n",
    "    model.fit(train)\n",
    "\n",
    "print(\"Took {} seconds for training.\".format(train_time.interval))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Took 0.21034361701458693 seconds for prediction.\n"
     ]
    }
   ],
   "source": [
    "with Timer() as test_time:\n",
    "    top_k = model.recommend_k_items(test, remove_seen=True)\n",
    "\n",
    "print(\"Took {} seconds for prediction.\".format(test_time.interval))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>userID</th>\n",
       "      <th>itemID</th>\n",
       "      <th>prediction</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>1</td>\n",
       "      <td>204</td>\n",
       "      <td>3.313306</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>1</td>\n",
       "      <td>89</td>\n",
       "      <td>3.280465</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>1</td>\n",
       "      <td>11</td>\n",
       "      <td>3.233867</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>1</td>\n",
       "      <td>367</td>\n",
       "      <td>3.192575</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>1</td>\n",
       "      <td>423</td>\n",
       "      <td>3.131517</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   userID  itemID  prediction\n",
       "0       1     204    3.313306\n",
       "1       1      89    3.280465\n",
       "2       1      11    3.233867\n",
       "3       1     367    3.192575\n",
       "4       1     423    3.131517"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "top_k.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 2.3. Evaluate how well SAR performs\n",
    "\n",
    "We evaluate how well SAR performs for a few common ranking metrics provided in the `python_evaluation` module in reco_utils. We will consider the Mean Average Precision (MAP), Normalized Discounted Cumalative Gain (NDCG), Precision, and Recall for the top-k items per user we computed with SAR. User, item and rating column names are specified in each evaluation method."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval_map = map_at_k(test, top_k, col_user='userID', col_item='itemID', col_rating='rating', k=TOP_K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval_ndcg = ndcg_at_k(test, top_k, col_user='userID', col_item='itemID', col_rating='rating', k=TOP_K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval_precision = precision_at_k(test, top_k, col_user='userID', col_item='itemID', col_rating='rating', k=TOP_K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval_recall = recall_at_k(test, top_k, col_user='userID', col_item='itemID', col_rating='rating', k=TOP_K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Model:\t\n",
      "Top K:\t10\n",
      "MAP:\t0.110591\n",
      "NDCG:\t0.382461\n",
      "Precision@K:\t0.330753\n",
      "Recall@K:\t0.176385\n"
     ]
    }
   ],
   "source": [
    "print(\"Model:\\t\",\n",
    "      \"Top K:\\t%d\" % TOP_K,\n",
    "      \"MAP:\\t%f\" % eval_map,\n",
    "      \"NDCG:\\t%f\" % eval_ndcg,\n",
    "      \"Precision@K:\\t%f\" % eval_precision,\n",
    "      \"Recall@K:\\t%f\" % eval_recall, sep='\\n')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>userID</th>\n",
       "      <th>itemID</th>\n",
       "      <th>rating</th>\n",
       "      <th>timestamp</th>\n",
       "      <th>prediction</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>876</td>\n",
       "      <td>523</td>\n",
       "      <td>5.0</td>\n",
       "      <td>879428378</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>876</td>\n",
       "      <td>529</td>\n",
       "      <td>4.0</td>\n",
       "      <td>879428451</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>876</td>\n",
       "      <td>174</td>\n",
       "      <td>4.0</td>\n",
       "      <td>879428378</td>\n",
       "      <td>0.353567</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>876</td>\n",
       "      <td>276</td>\n",
       "      <td>4.0</td>\n",
       "      <td>879428354</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>876</td>\n",
       "      <td>288</td>\n",
       "      <td>3.0</td>\n",
       "      <td>879428101</td>\n",
       "      <td>NaN</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   userID  itemID  rating  timestamp  prediction\n",
       "0     876     523     5.0  879428378         NaN\n",
       "1     876     529     4.0  879428451         NaN\n",
       "2     876     174     4.0  879428378    0.353567\n",
       "3     876     276     4.0  879428354         NaN\n",
       "4     876     288     3.0  879428101         NaN"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Now let's look at the results for a specific user\n",
    "user_id = 876\n",
    "\n",
    "ground_truth = test[test['userID']==user_id].sort_values(by='rating', ascending=False)[:TOP_K]\n",
    "prediction = model.recommend_k_items(pd.DataFrame(dict(userID=[user_id])), remove_seen=True) \n",
    "pd.merge(ground_truth, prediction, on=['userID', 'itemID'], how='left')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Above, we see that one of the highest rated items from the test set was recovered by the model's top-k recommendations, however the others were not. Offline evaluations are difficult as they can only use what was seen previously in the test set and may not represent the user's actual preferences across the entire set of items. Adjustments to how the data is split, algorithm is used and hyper-parameters can improve the results here. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/papermill.record+json": {
       "map": 0.11059057578638949
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/papermill.record+json": {
       "ndcg": 0.3824612290501957
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/papermill.record+json": {
       "precision": 0.33075291622481445
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/papermill.record+json": {
       "recall": 0.1763854474342893
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/papermill.record+json": {
       "train_time": 0.284792423248291
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/papermill.record+json": {
       "test_time": 0.1463017463684082
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Record results with papermill for tests - ignore this cell\n",
    "pm.record(\"map\", eval_map)\n",
    "pm.record(\"ndcg\", eval_ndcg)\n",
    "pm.record(\"precision\", eval_precision)\n",
    "pm.record(\"recall\", eval_recall)\n",
    "pm.record(\"train_time\", train_time.interval)\n",
    "pm.record(\"test_time\", test_time.interval)"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "kernelspec": {
   "display_name": "Python 3",
   "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.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}