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

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?