Triangle Inequality

One interesting aspect about the triangle in Figure 3-1 is that the length of the hypotenuse is always less than the length of each side added up individually (Figure 3-2).

Figure 3-2. Triangle broken into three line segments

Stated mathematically: ∥x + y∥ ≤ ∥x∥ + ∥y∥. This inequality is important for finding a distance function; if the triangle inequality didn’t hold, what would happen is distances would become slightly distorted as you measure distance between points in a Euclidean space.

Geometrical Distance

The most intuitive distance functions are geometrical. Intuitively we can measure how far something is from one point to another. We already know about the Pythagorean theorem, but there are an infinite amount of possibilities that satisfy the triangle inequality.

Stated mathematically we can take the Pythagorean theorem and build what is called the Euclidean distance, which is denoted as:

As you can see, this is similar to the Pythagorean theorem, except it includes a sum. Mathematics gives us even greater ability to build distances by using something called a Minkowski distance (see Figure 3-3):

This p can be any integer and still satisfy the triangle inequality.

Figure 3-3. Minkowski distances as n increases (Source: Wikimedia)

Computational Distances

Imagine you want to measure how far it is from one part of the city to another. One way of doing this would be to utilize coordinates (longitude, latitude) and calculate a Euclidean distance. Let’s say you’re at Saint Edward State Park in Kenmore, WA (47.7329290, -122.2571466) and you want to meet someone at Vivace Espresso on Capitol Hill, Seattle, WA (47.6216650, -122.3213002).

Using the Euclidean distance we would calculate:

This is obviously a small result as it’s in degrees of latitude and longitude. To convert this into miles we would multiply it by 69.055, which yields approximately 8.9 miles (14.32 kilometers). Unfortunately this is way off! The actual distance is 14.2 miles (22.9 kilometers). Why are things so far off?

If I had the ability to lift off from Saint Edward State Park and fly to Vivace then, yes, it’d be shorter, but if I were to walk or drive I’d have to drive around Lake Washington (see Figure 3-4).

This gets us to the motivation behind computational distances. If you were to drive from Saint Edward State Park to Vivace then you’d have to follow the constraints of a road.

Figure 3-4. Driving to Vivace from Saint Edward State Park

def lev(a, b):
  if not a: return len(b)
  if not b: return len(a)
  return min(lev(a[1:], b[1:])+(a[0] != b[0]), lev(a[1:], b)+1, lev(a, b[1:])+1)

Statistical Distances

Last, there’s a third class of distances that I call statistical distances. In statistics we’re taught that to measure volatility or variance, we take pairs of datapoints and measure the squared difference. This gives us an idea of how dispersed the population is. This can actually be used when calculating distance as well, using what is called the Mahalanobis distance.

Imagine for a minute that you want to measure distance in an affluent neighborhood that is right on the water. People love living on the water and the closer you are to it, the higher the home value. But with our distances discussed earlier, whether computational or geometrical, we would have a bad approximation of this particular neighborhood because those distance calculations are primarily spherical in nature (Figures 3-5 and 3-6).

Figure 3-5. Driving from point A to point B on a city block

Figure 3-6. Straight line between A and B

This seems like a bad approach for this neighborhood because it is not spherical in nature. If we were to use Euclidean distances we’d be measuring values of houses not on the beach. If we were to use Manhattan distances we’d only look at houses close by the road.

Mahalanobis distance

Another approach is using the Mahalanobis distance. This takes into consideration some other statistical factors:

$d(x,y)=\sqrt{{\sum }_{i=1}^n\frac{{(x_i-y_i)}^2}{s_i^2}}$

What this effectively does is give more stretch to the grouping of items (Figure 3-7):

Figure 3-7. Mahalanobis distance

Guessing K

Guessing is always a good solution. Many times when we are approaching a problem, we have domain knowledge of it. Whether we are an expert or not, we know about the problem enough to know what a neighborhood is. My neighborhood where I live, for instance, is roughly 12 houses. If I wanted to expand I could set my K to 30 for a more flattened-out approximation.

Heuristics for Picking K

There are three heuristics that can help you determine an optimal K for a KNN algorithm:

1. Use coprime class and K combinations

2. Choose a K that is greater or equal to the number of classes plus one

3. Choose a K that is low enough to avoid noise

Use coprime class and K combinations

Picking coprime numbers of classes and K will ensure fewer ties. Coprime numbers are two numbers that don’t share any common divisors except for 1. So, for instance, 4 and 9 are coprime while 3 and 9 are not. Imagine you have two classes, good and bad. If we were to pick a K of 6, which is even, then we might end up having ties. Graphically it looks like Figure 3-9.

Figure 3-9. Tie with K=6 and two classes

If you picked a K of 5 instead (Figure 3-10), there wouldn’t be a tie.

Figure 3-10. K=5 with two classes and no tie

Choose a K that is greater or equal to the number of classes plus one

Imagine there are three classes: lawful, chaotic, and neutral. A good heuristic is to pick a K of at least 3 because anything less will mean that there is no chance that each class will be represented. To illustrate, Figure 3-11 shows the case of K=2.

Figure 3-11. With K=2 there is no possibility that all three classes will be represented

Note how there are only two classes that get the chance to be used. Again, this is why we need to use at least K=3. But based on what we found in the first heuristic, ties are not a good thing. So, really, instead of K=3, we should use K=4 (as shown in Figure 3-12).

Figure 3-12. With K set greater than the number of classes, there is a chance for all classes to be represented

About the Data

While the data is freely available, it wasn’t easy to put together. I did a bit of cajoling to get the data well formed. There’s a lot of features, ranging from inadequate parking to whether the house has a view of Mount Rainier or not. I felt that while that was an interesting exercise, it’s not really important to discuss here. In addition to the data they gave us, geolocation has been added to all of the datapoints so we can come up with a location distance much easier.

General Strategy

Our general strategy for finding the values of houses in Seattle is to come up with something we’re trying to minimize/maximize so we know how good the model is. Since we will be looking at house values explicitly, we can’t calculate an “Accuracy” rate because every value will be different. So instead we will utilize a different metric called mean absolute error.

With all models, our goal is to minimize or maximize something, and in this case we’re going to minimize the mean absolute error. This is defined as the average of the absolute errors. The reason we’ll use absolute error over any other common metrics (like mean squared error) is that it’s useful. When it comes to house values it’s hard to get intuition around the average squared error, but by using absolute error we can instead say that our model is off by $70,000 or similar on average.

As for unit testing and functional testing, we will approach this in a random fashion by stratifying the data into multiple chunks so that we can sample the mean absolute errors. This is mainly so that we don’t find just one weird case where the mean absolute error was exceptionally low. We will not be talking extensively here about unit testing because this is an early chapter and I feel that it’s more important to focus on the overall testing of the model through mean absolute error.

Coding and Testing Design

The basic design of the code for this chapter is going to center around a Regressor class. This class will take in King County housing data that comes in via a flat, calculate an error rate, and do the regression (Figure 3-13). We will not be doing any unit testing in this chapter but instead will visually test the code using the plot_error function we will build inside of the Regressor class.

Figure 3-13. Overall coding design

For this chapter we will determine success by looking at the nuances of how our regressor works as we increase folds.

KNN Regressor Construction

To construct our KNN regression we will utilize something called a KDTree. It’s not essential that you know how these work but the idea is the KDTree will store data in a easily queriable fashion based on distance. The distance metric we will use is the Euclidean distance since it’s easy to compute and will suit us just fine. You could try many other metrics to see whether the error rate was better or worse.

import random
import sys

import pandas as pd
import numpy as np
from scipy.spatial import KDTree
from sklearn.metrics import mean_absolute_error
import matplotlib.pyplot as plt

sys.setrecursionlimit(10000)

class Regression(object):
  """
  Performs kNN regression
  """

  def __init__(self):
    self.k = 5
    self.metric = np.mean
    self.kdtree = None
    self.houses = None
    self.values = None

  def set_data(self, houses, values):
    """
    Sets houses and values data
    :param houses: pandas.DataFrame with houses parameters
    :param values: pandas.Series with houses values
    """
    self.houses = houses
    self.values = values
    self.kdtree = KDTree(self.houses)

Do note that we had to set the recursion limit higher since KDTree will recurse and throw an error otherwise.

There’s a few things we’re doing here I thought we should discuss. One of them is the idea of normalizing data. This is a great trick to make all of the data similar. Otherwise, what will happen is that we find something close that really shouldn’t be, or the bigger numbered dimensions will skew results.

On top of that we’re only selecting latitude and longitude and SqFtLot, because this is a proof of concept.

class Regression(object):
  # __init__
  # set_data
  def regress(self, query_point):
    """
    Calculates predicted value for house with particular parameters
    :param query_point: pandas.Series with house parameters
    :return: house value
    """
    _, indexes = self.kdtree.query(query_point, self.k)
    value = self.metric(self.values.iloc[indexes])
    if np.isnan(value):
      raise Exception('Unexpected result')
    else:
      return value

Here we are querying the KDTree to find the closest K houses. We then use the metric, in this case mean, to calculate a regression value.

At this point we need to focus on the fact that, although all of this is great, we need some sort of test to make sure our data is working properly.

KNN Testing

Up until this point we’ve written a perfectly reasonable KNN regression tool to tell us house prices in King County. But how well does it actually perform? To do that we use something called cross-validation, which involves the following generalized algorithm:

• Take a training set and split it into two categories: testing and training

• Use the training data to train the model

• Use the testing data to test how well the model performs.

We can do that with the following code:

class RegressionTest(object):
  """
  Take in King County housing data, calculate and
  plot the kNN regression error rate.
  """

  def __init__(self):
    self.houses = None
    self.values = None

  def load_csv_file(self, csv_file, limit=None):
    """
    Loads CSV file with houses data
    :param csv_file: CSV file name
    :param limit: number of rows of file to read
    """
    houses = pd.read_csv(csv_file, nrows=limit)
    self.values = houses['AppraisedValue']
    houses = houses.drop('AppraisedValue', 1)
    houses = (houses - houses.mean()) / (houses.max() - houses.min())
    self.houses = houses
    self.houses = self.houses[['lat', 'long', 'SqFtLot']]

  def tests(self, folds):
    """
    Calculates mean absolute errors for series of tests
    :param folds: how many times split the data
    :return: list of error values
    """
    holdout = 1 / float(folds)
    errors = []
    for _ in range(folds):
      values_regress, values_actual = self.test_regression(holdout)
      errors.append(mean_absolute_error(values_actual, values_regress))

    return errors

  def test_regression(self, holdout):
    """
    Calculates regression for out-of-sample data
    :param holdout: part of the data for testing [0,1]
    :return: tuple(y_regression, values_actual)
    """
    test_rows = random.sample(self.houses.index.tolist(),
                  int(round(len(self.houses) * holdout)))
    train_rows = set(range(len(self.houses))) - set(test_rows)
    df_test = self.houses.ix[test_rows]
    df_train = self.houses.drop(test_rows)

    train_values = self.values.ix[train_rows]
    regression = Regression()
    regression.set_data(houses=df_train, values=train_values)

    values_regr = []
    values_actual = []

    for idx, row in df_test.iterrows():
      values_regr.append(regression.regress(row))
      values_actual.append(self.values[idx])

    return values_regr, values_actual

Folds are generally how many times you wish to split the data. So for instance if we had 3 folds we would hold 2/3 of the data for training and 1/3 for testing and iterate through the problem set 3 times (Figure 3-14).

Figure 3-14. Split data into training and testing

Now these datapoints are interesting, but how well does our model perform? To do that, let’s take a visual approach and write code that utilizes Pandas’ graphics and matplotlib.

class RegressionTest(object):
  # __init__
  # load_csv_file
  # tests
  # test_regression

  def plot_error_rates(self):
    """
    Plots MAE vs #folds
    """
    folds_range = range(2, 11)
    errors_df = pd.DataFrame({'max': 0, 'min': 0}, index=folds_range)
    for folds in folds_range:
      errors = self.tests(folds)
      errors_df['max'][folds] = max(errors)
      errors_df['min'][folds] = min(errors)
    errors_df.plot(title='Mean Absolute Error of KNN over different folds_range')
    plt.xlabel('#folds_range')
    plt.ylabel('MAE')
    plt.show()

We finally run this by running the following script:

def main():
  regression_test = RegressionTest()
  regression_test.load_csv_file('king_county_data_geocoded.csv', 100)
  regression_test.plot_error_rates()


if __name__ == '__main__':
  main()

Running this yields the graph in Figure 3-15.

As you can see, starting with folds of 2 we have a fairly tight absolute deviation of about $77,000 dollars. As we increase the folds and, as a result, reduce the testing sample, that increases to a range of $73,000 to $77,000. For a very simplistic model that contains all information from waterfront property to condos, this actually does quite well!

Figure 3-15. The error rates we achieved. The x-axis is the number of folds, and the y-axis is the absolute error in estimated home price (i.e., how much it’s off by).