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