Announcements¶

• HW 3 is due Friday (2/17) at 8pm

• Upcoming office hours:

  • Today: Prof McDonald from 4:30-6pm in CCDS 1341
  • Tomorrow: Peer tutor Rohan Anand from 1:30-3pm in CCDS 16th floor

• Read Tan, Steinbach, Karpatne, Kumar Chapter 3.3

Recap¶

Decision trees are a supervised learning approach to classification.

Our task is determining:

• How to measure a 'good' split
  • We have several "impurity" metrics such as Entropy and the Gini coefficient
• What attribute to split on
  • Which gives us the largest information gain?
• The best split set based on a given attribute
  • Is the attribute nominal, ordinal, continuous?
• When to stop splitting
  • Should we fully grow the tree?

Lecture 12: $k$-Nearest Neighbors¶

[This lecture is based on Prof. Crovella's CS 506 lecture notes and Data Science from Scratch by Joel Grus.]

12.1 Parametric vs. Nonparametric Models¶

Today we'll expand our repetoire of classification techniques.

In so doing we'll look at a first example of a new kind of model: nonparametric.

There are many ways to define models (whether supervised or unsupervised).

One key distinction is this: does the model have a fixed number of parameters, or does the number of parameters grow with the training data?

• If the model has a fixed number of parameters, it is called parametric.

• If the number of parameters grows with the data, the model is called nonparametric.

Parametric models have

• the advantage of often being faster to use,
• but the disadvantage of making strong assumptions about the nature of data distributions.

Nonparametric models are

• more flexible,
• but can be computationally intractable for large datasets.

The classic example of a nonparametric classifier is called $k$-Nearest Neighbors.

12.2 $k$-Nearest Neighbors¶

When I see a bird that walks like a duck and swims like a duck and quacks like a duck, I call that bird a duck.

--James Whitcomb Riley (1849 - 1916)

Like any classifier, $k$-Nearest Neighbors is trained by providing it a set of labeled data.

However, at training time, the classifier does very little. It just stores away the training data.

The idea of the $k$-Nearest Neighbors classifier is that, at test time, it simply "looks at" the $k$ points in the training set that are nearest to the test input $x$, and makes a decision based on the labels on those points.

By "nearest" we usually mean in Euclidean distance.

Note that $k$-Nearest Neighbors can do either hard or soft classification.

As a hard classifier, it returns the majority vote of the labels on the $k$ Nearest Neighbors.

Which may be indeterminate, as above.

It is also reasonable to weight the votes of neighborhood points according to their distance from $x$.

As a soft classifier it returns:

Model Selection for $k$-NN¶

Each value of $k$ results in a different model.

The complexity of the resulting model is therefore controlled by the hyperparameter $k$.

Hence we will want to select $k$ using held-out data to avoid overfitting.

Consider this dataset where items fall into three classes:

Let's observe how the complexity of the resulting model changes as we vary $k$.

We'll do this by plotting the decision regions. These show how the method would classify each potential test point in the space.

Notice how increasing $k$ results in smoother decision boundaries.

These are more likely to show good generalization ability.

Challenges for $k$-NN¶

Working with a $k$-NN classifier can involve some challenges.

1. First and foremost, the computational cost of classification grows with the size of the training data. (Why?) While certain data structures may help, essentially the classification time grows linearly with the data set size.

   Note the tradeoff here: the training step is trivial, but the classification step can be prohibitively expensive.

2. Second, since Euclidean distance is the most common distance function used, data scaling is important.

   As previously discussed, features should be scaled to prevent distance measures from being dominated by a small subset of features.

3. Third concerns the curse of dimensionality.

   If training data lives in a high dimensional space, Euclidean distance measures become less effective.

   This is subtle but important, so we will now look at the curse of dimensionality more closely.

12.3 The Curse of Dimensionality¶

The Curse of Dimensionality is a somewhat tongue-in-cheek term for serious problems that arise when we use geometric algorithms in high dimensions.

There are various aspects of the Curse that affect $k$-NN.

1. Points are far apart in high dimension.

$k$-NN relies on there being one or more "close" points to the test point $x$.

In other words, we need the training data to be relatively dense, so there are "close" points everywhere.

Unfortunately, the amount of space we work in grows exponentially with the dimension $d$.

So the amount of data we need to maintain a given density also grows exponentially with dimension $d$.

Hence, points in high-dimensional spaces tend not to be close to one another at all.

One very intuitive way to think about it is this:

In order for two points to be close in $R^d$, they must be close in each of the $d$ dimensions.

As the number of dimensions grows, it becomes harder and harder for a pair of points to be close in each dimension.

2. Points tend to all be at similar distances in high dimension.

This one is a little harder to visualize. We'll use formulas instead to guide us.

Let's say points are uniformly distributed in space, so that the number of points in a region is proportional to the region's volume.

How does volume relate to distance as dimension $d$ grows?

Consider you are at some point in space (say, the test point $x$), and you want to know how many points are within a unit distance from you.

This is proportional to the volume of a hypersphere with radius 1.

Now, the volume of a hypersphere is $k_d{r}^d$.

For each $d$ there is a different $k_d$.

• For $d=2$, $k_d$ is $4\pi$, and
• for $d=3$, $k_d$ is 4/3 $\pi$,
• etc.

Let's also ask how many points are within a slightly smaller distance, let's say 0.99.

The new distance can be thought of as $1-ϵ$ for some small $ϵ$.

The number of points then of course is proprtional to $k_d(1-ϵ{)}^d$

Now, what is the fraction $f_d$ of all the points that are within a unit distance, but not within a distance of 0.99?

(That is, not within the the hypersphere with radius $1-ϵ$)?

This is $$f_d=\frac{k_d{1}^d-k_d(1-ϵ{)}^d}{k^d{1}^d}$$

Now, $(1-ϵ{)}^d$ goes to 0 as $d\to \infty$.

So, $f_d$ goes to 1 as $d\to \infty$.

Which means: in the limit of high $d$, all of the points that are within 1 unit of our location, are almost exactly 1 unit from our location!

Let's demonstrate this effect in practice.

What we will do is create 100 points, scattered at random within a $d$-dimensional space.

We will look at two quantities:

• The minimum distance between any two points, and
• The average distance between any two points.

as we vary $d$.

The average distance between points grows, but it seems that the minimum distance between points grows about as fast.

So the ratio of the minimum distance to the average distance grows as well!

Let's look at that ratio:

This shows that, for any test point $x$, the distance to the closest point to $x$, relatively speaking, gets closer and closer to the average distance between points.

Of course, if we used a point at the average distance for classifying $x$, we'd get a very poor classifier.

Implications of the Curse.

For $k$-means, the Curse of Dimensionality means that in high dimension, most points are nearly the same distance from the test point.

This makes $k$-means ineffective: it cannot reliably tell which are the $k$ nearest neighbors, and its performance degrades.

What Can be Done?

The problem is that you simply cannot have enough data to do a good job using $k$-NN in high dimensions.

If you must use $k$-NN for your task, the only option may be to reduce the dimension of your data.

Thankfully, this can often be done at little cost in accuracy using SVD! We can form a rank-$r$ approximation to the data and perform $k$-NN in a lower-dimensional space.

12.4 Comparing Classification Methods on Synthetic Data¶

Next we'll look at two classification methods in practice:

• Decision Trees, and
• k-Nearest Neighbors.

To compare these methods, the question arises:

How do we evaluate a classifier?

In the simple case of a binary classifier, we can call one class the 'Positive' class and one the 'Negative' class.

The most basic measure of success for a classifer is accuracy: what fraction of test points are correctly classified?

Of course, accuracy is important, but it can be too simplistic at times.

For example, let's say we have a dataset showing class imbalance: for example 90% of the data are the Positive class and 10% are the Negative class.

For this dataset, consider a classifier that always predicts 'Positive'. Its accuracy is 90%, but it is a very 'stupid' classifier! (ie, it could be one line of code: print(Positive)!)

A better way to measure the classifier's performance is using a Confusion Matrix:

Diagonal elements represent successes, and off diagonals represent errors.

Using the confusion matrix we can define some more useful measures:

• Recall - defined as the fraction of actual positives correctly classified:
  • TP/(TP + FN)
• Precision - defined as the fraction of classified positives correctly classified:
  • TP/(TP + FP)

Evaluating $k$- Nearest Neighbors¶

First we'll generate some synthetic data to work with.

Here is what the data looks like:

Recall that we always want to test on data separate from our training data.

For now, we will something very simple: take the first 50 examples for training and hold out the rest for testing. (Later we will do this a better way.)

For our first example, we will classify the points (in the two classes) using a k-nn classifier.

We will specify that $k=5$, i.e., we will classify based on the majority vote of the 5 nearest neighbors.

In the context of supervised learning, the scikit-learn fit() function corresponds to training and the predict() function corresponds to testing.

Accuracy of 72% sounds good -- but let's dig deeper.

We'll call the red points the Positive class and the green points the Negative class.

Here is the confusion matrix:

Looks like the classifier is getting all of the Negative class correct, but only achieving accuracy of 50% on the Positive class.

That is, its precision is 100%, but its recall is only 50%.

Let's visualize the results.

Indeed, the Positive (red) points in the upper half of the test data are all classified incorrectly.

Let's look at one of the points that the classifier got wrong:

For comparison purposes, let's try $k$ = 3.

And let's look at the same individual point as before:

So how confident can we be that the test accuracy is 92% in general?

What we really need to do is consider many different train/test splits.

Thus, the proper way to evaluate generalization ability (accuracy on the test data) is:

1. Form a random train/test split
2. Train the classifier on the training split
3. Test the classifier on the testing split
4. Accumulate statistics
5. Repeat from 1. until enough statistics have been collected.

Based on the generalization error -- ie, accuracy on test (held-out) data -- it looks like $k=2$ is the best choice.

Here is the decision boundary for $k$-NN with $k=2$.