3
$\begingroup$

I have a set of 3D points and I would like to know how to cluster them such that every point in a given cluster is at most a certain distance (let's assume EuclideanDistance for the purpose of this question) from at least one point in that cluster. For example, suppose there are $5$ points {1, 2, 3, 4, 5}, If point $1$ is at most 0.35 units from point $2$, then they belong in the same cluster and if point $3$ is at most 0.35 units from point $2$ or point $1$ then it also belongs to that cluster. If on the other hand, point $4$ is more than 0.35 units from either points $1$, $2$, or $3$, then it doesn't belong in that cluster and so on.

I've scanned through most of the clustering questions but none as specific as this. If there is, I will gladly delete this one.

I've tried using ClusteringComponents, FindClusters and Nearest, but it's not clear how to combine their options to make it work.

Here is a sample of the 3D point set . Assume 0.35 distance separation as the distance criterion. The output should just be a list of lists of 3D points, with each sub-list containing all points in a given cluster. In the data provided each line is the {x, y, z} coordinate of a given point.

$\endgroup$
  • $\begingroup$ One way is to use bisection clustering and use the desired max in-cluster distance in the stopping criteria. What is the expected size of your datasets? $\endgroup$ – Anton Antonov Aug 31 '16 at 9:58
  • $\begingroup$ @AntonAntonov, about 200 to 300 points. $\endgroup$ – RunnyKine Aug 31 '16 at 11:28
  • $\begingroup$ For that data size a better approach might be (1) to make a graph with nodes corresponding to the points and edges between nodes / points within the max distance, and (2) find graph components / clusters. $\endgroup$ – Anton Antonov Aug 31 '16 at 11:45
  • $\begingroup$ @AntonAntonov can you post an answer with that approach? $\endgroup$ – RunnyKine Aug 31 '16 at 12:01
  • $\begingroup$ Just did that -- I hope it is close to what you want. $\endgroup$ – Anton Antonov Aug 31 '16 at 12:26
4
$\begingroup$

For moderate data sizes one approach is:

  1. to make a graph with nodes corresponding to the points and edges between nodes / points within the max distance, and

  2. find graph components / clusters.

The obtained clusters would adhere to the condition by the graph construction. Code for implementing this approach follows.

Get the data linked in the question:

data = Import["http://pastebin.com/raw/zcYqgcUU", "Table", 
  "FieldSeparators" -> " "]

Calculate the distances between the points in a matrix:

distMat = 
  DistanceMatrix[data, DistanceFunction -> EuclideanDistance];
Do[distMat[[i, i]] = \[Infinity], {i, Length[distMat]}];

Optional examination of distances:

Histogram[Flatten[distMat]]

enter image description here

Pick a maximum distance and set elements exceeding it to infinity:

distMat = distMat /. {(x_ /; x > 2.5) :> \[Infinity]};

Make a graph from the obtained weighted adjacency matrix:

gr = WeightedAdjacencyGraph[distMat]

enter image description here

Find clusters / communities in the obtained graph:

CommunityGraphPlot[gr]

enter image description here

Visualize the found clusters in 3D:

ListPointPlot3D[data[[#]] & /@ FindGraphCommunities[gr], 
 PlotStyle -> PointSize[0.02], BoxRatios -> Automatic]

enter image description here

Note, that better or tighter clusters can be obtained using different max distances, and one can investigate for what max distances the graph becomes disconnected.

$\endgroup$
  • $\begingroup$ Thanks a lot. This is indeed what I seek. $\endgroup$ – RunnyKine Aug 31 '16 at 12:45
  • $\begingroup$ @RunnyKine Great -- here are related/similar question and solution. $\endgroup$ – Anton Antonov Aug 31 '16 at 12:57
  • $\begingroup$ Nice, +1 for that one too. $\endgroup$ – RunnyKine Aug 31 '16 at 13:00
1
$\begingroup$

Take for example the following data

data1 = {RandomVariate[NormalDistribution[3, 0.5], 100], 
RandomVariate[NormalDistribution[5, 0.8], 100]} // Transpose;
data2 = {RandomVariate[NormalDistribution[4, 0.4], 100], 
RandomVariate[NormalDistribution[8, 1], 100]} // Transpose;
data = Join[data1, data2] //RandomSample;

which will look something like this

data

I define the following helper functions:


to find the nearest existing neighbors in existing clusters;

nearstPointinGroup[groups_][point_]:=(Nearest[#, point, 1]& /@ groups) //Map@Flatten

to calculate the respective distance to the found nearest neighbor in each cluster and filter points that are farther away than the specified radius

toDistances[point_, radius_][nearestPoints_]:=
(EuclideanDistance[#, point]& /@ nearestPoints) //DeleteCases[#, _?(# > radius &), 2]&

The actual clustering algorithm is implemented with a Module for capturing the clusters

Module[{groups, neighbors, distances, classifier},
groups = <||>;
neighbors[point_] := nearstPointinGroup[groups][point];
distances[point_, radius_] := 
toDistances[point, radius]@neighbors[point];
classifier[point_, radius_] := 
distances[point, radius] //Sort //Keys //First[#, Length@groups + 1] &;
(*note the new second argument to First that gets applied if the list is empty *)

appendToGroups[point_, radius_] := 
If[KeyExistsQ[groups, classifier[point, radius]], (*if Cluster already exists*)
AppendTo[groups[classifier[point, radius]], point], (*add point to cluster*)
AssociateTo[groups, classifier[point, radius] -> {point}]]; (*else put point in new cluster*)

resetGroups := groups = <||>;
getClusters := groups//Values
]

The algorithm can be applied to the data and plotted via

resetGroups; (*reset the algorithm*)
Scan[appendToGroups[#, 1] &, data]; (*feed the data to the algorithm*)
getClusters // ListPlot

clusters

Note that there are several points which are quite close together in the graphic but were sorted into different clusters. This is due to the (random) order in which the points are shown to the algorithm. This could be desirable if the order in which the data points are generated has some intrinsic meaning. The following animation illustrates how the algorithm works:

animation

Showing the points in (random) order to the algorithm does produce varying results both in the way the points are clustered and the number of clusters. One way to make this actually useful might be to provide the algorithm with a initial seed of clusters as in the animation below. The seed used there consists of the four corner points of a unit rectangle. Note how a fifth cluster is formed by the algorithm when no other point within a given distance is found at the respective stage of the run.

animation

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.