01_FrequentSeqMining.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 util.data_utils import create_seq_db_filter_top_k, sequences_to_spfm_format\n",
    "from util.split import last_session_out_split\n",
    "from util.metrics import precision, recall, mrr\n",
    "from util import evaluation\n",
    "from recommenders.FSMRecommender import FSMRecommender"
   ]
  },
  {
   "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 ssome 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",
    "\n",
    "This algorithm extract Frequent Sequential Patterns from all the training sequences. Patterns are having support lower than `minsup` are discarded (support = # occurrences of a pattern in the traning data).  \n",
    "Recommendations are then generated by looking for patterns having a _prefix_ corresponding to the last `[max_context, min_context]` elements in the user profile, taken in order. Matches are then sorted by decreasing _confidence_ score (ratio between the support of the matched rule and the support of the context). Matches having confidence below `minconf` are discarded.\n",
    "\n",
    "The class `FSMRecommender` has the following initialization hyper-parameters:\n",
    "* `minsup`: the minimum support threshold. It is interpreted as relative count if in \\[0-1\\], otherwise as an absolute count. NOTE: Relative count required for training with SPFM (faster).\n",
    "* `minconf`: the minimum confidence threshold. Use to filter irrelevent recommendations.\n",
    "* `max_context`: the maximum number of items in the user profile (starting from the last) that will be used for lookup in the database of frequent sequences.\n",
    "* `min_context`: the minimum number of items in the user profile (starting from the last) that will be used for lookup in the database of frequent sequences.\n",
    "* `spmf_path`: path to SPMF jar file. If provided, SPFM library will be used for pattern extraction (algorithm: Prefix Span). Otherwise, use pymining, which can be significantly slower depending on the sequence database size.\n",
    "* `db_path`: path to the sequence database file\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# convert the training sequences to SPFM format first\n",
    "db_path = 'tmp/sequences.txt'\n",
    "sequences_to_spfm_format(train_data['sequence'], tmp_path=db_path)\n",
    "\n",
    "# then we instantiate and fit the recommender\n",
    "recommender = FSMRecommender(minsup=0.002, \n",
    "                             minconf=0.1, \n",
    "                             min_context=1, \n",
    "                             max_context=10,\n",
    "                             spmf_path='spmf/spmf.jar',\n",
    "                             db_path=db_path)\n",
    "# calling fit() without arguments to use SPFM and the sequences stored in db_path\n",
    "recommender.fit()\n",
    "# calling fit() with an argument will use pymining.seqmining for pattern extraction (slower, MANDATORY ON BIDNDER) \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=5 # 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')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}