notebooks/00_quick_start/sar_single_node_movielens.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# SAR Single Node on MovieLens (Python, CPU)\n",
    "\n",
    "SAR is a fast scalable adaptive algorithm for personalized recommendations based on user transaction history. It produces easily explainable / 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. \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 who have interacted with one item are also likely to have interacted with another. 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 matric 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": 11,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "System version: 3.6.0 | packaged by conda-forge | (default, Feb  9 2017, 14:36:55) \n",
      "[GCC 4.8.2 20140120 (Red Hat 4.8.2-15)]\n",
      "Pandas version: 0.23.4\n"
     ]
    }
   ],
   "source": [
    "# set the environment path to find Recommenders\n",
    "import sys\n",
    "sys.path.append(\"../../\")\n",
    "import time\n",
    "import os\n",
    "import itertools\n",
    "import pandas as pd\n",
    "import papermill as pm\n",
    "\n",
    "from reco_utils.recommender.sar.sar_singlenode import SARSingleNode\n",
    "from reco_utils.dataset import movielens\n",
    "from reco_utils.dataset.python_splitters import python_random_split\n",
    "from reco_utils.evaluation.python_evaluation import map_at_k, ndcg_at_k, precision_at_k, recall_at_k\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": 12,
   "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": 13,
   "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>MovieId</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  MovieId  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": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "data = movielens.load_pandas_df(\n",
    "    size=MOVIELENS_DATA_SIZE,\n",
    "    header=['UserId','MovieId','Rating','Timestamp']\n",
    ")\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 utilize the provided `python_random_split` function to split into `train` and `test` datasets randomly at a 80/20 ratio."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [],
   "source": [
    "train, test = python_random_split(data)"
   ]
  },
  {
   "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",
    "In order to use SAR, we need to hash users and items and set an index in order for SAR matrix operations to work. First we instantiate SAR using the reference implementation provided in `SARSingleNode`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "header = {\n",
    "    \"col_user\": \"UserId\",\n",
    "    \"col_item\": \"MovieId\",\n",
    "    \"col_rating\": \"Rating\",\n",
    "    \"col_timestamp\": \"Timestamp\",\n",
    "}\n",
    "\n",
    "model = SARSingleNode(\n",
    "    remove_seen=True, similarity_type=\"jaccard\", \n",
    "    time_decay_coefficient=30, time_now=None, timedecay_formula=True, **header\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will hash users and items to smaller continuous space.\n",
    "This is an ordered set - it's discrete, but contiguous.\n",
    "This helps keep the matrices we keep in memory as small as possible."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "unique_users = data[\"UserId\"].unique()\n",
    "unique_items = data[\"MovieId\"].unique()\n",
    "enumerate_items_1, enumerate_items_2 = itertools.tee(enumerate(unique_items))\n",
    "enumerate_users_1, enumerate_users_2 = itertools.tee(enumerate(unique_users))\n",
    "\n",
    "item_map_dict = {x: i for i, x in enumerate_items_1}\n",
    "user_map_dict = {x: i for i, x in enumerate_users_1}\n",
    "# The reverse of the dictionary above - array index to actual ID\n",
    "index2user = dict(enumerate_users_2)\n",
    "index2item = dict(enumerate_items_2)\n",
    "\n",
    "# We need to index the train and test sets for SAR matrix operations to work\n",
    "model.set_index(unique_users, unique_items, user_map_dict, item_map_dict, index2user, index2item)\n",
    "\n",
    "preprocess_time = time.time() - start_time"
   ]
  },
  {
   "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_modeling/sar_educational_walkthrough.ipynb)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Collecting user affinity matrix...\n",
      "Calculating time-decayed affinities...\n",
      "Creating index columns...\n",
      "Building user affinity sparse matrix...\n",
      "Calculating item cooccurrence...\n",
      "Calculating item similarity...\n",
      "Calculating jaccard...\n",
      "Calculating recommendation scores...\n",
      "done training\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Took 0.5829987525939941 seconds for training.\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "model.fit(train)\n",
    "\n",
    "train_time = time.time() - start_time + preprocess_time\n",
    "print(\"Took {} seconds for training.\".format(train_time))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "Converting to dense matrix...\n",
      "Removing seen items...\n",
      "Getting top K...\n",
      "Select users from the test set\n",
      "Creating output dataframe...\n",
      "Formatting output\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Took 0.13302063941955566 seconds for prediction.\n"
     ]
    }
   ],
   "source": [
    "start_time = time.time()\n",
    "\n",
    "top_k = model.recommend_k_items(test)\n",
    "\n",
    "test_time = time.time() - start_time\n",
    "print(\"Took {} seconds for prediction.\".format(test_time))\n",
    "\n",
    "# TODO: remove this call when the model returns same type as input\n",
    "top_k['UserId'] = pd.to_numeric(top_k['UserId'])\n",
    "top_k['MovieId'] = pd.to_numeric(top_k['MovieId'])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "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>MovieId</th>\n",
       "      <th>prediction</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>600</td>\n",
       "      <td>69</td>\n",
       "      <td>12.984131</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>600</td>\n",
       "      <td>423</td>\n",
       "      <td>12.991756</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>600</td>\n",
       "      <td>183</td>\n",
       "      <td>13.106912</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>600</td>\n",
       "      <td>89</td>\n",
       "      <td>13.163791</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>600</td>\n",
       "      <td>144</td>\n",
       "      <td>13.489795</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   UserId  MovieId  prediction\n",
       "0     600       69   12.984131\n",
       "1     600      423   12.991756\n",
       "2     600      183   13.106912\n",
       "3     600       89   13.163791\n",
       "4     600      144   13.489795"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "display(top_k.head())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5. Evaluate how well SAR performs \n",
    "\n",
    "We evaluate how well SAR performs with for a few common ranking metrics provided in the `PythonRankingEvaluation` classs in utilities. 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."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval_map = map_at_k(test, top_k, col_user=\"UserId\", col_item=\"MovieId\", \n",
    "                    col_rating=\"Rating\", col_prediction=\"prediction\", \n",
    "                    relevancy_method=\"top_k\", k=TOP_K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval_ndcg = ndcg_at_k(test, top_k, col_user=\"UserId\", col_item=\"MovieId\", \n",
    "                      col_rating=\"Rating\", col_prediction=\"prediction\", \n",
    "                      relevancy_method=\"top_k\", k=TOP_K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval_precision = precision_at_k(test, top_k, col_user=\"UserId\", col_item=\"MovieId\", \n",
    "                                col_rating=\"Rating\", col_prediction=\"prediction\", \n",
    "                                relevancy_method=\"top_k\", k=TOP_K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "eval_recall = recall_at_k(test, top_k, col_user=\"UserId\", col_item=\"MovieId\", \n",
    "                          col_rating=\"Rating\", col_prediction=\"prediction\", \n",
    "                          relevancy_method=\"top_k\", k=TOP_K)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Model:\tsar_ref\n",
      "Top K:\t10\n",
      "MAP:\t0.105815\n",
      "NDCG:\t0.373197\n",
      "Precision@K:\t0.326617\n",
      "Recall@K:\t0.175957\n"
     ]
    }
   ],
   "source": [
    "print(\"Model:\\t\" + model.model_str,\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": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "application/papermill.record+json": {
       "map": 0.10581526176416436
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/papermill.record+json": {
       "ndcg": 0.373197254984399
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/papermill.record+json": {
       "precision": 0.3266171792152704
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/papermill.record+json": {
       "recall": 0.17595674338464226
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/papermill.record+json": {
       "train_time": 0.5829987525939941
      }
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "application/papermill.record+json": {
       "test_time": 0.13302063941955566
      }
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "# Record results with papermill for tests\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)\n",
    "pm.record(\"test_time\", test_time)"
   ]
  }
 ],
 "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.6.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}