
K-Nearest Neighbors from Scratch - craigkerstiens
https://lettier.github.io/posts/2016-06-10-k-nearest-neighbors-from-scratch.html
======
Radim
While the topic may seem trivial and the execution/implementation a bit too
naive, it should be noted the author is a _graphic designer_! Check out
David's homepage [0] -- original, if not very practical :-)

I personally think it's great to see such cross-pollination between various
fields. It helps other newcomers to read about this stuff "in their own
language", using a perspective of someone from their own field (as opposed to
the usual academic / old-hand angle).

[0] [http://www.lettier.com/](http://www.lettier.com/)

~~~
hugh4
Maybe, but if the new cross-pollination just confuses the issue rather than
clarifying it, what's the point?

"Suppose you have a bunch of flowers in a field, and they're planted so that
the east-west direction corresponds to the diameter of the flower and the
north-west direction corresponds to the length of the leaf."

"Huh?"

"Suppose you have a bunch of data points in an n-dimensional space"

"Oh, gotcha"

~~~
spdustin
What an exclusionary thing to say. Was that your intent?

~~~
hugh4
That's not even a word.

~~~
spdustin
[http://www.dictionary.com/browse/exclusionary](http://www.dictionary.com/browse/exclusionary)

Of course, I did hear that _gullible_ was removed from the dictionary during
an annual meeting of linguists in Leeds last year.

------
henryw
Pretty neat for implementation used as a tutorial. A more industry standard
implementation would probably use a tree of some type to reduce the space and
search time. For example
[https://en.wikipedia.org/wiki/K-d_tree](https://en.wikipedia.org/wiki/K-d_tree)
in [http://scikit-
learn.org/stable/modules/generated/sklearn.nei...](http://scikit-
learn.org/stable/modules/generated/sklearn.neighbors.KNeighborsClassifier.html)

------
bra-ket
very nice write-up. if you're interested in this, the next logical step is to
look at 'locality-sensitive hashing' and some simple state-of-the-art methods:
[https://github.com/spotify/annoy](https://github.com/spotify/annoy)

------
leecarraher
this description of linear scan kNN may be a bit tedious for the hacker news
crowd. here's the gist (in python):

    
    
      def knn(y,X,k):
         d = len(y)
         least = [(float('inf'),[float('inf')]*d) for i in xrange(k)]
         for x in X:
            d = 0.0 
            for i in xrange(len(x)):
               d+=abs(x[i]-y[i])
            if d < least[k-1][0]:
               least[k-1] = (d,x)
               least.sort()
         return least
    
    

Sorting even for linear isn't the best idea but keeps the algorithm terse. A
data structure like a priority queue should probably be used instead of an
array.

and one should use a kd tree or ball tree for exact, and LSH-knn for inexact
in practice.

~~~
thomasahle
You can use `heapq` from the standard library to at least go from `n k log k`
to `n log k`.

------
theoracle101
Why not just use a kd tree or voroni?

~~~
jeena
How would you learn how to implement that algorythm if you'd just use an
existing implementation?

~~~
AReallyGoodName
Read the wiki page on it, run through the psuedocode on pen and paper a few
times and then implement it.

Source: I did this when I wrote a library for reverse geocoding which uses a
kd tree.

[https://github.com/AReallyGoodName/OfflineReverseGeocode](https://github.com/AReallyGoodName/OfflineReverseGeocode)

