News for hackers. Stuff that matters.
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?
Re:K-Nearest Neighbors from Scratch by Scea91 on Wednesday June 15, 2016 @04:26AM (#11907882)
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.

Re:K-Nearest Neighbors from Scratch by jeena on Wednesday June 15, 2016 @03:40AM (#11907730)
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.

https://github.com/AReallyGoodName/OfflineReverseGeocode

Re:K-Nearest Neighbors from Scratch by UK-AL on Wednesday June 15, 2016 @06:27AM (#11908331)
Implementing a spatial tree is not the same as implementing Nearest neighbours. It's just a data structure to allow efficient culling.