05-minhash-rec.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# MinHash for recommendations\n",
    "\n",
    "In the [previous notebook](04-minhash.ipynb) we saw how MinHash can be used to approximate the similarity of sets. In this notebook we will see that MinHash can also be used to make personalised recommendations to users.\n",
    "\n",
    "We'll illustrate this technique using a data set which contains users' listening history from a music streaming service. If you're interested in how we generated the data, take a look at [this notebook](99a-data-generator.ipynb). "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "import os.path\n",
    "\n",
    "## Importing the data\n",
    "df = pd.read_parquet(os.path.join(\"data\", \"userdat1.parquet\"))\n",
    "print(df.shape)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The file contains three columns and over three million rows. Let's take a closer look at a sample of the data:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "df.sample(10, random_state=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The first column is an integer representing a user id, the second is an integer representing an artist name, and the third column is an integer indicating how many times the user listened to the artist. \n",
    "\n",
    "(It turns out that the artist and user ids are not currently stored as integers, but as strings instead. In the next cell we transform these to integers.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "df['artist'] = df['artist'].astype('int')\n",
    "df['user'] = df['user'].astype('int')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We take one pass through the data frame to identify the set of unique users and the set of unique artists. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "artists = df['artist'].unique()\n",
    "users = df['user'].unique()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"There are \", len(artists), \" artists and \", len(users), \" users in our data.\" , sep=\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also load in a dictionary which maps from the artist integers to artist names. We will use this dictionary to map from the integers, representing artist names, back into artist names. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pickle\n",
    "dartists = None\n",
    "with open(os.path.join(\"data\", \"dartists.pkl\"),\"rb\") as f:\n",
    "    dartists = pickle.load(f)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We group the data by user. From there we can see which artists a particular user has listened to:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "## grouping the data by user\n",
    "grouped_df = df.groupby(['user']) \n",
    "\n",
    "## extracting user1's data:\n",
    "user1 = grouped_df.get_group(1)\n",
    "user1.sample(10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `artist_names` function maps from the integers to the names of the artist, using the dictionary we loaded in earlier. The `top_k_listens` function returns the names of the $k$ artists a particular user has listened to most:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "def artist_names(artist_ints, artist_dic = dartists):\n",
    "    return [artist_dic[k] for k in artist_ints]\n",
    "\n",
    "\n",
    "def top_k_listens(listening_history, k=10):\n",
    "    \"\"\"extracts the k most listened to artists in a given listening history\"\"\"\n",
    "    top_k = listening_history.sort_values(by=\"plays\", ascending = False)[\"artist\"].head(k).values\n",
    "    return artist_names(top_k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "top_k_listens(user1, 10) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So that's how we see what a particular user has listened to, but how do we use this to make recommendations? \n",
    "\n",
    "MinHash provides gives us a way to summarise set in a fixed amount of memory. If we create a MinHash signature of users’ listening history, we can identify similar users by comparing minhash signatures. \n",
    "\n",
    "One way to generate a MinHash signature for a user's listening history would be to add every artist the user has listened to into the MinHash signature for that user. In practise this works fine, but can be slow when users have listened to a large number of artists. \n",
    "\n",
    "Instead, we will use a faster function which works by pre-computing the MinHash signature for each artist, then generating a user's MinHash signature by combining the MinHash signatures for all of the artists that user has listened to. The code can be found in [this helper file](./datasketching/minhash.py).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from datasketching.minhash import generate_minhashes_for\n",
    "from datasketching.minhash import LSHMinhash"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "mh_structs = LSHMinhash(32, 4) ## this is a MinHash signature with 32*4 = 128 Buckets. \n",
    "minhashes = generate_minhashes_for(grouped_df, \"user\", \"artist\", mh_structs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(len(minhashes))\n",
    "minhashes[0][1] ## this is a minhash object. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can compare MinHash signatures with the 'similarity' function. This returns a number between 0 and 1, where a `1` denotes identical signatures, and a `0` means that no corresponding buckets of the MinHash signatures hold the same value. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "minhashes[2][1].similarity(minhashes[1][1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using the similarity, we can identify the set of users who are _most similar_ to the user we want to make recommendations for:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "sim = []\n",
    "for i in range(len(minhashes)):\n",
    "    sim.append(minhashes[1][1].similarity(minhashes[i][1]))\n",
    "    \n",
    "similar = set(sorted(sim, reverse = True)[1:10])\n",
    "similar_users = ([i for i, e in enumerate(sim) if e in similar])\n",
    "for j in similar_users:\n",
    "    print(users[j])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "From there, we make recommendations by looking at the top artists listened to by all these users. We remove any artists user 1 already listened to, and recommend the others. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "unheard = []\n",
    "for u in similar_users:\n",
    "    u_dat = grouped_df.get_group(users[u])\n",
    "    unheard = unheard + list(top_k_listens(u_dat, 2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "unheard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "So that's just a quick example of how we can use minhash to identify artists we should recommend to a particular user. This method works fine on a small number of users, but falls into dificulty when the number of users grows, and the number of users for which we want to make recommendations for grows. \n",
    "\n",
    "Let's plot the time required to compare users:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "npairs = [10, 25, 50, 75, 100, 300, 500, 750, 1000, 2000, 3100] #number of users to compare\n",
    "times = []\n",
    "for pairs in npairs:\n",
    "    start = time.time()\n",
    "    sim=[]\n",
    "    for i in range(1, pairs):\n",
    "        for j in range((i+1), pairs):\n",
    "            sim.append(minhashes[i][1].similarity(minhashes[j][1]))\n",
    "    end = time.time()\n",
    "    times.append((pairs, end-start))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import altair as alt\n",
    "\n",
    "times_df = pd.DataFrame.from_records(times)\n",
    "times_df.rename(columns = {0:\"nusers\", 1:\"time (s)\"}, inplace = True)\n",
    "alt.renderers.enable('notebook')\n",
    "alt.Chart(times_df). mark_line().encode(x=\"nusers\", y=\"time (s)\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Locality-Sensitive Minhash\n",
    "\n",
    "As the graph above shows, one big disadvantage of using Minhash signatures to identify similar users is the number of pairwise comparisons which must be made to determine similarity - Comparing 500 users takes less than half a second, but it takes nearly 8 seconds to compare 3000 users. This quadratic growth means that extensively comparing all users is not possible for real applications of this method with a non-trivial number of users. \n",
    "\n",
    "Locality-sensitive Minhash is a technique we can use to identify candidate pairs of similar users for a much smaller computational cost. The MinHash signature is split into subsets, and if two users have identical signatures in ANY of the subsets these users are considered a _candidate pair_. From there you can go and compute their approximate Jaccard index, or similarity, using the full minhash signatures, to determine just how similar they are, and decide if you want to make recommendations. \n",
    "\n",
    "In practice, the subsets into which we split the minhash signature are known as 'bands'. The contents of the bands are hashed to a set of buckets. Any two users who have at least one band which hashes to the same bucket are a candidate pair. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "bands = [defaultdict(lambda: list()) for i in range(len(mh_structs.lsh_keys()))]\n",
    "\n",
    "for ind, lshm in minhashes:\n",
    "    for idx, key in enumerate(lshm.lsh_keys()):\n",
    "        bands[idx][key % (1 << 14)].append(ind)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We've made a dictionary of values for each band, where the keys correspond to buckets, and the values are indexes of minhash signature which mapped to that bucket. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import itertools\n",
    "candidates = []\n",
    "for b in bands:\n",
    "    for it in b.items():\n",
    "        if len(it[1])>1:\n",
    "            candidates.extend(list(itertools.combinations(it[1],2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`candidates` holds an extensive list of all candidate pairs of similar users. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# extract set of users who are similar to _user_\n",
    "def candidate_pairs(user, full_candidate_list):\n",
    "    return set([y for x in [tup for tup in full_candidate_list if user in tup] for y in x]) - set([user])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "len(candidate_pairs(1, full_candidate_list=candidates))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "By using locality-sensitive MinHash we have reduced the number of pairwise comparisons needed from 3099 to 51, for user 1. "
   ]
  }
 ],
 "metadata": {
  "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.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}