469,592 Members | 1,713 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 469,592 developers. It's quick & easy.

Fast kNN from python

Hi!

I am looking for a Python implementation or bindings to a library that
can quickly find k-Nearest Neighbors given an arbitrary distance
metric between objects. Specifically, I have an "edit distance"
between objects that is written in Python.

I haven't looked at the methods in detail but I think I'm looking for
one of the data structures listed on http://en.wikipedia.org/wiki/Metric_trees
(i.e. vp-trees, cover trees, m-trees or bk trees). But I might be
wrong. An approximate kNN would also work.

If there doesn't exist such an implementation yet, any advice on a
library I can wrap myself would also be appreciated.

Thanks!
Janto

PS Before anyone suggests it, I can't use the library at
http://www.cs.umd.edu/~mount/ANN/ as it assumes Minkowski distance
functions.

Aug 14 '07 #1
5 7957
Janto Dreijer wrote:
I am looking for a Python implementation or bindings to a library that
can quickly find k-Nearest Neighbors given an arbitrary distance
metric between objects. Specifically, I have an "edit distance"
between objects that is written in Python.
Orange? See http://www.ailab.si/orange/ - not sure about speed, but
quite a few parts of it are written in C, and it does kNN.

Tim C
Aug 14 '07 #2
Hello,
I am looking for a Python implementation or bindings to a library that
can quickly find k-Nearest Neighbors given an arbitrary distance
metric between objects. Specifically, I have an "edit distance"
between objects that is written in Python.
First Google search for "k-Nearest Neighbors python", yielded
http://people.revoledu.com/kardi/tut...resources.html which
pointed to http://biopython.org/DIST/docs/api/p...NN-module.html

HTH,
--
Miki <mi*********@gmail.com>
http://pythonwise.blogspot.com

Aug 14 '07 #3
On Aug 14, 6:16 am, Janto Dreijer <jan...@gmail.comwrote:
Hi!

I am looking for a Python implementation or bindings to a library that
can quickly find k-Nearest Neighbors given an arbitrary distance
metric between objects. Specifically, I have an "edit distance"
between objects that is written in Python.

I haven't looked at the methods in detail but I think I'm looking for
one of the data structures listed onhttp://en.wikipedia.org/wiki/Metric_trees
(i.e. vp-trees, cover trees, m-trees or bk trees). But I might be
wrong. An approximate kNN would also work.

If there doesn't exist such an implementation yet, any advice on a
library I can wrap myself would also be appreciated.

Thanks!
Janto
Have you looked at using Rpy and R? There are probably several knn
implementations that then become accessible to you (although I haven't
checked recently).

Sean
Aug 14 '07 #4
On Aug 14, 8:44 pm, Miki <miki.teb...@gmail.comwrote:
Hello,
I am looking for a Python implementation or bindings to a library that
can quickly find k-Nearest Neighbors given an arbitrary distance
metric between objects. Specifically, I have an "edit distance"
between objects that is written in Python.

First Google search for "k-Nearest Neighbors python", yieldedhttp://people.revoledu.com/kardi/tutorial/KNN/resources.html which
pointed tohttp://biopython.org/DIST/docs/api/public/Bio.kNN-module.html

HTH,
--
Miki <miki.teb...@gmail.com>http://pythonwise.blogspot.com
Thanks. Indeed, I did see that page. Unfortunately biopython's knn
does a brute force search for the nearest k and is therefore way too
slow.

Janto

Aug 14 '07 #5
On Aug 14, 9:27 pm, Sean Davis <seand...@gmail.comwrote:
On Aug 14, 6:16 am, Janto Dreijer <jan...@gmail.comwrote:
Hi!
I am looking for a Python implementation or bindings to a library that
can quickly find k-Nearest Neighbors given an arbitrary distance
metric between objects. Specifically, I have an "edit distance"
between objects that is written in Python.
I haven't looked at the methods in detail but I think I'm looking for
one of the data structures listed onhttp://en.wikipedia.org/wiki/Metric_trees
(i.e. vp-trees, cover trees, m-trees or bk trees). But I might be
wrong. An approximatekNNwould also work.
If there doesn't exist such an implementation yet, any advice on a
library I can wrap myself would also be appreciated.
Thanks!
Janto

Have you looked at using Rpy and R? There are probably severalknn
implementations that then become accessible to you (although I haven't
checked recently).

Sean
Interesting. I have not looked at that. I can't really find an R
package that does what I want, so any suggestions are appreciated.

Janto

Aug 15 '07 #6

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

4 posts views Thread by Andreas Neudecker | last post: by
5 posts views Thread by K. N. | last post: by
11 posts views Thread by Sebastian Krause | last post: by
114 posts views Thread by Maurice LING | last post: by
7 posts views Thread by Johnny Lee | last post: by
21 posts views Thread by mm | last post: by
28 posts views Thread by windandwaves | last post: by
71 posts views Thread by Jack | last post: by
68 posts views Thread by Santiago Romero | last post: by
39 posts views Thread by cm_gui | last post: by
reply views Thread by suresh191 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.