notebooks/12_Recommender_Systems.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Movie Recommendations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    ">### Today\n",
    ">\n",
    ">- [The MovieLens 1M Dataset](#The-MovieLens-1M-Dataset)\n",
    ">\n",
    ">\n",
    ">- [Similarity Measures](#Similarity-Measures)\n",
    ">\n",
    ">\n",
    ">- [User-to-user kNN](#User-to-user-kNN)\n",
    ">\n",
    ">\n",
    ">- [Item-to-item kNN](#Item-to-item-kNN)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "\n",
    "from itertools import product, combinations\n",
    "from operator import itemgetter\n",
    "from collections import defaultdict\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "from scipy.spatial import distance\n",
    "from sklearn.metrics import mean_absolute_error"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The MovieLens 1M Dataset\n",
    "\n",
    "The MovieLens 1M dataset has been developed by the members of the [GroupLens](https://grouplens.org/) lab in the Department of Computer Science and Engineering at the University of Minnesota."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The MovieLens 1M dataset in brief:\n",
    "\n",
    "- Ratings: 1 million\n",
    "- Users: 6,040\n",
    "- Rated Movies: 3,592\n",
    "- Rating Scale: {1, ... , 5}\n",
    "- Additional information on the users: gender, age range, occupation, zip-code\n",
    "- Additional infomation on the movies: genre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(A zipped version of this dataset is available in the data folder, or you can [download it](https://grouplens.org/datasets/movielens/1m/) and unzip it)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The dataset is composed by three files:\n",
    "\n",
    "- `movies.dat`, providing information about the rated movies \n",
    "    - it follows the format `MovieID::Title::Genres`\n",
    "    \n",
    "\n",
    "- `users.dat`, providing information about the users\n",
    "    - it follows the format `UserID::Gender::Age::Occupation::Zip-code`\n",
    "    - each user has at least 20 ratings\n",
    "\n",
    "\n",
    "- `ratings.dat`, encoding the ratings\n",
    "    - it follows the format `UserID::MovieID::Rating::Timestamp`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "id2movie = dict()\n",
    "\n",
    "with open(\"data/ml-1m/movies.dat\", \"r\", encoding='windows-1252') as infile:\n",
    "    for line in infile:\n",
    "        movieId, movie, _ = line.split(\"::\")\n",
    "        id2movie[int(movieId)] = movie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no. of movies: 3883\n",
      "(1, 'Toy Story (1995)')\n",
      "(2, 'Jumanji (1995)')\n",
      "(3, 'Grumpier Old Men (1995)')\n"
     ]
    }
   ],
   "source": [
    "print(\"no. of movies:\", len(id2movie))\n",
    "for i in list(id2movie.items())[:3]:\n",
    "    print(i)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "user2movies_ratings = defaultdict(dict)\n",
    "\n",
    "with open(\"data/ml-1m/ratings.dat\", \"r\", encoding='utf-8') as infile:\n",
    "    for line in infile:\n",
    "        userId, movieId, rating = [int(el) for el in line.split(\"::\")[:3]]\n",
    "        user2movies_ratings[userId][movieId] = rating"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no. of users: 6040\n",
      "(1, {1193: 5, 661: 3, 914: 3, 3408: 4, 2355: 5, 1197: 3, 1287: 5, 2804: 5, 594: 4, 919: 4, 595: 5, 938: 4, 2398: 4, 2918: 4, 1035: 5, 2791: 4, 2687: 3, 2018: 4, 3105: 5, 2797: 4, 2321: 3, 720: 3, 1270: 5, 527: 5, 2340: 3, 48: 5, 1097: 4, 1721: 4, 1545: 4, 745: 3, 2294: 4, 3186: 4, 1566: 4, 588: 4, 1907: 4, 783: 4, 1836: 5, 1022: 5, 2762: 4, 150: 5, 1: 5, 1961: 5, 1962: 4, 2692: 4, 260: 4, 1028: 5, 1029: 5, 1207: 4, 2028: 5, 531: 4, 3114: 4, 608: 4, 1246: 4})\n"
     ]
    }
   ],
   "source": [
    "print(\"no. of users:\", len(user2movies_ratings))\n",
    "print(list(user2movies_ratings.items())[0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "no. of ratings: 1000209\n"
     ]
    }
   ],
   "source": [
    "print(\"no. of ratings:\",sum([len(v) for v in user2movies_ratings.values()]))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "\n",
    "Explore the dataset:\n",
    "\n",
    "- (optional) Turn the dataset into a Pandas data frames if you prefer.\n",
    "\n",
    "\n",
    "- What is the average rating?\n",
    "\n",
    "\n",
    "- Which are the top-rated movies? And which are the lowest-rated ones?\n",
    "\n",
    "\n",
    "- What are the average ratings for men and women?\n",
    "\n",
    "\n",
    "- Which movies received the highest rates from men? Which ones from women?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Use case for k-NN\n",
    "\n",
    "In the following exercise we will use the **k Nearest Neighbors algorithm** (k-NN)\n",
    "\n",
    "- to model the ratings given by user `4447` (982 ratings)\n",
    "    \n",
    "\n",
    "- .. to the following movies:\n",
    "\n",
    "    - `Silence of the Lambs, The (1991)` : id = `593`\n",
    "    - `Raiders of the Lost Ark (1981)` : id = `1198`\n",
    "    - `Back to the Future (1985)`: id = `1270`"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "target_movies = [593, 1198, 1270]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# First, let's remove our target ratings from the dataset\n",
    "target_ratings = dict([(i, user2movies_ratings[4447].pop(i)) for i in target_movies])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{593: 4, 1198: 2, 1270: 3}"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "target_ratings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Similarity Measures\n",
    "\n",
    "- Similarity/Distance measures are used in many applications (e.g., clustering, classification, word modeling) to measure how two objects are similar/different.\n",
    "\n",
    "\n",
    "- Distances/Similarities are described by a single scalar, the value of which depends on three factors:\n",
    "    - the properties of the **object** \n",
    "    - the **representation** choosen for the objects\n",
    "    - the properites of the **measure**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In order to be qualifies as a **metric**, a distance/similarity measure must satisfy the following four conditions:\n",
    "\n",
    "- The distance between any points is always **nonegative**\n",
    "\n",
    "\n",
    "- The distance between two points equals $0$ iff two objects are **identical**\n",
    "\n",
    "\n",
    "- **Symmetry**, i.e., $d(x,y) = d(y,x)$\n",
    "\n",
    "\n",
    "- **Triangular inequality**, i.e., $d(x, z) \\leq d(x, y) + d(y, z)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Euclidean similarity**\n",
    "\n",
    "- Euclidean distance is the ordinary straight-line distance between two points\n",
    "\n",
    "\n",
    "- Distance is calculated by using the Pythagorean theorem\n",
    "\n",
    "\n",
    "- Distance can be transformed into a similarity measure by summing 1 to the distance and inverting it"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$sim_{\\ euclidean} (p,q)=\\frac{1}{dist(p,q)} = \\frac{1}{1 + \\sqrt{\\sum_{i = 1}^n (p_i - q_i)^2}}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def euclidean_similarity(p, q):\n",
    "    dist = math.sqrt(sum((pi-qi)**2 for pi,qi in zip(p, q)))\n",
    "    sim = 1 / (1+dist)\n",
    "    return sim    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Manhattan similarity**\n",
    "\n",
    "- The Manhattan (or taxicab, cityblock, rectilinear, $L_1$) distance between two points is calculated as the sum of the absolute distances of their Cartesian coordinates\n",
    "\n",
    "\n",
    "- Similar to the Euclidean distance, but less influenced by outliers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$sim_{\\ manhattan} (p,q) =\\frac{1}{dist(p,q)} = \\frac{1}{1 + \\sum_{i = 1}^n |p_i - q_i|}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "\n",
    "Write a function called `manhattan_similarity()` that calculates this metric"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Cosine similarity**\n",
    "\n",
    "- The normalized dot product of two vectors, i.e., the cosine of the angle between them\n",
    "\n",
    "\n",
    "- **Scale-invariance**: cosine similarity is independent of vector length \n",
    "    - you can multiply your vector for any non-zero constant and the angle won't change\n",
    "    - it should be used when vector length is irrelevant\n",
    "    - in k-NN, this means that it is independent of the absolute number of rating per user/item"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$sim_{\\ cosine} (\\vec{p},\\vec{q})=\\frac{\\vec{p} \\cdot \\vec{q}}{\\lVert \\vec{p} \\rVert \\lVert \\vec{q} \\rVert} = \\frac{\\sum_{i = 1}^n p_i q_i}{\\sqrt{\\sum_{i = 1}^n (p_i)^2} \\sqrt{\\sum_{i = 1}^n (q_i)^2}}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cosine_similarity(p,q):\n",
    "    d = sum(pi * qi for pi,qi in zip(p, q))\n",
    "    mag_p = math.sqrt(sum([pi**2 for pi in p]))\n",
    "    mag_q = math.sqrt(sum([qi**2 for qi in q]))\n",
    "    sim = d / ( mag_p * mag_q)\n",
    "    return sim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Pearson correlation**: \n",
    "\n",
    "\n",
    "- Measure of the strength of linear dependence between two variables\n",
    "\n",
    "\n",
    "- Calculated as the ratio between the variance that is shared between the two variables (covariance) and the product of their standard deviations (i.e., of their variance)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$r(p,q) = \\frac{\\sum_{i = 1}^n (p_i - \\bar{p})(q_i - \\bar{q})}{\\sqrt{\\sum_{i = 1}^n (p_i - \\bar{p})^2}\\ \\sqrt{\\sum_{i = 1}^n (q_i - \\bar{q})^2}}$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- The correlation value between two variables is invariant to **scale** and **location** tranformations:\n",
    "    - that is, if $a$, $b$, $c$, $d$ are constants and $a > 0$ and $c > 0$:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$r(p,q) = r(a\\cdot p + b, c\\cdot q + d)$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pearson_correlation(p,q):\n",
    "    # this code does not scale well to large datasets. In the following, we rely on \n",
    "    # scipy.spatial.distance.correlation() to compute long vectors\n",
    "    if len(p) > 99:\n",
    "        return 1 - distance.correlation(p,q)        \n",
    "    \n",
    "    p_mean = sum(p) / len(p)\n",
    "    p_deviations = [(pi-p_mean) for pi in p]\n",
    "    \n",
    "    q_mean = sum(q) / len(q)\n",
    "    q_deviations = [(qi-q_mean) for qi in q]\n",
    "    \n",
    "    cov = sum(pd * qd for pd,qd in zip(p_deviations, q_deviations))\n",
    "        \n",
    "    sds_product = math.sqrt(sum((pd)**2 for pd in p_deviations) * sum((qd)**2 for qd in q_deviations))\n",
    "    \n",
    "    if sds_product != 0:\n",
    "        r = cov / sds_product\n",
    "    else:\n",
    "        r = 0\n",
    "    return r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Pearson correlation** and **cosine similarity**:\n",
    "\n",
    "- The Pearson correlation is equivalent to the cosine similarity if the values of input vectors has been **normalized to their arithmetic means**:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$sim_{\\ cosine} (p - \\bar{p}, q - \\bar{q}) = \\frac{\\sum_{i = 1}^n (p_i - \\bar{p})(q_i - \\bar{q})}{\\sqrt{\\sum_{i = 1}^n (p_i - \\bar{p})^2}\\ \\sqrt{\\sum_{i = 1}^n (q_i - \\bar{q})^2}} = r(p,q) $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- That is, the Pearson correlation and the cosine similarity are equivalent when the two vectors have **mean of 0**:\n",
    "\n",
    "    - geometrically, the Pearson correlation can be seen as the angle between the two vectors where the origin of the coordinate system is translated at the arithmetic mean values of the vectors;\n",
    "    \n",
    "    - both the cosine similarity and the Pearson correlation are **scale invariant**, while Pearson correlation is also **invariant to constant addition**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Jaccard similarity** \n",
    "\n",
    "Measured as the ratio of the cardinality of the intersection set (number of items that are in both sets) to that of the union set (number of items in either sets)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$sim_{\\ jaccard} (P, Q) = \\frac{|P \\cap Q|}{|P \\cup Q|}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def jaccard_sets(p,q): \n",
    "    intersection_cardinality = len(set(p).intersection(set(q)))\n",
    "    union_cardinality = len(set(p).union(set(q)))\n",
    "    sim = intersection_cardinality / union_cardinality\n",
    "    return sim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- It is particularly useful for **datasets with binary values** (e.g., 1s for a preference and 0s for indifference)\n",
    "    - in these cases, you have two objects $P$ and $Q$ with $n$ attributes,\n",
    "    - and you may use this measure to estimate the **overlap that $P$ and $Q$ share with their attributes**.\n",
    "\n",
    "\n",
    "- If $M_{11}$ represents the number of attributes where both objects have a value of 1 and $M_{10} + M_{01}$ represents the number of attributes where only one object has a value of 1:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$sim_{\\ jaccard} = \\frac{M_{11}}{M_{01} + M_{10} + M_{11}}$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def jaccard_binary(p, q):\n",
    "    # only works for binary vectors! Binarize your vectors first\n",
    "    m_11, m_01, m_10 = 0, 0, 0\n",
    "    for pi, qi in zip(p, q):\n",
    "\n",
    "        if pi == 1:\n",
    "            if qi == 1:\n",
    "                m_11 += 1\n",
    "            else:\n",
    "                m_10 += 1\n",
    "                \n",
    "        elif qi == 1:\n",
    "            m_01 += 1\n",
    "    \n",
    "    sim = m_11 / (m_10 + m_01 + m_11) \n",
    "    return sim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "\n",
    "Apply the above measures on the following two vectors and be sure to understand their properties."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "p = [1, 2, 1, 0, 5, 0, 1, 1, 3, 4, 4, 0, 1, 0, 3, 1, 1, 1, 1, 1]\n",
    "q = [1, 3, 5, 0, 0, 0, 0, 1, 1, 0, 0, 2, 0, 0, 4, 1, 0, 0, 5, 0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Which one should I use?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This very much depends on your application:\n",
    "\n",
    "- How are we modeling our problem (i.e. are we using binary features)?\n",
    "\n",
    "\n",
    "- How do we want our measure to behave?\n",
    "    - do we want results to be less sensitive to outliers?\n",
    "    - do we want results to be scale-invariant?\n",
    "    - do we want results to be location-invariant?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As a **rule of thumb**, the best practice is to try how the similarity measures which make sense and decide on the basis of an **empirical evaluation**."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## User-to-user kNN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Given an active user $a$:\n",
    "\n",
    "- Use a similarity measure to determine the $k$ most-similar users to $a$.\n",
    "\n",
    "- Obtain the prediction on item $i$ for user $a$ by using one of the following aggregation approaches on the ratings from the neighborhood:\n",
    "    - average\n",
    "    - weighted sum\n",
    "    - adjusted weighted aggregation (deviation-from-mean)\n",
    "\n",
    "- Choose the top-$n$ items by selecting the $n$ items with the highest scores calculated by applying the previous steps on the items that haven’t been rated by the user $a$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### STEP 1: Find the top-50 similar users\n",
    "\n",
    "Let's build the neighborhood for our target user `4447` by calculating his similarity with other users."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def calculate_similarity(ratings, id1, id2, measure, threshold = 0):\n",
    "    # get the list of shared rated items\n",
    "    shared = sorted(set(ratings[id1].keys()).intersection(set(ratings[id2].keys())))\n",
    "\n",
    "    # ignore comparisons with too few overlapping ratings (default is 0)\n",
    "    if len(shared) <= threshold:\n",
    "        return 0\n",
    "    \n",
    "    sel_ratings = [np.asarray([v for (k,v) in ratings[i].items() if k in shared]) for i in [id1, id2]]\n",
    "    \n",
    "    # compute similarity\n",
    "    sim = measure(*sel_ratings)\n",
    "    return sim"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Calculate the similarities (NB: this can take a minute)\n",
    "measure2function = {\"euclidean\" : euclidean_similarity, \"cosine\": cosine_similarity, \"correlation\": pearson_correlation}\n",
    "\n",
    "similarities = dict()\n",
    "for measure, function in measure2function.items():\n",
    "    similarities[measure] = dict()\n",
    "    for id1, id2 in product([4447], user2movies_ratings.keys()):\n",
    "        # do not compare our target user with himself\n",
    "        if id1 == id2:\n",
    "            continue\n",
    "        similarities[measure][id2] = calculate_similarity(user2movies_ratings, id1, id2, function)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{'euclidean': {1037: 1.0, 3325: 1.0, 4628: 1.0, 61: 0.5, 782: 0.5, 1615: 0.5, 1838: 0.5, 1918: 0.5, 1979: 0.5, 2245: 0.5, 2584: 0.5, 2992: 0.5, 3133: 0.5, 3245: 0.5, 3264: 0.5, 3495: 0.5, 3542: 0.5, 3893: 0.5, 4008: 0.5, 1270: 0.4142135623730951, 1305: 0.4142135623730951, 1967: 0.4142135623730951, 2357: 0.4142135623730951, 3552: 0.4142135623730951, 3838: 0.4142135623730951, 4500: 0.4142135623730951, 4550: 0.4142135623730951, 4651: 0.4142135623730951, 4749: 0.4142135623730951, 364: 0.36602540378443865, 886: 0.36602540378443865, 1240: 0.36602540378443865, 1844: 0.36602540378443865, 3179: 0.36602540378443865, 3381: 0.36602540378443865, 3883: 0.36602540378443865, 4184: 0.36602540378443865, 4270: 0.36602540378443865, 4548: 0.36602540378443865, 4724: 0.36602540378443865, 5409: 0.36602540378443865, 5439: 0.36602540378443865, 5529: 0.36602540378443865, 653: 0.3333333333333333, 2037: 0.3333333333333333, 2673: 0.3333333333333333, 3122: 0.3333333333333333, 3168: 0.3333333333333333, 3351: 0.3333333333333333, 3548: 0.3333333333333333}, 'cosine': {1171: 1.0, 2037: 1.0, 2245: 1.0, 2357: 1.0, 2992: 1.0, 3133: 1.0, 3325: 1.0, 3542: 1.0, 3548: 1.0, 4008: 1.0, 4628: 1.0, 4651: 1.0, 1037: 0.9999999999999998, 1270: 0.9999999999999998, 5772: 0.9986310739646673, 3245: 0.9965457582448796, 3351: 0.9962679474209224, 3537: 0.9962405881956831, 1615: 0.9949366763261822, 1305: 0.9949366763261821, 3495: 0.9945358423571875, 5411: 0.9943342320224884, 5439: 0.9941734853720237, 3176: 0.9938837346736188, 5609: 0.9932005593217944, 3883: 0.9928946094454706, 1967: 0.9925037794773716, 3552: 0.9922426389474776, 1363: 0.9921371451421912, 703: 0.9920285511170235, 5409: 0.9916230680853516, 364: 0.9915610305527969, 4176: 0.9913925694908761, 5589: 0.9910438094089645, 4550: 0.9904348670716856, 1918: 0.9903751369442767, 2584: 0.9899494936611667, 841: 0.9899494936611665, 1838: 0.9899494936611665, 3893: 0.9898267954648645, 5628: 0.9897899683088598, 4724: 0.989772275519182, 4881: 0.9893228905061733, 2108: 0.9891934612115588, 91: 0.988986760303917, 1444: 0.9888475862700887, 4900: 0.9888299807922705, 1821: 0.9887921042262728, 5007: 0.9883134055507964, 2834: 0.9881544795032398}, 'correlation': {986: 1.0, 1037: 1.0, 1615: 1.0, 2673: 1.0, 3043: 1.0, 3245: 1.0, 3537: 1.0, 4259: 1.0, 5380: 1.0, 5772: 1.0, 3893: 0.9449111825230683, 1240: 0.9438798074485389, 5409: 0.9431325307120428, 5672: 0.9284766908852594, 2440: 0.9101820546182064, 1967: 0.899228803025897, 5398: 0.8749999999999999, 3351: 0.8728715609439696, 4612: 0.872402414514471, 3264: 0.8703882797784892, 4749: 0.8703882797784892, 5411: 0.8703882797784892, 61: 0.8660254037844387, 1444: 0.8660254037844387, 1918: 0.8660254037844387, 782: 0.8660254037844385, 3552: 0.8660254037844385, 4463: 0.849384675469882, 4900: 0.8353813293887845, 3495: 0.8164965809277261, 5589: 0.8136249378480974, 3222: 0.811147458237388, 4880: 0.8110930725375102, 364: 0.8017837257372732, 4548: 0.7895420339517227, 4935: 0.7814423676209548, 5439: 0.7753148860571064, 3179: 0.7730206825239259, 4332: 0.768273325346536, 1154: 0.7669649888473704, 4226: 0.7629593851650108, 5207: 0.7513428837969105, 5343: 0.7504511788447622, 4881: 0.7456011350793258, 5224: 0.7426845355346071, 1813: 0.7302967433402215, 3168: 0.7302967433402214, 3883: 0.7302967433402214, 5311: 0.7288779503769464, 3122: 0.7258661863112977}}\n"
     ]
    }
   ],
   "source": [
    "# select the most similar users according to each measure\n",
    "\n",
    "k = 50 # this is the k in k-NN\n",
    "neighborhood = dict()\n",
    "for measure in similarities.keys():\n",
    "    neighborhood[measure] = dict(sorted(similarities[measure].items(), key = itemgetter(1), reverse = True)[:k])\n",
    "print(neighborhood)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### STEP 2: Obtain the predictions for all items of interest \n",
    "\n",
    "- In a real life scenario, we should obtain a predictions for all the items that were not rated by our user.\n",
    "\n",
    "\n",
    "- In this example, we will get predictions for just our three target movies."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's use the following weighted score to aggregate our ratings:\n",
    " \n",
    "- Take the votes of all other critics and multiply them by their similarity with our target user.\n",
    "\n",
    "\n",
    "- Sum these weighted votes for each item of interest.\n",
    "\n",
    "\n",
    "- In order to handle the sparseness of the dataset (no movie has been rated by all the users), divide this score by the sum of all the similarities for critics that reviewed that movie."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/weighting-users.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getPredictions(movieId, neighborhood, ratings):\n",
    "    weigthed_scores = []\n",
    "    similarities = []\n",
    "\n",
    "    for user, sim in neighborhood.items():\n",
    "        if movieId in ratings[user]:\n",
    "            weigthed_scores.append(sim * ratings[user][movieId])\n",
    "            similarities.append(sim)\n",
    "    \n",
    "    return sum(weigthed_scores) / sum(similarities)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "recommendations = defaultdict(dict)\n",
    "\n",
    "for measure in similarities.keys():\n",
    "    for movie in target_movies:\n",
    "        recommendations[measure][movie] = getPredictions(movie, neighborhood[measure], user2movies_ratings)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### STEP 3: Choose the top-items \n",
    "\n",
    "- In a real life scenario, you should choose the top-rated items and recommend them to the user.\n",
    "\n",
    "\n",
    "- In this exercise, we will compare the **rating predictions** produced by our RC against the **actual ratings** given by our user."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How do the predicted ratings compare to the actual ones?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Original ratings\n",
      "Silence of the Lambs, The (1991) --> 4\n",
      "Raiders of the Lost Ark (1981) --> 2\n",
      "Back to the Future (1985) --> 3\n"
     ]
    }
   ],
   "source": [
    "print(\"# Original ratings\")\n",
    "\n",
    "for movieID in target_ratings:\n",
    "    print(id2movie[movieID], \"-->\", target_ratings[movieID])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "#  Predicted, euclidean\n",
      "Silence of the Lambs, The (1991) --> 4.098217993648402\n",
      "Raiders of the Lost Ark (1981) --> 5.0\n",
      "Back to the Future (1985) --> 2.7088761776287287\n",
      "\n",
      "#  Predicted, cosine\n",
      "Silence of the Lambs, The (1991) --> 4.144352723486918\n",
      "Raiders of the Lost Ark (1981) --> 3.7517827670141886\n",
      "Back to the Future (1985) --> 2.74679603706995\n",
      "\n",
      "#  Predicted, correlation\n",
      "Silence of the Lambs, The (1991) --> 3.8862286223113807\n",
      "Raiders of the Lost Ark (1981) --> 4.614829742977353\n",
      "Back to the Future (1985) --> 3.2929248770516923\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for measure in similarities.keys():\n",
    "    print(\"# \", \"Predicted,\", measure)\n",
    "    for movieID in target_ratings:\n",
    "        print(id2movie[movieID], \"-->\", recommendations[measure][movieID])\n",
    "    print()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let's calculate the **Mean Absolute Error** \n",
    "\n",
    "- The difference between the real ratings and those produced by the RS.\n",
    "\n",
    "\n",
    "- If $\\hat{y}_i$ is the predicted value of the $i$-th sample, $y_i$ is the true value and $n$ is the sample size:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$MAE(y, \\hat{y}) = \\frac{1}{n} \\sum_{i = 0}^{n - 1} \\left| \\ y_i, \\hat{y_i}\\ \\right|$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Mean Absolute Error, euclidean\n",
      "1.129780605339891\n",
      "# Mean Absolute Error, cosine\n",
      "0.7164464844770522\n",
      "# Mean Absolute Error, correlation\n",
      "1.0071753325725548\n"
     ]
    }
   ],
   "source": [
    "true_ratings = [target_ratings[movieID] for movieID in target_ratings]\n",
    "\n",
    "for measure in similarities.keys():\n",
    "    print(\"#\", \"Mean Absolute Error,\", measure)\n",
    "    predicted = [recommendations[measure][movieID] for movieID in target_ratings]\n",
    "    print(mean_absolute_error(true_ratings, predicted))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "\n",
    "See what happens if:\n",
    "\n",
    "- we specify a minimum rating overlap threshold (say, 10) in the `calculate_similarity()` function.\n",
    "\n",
    "\n",
    "- We change the size of the neighborhood (say, to 100)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Item-to-item kNN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Given an active user $a$:\n",
    "\n",
    "- For each item in the database, use a similarity measure to determine its $k$ most-similar items.\n",
    "\n",
    "\n",
    "- For each item $i$ not rated by $a$, predict its rating on the basis of the $a$'s previous ratings of the items in the $i$'s neighborhood.\n",
    "\n",
    "\n",
    "- Choose the top-$n$ items by selecting the $n$ items with the highest scores calculated in the previous step."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### STEP 1: Find the top-25 similar items\n",
    "\n",
    "Re-arranging the ratings dictionary allows us to use the `calculate_distance()` function to calculate the item-based similarities as well"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "# let's rearrange the dictionary of ratings \n",
    "\n",
    "movies2user_ratings = defaultdict(dict)\n",
    "\n",
    "for user, user_ratings in user2movies_ratings.items():\n",
    "    for movie, rating in user_ratings.items():\n",
    "        movies2user_ratings[movie][user] = rating"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To speed up the process, we will ignore all those movies that has not been rated by at least 1500 users"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "- 3639 movies have been discarded\n",
      "- 67 movies have been selected\n"
     ]
    }
   ],
   "source": [
    "filtered_movies2user_ratings = dict()\n",
    "for movie in movies2user_ratings.keys():\n",
    "    if len(movies2user_ratings[movie]) < 1500:\n",
    "        continue\n",
    "    else:\n",
    "        filtered_movies2user_ratings[movie] = movies2user_ratings[movie]\n",
    "\n",
    "print(\"-\", len(movies2user_ratings) - len(filtered_movies2user_ratings), \"movies have been discarded\")\n",
    "print(\"-\", len(filtered_movies2user_ratings), \"movies have been selected\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Let's calculate the similarities, this time only using Pearson's correlation\n",
    "# WARNING: This method is quite inefficient! Can you find the bottleneck, and think of a way to speed it up?\n",
    "\n",
    "similarities = defaultdict(dict)\n",
    "for id1, id2 in combinations(filtered_movies2user_ratings.keys(), 2):\n",
    "    similarities[id1][id2] = calculate_similarity(movies2user_ratings, id1, id2, pearson_correlation)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# select the most similar items\n",
    "neighborhood = dict()\n",
    "for movie in similarities.keys():\n",
    "    neighborhood[movie] = dict(sorted(similarities[movie].items(), key = itemgetter(1), reverse = True)[:25])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise\n",
    "\n",
    "Choose a movie and explore its immediate neighborhood by printing its most similar movies and using MDS or PCA to plot them in a 2-dimensional space"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# your code here"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### STEP 2: Obtain the predictions for all the items of interest \n",
    "\n",
    "For all the items that the user hasn't rated (here we restrict ourselves to our three target movies), the following weighted score is used to aggregate our ratings:\n",
    "\n",
    "- for each pair of items composed by one item rated by our user and one of our items of interest, we calculate a score by multiplying their pairwise similarity and the rating for the known movie.\n",
    "\n",
    "\n",
    "- For each item of interest we sum all these scores.\n",
    "\n",
    "\n",
    "- The score is normalized by diving this total by the total of the pairwise similarity scores involving a item of interest."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![alt text](images/weighting-item.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def getPredictionsForItems(userId, neighborhood, ratings):\n",
    "    weigthed_scores = []\n",
    "    similarities = []\n",
    "\n",
    "    for item, sim in neighborhood.items():\n",
    "        if userId in ratings[item]:\n",
    "            weigthed_scores.append(sim * ratings[item][userId])\n",
    "            similarities.append(sim)\n",
    "    \n",
    "    return sum(weigthed_scores) / sum(similarities)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "recommendations = defaultdict(dict)\n",
    "\n",
    "for movie in target_movies:\n",
    "    recommendations[movie] = getPredictionsForItems(4447, neighborhood[movie], filtered_movies2user_ratings)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### STEP 3: Choose the top-items \n",
    "\n",
    "- In a real life scenario, you should choose the top-rated items and recommend them to the user.\n",
    "\n",
    "\n",
    "- In this exercise, we will compare the **rating predictions** produced by our RC against those produced by our user."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "How do the predicted ratings compare to the actual ones?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Original ratings\n",
      "Silence of the Lambs, The (1991) --> 4\n",
      "Raiders of the Lost Ark (1981) --> 2\n",
      "Back to the Future (1985) --> 3\n"
     ]
    }
   ],
   "source": [
    "print(\"# Original ratings\")\n",
    "\n",
    "for movieID in target_ratings:\n",
    "    print(id2movie[movieID], \"-->\", target_ratings[movieID])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Predicted ratings\n",
      "Silence of the Lambs, The (1991) --> 3.605898258715225\n",
      "Raiders of the Lost Ark (1981) --> 3.3224392124831894\n",
      "Back to the Future (1985) --> 3.0006836869169238\n"
     ]
    }
   ],
   "source": [
    "print(\"# Predicted ratings\")\n",
    "for movieID in target_ratings:\n",
    "    print(id2movie[movieID], \"-->\", recommendations[movieID])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As before, let's calculate the **Mean Absolute Error** (i.e. the difference between the real ratings and those produced by the RS)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "# Mean Absolute Error\n",
      "0.5724082135616294\n"
     ]
    }
   ],
   "source": [
    "true_ratings = [target_ratings[movieID] for movieID in target_ratings]\n",
    "predicted = [recommendations[movieID] for movieID in target_ratings]\n",
    "\n",
    "print(\"# Mean Absolute Error\")\n",
    "print(mean_absolute_error(true_ratings, predicted))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  }
 ],
 "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.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}