CODEWITHSUNDEEP
machine-learningcluster-analysisdata-mining
user3061631
user3061631

Reputation: 25

Cluster adjacent points

I have a sequence of xy planes with integer coordinates and each one has points scattered differently over it.

For each plane I would like perform clustering of the points, putting in the same cluster a point that is far from another point in the cluster by less than d (or exactly d).
For example if there is a point P1(x,y) in the cluster and d=1 also

will fall in the same cluster. Graphically:

P9   P3   P4    
   \ |  /
P5 - P1 - P2
   / |  \
P7   P6   P8

Which clustering algorithm is best suited for this task?

Upvotes: 0

Views: 367

Answers (1)

Has QUIT--Anony-Mousse
Has QUIT--Anony-Mousse

Reputation: 77454

This is not so much a clustering problem, but you have your neighbor relation, and you want to compute the transitive closure of this neighbor relation.

This is a much simpler problem, and it has an obvious and efficient straightforward solution (breadth-first search):

While there are unprocessed points:

  1. Initialize a new empty result set.
  2. Working set = choose any one (!) unprocessed point
  3. While the working set is not empty:
    1. Add working set to result set
    2. Mark all points in the working set as processed
    3. Working set = all ''unprocessed'' neighbors of the previous working set
  4. Return the result set as new group.

Upvotes: 1

Related Questions