Week 6 - Local Regression Assignment.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Predicting house prices using k-nearest neighbors regression\n",
    "In this notebook, you will implement k-nearest neighbors regression. You will:\n",
    "  * Find the k-nearest neighbors of a given query input\n",
    "  * Predict the output for the query input using the k-nearest neighbors\n",
    "  * Choose the best value of k using a validation set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Fire up GraphLab Create"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import graphlab"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Load in house sales data"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For this notebook, we use a subset of the King County housing dataset created by randomly selecting 40% of the houses in the full dataset."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "This non-commercial license of GraphLab Create for academic use is assigned to amitha353@gmail.com and will expire on May 07, 2019.\n"
     ]
    },
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "[INFO] graphlab.cython.cy_server: GraphLab Create v2.1 started. Logging: C:\\Users\\Amitha\\AppData\\Local\\Temp\\graphlab_server_1532010859.log.0\n"
     ]
    }
   ],
   "source": [
    "sales = graphlab.SFrame('kc_house_data_small.gl/')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Import useful functions from previous notebooks"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To efficiently compute pairwise distances among data points, we will convert the SFrame into a 2D Numpy array. First import the numpy library and then copy and paste `get_numpy_data()` from the second notebook of Week 2."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import numpy as np # note this allows us to refer to numpy as np instead"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def get_numpy_data(data_sframe, features, output):\n",
    "    data_sframe['constant'] = 1 # this is how you add a constant column to an SFrame\n",
    "    # add the column 'constant' to the front of the features list so that we can extract it along with the others:\n",
    "    features = ['constant'] + features # this is how you combine two lists\n",
    "    # select the columns of data_SFrame given by the features list into the SFrame features_sframe (now including constant):\n",
    "    features_sframe = data_sframe[features]\n",
    "    # the following line will convert the features_SFrame into a numpy matrix:\n",
    "    feature_matrix = features_sframe.to_numpy()\n",
    "    # assign the column of data_sframe associated with the output to the SArray output_sarray\n",
    "    output_sarray = data_sframe[output]\n",
    "    # the following will convert the SArray into a numpy array by first converting it to a list\n",
    "    output_array = output_sarray.to_numpy()\n",
    "    return(feature_matrix, output_array)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We will also need the `normalize_features()` function from Week 5 that normalizes all feature columns to unit norm. Paste this function below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def normalize_features(feature_matrix):\n",
    "    norms = np.linalg.norm(feature_matrix, axis=0)\n",
    "    normalized_features = feature_matrix/norms\n",
    "    return (normalized_features, norms)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Split data into training, test, and validation sets"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "(train_and_validation, test) = sales.random_split(.8, seed=1) # initial train/test split\n",
    "(train, validation) = train_and_validation.random_split(.8, seed=1) # split training set into training and validation sets"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Extract features and normalize"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using all of the numerical inputs listed in `feature_list`, transform the training, test, and validation SFrames into Numpy arrays:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "feature_list = ['bedrooms',  \n",
    "                'bathrooms',  \n",
    "                'sqft_living',  \n",
    "                'sqft_lot',  \n",
    "                'floors',\n",
    "                'waterfront',  \n",
    "                'view',  \n",
    "                'condition',  \n",
    "                'grade',  \n",
    "                'sqft_above',  \n",
    "                'sqft_basement',\n",
    "                'yr_built',  \n",
    "                'yr_renovated',  \n",
    "                'lat',  \n",
    "                'long',  \n",
    "                'sqft_living15',  \n",
    "                'sqft_lot15']\n",
    "features_train, output_train = get_numpy_data(train, feature_list, 'price')\n",
    "features_test, output_test = get_numpy_data(test, feature_list, 'price')\n",
    "features_valid, output_valid = get_numpy_data(validation, feature_list, 'price')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In computing distances, it is crucial to normalize features. Otherwise, for example, the `sqft_living` feature (typically on the order of thousands) would exert a much larger influence on distance than the `bedrooms` feature (typically on the order of ones). We divide each column of the training feature matrix by its 2-norm, so that the transformed column has unit norm.\n",
    "\n",
    "IMPORTANT: Make sure to store the norms of the features in the training set. The features in the test and validation sets must be divided by these same norms, so that the training, test, and validation sets are normalized consistently."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "features_train, norms = normalize_features(features_train) # normalize training set features (columns)\n",
    "features_test = features_test / norms # normalize test set by training set norms\n",
    "features_valid = features_valid / norms # normalize validation set by training set norms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Compute a single distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To start, let's just explore computing the \"distance\" between two given houses.  We will take our **query house** to be the first house of the test set and look at the distance between this house and the 10th house of the training set.\n",
    "\n",
    "To see the features associated with the query house, print the first row (index 0) of the test feature matrix. You should get an 18-dimensional vector whose components are between 0 and 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0.01345102  0.01551285  0.01807473  0.01759212  0.00160518  0.017059    0.\n",
      "  0.05102365  0.0116321   0.01564352  0.01362084  0.02481682  0.01350306\n",
      "  0.          0.01345386 -0.01346927  0.01375926  0.0016225 ]\n"
     ]
    }
   ],
   "source": [
    "print features_test[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now print the 10th row (index 9) of the training feature matrix. Again, you get an 18-dimensional vector with components between 0 and 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0.01345102  0.01163464  0.00602491  0.0083488   0.00050756  0.01279425\n",
      "  0.          0.          0.01938684  0.01390535  0.0096309   0.\n",
      "  0.01302544  0.          0.01346821 -0.01346254  0.01195898  0.00156612]\n"
     ]
    }
   ],
   "source": [
    "print features_train[9]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***QUIZ QUESTION ***\n",
    "\n",
    "What is the Euclidean distance between the query house and the 10th house of the training set? \n",
    "\n",
    "Note: Do not use the `np.linalg.norm` function; use `np.sqrt`, `np.sum`, and the power operator (`**`) instead. The latter approach is more easily adapted to computing multiple distances at once.\n",
    "\n",
    "Euclidean distance: distance(xj,xq)* sqrt(a1(xj[1]−xq[1])2+...+ad(xj[d]−xq[d])2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0597235937167\n"
     ]
    }
   ],
   "source": [
    "euclidean_distance = np.sqrt(np.sum((features_train[9] - features_test[0])** 2))\n",
    "print euclidean_distance"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Compute multiple distances"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Of course, to do nearest neighbor regression, we need to compute the distance between our query house and *all* houses in the training set.  \n",
    "\n",
    "To visualize this nearest-neighbor search, let's first compute the distance from our query house (`features_test[0]`) to the first 10 houses of the training set (`features_train[0:10]`) and then search for the nearest neighbor within this small set of houses.  Through restricting ourselves to a small set of houses to begin with, we can visually scan the list of 10 distances to verify that our code for finding the nearest neighbor is working.\n",
    "\n",
    "Write a loop to compute the Euclidean distance from the query house to each of the first 10 houses in the training set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(0, 0.0602747091729555)\n",
      "(1, 0.085468811488270832)\n",
      "(2, 0.061499464371202843)\n",
      "(3, 0.053402739788200579)\n",
      "(4, 0.058444840639381393)\n",
      "(5, 0.059879215101840008)\n",
      "(6, 0.054631404972615261)\n",
      "(7, 0.055431083241597921)\n",
      "(8, 0.052383627840972731)\n",
      "(9, 0.059723593716661257)\n"
     ]
    }
   ],
   "source": [
    "dist_dict = {}\n",
    "for i in range(0,10):\n",
    "    dist_dict[i] = np.sqrt(np.sum((features_train[i] - features_test[0])**2))\n",
    "    print (i, np.sqrt(np.sum((features_train[i] - features_test[0])**2)))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*** QUIZ QUESTION ***\n",
    "\n",
    "Among the first 10 training houses, which house is the closest to the query house?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(8, 0.052383627840972731)\n"
     ]
    }
   ],
   "source": [
    "print min(dist_dict.items(), key=lambda x:x[1])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is computationally inefficient to loop over computing distances to all houses in our training dataset. Fortunately, many of the Numpy functions can be **vectorized**, applying the same operation over multiple values or vectors.  We now walk through this process."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Consider the following loop that computes the element-wise difference between the features of the query house (`features_test[0]`) and the first 3 training houses (`features_train[0:3]`):"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[  0.00000000e+00  -3.87821276e-03  -1.20498190e-02  -1.05552733e-02\n",
      "   2.08673616e-04  -8.52950206e-03   0.00000000e+00  -5.10236549e-02\n",
      "   0.00000000e+00  -3.47633726e-03  -5.50336860e-03  -2.48168183e-02\n",
      "  -1.63756198e-04   0.00000000e+00  -1.70072004e-05   1.30577772e-05\n",
      "  -5.14364795e-03   6.69281453e-04]\n",
      "[  0.00000000e+00  -3.87821276e-03  -4.51868214e-03  -2.26610387e-03\n",
      "   7.19763456e-04   0.00000000e+00   0.00000000e+00  -5.10236549e-02\n",
      "   0.00000000e+00  -3.47633726e-03   1.30705004e-03  -1.45830788e-02\n",
      "  -1.91048898e-04   6.65082271e-02   4.23240653e-05   6.22415897e-06\n",
      "  -2.89330197e-03   1.47606982e-03]\n",
      "[  0.00000000e+00  -7.75642553e-03  -1.20498190e-02  -1.30002801e-02\n",
      "   1.60518166e-03  -8.52950206e-03   0.00000000e+00  -5.10236549e-02\n",
      "   0.00000000e+00  -5.21450589e-03  -8.32384500e-03  -2.48168183e-02\n",
      "  -3.13866046e-04   0.00000000e+00   4.71047219e-05   1.56530415e-05\n",
      "   3.72914476e-03   1.64764925e-03]\n"
     ]
    }
   ],
   "source": [
    "for i in xrange(3):\n",
    "    print features_train[i]-features_test[0]\n",
    "    # should print 3 vectors of length 18"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The subtraction operator (`-`) in Numpy is vectorized as follows:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[  0.00000000e+00  -3.87821276e-03  -1.20498190e-02  -1.05552733e-02\n",
      "    2.08673616e-04  -8.52950206e-03   0.00000000e+00  -5.10236549e-02\n",
      "    0.00000000e+00  -3.47633726e-03  -5.50336860e-03  -2.48168183e-02\n",
      "   -1.63756198e-04   0.00000000e+00  -1.70072004e-05   1.30577772e-05\n",
      "   -5.14364795e-03   6.69281453e-04]\n",
      " [  0.00000000e+00  -3.87821276e-03  -4.51868214e-03  -2.26610387e-03\n",
      "    7.19763456e-04   0.00000000e+00   0.00000000e+00  -5.10236549e-02\n",
      "    0.00000000e+00  -3.47633726e-03   1.30705004e-03  -1.45830788e-02\n",
      "   -1.91048898e-04   6.65082271e-02   4.23240653e-05   6.22415897e-06\n",
      "   -2.89330197e-03   1.47606982e-03]\n",
      " [  0.00000000e+00  -7.75642553e-03  -1.20498190e-02  -1.30002801e-02\n",
      "    1.60518166e-03  -8.52950206e-03   0.00000000e+00  -5.10236549e-02\n",
      "    0.00000000e+00  -5.21450589e-03  -8.32384500e-03  -2.48168183e-02\n",
      "   -3.13866046e-04   0.00000000e+00   4.71047219e-05   1.56530415e-05\n",
      "    3.72914476e-03   1.64764925e-03]]\n"
     ]
    }
   ],
   "source": [
    "print features_train[0:3] - features_test[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note that the output of this vectorized operation is identical to that of the loop above, which can be verified below:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]\n",
      "[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]\n",
      "[ 0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.]\n"
     ]
    }
   ],
   "source": [
    "# verify that vectorization works\n",
    "results = features_train[0:3] - features_test[0]\n",
    "print results[0] - (features_train[0]-features_test[0])\n",
    "# should print all 0's if results[0] == (features_train[0]-features_test[0])\n",
    "print results[1] - (features_train[1]-features_test[0])\n",
    "# should print all 0's if results[1] == (features_train[1]-features_test[0])\n",
    "print results[2] - (features_train[2]-features_test[0])\n",
    "# should print all 0's if results[2] == (features_train[2]-features_test[0])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Aside: it is a good idea to write tests like this cell whenever you are vectorizing a complicated operation."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Perform 1-nearest neighbor regression\n",
    "\n",
    "Now that we have the element-wise differences, it is not too hard to compute the Euclidean distances between our query house and all of the training houses. First, write a single-line expression to define a variable `diff` such that `diff[i]` gives the element-wise difference between the features of the query house and the `i`-th training house."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "diff = features_train - features_test[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To test the code above, run the following cell, which should output a value -0.0934339605842:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-0.0934339605842\n"
     ]
    }
   ],
   "source": [
    "print diff[-1].sum() # sum of the feature differences between the query and last training house\n",
    "# should print -0.0934339605842"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The next step in computing the Euclidean distances is to take these feature-by-feature differences in `diff`, square each, and take the sum over feature indices.  That is, compute the sum of square feature differences for each training house (row in `diff`).\n",
    "\n",
    "By default, `np.sum` sums up everything in the matrix and returns a single number. To instead sum only over a row or column, we need to specifiy the `axis` parameter described in the `np.sum` [documentation](http://docs.scipy.org/doc/numpy-1.10.1/reference/generated/numpy.sum.html). In particular, `axis=1` computes the sum across each row.\n",
    "\n",
    "Below, we compute this sum of square feature differences for all training houses and verify that the output for the 16th house in the training set is equivalent to having examined only the 16th row of `diff` and computing the sum of squares on that row alone."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.00330705902879\n",
      "0.00330705902879\n"
     ]
    }
   ],
   "source": [
    "print np.sum(diff**2, axis=1)[15] # take sum of squares across each row, and print the 16th sum\n",
    "print np.sum(diff[15]**2) # print the sum of squares for the 16th row -- should be same as above"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "With this result in mind, write a single-line expression to compute the Euclidean distances between the query house and all houses in the training set. Assign the result to a variable `distances`.\n",
    "\n",
    "**Hint**: Do not forget to take the square root of the sum of squares."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "distances = np.sqrt(np.sum(diff**2, axis=1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To test the code above, run the following cell, which should output a value 0.0237082324496:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.0237082324496\n"
     ]
    }
   ],
   "source": [
    "print distances[100] # Euclidean distance between the query house and the 101th training house\n",
    "# should print 0.0237082324496"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now you are ready to write a function that computes the distances from a query house to all training houses. The function should take two parameters: (i) the matrix of training features and (ii) the single feature vector associated with the query."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compute_distances(train_matrix, query_vector):\n",
    "    diff = train_matrix - query_vector\n",
    "    distances = np.sqrt(np.sum(diff**2, axis=1))\n",
    "    return distances"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "*** QUIZ QUESTIONS ***\n",
    "\n",
    "1.  Take the query house to be third house of the test set (`features_test[2]`).  What is the index of the house in the training set that is closest to this query house?\n",
    "2.  What is the predicted value of the query house based on 1-nearest neighbor regression?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[382] 0.00286049526751\n",
      "0.00286049526751\n"
     ]
    }
   ],
   "source": [
    "third_house_distance = compute_distances(features_train, features_test[2])\n",
    "print third_house_distance.argsort()[:1], min(third_house_distance)\n",
    "print third_house_distance[382]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 382 1149 4087 3142]\n"
     ]
    }
   ],
   "source": [
    "print np.argsort(third_house_distance, axis = 0)[:4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "249000\n"
     ]
    }
   ],
   "source": [
    "print output_train[382]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Perform k-nearest neighbor regression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "For k-nearest neighbors, we need to find a *set* of k houses in the training set closest to a given query house. We then make predictions based on these k nearest neighbors."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Fetch k-nearest neighbors\n",
    "\n",
    "Using the functions above, implement a function that takes in\n",
    " * the value of k;\n",
    " * the feature matrix for the training houses; and\n",
    " * the feature vector of the query house\n",
    " \n",
    "and returns the indices of the k closest training houses. For instance, with 2-nearest neighbor, a return value of [5, 10] would indicate that the 6th and 11th training houses are closest to the query house.\n",
    "\n",
    "**Hint**: Look at the [documentation for `np.argsort`](http://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compute_k_nearest_neighbors(k, features_matrix, feature_vector):\n",
    "    distances = compute_distances(features_matrix, feature_vector)\n",
    "    return np.argsort(distances, axis = 0)[:k]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*** QUIZ QUESTION ***\n",
    "\n",
    "Take the query house to be third house of the test set (`features_test[2]`).  What are the indices of the 4 training houses closest to the query house?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[ 382 1149 4087 3142]\n"
     ]
    }
   ],
   "source": [
    "print compute_k_nearest_neighbors(4, features_train, features_test[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Make a single prediction by averaging k nearest neighbor outputs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now that we know how to find the k-nearest neighbors, write a function that predicts the value of a given query house. **For simplicity, take the average of the prices of the k nearest neighbors in the training set**. The function should have the following parameters:\n",
    " * the value of k;\n",
    " * the feature matrix for the training houses;\n",
    " * the output values (prices) of the training houses; and\n",
    " * the feature vector of the query house, whose price we are predicting.\n",
    " \n",
    "The function should return a predicted value of the query house.\n",
    "\n",
    "**Hint**: You can extract multiple items from a Numpy array using a list of indices. For instance, `output_train[[6, 10]]` returns the prices of the 7th and 11th training houses."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compute_distances_k_avg(k, features_matrix, output_values, feature_vector):\n",
    "    k_neigbors = compute_k_nearest_neighbors(k, features_matrix, feature_vector)\n",
    "    avg_value = np.mean(output_values[k_neigbors])\n",
    "    return avg_value   "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*** QUIZ QUESTION ***\n",
    "\n",
    "Again taking the query house to be third house of the test set (`features_test[2]`), predict the value of the query house using k-nearest neighbors with `k=4` and the simple averaging method described and implemented above."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "413987.5\n"
     ]
    }
   ],
   "source": [
    "print compute_distances_k_avg(4, features_train, output_train, features_test[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Compare this predicted value using 4-nearest neighbors to the predicted value using 1-nearest neighbor computed earlier."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Make multiple predictions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Write a function to predict the value of *each and every* house in a query set. (The query set can be any subset of the dataset, be it the test set or validation set.) The idea is to have a loop where we take each house in the query set as the query house and make a prediction for that specific house. The new function should take the following parameters:\n",
    " * the value of k;\n",
    " * the feature matrix for the training houses;\n",
    " * the output values (prices) of the training houses; and\n",
    " * the feature matrix for the query set.\n",
    " \n",
    "The function should return a set of predicted values, one for each house in the query set.\n",
    "\n",
    "**Hint**: To get the number of houses in the query set, use the `.shape` field of the query features matrix. See [the documentation](http://docs.scipy.org/doc/numpy-1.10.1/reference/generated/numpy.ndarray.shape.html)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def compute_distances_k_all(k, features_matrix, output_values, feature_vector):\n",
    "    num_of_rows = feature_vector.shape[0]\n",
    "    predicted_values = []\n",
    "    for i in xrange(num_of_rows):\n",
    "        avg_value = compute_distances_k_avg(k, features_train, output_train, features_test[i])\n",
    "        predicted_values.append(avg_value)\n",
    "    return predicted_values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10\n"
     ]
    }
   ],
   "source": [
    "print features_test[0:10].shape[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*** QUIZ QUESTION ***\n",
    "\n",
    "Make predictions for the first 10 houses in the test set using k-nearest neighbors with `k=10`. \n",
    "\n",
    "1. What is the index of the house in this query set that has the lowest predicted value? \n",
    "2. What is the predicted value of this house?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[881300.0, 431860.0, 460595.0, 430200.0, 766750.0, 667420.0, 350032.0, 512800.70000000001, 484000.0, 457235.0]\n"
     ]
    }
   ],
   "source": [
    "predicted_values = compute_distances_k_all(10, features_train, output_train, features_test[0:10])\n",
    "print predicted_values"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "6\n"
     ]
    }
   ],
   "source": [
    "print predicted_values.index(min(predicted_values))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "350032.0\n"
     ]
    }
   ],
   "source": [
    "print min(predicted_values)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Choosing the best value of k using a validation set"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "There remains a question of choosing the value of k to use in making predictions. Here, we use a validation set to choose this value. Write a loop that does the following:\n",
    "\n",
    "* For `k` in [1, 2, ..., 15]:\n",
    "    * Makes predictions for each house in the VALIDATION set using the k-nearest neighbors from the TRAINING set.\n",
    "    * Computes the RSS for these predictions on the VALIDATION set\n",
    "    * Stores the RSS computed above in `rss_all`\n",
    "* Report which `k` produced the lowest RSS on VALIDATION set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "(Depending on your computing environment, this computation may take 10-15 minutes.)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "rss_all = []\n",
    "for k in range(1,16):    \n",
    "    predict_value = compute_distances_k_all(k, features_train, output_train, features_valid)\n",
    "    residual = (output_valid - predict_value)\n",
    "    rss = sum(residual**2)\n",
    "    rss_all.append(rss)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": false
   },
   "source": [
    "To visualize the performance as a function of `k`, plot the RSS on the VALIDATION set for each considered `k` value:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[355632427476622.0, 317939124951086.5, 313153111376088.5, 301621468995236.0, 294266734341982.37, 287781925015337.87, 287842561046849.31, 286179146468967.94, 281718696883431.62, 280358603702662.75, 278687700531166.91, 278744728841428.25, 275043861135800.91, 273895810640073.47, 272162684453609.75]\n"
     ]
    }
   ],
   "source": [
    "print rss_all"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "14\n"
     ]
    }
   ],
   "source": [
    "print rss_all.index(min(rss_all))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[<matplotlib.lines.Line2D at 0x29a4fda0>]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAEGCAYAAACevtWaAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAIABJREFUeJzt3Xt4VPW1//H3GhDkoihiUULlkoqKBUErCnrsYH8o9Nef\nWrWtFjylta1HrVVb7YU2J8mTtnp60Fbx0oNagWpbrPWg9oAUK1MfVC5iuAmiQogIIgfxBsh11u+P\nPZBhkpBJMjN7MvN5Pc882TPznT2LkKz5Zu3vxdwdEREpLJGwAxARkcxTchcRKUBK7iIiBUjJXUSk\nACm5i4gUICV3EZEClPPkbmYPmdm7ZrYsjbb/YmaLzWyPmV3awPNHmNl6M7s7O9GKiLRNYfTcHwYu\nTLNtLfAN4NFGnq8C/pmJoERECknOk7u7zwPeT37MzPqb2SwzW2Rm/zSzAYm2b7n7CqDeTCszOwP4\nFPD3XMQtItKW5EvNfTLwPXc/E7gVuP9Qjc3MgInALYBlPzwRkbalfdgBmFkXYATwl0TSBjisiZdd\nB/yPu29MvEQJXkQkSejJneCvh/fd/fRmvGY4cK6ZXQccARxmZh+7+4SsRCgi0sY0WZYxs45mtsDM\nqs1suZmVN9IummizwszmNnXaxA13/xioMbPLk841uJHXkHjNOHfv6+79CUoz05TYRUTqNJnc3X0X\nMNLdhwJDgDFmNiy5jZl1A+4FvuTunwW+0tj5zOyPwIvAADN7y8y+CYwFrjazJWa2Argo0fZzZrYe\nuBz4nZktb9G/UkSkyFhzlvw1s87A88C17r4o6fFrgePd/d8zH6KIiDRXWqNlzCxiZtXAJmBOcmJP\nGAB0N7O5ieGMV2U6UBERSV9aF1TdPQ4MNbMjgRlmNtDdV6ac53TgfKAL8JKZveTub2Y8YhERaVKz\nRsu4+0eJi6WjgeTk/jawxd13AjvN7HngNOCg5G5m2vZJRKQF3L1ZQ77TGS3TI3HBFDPrBIwCXktp\n9iTB0MR2ibr8WcCqRgLM+1t5eXnoMShOxdlWY1Scmb+1RDo99+OBqWYWIfgwmO7uM83smiBX+2R3\nf83MZgPLgH3AZD+4bCMiIjnUZHJ39+UE9fTUx/8r5f5EgiUBREQkZPmytkxeiUajYYeQFsWZWW0h\nzrYQIyjOfNCsce6tfjMzz+X7iYgUAjPDM31BVURE2p58WDisRWpqaikrm8KGDXFKSiJUVY2nX78+\nYYclIpIX2mRZpqamllGjJrFmTSXBnKntlJaWM2fODUrwIlJwiqYsU1Y2JSmxA3RhzZpKysqmhBiV\niEj+aJPJfcOGOHWJfb8ubNwYDyMcEZG80yaTe0lJBNie8uh2evVqk/8cEZGMa5PZsKpqPKWl5dQl\n+KDmXlU1PrSYRETySZu8oAp1o2VmzYpz6qkRpk7VaBkRKUwtuaDaZpP7fr/8Jbz/PkzUwgciUqCK\nZrRMsuHD4aWXwo5CRCS/tPme+7Zt0LMnbN0KHTtm9NQiInmhKHvuXbvCgAFQXR12JCIi+aPNJ3dQ\naUZEJFXBJPcXXww7ChGR/JHONnsdzWyBmVWb2XIzK2+gzefN7AMzeyVx+3l2wm3YiBHquYuIJEtn\nJ6ZdZjbS3XeYWTvgBTOb5e4LU5o+7+4XZSfMQ+vfH3bvhvXr4dOfDiMCEZH8klZZxt13JA47Enwg\nNDTkpVlXcjPJTKUZEZFkaSV3M4uYWTWwCZjj7osaaDbczJaY2f+Y2cCMRpkGlWZEROqktVmHu8eB\noWZ2JDDDzAa6+8qkJouBExKlmzHADGBAQ+eqqKg4cByNRjO2h+Hw4XDrrRk5lYhIqGKxGLFYrFXn\naPYkJjMrA7a7+52HaFMDnOHuW1Mez9oeqjt2wLHHwpYt0KlTVt5CRCQUWZnEZGY9zKxb4rgTMAp4\nLaVNz6TjYQQfGgcl9mzr3BkGDoTFi3P5riIi+SmdsszxwFQzixB8GEx395lmdg3g7j4ZuNzMrgX2\nAJ8AX8taxIewfzLTueeG8e4iIvmjza8tk+xPf4K//AWeeCJrbyEiknNFubZMshEjguGQOfy8EhHJ\nSwWV3E84ASIRWLcu7EhERMJVUMl9/2QmjXcXkWJXUMkdNFNVRAQKMLlrpqqISIGNlgHYuROOOQY2\nb4YuXbL6ViIiOVH0o2UADj8cBg2Cl18OOxIRkfAUXHKHuiGRIiLFqiCTu0bMiEixK7iaO8Dbb8PQ\noUHd3UJbZV5EJDNUc0/o3TtYGfLNN8OOREQkHAWZ3EGlGREpbkruIiIFqGCTu0bMiEgxK8gLqgC7\nd0P37vDOO3DEETl5SxGRrNAF1SQdOsCQIbBwYdiRiIjkXjrb7HU0swVmVm1my82s/BBtzzSzPWZ2\naWbDbBnV3UWkWDWZ3N19FzDS3YcCQ4AxiX1SD5LYhu92YHbGo2wh1d1FpFilVZZx9x2Jw44E+642\nVDi/AXgc2JyZ0Fpv+HCYPx/i8bAjERHJrbSSu5lFzKwa2ATMcfdFKc/3Ai5x9/uBvJkTetxx0K0b\nvP562JGIiORW+3QauXscGGpmRwIzzGygu69MavJb4MdJ9xtN8BUVFQeOo9Eo0Wi0OfE22/7SzMkn\nZ/VtREQyJhaLEYvFWnWOZg+FNLMyYLu735n02Nr9h0APYDvwXXd/KuW1ORsKud8998DSpfDAAzl9\nWxGRjMnKUEgz62Fm3RLHnYBRwGvJbdy9f+LWj6Dufl1qYg+LRsyISDFKpyxzPDA1MRomAkx395lm\ndg3g7j45pX1uu+ZNGDwYamvhgw/gqKPCjkZEJDcKdoZqsmgUfvpTuPDCnL+1iEiraYZqI1SaEZFi\nUxTJfcQIJXcRKS5FUZb53/+FE0+ErVshUhQfZyJSSFSWacSxxwa3lSubbisiUgiKIrmD6u4iUlyK\nJrlrETERKSZFk9zVcxeRYlIUF1QB9u2Do4+Gmho45phQQhARaRFdUD2Edu1g2LBgCWARkUJXNMkd\nVJoRkeKh5C4iUoCKpuYOwSSmvn2Dr+3TWsleRCR8qrk3oXt3KCmBFSvCjkREJLuKKrmDSjMiUhyK\nLrlrETERKQZFl9yHD9dMVREpfOlss9fRzBaYWbWZLTez8gbaXGRmSxNtFprZOdkJt/VOOQW2bIHN\nm8OOREQke5pM7u6+Cxjp7kOBIcAYMxuW0uxZdz8t0eZq4MHMh5oZkQicfbYmM4lIYUurLOPuOxKH\nHQn2XfVGngfoCsQzEl2WqDQjIoUureRuZhEzqwY2AXPcfVEDbS4xs1XA08C3MhtmZmnEjIgUurSm\n8rh7HBhqZkcCM8xsoLuvTGkzI/HcucAvgFENnauiouLAcTQaJRqNtizyVjjrLFi8GPbsgcMOy/nb\ni4gcUiwWIxaLteoczZ6hamZlwHZ3v/MQbdYAZ7r71pTHQ52hmmzQIJgyBc44I+xIREQOLSszVM2s\nh5l1Sxx3IuiRv5bSpjTp+HSgQ2pizzequ4tIIUun5n48MNfMlgALgNnuPtPMrjGz7ybaXGZmK8zs\nFWAS8NUsxZsxqruLSCErqoXDkq1eDaNHB5t3iIjkMy0c1gwDBsBHH8E774QdiYhI5hVtcjcLJjOp\nNCMihahokztoETERKVxFndw1YkZEClXRXlAF2LYNevaE99+HDh3CjkZEpGG6oNpMXbsGF1arq8OO\nREQks4o6uYNKMyJSmJTcNZlJRAqQkruSu4gUoKJP7qWlsGsXrF8fdiQiIplT9MndTL13ESk8RZ/c\nQcldRAqPkjuaqSoihaeoJzHtt2MHHHssvPceHH542NGIiBxMk5haqHNnOOWUYOs9EZFCkM5OTB3N\nbIGZVZvZcjMrb6DN181saeI2z8wGZSfc7FFpRkQKSZPJ3d13ASPdfSgwBBhjZsNSmq0FznP30wg2\nx34g45FmmWaqikghSass4+47EocdgfaApzw/390/TNydD5RkLMIc2T9iJg8vCYiINFtayd3MImZW\nDWwC5rj7okM0/zYwKxPB5VKfPsGY99rasCMREWm9dHvu8URZpjdwlpkNbKidmY0Evgn8OHMh5oYm\nM4lIIWnfnMbu/pGZzQVGAyuTnzOzwcBkYLS7v9/YOSoqKg4cR6NRotFoc0LIqv119yuvDDsSESlm\nsViMWCzWqnM0Oc7dzHoAe9z9QzPrBMwGbnf3mUltTgD+AVzl7vMPca68HOe+3wsvwI03wssvhx2J\niEidloxzT6fnfjww1cwiBGWc6e4+08yuAdzdJwNlQHfgPjMzgg+D1BE1ee+YY2pZsmQK550X54QT\nIlRVjadfvz5hhyUi0myaoZpQU1PLqFGTWLOmEugCbKe0tJw5c25QgheRUGmGaiuUlU1JSuwAXViz\nppKysikhRiUi0jJK7gkbNsSpS+z7dWHjxngY4YiItIqSe0JJSQTYnvLodlavjrBqVRgRiYi0nJJ7\nQlXVeEpLy6lL8Nvp37+c8ePHc955cMMNwaqRIiJtgS6oJqmpqaWsbAobN8bp1atutMyWLVBRAdOn\nw4QJcP310KFD2NGKSLFoyQVVJfdmWLkSfvhDWLMG/vM/4aKLgpmtIiLZpOSeI888EyT5446DO++E\n004LOyIRKWQaCpkjo0fD0qVw2WVwwQXwne/Apk1hRyUiUkfJvYXat4frroPVq+HII+Gzn4XbboOd\nO8OOTEREyb3VjjoK7rgjWE1y4cJgu77HHtO68CISLtXcM2zuXLj5ZujaFX7zG+jRIxiBs2FDnJIS\nrVcjIs2nC6p5Yt8+mDIFfvrTWj75ZBLbtmm9GhFpOV1QzRPt2sHVV8PIkVOSEjtovRoRyRUl9yza\nvFnr1YhIOJTcs6ix9Wp69dK3XUSySzX3LGpojfgjjyxnyRLV3EUkfVm5oGpmHYHngQ4EOzc97u6V\nKW1OAh4GTgcmuPudjZyrqJI7HLxeTY8eEV56aTx33dWHSy8NOzIRaSuyNlrGzDq7+w4zawe8AHzf\n3RcmPd8D6ANcAryv5N64BQuCNWkWLoQ+6ryLSBqyNlrG3XckDjsS9N495fkt7r4Y2NucNy9GZ50V\nrEszdizs1XdLRLIkreRuZhEzqwY2AXPcfVF2wypst9wCXbpAZWXTbUVEWiLdnnvc3YcCvYGzzGxg\ndsMqbJEITJ0KDz0UzGgVEcm09s1p7O4fmdlcYDSwsiVvWFFRceA4Go0SjUZbcpo277jjglmsV10F\n1dVw7LFhRyQi+SIWixGLxVp1jnRGy/QA9rj7h2bWCZgN3O7uMxtoWw5sc/c7GjlX0V9QTfXjH8Or\nr8LTT2vjDxFpWLaGQg4CphKUcCLAdHf/pZldA7i7TzaznsDLwBFAHNgGDHT3bSnnUnJPsWcPnHsu\nXHkl3HRT2NGISD7SwmFt1Nq1wSiaZ56BM84IOxoRyTdaOKyN6t8f7rkHrrgCPv447GhEpBCo555H\nvv1t2L0bpk0LOxIRySfqubdxd90FixbBH/4QdiQi0tap555nli2DL3wBXngBBgwIOxoRyQfquReA\nwYODmatXXAG7doUdjYi0Veq55yF3uOyyYGGx3/wm7GhEJGwaCllAtm6FoUPh3nvhS18KOxoRCZOS\ne4GZNw8uvxwWL4aSkrCjEZGwqOZeYM49F66/HsaNg337wo5GRNoSJfc8N2FC8PW228KNQ0TaFpVl\n2oANG4JlCR5/POjNi0hxUVmmQJWUwIMPBrs3bd0adjQi0hao596G3HQTvPUW/PWvWh5YpJhotEyB\n27ULhg+HL3+5ltWrp7BhQ5ySkghVVePp10+7bYsUKiX3IvCPf9RywQWTiMcrgS7AdkpLy5kz5wYl\neJECpZp7EXj44SlJiR2gC2vWVFJWNiXEqEQk3zSZ3M2so5ktMLNqM1ue2EqvoXZ3m9kbZrbEzIZk\nPlQB2LAhTl1i368LGzfGwwhHRPJUk8nd3XcBI919KDAEGGNmw5LbmNkYoNTdTwSuAX6XjWAFSkoi\nwPaUR7fTq5f+CBOROmllBHffkTjsCLQHUgvnFwPTEm0XAN0S+6pKhlVVjae0tJy6BL+ddu3K+drX\nxocXlIjknfbpNDKzCLAYKAXudfdFKU1KgPVJ9zckHns3E0FKnX79+jBnzg2UlU1k48Y4vXpFOOec\nG7j66j5MmQJf/GLYEYpIPkgrubt7HBhqZkcCM8xsoLuvbMkbVlRUHDiORqNEo9GWnKao9evXh0ce\nOfjSx9Ch8OUvQ3k5/Nu/hRSYiGRELBYjFou16hzNHgppZmXAdne/M+mx3wFz3X164v5rwOfd/d2U\n12ooZBatWQNjxsCll8KvfgURleFFCkJWhkKaWQ8z65Y47gSMAl5LafYU8K+JNmcDH6Qmdsm+0lJ4\n8cVgqeCxY2HnzrAjEpGwpNO3Ox6Ya2ZLgAXAbHefaWbXmNl3Adx9JlBjZm8C/wVcl7WI5ZB69IBn\nnw2WCB41Ct57L+yIRCQMmqFaoOJx+MlP4MknYdYs6N8/7IhEpKU0Q1UOiETg17+GG28MlgleuDDs\niEQkl5TcC9x118HkycE+rDNmhB2NiOSKknsR+NKXYObMYMu+u+4KOxoRyQXV3IvIunXBJKcLL4SJ\nE6Fdu7AjEpF0aMlfadL77wfj4I8+Gh55BDp3DjsiEWmKLqhKk44+Gp55Brp0gfPPh82bw45IRLJB\nyb0IdewI06YF4+BHjIDXXw87IhHJtLTWlpHCYwZVVdC3L5x3HkyaVMuTT2rrPpFCoZq7MHVqLd/6\nlrbuE8lXqrlLi8yZo637RAqNkrto6z6RAqTkLo1u3dehg348RNoq/fZKg1v39exZzsKF47nnHtBl\nEpG2RxdUBYCamlrKyqYc2Lqvqmo88XgfLrsMTjkFHngAunYNO0qR4qQZqpJxn3wC3/sevPQS/PWv\nQaIXkdzSaBnJuE6d4KGH4JZbgvHwf/pT2BGJSDqa7LmbWW9gGtATiAMPuPvdKW2OAn4PlAKfAN9q\naANt9dzbtiVL4PLLYfRouOOOYKariGRftnrue4EfuPupwHDgejM7OaXNBKDa3U8DvgHcjRScIUNg\n8WLYsCHoxdfWhh2RiDSmyeTu7pvcfUnieBuwCihJaTYQeC7RZjXQ18yOzXCskge6dYMnnoCvfAXO\nOitYhExE8k+zau5m1hcYQrBRdrKlwKWJNsOAE4DerQ9P8pFZUIN/7DG4+mooLw825BaR/JH2wmFm\n1hV4HLgx0YNPdjtwl5m9AiwHqoEGf90rKioOHEejUaLRaPMilrxx3nlBmebKK2HMGHj0UThWf6+J\ntFosFiMWi7XqHGkNhTSz9sDfgFnu3uRGbWZWAwxK/RDQBdXCtHcvlJUFyX36dBg+POyIRApLNodC\n/h5Y2VhiN7NuZnZY4vg7wD8b6N1LgWrfHm67De65By6+GO6+W7NaRcKWzlDIc4DnCcotnrhNAPoA\n7u6TzexsYCrBUMlXgavd/cMGzqWee4FbuzYYLnniifDzn9fyH/+R2TXi98+k1brzUkw0Q1Xyws6d\nMH58LU88MYk9ezK3RnxNTS2jRk1izRqtOy/FRcld8sa4cZU8+ugtHLyU8Ha6dZtIr17lxOMQjwfl\nm/3HybeGHt+2rZI9e+qf88ILJzJjRjmHH57bf6NIrrQkuWubPcmKxtaIHzAgzpQpEInU3cwOvt/Y\nYxdfHGfevPrnnDcvTvfuQSnojDPg9NODr6edBp075+bfK5JvlNwlK+rWiD+4lz1gQISBA1t2zj59\nIsybV/+cl1wS4cEHYfnyYGjmK6/Aww/DqlXQv39dsj/99GCW7RFHHHxe1fGlEKksI1mRjfp4c8+5\nezesWBEk+/1Jf8UK+PSn65J9r161/Oxnk6ipUR1f8pdq7pJXGlojPlOjZVp6zj17gh79/oT/5z9X\nsmVL/Tr+2LETeeSR8lbFKpIpSu4izTRyZDmxWGW9x6PRcubOrf+4SBi0nrtIMzW2f2x1dYSnn9Zk\nLGm7lNylqDW0f2xpaTm//vV4JkyAc8+F558PMUCRFlJZRopeY3X8ffuCnaf+/d/hpJPgV7+CoUPD\njlaKkWruIlmwe3ewQfgvfgGf/zxUVQVj6kVyRTV3kSzo0AGuvx7efBMGD4YRI+C734W33w47MpHG\nKbmLpKlLF5gwAVavhu7dgxmwt94K770XdmQi9Sm5izRT9+5w++3BjNht24J6fFVVcCySL5TcRVqo\nVy+4/36YPz+YGHXiicFa9rt2BRdpx42rZOTIcsaNq6SmRruJS27pgqpIhixdCj/7GVRX17J37yQ2\nb9aSBpIZGi0jkgcuuKCSOXPqL2lw0UUT+e//Lieiv5elmbKy5K+Z9QamAT0Jdlp6wN3vTmlzJPAI\ncALQDrjD3ac0JxCRQrFnT8PLHc+eHeeII2DAADjllOA2cGDw9TOfCUblNEYrV0pzpbPk717gB+6+\nxMy6AovN7O/u/lpSm+uBV939IjPrAaw2s0fcfW82ghbJZ40td3z55RHuvx9eey2o0a9aBdOmBV/f\negv69q1L9vtvJ58MmzfXXw1z/nyVeeTQml2WMbMZwCR3/0fSYz8Berv798ysHzDb3Qc08FqVZaTg\ntWS541274I03YOXKusS/ahW8/jq0a1fJ9u1aubKYZb3mbmZ9gRjwWXfflvR4V+Ap4GSgK/A1d5/V\nwOuV3KUoZGq543374JxzylmwoP4KlV27lnPllZUH1qYfNAhtNVigsrrNXiKBPw7cmJzYEy4Eqt39\nfDMrBeaY2eAG2lFRUXHgOBqNEo1GmxOvSJvQr1+fjPSq27WDz3wmwoIF9cs8I0ZEGDw4GIp5331B\nz/+kkw7eanDwYOjUqeFzZ6OOr2sDmRGLxYjFYq07ibs3eSP4EHiGILE39PzfgHOS7v8D+FwD7VxE\nmmft2nVeWvpDh20eLEK8zUtLf+hr1647qN2OHe7z57vfd5/71Ve7Dxni3qmT+6BB7uPHu0+a5P7i\ni+7bt6d/zmzEKc2XyJ1p5ev9t7TKMmY2Ddji7j9o5Pl7gc3uXmlmPYGXgdPcfWtKO0/n/UTkYC0t\n8+zcGWwtuHhx3W3VKujQoZIPP6xfxz///In86EfluEM8XndLvt/Yc/fdV8n8+bo2kA3ZGgp5DjAW\nWG5m1YADE4A+BJ8mk4FfAFPMbFniZT9KTewi0nItLfMcfjh87nPBbb/du2HEiDiLF9cfrlldHeeO\nOyASqbuZpXe/pqbhIaC1tfFmxy2t12Ryd/cXCMauH6rNOwR1dxHJcx06wMknR1i8uH4d/4tfjPDI\nIy0777hxER59tP45FyyIcO218P3vB8M7JTc0V06kCDW2A1VV1fiMn3PevPH07AkjR8KYMTB7trYv\nzAUtPyBSpDI1XDPdc+7cGexs9dvfwp49cNNNMG4cdO7c+n9LodPaMiKS99xh7twgyc+fD9/5Dlx3\nHZSUhB1Z/tJOTCKS98zg/PPhqafghRfg44+DCVhjx8KiRWFHVzjUcxeR0H3wATz0EEyaFPTgb74Z\nLrkE2rfXxChQWUZE2ri9e2HGjKBks349fP3rtUyfPomamuJeG1/JXUQKxqJF8NWvVrJunSZGZXVt\nGRGRXDrzTOjbN866dfUnRj39dJyrroLS0oNvn/pUUNNvSjGUepTcRSRvNbY2/rBhEb7wBVizBmbN\nCr6uWRMMt+zfv37S798f+vSBww5reEnmQlwfX2UZEclbzV0b/8MPgyS/dm1dwt9/e+ed4GLtJ59U\nsmlT2yr1qOYuIgUnU5Otdu+GdevgK18pZ9my+uvjH3NMOTffXHlgLZ5jjml97JmimruIFJxMrY3f\noUOwf+2gQRGWLatf6jnllAgffAC33QavvAI9egR1/zPPDJL9GWfAEUc0fv58q+Or5y4iRSWdUk88\nDqtXw8svB6N2Xn4Zli6FE044OOEPGRJshtKSrRWbQ2UZEZE0tKTUs2cPvPrqwQl/1argr4Ft2ypZ\nsyZ7dXwldxGRHNq5E5Ytg3Hjynnjjfp1/JEjy3nuufqPN1dW1pYxs95m9pyZvWpmy83s+w20ucXM\nqs3slUSbvWZ2VHMCERFpaw4/HIYNg2HD9g/ZTLadXr3CW74rnXfeC/zA3U8FhgPXm9nJyQ3cfaK7\nD3X304GfAjF3/yDz4eZGqzemzRHFmVltIc62ECMUX5zZWB+/tZpM7u6+yd2XJI63AauAQy3OeSXw\np8yEF45i+8HMNsWZOW0hRii+OPv168OcOTcwduxERo4sZ+zYiaFPimrWUEgz6wsMARY08nwnYDRw\nfWsDExFpSzI1ZDNT0i4ImVlX4HHgxkQPviH/D5jXlksyIiKFIK3RMmbWHvgbMMvd7zpEuyeAx9z9\nz408r6EyIiItkJWhkGY2Ddji7j84RJtuwFqgt7t/0pwgREQks5qsuZvZOcBYYLmZVQMOTAD6AO7u\nkxNNLwFmK7GLiIQvp5OYREQkN3I2wt7MRpvZa2b2upn9OFfv2xzpTNjKF2YWSUwaeyrsWBpjZt3M\n7C9mtirxPT0r7JgaYmY3m9kKM1tmZo+aWYewYwIws4fM7F0zW5b02NFm9nczW21msxPl0FA1Euev\nE//vS8zsr2Z2ZJgxJmKqF2fScz80s7iZdQ8jtpRYGozTzG5IfE+Xm9ntTZ0nJ8ndzCLAPcCFwKnA\nlakTofJEkxO28siNwMqwg2jCXcBMdz8FOI1gjkReMbNewA3A6e4+mKBUeUW4UR3wMMHvTLKfAM+6\n+0nAcwSTBsPWUJx/B0519yHAG+RvnJhZb2AUUJvziBpWL04zixKMRhzk7oOAiU2dJFc992HAG+5e\n6+57gD8DF+fovdPWgglboUj8MH4ReDDsWBqT6Kn9i7s/DODue939o5DDakw7oEtiVFhnYGPI8QDg\n7vOA91MevhiYmjieSnCtK1QNxenuz7p7PHF3PtA754GlaOT7CfAb4NYch9OoRuK8Frjd3fcm2mxp\n6jy5Su4lwPqk+2+Th0kzWVMTtkK2/4cxny+Y9AO2mNnDifLR5MQkt7zi7huBO4C3gA3AB+7+bLhR\nHdKn3P1dCDojwKdCjicd3wJmhR1EQ8zsImC9uy8PO5YmDADOM7P5ZjbXzD7X1AvCW9Umj6U5YSsU\nZvZ/gXdwb28bAAACC0lEQVQTf2FY4paP2gOnA/cm1hzaQVBSyCuJBe4uJhj91QvoamZfDzeqZsnn\nD3jM7GfAHnf/Y9ixpEp0NiYAydNK8/n36Wh3Pxv4EfBYUy/IVXLfAJyQdL934rG8k/jT/HHgD+7+\nZNjxNOAc4CIzW0uwhs/IxDyEfPM2QY/o5cT9xwmSfb75P8Bad9/q7vuAJ4ARIcd0KO+aWU8AMzsO\n2BxyPI0ys/EE5cN8/bAsBfoCS82shiAvLTazfPxraD3BzybuvgiIm9khNwLMVXJfBHzGzPokRiJc\nAeTrKI/fAysPNRM3TO4+wd1PcPf+BN/H59z9X8OOK1WidLDezAYkHvoC+XkB+C3gbDM73MyMIM58\nuvCb+tfZU8D4xPE3gHzpgBwUp5mNJigdXuTuu0KLqr4Dcbr7Cnc/zt37u3s/gg7JUHfPhw/M1P/3\nGcD5AInfqcPc/b1DnSAnyT3RI/oewRX0V4E/u3s+/QIBB03YOj9pffrRYcfVhn0feNTMlhCMlvlV\nyPHU4+4LCf6qqAaWEvxCTT7ki3LEzP4IvAgMMLO3zOybwO3AKDNbTfBB1OSQuGxrJM5JQFdgTuL3\n6L5Qg6TROJM5eVCWaSTO3wP9zWw58EegyQ6dJjGJiBQgXVAVESlASu4iIgVIyV1EpAApuYuIFCAl\ndxGRAqTkLiJSgJTcRUQKkJK7iEgB+v/13brqd1h0IwAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x29841e80>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline\n",
    "\n",
    "kvals = range(1, 16)\n",
    "plt.plot(kvals, rss_all,'bo-')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "***QUIZ QUESTION ***\n",
    "\n",
    "What is the RSS on the TEST data using the value of k found above?  To be clear, sum over all houses in the TEST set."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1.33006256366e+14\n"
     ]
    }
   ],
   "source": [
    "predict_value = compute_distances_k_all(14, features_train, output_train, features_test)\n",
    "residual = (output_test - predict_value)\n",
    "rss = sum(residual**2)\n",
    "print rss"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "### Quiz\n",
    "\n",
    "<img src=\"quiz-w6-A-1,2.png\">\n",
    "\n",
    "<img src=\"quiz-w6-A-3,4.png\">\n",
    "\n",
    "<img src=\"quiz-w6-A-5,6.png\">\n",
    "\n",
    "<img src=\"quiz-w6-A-7,8.png\">"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}