Finding Neighboors
Hi, I wanted to know if there was a module in scipy that is able to find the k-neighboors of a point ? If so, is there an optimized one - tree-based search - ? If not, I'm doing the optimized version... Matthieu
Biopython has an implementation of KD-trees -- that might be a good starting place. http://biopython.org/DIST/docs/api/public/trees.html http://biopython.org/DIST/docs/api/public/Bio.KDTree-module.html On Apr 17, 2007, at 5:41 AM, Matthieu Brucher wrote:
Hi,
I wanted to know if there was a module in scipy that is able to find the k-neighboors of a point ? If so, is there an optimized one - tree-based search - ? If not, I'm doing the optimized version...
Matthieu _______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
On Tue, 17 Apr 2007, Matthieu Brucher apparently wrote:
I wanted to know if there was a module in scipy that is able to find the k-neighboors of a point ? If so, is there an optimized one - tree-based search - ? If not, I'm doing the optimized version.
Hi Matthieu, Where did you go with this? Thanks! Alan
Hi, I have an implementation, but it depends on my own matrix library... That's a stopper... But it works. I do not know the other templated matrix libraries very well, but I'd say I do not need much to make it work with another library. Matthieu 2007/8/1, Alan G Isaac <aisaac@american.edu>:
On Tue, 17 Apr 2007, Matthieu Brucher apparently wrote:
I wanted to know if there was a module in scipy that is able to find the k-neighboors of a point ? If so, is there an optimized one - tree-based search - ? If not, I'm doing the optimized version.
Hi Matthieu,
Where did you go with this?
Thanks! Alan
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
Hi, you might want to take a look at kd-trees. No implementation in scipy, but it should not be too hard to achieve. As far as i can remember its definition in wikipedia includes some python code. Just my 2 cents :) On 8/1/07, Matthieu Brucher <matthieu.brucher@gmail.com> wrote:
Hi,
I have an implementation, but it depends on my own matrix library... That's a stopper... But it works. I do not know the other templated matrix libraries very well, but I'd say I do not need much to make it work with another library.
Matthieu
2007/8/1, Alan G Isaac <aisaac@american.edu>:
On Tue, 17 Apr 2007, Matthieu Brucher apparently wrote:
I wanted to know if there was a module in scipy that is able to find the k-neighboors of a point ? If so, is there an optimized one - tree-based search - ? If not, I'm doing the optimized version.
Hi Matthieu,
Where did you go with this?
Thanks! Alan
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
-- Emanuele Zattin --------------------------------------------------- -I don't have to know an answer. I don't feel frightened by not knowing things; by being lost in a mysterious universe without any purpose — which is the way it really is, as far as I can tell, possibly. It doesn't frighten me.- Richard Feynman
2007/8/1, Emanuele Zattin <emanuelez@gmail.com>:
Hi, you might want to take a look at kd-trees. No implementation in scipy, but it should not be too hard to achieve. As far as i can remember its definition in wikipedia includes some python code. Just my 2 cents :)
Thank you for the link ;) As far as I see, I did not implement a real kd-tree, I always split dimensions in two equal parts. It is true I can make a better partition with not much recoding (instead of splitting at the middle, I split at the medians of the points, it can be a balanced kd-tree if the points are uniformy reparted). I will not implement a full kd-tree with adding or removing points, I do not have the time :( What is more, I only implemented it for K-neighboors or Parzen Windows, and for this, I don't need to make the tree appear in Python, everything is in C++ (I had an implementation in Python, but it was too slow because of the computation of the nearest zone to analyze, it is far better with a std::map). Matthieu
Note that BioPython has a decent KdTree implementation in C. Perhaps that might work for you. -jelle
If you are using a data set that is static, i.e. you are not adding or deleting data points, then you should check out nearest neighbor searches using slices along various directions. It's *much* easier to code than k-d trees and is about as efficient. The reference is, Nene and Nayer, IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 9, SEPTEMBER 1997, pg. 989 If your data is changing a lot as you are doing searches, then as I understand it, k-d trees are better to use since you can delete and insert nodes easily. --- Emanuele Zattin <emanuelez@gmail.com> wrote:
Hi, you might want to take a look at kd-trees. No implementation in scipy, but it should not be too hard to achieve. As far as i can remember its definition in wikipedia includes some python code. Just my 2 cents :)
-- Lou Pecora, my views are my own. --------------- Great spirits have always encountered violent opposition from mediocre minds. -Albert Einstein ____________________________________________________________________________________ Park yourself in front of a world of choices in alternative vehicles. Visit the Yahoo! Auto Green Center. http://autos.yahoo.com/green_center/
2007/8/1, Lou Pecora <lou_boog2000@yahoo.com>:
If you are using a data set that is static, i.e. you are not adding or deleting data points, then you should check out nearest neighbor searches using slices along various directions. It's *much* easier to code than k-d trees and is about as efficient. The reference is,
Nene and Nayer, IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, VOL. 19, NO. 9, SEPTEMBER 1997, pg. 989
If your data is changing a lot as you are doing searches, then as I understand it, k-d trees are better to use since you can delete and insert nodes easily.
Isn't that just what kd-trees do ? If you take several slices around a point, you must know which points belong to each slice, thus making a tree anyway, no ? Matthieu
Hi all, Catching this conversation late. As jelle points out, BioPython has a k-d tree implemetation, but it hasn't been converted to numpy yet (I think it still uses Numeric). I've written a SWIG (with numpy type maps) wrapper around the Approximate Nearest Neighbor library (http://www.cs.umd.edu/~mount/ANN/), which includes both exact and approximate k-d tree searches. Email me off list if you would like a copy of the swig definition files. If there's interest, I will send it on to the ANN writers for inclusion in the library itself. Barry On 7/31/07, Emanuele Zattin <emanuelez@gmail.com> wrote:
Hi, you might want to take a look at kd-trees. No implementation in scipy, but it should not be too hard to achieve. As far as i can remember its definition in wikipedia includes some python code. Just my 2 cents :)
On 8/1/07, Matthieu Brucher <matthieu.brucher@gmail.com> wrote:
Hi,
I have an implementation, but it depends on my own matrix library... That's a stopper... But it works. I do not know the other templated matrix libraries very well, but I'd say I do not need much to make it work with another library.
Matthieu
2007/8/1, Alan G Isaac <aisaac@american.edu>:
On Tue, 17 Apr 2007, Matthieu Brucher apparently wrote:
I wanted to know if there was a module in scipy that is able to find the k-neighboors of a point ? If so, is there an optimized one - tree-based search - ? If not, I'm doing the optimized version.
Hi Matthieu,
Where did you go with this?
Thanks! Alan
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
-- Emanuele Zattin --------------------------------------------------- -I don't have to know an answer. I don't feel frightened by not knowing things; by being lost in a mysterious universe without any purpose — which is the way it really is, as far as I can tell, possibly. It doesn't frighten me.- Richard Feynman _______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
Terrific! ANN seems like a very useful module Barry! Thanks for pointing out! Cheers, -jelle
participants (7)
-
Alan G Isaac -
Barry Wark -
Emanuele Zattin -
jelle -
Lou Pecora -
Matthieu Brucher -
Zachary Pincus