Re: 3D Cluster Detection

*To*: mathgroup at smc.vnet.net*Subject*: [mg2448] Re: [mg2413] 3D Cluster Detection*From*: Allan Hayes <hay at haystack.demon.co.uk>*Date*: Wed, 8 Nov 1995 23:45:05 -0500

Fergal Shevlin <fshevlin at maths.tcd.ie> >Subject: [mg2413] 3D Cluster Detection Asks about dealing with clusters of points in R3(message attached) Fergal: The function Clusters,below might be of use. You can also use the function ConnectedComponents from the standard package DiscreteMath`Combinatorica`, but some preliminary setting up is needed and the final calculation is much slower than with this more limited function. The supporting function, Split, seems to be very useful. Clusters::usage = "Clusters[lst,d] for a list of points in Rn gives the equivalence classes of the equivalence relation generated by the relation x ~ y <=> Max[Abs[x - y]] <=d Clusters[lst,d] for a list, lst, of non-complex numbers works similarly.\n Clusters[{{1,0},{1,9},{8,9},{3,2}},2] -->\n {{{1, 0}, {3, 2}}, {{1, 9}}, {{8, 9}}} "; Split::usage = "Split[lst] for a list lst splits lst into sublists at each change in entry: {1,2,2,2,3,3} gives {{1},{2,2,2},{3,3}}. Split[lst,crit] splits between x and y when crit[x,y] is not True."; Split[e_, tst_:SameQ]:= Module[{con,A}, con[{x___,u:A[___,m_]},p_]/;tst[m,p] := {x,A[u,p]}; con[u:{___,A[___,m_]},p_] := {u,A[p]}; con[{},p_] = {A[p]}; Apply[List,Flatten/@Flatten[Fold[con,{}, e]],1] ] clusters1[d_][lst_] := Split[ Sort[lst], (#2[[1]]-#1[[1]] <=d)&]; Clusters[lst_?VectorQ,d_] := clusters1[d][lst] Clusters[lst_?MatrixQ,d_] := Nest[ Map[RotateLeft,Flatten[clusters1[d]/@#,1],{2}]&, {lst}, Length[First[lst]] ] Allan Hayes hay at haystack.demon.co.uk *********** Begin forwarded message: >From: Fergal Shevlin <fshevlin at maths.tcd.ie> >To: mathgroup at smc.vnet.net >Subject: [mg2413] 3D Cluster Detection >Organization: Dept. of Maths, Trinity College, Dublin, Ireland. Hello, I have a list of Real 3D points, each coordinate having a value between 0 and 2 Pi. Within this list there are several "clusters" of points, i.e. the coordinates agree to several decimal places. Each cluster is quite distinct from the other, for example when I view the points with ScatterPlot3D[pointlist] I see 4 points, despite the fact that there are hundreds in the list. Can anybody suggest a means of automatically detecting the means or modes of these clusters? Thanks in advance, Fergal. -- ==================================================================== Fergal Shevlin Phone: +353-1-6081209 Fax: 6772204 Dept. of Computer Science http://www.cs.tcd.ie/ Trinity College, Dublin 2, Ireland. Fergal.Shevlin at cs.tcd.ie