[SciPy-user] (OT) Grouping of data points.

Bill Dandreta wjdandreta at att.net
Thu Dec 1 00:06:35 CST 2005


Stephen Walton wrote:

>You need graph theory.  I just did a similar project (in MATLAB, but 
>anyway) having to do with sunspots.  I needed to put sunspots into 
>groups by finding sunspots which were "close" in latitude and 
>longitude.  The eventual algorithm looked like this:
>
>1.  For each point i, compute its distance from point j.  (This part of 
>the algorithm is n**2, unfortunately.)  Set A[i,j] and A[j,i] to 1 if 
>the distance is less than some value, and 0 if it is greater.  A is in 
>fact an adjacency graph in MATLAB-ese, where A[i,j] is nonzero if vertex 
>i of a graph is connected to vertex j by an edge.  "Distance" here can 
>have any definition of course;  it doesn't have to be Cartesian.
>
>2. Find the components in the resulting graph, defined as those sets of 
>vertices which are in fact connected.  The algorithm for doing this is 
>at http://www.ececs.uc.edu/~gpurdy/lec20.html, in section 20.2.
>
>I also recommend the graph theory tutorial at 
>http://www.utm.edu/departments/math/graph.
>
Thanks Stephen, It looks like graph theory might fit the bill. The links 
look interesting but are over my head right now. It will take some 
studying for me to come up to speed.

Bill



More information about the SciPy-user mailing list