k-Nearest Neighbours
Learning Objectives
After reading this page, you should be able to:
- Classify a test point by applying KNN to a small data set.
- Draw the decision boundaries of KNN for a small data set.
- Analyze the impact of varying k on KNN’s behaviour.
- Explain the common pitfalls of KNN.
1 Introduction
In this section, we study a simple supervised learning algorithm. In fact, the technique is so simple that there is no “learning” process per se. However, the core idea behind the simple technique is actually quite deep and worth reflecting on.
This section also emphasizes the process of building a supervised learning model. We use the same notation, terminology, and examples from the previous section.
We also continue to use the same leaf prediction dataset. Suppose that we have the following data set:
| # | Leaf Width | Leaf Height | Leaf Type |
|---|---|---|---|
| 1 | 7.0 cm | 12.0 cm |  |
| 2 | 9.0 cm | 6.0 cm | |
| 3 | 10.0 cm | 18.0 cm | |
| 4 | 5.0 cm | 10.0 cm | |
| 5 | 13.0 cm | 11.0 cm |  |
| 6 | 11.0 cm | 9.0 cm | |
| 7 | 9.0 cm | 14.0 cm | |
| 12.0 cm | 16.0 cm | ? |
To familiarize ourselves with the dataset, let’s consider this same exercise again from the last section:
Question: In the table above, there is one unlabelled data point. What would your (human) prediction be of whether the leaf is an Oak or a Maple? What explanation can you provide for your prediction?
Answer:
There is no single right answer here. Most people would begin by searching for a labelled training data point that is similar to the test data point \(\begin{bmatrix} 12.0 \\ 16.0 \end{bmatrix}\), then predict whichever leaf type that similar point has.
That strategy of comparing against similar labelled points is exactly what we will do in the Nearest Neighbour classifier.
2 The 1-Nearest Neighbour Classifier
The 1-nearest neighbour algorithm formalizes this intuitive approach. The idea is remarkably simple: for a new data point \({\bf x}\) for which we want to make a prediction, we find the closest data point in the training set and copy its label.
Definition: To perform inference using the 1-nearest neighbour algorithm on a test data point \({\bf x}\), we first find its closest data point in the training set \({\bf x}^{(C)}\):
\[\begin{align*} C = \underset{i \in \{1, 2, \dots N\}}{\arg\min} \textrm{distance}({\bf x}^{(i)}, {\bf x}) \end{align*}\]
Then we copy the label of the \(C\)-th data point and predict \(y = t^{(C)}\).
Understanding \(\arg\min\):
- \(\arg\min\) means “the argument that minimizes”: it returns the index \(i\) that gives the smallest distance, not the distance value itself
- \(i \in \{1, 2, \dots N\}\) ranges over all \(N\) training examples
- \({\bf x}^{(i)}\) is the \(i\)-th training point
- So \({\bf x}^{(C)}\) is the training point closest to our test point \({\bf x}\)
In plain English: “Find which training example is closest to the test point.”
For example, for our test data point \(\begin{bmatrix} 12.0 \\ 16.0 \end{bmatrix}\), the closest data point appears to be data point \(C=3\), so we copy the label \(y=t^{(3)}\), which is Oak.
We can identify which training point is closest and draw a line connecting them:
1-Nearest neighbor identification
A critical design choice in the nearest neighbour algorithm is: how do we measure distance? Different distance measures make sense for different machine learning problems.
Euclidean Distance (also known as the \(L_2\) distance) is a reasonable “default” choice. This is the familiar straight-line distance in \(d\)-dimensional space.
\[\begin{align*} ||{\bf x}^{(a)} - {\bf x}^{(b)}||_2 = \sqrt{\sum_{j=1}^d (x_j^{(a)} - x_j^{(b)})^2} \end{align*}\]
Cosine Similarity is another option. This measures the angle between two vectors (where \(\cdot\) below is the vector inner product). Cosine similarity is particularly useful when the magnitude of vectors is less important than their direction, such as in text classification.
\[\begin{align*} \textrm{cosine}({\bf x}^{(a)}, {\bf x}^{(b)}) = \frac{{\bf x}^{(a)} \cdot {\bf x}^{(b)}}{||{\bf x}^{(a)} ||_2 ||{\bf x}^{(b)} ||_2} \end{align*}\]
Other \(L_p\) distances can also be reasonable: for example, the Manhattan distance (also known as the \(L_1\) distance) and the Chebyshev distance or maximum metric (also known as the \(L_\infty\) distance). More generally, the \(L_p\) distance is defined as follows:
\[\begin{align*} ||{\bf x}^{(a)} - {\bf x}^{(b)}||_p = \left( \sum_{j=1}^d \left| x_j^{(a)} - x_j^{(b)} \right|^p \right)^{\frac{1}{p}} \end{align*}\]
One can imagine using much more complex and powerful distance measures. In practice, however, we rarely use measures outside of Euclidean distance and cosine similarity. Sophistication instead comes from finding (or automatically learning) good features where these simple distance metrics work well. Thus, for the remainder of this section, we will use Euclidean distance.
3 Decision Boundaries
One way to gain intuition about any classification algorithm is by visualizing its decision boundary. Recall that a decision boundary is the set of points in the input space where perturbing the point by a tiny bit would change the predicted output.
What does the decision boundary for the 1-NN model look like for the leaf dataset? To answer this question, let’s start with the test data point \(\begin{bmatrix} 12.0 \\ 16.0 \end{bmatrix}\) again. How far (and in what direction) would we have to move this test data point in order for its prediction to change from Oak to Maple?
Interactive decision boundary exploration
You might see that if we move the test data point away from \({\textbf x}^{(3)} = \begin{bmatrix} 10 \\ 18 \end{bmatrix}\) and towards \({\textbf x}^{(7)} = \begin{bmatrix} 9 \\ 14 \end{bmatrix}\), the prediction will change. Where that prediction changes is on the decision boundary. And that decision boundary is precisely the set of points that are equidistant to \({\textbf x}^{(3)}\) and \({\textbf x}^{(7)}\). This set of points forms a line in the data space. Thus, for a 1-Nearest Neighbour model, the decision boundaries are comprised of line segments.
We can systematically draw the decision boundary for the 1-nearest neighbour model by drawing a Voronoi diagram. A Voronoi diagram partitions space into regions closest to each member of a set. Each region contains all points that are closer to that training example than to any other training example.
Voronoi diagram for the leaf dataset
The decision boundary of the 1NN model follows the lines in the Voronoi diagram that separate regions of different classes:
1-NN decision boundary visualization
Visualizing the decision boundaries allows us to intuitively “see” a summary of how the kNN algorithm behaves. Very shortly, we will be able to compare several different models.
4 Training Accuracy and Overfitting
One might ask: is the 1-nearest neighbour model a “good” model? As we saw in the last unit, the accuracy of a model’s prediction is one way of measuring how “good” a model performs. The accuracy of the model on the training set is called the training accuracy.
Question: When we evaluate our nearest neighbour model on the leaf training data, what accuracy do we get?
Answer:
Unless there are identical points with different labels, the nearest neighbour algorithm will achieve 100% training accuracy! This is because each training point’s nearest neighbor is itself, so it will always predict its own label correctly!
However, this doesn’t necessarily mean the model is good. The nearest neighbour algorithm is sensitive to noise or mislabeled data. A single mislabeled point can create an entire Voronoi region of incorrect predictions.
This suggests that training accuracy alone is not the best metric for evaluating model quality. We need to consider how well the model will perform on new, unseen data.
5 k-Nearest Neighbours
To address the sensitivity to noise, we can extend the algorithm: instead of basing the prediction on a single training example, we use \(k\) of them!
To perform inference in the k-Nearest Neighbour Algorithm on a test instance \({\bf x}\), we first find \(k\) training examples \(\{{\bf x}^{(i)}, t^{(i)}\}\) closest to \({\bf x}\), then set the prediction \(y\) to the majority class out of these \(k\) examples.
Question: In the leaf prediction problem, at what points in the data space would a 3-NN model give a different prediction than a 1-NN model?
As with 1-NN, the figure below allows us to explore the 3NN predictions interactively. When you move the test point around the data space, the visualization shows the 3 nearest neighbors connected by lines. The prediction is determined by majority vote among these three neighbors. Notice how the prediction can change as you move the test point, and where it changes depends on which neighbors are included in the top 3.
Interactive 3-NN decision boundary exploration
You might observe that the prediction changes more gradually with 3-NN compared to 1-NN. This is because a single point moving in or out of the top 3 neighbors does not necessarily change the majority vote. This makes the decision boundary smoother and less sensitive to individual training points. We can systematically visualize the complete decision boundary for the 3-NN model:
Comparison of 1-NN (left) and 3-NN (right) decision boundaries
6 The Hyperparameter \(k\)
The number of data points \(k\) to use in a \(k\)-Nearest Neighbour model is considered a hyperparameter. A hyperparameter is a setting that we need to choose, but which is not learned automatically by the learning algorithm itself.
Different values of \(k\) lead to different model behaviors. This is much easier to see on a larger data set with more complex patterns.
k-NN decision boundaries for different values of k
As you can see, if \(k\) is too small, the model’s decision boundary appears “noisy”. The model is very good at capturing fine-grained patterns. In the extreme case of \(k=1\), we can achieve 100% training accuracy, but we expect the model to perform poorly on new data. That is, the patterns that are captured are not all “real”; some are just idiosyncrasies in the training dataset we happened to get, and do not generalize. This is called overfitting.
Definition: A model is said to be overfitting to the training data when it captures not only the true generalizable patterns, but also random noise or idiosyncrasies. As a result, the model performs exceptionally well on the training set but fails to generalize to new, unseen data, leading to poor performance on test or validation examples.
However, if \(k\) is too large, then the model’s decision boundary becomes too “simple”. The model makes fairly stable predictions, even if the input changes by a little bit. In the extreme case, where \(k=N\), the size of the training set, our model would always predict the most common class in the training set. That is, important patterns or regularities in the data are not captured. This is called underfitting.
Definition: A model is said to be underfitting the training data when it is too simple to capture the underlying generalizable patterns that exist. Such a model performs poorly on the training set itself, as well as on new, unseen data, because it fails to represent the important structure in the data.
So what is the optimal \(k\)? It is possible to show that, under certain assumptions, the optimal choice of \(k\) depends on the number of data points \(n\). There are nice theoretical properties if \(k \to \infty\) and \(\frac{k}{n} \to 0\). Thus, theory tells us that we should typically choose \(k < \sqrt{n}\).
In practice, ML practitioners choose \(k\) by evaluating which value performs best on a separate labeled dataset: i.e., the validation set.
As discussed in the previous section, when building a supervised learning model, we set aside some labeled data in a separate validation set. The validation set will be used to tune hyperparameters like \(k\).
7 Pitfalls and Practical Considerations
We mentioned in the previous sections that data and features are both extremely important. We can see that in action with \(k\)-Nearest Neighbours. The \(k\)-Nearest neighbours classifier is particularly sensitive to the ranges of different features. Often, the units we use are arbitrary: in the leaf dataset, we measured the width and height of a leaf in cm. But what if we measured the width in nanometers?
The figure below shows how the 1NN decision boundary changes if the leaf width is measured in mm rather than cm (and thus the first data point would be represented \({\textbf x}^{(1)} = \begin{bmatrix} 7 \\ 120 \end{bmatrix}\) rather than \({\textbf x}^{(1)} = \begin{bmatrix} 7 \\ 12 \end{bmatrix}\)). Notice that the decision boundary looks very different from the 1NN model from earlier. In fact, the test data point is now closer to \({\textbf x}^{(5)}\) than \({\textbf x}^{(3)}\), so the prediction on that data point changes. Thus, if one feature has a much larger scale than another, it will dominate the distance calculation.
Impact of feature scaling on k-NN decision boundaries
So what units should we use? With this data set, using consistent units for width and height makes intuitive sense. But what if our data set has many different measures? For example, we may wish to predict if a person has heart disease based on their blood pressure, height, weight, caloric intake, etc. All these measures have different units. The choice of units is actually quite arbitrary.
One approach that works reasonably well is to standardize (or normalize) the data so that each dimension has zero mean and unit variance. This method assumes that each feature is roughly equally “important”, and should be weighted similarly in the distance measurement.
To standardize the data set, we do the following:
- Compute the mean \(\mu_j\) and standard deviation \(\sigma_j\) for each feature \(j\) using the training set
- Create new features: \(\tilde{x}_j = \frac{x_j - \mu_j}{\sigma_j}\), which are then used for building the kNN model.
It is important to note that the statistics (\(\mu_j\), \(\sigma_j\)) should be computed from the training set only. To avoid data leakage, the validation and test sets should be excluded from the computation. However, when normalizing the validation and test sets, we apply the same transformation using the \(\mu_j\) and \(\sigma_j\) computed from the training set. We do not compute separate statistics for each data set, to ensure that the transformations made to the features are consistent.
8 The Curse of Dimensionality
Although the \(k\)-nearest neighbour algorithm visualization looks quite nice, it is important to note that in realistic, high-dimensional settings, our intuition about distances do not hold. Like many models, the \(k\)-nearest neighbours algorithm suffers from a fundamental problem in high-dimensional spaces, known as the curse of dimensionality.
The problem is that in high dimensions, most points are far apart from each other. Intuitively, because there are more dimensions in which two points could be different, points tend to just be further away.
Why does this matter? In kNN, we would like our prediction (for the test data point) to be based on training data points that are close by: this is desirable because data points that are “close by” give us better information about how to predict a test data point.
To explore the curse of dimensionality, let’s assume training data is spread out uniformly, and the test point is at the origin. We will consider what portion of the data lies “close” to the origin as the dimensionality \(d\) increases.
More formally, think of our data as being spread out uniformly in a \([0, 1]^d\) hypercube: in 1D \([0, 1]\) is a line, in 2D \([0, 1]^2\) is a square, in 3D \([0, 1]^3\) is a cube, and in 4D and more generally we call \([0 ,1]^d\) a hypercube. We will define “close” to mean “within distance \(\epsilon\) from the origin”, and analyze the fraction of the hypercube that is “close” to the origin. For simplicity, we will use the Chebyshev distance, also known as the \(L_\infty\) distance. The same analysis works with Euclidean and other distances as well. Intuitively, the Chebyshev distance between two points is the largest absolute difference between them along any single coordinate:
\[||{\bf x}^{(a)} - {\bf x}^{(b)}||_\infty = \max_{j \in \{1, \dots, d\}} |x_j^{(a)} - x_j^{(b)}|.\]
The set of points within distance \(\epsilon\) of a given point is called its ball of radius \(\epsilon\). The shape of this ball depends on the distance we use: under the Chebyshev distance, the ball is an axis-aligned cube. The Chebyshev distance is convenient here because the origin sits at a corner of \([0,1]^d\), so the points within distance \(\epsilon\) of it form the small cube \([0, \epsilon]^d\), whose volume is exactly \(\epsilon^d\). Since the total volume of a hypercube \([0,1]^d\) is \(1\), the fraction of points that are within \(\epsilon\) of the origin is \(\epsilon^d\), which shrinks exponentially as the dimension \(d\) grows!
Fraction of space within distance \(\epsilon = 0.3\) from the origin within hypercubes of different dimensions
As we have shown, in high dimension, most points are far apart. Thus, we need many more training data points to support our kNN model in order to ensure that the selected neighbours are “close by”.
Question: How many training points do we need so that every test point \({\bf x}\) in the unit hypercube \([0,1]^d\) has a training point within distance \(\epsilon\)?
Answer:
Each training point “covers” all the test points within distance \(\epsilon\). Under the Chebyshev distance, that region is a cube of side \(2\epsilon\) centred on the training point. Thus, every training point covers a volume of at most \((2\epsilon)^d\).
Let \(N\) be the number of training points required. Together they cover a volume of at most \(N(2\epsilon)^d\), and they must cover the entire unit hypercube \([0,1]^d\), whose volume is \(1\). So the number of training points \(N\) must satisfy the inequality below
\[N(2\epsilon)^d \geq 1 \Rightarrow N \geq \frac{1}{(2\epsilon)^d} = \left(\frac{1}{2\epsilon}\right)^d.\]
For \(\epsilon < \frac{1}{2}\), this lower bound grows exponentially with \(d\). In other words, the number of training points needed to cover the unit hypercube grows exponentially with the dimension \(d\).
Another manifestation of the curse of dimensionality: in high dimensions, “most” points are approximately the same distance from any given test point.
Interactive distance distribution in low vs. high dimensions
This means that the notion of “nearest” neighbor becomes less meaningful: if all neighbors are roughly equidistant, there’s no clear “closest” point to base our prediction on. This property can be shown rigorously using properties of expectation and covariance of random variables, and affects the effectiveness of k-NN in high-dimensional spaces.
9 Summary
The k-nearest neighbour algorithm is appealingly simple and intuitive. It is a “lazy learning” algorithm that does all its work at inference time. In a sense, there’s no training phase, only inference. However, it is already enough to illustrate several of the key ideas in machine learning described in the introduction.
Fundamental Idea #2: ML Requires Balancing Tradeoffs in Sources of Error, is on display in the choice of \(k\). Like many machine learning models, the parameter \(k\) in a \(k\)-Nearest Neighbour model controls the “complexity” of the model. Decreasing \(k\) makes the model more capable of fitting intricate patterns, but also more prone to learning idiosyncrasies in the training data that don’t generalize. Increasing \(k\) makes the model focus on simpler patterns that tend to generalize better, but may cause it to miss real complex patterns in the data.
There are also tradeoffs related to computation time for training vs. inference. Since \(k\)-nearest neighbour has no training phase, all computation is deferred to test time: we need to both store and compute distances to all training points. If the size of the training set is large, the storage and distance computation costs can be prohibitively expensive. Needing to store the entire training set is unusual: we will see that other model families will compress/summarize the training set in some way.
Fundamental Idea #4: ML Describes Geometric Processes, is central to understanding kNN. Selecting the right features and feature scaling is important for a distance measure that is meaningful. Performance in kNN is directly related to a “good” notion of distance between data points, which relies on “good” choices of features.
When features are not scaled appropriately, one feature could dominate the others. Normalization (or standardization) is a default option for ensuring that features are scaled appropriately, and that no single feature overwhelms the distance computation.
The curse of dimensionality is another geometric aspect of data important for kNN and other models. Intuitions about distances in 2D do not necessarily follow in high-dimensional spaces, where data points tend to be further apart from one another.
Despite these limitations, k-NN remains a useful algorithm. It is a simple baseline to compare against more sophisticated methods. It is also useful as a component in more complex algorithms, for example where distance computation is done using features that are automatically learned from another model. It also turns out that as we collect more data and refine our models, many sophisticated learning methods can approach the behavior of nearest-neighbor methods. This is because with sufficient data density, the optimal prediction at any point often depends most heavily on the nearby training examples.