Quantcast

Incremental Nearest Neighbor

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Incremental Nearest Neighbor

w.richert (Bugzilla)
Hi,

I'm looking for a nearest neighbor lib (accessible from Python) which
increments on-line adding and removing of training data.

The best kNN lib I've come across so far is  approximate
nearest neighbor library (http://www.cs.umd.edu/~mount/ANN/) together with the
Python wrappers created by Barry Wark (posted at scipy-user some time ago).
Howerver, that lib only supports batch mode.

I need an approach with which I can add and remove training samples at
run-time, while always being able to classify/test arriving data according to
the actual realization of the kNN.


Thanks for any help,
wr
_______________________________________________
SciPy-user mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Incremental Nearest Neighbor

Barry Wark
Willi,

You're right that libANN doesn't allow you to update the kd-tree after
construction. Depending on your use, however, you may find that
re-creating the kd-tree with the new set of points is fast enough. If
you really need to dynamically update a kd-tree, you may want to start
at http://citeseer.ist.psu.edu/procopiuc02bkdtree.html. I've never
used this structure, but the Bkd-tree appears to allow dynamically
updating the set of points while retaining the kd-tree's efficient
query performance. I don't know of any python implementations or
wrappers of the Bkd-tree, however.

barry

On Tue, Apr 8, 2008 at 11:45 PM, Willi Richert <[hidden email]> wrote:

> Hi,
>
>  I'm looking for a nearest neighbor lib (accessible from Python) which
>  increments on-line adding and removing of training data.
>
>  The best kNN lib I've come across so far is  approximate
>  nearest neighbor library (http://www.cs.umd.edu/~mount/ANN/) together with the
>  Python wrappers created by Barry Wark (posted at scipy-user some time ago).
>  Howerver, that lib only supports batch mode.
>
>  I need an approach with which I can add and remove training samples at
>  run-time, while always being able to classify/test arriving data according to
>  the actual realization of the kNN.
>
>
>  Thanks for any help,
>  wr
>  _______________________________________________
>  SciPy-user mailing list
>  [hidden email]
>  http://projects.scipy.org/mailman/listinfo/scipy-user
>
_______________________________________________
SciPy-user mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/scipy-user
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: Incremental Nearest Neighbor

Christopher Ellison-2
Barry Wark wrote the following on 04/09/2008 01:03 PM:
> You're right that libANN doesn't allow you to update the kd-tree after
> construction. Depending on your use, however, you may find that
> re-creating the kd-tree with the new set of points is fast enough. If
> you really need to dynamically update a kd-tree, you may want to start
> at http://citeseer.ist.psu.edu/procopiuc02bkdtree.html.

Wow.  This would be quite useful.  Anyone know of a Python implementation?
_______________________________________________
SciPy-user mailing list
[hidden email]
http://projects.scipy.org/mailman/listinfo/scipy-user
Loading...