# K nearest neighbours algorithm interpretation

In the book, The Elements of Statistical Learning http://statweb.stanford.edu/~tibs/ElemStatLearn/printings/ESLII_print10.pdf (page 19-20)

The author claims that

1. In the least squares method, we assume the regression function $f(x)$ is well approximated by a globally linear function.

2. In the k nearest neighbors method we assume the regression function $f(x)$ is well approximated by a locally constant function.

I can understand this statement when $k=1$ (like we assume that on the line segment joining the target point $x_i$ and it's nearest neighbor $x_j$ the function is constant).

I am unable to understand this statement when $k \neq 1$. If $k \neq 1$ we average over the $k$ nearest neighbors. If we assume the function to be locally constant, why do we need to average, we can just pick one of the k neighbors.

Can anyone clarify what the author means by statement 2.

Let's suppose that we observe $y_1, \dots, y_n$ where $y_i = \mu + \varepsilon_i$ for iid errors $\varepsilon_i$ with mean 0 and variance $\sigma^2$. I'm just denoting the constant value of $f(x_i)$ for each $i$ by $\mu$ here. We want to predict the label $y_0$ for some new point $x_0$, which we could do by (1) taking the nearest point to our test point, say $y_1$, or (2) we could average the $y_i$ over all $n$.

Both are unbiased since $E(y_1) = E(\bar y) = \mu$. But their variances differ: $Var(y_1) = \sigma^2$ while $Var(\bar y) = \sigma^2/n$, so $\bar y$ is the better estimator.

So if the regression function really is constant for all $n$ of these points, then we'll get a much better estimator by averaging rather than just using one of them. In practice it's not so simple, though, because we don't think the regression function is truly constant, so it may be that the expected value of farther away points is too different and that we don't want to include them. This is all captured by choosing $k$.

• I added an answer as well to address the other aspect of the question: where are the boundaries of the piecewise-constant cells, and why do they depend on $k$? So in addition to improving signal-to-noise by averaging, the higher $k$ also implies a spatial refinement of the tessellation. – GeoMatt22 Sep 6 '16 at 18:13

Note that for any $k$, the function approximation will be piecewise constant on some set of cells. Obviously the cells will depend on the spatial distribution of the data. However the cells will also depend on $k$.

As the question notes, this may be non-intuitive for $k>1$, so a visualization may help. Here I consider the case of points in 2D with $k=1$ and $k=2$. (Hopefully the generalization will be clear.)

Below is a set of 2D data points, along with their Voronoi diagram (blue points and lines). The Voronoi cells tessellate the plane, and for each point $x_i$ its corresponding cell contains all points $x$ that are closer to $x_i$ than to any other point $x_{j\neq i}$.

I have highlighted a single point $x_i$ in black. For $k=1$ the function approximation will be constant within the associated Voronoi cell (bold black outline). So in general the 1-NN cells correspond to the Voronoi cells.

Now consider the $k=2$ case. For all points $x$ in the highlighted (black) Voronoi cell, their nearest neighbor is $x_i$. But what is their 2nd nearest neighbor? The dashed black rectangle in the picture above highlights the possible neighbors. The picture below shows how these "$k=2$" neighbors are determined, zooming in on the area of interest (dashed rectangle above).

In this figure, the point $x_i$ has been removed, and is shown as a hollow black circle. Its Voronoi cell is indicated by the black dashed outline. The Voronoi diagram of the remaining points is shown in blue. For any point $x$ in the plane, these "leave one out" Voronoi cells indicate which of the blue points $x_{j\neq i}$ is its nearest neighbor.

For points whose $k=1$ approximation uses $x_i$, the $k=2$ approximation will use a 2nd point based on the "leave one out" Voronoi diagram. So the cells used for the 2-NN approximation will be determined by intersecting these "leave one out" Voronoi cells with the Voronoi cell of the left-out point. This is shown in a third figure below.

Here the Voronoi cell for $x_i$ is partitioned into a set of 2-NN cells. The color of each sub-cell corresponds to the 2nd nearest neighbor $x_j$. In each of these sub-cells, the closest 2 neighbors are fixed, so the function approximation of 2-NN will be constant.

(Note: The colored cells above are really "half 2-NN cells", because for any $x_j$, its leave-one-out Voronoi diagram will have a corresponding half-cell corresponding to $x_i$. In both of these half-cells the 2-NN approximation will be the same.)

Hopefully this helps with the intuition on what is meant by "piecewise constant". For larger $k$ these cells would be sub-divided further (e.g. using a "leave two out" Voronoi diagram for $k=3$). The Voronoi diagrams can logically be extended to higher dimensions (3D,4D,...) as well, but their practical computation becomes infeasible. Of course for kNN the complete diagram is never needed over the entire space, but just over a finite set of query points.

A final note. The assumption of piecewise constant is not necessarily always justified. For 2D and 3D cases, where the function is smooth, a related approach using incremental Voronoi diagrams is Natural Neighbor Interpolation. (This is sometimes used for physics simulations, as part of the Natural Element Method.)

• Great answer, thanks! Did you generate the diagrams on your own? may i know what tool you used for it? – Vikash B Sep 6 '16 at 18:04
• I did them in Matlab. – GeoMatt22 Sep 6 '16 at 18:09