k-Nearest Neighbors

\(k\)-Nearest Neighbors#

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.

Parametric vs. Nonparametric Models#

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

However a 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.

\(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.

_images/7e1a3c1561d426d05681d84e4a9ecfd77b90958ac6db5bc067a5f55cd90f6981.png

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.

_images/af47e9602b7964b34a599fc8d8042d814bb962af653fd58c769c4e5bc9498a65.png

_images/deb333da0dfbc23af3eb83d2ea2dd3a3d25afbc40b07aedb6fc2a79346ecbfc1.png

_images/86f0da6589c6af5e50fc17b31f07f2e8537bcbb0b85ac34f269c77800e5e1bbe.png

_images/6c06e4be33f20b26df67c3f8a2256d89948ef1c18015d046dc54d004a7ac196c.png

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:

\[ p(x = c\,|\,\mathbf{x}, k) = \frac{\text{number of points in neighborhood with label } c}{k} \]

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:

_images/cafb6a02ec859bdbc40e6a34d050d4899fd22902b4d3b63e6d0db3d713ff37bb.png

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.

_images/f9fb5536589de32c89b869c928153c54215e86eb9d0f11052594109822ef5c0b.png

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.

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.

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.

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.

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 \(\mathbb{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 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.

_images/cedb9f720b21a65f3356fe6bc4609fd181c0fa1fc700694687c48ddb6188ff69.png

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 - \epsilon\) for some small \(\epsilon\).

The number of points then of course is proprtional to \(k_d (1-\epsilon)^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-\epsilon\))?

This is

\[ f_d = \frac{k_d 1^d - k_d (1-\epsilon)^d}{k^d 1^d} \]

_images/9faf73e7f18be607c6a19f22fdac8083a17e0cb85b4371aab2efd2a51b0c71d4.png

Now, \((1-\epsilon)^d\) goes to 0 as \(d \rightarrow \infty\).

So, \(f_d\) goes to 1 as \(d \rightarrow \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!

_images/5f70b5adda7c3744ec3db89b94296226b684d901eb4f1e7aea3d3a33a7d7aa23.png

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\).

_images/2bf966779ba45781acef2c7253ee6a33c56d2576a518f8b31913e826604627e1.png

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:

_images/2e1d6b28a69df720fbf886ca0bfe679b86a85865f36118fd21c72f12e9bb07fb.png

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.

Surprisingly, this can often be done at little cost in accuracy.

We will discuss dimensionality reduction techniques at length later in the course.

In Practice#

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 and Decision Trees#

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

X, y = datasets.make_circles(noise=.1, factor=.5, random_state=1)
print('Shape of data: {}'.format(X.shape))
print('Unique labels: {}'.format(np.unique(y)))

Shape of data: (100, 2)
Unique labels: [0 1]

Here is what the data looks like:

_images/037db81e67dccaa672c2de750cd5694b6f463d99e4035f9301f19c70c3b0a702.png

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 the rest for testing. (Later we will do this a better way.)

X_train = X[:50]
y_train = y[:50]
X_test = X[50:]
y_test = y[50:]

_images/f54571f5ed3be4ce4fc3db66fdc06088dd23581dc8122b33f50d6279e984985b.png

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.

k = 5
knn5 = KNeighborsClassifier(n_neighbors = k)    

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

knn5.fit(X_train,y_train)
print(f'Accuracy on test data: {knn5.score(X_test, y_test)}')

Accuracy on test data: 0.72

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:

	Predicted +	Predicted -
Actual +	14	14
Actual -	0	22

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.

_images/48a46cc694669d9738b5db1ca59a7714f514b53bcd3a73a2a983fd54a9bc6319.png

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:

_images/36dc80526e94072f5a7b83e9cfd95f92f76adb9be1990998bb1699210aa647e8.png

For comparison purposes, let’s try \(k\) = 3.

_images/15f2fb64dd7811ad14fc4ce7b2a1ee2eb3b4e79b085a1d4d54383b81176e7c80.png

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

_images/8be09c5a5253847bc2a96d72e5e366359f751a8fabb3d9093652524b3556113a.png

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:

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

import sklearn.model_selection as model_selection

nreps = 50
kvals = range(1, 10)
acc = []
np.random.seed(4)
for k in kvals:
    test_rep = []
    train_rep = []
    for i in range(nreps):
        X_train, X_test, y_train, y_test = model_selection.train_test_split(X, 
                                                                            y, 
                                                                            test_size = 0.5)
        knn = KNeighborsClassifier(n_neighbors = k)    
        knn.fit(X_train, y_train)
        train_rep.append(knn.score(X_train, y_train))
        test_rep.append(knn.score(X_test, y_test))
    acc.append([np.mean(np.array(test_rep)), np.mean(np.array(train_rep))])
accy = np.array(acc)

_images/2a3f9b88b52caeb51fa241d41759ef3d24fc20aee321a381a628fb490e84184e.png

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\).

_images/cd4ca0ad0fb103394e236fcf8cefed0292557b85596658ffc2acbb2a6d6621db.png

Decision Tree#

Next, we’ll use a decision tree on the same data set.

import sklearn.tree as tree
dtc = tree.DecisionTreeClassifier(max_leaf_nodes = 5)

dtc.fit(X_train,y_train)
y_pred_test = dtc.predict(X_test)
print('DT accuracy on test data: ', dtc.score(X_test, y_test))
y_pred_train = dtc.predict(X_train)
print('DT accuracy on training data: ', dtc.score(X_train, y_train))

DT accuracy on test data:  0.94
DT accuracy on training data:  0.98

_images/8617966da275f4ca783feeadd09005da574d4421009e25789007b1cf7a7b42dd.png

Let’s visualize the decision boundary of the Decision Tree.

_images/d423e7b4a0e979026fb95afad3c69d76a0e47458fa5aee5112940e834f185faf.png

Comparing \(k\)-NN and Decision Tree#

It appears that \(k\)-NN and a Decision Tree have approximately comparable performance on this dataset.

However - there is a difference in interpretability.

Interpretability is a big deal! It means the ability to explain why the classifier made the decision it did.

It can be relatively difficult to understand why \(k\)-NN is making a specific prediction. It depends on the data in the neighborhood of the test point.

On the other hand, the Decision Tree can be easily understood.

We sometimes use the terms “black box” for an uninterpretable classifier like \(k\)-NN, and “white box” for an interpretable classifier like DT.

Let’s see an example of the interpretability of the Decision Tree:

_images/e30ca63cfc2fabcdef35479f05d85520861b25b361c58f69fb903991f917211c.png

Real Data#

To explore a few more issues, we’ll now turn to some famous datasets that have been extensively studied in the past.

The Iris Dataset#

The Iris dataset is a famous dataset used by Ronald Fisher in a classic 1936 paper on classification.

R. A. Fisher

By http://www.swlearning.com/quant/kohler/stat/biographical_sketches/Fisher_3.jpeg, Public Domain, https://commons.wikimedia.org/w/index.php?curid=4233489

Quoting from Wikipedia:

The data set consists of 50 samples from each of three species of Iris (Iris setosa, Iris virginica and Iris versicolor). Four features were measured from each sample: the length and the width of the sepals and petals, in centimetres. Based on the combination of these four features, Fisher developed a linear discriminant model to distinguish the species from each other.

I. setosa

I. versicolor

I. virginica

iris = datasets.load_iris()

X = iris.data
y = iris.target
ynames = iris.target_names
print(X.shape, y.shape)
print(X[1,:])
print(iris.target_names)
print(y)

(150, 4) (150,)
[4.9 3.  1.4 0.2]
['setosa' 'versicolor' 'virginica']
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2
 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
 2 2]

First, we’ll explore setting hyperparameters.

We start with \(k\)-NN.

To set the hyperparameter \(k\), we evaluate error on the test set for many train/test splits:

kvals = range(2, 20)
nreps = 50

acc = []
std = []
np.random.seed(0)
for k in kvals:
    test_rep = []
    train_rep = []
    for i in range(nreps):
        X_train, X_test, y_train, y_test = model_selection.train_test_split(
            X, y, test_size = 0.33)
        knn = KNeighborsClassifier(n_neighbors = k)    
        knn.fit(X_train, y_train)
        train_rep.append(knn.score(X_train, y_train))
        test_rep.append(knn.score(X_test, y_test))
    acc.append([np.mean(np.array(test_rep)), np.mean(np.array(train_rep))])
    std.append([np.std(np.array(test_rep)), np.std(np.array(train_rep))])

Max Test Accuracy at k = 13 with accuracy 0.969

_images/0882afa462eeb3befa3c4296ec1cf066208752699e7c11139dd4ee6e16f75814.png

Now, it looks llike \(k\) = 13 is the best-performing value of the hyperparameter.

Can we be sure?

Be careful! Each point in the above plot is the mean of 50 random train/test splits!

If we are going to be sure that \(k\) = 13 is best, then it should be be statistically distinguishable from the other values.

To make this call, let’s plot \(\pm 1 \sigma\) confidence intervals on the mean values.

(See the Probability Refresher for details on the proper formula.)

_images/35201d51a722bc401742959d2929e7ee6bc918fa6de29d44e0cf42706e627090.png

It looks like \(k\) = 13 is a reasonable value,

although a case can be made that 9 and 11 are not statistically distinguishable from 13.

To gain insight onto the complexity of the model for \(k\) = 13, let’s look at the decision boundary.

Note that we will re-run the classifier using only two (of four) features, so we can visualize.

_images/09a3ea6a5d4e3dbc9e3095b8a830dd7289f5d9f91cb80f12e60f582dc1561960.png

There are a few artifacts, but overall this looks like a reasonably smooth set of decision boundaries.

Now we’ll compare to a decision tree.

How do we control the complexity of a Decision Tree?

There are a variety of ways (see the sklearn documentation) but the simplest one is to control the number of leaf nodes in the tree.

A small number of leaf nodes is a low-complexity model, and a large number of nodes is a high-complexity model.

_images/de9bc71c77ee1afd0c83b9ce89c6fa50ce60b8c7d39976a448f17795641f8d95.png

_images/ae49bdd31fc2a6143a29e3542812c01906158f4dd3bb6b7ea9b5a4c8ecf11ac4.png

It looks like 9 leaf nodes is appropriate, but we would be justified to choose 4 or 13 as well.

And now let’s visualize the decision boundary for the DT:

_images/20e8b0d5ecac2338671dc6f3f22e76f1717fc478aa170635c2e2a29de0817a24.png

MNIST dataset#

NIST used to be called the “National Bureau of Standards.” These are the folks who bring you the reference meter, reference kilogram, etc.

NIST constructed datasets for machine learning of handwritten digits. These were collected from Census Bureau employees and also from high-school students.

These data have been used repeatedly for many years to evaluate classifiers. For a peek at some of the work done with this dataset you can visit http://yann.lecun.com/exdb/mnist/.

import sklearn.utils as utils

digits = datasets.load_digits()
X, y = utils.shuffle(digits.data, digits.target, random_state = 1)

print ('Data shape: {}'.format(X.shape))
print ('Data labels: {}'.format(y))
print ('Unique labels: {}'.format(digits.target_names))

Data shape: (1797, 64)
Data labels: [1 5 0 ... 9 1 5]
Unique labels: [0 1 2 3 4 5 6 7 8 9]

An individual item is an \(8 \times 8\) image, encoded as a matrix:

digits.images[3]

array([[ 0.,  0.,  7., 15., 13.,  1.,  0.,  0.],
       [ 0.,  8., 13.,  6., 15.,  4.,  0.,  0.],
       [ 0.,  2.,  1., 13., 13.,  0.,  0.,  0.],
       [ 0.,  0.,  2., 15., 11.,  1.,  0.,  0.],
       [ 0.,  0.,  0.,  1., 12., 12.,  1.,  0.],
       [ 0.,  0.,  0.,  0.,  1., 10.,  8.,  0.],
       [ 0.,  0.,  8.,  4.,  5., 14.,  9.,  0.],
       [ 0.,  0.,  7., 13., 13.,  9.,  0.,  0.]])

Let’s show the matrix as an image:

<Figure size 640x480 with 0 Axes>

_images/bcb947dd09c3d2691eb1d28dacb0edd310120529734164a296f64fb20eb85b87.png

It is easier to visualize if we blur the pixels a little bit.

_images/549dfae8cfd04142bc024d8822c29d5bd7b7a55150c441fa79449d1e642739bc.png

Here are some more samples from the dataset:

_images/219c953497ffcaea0fb3484973f943015ee4895ad453eab47a86c04325565e07.png

_images/d3fa2db197ea2b852a6fbb992dc6bfcf61b84b4123233f3bcf54fa860bf9a18b.png

_images/aef4e9d7b89f6aab0f01be9f8562268f104df6be07206db665691704bcf34736.png

_images/be006775ac6999d67c2c1c730263e831ad24b2f1e934d282c38aff635bf8dd97.png

Although this is an 8 \(\times\) 8 image, we can just treat it as a vector of length 64.

To do model selection, we will again average over many train/test splits.

However, recall one issue of \(k\)-NN: it can be slow on a large training set (why?).

We may thus decide to limit the size of our testing set to speed up testing.

How does the train/test split affect results?

Let’s consider two cases:

Train: 90% of data, Test: 10% of data
Train: 67% of data, Test: 33% of data

def test_knn(kvals, test_fraction, nreps):
    acc = []
    std = []
    np.random.seed(0)
    #
    for k in kvals:
        test_rep = []
        train_rep = []
        for i in range(nreps):
            X_train, X_test, y_train, y_test = model_selection.train_test_split(
                X, y, test_size = test_fraction)
            knn = KNeighborsClassifier(n_neighbors = k)    
            knn.fit(X_train, y_train)
            test_rep.append(knn.score(X_test, y_test))
        acc.append(np.mean(np.array(test_rep)))
        std.append(np.std(np.array(test_rep)))
    return(np.array(acc), np.array(std)/np.sqrt(nreps))

test_fraction1 = 0.33
accy1, stds1 = test_knn(range(2, 20), test_fraction1, 50)
test_fraction2 = 0.10
accy2, stds2 = test_knn(range(2, 20), test_fraction2, 50)

_images/883e302b0d1be2aba9ef56f139e0e40311163cc8625e9d533850c0b75dea1c7f.png

These plots illustrate important principles:

The more data used for training, the better the classifier will tend to perform
The less data used for testing, the more variable will be the testing results (but the faster testing will go)

Note that the key decision here is what value to choose for \(k\). So it makes sense to use the 33% test split, because the smaller error bars give us better confidence in our decision.

We can get a sense of why \(k\)-NN can succeed at this task by looking at the nearest neighbors of some points:

_images/859c76a639c4bd1893b9a3cebe5af73990199b293a7ffa183e353d5e2d08706e.png

_images/ecc4e18b72c1b9ce2e3f4e020bcba3fb9fbc6fd3f3f8fee264f1d852eca91f01.png

_images/eb78ba886e4b68d43673e688481f44ce9358552ed782bd9bdb2ea699449497d8.png

k-Nearest Neighbors

Contents

\(k\)-Nearest Neighbors#

Parametric vs. Nonparametric Models#

\(k\)-Nearest Neighbors#

Model Selection for \(k\)-NN#

Challenges for \(k\)-NN#

The Curse of Dimensionality#

In Practice#

How do we evaluate a classifier?#

Evaluating \(k\)- Nearest Neighbors and Decision Trees#

Decision Tree#

Comparing \(k\)-NN and Decision Tree#

Real Data#

The Iris Dataset#

MNIST dataset#