473,383 Members | 1,725 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,383 software developers and data experts.

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 8107
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

4
by: Andreas Neudecker | last post by:
Hi. I have seen some discussions going on about making Python code faster and several measures looked fairly 'esoteric' to me (i.e.: you need to know a lot of background things to even KNOW...
5
by: K. N. | last post by:
Is there any good and fast Python module for XSLT processing ? I'm going to use XML and XSLT to generate web pages, so I need XSLT processor that will be able to transform for example a DOM object...
11
by: Sebastian Krause | last post by:
Hello, I tried to read in some large ascii files (200MB-2GB) in Python using scipy.io.read_array, but it did not work as I expected. The whole idea was to find a fast Python routine to read in...
114
by: Maurice LING | last post by:
This may be a dumb thing to ask, but besides the penalty for dynamic typing, is there any other real reasons that Python is slower than Java? maurice
7
by: Johnny Lee | last post by:
Hi, First, I want to know whether the python interpreter translate the code directly into machine code, or translate it into C then into machine code? Second, if the codes are translated directly...
21
by: mm | last post by:
(Yes, I konw whats an object is...) BTW. I did a translation of a pi callculation programm in C to Python. (Do it by your own... ;-) -------- Calc PI for 800 digs(?). (german: Stellen) ------...
28
by: windandwaves | last post by:
Can someone tell me why I should learn python? I am a webdeveloper, but I often see Python mentioned and I am curious to find out what I am missing out on. Thank you Nicolaas
71
by: Jack | last post by:
I understand that the standard Python distribution is considered the C-Python. Howerver, the current C-Python is really a combination of C and Python implementation. There are about 2000 Python...
68
by: Santiago Romero | last post by:
( Surely if this question has been asked for a zillion of times... ) ( and sorry for my english! ) I'm impressed with python. I'm very happy with the language and I find Python+Pygame a very...
39
by: cm_gui | last post by:
Python is slow. Almost all of the web applications written in Python are slow. Zope/Plone is slow, sloow, so very slooow. Even Google Apps is not faster. Neither is Youtube. Facebook and...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...
0
by: ryjfgjl | last post by:
In our work, we often need to import Excel data into databases (such as MySQL, SQL Server, Oracle) for data analysis and processing. Usually, we use database tools like Navicat or the Excel import...
0
by: taylorcarr | last post by:
A Canon printer is a smart device known for being advanced, efficient, and reliable. It is designed for home, office, and hybrid workspace use and can also be used for a variety of purposes. However,...
0
by: Charles Arthur | last post by:
How do i turn on java script on a villaon, callus and itel keypad mobile phone
0
by: emmanuelkatto | last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud. Please let me know. Thanks! Emmanuel
0
BarryA
by: BarryA | last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
0
by: Hystou | last post by:
There are some requirements for setting up RAID: 1. The motherboard and BIOS support RAID configuration. 2. The motherboard has 2 or more available SATA protocol SSD/HDD slots (including MSATA, M.2...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.