Recommender Systems using Affinity Analysis.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Recommender Systems using Affinity Analysis\n",
    "<hr>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Here we will look at affinity analysis that determines when objects occur\n",
    "frequently together. This is also called market basket analysis, after one of\n",
    "the use cases of determining when items are purchased together frequently.\n",
    "In this example, we wish to work out when\n",
    "two movies are recommended by the same reviewers.\n",
    "\n",
    "### Affinity analysis\n",
    "Affinity analysis is the task of determining when objects are used in similar\n",
    "ways. The data for affinity analysis is often described in the form of a\n",
    "transaction. Intuitively, this comes from a transaction at a store—determining\n",
    "when objects are purchased together.\n",
    "\n",
    "The classic algorithm for affinity analysis is called the Apriori algorithm. It addresses\n",
    "the exponential problem of creating sets of items that occur frequently within a\n",
    "database, called frequent itemsets. Once these frequent itemsets are discovered,\n",
    "creating association rules is straightforward.\n",
    "\n",
    "#### Apriori algorithm\n",
    "\n",
    "First, we ensure that a rule\n",
    "has sufficient support within the dataset. Defining a minimum support level is the\n",
    "key parameter for Apriori. To build a frequent itemset, for an itemset (A, B) to have a\n",
    "support of at least 30, both A and B must occur at least 30 times in the database. This\n",
    "property extends to larger sets as well. For an itemset (A, B, C, D) to be considered\n",
    "frequent, the set (A, B, C) must also be frequent (as must D).\n",
    "These frequent itemsets can be built up and possible itemsets that are not frequent\n",
    "(of which there are many) will never be tested. This saves significant time in testing\n",
    "new rules.\n",
    "Other example algorithms for affinity analysis include the Eclat and FP-growth\n",
    "algorithms. There are many improvements to these algorithms in the data mining\n",
    "literature that further improve the efficiency of the method. In this chapter, we will\n",
    "focus on the basic Apriori algorithm.\n",
    "\n",
    "#### Choosing parameters\n",
    "\n",
    "To perform association rule mining for affinity analysis, we first use the Apriori\n",
    "to generate frequent itemsets. Next, we create association rules (for example, if a\n",
    "person recommended movie X, they would also recommend movie Y) by testing\n",
    "combinations of premises and conclusions within those frequent itemsets.\n",
    "For the first stage, the Apriori algorithm needs a value for the minimum support\n",
    "that an itemset needs to be considered frequent. Any itemsets with less support will\n",
    "not be considered. Setting this minimum support too low will cause Apriori to test a\n",
    "larger number of itemsets, slowing the algorithm down. Setting it too high will result\n",
    "in fewer itemsets being considered frequent.\n",
    "\n",
    "In the second stage, after the frequent itemsets have been discovered, association\n",
    "rules are tested based on their confidence. We could choose a minimum confidence\n",
    "level, a number of rules to return, or simply return all of them and let the user decide\n",
    "what to do with them.\n",
    "\n",
    "Here, we will return only rules above a given confidence level. Therefore,\n",
    "we need to set our minimum confidence level. Setting this too low will result in rules\n",
    "that have a high support, but are not very accurate. Setting this higher will result in\n",
    "only more accurate rules being returned, but with fewer rules being discovered."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The movie recommendation problem\n",
    "\n",
    "Product recommendation is big business. Online stores use it to up-sell to\n",
    "customers by recommending other products that they could buy. Making better\n",
    "recommendations leads to better sales. When online shopping is selling to millions\n",
    "of customers every year, there is a lot of potential money to be made by selling more\n",
    "items to these customers.\n",
    "\n",
    "Product recommendations have been researched for many years; however, the field\n",
    "gained a significant boost when Netflix ran their Netflix Prize between 2007 and\n",
    "2009. This competition aimed to determine if anyone can predict a user's rating of a\n",
    "film better than Netflix was currently doing. The prize went to a team that was just\n",
    "over 10 percent better than the current solution. While this may not seem like a large\n",
    "improvement, such an improvement would net millions to Netflix in revenue from\n",
    "better movie recommendations.\n",
    "\n",
    "### Obtaining the dataset\n",
    "\n",
    "Since the inception of the Netflix Prize, Grouplens, a research group at the University\n",
    "of Minnesota, has released several datasets that are often used for testing algorithms\n",
    "in this area. They have released several versions of a movie rating dataset, which\n",
    "have different sizes. There is a version with 100,000 reviews, one with 1 million\n",
    "reviews and one with 10 million reviews.\n",
    "The datasets are available from http://grouplens.org/datasets/movielens/\n",
    "and the dataset we are going to use in this chapter is the MovieLens 1 million\n",
    "dataset. Download this dataset and unzip it in your data folder. We then load the dataset using Pandas. The MovieLens dataset is in a good shape; however, there are some changes from the\n",
    "default options in pandas.read_csv that we need to make. To start with, the data is\n",
    "separated by tabs, not commas. Next, there is no heading line. This means the first\n",
    "line in the file is actually data and we need to manually set the column names. When loading the file, we set the delimiter parameter to the tab character, tell pandas\n",
    "not to read the first row as the header (with header=None), and set the column\n",
    "names."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "ratings_filename = \"data/ml-100k/u.data\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "import pandas as pd"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>UserID</th>\n",
       "      <th>MovieID</th>\n",
       "      <th>Rating</th>\n",
       "      <th>Datetime</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>0</th>\n",
       "      <td>196</td>\n",
       "      <td>242</td>\n",
       "      <td>3</td>\n",
       "      <td>1997-12-04 15:55:49</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>1</th>\n",
       "      <td>186</td>\n",
       "      <td>302</td>\n",
       "      <td>3</td>\n",
       "      <td>1998-04-04 19:22:22</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>2</th>\n",
       "      <td>22</td>\n",
       "      <td>377</td>\n",
       "      <td>1</td>\n",
       "      <td>1997-11-07 07:18:36</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>244</td>\n",
       "      <td>51</td>\n",
       "      <td>2</td>\n",
       "      <td>1997-11-27 05:02:03</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>4</th>\n",
       "      <td>166</td>\n",
       "      <td>346</td>\n",
       "      <td>1</td>\n",
       "      <td>1998-02-02 05:33:16</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "   UserID  MovieID  Rating            Datetime\n",
       "0     196      242       3 1997-12-04 15:55:49\n",
       "1     186      302       3 1998-04-04 19:22:22\n",
       "2      22      377       1 1997-11-07 07:18:36\n",
       "3     244       51       2 1997-11-27 05:02:03\n",
       "4     166      346       1 1998-02-02 05:33:16"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_ratings = pd.read_csv(ratings_filename, delimiter=\"\\t\", header=None, names = [\"UserID\", \"MovieID\", \"Rating\", \"Datetime\"])\n",
    "all_ratings[\"Datetime\"] = pd.to_datetime(all_ratings['Datetime'],unit='s')\n",
    "all_ratings[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sparse data formats:\n",
    "\n",
    "This dataset is in a sparse format. Each row can be thought of as a cell in a large\n",
    "feature matrix of the type used in previous chapters, where rows are users and\n",
    "columns are individual movies. The first column would be each user's review\n",
    "of the first movie, the second column would be each user's review of the second\n",
    "movie, and so on.\n",
    "There are 1,000 users and 1,700 movies in this dataset, which means that the full\n",
    "matrix would be quite large. We may run into issues storing the whole matrix in\n",
    "memory and computing on it would be troublesome. However, this matrix has the\n",
    "property that most cells are empty, that is, there is no review for most movies for\n",
    "most users. There is no review of movie #675 for user #213 though, and not for most\n",
    "other combinations of user and movie."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Miniconda2\\lib\\site-packages\\ipykernel\\__main__.py:2: FutureWarning: sort(columns=....) is deprecated, use sort_values(by=.....)\n",
      "  from ipykernel import kernelapp as app\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>UserID</th>\n",
       "      <th>MovieID</th>\n",
       "      <th>Rating</th>\n",
       "      <th>Datetime</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>81098</th>\n",
       "      <td>675</td>\n",
       "      <td>86</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-03-10 00:26:14</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>90696</th>\n",
       "      <td>675</td>\n",
       "      <td>223</td>\n",
       "      <td>1</td>\n",
       "      <td>1998-03-10 00:35:51</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>92650</th>\n",
       "      <td>675</td>\n",
       "      <td>235</td>\n",
       "      <td>1</td>\n",
       "      <td>1998-03-10 00:35:51</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>95459</th>\n",
       "      <td>675</td>\n",
       "      <td>242</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-03-10 00:08:42</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>82845</th>\n",
       "      <td>675</td>\n",
       "      <td>244</td>\n",
       "      <td>3</td>\n",
       "      <td>1998-03-10 00:29:35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>53293</th>\n",
       "      <td>675</td>\n",
       "      <td>258</td>\n",
       "      <td>3</td>\n",
       "      <td>1998-03-10 00:11:19</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>97286</th>\n",
       "      <td>675</td>\n",
       "      <td>269</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:08:07</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>93720</th>\n",
       "      <td>675</td>\n",
       "      <td>272</td>\n",
       "      <td>3</td>\n",
       "      <td>1998-03-10 00:07:11</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>73389</th>\n",
       "      <td>675</td>\n",
       "      <td>286</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-03-10 00:07:11</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>77524</th>\n",
       "      <td>675</td>\n",
       "      <td>303</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:08:42</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>47367</th>\n",
       "      <td>675</td>\n",
       "      <td>305</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-03-10 00:09:08</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>44300</th>\n",
       "      <td>675</td>\n",
       "      <td>306</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:08:07</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>53730</th>\n",
       "      <td>675</td>\n",
       "      <td>311</td>\n",
       "      <td>3</td>\n",
       "      <td>1998-03-10 00:10:47</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>54284</th>\n",
       "      <td>675</td>\n",
       "      <td>312</td>\n",
       "      <td>2</td>\n",
       "      <td>1998-03-10 00:10:24</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>63291</th>\n",
       "      <td>675</td>\n",
       "      <td>318</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:21:13</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>87082</th>\n",
       "      <td>675</td>\n",
       "      <td>321</td>\n",
       "      <td>2</td>\n",
       "      <td>1998-03-10 00:11:48</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>56108</th>\n",
       "      <td>675</td>\n",
       "      <td>344</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-03-10 00:12:34</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>53046</th>\n",
       "      <td>675</td>\n",
       "      <td>347</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-03-10 00:07:11</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>94617</th>\n",
       "      <td>675</td>\n",
       "      <td>427</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:28:11</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>69915</th>\n",
       "      <td>675</td>\n",
       "      <td>463</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:16:43</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>46744</th>\n",
       "      <td>675</td>\n",
       "      <td>509</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:24:25</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>46598</th>\n",
       "      <td>675</td>\n",
       "      <td>531</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:18:28</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>52962</th>\n",
       "      <td>675</td>\n",
       "      <td>650</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:32:51</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>94029</th>\n",
       "      <td>675</td>\n",
       "      <td>750</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-03-10 00:08:07</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>53223</th>\n",
       "      <td>675</td>\n",
       "      <td>874</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-03-10 00:11:19</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>62277</th>\n",
       "      <td>675</td>\n",
       "      <td>891</td>\n",
       "      <td>2</td>\n",
       "      <td>1998-03-10 00:12:59</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>77274</th>\n",
       "      <td>675</td>\n",
       "      <td>896</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:09:35</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>66194</th>\n",
       "      <td>675</td>\n",
       "      <td>900</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-03-10 00:10:24</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>54994</th>\n",
       "      <td>675</td>\n",
       "      <td>937</td>\n",
       "      <td>1</td>\n",
       "      <td>1998-03-10 00:35:51</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>61742</th>\n",
       "      <td>675</td>\n",
       "      <td>1007</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-03-10 00:25:22</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>49225</th>\n",
       "      <td>675</td>\n",
       "      <td>1101</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-03-10 00:33:49</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>50692</th>\n",
       "      <td>675</td>\n",
       "      <td>1255</td>\n",
       "      <td>1</td>\n",
       "      <td>1998-03-10 00:35:51</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>74202</th>\n",
       "      <td>675</td>\n",
       "      <td>1628</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:30:37</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>47866</th>\n",
       "      <td>675</td>\n",
       "      <td>1653</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-03-10 00:31:53</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "       UserID  MovieID  Rating            Datetime\n",
       "81098     675       86       4 1998-03-10 00:26:14\n",
       "90696     675      223       1 1998-03-10 00:35:51\n",
       "92650     675      235       1 1998-03-10 00:35:51\n",
       "95459     675      242       4 1998-03-10 00:08:42\n",
       "82845     675      244       3 1998-03-10 00:29:35\n",
       "53293     675      258       3 1998-03-10 00:11:19\n",
       "97286     675      269       5 1998-03-10 00:08:07\n",
       "93720     675      272       3 1998-03-10 00:07:11\n",
       "73389     675      286       4 1998-03-10 00:07:11\n",
       "77524     675      303       5 1998-03-10 00:08:42\n",
       "47367     675      305       4 1998-03-10 00:09:08\n",
       "44300     675      306       5 1998-03-10 00:08:07\n",
       "53730     675      311       3 1998-03-10 00:10:47\n",
       "54284     675      312       2 1998-03-10 00:10:24\n",
       "63291     675      318       5 1998-03-10 00:21:13\n",
       "87082     675      321       2 1998-03-10 00:11:48\n",
       "56108     675      344       4 1998-03-10 00:12:34\n",
       "53046     675      347       4 1998-03-10 00:07:11\n",
       "94617     675      427       5 1998-03-10 00:28:11\n",
       "69915     675      463       5 1998-03-10 00:16:43\n",
       "46744     675      509       5 1998-03-10 00:24:25\n",
       "46598     675      531       5 1998-03-10 00:18:28\n",
       "52962     675      650       5 1998-03-10 00:32:51\n",
       "94029     675      750       4 1998-03-10 00:08:07\n",
       "53223     675      874       4 1998-03-10 00:11:19\n",
       "62277     675      891       2 1998-03-10 00:12:59\n",
       "77274     675      896       5 1998-03-10 00:09:35\n",
       "66194     675      900       4 1998-03-10 00:10:24\n",
       "54994     675      937       1 1998-03-10 00:35:51\n",
       "61742     675     1007       4 1998-03-10 00:25:22\n",
       "49225     675     1101       4 1998-03-10 00:33:49\n",
       "50692     675     1255       1 1998-03-10 00:35:51\n",
       "74202     675     1628       5 1998-03-10 00:30:37\n",
       "47866     675     1653       5 1998-03-10 00:31:53"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# As you can see, there are no review for most movies, such as #213\n",
    "all_ratings[all_ratings[\"UserID\"] == 675].sort(\"MovieID\")  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The format given here represents the full matrix, but in a more compact way.\n",
    "The first row indicates that user #196 reviewed movie #242, giving it a ranking\n",
    "of 3 (out of five) on the December 4, 1997.\n",
    "Any combination of user and movie that isn't in this database is assumed to not exist.\n",
    "This saves significant space, as opposed to storing a bunch of zeroes in memory. This\n",
    "type of format is called a sparse matrix format. As a rule of thumb, if you expect\n",
    "about 60 percent or more of your dataset to be empty or zero, a sparse format will\n",
    "take less space to store.\n",
    "\n",
    "When computing on sparse matrices, the focus isn't usually on the data we don't\n",
    "have—comparing all of the zeroes. We usually focus on the data we have and\n",
    "compare those.\n",
    "\n",
    "### The Apriori implementation\n",
    "\n",
    "The goal of this chapter is to produce rules of the following form: if a person\n",
    "recommends these movies, they will also recommend this movie. We will also discuss\n",
    "extensions where a person recommends a set of movies is likely to recommend\n",
    "another particular movie.\n",
    "\n",
    "To do this, we first need to determine if a person recommends a movie. We can\n",
    "do this by creating a new feature Favorable, which is True if the person gave a\n",
    "favorable review to a movie:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>UserID</th>\n",
       "      <th>MovieID</th>\n",
       "      <th>Rating</th>\n",
       "      <th>Datetime</th>\n",
       "      <th>Favorable</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>10</th>\n",
       "      <td>62</td>\n",
       "      <td>257</td>\n",
       "      <td>2</td>\n",
       "      <td>1997-11-12 22:07:14</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>286</td>\n",
       "      <td>1014</td>\n",
       "      <td>5</td>\n",
       "      <td>1997-11-17 15:38:45</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>12</th>\n",
       "      <td>200</td>\n",
       "      <td>222</td>\n",
       "      <td>5</td>\n",
       "      <td>1997-10-05 09:05:40</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>13</th>\n",
       "      <td>210</td>\n",
       "      <td>40</td>\n",
       "      <td>3</td>\n",
       "      <td>1998-03-27 21:59:54</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>14</th>\n",
       "      <td>224</td>\n",
       "      <td>29</td>\n",
       "      <td>3</td>\n",
       "      <td>1998-02-21 23:40:57</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    UserID  MovieID  Rating            Datetime Favorable\n",
       "10      62      257       2 1997-11-12 22:07:14     False\n",
       "11     286     1014       5 1997-11-17 15:38:45      True\n",
       "12     200      222       5 1997-10-05 09:05:40      True\n",
       "13     210       40       3 1998-03-27 21:59:54     False\n",
       "14     224       29       3 1998-02-21 23:40:57     False"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Not all reviews are favourable! Our goal is \"other recommended books\", so we only want favourable reviews\n",
    "all_ratings[\"Favorable\"] = all_ratings[\"Rating\"] > 3\n",
    "all_ratings[10:15]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>UserID</th>\n",
       "      <th>MovieID</th>\n",
       "      <th>Rating</th>\n",
       "      <th>Datetime</th>\n",
       "      <th>Favorable</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>202</th>\n",
       "      <td>1</td>\n",
       "      <td>61</td>\n",
       "      <td>4</td>\n",
       "      <td>1997-11-03 07:33:40</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>305</th>\n",
       "      <td>1</td>\n",
       "      <td>189</td>\n",
       "      <td>3</td>\n",
       "      <td>1998-03-01 06:15:28</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>333</th>\n",
       "      <td>1</td>\n",
       "      <td>33</td>\n",
       "      <td>4</td>\n",
       "      <td>1997-11-03 07:38:19</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>334</th>\n",
       "      <td>1</td>\n",
       "      <td>160</td>\n",
       "      <td>4</td>\n",
       "      <td>1997-09-24 03:42:27</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>478</th>\n",
       "      <td>1</td>\n",
       "      <td>20</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-02-14 04:51:23</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "     UserID  MovieID  Rating            Datetime Favorable\n",
       "202       1       61       4 1997-11-03 07:33:40      True\n",
       "305       1      189       3 1998-03-01 06:15:28     False\n",
       "333       1       33       4 1997-11-03 07:38:19      True\n",
       "334       1      160       4 1997-09-24 03:42:27      True\n",
       "478       1       20       4 1998-02-14 04:51:23      True"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "all_ratings[all_ratings[\"UserID\"] == 1][:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will sample our dataset to form a training dataset. This also helps reduce\n",
    "the size of the dataset that will be searched, making the Apriori algorithm run faster.\n",
    "We obtain all reviews from the first 200 users:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Sample the dataset. You can try increasing the size of the sample, but the run time will be considerably longer\n",
    "ratings = all_ratings[all_ratings['UserID'].isin(range(200))]  # & ratings[\"UserID\"].isin(range(100))]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next, we can create a dataset of only the favorable reviews in our sample:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>UserID</th>\n",
       "      <th>MovieID</th>\n",
       "      <th>Rating</th>\n",
       "      <th>Datetime</th>\n",
       "      <th>Favorable</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>16</th>\n",
       "      <td>122</td>\n",
       "      <td>387</td>\n",
       "      <td>5</td>\n",
       "      <td>1997-11-11 17:47:39</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>20</th>\n",
       "      <td>119</td>\n",
       "      <td>392</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-01-30 16:13:34</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>21</th>\n",
       "      <td>167</td>\n",
       "      <td>486</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-04-16 14:54:12</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>26</th>\n",
       "      <td>38</td>\n",
       "      <td>95</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-04-13 01:14:54</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>28</th>\n",
       "      <td>63</td>\n",
       "      <td>277</td>\n",
       "      <td>4</td>\n",
       "      <td>1997-10-01 23:10:01</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    UserID  MovieID  Rating            Datetime Favorable\n",
       "16     122      387       5 1997-11-11 17:47:39      True\n",
       "20     119      392       4 1998-01-30 16:13:34      True\n",
       "21     167      486       4 1998-04-16 14:54:12      True\n",
       "26      38       95       5 1998-04-13 01:14:54      True\n",
       "28      63      277       4 1997-10-01 23:10:01      True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# We start by creating a dataset of each user's favourable reviews\n",
    "favorable_ratings = ratings[ratings[\"Favorable\"]]\n",
    "favorable_ratings[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will be searching the user's favorable reviews for our itemsets. So, the next thing\n",
    "we need is the movies which each user has given a favorable. We can compute this\n",
    "by grouping the dataset by the User ID and iterating over the movies in each group:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "199"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# We are only interested in the reviewers who have more than one review\n",
    "favorable_reviews_by_users = dict((k, frozenset(v.values)) for k, v in favorable_ratings.groupby(\"UserID\")[\"MovieID\"])\n",
    "len(favorable_reviews_by_users)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In the preceding code, we stored the values as a frozenset, allowing us to quickly\n",
    "check if a movie has been rated by a user. Sets are much faster than lists for this type\n",
    "of operation, and we will use them in a later code.\n",
    "Finally, we can create a DataFrame that tells us how frequently each movie has been\n",
    "given a favorable review:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false,
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "C:\\Miniconda2\\lib\\site-packages\\ipykernel\\__main__.py:3: FutureWarning: sort(columns=....) is deprecated, use sort_values(by=.....)\n",
      "  app.launch_new_instance()\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>Favorable</th>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>MovieID</th>\n",
       "      <th></th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>50</th>\n",
       "      <td>100.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>100</th>\n",
       "      <td>89.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>258</th>\n",
       "      <td>83.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>181</th>\n",
       "      <td>79.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>174</th>\n",
       "      <td>74.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "         Favorable\n",
       "MovieID           \n",
       "50           100.0\n",
       "100           89.0\n",
       "258           83.0\n",
       "181           79.0\n",
       "174           74.0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Find out how many movies have favourable ratings\n",
    "num_favorable_by_movie = ratings[[\"MovieID\", \"Favorable\"]].groupby(\"MovieID\").sum()\n",
    "num_favorable_by_movie.sort(\"Favorable\", ascending=False)[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### The Apriori algorithm  revisited\n",
    "\n",
    "The Apriori algorithm is part of our affinity analysis and deals specifically with\n",
    "finding frequent itemsets within the data. The basic procedure of Apriori builds\n",
    "up new candidate itemsets from previously discovered frequent itemsets. These\n",
    "candidates are tested to see if they are frequent, and then the algorithm iterates as\n",
    "explained here:\n",
    "    \n",
    "1. Create initial frequent itemsets by placing each item in its own itemset. Only items with at least the minimum support are used in this step.\n",
    "2. New candidate itemsets are created from the most recently discovered frequent itemsets by finding supersets of the existing frequent itemsets.\n",
    "3. All candidate itemsets are tested to see if they are frequent. If a candidate is not frequent then it is discarded. If there are no new frequent itemsets from this step, go to the last step.\n",
    "4. Store the newly discovered frequent itemsets and go to the second step.\n",
    "5. Return all of the discovered frequent itemsets."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Implementation\n",
    "\n",
    "On the first iteration of Apriori, the newly discovered itemsets will have a length\n",
    "of 2, as they will be supersets of the initial itemsets created in the first step. On the\n",
    "second iteration (after applying the fourth step), the newly discovered itemsets will\n",
    "have a length of 3. This allows us to quickly identify the newly discovered itemsets,\n",
    "as needed in second step.\n",
    "\n",
    "We can store our discovered frequent itemsets in a dictionary, where the key is the\n",
    "length of the itemsets. This allows us to quickly access the itemsets of a given length,\n",
    "and therefore the most recently discovered frequent itemsets, with the help of the\n",
    "following code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "frequent_itemsets = {}  # itemsets are sorted by length"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We also need to define the minimum support needed for an itemset to be considered frequent. This value is chosen based on the dataset but feel free to try different\n",
    "values. I recommend only changing it by 10 percent at a time though, as the time the\n",
    "algorithm takes to run will be significantly different! Let's apply minimum support:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "min_support = 50"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To implement the first step of the Apriori algorithm, we create an itemset with each\n",
    "movie individually and test if the itemset is frequent. We use frozenset, as they\n",
    "allow us to perform set operations later on, and they can also be used as keys in our\n",
    "counting dictionary (normal sets cannot)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# k=1 candidates are the isbns with more than min_support favourable reviews\n",
    "frequent_itemsets[1] = dict((frozenset((movie_id,)), row[\"Favorable\"])\n",
    "                                for movie_id, row in num_favorable_by_movie.iterrows()\n",
    "                                if row[\"Favorable\"] > min_support)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We implement the second and third steps together for efficiency by creating a\n",
    "function that takes the newly discovered frequent itemsets, creates the supersets,\n",
    "and then tests if they are frequent. First, we set up the function and the counting\n",
    "dictionary. In keeping with our rule of thumb of reading through the data as little as possible,\n",
    "we iterate over the dataset once per call to this function. While this doesn't matter too\n",
    "much in this implementation (our dataset is relatively small), it is a good practice to\n",
    "get into for larger applications. We iterate over all of the users and their reviews. Next, we go through each of the previously discovered itemsets and see if it is a\n",
    "subset of the current set of reviews. If it is, this means that the user has reviewed\n",
    "each movie in the itemset. We can then go through each individual movie that the user has reviewed that isn't\n",
    "in the itemset, create a superset from it, and record in our counting dictionary that\n",
    "we saw this particular itemset. We end our function by testing which of the candidate itemsets have enough support\n",
    "to be considered frequent and return only those : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from collections import defaultdict\n",
    "\n",
    "def find_frequent_itemsets(favorable_reviews_by_users, k_1_itemsets, min_support):\n",
    "    counts = defaultdict(int)\n",
    "    for user, reviews in favorable_reviews_by_users.items():\n",
    "        for itemset in k_1_itemsets:\n",
    "            if itemset.issubset(reviews):\n",
    "                for other_reviewed_movie in reviews - itemset:\n",
    "                    current_superset = itemset | frozenset((other_reviewed_movie,))\n",
    "                    counts[current_superset] += 1\n",
    "    return dict([(itemset, frequency) for itemset, frequency in counts.items() if frequency >= min_support])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To run our code, we create a loop that iterates over the steps of the Apriori\n",
    "algorithm, storing the new itemsets as we go. In this loop, k represents the length\n",
    "of the soon-to-be discovered frequent itemsets, allowing us to access the previously\n",
    "most discovered ones by looking in our frequent_itemsets dictionary using the\n",
    "key k - 1. We create the frequent itemsets and store them in our dictionary by their\n",
    "length. We want to break out the preceding loop if we didn't find any new frequent itemsets\n",
    "(and also to print a message to let us know what is going on). If we do find frequent itemsets, we print out a message to let us know the loop will\n",
    "be running again. This algorithm can take a while to run, so it is helpful to know that\n",
    "the code is still running while you wait for it to complete! Finally, after the end of the loop, we are no longer interested in the first set of\n",
    "itemsets anymore—these are itemsets of length one, which won't help us create\n",
    "association rules – we need at least two items to create association rules. Let's\n",
    "delete them : \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are 16 movies with more than 50 favorable reviews\n",
      "I found 93 frequent itemsets of length 2\n",
      "I found 295 frequent itemsets of length 3\n",
      "I found 593 frequent itemsets of length 4\n",
      "I found 785 frequent itemsets of length 5\n",
      "I found 677 frequent itemsets of length 6\n",
      "I found 373 frequent itemsets of length 7\n",
      "I found 126 frequent itemsets of length 8\n",
      "I found 24 frequent itemsets of length 9\n",
      "I found 2 frequent itemsets of length 10\n",
      "Did not find any frequent itemsets of length 11\n"
     ]
    }
   ],
   "source": [
    "import sys\n",
    "\n",
    "print(\"There are {} movies with more than {} favorable reviews\".format(len(frequent_itemsets[1]), min_support))\n",
    "sys.stdout.flush()\n",
    "for k in range(2, 20):\n",
    "    # Generate candidates of length k, using the frequent itemsets of length k-1\n",
    "    # Only store the frequent itemsets\n",
    "    cur_frequent_itemsets = find_frequent_itemsets(favorable_reviews_by_users, frequent_itemsets[k-1],\n",
    "                                                   min_support)\n",
    "    if len(cur_frequent_itemsets) == 0:\n",
    "        print(\"Did not find any frequent itemsets of length {}\".format(k))\n",
    "        sys.stdout.flush()\n",
    "        break\n",
    "    else:\n",
    "        print(\"I found {} frequent itemsets of length {}\".format(len(cur_frequent_itemsets), k))\n",
    "        #print(cur_frequent_itemsets)\n",
    "        sys.stdout.flush()\n",
    "        frequent_itemsets[k] = cur_frequent_itemsets\n",
    "# We aren't interested in the itemsets of length 1, so remove those\n",
    "del frequent_itemsets[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This code may take a few minutes to run. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Found a total of 2968 frequent itemsets\n"
     ]
    }
   ],
   "source": [
    "print(\"Found a total of {0} frequent itemsets\".format(sum(len(itemsets) for itemsets in frequent_itemsets.values())))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "As we can see it returns 2968 frequent itemsets of varying lengths. You'll notice\n",
    "that the number of itemsets grows as the length increases before it shrinks. It grows\n",
    "because of the increasing number of possible rules. After a while, the large number\n",
    "of combinations no longer has the support necessary to be considered frequent.\n",
    "This results in the number shrinking. This shrinking is the benefit of the Apriori\n",
    "algorithm. If we search all possible itemsets (not just the supersets of frequent ones),\n",
    "we would be searching thousands of times more itemsets to see if they are frequent. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Extracting association rules\n",
    "\n",
    "After the Apriori algorithm has completed, we have a list of frequent itemsets.\n",
    "These aren't exactly association rules, but they are similar to it. A frequent itemset\n",
    "is a set of items with a minimum support, while an association rule has a premise\n",
    "and a conclusion.\n",
    "\n",
    "We can make an association rule from a frequent itemset by taking one of the movies\n",
    "in the itemset and denoting it as the conclusion. The other movies in the itemset will\n",
    "be the premise. This will form rules of the following form: if a reviewer recommends all\n",
    "of the movies in the premise, they will also recommend the conclusion.\n",
    "\n",
    "For each itemset, we can generate a number of association rules by setting each\n",
    "movie to be the conclusion and the remaining movies as the premise.\n",
    "\n",
    "In code, we first generate a list of all of the rules from each of the frequent itemsets,\n",
    "by iterating over each of the discovered frequent itemsets of each length. We then iterate over every movie in this itemset, using it as our conclusion.\n",
    "The remaining movies in the itemset are the premise. We save the premise and\n",
    "conclusion as our candidate rule. This returns a very large number of candidate rules. We can see some by printing\n",
    "out the first few rules in the list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "There are 15285 candidate rules\n"
     ]
    }
   ],
   "source": [
    "# Now we create the association rules. First, they are candidates until the confidence has been tested\n",
    "candidate_rules = []\n",
    "for itemset_length, itemset_counts in frequent_itemsets.items():\n",
    "    for itemset in itemset_counts.keys():\n",
    "        for conclusion in itemset:\n",
    "            premise = itemset - set((conclusion,))\n",
    "            candidate_rules.append((premise, conclusion))\n",
    "print(\"There are {} candidate rules\".format(len(candidate_rules)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(frozenset([50]), 64), (frozenset([64]), 50), (frozenset([127]), 181), (frozenset([181]), 127), (frozenset([127]), 1)]\n"
     ]
    }
   ],
   "source": [
    "print(candidate_rules[:5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "These rules were returned as the resulting output."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In these rules, the first part (the frozenset) is the list of movies in the premise,\n",
    "while the number after it is the conclusion. In the first case, if a reviewer\n",
    "recommends movie 50, they are also likely to recommend movie 64.\n",
    "\n",
    "Next, we compute the confidence of each of these rules. The process starts by creating dictionaries to store how many times we see the\n",
    "premise leading to the conclusion (a correct example of the rule) and how many\n",
    "times it doesn't (an incorrect example). We iterate over all of the users, their favorable reviews, and over each candidate\n",
    "association rule. We then test to see if the premise is applicable to this user. In other words, did the\n",
    "user favorably review all of the movies in the premise? If the premise applies, we see if the conclusion movie was also rated favorably.\n",
    "If so, the rule is correct in this instance. If not, it is incorrect. We then compute the confidence for each rule by dividing the correct count by the\n",
    "total number of times the rule was seen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Now, we compute the confidence of each of these rules. This is very similar to what we did in chapter 1\n",
    "correct_counts = defaultdict(int)\n",
    "incorrect_counts = defaultdict(int)\n",
    "for user, reviews in favorable_reviews_by_users.items():\n",
    "    for candidate_rule in candidate_rules:\n",
    "        premise, conclusion = candidate_rule\n",
    "        if premise.issubset(reviews):\n",
    "            if conclusion in reviews:\n",
    "                correct_counts[candidate_rule] += 1\n",
    "            else:\n",
    "                incorrect_counts[candidate_rule] += 1\n",
    "rule_confidence = {candidate_rule: \n",
    "                   correct_counts[candidate_rule] / float(correct_counts[candidate_rule] + incorrect_counts[candidate_rule])\n",
    "                    for candidate_rule in candidate_rules}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Choose only rules above a minimum confidence level\n",
    "min_confidence = 0.9"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5152\n"
     ]
    }
   ],
   "source": [
    "# Filter out the rules with poor confidence\n",
    "rule_confidence = {rule: confidence for rule, confidence in rule_confidence.items() if confidence > min_confidence}\n",
    "print(len(rule_confidence))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can print the top five rules by sorting this confidence dictionary and\n",
    "printing the results:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from operator import itemgetter\n",
    "sorted_confidence = sorted(rule_confidence.items(), key=itemgetter(1), reverse=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Rule #1\n",
      "Rule: If a person recommends frozenset([64, 56, 50, 98, 7]) they will also recommend 174\n",
      " - Confidence: 1.000\n",
      "\n",
      "Rule #2\n",
      "Rule: If a person recommends frozenset([98, 100, 7, 172, 50, 181]) they will also recommend 56\n",
      " - Confidence: 1.000\n",
      "\n",
      "Rule #3\n",
      "Rule: If a person recommends frozenset([64, 98, 100, 7, 172, 50]) they will also recommend 56\n",
      " - Confidence: 1.000\n",
      "\n",
      "Rule #4\n",
      "Rule: If a person recommends frozenset([64, 98, 100, 50, 56, 127]) they will also recommend 174\n",
      " - Confidence: 1.000\n",
      "\n",
      "Rule #5\n",
      "Rule: If a person recommends frozenset([98, 100, 172, 79, 50, 56]) they will also recommend 7\n",
      " - Confidence: 1.000\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for index in range(5):\n",
    "    print(\"Rule #{0}\".format(index + 1))\n",
    "    (premise, conclusion) = sorted_confidence[index][0]\n",
    "    print(\"Rule: If a person recommends {0} they will also recommend {1}\".format(premise, conclusion))\n",
    "    print(\" - Confidence: {0:.3f}\".format(rule_confidence[(premise, conclusion)]))\n",
    "    print(\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The resulting printout shows only the movie IDs, which isn't very helpful without\n",
    "the names of the movies also. The dataset came with a file called u.items, which\n",
    "stores the movie names and their corresponding MovieID (as well as other\n",
    "information, such as the genre).\n",
    "\n",
    "We can load the titles from this file using pandas. Additional information about\n",
    "the file and categories is available in the README that came with the dataset.\n",
    "The data in the files is in CSV format, but with data separated by the | symbol;\n",
    "it has no header and the encoding is important to set. The column names were\n",
    "found in the README file"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Even better, we can get the movie titles themselves from the dataset\n",
    "movie_name_filename = 'data/ml-100k/u.item'\n",
    "movie_name_data = pd.read_csv(movie_name_filename, delimiter=\"|\", header=None, encoding = \"mac-roman\")\n",
    "movie_name_data.columns = [\"MovieID\", \"Title\", \"Release Date\", \"Video Release\", \"IMDB\", \"<UNK>\", \"Action\", \"Adventure\",\n",
    "                           \"Animation\", \"Children's\", \"Comedy\", \"Crime\", \"Documentary\", \"Drama\", \"Fantasy\", \"Film-Noir\",\n",
    "                           \"Horror\", \"Musical\", \"Mystery\", \"Romance\", \"Sci-Fi\", \"Thriller\", \"War\", \"Western\"]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Getting the movie title is important, so we will create a function that will return a\n",
    "movie's title from its MovieID, saving us the trouble of looking it up each time. We look up the movie_name_data DataFrame for the given MovieID and return only\n",
    "the title column. We use the values parameter to get the actual value (and not the pandas Series\n",
    "object that is currently stored in title_object). We are only interested in the first\n",
    "value—there should only be one title for a given MovieID anyway! We end the function by returning the title as needed."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "def get_movie_name(movie_id):\n",
    "    title_object = movie_name_data[movie_name_data[\"MovieID\"] == movie_id][\"Title\"]\n",
    "    title = title_object.values[0]\n",
    "    return title"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "u'Get Shorty (1995)'"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_movie_name(4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We adjust our previous code for printing out the top\n",
    "rules to also include the titles"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Rule #1\n",
      "Rule: If a person recommends Shawshank Redemption, The (1994), Pulp Fiction (1994), Star Wars (1977), Silence of the Lambs, The (1991), Twelve Monkeys (1995) they will also recommend Raiders of the Lost Ark (1981)\n",
      " - Confidence: 1.000\n",
      "\n",
      "Rule #2\n",
      "Rule: If a person recommends Silence of the Lambs, The (1991), Fargo (1996), Twelve Monkeys (1995), Empire Strikes Back, The (1980), Star Wars (1977), Return of the Jedi (1983) they will also recommend Pulp Fiction (1994)\n",
      " - Confidence: 1.000\n",
      "\n",
      "Rule #3\n",
      "Rule: If a person recommends Shawshank Redemption, The (1994), Silence of the Lambs, The (1991), Fargo (1996), Twelve Monkeys (1995), Empire Strikes Back, The (1980), Star Wars (1977) they will also recommend Pulp Fiction (1994)\n",
      " - Confidence: 1.000\n",
      "\n",
      "Rule #4\n",
      "Rule: If a person recommends Shawshank Redemption, The (1994), Silence of the Lambs, The (1991), Fargo (1996), Star Wars (1977), Pulp Fiction (1994), Godfather, The (1972) they will also recommend Raiders of the Lost Ark (1981)\n",
      " - Confidence: 1.000\n",
      "\n",
      "Rule #5\n",
      "Rule: If a person recommends Silence of the Lambs, The (1991), Fargo (1996), Empire Strikes Back, The (1980), Fugitive, The (1993), Star Wars (1977), Pulp Fiction (1994) they will also recommend Twelve Monkeys (1995)\n",
      " - Confidence: 1.000\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for index in range(5):\n",
    "    print(\"Rule #{0}\".format(index + 1))\n",
    "    (premise, conclusion) = sorted_confidence[index][0]\n",
    "    premise_names = \", \".join(get_movie_name(idx) for idx in premise)\n",
    "    conclusion_name = get_movie_name(conclusion)\n",
    "    print(\"Rule: If a person recommends {0} they will also recommend {1}\".format(premise_names, conclusion_name))\n",
    "    print(\" - Confidence: {0:.3f}\".format(rule_confidence[(premise, conclusion)]))\n",
    "    print(\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The result is much more readable (there are still some issues, but we can ignore them\n",
    "for now.)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Evaluation\n",
    "\n",
    "In a broad sense, we can evaluate the association rules using the same concept as for\n",
    "classification. We use a test set of data that was not used for training, and evaluate\n",
    "our discovered rules based on their performance in this test set.\n",
    "\n",
    "To do this, we will compute the test set confidence, that is, the confidence of each\n",
    "rule on the testing set.\n",
    "We won't apply a formal evaluation metric in this case; we simply examine the rules\n",
    "and look for good examples.\n",
    "\n",
    "First, we extract the test dataset, which is all of the records we didn't use in the\n",
    "training set. We used the first 200 users (by ID value) for the training set, and we will\n",
    "use all of the rest for the testing dataset. As with the training set, we will also get the\n",
    "favorable reviews for each of the users in this dataset as well. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Evaluation using test data\n",
    "test_dataset = all_ratings[~all_ratings['UserID'].isin(range(200))]\n",
    "test_favorable = test_dataset[test_dataset[\"Favorable\"]]\n",
    "#test_not_favourable = test_dataset[~test_dataset[\"Favourable\"]]\n",
    "test_favorable_by_users = dict((k, frozenset(v.values)) for k, v in test_favorable.groupby(\"UserID\")[\"MovieID\"])\n",
    "#test_not_favourable_by_users = dict((k, frozenset(v.values)) for k, v in test_not_favourable.groupby(\"UserID\")[\"MovieID\"])\n",
    "#test_users = test_dataset[\"UserID\"].unique()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>UserID</th>\n",
       "      <th>MovieID</th>\n",
       "      <th>Rating</th>\n",
       "      <th>Datetime</th>\n",
       "      <th>Favorable</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th>3</th>\n",
       "      <td>244</td>\n",
       "      <td>51</td>\n",
       "      <td>2</td>\n",
       "      <td>1997-11-27 05:02:03</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>5</th>\n",
       "      <td>298</td>\n",
       "      <td>474</td>\n",
       "      <td>4</td>\n",
       "      <td>1998-01-07 14:20:06</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>7</th>\n",
       "      <td>253</td>\n",
       "      <td>465</td>\n",
       "      <td>5</td>\n",
       "      <td>1998-04-03 18:34:27</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>8</th>\n",
       "      <td>305</td>\n",
       "      <td>451</td>\n",
       "      <td>3</td>\n",
       "      <td>1998-02-01 09:20:17</td>\n",
       "      <td>False</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th>11</th>\n",
       "      <td>286</td>\n",
       "      <td>1014</td>\n",
       "      <td>5</td>\n",
       "      <td>1997-11-17 15:38:45</td>\n",
       "      <td>True</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "    UserID  MovieID  Rating            Datetime Favorable\n",
       "3      244       51       2 1997-11-27 05:02:03     False\n",
       "5      298      474       4 1998-01-07 14:20:06      True\n",
       "7      253      465       5 1998-04-03 18:34:27      True\n",
       "8      305      451       3 1998-02-01 09:20:17     False\n",
       "11     286     1014       5 1997-11-17 15:38:45      True"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "test_dataset[:5]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We then count the correct instances where the premise leads to the conclusion, in the\n",
    "same way we did before. The only change here is the use of the test data instead of\n",
    "the training data."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "correct_counts = defaultdict(int)\n",
    "incorrect_counts = defaultdict(int)\n",
    "for user, reviews in test_favorable_by_users.items():\n",
    "    for candidate_rule in candidate_rules:\n",
    "        premise, conclusion = candidate_rule\n",
    "        if premise.issubset(reviews):\n",
    "            if conclusion in reviews:\n",
    "                correct_counts[candidate_rule] += 1\n",
    "            else:\n",
    "                incorrect_counts[candidate_rule] += 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " Next, we compute the confidence of each rule from the correct counts. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5152\n"
     ]
    }
   ],
   "source": [
    "test_confidence = {candidate_rule: correct_counts[candidate_rule] / float(correct_counts[candidate_rule] + incorrect_counts[candidate_rule])\n",
    "                   for candidate_rule in rule_confidence}\n",
    "print(len(test_confidence))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[((frozenset([64, 1, 7, 172, 79, 50]), 174), 1.0), ((frozenset([64, 98, 7, 258, 174, 181]), 172), 1.0), ((frozenset([64, 1, 98, 7, 79, 181, 56]), 174), 1.0), ((frozenset([64, 1, 98, 172, 79, 181, 56]), 174), 1.0), ((frozenset([64, 1, 98, 7, 172, 79, 181]), 174), 1.0)]\n"
     ]
    }
   ],
   "source": [
    "sorted_test_confidence = sorted(test_confidence.items(), key=itemgetter(1), reverse=True)\n",
    "print(sorted_test_confidence[:5])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we print out the best association rules with the titles instead of the\n",
    "movie IDs. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Rule #1\n",
      "Rule: If a person recommends Shawshank Redemption, The (1994), Pulp Fiction (1994), Star Wars (1977), Silence of the Lambs, The (1991), Twelve Monkeys (1995) they will also recommend Raiders of the Lost Ark (1981)\n",
      " - Train Confidence: 1.000\n",
      " - Test Confidence: 0.909\n",
      "\n",
      "Rule #2\n",
      "Rule: If a person recommends Silence of the Lambs, The (1991), Fargo (1996), Twelve Monkeys (1995), Empire Strikes Back, The (1980), Star Wars (1977), Return of the Jedi (1983) they will also recommend Pulp Fiction (1994)\n",
      " - Train Confidence: 1.000\n",
      " - Test Confidence: 0.811\n",
      "\n",
      "Rule #3\n",
      "Rule: If a person recommends Shawshank Redemption, The (1994), Silence of the Lambs, The (1991), Fargo (1996), Twelve Monkeys (1995), Empire Strikes Back, The (1980), Star Wars (1977) they will also recommend Pulp Fiction (1994)\n",
      " - Train Confidence: 1.000\n",
      " - Test Confidence: 0.824\n",
      "\n",
      "Rule #4\n",
      "Rule: If a person recommends Shawshank Redemption, The (1994), Silence of the Lambs, The (1991), Fargo (1996), Star Wars (1977), Pulp Fiction (1994), Godfather, The (1972) they will also recommend Raiders of the Lost Ark (1981)\n",
      " - Train Confidence: 1.000\n",
      " - Test Confidence: 0.848\n",
      "\n",
      "Rule #5\n",
      "Rule: If a person recommends Silence of the Lambs, The (1991), Fargo (1996), Empire Strikes Back, The (1980), Fugitive, The (1993), Star Wars (1977), Pulp Fiction (1994) they will also recommend Twelve Monkeys (1995)\n",
      " - Train Confidence: 1.000\n",
      " - Test Confidence: 0.609\n",
      "\n",
      "Rule #6\n",
      "Rule: If a person recommends Shawshank Redemption, The (1994), Silence of the Lambs, The (1991), Fargo (1996), Twelve Monkeys (1995), Empire Strikes Back, The (1980), Star Wars (1977) they will also recommend Raiders of the Lost Ark (1981)\n",
      " - Train Confidence: 1.000\n",
      " - Test Confidence: 0.971\n",
      "\n",
      "Rule #7\n",
      "Rule: If a person recommends Shawshank Redemption, The (1994), Toy Story (1995), Twelve Monkeys (1995), Empire Strikes Back, The (1980), Fugitive, The (1993), Star Wars (1977) they will also recommend Return of the Jedi (1983)\n",
      " - Train Confidence: 1.000\n",
      " - Test Confidence: 0.900\n",
      "\n",
      "Rule #8\n",
      "Rule: If a person recommends Toy Story (1995), Silence of the Lambs, The (1991), Fargo (1996), Raiders of the Lost Ark (1981), Godfather, The (1972) they will also recommend Pulp Fiction (1994)\n",
      " - Train Confidence: 1.000\n",
      " - Test Confidence: 0.750\n",
      "\n",
      "Rule #9\n",
      "Rule: If a person recommends Silence of the Lambs, The (1991), Godfather, The (1972), Empire Strikes Back, The (1980), Raiders of the Lost Ark (1981), Twelve Monkeys (1995) they will also recommend Shawshank Redemption, The (1994)\n",
      " - Train Confidence: 1.000\n",
      " - Test Confidence: 0.854\n",
      "\n",
      "Rule #10\n",
      "Rule: If a person recommends Pulp Fiction (1994), Toy Story (1995), Shawshank Redemption, The (1994), Godfather, The (1972) they will also recommend Silence of the Lambs, The (1991)\n",
      " - Train Confidence: 1.000\n",
      " - Test Confidence: 0.870\n",
      "\n"
     ]
    }
   ],
   "source": [
    "for index in range(10):\n",
    "    print(\"Rule #{0}\".format(index + 1))\n",
    "    (premise, conclusion) = sorted_confidence[index][0]\n",
    "    premise_names = \", \".join(get_movie_name(idx) for idx in premise)\n",
    "    conclusion_name = get_movie_name(conclusion)\n",
    "    print(\"Rule: If a person recommends {0} they will also recommend {1}\".format(premise_names, conclusion_name))\n",
    "    print(\" - Train Confidence: {0:.3f}\".format(rule_confidence.get((premise, conclusion), -1)))\n",
    "    print(\" - Test Confidence: {0:.3f}\".format(test_confidence.get((premise, conclusion), -1)))\n",
    "    print(\"\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "The fifth rule, for instance, has a perfect confidence in the training data (1.000), but it\n",
    "is only accurate in 60 percent of cases for the test data (0.609). Many of the other rules in\n",
    "the top 10 have high confidences in test data though, making them good rules for\n",
    "making recommendations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Summary\n",
    "\n",
    "In this example, we performed affinity analysis in order to recommend movies based\n",
    "on a large set of reviewers. We did this in two stages. First, we found frequent\n",
    "itemsets in the data using the Apriori algorithm. Then, we created association rules\n",
    "from those itemsets.\n",
    "\n",
    "The use of the Apriori algorithm was necessary due to the size of the dataset.\n",
    "We performed training on a subset of our data in order to find the association rules,\n",
    "and then tested those rules on the rest of the data—a testing set. From what we\n",
    "discussed in the previous chapters, we could extend this concept to use cross-fold\n",
    "validation to better evaluate the rules. This would lead to a more robust evaluation\n",
    "of the quality of each rule\n",
    "\n",
    "___"
   ]
  }
 ],
 "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}