02_MarkovChain.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Table of contents\n",
    "\n",
    "1. [Load the dataset](#load_the_dataset)\n",
    "2. [Split the dataset](#split_the_dataset)\n",
    "3. [Fitting the recommender](#fitting)\n",
    "4. [Sequential evaluation](#seq_evaluation)  \n",
    "    4.1 [Evaluation with sequentially revaeled user profiles](#eval_seq_rev)  \n",
    "    4.2 [Evaluation with \"static\" user profiles](#eval_static)  \n",
    "5. [Analysis of next-item recommendation](#next-item)  \n",
    "    5.1 [Evaluation with different recommendation list lengths](#next-item_list_length)  \n",
    "    5.2 [Evaluation with different user profile lengths](#next-item_profile_length)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import pandas as pd\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sars_tutorial.util.data_utils import create_seq_db_filter_top_k, sequences_to_spfm_format\n",
    "from sars_tutorial.util.split import last_session_out_split\n",
    "from sars_tutorial.util.metrics import precision, recall, mrr\n",
    "from sars_tutorial.util import evaluation\n",
    "from sars_tutorial.recommenders.MixedMarkovRecommender import MixedMarkovChainRecommender"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import datetime"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def get_test_sequences(test_data, given_k):\n",
    "    # we can run evaluation only over sequences longer than abs(LAST_K)\n",
    "    test_sequences = test_data.loc[test_data['sequence'].map(len) > abs(given_k), 'sequence'].values\n",
    "    return test_sequences"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='load_the_dataset'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Load the dataset\n",
    "\n",
    "For this hands-on session we will use a dataset of user-listening sessions crawled from [last.fm](https://www.last.fm/). In detail, we will use a subset of the following dataset:\n",
    "\n",
    "* 30Music listening and playlists dataset, Turrin et al., ACM RecSys 2015 ([paper](https://home.deib.polimi.it/pagano/portfolio/papers/30Musiclisteningandplaylistsdataset.pdf))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# unzip the dataset, if you haven't already done it\n",
    "# ! unzip datasets/sessions.zip -d datasets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset_path = 'datasets/sessions.csv'\n",
    "# load this sample if you experience a severe slowdown with the previous dataset\n",
    "#dataset_path = 'datasets/sessions_sample_10.csv'\n",
    "\n",
    "# for the sake of speed, let's keep only the top-1k most popular items in the last month\n",
    "dataset = create_seq_db_filter_top_k(path=dataset_path, topk=1000, last_months=1) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's see at how the dataset looks like"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset.head()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's show some statistics about the dataset"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import Counter\n",
    "cnt = Counter()\n",
    "dataset.sequence.map(cnt.update);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sequence_length = dataset.sequence.map(len).values\n",
    "n_sessions_per_user = dataset.groupby('user_id').size()\n",
    "\n",
    "print('Number of items: {}'.format(len(cnt)))\n",
    "print('Number of users: {}'.format(dataset.user_id.nunique()))\n",
    "print('Number of sessions: {}'.format(len(dataset)) )\n",
    "\n",
    "print('\\nSession length:\\n\\tAverage: {:.2f}\\n\\tMedian: {}\\n\\tMin: {}\\n\\tMax: {}'.format(\n",
    "    sequence_length.mean(), \n",
    "    np.quantile(sequence_length, 0.5), \n",
    "    sequence_length.min(), \n",
    "    sequence_length.max()))\n",
    "\n",
    "print('Sessions per user:\\n\\tAverage: {:.2f}\\n\\tMedian: {}\\n\\tMin: {}\\n\\tMax: {}'.format(\n",
    "    n_sessions_per_user.mean(), \n",
    "    np.quantile(n_sessions_per_user, 0.5), \n",
    "    n_sessions_per_user.min(), \n",
    "    n_sessions_per_user.max()))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('Most popular items: {}'.format(cnt.most_common(5)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='split_the_dataset'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 2. Split the dataset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For simplicity, let's split the dataset by assigning the **last session** of every user to the **test set**, and **all the previous** ones to the **training set**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "train_data, test_data = last_session_out_split(dataset)\n",
    "print(\"Train sessions: {} - Test sessions: {}\".format(len(train_data), len(test_data)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='fitting'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 3. Fitting the recommender\n",
    "\n",
    "Here we fit the recommedation algorithm over the sessions in the training set.  \n",
    "This recommender is based on the `MarkovChainRecommender` implemented from:\n",
    "\n",
    "_Shani, Guy, David Heckerman, and Ronen I. Brafman. \"An MDP-based recommender system.\" Journal of Machine Learning Research 6, no. Sep (2005): 1265-1295. Chapter 3-4_\n",
    "\n",
    "This recommender computes the item transition matrices for any Markov Chain having order in `[min_order, max_order]`. Each individual Markov Chain model employes some heristics like skipping or clustering to deal better with data sparsity. Recommendations are generated by sorting items by their transition probability to being next, given the user profile. The scores coming from different MC are weighted _inversely_ wrt to their order.\n",
    "\n",
    "The class `MixedMarkovChainRecommender` has the following initialization hyper-parameters:\n",
    "* `min_order`: the minimum order of the Mixed Markov Chain\n",
    "* `max_order`: the maximum order of the Mixed Markov Chain\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# You can try with max_order=2 or higher too, but it will take some time to complete though due to slow heristic computations\n",
    "recommender = MixedMarkovChainRecommender(min_order=1, \n",
    "                                          max_order=1)\n",
    "recommender.fit(train_data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='seq_evaluation'></a>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 4. Sequential evaluation\n",
    "\n",
    "In the evaluation of sequence-aware recommenders, each sequence in the test set is split into:\n",
    "- the _user profile_, used to compute recommendations, is composed by the first *k* events in the sequence;\n",
    "- the _ground truth_, used for performance evaluation, is composed by the remainder of the sequence.\n",
    "\n",
    "In the cells below, you can control the dimension of the _user profile_ by assigning a **positive** value to `GIVEN_K`, which correspond to the number of events from the beginning of the sequence that will be assigned to the initial user profile. This ensures that each user profile in the test set will have exactly the same initial size, but the size of the ground truth will change for every sequence.\n",
    "\n",
    "Alternatively, by assigning a **negative** value to `GIVEN_K`, you will set the initial size of the _ground truth_. In this way the _ground truth_ will have the same size for all sequences, but the dimension of the user profile will differ."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "METRICS = {'precision':precision, \n",
    "           'recall':recall,\n",
    "           'mrr': mrr}\n",
    "TOPN = 10 # length of the recommendation list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='eval_seq_rev'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.1 Evaluation with sequentially revealed user-profiles\n",
    "\n",
    "Here we evaluate the quality of the recommendations in a setting in which user profiles are revealed _sequentially_.\n",
    "\n",
    "The _user profile_ starts from the first `GIVEN_K` events (or, alternatively, from the last `-GIVEN_K` events if `GIVEN_K<0`).  \n",
    "The recommendations are evaluated against the next `LOOK_AHEAD` events (the _ground truth_).  \n",
    "The _user profile_ is next expanded to the next `STEP` events, the ground truth is scrolled forward accordingly, and the evaluation continues until the sequence ends.\n",
    "\n",
    "In typical **next-item recommendation**, we start with `GIVEN_K=1`, generate a set of **alternatives** that will evaluated against the next event in the sequence (`LOOK_AHEAD=1`), move forward of one step (`STEP=1`) and repeat until the sequence ends.\n",
    "\n",
    "You can set the `LOOK_AHEAD='all'` to see what happens if you had to recommend a **whole sequence** instead of a set of a set of alternatives to a user.\n",
    "\n",
    "NOTE: Metrics are averaged over each sequence first, then averaged over all test sequences.\n",
    "\n",
    "** (TODO) Try out with different evaluation settings to see how the recommandation quality changes. **\n",
    "\n",
    "\n",
    "![](gifs/sequential_eval.gif)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# GIVEN_K=1, LOOK_AHEAD=1, STEP=1 corresponds to the classical next-item evaluation\n",
    "GIVEN_K = 1\n",
    "LOOK_AHEAD = 1\n",
    "STEP=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_sequences = get_test_sequences(test_data, GIVEN_K)\n",
    "print('{} sequences available for evaluation'.format(len(test_sequences)))\n",
    "\n",
    "results = evaluation.sequential_evaluation(recommender,\n",
    "                                           test_sequences=test_sequences,\n",
    "                                           given_k=GIVEN_K,\n",
    "                                           look_ahead=LOOK_AHEAD,\n",
    "                                           evaluation_functions=METRICS.values(),\n",
    "                                           top_n=TOPN,\n",
    "                                           scroll=True,  # scrolling averages metrics over all profile lengths\n",
    "                                           step=STEP)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('Sequential evaluation (GIVEN_K={}, LOOK_AHEAD={}, STEP={})'.format(GIVEN_K, LOOK_AHEAD, STEP))\n",
    "for mname, mvalue in zip(METRICS.keys(), results):\n",
    "    print('\\t{}@{}: {:.4f}'.format(mname, TOPN, mvalue))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='eval_static'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 4.2 Evaluation with \"static\" user-profiles\n",
    "\n",
    "Here we evaluate the quality of the recommendations in a setting in which user profiles are instead _static_.\n",
    "\n",
    "The _user profile_ starts from the first `GIVEN_K` events (or, alternatively, from the last `-GIVEN_K` events if `GIVEN_K<0`).  \n",
    "The recommendations are evaluated against the next `LOOK_AHEAD` events (the _ground truth_).  \n",
    "\n",
    "The user profile is *not extended* and the ground truth *doesn't move forward*.\n",
    "This allows to obtain \"snapshots\" of the recommendation performance for different user profile and ground truth lenghts.\n",
    "\n",
    "Also here you can set the `LOOK_AHEAD='all'` to see what happens if you had to recommend a **whole sequence** instead of a set of a set of alternatives to a user.\n",
    "\n",
    "**(TODO) Try out with different evaluation settings to see how the recommandation quality changes.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GIVEN_K = 1\n",
    "LOOK_AHEAD = 'all'\n",
    "STEP=1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_sequences = get_test_sequences(test_data, GIVEN_K)\n",
    "print('{} sequences available for evaluation'.format(len(test_sequences)))\n",
    "\n",
    "results = evaluation.sequential_evaluation(recommender,\n",
    "                                           test_sequences=test_sequences,\n",
    "                                           given_k=GIVEN_K,\n",
    "                                           look_ahead=LOOK_AHEAD,\n",
    "                                           evaluation_functions=METRICS.values(),\n",
    "                                           top_n=TOPN,\n",
    "                                           scroll=False  # notice that scrolling is disabled!\n",
    "                                          )  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print('Sequential evaluation (GIVEN_K={}, LOOK_AHEAD={}, STEP={})'.format(GIVEN_K, LOOK_AHEAD, STEP))\n",
    "for mname, mvalue in zip(METRICS.keys(), results):\n",
    "    print('\\t{}@{}: {:.4f}'.format(mname, TOPN, mvalue))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='next-item'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5. Analysis of next-item recommendation\n",
    "\n",
    "Here we propose to analyse the performance of the recommender system in the scenario of *next-item recommendation* over the following dimensions:\n",
    "\n",
    "* the *length* of the **recommendation list**, and\n",
    "* the *length* of the **user profile**.\n",
    "\n",
    "NOTE: This evaluation is by no means exhaustive, as different the hyper-parameters of the recommendation algorithm should be *carefully tuned* before drawing any conclusions. Unfortunately, given the time constraints for this tutorial, we had to leave hyper-parameter tuning out. A very useful reference about careful evaluation of (session-based) recommenders can be found at:\n",
    "\n",
    "*  Evaluation of Session-based Recommendation Algorithms, Ludewig and Jannach, 2018 ([paper](https://arxiv.org/abs/1803.09587))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='next-item_list_length'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.1 Evaluation for different recommendation list lengths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "GIVEN_K = 1\n",
    "LOOK_AHEAD = 1\n",
    "STEP = 1\n",
    "topn_list = [1, 5, 10, 20, 50, 100]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ensure that all sequences have the same minimum length \n",
    "test_sequences = get_test_sequences(test_data, GIVEN_K)\n",
    "print('{} sequences available for evaluation'.format(len(test_sequences)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "res_list = []\n",
    "\n",
    "for topn in topn_list:\n",
    "    print('Evaluating recommendation lists with length: {}'.format(topn))\n",
    "    res_tmp = evaluation.sequential_evaluation(recommender,\n",
    "                                               test_sequences=test_sequences,\n",
    "                                               given_k=GIVEN_K,\n",
    "                                               look_ahead=LOOK_AHEAD,\n",
    "                                               evaluation_functions=METRICS.values(),\n",
    "                                               top_n=topn,\n",
    "                                               scroll=True,  # here we average over all profile lengths\n",
    "                                               step=STEP)\n",
    "    mvalues = list(zip(METRICS.keys(), res_tmp))\n",
    "    res_list.append((topn, mvalues))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# show separate plots per metric\n",
    "fig, axes = plt.subplots(nrows=1, ncols=len(METRICS), figsize=(15,5))\n",
    "res_list_t = list(zip(*res_list))\n",
    "for midx, metric in enumerate(METRICS):\n",
    "    mvalues = [res_list_t[1][j][midx][1] for j in range(len(res_list_t[1]))]\n",
    "    ax = axes[midx]\n",
    "    ax.plot(topn_list, mvalues)\n",
    "    ax.set_title(metric)\n",
    "    ax.set_xticks(topn_list)\n",
    "    ax.set_xlabel('List length')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<a id='next-item_profile_length'></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2 Evaluation for different user profile lengths"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "given_k_list = [1, 2, 3, 4]\n",
    "LOOK_AHEAD = 1\n",
    "STEP = 1\n",
    "TOPN = 20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ensure that all sequences have the same minimum length \n",
    "test_sequences = get_test_sequences(test_data, max(given_k_list))\n",
    "print('{} sequences available for evaluation'.format(len(test_sequences)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "res_list = []\n",
    "\n",
    "for gk in given_k_list:\n",
    "    print('Evaluating profiles having length: {}'.format(gk))\n",
    "    res_tmp = evaluation.sequential_evaluation(recommender,\n",
    "                                               test_sequences=test_sequences,\n",
    "                                               given_k=gk,\n",
    "                                               look_ahead=LOOK_AHEAD,\n",
    "                                               evaluation_functions=METRICS.values(),\n",
    "                                               top_n=TOPN,\n",
    "                                               scroll=False,  # here we stop at each profile length\n",
    "                                               step=STEP)\n",
    "    mvalues = list(zip(METRICS.keys(), res_tmp))\n",
    "    res_list.append((gk, mvalues))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# show separate plots per metric\n",
    "fig, axes = plt.subplots(nrows=1, ncols=len(METRICS), figsize=(15,5))\n",
    "res_list_t = list(zip(*res_list))\n",
    "for midx, metric in enumerate(METRICS):\n",
    "    mvalues = [res_list_t[1][j][midx][1] for j in range(len(res_list_t[1]))]\n",
    "    ax = axes[midx]\n",
    "    ax.plot(given_k_list, mvalues)\n",
    "    ax.set_title(metric)\n",
    "    ax.set_xticks(given_k_list)\n",
    "    ax.set_xlabel('Profile length')"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "srs",
   "language": "python",
   "name": "srs"
  },
  "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.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}