On Nearest Neighbor

I’ve been using nearest neighbor quite a bit lately, and I’ve noticed that its accuracy is remarkable, and I’ve been trying to understand why.

It turns out that you can prove that for certain datasets, you actually can’t do better than the nearest neighbor algorithm:

Assume that for a given dataset, classifications are constant within a radius of R of any data point.

Also assume that each point has a neighbor that is within R.

That is, if x is a point in the dataset, then there is another point y in the dataset such that ||x-y|| < R.

In plain terms, classifications don’t change unless you travel further than R from a given data point, and every point in the dataset has a neighbor that is within R of that point.

Now let’s assume we’re given a new data point from the testing set that is within the boundaries of the training set.

By definition, the new point is within R of some point from the training set, which implies it has the same class as that point from the training set.

This proves the result.

This means that given a sufficiently dense, locally consistent dataset, it is mathematically impossible to make predictions that are more accurate than nearest neighbor, since it will be 100% accurate in this case.

Unless you’re doing discrete mathematics, which can be chaotic (e.g., nearest neighbor obviously won’t work for determining whether a number is prime) your dataset will probably be locally consistent for a small enough value of R.

And since we have the technology to make an enormous number of observations, we can probably produce datasets that satisfy the criteria above.

The inescapable conclusion is that if you have a sufficiently large number of observations, you can probably achieve a very high accuracy simply using nearest neighbor.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s