Dear All, I hope this will not sound too off-topic. Without going into details, I am simulating the behavior of a set of particles interacting with a short-ranged, strongly binding potential. I start with a number N of particles which undergo collisions with each other and, in doing so, they stick giving rise to clusters. The code which does that is not written in Python, but it returns the positions of these particles in space. As time goes on, more and more particles coagulate around one of these clusters. Eventually, they will all end up in the same cluster. Two particles are considered to be bounded if their distance falls below a certain threshold d. A cluster is nothing else than a group of particles all directly or indirectly bound together. Having said so, I now need an efficient algorithm to look for clusters, since at the very least I need to be able to count them to study how the number of clusters evolve in time. Is there anything suitable for this already implemented in SciPy? I wonder if people in Astronomy have similar problems if they need e.g. to detect/study clusters of stars. Simply I would like not to re-invent the wheel and it goes without saying that any suggestions here are really appreciated. Many thanks and a nice Xmas break to everybody on this list. Lorenzo
Have you tried looking into the hierarchical clustering algorithms that are in the biopython package? http://www.inb.mu-luebeck.de/biosoft/biopython/api/Bio/Tools/Clustering/kMea... Cheers, William On Dec 26, 2007 7:28 PM, Lorenzo Isella <lorenzo.isella@gmail.com> wrote:
Dear All, I hope this will not sound too off-topic. Without going into details, I am simulating the behavior of a set of particles interacting with a short-ranged, strongly binding potential. I start with a number N of particles which undergo collisions with each other and, in doing so, they stick giving rise to clusters. The code which does that is not written in Python, but it returns the positions of these particles in space. As time goes on, more and more particles coagulate around one of these clusters. Eventually, they will all end up in the same cluster. Two particles are considered to be bounded if their distance falls below a certain threshold d. A cluster is nothing else than a group of particles all directly or indirectly bound together. Having said so, I now need an efficient algorithm to look for clusters, since at the very least I need to be able to count them to study how the number of clusters evolve in time. Is there anything suitable for this already implemented in SciPy? I wonder if people in Astronomy have similar problems if they need e.g. to detect/study clusters of stars. Simply I would like not to re-invent the wheel and it goes without saying that any suggestions here are really appreciated. Many thanks and a nice Xmas break to everybody on this list.
Lorenzo
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
On 26-Dec-07, at 7:28 PM, Lorenzo Isella wrote:
Dear All, I hope this will not sound too off-topic. Without going into details, I am simulating the behavior of a set of particles interacting with a short-ranged, strongly binding potential. I start with a number N of particles which undergo collisions with each other and, in doing so, they stick giving rise to clusters. The code which does that is not written in Python, but it returns the positions of these particles in space. As time goes on, more and more particles coagulate around one of these clusters. Eventually, they will all end up in the same cluster. Two particles are considered to be bounded if their distance falls below a certain threshold d. A cluster is nothing else than a group of particles all directly or indirectly bound together.
This doesn't sound like what would typically be considered a Do you have code that produces the (N^2 - N)/2 distances between pairs of particles? How large is N? If it's small enough, turning it into a NumPy array should be straightforward, and then thresholding at d is one line of code. Then what you end up with is a boolean matrix that where the (i,j) entry denotes that i and j are in a cluster together. This can be thought of as a graph or network where the nodes are particles and connections / links / edges exist between those particles that are in a cluster together. Once you have this your problem is what graph theorists would call identifying the "connected components", which is a well-studied problem and can be done fairly easily, Google "finding connected components" or pick up any algorithms textbook at your local library such as the Cormen et al "Introduction to Algorithms". I'm not in a position to comment on whether there's something like this already in SciPy, as I really don't know. However, finding connected components of a graph (i.e. your clusters) is a very well studied problem in the computer science (namely graph theory) literature, and the algorithms are simple enough that less than 20 lines of Python should do the trick provided the distance matrix is manageable. Regards, David
On 27-Dec-07, at 1:24 AM, David Warde-Farley wrote:
This doesn't sound like what would typically be considered a
This should read, "This doesn't sound like what would typically be considered a clustering problem." What I meant is, "clustering" usually means finding a natural way of grouping the data (either hierarchically or non-hierarchically) where you only have some notion of similarity or distance to work with. ] In your problem, your similarity metric is essentially binary ("are you less than d away from each other", yes or no) and so it reduces to a rather graph-theoretic problem. That said, if your number of particles is particularly large, Nathan's suggestion of a kd-tree solution sounds like it's on the right track. "Locality sensitive hashing" comes to mind, which is basically a fast way of finding the nearest neighbour of a given point -- if you knew this then you'd be able to tell whether any point at all was within d, since if the nearest neighbour isn't then none of them are. Take a look at http://web.mit.edu/andoni/www/LSH/index.html Cheers, David
On Thu, Dec 27, 2007 at 01:24:26AM -0500, David Warde-Farley wrote:
Once you have this your problem is what graph theorists would call identifying the "connected components", which is a well-studied problem and can be done fairly easily, Google "finding connected components" or pick up any algorithms textbook at your local library such as the Cormen et al "Introduction to Algorithms".
I have implemented the O(N) algorithm described in Christophe Fiorio and Jens Gustedt, "Two linear time Union-Find strategies for image processing", Theoretical Computer Science 154 (1996), pp. 165-181. and Kensheng Wu, Ekow Otoo and Arie Shoshani, "Optimizing connected component labeling algorithms", Paper LBNL-56864, 2005, Lawrence Berkeley National Laboratory (University of California), http://repositories.cdlib.org/lbnl/LBNL-56864. The code can be found at http://mentat.za.net/source/connected_components.tar.bz2 Run 'scons' to compile (I can send a setup.py if necessary). Typical usage: x = N.array([[0, 0, 3, 2, 1, 9], [0, 1, 1, 9, 2, 9], [0, 0, 1, 9, 9, 9], [3, 1, 1, 5, 3, 0]]) labels = connected_components.linear(x) Result: [[0, 0, 1, 2, 3, 4], [0, 5, 5, 4, 6, 4], [0, 0, 5, 4, 4, 4], [7, 5, 5, 8, 9, 10]]) The given source searches for neighbours that have the same values, but this can easily be modified to look for values within a certain difference range. Regards Stéfan
On Dec 26, 2007 6:28 PM, Lorenzo Isella <lorenzo.isella@gmail.com> wrote:
Two particles are considered to be bounded if their distance falls below a certain threshold d.
Assuming d is the same for all pairs of contacts you should probably use spatial hashing. I had a similar problem in the simulation of granular materials and found spatial hashing to be the fastest approach. By spatial hashing I mean that to each point (x,y,z) you associate the integer tuple ( floor( x/d ), (floor( y/d ), (floor( z/d ) ). When looking for all the neighbors of a point you simply look at all 27 neighboring tuples. You could do this with Python dictionaries, but you'll probably prefer something like the STL hash_map or Google's sparsehash library. If d varies then a k-D tree is probably your best best.
A cluster is nothing else than a group of particles all directly or indirectly bound together. Having said so, I now need an efficient algorithm to look for clusters, since at the very least I need to be able to count them to study how the number of clusters evolve in time. Is there anything suitable for this already implemented in SciPy? I wonder if people in Astronomy have similar problems if they need e.g. to detect/study clusters of stars. Simply I would like not to re-invent the wheel and it goes without saying that any suggestions here are really appreciated. Many thanks and a nice Xmas break to everybody on this list.
I don't think SciPy has the functionality you need. The cluster module has k-means stuff, but I don't think that will help you. -- Nathan Bell wnbell@gmail.com
Hi, Sounds like a pseudo correlation clustering problem, isn't ? It's not too hard to create the clusters once you have the similarity matrix. You can make a loop and for every point not labeled, you cluster around it every point that are similar. This way you get a good approximation of your optimal correlation problem (don't remember which article demonstrates it). Matthieu 2007/12/27, Lorenzo Isella <lorenzo.isella@gmail.com>:
Dear All, I hope this will not sound too off-topic. Without going into details, I am simulating the behavior of a set of particles interacting with a short-ranged, strongly binding potential. I start with a number N of particles which undergo collisions with each other and, in doing so, they stick giving rise to clusters. The code which does that is not written in Python, but it returns the positions of these particles in space. As time goes on, more and more particles coagulate around one of these clusters. Eventually, they will all end up in the same cluster. Two particles are considered to be bounded if their distance falls below a certain threshold d. A cluster is nothing else than a group of particles all directly or indirectly bound together. Having said so, I now need an efficient algorithm to look for clusters, since at the very least I need to be able to count them to study how the number of clusters evolve in time. Is there anything suitable for this already implemented in SciPy? I wonder if people in Astronomy have similar problems if they need e.g. to detect/study clusters of stars. Simply I would like not to re-invent the wheel and it goes without saying that any suggestions here are really appreciated. Many thanks and a nice Xmas break to everybody on this list.
Lorenzo
_______________________________________________ SciPy-user mailing list SciPy-user@scipy.org http://projects.scipy.org/mailman/listinfo/scipy-user
-- French PhD student Website : http://matthieu-brucher.developpez.com/ Blogs : http://matt.eifelle.com and http://blog.developpez.com/?blog=92 LinkedIn : http://www.linkedin.com/in/matthieubrucher
participants (6)
-
David Warde-Farley -
Lorenzo Isella -
Matthieu Brucher -
Nathan Bell -
Stefan van der Walt -
william ratcliff