Re:K-Nearest Neighbors from Scratch
by theoracle101 on Wednesday June 15, 2016 @12:56AM
(#11907225)
Why not just use a kd tree or voroni?
[ Parent
| on HN ]
One reason is that the implementations are much more difficult. In k-d trees you have to deal with the distance from hyperrectangles. It is not something you would write in 30 minutes.
Also k-d trees don't scale much in higher dimensions (https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/...) so in large dimensional problems (the article says 20 is already large) the naive linear search tends to be actually faster. Voronoi is even worse in dimensions larger than 2.
How would you learn how to implement that algorythm if you'd just use an existing implementation?
Re:K-Nearest Neighbors from Scratch
by AReallyGoodName on Wednesday June 15, 2016 @05:29PM
(#11912282)
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.