{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import gzip\n",
    "import math\n",
    "import random\n",
    "from collections import defaultdict"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Data is available at http://cseweb.ucsd.edu/~jmcauley/pml/data/. Download and save to your own directory"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataDir = \"/home/jmcauley/pml_data/\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Amazon musical instrument review data. Originally from https://s3.amazonaws.com/amazon-reviews-pds/tsv/index.txt "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "path = dataDir + \"amazon_reviews_us_Musical_Instruments_v1_00.tsv.gz\"\n",
    "f = gzip.open(path, 'rt', encoding=\"utf8\")\n",
    "\n",
    "header = f.readline()\n",
    "header = header.strip().split('\\t')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dataset contains the following fields"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['marketplace',\n",
       " 'customer_id',\n",
       " 'review_id',\n",
       " 'product_id',\n",
       " 'product_parent',\n",
       " 'product_title',\n",
       " 'product_category',\n",
       " 'star_rating',\n",
       " 'helpful_votes',\n",
       " 'total_votes',\n",
       " 'vine',\n",
       " 'verified_purchase',\n",
       " 'review_headline',\n",
       " 'review_body',\n",
       " 'review_date']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "header"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Parse the data and convert fields to integers where needed"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "dataset = []\n",
    "\n",
    "for line in f:\n",
    "    fields = line.strip().split('\\t')\n",
    "    d = dict(zip(header, fields))\n",
    "    d['star_rating'] = int(d['star_rating'])\n",
    "    d['helpful_votes'] = int(d['helpful_votes'])\n",
    "    d['total_votes'] = int(d['total_votes'])\n",
    "    dataset.append(d)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "One row of the dataset (as a python dictionary)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'customer_id': '45610553',\n",
       " 'helpful_votes': 0,\n",
       " 'marketplace': 'US',\n",
       " 'product_category': 'Musical Instruments',\n",
       " 'product_id': 'B00HH62VB6',\n",
       " 'product_parent': '618218723',\n",
       " 'product_title': 'AGPtek® 10 Isolated Output 9V 12V 18V Guitar Pedal Board Power Supply Effect Pedals with Isolated Short Cricuit / Overcurrent Protection',\n",
       " 'review_body': 'Works very good, but induces ALOT of noise.',\n",
       " 'review_date': '2015-08-31',\n",
       " 'review_headline': 'Three Stars',\n",
       " 'review_id': 'RMDCHWD0Y5OZ9',\n",
       " 'star_rating': 3,\n",
       " 'total_votes': 1,\n",
       " 'verified_purchase': 'N',\n",
       " 'vine': 'N'}"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dataset[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extract a few utility data structures"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "usersPerItem = defaultdict(set) # Maps an item to the users who rated it\n",
    "itemsPerUser = defaultdict(set) # Maps a user to the items that they rated\n",
    "itemNames = {}\n",
    "ratingDict = {} # To retrieve a rating for a specific user/item pair\n",
    "\n",
    "for d in dataset:\n",
    "    user,item = d['customer_id'], d['product_id']\n",
    "    usersPerItem[item].add(user)\n",
    "    itemsPerUser[user].add(item)\n",
    "    ratingDict[(user,item)] = d['star_rating']\n",
    "    itemNames[item] = d['product_title']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Extract per-user and per-item averages (useful later for rating prediction)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "userAverages = {}\n",
    "itemAverages = {}\n",
    "\n",
    "for u in itemsPerUser:\n",
    "    rs = [ratingDict[(u,i)] for i in itemsPerUser[u]]\n",
    "    userAverages[u] = sum(rs) / len(rs)\n",
    "    \n",
    "for i in usersPerItem:\n",
    "    rs = [ratingDict[(u,i)] for u in usersPerItem[i]]\n",
    "    itemAverages[i] = sum(rs) / len(rs)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Similarity metrics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Jaccard"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Jaccard(s1, s2):\n",
    "    numer = len(s1.intersection(s2))\n",
    "    denom = len(s1.union(s2))\n",
    "    if denom == 0:\n",
    "        return 0\n",
    "    return numer / denom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cosine"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Simple implementation for set-structured data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "def CosineSet(s1, s2):\n",
    "    # Not a proper implementation, operates on sets so correct for interactions only\n",
    "    numer = len(s1.intersection(s2))\n",
    "    denom = math.sqrt(len(s1)) * math.sqrt(len(s2))\n",
    "    if denom == 0:\n",
    "        return 0\n",
    "    return numer / denom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Or for real values (e.g. ratings). Note that this implementation uses global variables (usersPerItem, ratingDict), which ideally should be passed as parameters."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Cosine(i1, i2):\n",
    "    # Between two items\n",
    "    inter = usersPerItem[i1].intersection(usersPerItem[i2])\n",
    "    numer = 0\n",
    "    denom1 = 0\n",
    "    denom2 = 0\n",
    "    for u in inter:\n",
    "        numer += ratingDict[(u,i1)]*ratingDict[(u,i2)]\n",
    "    for u in usersPerItem[i1]:\n",
    "        denom1 += ratingDict[(u,i1)]**2\n",
    "    for u in usersPerItem[i2]:\n",
    "        denom2 += ratingDict[(u,i2)]**2\n",
    "    denom = math.sqrt(denom1) * math.sqrt(denom2)\n",
    "    if denom == 0: return 0\n",
    "    return numer / denom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pearson"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def Pearson(i1, i2):\n",
    "    # Between two items\n",
    "    iBar1 = itemAverages[i1]\n",
    "    iBar2 = itemAverages[i2]\n",
    "    inter = usersPerItem[i1].intersection(usersPerItem[i2])\n",
    "    numer = 0\n",
    "    denom1 = 0\n",
    "    denom2 = 0\n",
    "    for u in inter:\n",
    "        numer += (ratingDict[(u,i1)] - iBar1)*(ratingDict[(u,i2)] - iBar2)\n",
    "    for u in inter: #usersPerItem[i1]:\n",
    "        denom1 += (ratingDict[(u,i1)] - iBar1)**2\n",
    "    #for u in usersPerItem[i2]:\n",
    "        denom2 += (ratingDict[(u,i2)] - iBar2)**2\n",
    "    denom = math.sqrt(denom1) * math.sqrt(denom2)\n",
    "    if denom == 0: return 0\n",
    "    return numer / denom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Retrieve the most similar items to a given query"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this case, based on the Jaccard similarity"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mostSimilar(i, N):\n",
    "    similarities = []\n",
    "    users = usersPerItem[i]\n",
    "    for i2 in usersPerItem:\n",
    "        if i2 == i: continue\n",
    "        sim = Jaccard(users, usersPerItem[i2])\n",
    "        #sim = Pearson(i, i2) # Could use alternate similarity metrics straightforwardly\n",
    "        similarities.append((sim,i2))\n",
    "    similarities.sort(reverse=True)\n",
    "    return similarities[:N]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Choose an item to use as a query"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'customer_id': '6111003',\n",
       " 'helpful_votes': 0,\n",
       " 'marketplace': 'US',\n",
       " 'product_category': 'Musical Instruments',\n",
       " 'product_id': 'B0006VMBHI',\n",
       " 'product_parent': '603261968',\n",
       " 'product_title': 'AudioQuest LP record clean brush',\n",
       " 'review_body': 'removes dust. does not clean',\n",
       " 'review_date': '2015-08-31',\n",
       " 'review_headline': 'Three Stars',\n",
       " 'review_id': 'RIZR67JKUDBI0',\n",
       " 'star_rating': 3,\n",
       " 'total_votes': 1,\n",
       " 'verified_purchase': 'Y',\n",
       " 'vine': 'N'}"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dataset[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "query = dataset[2]['product_id']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Retrieve the most similary items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "ms = mostSimilar(query, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0.028446389496717725, 'B00006I5SD'),\n",
       " (0.01694915254237288, 'B00006I5SB'),\n",
       " (0.015065913370998116, 'B000AJR482'),\n",
       " (0.014204545454545454, 'B00E7MVP3S'),\n",
       " (0.008955223880597015, 'B001255YL2'),\n",
       " (0.008849557522123894, 'B003EIRVO8'),\n",
       " (0.008333333333333333, 'B0015VEZ22'),\n",
       " (0.00821917808219178, 'B00006I5UH'),\n",
       " (0.008021390374331552, 'B00008BWM7'),\n",
       " (0.007656967840735069, 'B000H2BC4E')]"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Print names of query and recommended items"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'AudioQuest LP record clean brush'"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "itemNames[query]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Shure SFG-2 Stylus Tracking Force Gauge',\n",
       " 'Shure M97xE High-Performance Magnetic Phono Cartridge',\n",
       " 'ART Pro Audio DJPRE II Phono Turntable Preamplifier',\n",
       " 'Signstek Blue LCD Backlight Digital Long-Playing LP Turntable Stylus Force Scale Gauge Tester',\n",
       " 'Audio Technica AT120E/T Standard Mount Phono Cartridge',\n",
       " 'Technics: 45 Adaptor for Technics 1200 (SFWE010)',\n",
       " 'GruvGlide GRUVGLIDE DJ Package',\n",
       " 'STANTON MAGNETICS Record Cleaner Kit',\n",
       " 'Shure M97xE High-Performance Magnetic Phono Cartridge',\n",
       " 'Behringer PP400 Ultra Compact Phono Preamplifier']"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[itemNames[x[1]] for x in ms]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Faster implementation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mostSimilarFast(i, N):\n",
    "    similarities = []\n",
    "    users = usersPerItem[i]\n",
    "    candidateItems = set()\n",
    "    for u in users:\n",
    "        candidateItems = candidateItems.union(itemsPerUser[u])\n",
    "    for i2 in candidateItems:\n",
    "        if i2 == i: continue\n",
    "        sim = Jaccard(users, usersPerItem[i2])\n",
    "        similarities.append((sim,i2))\n",
    "    similarities.sort(reverse=True)\n",
    "    return similarities[:N]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Confirm that results are the same..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0.028446389496717725, 'B00006I5SD'),\n",
       " (0.01694915254237288, 'B00006I5SB'),\n",
       " (0.015065913370998116, 'B000AJR482'),\n",
       " (0.014204545454545454, 'B00E7MVP3S'),\n",
       " (0.008955223880597015, 'B001255YL2'),\n",
       " (0.008849557522123894, 'B003EIRVO8'),\n",
       " (0.008333333333333333, 'B0015VEZ22'),\n",
       " (0.00821917808219178, 'B00006I5UH'),\n",
       " (0.008021390374331552, 'B00008BWM7'),\n",
       " (0.007656967840735069, 'B000H2BC4E')]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mostSimilarFast(query, 10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Similarity-based rating estimation"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Use our similarity functions to estimate ratings. Start by building a few utility data structures."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "reviewsPerUser = defaultdict(list)\n",
    "reviewsPerItem = defaultdict(list)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "for d in dataset:\n",
    "    user,item = d['customer_id'], d['product_id']\n",
    "    reviewsPerUser[user].append(d)\n",
    "    reviewsPerItem[item].append(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "ratingMean = sum([d['star_rating'] for d in dataset]) / len(dataset)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.251102772543146"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ratingMean"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Rating prediction heuristic (several alternatives from Chapter 4 could be used)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predictRating(user,item):\n",
    "    ratings = []\n",
    "    similarities = []\n",
    "    for d in reviewsPerUser[user]:\n",
    "        i2 = d['product_id']\n",
    "        if i2 == item: continue\n",
    "        ratings.append(d['star_rating'] - itemAverages[i2])\n",
    "        similarities.append(Jaccard(usersPerItem[item],usersPerItem[i2]))\n",
    "    if (sum(similarities) > 0):\n",
    "        weightedRatings = [(x*y) for x,y in zip(ratings,similarities)]\n",
    "        return itemAverages[item] + sum(weightedRatings) / sum(similarities)\n",
    "    else:\n",
    "        # User hasn't rated any similar items\n",
    "        return ratingMean"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{'customer_id': '14640079',\n",
       " 'helpful_votes': 0,\n",
       " 'marketplace': 'US',\n",
       " 'product_category': 'Musical Instruments',\n",
       " 'product_id': 'B003LRN53I',\n",
       " 'product_parent': '986692292',\n",
       " 'product_title': 'Sennheiser HD203 Closed-Back DJ Headphones',\n",
       " 'review_body': 'Nice headphones at a reasonable price.',\n",
       " 'review_date': '2015-08-31',\n",
       " 'review_headline': 'Five Stars',\n",
       " 'review_id': 'RZSL0BALIYUNU',\n",
       " 'star_rating': 5,\n",
       " 'total_votes': 0,\n",
       " 'verified_purchase': 'Y',\n",
       " 'vine': 'N'}"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dataset[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Predict a rating for a particular user/item pair"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "u,i = dataset[1]['customer_id'], dataset[1]['product_id']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4.509357030989021"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "predictRating(u, i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compute the MSE for a model based on this heuristic"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def MSE(predictions, labels):\n",
    "    differences = [(x-y)**2 for x,y in zip(predictions,labels)]\n",
    "    return sum(differences) / len(differences)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compared to a trivial predictor which always predicts the mean"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "alwaysPredictMean = [ratingMean for d in dataset]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Get predictions for all instances (fairly slow!)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "simPredictions = [predictRating(d['customer_id'], d['product_id']) for d in dataset]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "labels = [d['star_rating'] for d in dataset]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.4796142779564334"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MSE(alwaysPredictMean, labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.44672577948388"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MSE(simPredictions, labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Exercises"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(implementation is provided via the function mostSimilarFast above)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(using Amazon musical instruments data from examples above)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "def simTest(simFunction, nUserSamples):\n",
    "    sims = []\n",
    "    randomSims = []\n",
    "\n",
    "    items = set(usersPerItem.keys())\n",
    "    users = list(itemsPerUser.keys())\n",
    "\n",
    "    for u in random.sample(users, nUserSamples):\n",
    "        itemsU = set(itemsPerUser[u])\n",
    "        if len(itemsU) < 2: continue # User needs at least two interactions\n",
    "        (i,j) = random.sample(itemsU, 2)\n",
    "        k = random.sample(items.difference(itemsU),1)[0]\n",
    "        usersi = usersPerItem[i].difference(set([u]))\n",
    "        usersj = usersPerItem[j].difference(set([u]))\n",
    "        usersk = usersPerItem[k].difference(set([u]))\n",
    "        sims.append(simFunction(usersi,usersj))\n",
    "        randomSims.append(simFunction(usersi,usersk))\n",
    "\n",
    "    print(\"Average similarity = \" + str(sum(sims)/len(sims)))\n",
    "    print(\"Average similarity (with random item) = \" + str(sum(randomSims)/len(randomSims)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average similarity = 0.0019330961239460492\n",
      "Average similarity (with random item) = 0.0\n"
     ]
    }
   ],
   "source": [
    "simTest(Jaccard, 1000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Average similarity = 0.005634438126569325\n",
      "Average similarity (with random item) = 0.0\n"
     ]
    }
   ],
   "source": [
    "simTest(CosineSet, 1000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "items = set(usersPerItem.keys())\n",
    "users = set(itemsPerUser.keys())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 1: Average Jaccard similarity between i and items in u's history\n",
    "def rec1score(u, i, userHistory):\n",
    "    if len(userHistory) == 0:\n",
    "        return 0\n",
    "    averageSim = []\n",
    "    s1 = usersPerItem[i].difference(set([u]))\n",
    "    for h in userHistory:\n",
    "        s2 = usersPerItem[h].difference(set([u]))\n",
    "        averageSim.append(Jaccard(s1,s2))\n",
    "    averageSim = sum(averageSim)/len(averageSim)\n",
    "    return averageSim\n",
    "\n",
    "# 2: Jaccard similarity with most similar user who has consumed i\n",
    "def rec2score(u, i, userHistory):\n",
    "    bestSim = None\n",
    "    for v in usersPerItem[i]:\n",
    "        if u == v:\n",
    "            continue\n",
    "        sim = Jaccard(userHistory, itemsPerUser[v])\n",
    "        if bestSim == None or sim > bestSim:\n",
    "            bestSim = sim\n",
    "    if bestSim == None:\n",
    "        return 0\n",
    "    return bestSim\n",
    "\n",
    "# Generate a recommendation for a user based on a given scoring function\n",
    "def rec(u, score):\n",
    "    history = itemsPerUser[u]\n",
    "    if len(history) > 5: # If the history is too long, just take a sample\n",
    "        history = random.sample(history,5)\n",
    "    bestItem = None\n",
    "    bestScore = None\n",
    "    for i in items:\n",
    "        if i in itemsPerUser[u]: continue\n",
    "        s = score(u, i, history)\n",
    "        if bestItem == None or s > bestScore:\n",
    "            bestItem = i\n",
    "            bestScore = s\n",
    "\n",
    "    return bestItem, bestScore"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "u = random.sample(users,1)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('B002KYLGT8', 0.043478260869565216)"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rec(u, rec1score)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "('B00HCPTXJA', 0.5)"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "rec(u, rec2score)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [],
   "source": [
    "def recTest(simFunction, nUserSamples):\n",
    "    items = set(usersPerItem.keys())\n",
    "    users = list(itemsPerUser.keys())\n",
    "    \n",
    "    better = 0\n",
    "    worse = 0\n",
    "\n",
    "    for u in random.sample(users, nUserSamples):\n",
    "        itemsU = set(itemsPerUser[u])\n",
    "        if len(itemsU) < 2:\n",
    "            continue\n",
    "        i = random.sample(itemsU, 1)[0]\n",
    "        uWithheld = itemsU.difference(set([i]))\n",
    "        j = random.sample(items,1)[0]\n",
    "\n",
    "        si = simFunction(u,i,uWithheld)\n",
    "        sj = simFunction(u,j,uWithheld)\n",
    "        \n",
    "        if si > sj:\n",
    "            better += 1\n",
    "        if sj > si:\n",
    "            worse += 1\n",
    "            \n",
    "    print(\"Better than random \" + str(better) + \" times\")\n",
    "    print(\"Worse than random \" + str(worse) + \" times\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Results on this dataset aren't particularly interesting. Could try with a denser dataset (so that many items have non-zero similarity) to get more interesting results."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Better than random 306 times\n",
      "Worse than random 1 times\n"
     ]
    }
   ],
   "source": [
    "recTest(rec1score,5000)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Better than random 278 times\n",
      "Worse than random 4 times\n"
     ]
    }
   ],
   "source": [
    "recTest(rec2score,5000)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 4.4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(following code and auxiliary data structures from the examples above)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Equation 4.20"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predictRating1(user,item):\n",
    "    ratings = []\n",
    "    similarities = []\n",
    "    for d in reviewsPerUser[user]:\n",
    "        i2 = d['product_id']\n",
    "        if i2 == item: continue\n",
    "        ratings.append(d['star_rating'])\n",
    "        similarities.append(Jaccard(usersPerItem[item],usersPerItem[i2]))\n",
    "    if (sum(similarities) > 0):\n",
    "        weightedRatings = [(x*y) for x,y in zip(ratings,similarities)]\n",
    "        return sum(weightedRatings) / sum(similarities)\n",
    "    else:\n",
    "        return ratingMean"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Equation 4.21"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predictRating2(user,item):\n",
    "    ratings = []\n",
    "    similarities = []\n",
    "    for d in reviewsPerItem[item]:\n",
    "        u2 = d['customer_id']\n",
    "        if u2 == user: continue\n",
    "        ratings.append(d['star_rating'])\n",
    "        similarities.append(Jaccard(itemsPerUser[user],itemsPerUser[u2]))\n",
    "    if (sum(similarities) > 0):\n",
    "        weightedRatings = [(x*y) for x,y in zip(ratings,similarities)]\n",
    "        return sum(weightedRatings) / sum(similarities)\n",
    "    else:\n",
    "        return ratingMean"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Equation 4.22"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [],
   "source": [
    "def predictRating3(user,item):\n",
    "    ratings = []\n",
    "    similarities = []\n",
    "    for d in reviewsPerUser[user]:\n",
    "        i2 = d['product_id']\n",
    "        if i2 == item: continue\n",
    "        ratings.append(d['star_rating'] - itemAverages[i2])\n",
    "        similarities.append(Jaccard(usersPerItem[item],usersPerItem[i2]))\n",
    "    if (sum(similarities) > 0):\n",
    "        weightedRatings = [(x*y) for x,y in zip(ratings,similarities)]\n",
    "        return itemAverages[item] + sum(weightedRatings) / sum(similarities)\n",
    "    else:\n",
    "        return ratingMean"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [],
   "source": [
    "simPredictions1 = [predictRating1(d['customer_id'], d['product_id']) for d in dataset]\n",
    "simPredictions2 = [predictRating2(d['customer_id'], d['product_id']) for d in dataset]\n",
    "simPredictions3 = [predictRating3(d['customer_id'], d['product_id']) for d in dataset]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.4796142779564334"
      ]
     },
     "execution_count": 51,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MSE(alwaysPredictMean, labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.6146130004291603"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MSE(simPredictions1, labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.4540822838636853"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MSE(simPredictions2, labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.44672577948388"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "MSE(simPredictions3, labels)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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
}