HW4.ipynb

{
  "metadata": {
    "name": ""
  }, 
  "nbformat": 3, 
  "nbformat_minor": 0, 
  "worksheets": [
    {
      "cells": [
        {
          "source": [
            "HW4: Do we really need Chocolate Recommendations?"
          ], 
          "cell_type": "heading", 
          "metadata": {}, 
          "level": 1
        }, 
        {
          "source": [
            "<img src=\"http://1.bp.blogspot.com/-8dGYKeMKNaU/TvutmCenc-I/AAAAAAAABEo/b2Czf4RlAzw/s1600/Death%2BBy%2BChocolate.JPG\" width=\"400\" height=\"300\"/>"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###Before You Start\n", 
            "\n", 
            "This is a **long** homework. Please start early. It uses a lot of different (and sometimes complex) concepts, so you might find yourself reading a lot. So, please, give yourself a lot of time.\n", 
            "\n", 
            "Also, please see this [link](http://nbviewer.ipython.org/urls/raw.github.com/cs109/content/master/InstructionsForAmazonEMR.ipynb) on getting an Amazon Web Services account soon, so that you dont delay its creation. This class gives you $100 in credits which you will use for this homework, possibly your project, and any other projects you might like.\n", 
            "\n", 
            "Finally, please go to the labs. The one on 18th October (Today) will cover Gibbs Sampling and Bayesian Normal distributions. The one on the 25th will cover Map-Reduce. Both will help on the homework."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###Collaborative Filtering systems\n", 
            "\n", 
            "In this homework, you will create a recommendation system for **restaurants** using [collaborative filtering](http://en.wikipedia.org/wiki/Collaborative_filtering) (CF). The general structure of a recommendation system is that there are users and there are items. Users express explicit or implicit preferences towards certain items. CF thus relies on users' past behavior.\n", 
            "\n", 
            "There are two primary approaches to CF: neighboorhood and latent factor model. The former is concerned with computing the relationships between items or between users. In the latter approach you have a model of hidden factors through which users and items are transformed to the same space. For example, if you are rating movies we may transform items into genre factors, and users into their preference for a particular genre.\n", 
            "\n", 
            "Factor models generally lead to more accurate recommenders. One of the reasons for this is the sparsity of the item-user matrix. Most users tend to rate barely one or two items. Latent factor models are more expressive, and fit fewer parameters. However, neighborhood models are more prevalent, as they have an intuitive aspect that appeals to users(if you liked this you will like that) and online(a new preference can be incorporated very quickly).\n", 
            "\n", 
            "Most recommenders today combine neighboorhood CF with model based CF, and SVD based matrix factorization approaches.\n", 
            "\n", 
            "To see the example of a simple beer recommender, go [here](http://nbviewer.ipython.org/20a18d52c539b87de2af). This homework is inspired by the one there but we go after food instead, and go deeper into the problem of making recommendations."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "### User and Item based approaches\n", 
            "\n", 
            "Original approaches to neighborhood based CF used user-user models. By this we mean that rating estimates are made from recorded ratings of like minded users. However, since most users tend to rate very few items, this is usually a losing proposition for explicit-rating based recommenders. Thus, most neighborhood based systems such as Amazon these days rely on item-item approaches. In these methods, a rating is estimated by other ratings made by the user on \"similar\" or \"nearby\" items: we have a K-Nearest-Neighbors algorithm, in effect."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###Outline of this Homework\n", 
            "\n", 
            "The outline of this homework is as follows:\n", 
            "\n", 
            "1. Create a database of item-item similarities. Use this to implement a neighborhood-based CF recommender that can answer simple questions like \"give me more restaurants like this one\". This part of the homework assumes that the similaties calculated make good \"global recommendations\".\n", 
            "\n", 
            "2. In the second part, we go one step further and attempt to predict the rating that a user will give an item they have not seen before. This requires that we find the restaurants that *this* user would rate as similar (not just those which are globally similar). \n", 
            "\n", 
            "3. In the third part, we implement a factor-based CF recommender using a Bayesian model. While quite a bit more complex, this allows us to pool information both about similar users and about similar restaurants.\n", 
            "\n", 
            "5. We will scale up our system by creating a recommender on the lines of Q1 and Q2 that works on the entire data set. We will use the map-reduce paradigm to split the computation over multiple machines."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "You will start simply, by working on a subset of the restaurant data before generalizing to the entire data set in Problem 4. The complete data set has 150,000 reviews, but we shall start with just about 7000. You will create this  smaller set by taking all the users who had rated more than 60 restaurants, and all the businesses which had greater than 150 reviews from the larger data set. This is not a random set: indeed we use it as it a computationally tractable set that is a bit less sparse than the entire data set."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 1, 
          "input": [
            "%matplotlib inline\n", 
            "from collections import defaultdict\n", 
            "import json\n", 
            "\n", 
            "import numpy as np\n", 
            "import scipy as sp\n", 
            "import matplotlib.pyplot as plt\n", 
            "import pandas as pd\n", 
            "\n", 
            "from matplotlib import rcParams\n", 
            "import matplotlib.cm as cm\n", 
            "import matplotlib as mpl\n", 
            "\n", 
            "#colorbrewer2 Dark2 qualitative color table\n", 
            "dark2_colors = [(0.10588235294117647, 0.6196078431372549, 0.4666666666666667),\n", 
            "                (0.8509803921568627, 0.37254901960784315, 0.00784313725490196),\n", 
            "                (0.4588235294117647, 0.4392156862745098, 0.7019607843137254),\n", 
            "                (0.9058823529411765, 0.1607843137254902, 0.5411764705882353),\n", 
            "                (0.4, 0.6509803921568628, 0.11764705882352941),\n", 
            "                (0.9019607843137255, 0.6705882352941176, 0.00784313725490196),\n", 
            "                (0.6509803921568628, 0.4627450980392157, 0.11372549019607843)]\n", 
            "\n", 
            "rcParams['figure.figsize'] = (10, 6)\n", 
            "rcParams['figure.dpi'] = 150\n", 
            "rcParams['axes.color_cycle'] = dark2_colors\n", 
            "rcParams['lines.linewidth'] = 2\n", 
            "rcParams['axes.facecolor'] = 'white'\n", 
            "rcParams['font.size'] = 14\n", 
            "rcParams['patch.edgecolor'] = 'white'\n", 
            "rcParams['patch.facecolor'] = dark2_colors[0]\n", 
            "rcParams['font.family'] = 'StixGeneral'\n", 
            "\n", 
            "\n", 
            "def remove_border(axes=None, top=False, right=False, left=True, bottom=True):\n", 
            "    \"\"\"\n", 
            "    Minimize chartjunk by stripping out unnecesasry plot borders and axis ticks\n", 
            "    \n", 
            "    The top/right/left/bottom keywords toggle whether the corresponding plot border is drawn\n", 
            "    \"\"\"\n", 
            "    ax = axes or plt.gca()\n", 
            "    ax.spines['top'].set_visible(top)\n", 
            "    ax.spines['right'].set_visible(right)\n", 
            "    ax.spines['left'].set_visible(left)\n", 
            "    ax.spines['bottom'].set_visible(bottom)\n", 
            "    \n", 
            "    #turn off all ticks\n", 
            "    ax.yaxis.set_ticks_position('none')\n", 
            "    ax.xaxis.set_ticks_position('none')\n", 
            "    \n", 
            "    #now re-enable visibles\n", 
            "    if top:\n", 
            "        ax.xaxis.tick_top()\n", 
            "    if bottom:\n", 
            "        ax.xaxis.tick_bottom()\n", 
            "    if left:\n", 
            "        ax.yaxis.tick_left()\n", 
            "    if right:\n", 
            "        ax.yaxis.tick_right()\n", 
            "        \n", 
            "pd.set_option('display.width', 500)\n", 
            "pd.set_option('display.max_columns', 100)"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "### Description of the data set\n", 
            "\n", 
            "The data set has been extracted from the Yelp Phoenix restaurants dataset. It is available [here](https://dl.dropboxusercontent.com/u/75194/bigdf.csv)."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 2, 
          "input": [
            "fulldf=pd.read_csv(\"bigdf.csv\")\n", 
            "fulldf.head(2)"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "The data frame is a frame of reviews. We have joined in information about users and businesses into this frame so that you have only one frame to work with."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "This information is for the reviews themselves:"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "  'stars': (star rating, integer 1-5),\n", 
            "  'date': (date, formatted like '2011-04-19'),\n", 
            "  'review_id': (unique id for the review)."
          ], 
          "cell_type": "raw", 
          "metadata": {}
        }, 
        {
          "source": [
            "Here is a description of the data fields in this dataframe, on the business side"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "  'business_id': (a unique identifier for this business),\n", 
            "  'biz_name': (the full business name),\n", 
            "  'latitude': (latitude),\n", 
            "  'longitude': (longitude),\n", 
            "  'business_review_count': (review count for the restaurant[this is a repeated field for all reviews of the restaurant]),\n", 
            "  'categories': [(localized category names)],\n", 
            "  'business_avg': (average stars over all users reviews for business[this is a repeated field for all reviews of the restaurant])."
          ], 
          "cell_type": "raw", 
          "metadata": {}
        }, 
        {
          "source": [
            "And Finally, a set of fields for users"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "  'user_id': (unique user identifier),\n", 
            "  'user_name': (first name, last initial, like 'Matt J.'),\n", 
            "  'user_review_count': (count of restaurants reviewed by user[this is a repeated field for all reviews by the user]),\n", 
            "  'user_avg': (floating point average of users reviews over all businesses, like 4.31[this is a repeated field for all reviews by the user])."
          ], 
          "cell_type": "raw", 
          "metadata": {}
        }, 
        {
          "source": [
            "In this data set, every user has only one review for each restaurant. Convince yourself of this. (This answer does not need to be submitted)."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###Our Recommender\n", 
            "\n", 
            "To motivate our recommendation system, consider the follwing example. Let's pretend we are in Boston for a second. Lets say the average rating of restaurants here by all the users is 3.5. Sandrine's at Harvard square is better than an average restaurant, so it tends to be rated 0.5 stars above the average (over all the users). However, you are a curmudgeon, who tends to rate 0.2 stars below the average. Then a baseline estimate for the recommendation for Sandrine's, for you, is 3.5+0.5-0.2=3.8.\n", 
            "\n", 
            "These baseline estimates thus adjust the data by accounting for the systematic tendencies for some users who give higher ratings than others, and for some restaurants to recieve higher ratings than others. We can write the baseline estimate $\\hat Y_{um}^{baseline}$ for an unknown rating $Y_{um}$ for user $u$ and restaurant or business $m$ as:\n", 
            "\n", 
            "$$ \\hat Y_{um}^{baseline} = \\hat \\mu + \\hat \\theta_{u0} + \\hat \\gamma_{m0} $$\n", 
            "\n", 
            "where the unknown parameters $\\theta_{u0}$ and $\\gamma_{m0}$ indicate the deviations, or biases, of user $u$ and item $m$, respectively, from some intercept parameter $\\mu$. (The reason for the strange notation with 0s will become clear in Problem 3)\n", 
            "\n", 
            "Notice that the $\\theta_{u0}$ and $\\gamma_{m0}$ are parameters which need to be fit. The simplest thing to start with, and something we will do for Problems 1 and 2 (but not 3), is to replace them by their \"mean\" estimates from the data. Thus:\n", 
            "\n", 
            "$$ \\hat Y^{baseline}_{um} = \\bar Y + (\\bar Y_u - \\bar Y) + (\\bar Y_m - \\bar Y)$$\n", 
            "\n", 
            "where $\\bar Y_u$ =  `user_avg`, the average of all a user $u$'s ratings and $\\bar Y_m$ = `business_avg`, the average of all ratings for a restaurant $m$. $\\bar Y$ is the average rating over all reviews.\n", 
            "\n", 
            "The final two terms correspond to the user-specific and item-specific bias in ratings, that is, how their ratings tend to systematically diverge from the global average. This is the simplest possible way to predict a rating, based only on information about *this* user and *this* restaurant.\n", 
            "\n", 
            "Can we do a better job of predicting the rating $Y_{um}$ user $u$ would give to restaurant $r$? According to the central dogma of CF, we ought to be able to use the responses of *similar* users regarding *similar* restaurants to get a better prediction. \n", 
            "\n", 
            "We can make an estimate of $Y_{um}$ as:\n", 
            "\n", 
            "$$ \\hat{Y_{um}} = \\hat Y_{um}^{baseline}\\, + \\,\\frac{\\sum\\limits_{j \\in S^{k}(m)} s_{mj} ( Y_{uj} - \\hat Y_{uj}^{baseline} )}{\\sum\\limits_{j \\in S^{k}(m)} s_{mj} } $$\n", 
            "\n", 
            "where $s^{k}(m)$ is the $k$ neighbor items of item $m$ based on some pooling criterion, for example, those items which have been rated by user $u$.\n", 
            "\n", 
            "In the next two problems, we will focus on using similar restaurants, or the item neighborhood.\n", 
            "To do this, we compute a *similarity measure* $s_{mj}$ between the $m$th and $j$th items. This similarity might be measured via [cosine similarity](http://en.wikipedia.org/wiki/Cosine_similarity), [pearson co-efficient](http://en.wikipedia.org/wiki/Pearson_product-moment_correlation_coefficient) or using other distance based measures. Here we shall use the Pearson coefficient. This measures the tendency of users to rate items similarly. Since most ratings are unknown, it is computed on the \"common user support\" (`n_common`), which is the set of common raters of both items. \n", 
            "\n", 
            "In the first problem we shall set $S$ to the global neighborhood of the item, and in the second we shall set it to those items which have been rated by user $u$."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "##Q1. Writing a simple \"global\" recommender"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "Now we have a way to pool information between similar restaurants to try to predict a user's recommendation. But how do we choose the neighborhood to pool over? We begin with the simplest choice. We calculate the similarity between items using their entire common user support, and rank the nearest neighbors of an item by this similarity. We call this a \"global\" recommender because it assumes that every user perceives the similarity between restaurants in the same way. Later on, we will implement a more specific recommender that pools information based on which items seem the most similar *to this user*.\n", 
            "\n", 
            "The global recommender does have the advantage of dealing with the possible sparsity of the user's rated items, but also the disadvantage of giving one answer for all users, without taking the user's preferences into account. This is a classic case of bias-variance tradeoff.\n", 
            "\n", 
            "Lets implement this simpler global recommender first.\n"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "### Exploratory Data Analysis"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**1.1** Visualize the sparsity of the full data set by plotting two histograms of the review count  grouped by the `user_id` and `business_id` respectively. Are there more users or more businesses? "
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 3, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 4, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 5, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "*your answer here*"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**1.2** Compute the average rating of reviews in the data set and a histogram of all the ratings in the dataset."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 6, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "The following function is used to re-compute review counts and averages whenever you subset a reviews data frame. We'll use it soon to construct a smaller, more computationally tractable data frame."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 7, 
          "input": [
            "def recompute_frame(ldf):\n", 
            "    \"\"\"\n", 
            "    takes a dataframe ldf, makes a copy of it, and returns the copy\n", 
            "    with all averages and review counts recomputed\n", 
            "    this is used when a frame is subsetted.\n", 
            "    \"\"\"\n", 
            "    ldfu=ldf.groupby('user_id')\n", 
            "    ldfb=ldf.groupby('business_id')\n", 
            "    user_avg=ldfu.stars.mean()\n", 
            "    user_review_count=ldfu.review_id.count()\n", 
            "    business_avg=ldfb.stars.mean()\n", 
            "    business_review_count=ldfb.review_id.count()\n", 
            "    nldf=ldf.copy()\n", 
            "    nldf.set_index(['business_id'], inplace=True)\n", 
            "    nldf['business_avg']=business_avg\n", 
            "    nldf['business_review_count']=business_review_count\n", 
            "    nldf.reset_index(inplace=True)\n", 
            "    nldf.set_index(['user_id'], inplace=True)\n", 
            "    nldf['user_avg']=user_avg\n", 
            "    nldf['user_review_count']=user_review_count\n", 
            "    nldf.reset_index(inplace=True)\n", 
            "    return nldf"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "**1.3** Create a smaller data set in dataframe `smalldf` by looking for those businesses with more than 150 reviews and those users with more than 60 reviews. Include all the columns that were there in the parent dataframe. Since you have created a subset of the data set, use the method provided above to recalculate the averages. Print the number of unique users and items in this data set.  \n", 
            "\n", 
            "Note that while this cut makes sure we have prolific users, the cut on businesses restores sparsity  by reducing the number of reviews per user."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 8, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "How does this compare to the parent data set, in terms of size and sparsity? Once again, plot histograms of the review count grouped by user, and by the review count grouped by business, respectively, and describe the results"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 9, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "*your answer here*"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**1.4** Compute histograms of the average user rating in the smaller data set, and the average business rating in the smaller data set. Print the overall mean."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 10, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "###Common Support\n", 
            "\n", 
            "Lets now make a histogram of the common user support (the number of common reviewers) of each pair of restaurants on the smaller set, and print the mean. Pay attention to the code, as you will use parts of it later. (This code takes a bit of time to run, so be patient).\n", 
            "\n", 
            "The common support is an important concept, as for each pair of restaurants, its the number of people who reviewed both. It will be used to modify similarity between restaurants. If the common support is low, the similarity is less believable."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 11, 
          "input": [
            "restaurants=smalldf.business_id.unique()\n", 
            "supports=[]\n", 
            "for i,rest1 in enumerate(restaurants):\n", 
            "    for j,rest2 in enumerate(restaurants):\n", 
            "        if  i < j:\n", 
            "            rest1_reviewers = smalldf[smalldf.business_id==rest1].user_id.unique()\n", 
            "            rest2_reviewers = smalldf[smalldf.business_id==rest2].user_id.unique()\n", 
            "            common_reviewers = set(rest1_reviewers).intersection(rest2_reviewers)\n", 
            "            supports.append(len(common_reviewers))\n", 
            "print \"Mean support is:\",np.mean(supports)\n", 
            "plt.hist(supports)"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "As you can see, even though we chose a subset of the dataframe in which every restaurant had 150 reviews and every user had atleast made 60, the common support of most pairs of restaurants is really low, indeed less than 10!."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "### Calculating Similarity"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "Users rate restaurants on a scale of 1-5. Even though this rating is integer valued, for the purposes of this assignment we shall treat it as a real number.\n", 
            "\n", 
            "Even though each reviewer uses the same 5-star scale when rating restaurants, comparing two users by comparing their raw user ratings can be problematic. Consider a user whose average rating is 2. This is a curmudgeonly user. Consider another whose average rating is 4. This is a rather enthusiastic one. How should we compare a 3 rating by the curmudgeonly one to a 5 rating of the enthusiastic one?\n", 
            "\n", 
            "It is for this purpose that we must subtract the average rating of the user from the actual rating of the restaurants in computing the similarity of two restaurants. This makes the above ratings by the two users comparable. We do this in the function `pearson_sim` defined below.\n", 
            "\n", 
            "If there is no common support (`n_common=0`), we have no basis for making a similarity estimate, and so we set the similarity to 0. In the case that the individual restaurant rating variance is 0, such as in the case where there is only one common reviewer (`n_common=1`), we return the `NaN` that the scipy `pearsonr` returns. We will deal with it soon,"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 12, 
          "input": [
            "from scipy.stats.stats import pearsonr\n", 
            "def pearson_sim(rest1_reviews, rest2_reviews, n_common):\n", 
            "    \"\"\"\n", 
            "    Given a subframe of restaurant 1 reviews and a subframe of restaurant 2 reviews,\n", 
            "    where the reviewers are those who have reviewed both restaurants, return \n", 
            "    the pearson correlation coefficient between the user average subtracted ratings.\n", 
            "    The case for zero common reviewers is handled separately. Its\n", 
            "    ok to return a NaN if any of the individual variances are 0.\n", 
            "    \"\"\"\n", 
            "    if n_common==0:\n", 
            "        rho=0.\n", 
            "    else:\n", 
            "        diff1=rest1_reviews['stars']-rest1_reviews['user_avg']\n", 
            "        diff2=rest2_reviews['stars']-rest2_reviews['user_avg']\n", 
            "        rho=pearsonr(diff1, diff2)[0]\n", 
            "    return rho"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "The function `get_restaurant_reviews` defined below takes a restaurant `business_id` and a set of users, and returns the reviews of that restaurant by those users. You will use this function in calculating a similarity function, in **1.5**."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 13, 
          "input": [
            "def get_restaurant_reviews(restaurant_id, df, set_of_users):\n", 
            "    \"\"\"\n", 
            "    given a resturant id and a set of reviewers, return the sub-dataframe of their\n", 
            "    reviews.\n", 
            "    \"\"\"\n", 
            "    mask = (df.user_id.isin(set_of_users)) & (df.business_id==restaurant_id)\n", 
            "    reviews = df[mask]\n", 
            "    reviews = reviews[reviews.user_id.duplicated()==False]\n", 
            "    return reviews"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "**1.5** Write a function `calculate_similarity` that operates between two restaurants and calculates a similarity for them, taking a dataframe and a similarity function `similarity_func`. An example of the `similarity_func` is the `pearson_sim` we defined above. `calculate_similarity` operates as follows: \n", 
            "\n", 
            "1. For each of the two restaurants, get the set of reviewers who have reviewed the restaurant and compute the intersection of these two sets. Also compute the number of common reviewers `n_common`.\n", 
            "\n", 
            "2. Use the function `get_restaurant_reviews` defined below to get the reviews for each restaurant as made by these common reviewers. Notice that `get_restaurant_reviews` returns a sub data frame of reviews.\n", 
            "\n", 
            "3. Calculate the similarity using `similarity_func` which takes the two reviews dataframes from part 2 and the number of common reviewers `n_common` as arguments\n", 
            "\n", 
            "4. Return the similarity and `n_common` in a tuple `(sim, n_common)`. If the similarity is a `NaN`, set the similarity to 0.\n"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 14, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "calculate_similarity\n", 
            "\n", 
            "Parameters\n", 
            "----------\n", 
            "rest1 : string\n", 
            "    The id of restaurant 1\n", 
            "rest2 : string\n", 
            "    The id of restaurant 2\n", 
            "df : DataFrame\n", 
            "  A dataframe of reviews, such as the smalldf above\n", 
            "similarity_func : func\n", 
            "  A function like pearson_sim above which takes two dataframes of individual\n", 
            "  restaurant reviews made by a common set of reviewers, and the number of\n", 
            "  common reviews. This function returns the similarity of the two restaurants\n", 
            "  based on the common reviews.\n", 
            "  \n", 
            "Returns\n", 
            "--------\n", 
            "A tuple\n", 
            "  The first element of the tuple is the similarity and the second the\n", 
            "  common support n_common. If the similarity is a NaN, set it to 0\n", 
            "\"\"\"\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "### Making a database of similarities\n", 
            "\n", 
            "We now move to calculating a global database of pairwise restaurant similarities.\n", 
            "We provide you here with a function to make a database of the similarities for each pair of restaurants in the database. The class `Database` is initialized in its constructor by taking as arguments a dataframe of reviews. The method `populate_by calculating` iterates over every possible pair of business_id's in the dataframe and populates the database with similarities and common supports. It takes as arguments a function the similarity function `similarity_func` like `pearson_sim` (`calculate_similarity` then uses this to calculate the similarity). The `get` method on the database can be used to retrieve the similarity for two business ids."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "(See Thu Oct 17th's class video for information about classes)"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 15, 
          "input": [
            "class Database:\n", 
            "    \"A class representing a database of similaries and common supports\"\n", 
            "    \n", 
            "    def __init__(self, df):\n", 
            "        \"the constructor, takes a reviews dataframe like smalldf as its argument\"\n", 
            "        database={}\n", 
            "        self.df=df\n", 
            "        self.uniquebizids={v:k for (k,v) in enumerate(df.business_id.unique())}\n", 
            "        keys=self.uniquebizids.keys()\n", 
            "        l_keys=len(keys)\n", 
            "        self.database_sim=np.zeros([l_keys,l_keys])\n", 
            "        self.database_sup=np.zeros([l_keys, l_keys], dtype=np.int)\n", 
            "        \n", 
            "    def populate_by_calculating(self, similarity_func):\n", 
            "        \"\"\"\n", 
            "        a populator for every pair of businesses in df. takes similarity_func like\n", 
            "        pearson_sim as argument\n", 
            "        \"\"\"\n", 
            "        items=self.uniquebizids.items()\n", 
            "        for b1, i1 in items:\n", 
            "            for b2, i2 in items:\n", 
            "                if i1 < i2:\n", 
            "                    sim, nsup=calculate_similarity(b1, b2, self.df, similarity_func)\n", 
            "                    self.database_sim[i1][i2]=sim\n", 
            "                    self.database_sim[i2][i1]=sim\n", 
            "                    self.database_sup[i1][i2]=nsup\n", 
            "                    self.database_sup[i2][i1]=nsup\n", 
            "                elif i1==i2:\n", 
            "                    nsup=self.df[self.df.business_id==b1].user_id.count()\n", 
            "                    self.database_sim[i1][i1]=1.\n", 
            "                    self.database_sup[i1][i1]=nsup\n", 
            "                    \n", 
            "\n", 
            "    def get(self, b1, b2):\n", 
            "        \"returns a tuple of similarity,common_support given two business ids\"\n", 
            "        sim=self.database_sim[self.uniquebizids[b1]][self.uniquebizids[b2]]\n", 
            "        nsup=self.database_sup[self.uniquebizids[b1]][self.uniquebizids[b2]]\n", 
            "        return (sim, nsup)"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Lets run `make_database` and store the result in the global variable `db`. Lets print out an example entry. Running this function will take a bit of time."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 16, 
          "input": [
            "db=Database(smalldf)\n", 
            "db.populate_by_calculating(pearson_sim)"
          ], 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 17, 
          "input": [
            "db.get(\"z3yFuLVrmH-3RJruPEMYKw\", \"zruUQvFySeXyEd7_rQixBg\")"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "### K-Nearest restaurants (in similarity)"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "We are now going to find the k-nearest restaurants to a given restaurant based on the database of similarities that we calculated. But we have a problem.\n", 
            "\n", 
            "Consider the two cases where there is just one common reviewer, and where there are 40. In the former case, we might get a artificially high similarity based on the tastes of just this user, and thus we must reduce its importance in the nearest-neighbor calculation. In the latter case, we would get a much more unbiased estimator of the similarity of the two restaurants.\n", 
            "\n", 
            "To control the effect of small common supports, we can **shrink** our pearson co-efficients. We shall do this by using the \"regularization\" parameter `reg`:\n", 
            "\n", 
            "$$s_{mj} = \\frac{N_{common}\\, \\rho_{mj}}{N_{common}+reg} $$\n", 
            "\n", 
            "where $N_{common}$ (`n_common`) is the common reviewer support and $\\rho_{ij}$ is the pearson co-relation coefficient.\n", 
            "\n", 
            "Recall the notions of regularization introduced in class. We want to reduce the variance in our estimates, so we pull our estimates in toward a conservative point in a way that strongly corrals in estimates when there is very little data, but allows the data to speak when there is a lot. This can be shown as equivalent to adding in a `reg` amount of bayesian prior, as Joe has alluded to in class. \n", 
            "\n", 
            "A good value of the regularizer is intuitively one that doesn't affect the similarity when the common support is high ~10, but has a large effect when the support is small. In this case, values of 2-4 are good. Usually, the value of `reg` is determined using cross-validation, but for the sake of simplicity we will generally set it to 3.\n", 
            "\n", 
            "We define a function `shrunk_sim` which takes the `sim` and `n_common` obtained from the database, and shrinks the similarity down using the regularizer `reg`."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 18, 
          "input": [
            "def shrunk_sim(sim, n_common, reg=3.):\n", 
            "    \"takes a similarity and shrinks it down by using the regularizer\"\n", 
            "    ssim=(n_common*sim)/(n_common+reg)\n", 
            "    return ssim"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "**1.6** Now we can move to writing a `knearest` function, which finds the `k` nearest neighbors of a given restaurant based on the shrunk similarities we calculate. Note that as defined here, the nearest neighbors are global over the entire set of restaurants, as opposed to being restricted to the restaurants a user has reviewed(we shall do that in the next problem). Thus, this is an expensive function!\n", 
            "\n", 
            "Write a `knearest` that returns a *k-length sorted list* of 3-tuples each corresponding to a restaurant. The tuple structure is `(business_id, shrunken similarity score, common support)` where the similarity score and common support are with respect to the restaurant whose neighbors we are finding, and the `business_id` is the id of the \"nearby\" restaurant found. The nearby restaurants are found from a supplied numpy array of restaurants `set_of_restaurants`. The spec for the function is given below. HINT: use `itemgetter` from the `operator` module to do the sorting."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 19, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "knearest\n", 
            "\n", 
            "Parameters\n", 
            "----------\n", 
            "restaurant_id : string\n", 
            "    The id of the restaurant whose nearest neighbors we want\n", 
            "set_of_restaurants : array\n", 
            "    The set of restaurants from which we want to find the nearest neighbors\n", 
            "dbase : instance of Database class.\n", 
            "    A database of similarities, on which the get method can be used to get the similarity\n", 
            "  of two businessed. e.g. dbase.get(rid1,rid2)\n", 
            "k : int\n", 
            "    the number of nearest neighbors desired, default 7\n", 
            "reg: float\n", 
            "    the regularization.\n", 
            "    \n", 
            "  \n", 
            "Returns\n", 
            "--------\n", 
            "A sorted list\n", 
            "    of the top k similar restaurants. The list is a list of tuples\n", 
            "    (business_id, shrunken similarity, common support).\n", 
            "\"\"\"\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "### Ok it's time to recommend!\n", 
            "\n", 
            "Lets choose the two very different businesses in the dataframe"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 20, 
          "input": [
            "testbizid=\"eIxSLxzIlfExI6vgAbn2JA\"\n", 
            "testbizid2=\"L-uPZxooP_ziXCtRrWi8Pw\""
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "We provide functions to look up a business name given a business id, and a username given a user id."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 21, 
          "input": [
            "def biznamefromid(df, theid):\n", 
            "    return df['biz_name'][df['business_id']==theid].values[0]\n", 
            "def usernamefromid(df, theid):\n", 
            "    return df['user_name'][df['user_id']==theid].values[0]"
          ], 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 22, 
          "input": [
            "print testbizid, biznamefromid(smalldf,testbizid)\n", 
            "print testbizid2, biznamefromid(smalldf, testbizid2)"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "####Get top matches\n", 
            "\n", 
            "Its now time to answer the question: \"if you liked this, you might also like these\". We use our `testbizid` and `testbizid2` to compute the `k=7` nearest neighbors with a regularization of `3.` . We print these top 7 matches names, along with their similarity coefficient and common support."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 23, 
          "input": [
            "tops=knearest(testbizid, smalldf.business_id.unique(), db, k=7, reg=3.)\n", 
            "print \"For \",biznamefromid(smalldf, testbizid), \", top matches are:\"\n", 
            "for i, (biz_id, sim, nc) in enumerate(tops):\n", 
            "    print i,biznamefromid(smalldf,biz_id), \"| Sim\", sim, \"| Support\",nc"
          ], 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 24, 
          "input": [
            "tops2=knearest(testbizid2, smalldf.business_id.unique(), db, k=7, reg=3.)\n", 
            "print \"For \",biznamefromid(smalldf, testbizid2), \", top matches are:\"\n", 
            "for i, (biz_id, sim, nc) in enumerate(tops2):\n", 
            "    print i,biznamefromid(smalldf,biz_id), \"| Sim\", sim, \"| Support\",nc"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "We can see that these two restaurants are in somewhat different orbits :-)."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "Lets now turn our attention to another question: what are the top recommendations for a user? To answer this we must find the user's top rated restaurants, find the nearest neighbors of these restaurants, merge these lists while removing the duplicates and the ones that the user has already rated, and sort by the restaurant's average rating. We provide the code to get the user's top choices in a subset data frame."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 25, 
          "input": [
            "def get_user_top_choices(user_id, df, numchoices=5):\n", 
            "    \"get the sorted top 5 restaurants for a user by the star rating the user gave them\"\n", 
            "    udf=df[df.user_id==user_id][['business_id','stars']].sort(['stars'], ascending=False).head(numchoices)\n", 
            "    return udf\n", 
            "testuserid=\"7cR92zkDv4W3kqzii6axvg\"\n", 
            "print \"For user\", usernamefromid(smalldf,testuserid), \"top choices are:\" \n", 
            "bizs=get_user_top_choices(testuserid, smalldf)['business_id'].values\n", 
            "[biznamefromid(smalldf, biz_id) for biz_id in bizs]"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "#### Get top recommendations for user."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**1.7** Its your job now to write a function `get_top_recos_for_user` which takes as arguments a `userid`, the `n` top choices for the user, the dataframe, `k`, and a regularizer, and returns the top recommendations obtained from combining the restaurants that are neighbors of each of the `n` choices, in the way described in the previous paragraph. This returned list is a list of tuples `(restaurant_id, business_avg)` sorted by `business_avg` where `business_avg` is the average rating of the restaurant over the dataframe."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 26, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "get_top_recos_for_user\n", 
            "\n", 
            "Parameters\n", 
            "----------\n", 
            "userid : string\n", 
            "    The id of the user for whom we want the top recommendations\n", 
            "df : Dataframe\n", 
            "    The dataframe of restaurant reviews such as smalldf\n", 
            "dbase : instance of Database class.\n", 
            "    A database of similarities, on which the get method can be used to get the similarity\n", 
            "  of two businesses. e.g. dbase.get(rid1,rid2)\n", 
            "n: int\n", 
            "    the n top choices of the user by star rating\n", 
            "k : int\n", 
            "    the number of nearest neighbors desired, default 8\n", 
            "reg: float\n", 
            "    the regularization.\n", 
            "    \n", 
            "  \n", 
            "Returns\n", 
            "--------\n", 
            "A sorted list\n", 
            "    of the top recommendations. The list is a list of tuples\n", 
            "    (business_id, business_avg). You are combining the k-nearest recommendations \n", 
            "    for each of the user's n top choices, removing duplicates and the ones the user\n", 
            "    has already rated.\n", 
            "\"\"\"\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Lets print the top recommendations for `testuserid`, with a regularization of 3."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 27, 
          "input": [
            "print \"For user\", usernamefromid(smalldf,testuserid), \"the top recommendations are:\"\n", 
            "toprecos=get_top_recos_for_user(testuserid, smalldf, db, n=5, k=7, reg=3.)\n", 
            "for biz_id, biz_avg in toprecos:\n", 
            "    print biznamefromid(smalldf,biz_id), \"| Average Rating |\", biz_avg"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "## Problem 2: A user based recommender with predicted ratings"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "This is all very nice. We can provide ratings based on global similarities to a restaurant. However, in many cases this is not enough.\n", 
            "\n", 
            "For example, it is hard to judge if the above recommendations are any good. In the usual testing paradigm, say that we break the dataframe into train and test. Based on the training set, I am recommended restaurant B. Now, I have rated B, but that information is in the testing set. I have no way of comparing the rating I give B in the testing set, to the similarity computed from the training set that was used to make the recomendation. The best I could do is to compare the average rating of restaurant B in the training set to my rating of restaurant B in the test set. \n", 
            "\n", 
            "In this section, we shift our focus to more fine-grained predictions about each user, and try to predict what _rating_ a user would give to a restaurant they have never tried before. To do this, we will try to personalize the information we use even further, and only pool information from restaurants that the user has rated.\n", 
            "\n", 
            "This allows us to return to the original problem of prediction $Y_{um}$ for a restaurant $m$ that user $u$ has never rated before. Using our newly computed similarity metrics, we can modify our original baseline estimate by pulling in information from the user's neighborhood of the restaurant $m$, and predict $Y_{um}$ as:\n", 
            "\n", 
            "$$ \\hat{Y_{um}} = \\hat Y^{baseline}_{um}\\, + \\,\\frac{\\sum\\limits_{j \\in S^{k}(m;u)} s_{mj} ( Y_{uj} - \\hat Y^{baseline}_{uj} )}{\\sum\\limits_{j \\in S^{k}(m;u)} s_{mj} } $$\n", 
            "\n", 
            "where $s^{k}(m;u)$ is the $k$ neighbor items of item $m$ which have been rated by user $u$.\n", 
            "\n", 
            "Now, this is not a particularly good assumption, especially in the situation where a restaurant is new (new item problem) or a user is new (cold start problem), or in the case when there are very few reviewers of a restaurant, or very few reviews by a user respectively. However, one must start somewhere!\n", 
            "\n", 
            "Notice that in adding in the similarity term, we subtract the baseline estimate from the observed rating of the user's neighbor items."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###Defining the predicted rating"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**2.1** Write a function `knearest_amongst_userrated`, analogous to the `knearest` function we defined above, to find the nearest `k` neighbors to a given restaurant from the **restaurants that the user has already rated**. This function will take as arguments the `restaurant_id`, the `user_id`, the dataframe of reviews, the database, the `k`, and the regularizer `reg`. Just like before, return a *k-length sorted list* of 3-tuples each corresponding to a restaurant.  HINT: use the `knearest` function you defined earlier"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 28, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "knearest_amongst_userrated\n", 
            "\n", 
            "Parameters\n", 
            "----------\n", 
            "restaurant_id : string\n", 
            "    The id of the restaurant whose nearest neighbors we want\n", 
            "user_id : string\n", 
            "    The id of the user, in whose reviewed restaurants we want to find the neighbors\n", 
            "df: Dataframe\n", 
            "    The dataframe of reviews such as smalldf\n", 
            "dbase : instance of Database class.\n", 
            "    A database of similarities, on which the get method can be used to get the similarity\n", 
            "  of two businessed. e.g. dbase.get(rid1,rid2)\n", 
            "k : int\n", 
            "    the number of nearest neighbors desired, default 7\n", 
            "reg: float\n", 
            "    the regularization.\n", 
            "    \n", 
            "  \n", 
            "Returns\n", 
            "--------\n", 
            "A sorted list\n", 
            "    of the top k similar restaurants. The list is a list of tuples\n", 
            "    (business_id, shrunken similarity, common support).\n", 
            "\"\"\"\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "**2.2** Now write a function that returns the predicted rating for a user and an item using the formula at the beginning of this problem. Include code to deal with the possibility that the sum of scores that goes in the denominator is 0: return a predicted rating of the baseline portion of the formula in that case. This function `rating` takes as arguments the dataframe, the database, the wanted `restaurant_id` and `user_id`, and `k` as well as the regularizer."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 29, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "rating\n", 
            "\n", 
            "Parameters\n", 
            "----------\n", 
            "df: Dataframe\n", 
            "    The dataframe of reviews such as smalldf\n", 
            "dbase : instance of Database class.\n", 
            "    A database of similarities, on which the get method can be used to get the similarity\n", 
            "  of two businessed. e.g. dbase.get(rid1,rid2)\n", 
            "restaurant_id : string\n", 
            "    The id of the restaurant whose nearest neighbors we want\n", 
            "user_id : string\n", 
            "    The id of the user, in whose reviewed restaurants we want to find the neighbors\n", 
            "k : int\n", 
            "    the number of nearest neighbors desired, default 7\n", 
            "reg: float\n", 
            "    the regularization.\n", 
            "    \n", 
            "  \n", 
            "Returns\n", 
            "--------\n", 
            "A float\n", 
            "    which is the impued rating that we predict that user_id will make for restaurant_id\n", 
            "\"\"\"\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "For the top-recommendations in the variable `toprecos` from the previous section, we compute the predicted rating and compare it with the average rating over all users available inside the tuples that make up `toprecos`. We use a `k` of 7 and regularization 3. For comparision we also print this users' average rating. Do you notice anything interesting about how the order has changed from when we did this with the global similarities? (for you to think, not to answer)"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 30, 
          "input": [
            "print \"User Average\", smalldf[smalldf.user_id==testuserid].stars.mean(),\"for\",usernamefromid(smalldf,testuserid)\n", 
            "print \"Predicted ratings for top choices calculated earlier:\"\n", 
            "for biz_id,biz_avg in toprecos:\n", 
            "    print biznamefromid(smalldf, biz_id),\"|\",rating(smalldf, db, biz_id, testuserid, k=7, reg=3.),\"|\",\"Average\",biz_avg "
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "###Testing the ratings\n", 
            "\n", 
            "Let us compare the predicted ratings with a user's ratings. Note that we are doing this on the same set that we constructed the predictions with, so this is not a validation of the procedure, but simply a check of the procedure's fit. We first write a helper function to return the user score for a restaurant, and the restaurant's average score over all users."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 31, 
          "input": [
            "def get_other_ratings(restaurant_id, user_id, df):\n", 
            "    \"get a user's rating for a restaurant and the restaurant's average rating\"\n", 
            "    choice=df[(df.business_id==restaurant_id) & (df.user_id==user_id)]\n", 
            "    users_score=choice.stars.values[0]\n", 
            "    average_score=choice.business_avg.values[0]\n", 
            "    return users_score, average_score"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "For the user `testuserid`, we loop over the variable `bizs` (which is a set of restaurants the user has rated) and print the predicted rating, and the actual rating and restaurant average rating obtained using the function above. We again use `k=7` and a regularization of 3."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 32, 
          "input": [
            "print \"for user\",usernamefromid(smalldf,testuserid), 'avg', smalldf[smalldf.user_id==testuserid].stars.mean() \n", 
            "for biz_id in bizs:\n", 
            "    print \"----------------------------------\"\n", 
            "    print biznamefromid(smalldf, biz_id)\n", 
            "    print \"Predicted Rating:\",rating(smalldf, db, biz_id, testuserid, k=7, reg=3.) \n", 
            "    u,a=get_other_ratings(biz_id, testuserid, smalldf)\n", 
            "    print \"Actual User Rating:\",u,\"Avg Rating\",a"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "**2.3** Explain in words why the predicted ratings are lower than the actual ratings. How do the user average rating and restaurant average rating affect this? How does sparsity affect the predicted ratings?"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "*your answer here*"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###Error Analysis\n", 
            "\n", 
            "This next function takes a set of actual ratings, and a set of predicted ratings, and plots the latter against the former. We can use a graph of this kind to see how well or badly we do in our predictions. Since the nearest neighbor models can have alternating positive and negative similarities (the sum of similarity weights in the denominator can get large), the ratings can get very large. Thus we restrict ourselves to be between -10 and 15 in our ratings and calculate the fraction within these bounds. We also plot the line with unit slope, line segments joining the means, and a filled in area representing one standard deviation from the mean.\n", 
            "\n", 
            "The first argument to `compare_results` is a numpy array of the actual star ratings obtained from the dataframe, while the second argument is the numpy array of the predicted ones. (*Feel free to improve this function for your display*)"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 33, 
          "input": [
            "def compare_results(stars_actual, stars_predicted, ylow=-10, yhigh=15, title=\"\"):\n", 
            "    \"\"\"\n", 
            "    plot predicted results against actual results. Takes 2 arguments: a\n", 
            "    numpy array of actual ratings and a numpy array of predicted ratings\n", 
            "    scatterplots the predictions, a unit slope line, line segments joining the mean,\n", 
            "    and a filled in area of the standard deviations.\"\n", 
            "    \"\"\"\n", 
            "    fig=plt.figure()\n", 
            "    df=pd.DataFrame(dict(actual=stars_actual, predicted=stars_predicted))\n", 
            "    ax=plt.scatter(df.actual, df.predicted, alpha=0.2, s=30, label=\"predicted\")\n", 
            "    plt.ylim([ylow,yhigh])\n", 
            "    plt.plot([1,5],[1,5], label=\"slope 1\")\n", 
            "    xp=[1,2,3,4,5]\n", 
            "    yp=df.groupby('actual').predicted.mean().values\n", 
            "    plt.plot(xp,yp,'k', label=\"means\")\n", 
            "    sig=df.groupby('actual').predicted.std().values\n", 
            "    plt.fill_between(xp, yp - sig, yp + sig, \n", 
            "                 color='k', alpha=0.2)\n", 
            "    plt.xlabel(\"actual\")\n", 
            "    plt.ylabel(\"predicted\")\n", 
            "    plt.legend(frameon=False)\n", 
            "    remove_border()\n", 
            "    plt.grid(False)\n", 
            "    plt.title(title)\n", 
            "    print np.mean(np.abs(df.predicted) < 15)\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "**2.4** For each review in the data set, obtain a prediction from the entire dataframe `smalldf`. Use the function `compare_results` above to plot the predicted ratings against the observed ones. Make 4 such graphs, at k=3 and k=10, and for reg=3. and reg=15.\n", 
            "\n", 
            "Note that this analysis is not strictly a model check because we are testing on the training set. However, since the user averages would change each time a cross-validation split was done on the set, we would incur the prohibitive expense of redoing the database each time. This would be better done on a cluster, using map-reduce or other techniques. While we explore map-reduce later in this homework, we shall not do any cross-validation.\n", 
            "\n", 
            "Explain the results you get in the graphs in words."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 34, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 35, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "*your answer here*"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**2.5** Outline a process, in words, for choosing the nearest neighbor parameter `k`. For this question fix the regularization parameter `reg` at `3`."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "*your answer here*"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "##Q3 Bayesian Chocolates: Model based recommendations"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "In this part of the homework, you will use your newly minted Bayesian and Gibbs sampler skills to write a recommender that uses Bayesian techniques to impute ratings."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###Model-Based Recommendations\n", 
            "\n", 
            "\n", 
            "####A Note on Frequentist and Bayesian Procedures\n", 
            "\n", 
            "In the previous section we implemented a **procedure** (a set of instructions for processing data) for giving recommendations and predicting user ratings for restaurants. This procedure involved a number of arbitrary choices -- for example, the particular measure of similarity between restaurants, or the weighting scheme for constructing a predicted rating. It also gave no sense of uncertainty -- in the case of giving recommendations, there was no statement about how we would expect the ranking from the procedure to compare to the user's true opinions of restaurants, and in the case of predicting ratings, there was no confidence interval for the prediction.\n", 
            "\n", 
            "It is possible in repeated applications of the above procedure to see how it performs in the long run. Based on this long-run performance we could potentially justify certain functional choices and compute measurements of uncertainty. This framework of proposing a procedure first, then evaluating its performance in real or hypothetical replications of the experiment is an example of a *frequentist* approach to a problem. One aspect of the frequentist approach is that the proposed procedure does not necessarily have to be derived from a model (although it often is). While this means that a proposed procedure may be more flexible or robust than a model-based procedure, it also means that there is no natural way to justify certain functional choices or construct uncertainty estimates.\n", 
            "\n", 
            "In contrast, the *Bayesian* approach to a problem always begins with a **probablistic model** for how the data were generated. Assuming this model is true, the posterior distribution over unknown quantities (either parameters to be estimated or unobserved data to be predicted) gives a single coherent expression of what the observed data tell us about the unknowns. By summarizing the posterior distribution, we can derive the exact functional form of a procedure for constructing estimates or predictions. We call a procedure derived from this Bayesian approach a **Bayes rule** (not to be confused with Bayes' Theorem). Using the posterior distribution, we can also give a sense of how uncertain we are about the estimate or prediction we have constructed.\n", 
            "\n", 
            "####Outline for this Problem\n", 
            "\n", 
            "In this section, we construct a **model** of how ratings are generated, and use this model to build a recommendation and ratings prediction system. We will take a Bayesian approach here, and construct our estimates and predictions from summaries of the *posterior distribution* of the model's parameters, which we will compute using a *Gibbs sampler*. We will also give measures of uncertainty based on the posterior distribution. We will evaluate predictions from this approach in the same way we evalutated predictions from the KNN procedure above."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###The Latent Factor Model###\n", 
            "\n", 
            "####Model Overview####\n", 
            "\n", 
            "The central dogma in constructing a recommendation system using collaborative filtering is that *similar users will rate similar restaurants similarly*. In the previous section, we explicitly encoded this idea by using a similarity function to identify similar restaurants. We also assumed that either all users were the same (the global approach) or that only the current user was similar enough to make a recommendation (the user-specific approach). In this section, we will use a model that allows us to identify both similar users and similar restaurants as a function of **latent factors**.\n", 
            "\n", 
            "We can think of latent factors as properties of restaurants (e.g., spiciness of food or price) that users have a positive or negative preference for. We do not observe these factors or the users' preferences directly, but we assume that they affect how users tend to rate restaurants. For example, if a restaurant serves a lot of spicy food and a user dislikes spicy food, then the restaurant would have a high \"spiciness\" factor, and the user would have a strongly negative preference, resulting in a prediction of a low rating. Note that if users have similar preferences, then according to the model, they will behave similarly, and likewise, if restaurants have similar latent factors, they will be rated similarly by similar users. Latent factors thus give us an intuitive way to specify a generative model the obeys the central dogma.\n", 
            "\n", 
            "One issue that comes up with latent factor models is determining how many latent factors to include. There may be a number of different unmeasured properties that affect ratings in different ways -- for example, in addition to the spiciness factor above, there may also be a price factor that affects how users rate a restaurant. We deal with the problem of choosing the number of latent factors to include in the same way we deal with choosing $K$ in a $K$-nearest neighbors problem.\n", 
            "\n", 
            "####Rating Model Specification####\n", 
            "\n", 
            "To make this model concrete, we can write down our probability model as a generative process. First, we define the following quantities:\n", 
            "\n", 
            "Counts:\n", 
            "\n", 
            "* $L$: The number of latent factors.\n", 
            "\n", 
            "* $U$: The number of users.\n", 
            "\n", 
            "* $M$: The number of items (restaurants).\n", 
            "\n", 
            "* $N$: The number of observed ratings.\n", 
            "\n", 
            "Data:\n", 
            "\n", 
            "* $Y_{um}$: The star rating given to restaurant $m$ by user $u$.\n", 
            "* $Y$: The full collection of observed star ratings.\n", 
            "\n", 
            "Item-specific quantities:\n", 
            "\n", 
            "* $\\gamma_m$: An item-specific parameter vector of length $L+1$. The first element of $\\gamma_m$, denoted $\\gamma_m[0]$ is the item-specific bias. The remaining $L$ elements of $\\gamma_m$, denoted $\\gamma_m[1:]$, are the latent factors associated with item $m$.\n", 
            "\n", 
            "* $\\Gamma$: An $M$ by $L+1$ matrix where the $m$th row is $\\gamma_m$.\n", 
            "\n", 
            "User-specific quantities:\n", 
            "\n", 
            "* $\\theta_u$: A user-specific parameter vector of length $L+1$. The first element of $\\theta_u$, denoted $\\theta_u[0]$ is the user-specific bias. The remaining $L$ elements of $\\theta_u$, denoted $\\theta_u[1:]$, are user $u$'s preferences for the latent factors.\n", 
            "\n", 
            "* $\\Theta$: A $U$ by $L+1$ matrix where the $u$th row is $\\theta_u$.\n", 
            "\n", 
            "Global quantities:\n", 
            "\n", 
            "* $\\mu$: The overall ratings mean.\n", 
            "\n", 
            "* $\\sigma$: The residual variance of ratings after the mean, bias terms, and latent factors have been taken into account.\n", 
            "\n", 
            "Using these quantities, we can specify our model for each rating $Y_{um}$ similarly to a linear regression:\n", 
            "\n", 
            "$$Y_{um} = \\mu + \\theta_{u}[0] + \\gamma_{m}[0] + \\theta_{u}[1:]^{\\top}\\gamma_{m}[1:] + \\epsilon_{um}$$\n", 
            "\n", 
            "where\n", 
            "\n", 
            "$$\\epsilon_{um} \\sim N(0, \\sigma).$$\n", 
            "\n", 
            "Note that while this looks like a linear regression, it is of a slightly different form because the latent factor term involves the product of two unknowns. This is like a linear regression where we forgot to measure some covariates.\n", 
            "\n", 
            "We also assume the following priors on the user-specific and item-specific parameters:\n", 
            "\n", 
            "$$\n", 
            "\\begin{align*}\n", 
            "\\gamma_m &\\sim MVN(\\mathbf 0, \\Lambda_\\gamma^{-1})\\\\\n", 
            "\\theta_u &\\sim MVN(\\mathbf 0, \\Lambda_\\theta^{-1}),\n", 
            "\\end{align*}\n", 
            "$$\n", 
            "\n", 
            "where $MVN$ means multivariate normal, $\\mathbf 0$ is vector of length $L+1$ filled with zeros, and $\\Lambda_\\theta^{-1}$ and $\\Lambda_\\gamma^{-1}$ are $L+1 \\times L+1$ covariance matrices. $\\mu$ and $\\sigma$ also have priors, but they are not relevant to your task so we won't write them here.\n", 
            "\n", 
            "#### Goal for this Model####\n", 
            "Using this model, we want to make inference about all of the quantities that, if we knew them, would allow us to sample $Y_{um}$ for any user and any item. These quantities are $\\mu$, $\\sigma$, and the elements of $\\Theta$ and $\\Gamma$."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**3.1**: Given the goal specified above, how many quantities (counting a vector of $L$ items as $L$ quantities) are we trying to make inference about? Express your answer in terms of the variables in the \"Counts\" section above."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "*your answer here*"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###Gibbs Sampling from the Posterior###\n", 
            "\n", 
            "Our goal is to compute the **posterior distribution** over the unknowns $\\mu$, $\\sigma$, $\\Gamma$, and $\\Theta$ given $Y$, which reflects how much we know about these quantities given the data we have observed. We write this distribution as $P(\\mu, \\sigma, \\Gamma, \\Theta \\mid Y)$.\n", 
            "\n", 
            "The most general way to learn about the posterior distribution is to sample from it. This can be challenging, particularly in problems that are very high dimensional (see your answer to the question above). One strategy for for sampling from high-dimensional distributions is **Gibbs sampling**, which we discussed in class and lab.\n", 
            "\n", 
            "Gibbs sampling breaks down the posterior probability distribution into blocks of unknowns, and samples iteratively from each block assuming that the values of the other blocks (and the data) are known and fixed. In this case, we will break down the posterior distribution into blocks of $\\mu$, $\\sigma$, each vector $\\gamma_m$, and each vector $\\theta_u$. We have already implemented the draws for $\\mu$ and $\\sigma$. You will need to implement the draws for each $\\gamma_m$ and each $\\theta_u$. Luckily, the structures of these draws are similar, so you will only need to implement two functions.\n", 
            "\n", 
            "First, we'll derive the form of the draws below. Note that you don't need to be able to follow these derivations fully -- you'll just need to be able to use the result at the end.\n", 
            "\n", 
            "####Distribution of $\\gamma_{m'}$ given $Y, \\mu, \\sigma, \\Gamma_{-m'}, \\Theta$####\n", 
            "\n", 
            "Intuitively, this is the distribution of the item-specific parameters for item $m'$, imagining that all of the other unknowns are fixed.\n", 
            "\n", 
            "More precisely, we want to draw from the distribution of $\\gamma_{m'}$ conditional on the data $Y$ and all other unknowns -- that is, $\\mu$, $\\sigma$, all of $\\Theta$, and all of $\\Gamma$ except for $\\gamma_{m'}$, which we denote $\\Gamma_{-m}$.\n", 
            "\n", 
            "Note that in the model specification above, the only places that $\\gamma_{m'}$ appears are in the regression equations for each $Y_{um}$ that involves item $m'$. If we write out just these equations, we get a system of the following form,\n", 
            "\n", 
            "$$Y_{um'} = \\mu + \\theta_{u}[0] + \\gamma_{m'}[0] + \\theta_{u}[1:]^{\\top}\\gamma_{m'}[1:] + \\epsilon_{um'},$$\n", 
            "\n", 
            "with one equation for each $u$ that rated item $m'$. Now, because \n", 
            "\n", 
            "If we move all of the fully known terms to the left-hand side, we obtain the system:\n", 
            "\n", 
            "$$Y_{um'} - \\mu - \\theta_{u}[0] = \\gamma_{m'}[0] + \\theta_{u}[1:]^{\\top}\\gamma_{m'}[1:] + \\epsilon_{um'}.$$\n", 
            "\n", 
            "Notice that, because we assume that $\\theta_{u}$ is known, this equation now fits cleanly into the form of a linear regression, where $\\gamma_{m'}$ is the vector of unknown coefficients. This means that the posterior distribution for $\\gamma_{m'}$ conditional on everything else is the same as the posterior for the coefficients of a Bayesian linear regression of $(Y_{um'} - \\mu - \\theta_{u}[0])$ on $\\theta_{u}[1:]$ and an intercept.\n", 
            "\n", 
            "Let's denote the set of users who rated item $m'$ as $(u_1, \\cdots, u_g)$. Then, we can define the following vector and matrix:\n", 
            "\n", 
            "\\begin{align*}\n", 
            "Y_{m'} = \\left(\\begin{array}{c} Y_{u_1m'}-\\mu-\\theta_{u_1}[0]\\\\ \\vdots \\\\ Y_{u_gm'}-\\mu-\\theta_{u_g}[0]\\end{array}\\right), \\qquad\n", 
            "X_{m'} &= \\left(\\begin{array}{cc} 1 & \\theta_{u_1}[1:]^\\top \\\\ \\vdots & \\vdots \\\\ 1 & \\theta_{u_g}[1:]^\\top\\end{array}\\right),\n", 
            "\\end{align*}\n", 
            "\n", 
            "where $Y_{m'}$ is a vector of length $g$ and $X_{m'}$ is a $g \\times L+1$ matrix.\n", 
            "\n", 
            "The draw from $\\gamma_{m'}$ given everything else then has the form:\n", 
            "$$ \\gamma_{m'} \\mid Y, \\mu, \\sigma, \\Gamma_{-m'}, \\Theta \\sim MVN\\left(Q_{m'}^{-1} \\frac{1}{\\sigma^2}X_{m'}^\\top Y_{m'}, Q_{m'}^{-1}\\right)$$\n", 
            "where\n", 
            "$$ Q_{m'} = \\left(\\frac{1}{\\sigma^2}X_{m'}^\\top X_{m'} + \\Lambda_\\gamma\\right).$$\n", 
            "\n", 
            "#### Distribution of $\\theta_{u'}$ given $Y, \\mu, \\sigma, \\Gamma, \\Theta_{-u'}$####\n", 
            "\n", 
            "Intuitively, this is the distribution of the user-specific parameters for user $u'$, imagining that all of the other unknowns are fixed.\n", 
            "\n", 
            "We can use a very similar argument to the one above. We can denote the set of items rated by user $u'$ as $(m_1, \\cdots, m_g)$ and define the vector and matrix:\n", 
            "\\begin{align*}\n", 
            "Y_{u'} = \\left(\\begin{array}{c} Y_{u'm_1}-\\mu-\\gamma_{m_1}[0] \\\\ \\vdots \\\\ Y_{u'm_g}-\\mu-\\gamma_{m_g}[0]\\end{array}\\right), \\qquad\n", 
            "X_{u'} &= \\left(\\begin{array}{cc} 1 & \\gamma_{m_1}[1:]^\\top \\\\ \\vdots & \\vdots \\\\ 1 & \\gamma_{m_g}[1:]^\\top\\end{array}\\right),\n", 
            "\\end{align*}\n", 
            "\n", 
            "where $Y_{u'}$ is a vector of length $g$ and $X_{u'}$ is a $g \\times L+1$ matrix.\n", 
            "\n", 
            "the draw from $\\theta_{u'}$ given everything else has the form:\n", 
            "$$ \\theta_{u'} \\mid Y, \\mu, \\sigma, \\Gamma, \\Theta_{-u'} \\sim MVN\\left(Q_{u'}^{-1} \\frac{1}{\\sigma^2}X_{u'}^\\top Y_{u'}, Q_{u'}^{-1}\\right)$$\n", 
            "where\n", 
            "$$ Q_{u'}= \\left(\\frac{1}{\\sigma^2}X_{u'}^\\top X_{u'} + \\Lambda_\\theta\\right).$$"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**3.2** We will only ask you to implement a tiny portion of the Gibbs sampler. Complete the following functions that implement the conditional posterior draws for $\\gamma_m$ and $\\theta_u$ derived above.\n", 
            "\n", 
            "**Hint**: `np.random.multivariate_normal` is a good function to know."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 36, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "gamma_m_draw\n", 
            "\n", 
            "Draw a single sample from the conditional posterior distribution\n", 
            "of gamma_m.\n", 
            "\n", 
            "Inputs\n", 
            "-------\n", 
            "X_m: A g-by-L+1 matrix, defined above. \n", 
            "Y_m: A 1D vector of length g, defined above.\n", 
            "sig2: Residual _variance_, as defined above.\n", 
            "Lambda_gamma: Prior precision matrix.\n", 
            "\n", 
            "Outputs\n", 
            "--------\n", 
            "Single draw from conditional posterior, defined above.\n", 
            "\"\"\"\n", 
            "#Item-specific parameters given all else\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 37, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "theta_u_draw\n", 
            "\n", 
            "Draw a single sample from the conditional posterior distribution\n", 
            "of gamma_m.\n", 
            "\n", 
            "Inputs\n", 
            "-------\n", 
            "X_u: A g-by-L+1 matrix, defined above. \n", 
            "Y_u: A 1D vector of length g, defined above.\n", 
            "sig2: Residual _variance_, as defined above.\n", 
            "Lambda_theta: Prior precision matrix.\n", 
            "\n", 
            "Outputs\n", 
            "--------\n", 
            "Single draw from conditional posterior, defined above.\n", 
            "\"\"\"\n", 
            "#User-specific parameters given all else\n", 
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Here is the Gibbs sampler skeleton that your functions fit into. Look over the structure to see how for each draw from the posterior, the sampler iterates through $\\mu$, $\\sigma$, $\\gamma_m$ for each item, and $\\theta_u$ for each user."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 38, 
          "input": [
            "\"\"\"\n", 
            "Function\n", 
            "--------\n", 
            "factor_gibbs\n", 
            "\n", 
            "Runs a gibbs sampler to infer mean, variance, user-specific, and item-specific\n", 
            "parameters.\n", 
            "\n", 
            "Inputs\n", 
            "-------\n", 
            "data: A dataframe containing ratings data.\n", 
            "L: Dimension of latent factors.\n", 
            "maxit: Number of samples to draw from posterior.\n", 
            "Lambda_theta_diag: Hyperparameter controlling regularization of Theta.\n", 
            "Lambda_gamma_diag: Hyperparameter controlling regularization of Gamma.\n", 
            "progress: if true, print iteration number every 100 iterations.\n", 
            "\n", 
            "Outputs\n", 
            "--------\n", 
            "Dictionary with elements\n", 
            "mu: Draws of mu. 1D array of length maxiter.\n", 
            "sig2: Draws of sig2, residual _variance_. 1D array of length maxiter.\n", 
            "theta: Draws of Theta. U-by-L-by-maxiter array.\n", 
            "gamma: Draws of Gamma. M-by-L-by-maxiter array.\n", 
            "EY: Draws of fitted values of Y. N-by-maxiter array.\n", 
            "\"\"\"\n", 
            "def factor_gibbs(data, L, maxit, Lambda_theta_diag, Lambda_gamma_diag, progress=True):\n", 
            "    data = data.copy()\n", 
            "    N = data.shape[0]\n", 
            "\n", 
            "    #Create indices that allow us to map users and restaurants to rows\n", 
            "    #in parameter vectors.\n", 
            "    uusers, uidx = np.unique(data.user_id, return_inverse=True)\n", 
            "    uitems, midx = np.unique(data.business_id, return_inverse=True)\n", 
            "\n", 
            "    nusers = uusers.size\n", 
            "    nitems = uitems.size\n", 
            "\n", 
            "    #Add numerical indices to dataframe.\n", 
            "    data[\"uidx\"] = uidx\n", 
            "    data[\"midx\"] = midx\n", 
            "\n", 
            "    #Group observations by user and by business.\n", 
            "    ugroups = data.groupby(\"uidx\")\n", 
            "    mgroups = data.groupby(\"midx\")\n", 
            "\n", 
            "    all_avg = data.stars.mean()\n", 
            "    u_avg = ugroups.stars.mean()\n", 
            "    m_avg = mgroups.stars.mean()\n", 
            "\n", 
            "    #Initialize parameters and set up data structures for\n", 
            "    #holding draws.\n", 
            "    #Overall mean\n", 
            "    mu = all_avg\n", 
            "    mu_draws = np.zeros(maxit)\n", 
            "    #Residual variance\n", 
            "    sig2 = 0.5\n", 
            "    sig2_draws = np.zeros(maxit)\n", 
            "\n", 
            "    #Matrix of user-specific bias and L latent factors.\n", 
            "    theta = np.zeros([nusers, L+1])\n", 
            "    theta[:,0] = u_avg-all_avg\n", 
            "    theta_draws = np.zeros([nusers, L+1, maxit])\n", 
            "\n", 
            "    #Matrix of item-specific bias and L latent factors.\n", 
            "    gamma = np.zeros([nitems, L+1])\n", 
            "    gamma[:,0] = m_avg-all_avg\n", 
            "    gamma_draws = np.zeros([nitems, L+1, maxit])\n", 
            "\n", 
            "    #Matrix for holding the expected number of stars\n", 
            "    #for each observation at each draw from the posterior.\n", 
            "    EY_draws = np.zeros([data.shape[0], maxit])\n", 
            "\n", 
            "    #Inverse covariance matrices from the prior on each theta_u\n", 
            "    #and gamma_b. These are diagonal, like Ridge regression.\n", 
            "    Lambda_theta = np.eye(L+1)*Lambda_theta_diag\n", 
            "    Lambda_gamma = np.eye(L+1)*Lambda_gamma_diag\n", 
            "\n", 
            "    #Main sampler code\n", 
            "    for i in range(maxit):\n", 
            "        if i%100==0 and progress:\n", 
            "            print i\n", 
            "\n", 
            "        #The entire regression equation except for the overall mean.\n", 
            "        nomu = np.sum(theta[data.uidx,1:]*gamma[data.midx,1:], axis=1) +\\\n", 
            "                  theta[data.uidx,0] + gamma[data.midx,0]\n", 
            "\n", 
            "        #Compute the expectation of each observation given the current\n", 
            "        #parameter values.\n", 
            "        EY_draws[:,i]=mu+nomu\n", 
            "\n", 
            "        #Draw overall mean from a normal distribution\n", 
            "        mu = np.random.normal(np.mean(data.stars-nomu), np.sqrt(sig2/N))\n", 
            "        #Draw overall residual variance from a scaled inverse-Chi squared distribution.\n", 
            "        sig2 = np.sum(np.power(data.stars-nomu-mu,2))/np.random.chisquare(N-2)\n", 
            "        \n", 
            "        #For each item\n", 
            "        for mi,itemdf in mgroups:\n", 
            "            #Gather relevant observations, and subtract out overall mean and\n", 
            "            #user-specific biases, which we are holding fixed.\n", 
            "            Y_m = itemdf.stars-mu-theta[itemdf.uidx,0]\n", 
            "            #Build the regression design matrix implied by holding user factors\n", 
            "            #fixed.\n", 
            "            X_m = np.hstack((np.ones([itemdf.shape[0],1]),\n", 
            "                             theta[itemdf.uidx,1:]))\n", 
            "            gamma[mi,:] = gamma_m_draw(X_m, Y_m, sig2, Lambda_gamma)\n", 
            "            \n", 
            "        #For each user\n", 
            "        for ui,userdf in ugroups:\n", 
            "            #Gather relevant observations, and subtract out overall mean and\n", 
            "            #business-specific biases, which we are holding fixed.\n", 
            "            Y_u = userdf.stars-mu-gamma[userdf.midx,0]\n", 
            "            #Build the regression design matrix implied by holding business factors\n", 
            "            #fixed.\n", 
            "            X_u = np.hstack((np.ones([userdf.shape[0],1]),\n", 
            "                             gamma[userdf.midx,1:]))\n", 
            "            \n", 
            "            theta[ui,:] = theta_u_draw(X_u, Y_u, sig2, Lambda_theta)\n", 
            "\n", 
            "        #Record draws\n", 
            "        mu_draws[i] = mu\n", 
            "        sig2_draws[i] = sig2\n", 
            "        theta_draws[:,:,i] = theta\n", 
            "        gamma_draws[:,:,i] = gamma\n", 
            "\n", 
            "    return {\"mu\": mu_draws, \"sig2\": sig2_draws,\n", 
            "            \"theta\": theta_draws, \"gamma\": gamma_draws,\n", 
            "            \"EY\": EY_draws}"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "###Posterior Summaries###\n", 
            "\n", 
            "Once you have posterior draws from the sampler, the most natural thing to do is to compute the **posterior mean** of each quantity you are intersted in. To do this, we simply need to take the average value of each quantity across the samples drawn from the sampler. Before taking the average, however, we will want to ignore the first 20-30% of samples because these correspond the **burnin period**, the time during which the sampler is still looking for the main meat of the distribution."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "####Ok it's time to recommend!"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**3.3** Now that you have the Gibbs sampler, draw 1000 samples from the posterior distribution using a two-dimensional latent factor and prior precisions `Lambda_theta_diag` and `Lambda_gamma_diag` both equal to 0.1.\n", 
            "\n", 
            "Compute the posterior mean of the fitted values for each $Y_{um}$, eliminating the first 200 samples. Call these the `prediction`.  These constitute our recommendations. True to the bayesian paradigm, we dont just have mean predictions, but entire distributions. But currently we are only interested in the means."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 39, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "Plot the predictions against the observed data.You can use the `compare_results` function defined in the previous section. How do the fitted values compare to those from the KNN procedure?"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 40, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "*your answer here*"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "##Q4 Scaling Up"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "All our recommenders suffer from problems having to do with the fact that we subsetted an already sparse user-item matrix. The more items we have, the more items we may find in the vicinity of a given item, and thus we are likely to give a more robust average rating to the given item.\n", 
            "\n", 
            "In this problem we shall use Amazon Elastic Map-Reduce to tackle the entire user-restaurant matrix. We shall do this in two parts: we'll use MRJob locally on your machine to on the smaller data set to calclate the pearson database, and then we'll tackle the entire data set on Amazon.\n", 
            "\n", 
            "The larger set has 35000 users and 4500 items. Computing the 4500X4500 similarity matrix on one machine will be prohibitively expensive. Thus we'll adopt a strategy where we'll split the calculation over multiple machines using the map-reduce paradigm, with mappers and reducers working on multiple machines \n", 
            "\n", 
            "Then we calculate the k-nearest neighbors in the 'space' of the user: this involves a database lookup and an iteration over the items a user has rated. Since the latter is usually not a very large number, this computation can be managed on a front end machine (even if storing the database will take a lot of memory).\n"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "We'll first create subset data frames, which have just those columns which we will send to the map-reduce. We'll also strip out the header and index of the frame. The reason for doing this is: unless we pre-populate the machines on Amazon with software, we can *rely only on the regular python library, numpy, and scipy being there (and at python 2.6)*, and thus we will need to parse the csv file, line by line (`mrjob` uses hadoop's stream protocol and thus needs to be fed line by line)."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 41, 
          "input": [
            "subsetoffull=fulldf[['user_id','business_id', 'stars','business_avg','user_avg']]\n", 
            "subsetoffull.to_csv(\"subset-full.csv\", index=False, header=False)\n", 
            "subsetofsmall=smalldf[['user_id','business_id', 'stars','business_avg','user_avg']]\n", 
            "subsetofsmall.to_csv(\"subset-small.csv\", index=False, header=False)"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "### Running mrjob locally\n", 
            "\n", 
            "`mrjob` scripts cannot be run from the ipython notebook, as they fork themselves on execution. Thus you must write the code for mrjob in a separate file which you must submit along with this homework, in the same folder as the python notebook file.\n", 
            "\n", 
            "If you have not done so already (you were supposed to do this as part of HW 0), you will first need to install `mrjob`. The appropriate equivalent of the following incantation should do the job:\n", 
            "\n", 
            "    ~/anaconda/bin/pip install mrjob\n", 
            "    \n", 
            "\n", 
            "    \n", 
            "To familiarize yourself with the structure of an `mrjob` script, please read [this](http://mrjob.readthedocs.org/en/latest/guides/quickstart.html#writing-your-first-job) . Run the examples in that document to familiarize yourself with `mrjob`.\n", 
            "\n", 
            "The kind of script you will be writing is in the section \"Writing your second job\" in that document. \n"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "All mrjob tasks use the map-reduce strategy to divide up computation across computers. You should work through the mrjob tutorial to gain familiarity with this, but we\u2019ll also outline the basic process here:\n", 
            "\n", 
            "1. During the first map step, mrjob calls a mapper function with a key (which for the first step is None), and a value (which for the first step is a line of data from an input file). This function does whatever it wants with this data, and yields a key and value.  The key is used in step 2 to gather up the values from all the different mappers into groups\n", 
            "\n", 
            "2. mrjob collects the outputs from all the mappers, and gathers them into subsets with the same key value (this is similar to what pandas.groupby does). It passes each of these subsets to a reducer (or \u201ccollector\u201d) function, whose job is to synthesize this list of grouped data into something useful (e.g., computing the mean of all the inputs). It then yields the key and reduced value. \n", 
            "\n", 
            "3. If there are any additional steps, mrjob feeds each output from a reducer function in step 2 to the next mapper. Otherwise, it prints the output.\n", 
            "\n", 
            "The point behind map-reduce is to agree upon a common framework to split up a large computational job into smaller tasks. mrjob then has a lot of freedom to organize how these tasks run in parallel, on many machines"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "#### Writing your script"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**4.1** Write a MRJOB script, called `computesim.py`. The object of this script is to take a csv file and return a tuple `(rho, n_common)` as `calculate_similarity` for pairs of restaurants. See `skeleton.py` below for the SPEC of this file. Your job is to fill in those methods. You MUST use this skeleton.\n", 
            "\n", 
            "This script is to be run like so (substitute your own operating system's call):\n", 
            "\n", 
            "    ~/anaconda/bin/python computesim.py subset-small.csv > output.small.local.txt\n", 
            "\n", 
            "Thus, when the script below is run in this fashion, mrjob will read the data line-by-line from subset-small.csv, and pass it to the first \"step\".\n", 
            "\n"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "####Algorithm to calculate pearson similarities\n", 
            "\n", 
            "Here is the description of the algorithm for RestaurantSimilarities.\n", 
            "\n", 
            "Your code will have two steps. Each step will have a mapper and a reducer. These are described in turn here:\n", 
            "\n", 
            "1. `line_mapper` will split the line, yielding the `user_id` as key, and the rest as value. This method's implementation is provided for you.\n", 
            "\n", 
            "2. `users_items_collector` is a reducer. It is passed ALL mapper outputs corresponding to a particular `user_id`. Put these emissions into a list, and re-emit the `user_id` with this list.\n", 
            "\n", 
            "3. `pair_items_mapper` takes the `user_id` and the list. It dosent do anything with the `user_id`, however, it takes every combination (thus len(list) choose 2) of 2 `business_id`s from the passed on list (see combinations in itertools in the python documentation) and sends on the remaining information keyed on the tuple `(restaurant1, restaurant2)`. Be sure to handle the case where the restaurant id's are flipped: include them somehow under the same key.\n", 
            "\n", 
            "4. `calc_sim_collector` is passed ALL sent on list information for the pair of restaurants that was emitted in the previous step. Note that thse will come from different `user_id`s. This sort of collection is key to this style of programming. This list information should now correspond to all the common support of the two restaurants. Use this information to calculate this common support and the pearson similarity. Return the aforementioned tuple by yielding it keyed by the tuple of restaurants. This information will be sent to the output file. The output keys and values will both be in JSON format, separated by a tab.\n", 
            "\n", 
            "The output should be saved in a file via redirection as `output.small.local.txt`"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "####Skeleton File for this problem\n", 
            "\n", 
            "You ca access it [here](https://raw.github.com/cs109/content/master/skeleton.py) or just run the next cell to see it."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 42, 
          "input": [
            "from pygments import highlight\n", 
            "from pygments.lexers import PythonLexer\n", 
            "from pygments.formatters import HtmlFormatter\n", 
            "from IPython.display import HTML\n", 
            "import urllib\n", 
            "skelcode = urllib.urlopen(\"https://raw.github.com/cs109/content/master/skeleton.py\").read()\n", 
            "skelhtml=highlight(skelcode, PythonLexer(), HtmlFormatter())\n", 
            "HTML(skelhtml)"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "#### Explanation for those funny `yield` keywords\n", 
            "\n", 
            "The functions above \u201cyield\u201d values, and do not \u201creturn\u201d them. They are **generators**. Here is an example:"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 43, 
          "input": [
            "def upper_generator(words):\n", 
            "    for word in words:\n", 
            "        yield word.upper()\n", 
            "\n", 
            "words = ['a', 'couple', 'of', 'words', 'to', 'process']\n", 
            "\n", 
            "print upper_generator(words)\n", 
            "print list(upper_generator(words))\n", 
            "for u in upper_generator(words):\n", 
            "     print u\n", 
            "\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "You can read more [here](http://nedbatchelder.com/text/iter.html). Also see Thu Oct 17th's class video for information about classes and generators."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "Include `computesim.py` in your submission in the same folder as the notebook. Uncommenting and running the following cell should **output your code in here**."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 44, 
          "input": [
            "#thecode = open(\"computesim.py\").read()\n", 
            "#thehtml=highlight(thecode, PythonLexer(), HtmlFormatter())\n", 
            "#HTML(thehtml)"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "#### Checking the results\n", 
            "\n", 
            "Let us load the data from the file"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 45, 
          "input": [
            "output_small_local=[[json.loads(j) for j in line.strip().split(\"\\t\")] for line in open(\"./output.small.local.txt\")]\n", 
            "output_small_local[0]"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "We will Implement a function `make_database_from_pairs` which takes a dataframe of restaurants `smalldf` and the output parsed in the previous command to create the database like before. By the nature of the map-reduce algorithms these only contain those restaurant pairs with common support. The `Database` constructor initializes the remaining similarities to 0.\n", 
            "\n", 
            "The function will take the dataframe and `bizpairs` obtained by parsing the EMR output file which have the key of business pairs and value the pair of pearson correlation and `n_common`. It will return an instance of the `Database` class.\n", 
            "\n", 
            "This function will take a long time to run on large data sets.\n"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 46, 
          "input": [
            "def make_database_from_pairs(df, bizpairs):\n", 
            "    \"\"\"\n", 
            "    make the database from the pairs returned from mrjob.\n", 
            "    df is the dataframe, smalldf or fulldf.\n", 
            "    bizpairs are a list of elements, each of which is a list of two\n", 
            "        lists. The first of these lists has the two business id's, while\n", 
            "        the second has the similarity and the common support\n", 
            "    Returns an instance of the Database class.\n", 
            "    \"\"\"\n", 
            "    dbase=Database(df)\n", 
            "    cache={}\n", 
            "    for bp,corrs in bizpairs:\n", 
            "        b1,b2=bp\n", 
            "        i1=dbase.uniquebizids[b1]\n", 
            "        i2=dbase.uniquebizids[b2]\n", 
            "        sim,nsup=corrs\n", 
            "        dbase.database_sim[i1][i2]=sim\n", 
            "        dbase.database_sim[i2][i1]=sim\n", 
            "        dbase.database_sup[i1][i2]=nsup\n", 
            "        dbase.database_sup[i2][i1]=nsup\n", 
            "        if cache.has_key(b1):\n", 
            "            nsup1=cache[b1]\n", 
            "        else:\n", 
            "            nsup1=dbase.df[dbase.df.business_id==b1].user_id.count()\n", 
            "            cache[b1]=nsup1\n", 
            "        if cache.has_key(b2):\n", 
            "            nsup2=cache[b2]\n", 
            "        else:\n", 
            "            nsup2=dbase.df[dbase.df.business_id==b2].user_id.count()\n", 
            "            cache[b2]=nsup2\n", 
            "        dbase.database_sim[i1][i1]=1.0\n", 
            "        dbase.database_sim[i2][i2]=1.0\n", 
            "        dbase.database_sup[i1][i1]=nsup1\n", 
            "        dbase.database_sup[i2][i2]=nsup2\n", 
            "    return dbase"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "We will store the output in variable `db_mrjob_local`."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 47, 
          "input": [
            "db_mrjob_local=make_database_from_pairs(smalldf, output_small_local)"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "We print a pair to see that our answers are identical."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 48, 
          "input": [
            "print db.get(\"zruUQvFySeXyEd7_rQixBg\", \"z3yFuLVrmH-3RJruPEMYKw\")\n", 
            "print db_mrjob_local.get(\"zruUQvFySeXyEd7_rQixBg\", \"z3yFuLVrmH-3RJruPEMYKw\")"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "**4.2** Lets test that our results are overall the same as before"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 49, 
          "input": [
            "sums=0.\n", 
            "count=0\n", 
            "for k in db.uniquebizids.keys():\n", 
            "    for k2 in db.uniquebizids.keys():\n", 
            "        count=count+1\n", 
            "        sums=sums+db.get(k,k2)[0]-db_mrjob_local.get(k,k2)[0]\n", 
            "print sums, count"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "### Running on Amazon Elastic Map Reduce(EMR)"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "At this point, we shall shift to running on Amazon EMR. \n", 
            "\n", 
            "------------\n", 
            "\n", 
            "*Read [this document](http://nbviewer.ipython.org/urls/raw.github.com/cs109/content/master/InstructionsForAmazonEMR.ipynb) for instructions on how to set yourself up on Amazon.*\n", 
            "\n", 
            "------------\n", 
            "\n", 
            "#### Reproduce the results with the smaller file on EMR\n", 
            "\n", 
            "Test the smaller file and make sure it has the same results. For example, you could use the incantation:\n", 
            "\n", 
            "    ~/anaconda/bin/python computesim.py -r emr --num-ec2-instances 2 subset-small.csv > output.small.emr.txt\n", 
            "\n", 
            "You do **NOT** need to submit any results from that exploration to us.\n", 
            "\n", 
            "**Important**: Please always make sure that your code is bug free, before actually submitting it to amazon. Try to run the job locally first and see if it produces the desired result. Then, if this worked, you are ready to proceed to the cloud. The homework problems are small and your free credit should provide you with a lot of room for running and testing on Amazon. However, it is your responsibility to make sure the jobs terminate properly and do not cause excessive costs.\n", 
            "\n", 
            "You can always monitor your currently running jobs (in the US-East sector) using [this overview at region US-EAST-1](https://console.aws.amazon.com/elasticmapreduce/home?region=us-east-1) of your MapReduce job flows."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "#### Running the larger job"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**4.3** Run the script on the larger file `subset-full.csv`. Use between 4-8 instances on EMR on Amazon. Save the output in `output.full.emr.txt`. Your incantation will be something like:\n", 
            "\n", 
            "    ~/anaconda/bin/python computesim.py -r emr --num-ec2-instances 5 subset-full.csv > output.full.emr.txt"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "You might elect to [save the file on S3](http://mrjob.readthedocs.org/en/latest/guides/emr-quickstart.html#sending-output-to-a-specific-place) and bring it over manually.\n", 
            "\n", 
            "Try and think about what size job would be best to run on Amazon, given that there is a setup time. There is a way to persistently set up machines (the mrjob documentation provides the details), but then remember you will be billed for that setup and need to monitor it. However, a persistent setup might come useful for your projects."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###Loading the full output from EMR"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "Lets load the output in. **CAUTION** The next two cells will also take a lot of time to run and load.  "
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 50, 
          "input": [
            "output_full_emr=[[json.loads(j) for j in l.strip().split(\"\\t\")] for l in open(\"./output.full.emr.txt\")]"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "This function will take a very long time to run, on the order of 5 minutes or more, depending on your computer"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 51, 
          "input": [
            "dbfull=make_database_from_pairs(fulldf, output_full_emr)"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "**4.4**  For `testuserid`, once again, print out the ratings using the `bizs` list as before. How have they changed with respect to Question 2? Why might this be?"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "cell_type": "code", 
          "language": "python", 
          "outputs": [], 
          "collapsed": false, 
          "prompt_number": 52, 
          "input": [
            "#your code here\n"
          ], 
          "metadata": {}
        }, 
        {
          "source": [
            "*your answer here*"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "**4.5** Outline another `step` (in words) in the mrjob map-reduce class to implement a simple but scalable recommender of the global type that we did in Question 1.5 to 1.7."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "*your answer here*"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###Submission Instructions:\n", 
            "\n", 
            "Restart and run your notebook one last time (you do not have to rerun the Amazon EMR script computesim.py), to make sure the output from each cell is up to date. To submit your homework, create a folder named lastname_firstinitial_hw4 and place your solutions in the folder. Double check that the file is still called HW4.ipynb, and that it contains your code. Also include the `computesim.py` script and the `output.small.local.txt` data file. Do **NOT** include the data file `output.full.emr.txt` from the larger run (its huge, so we will check your answers to 4.4 instead). Compress the folder (please use .zip compression) and submit to the CS109 dropbox in the appropriate folder. If we cannot access your work because these directions are not followed correctly, we will not grade your work!"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "###FINI\n", 
            "\n", 
            "You have developed all kinds of recommenders. We hope it was fun. Time constraints prevented us from going into model checking, but perhaps you would like to try that on your own. Or use S3 or a hosted database as a place to store sharded similarities. You might want to take a gander at Yelp's entire Phoenix dataset, or use the other attributes present in the data set. So many possibilities!\n", 
            "\n", 
            "If you'd like to learn more, please read Chris Volinksy's papers on the Netflix prize. There are also comprehensive reviews [here](http://arxiv.org/abs/1202.1112) and [here](http://www.grouplens.org/system/files/FnT%20CF%20Recsys%20Survey.pdf)."
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }, 
        {
          "source": [
            "*css tweaks in this cell*\n", 
            "<style>\n", 
            "div.text_cell_render {\n", 
            " line-height: 150%;\n", 
            " font-size: 110%;\n", 
            " width: 800px;\n", 
            " margin-left:50px;\n", 
            " margin-right:auto;\n", 
            "}\n", 
            "\n", 
            "</style>"
          ], 
          "cell_type": "markdown", 
          "metadata": {}
        }
      ], 
      "metadata": {}
    }
  ]
}