2012/7/30 Gael Varoquaux <[email protected]>: > On Mon, Jul 30, 2012 at 11:52:36AM +0200, Olivier Grisel wrote: >> > In addition, a voronoi tessalation computed with a KMeans during the >> > train could be used to avoid testing all the samples in the large n >> > situation. > >> Hum, that won't work for exact k-NN. > > I don't understand. Yes I do believe that it would. The idea is to do a 2 > step predict, in which you first find the k nearest centroid, and then > you do a kNN restricted to the initial training samples that are in the > corresponding clustering. This is a trick to do fast kNN in the high n > limit.
Take the example of 1-NN it can be very well happen that for samples close to the voronoi boundary, the closest neighbor is on the other side of the boundary. -- Olivier http://twitter.com/ogrisel - http://github.com/ogrisel ------------------------------------------------------------------------------ Live Security Virtual Conference Exclusive live event will cover all the ways today's security and threat landscape has changed and how IT managers can respond. Discussions will include endpoint security, mobile security and the latest in malware threats. http://www.accelacomm.com/jaw/sfrnl04242012/114/50122263/ _______________________________________________ Scikit-learn-general mailing list [email protected] https://lists.sourceforge.net/lists/listinfo/scikit-learn-general
