k nearest neighbours

You stand at a crossroads in Almaty and want to know which district you are in. If there is a map with the district borders, this is the point in polygon problem. But what if there is no map, yet for thousands of other crossroads it is known which district they belong to? Then you can ask the neighbours: find the k nearest crossroads with a known district and trust the majority. Below are the real 7445 crossroads of the city centre. For half of them the district is “known”, the other half is the exam, which shows where the vote goes wrong.

The fill is what the neighbours would answer at each point of the map, the black lines are the real borders. With five neighbours and 3722 known crossroads the vote is right on 97.5% of the exam, and all its mistakes, the rings, huddle near the borders: there the neighbours really are from different districts. Now press “spoil 20% of labels”: every fifth known crossroads gets a random district. With k = 1 the map breaks out in spots, while with k = 9 it hardly changes. And at k = 51 the small Nauryzbay district in the south-west of the map vanishes: of its twenty exam crossroads the neighbours recognised none.

The idea

Nearby examples most likely belong to the same class. To answer a question about a new point, find the k known examples nearest to it and choose the answer that occurs most often among them.

There is no training in the usual sense here: the method only remembers the examples, and all the work happens at the moment of the question. That is why it is called lazy. Three decisions have to be made: what counts as distance, how many neighbours to take, and how to break ties. Here the distance is the ordinary straight-line one on the map; neighbours at equal distance are ordered by their number, and on a tie in votes the label of the nearest of the contenders wins. Without such rules one and the same method on the same data can answer differently.

Here is how the answer depends on k for seven crossroads sorted by distance from the question point: the nearest is in Medeu, the next two in Almaly, then Medeu again and three in Bostandyk.

k = 1: Medeu 1                          -> Medeu
k = 2: Almaly 1, Medeu 1                -> Medeu
k = 3: Almaly 2, Medeu 1                -> Almaly
k = 4: Almaly 2, Medeu 2                -> Medeu
k = 5: Almaly 2, Bostandyk 1, Medeu 2   -> Medeu
k = 6: Almaly 2, Bostandyk 2, Medeu 2   -> Medeu
k = 7: Almaly 2, Bostandyk 3, Medeu 2   -> Bostandyk

At k = 2 and k = 4 the votes split evenly, and the nearest decides. That is why for two classes k is often taken odd: then there are no ties.

Why it works

How good is such a simple method? There is an exact answer for the case when there are very many examples.

In an infinitely large sample, Cover and Hart say, half of all the information about a point’s class is contained in its nearest neighbour. And if one takes not one neighbour but k, and grows k together with the number of examples but more slowly (k → ∞, k/n → 0), the error tends to the best possible; Charles Stone proved this in 1977.

Both theorems speak of an infinitely large number of examples. On finite data, and there is no other kind, everything is decided by how many neighbours to take and what counts as closeness.

How many neighbours to ask

The listing below repeats the scene’s experiment: it splits the crossroads in half with the same generator, votes at different k and counts the share of right answers on the exam, with honest labels and with spoilt ones:

   k   clean labels   20% spoiled
   1          98.3%         82.0%
   3          97.6%         91.6%
   5          97.5%         96.2%
   9          97.5%         97.4%
  15          97.2%         97.3%
  25          96.9%         97.1%
  51          95.5%         95.9%

With honest labels one neighbour is best of all: the districts are solid pieces of the city, and the nearest crossroads is almost always in the same district as you. Each extra neighbour only adds a chance that residents of a neighbouring district come to vote. With spoilt labels it is the other way round: one neighbour repeats a random error, and one answer in five is wrong. Nine neighbours shout down one or two errors, and the accuracy is almost the same as without spoiling.

But too many neighbours harm in both cases. The vote blurs the borders, and the small districts suffer most: the Nauryzbay district has only 41 crossroads on this map, and at k = 51 its residents are shouted down by the neighbours.

Nauryzbay, the smallest district here: 20 exam crossroads, right at k = 1: 18, right at k = 9: 18, right at k = 51: 0

This is a general law of machine learning in its most visible form. A small k trusts each example too much, together with its random errors; a large k coarsens the picture and loses fine detail; the best is somewhere in between, and where exactly depends on the data. So k is not guessed but checked: part of the known examples is set aside to see which k answers best on them, or each example in turn is removed and the others are asked about it. The second way is in the article’s second problem.

Code

The method itself is a dozen lines. The nearest are chosen by heapq.nsmallest: a heap of k elements, without sorting all the distances.

The Almaty experiment: 7445 crossroads with districts, those lying inside the district borders from OpenStreetMap, shuffled and split in half. In Python the distances to all known crossroads are computed by NumPy in batches of five hundred questions at once; in Go, an ordinary loop that keeps the k best in a short ordered list.

What it costs

Remembering the examples is O(n·d) memory and no work. But each question in the simplest form compares the point with all n examples, O(d) per comparison, and chooses the k best: with a heap that is O(n log k), and with the quickselect algorithm O(n) on average. In the scene that is 3722 distances per question and almost fifteen million for one exam.

A question can be sped up by not looking at distant points at all. With few features this is done by a k-d tree: in the article on it, the nearest of 45 thousand towns of the world is found in a couple of dozen comparisons. But in hundreds of dimensions the tree stops pruning, and there one looks not for exact neighbours but for “close enough” ones, with graphs like HNSW or hashing similar to MinHash and LSH. This is how the vector search that finds similar texts and images is built.

The curse of dimensionality

Everything said rests on “close” meaning “similar”. In a space of many features this stops being true. Let us check on the same crossroads: to the two real coordinates add features that say nothing about the district, random numbers on the same scale as the city.

 useless features  right (k = 5)  nearest/farthest
                0          96.4%             0.011
                1          87.6%             0.041
                2          83.6%             0.079
                5          65.4%             0.186
               10          52.0%             0.308
               20          36.4%             0.440
               50          28.6%             0.602
              100          26.0%             0.700

The two real features drown in the noise. One random feature is enough to triple the errors, with ten the vote guesses only half, with a hundred barely better than always naming the largest district. The right column explains why: the ratio of the distances to the nearest and to the farthest of the thousand known crossroads. In two dimensions the nearest is a hundred times closer than the farthest, in a hundred and two only a third closer. When all the examples are almost equally far away, the word “nearest” loses its meaning.

This is the curse of dimensionality. For the examples to lie as densely as on the plane, exponentially more of them are needed in a many-dimensional space, and random distances are made up of many terms and so are almost equal.

But real data are not random points. The handwritten digits of the open UCI dataset are 256 pixels, and still they have neighbours: the basic course, in the chapter on machine learning, guesses digits by the neighbours’ vote about 98% of the time. The listing compares three clouds of 256 numbers:

digits                          nearest/farthest 0.346
pixels shuffled between digits  nearest/farthest 0.752
random pixels                   nearest/farthest 0.803

The second cloud has the same pixels, only shuffled between the digits: each point of the picture has the same share of ink, but the strokes no longer add up to digits. And the distances at once even out almost as for random noise. The digits occupy a narrow region of their space: an eight can be tilted, thickened, shifted, but there are far fewer variants than pictures of 256 pixels. Neighbours work exactly as far as the features reflect this structure. Hence the practical rules: throw out features that say nothing about the problem, and bring the rest to one scale, or a feature measured in metres will shout down one measured in units.

History

The nearest-neighbour rule was proposed by Evelyn Fix and Joseph Hodges in 1951, in a technical report on discrimination rules. They showed that as the number of examples grows, such discrimination rules approach the best one. The report itself was printed in a journal only in 1989, together with a commentary on its place in the history of statistics. The “no worse than twice” bound from the section on why the method works was proved by Thomas Cover and Peter Hart in 1967 in the paper “Nearest neighbor pattern classification”.

Problems

The first problem is the method with all the tie rules on real crossroads. In the second, k has to be chosen for earthquakes: asking all the others about each one is expensive if you start afresh for each k.