So most of the clustering algorithms I've looked at are based on the distance between points. I was wondering if anyone knows any simple clustering algorithms based off points making up a set. (example below)

I have the set:

[[0, 9], [3, 4], [3, 7], [4, 7], [5, 6], [5, 8], [6, 8]]

I want a clustering algorithm to link the following points together.

[3, 4], [3, 7], [4, 7]

[5, 6], [5, 8], [6, 8]

[0, 9]

I'm not sure what would happen if there was a link between the two clusters, [5,3] or if 3 points only had two links: [1,2] and [2,3], but I guess an algorithm would make some distinction.

  • $\begingroup$ What do you mean by "if there was a link between the two clusters, [5,3] or if 3 points only had two links: [1,2] and [2,3]"? $\endgroup$ – missingdataguy May 27 '15 at 17:13
  • $\begingroup$ If I had the point [5,3] included in the set, my first cluster, [3, 4], [3, 7], [4, 7], would be linked with my second cluster, [5, 6], [5, 8], [6, 8] Also, if [1,2] and [2,3] link together, I don't know where the distinction should lie as to whether that forms a cluster or not. $\endgroup$ – Froblinkin May 27 '15 at 17:40

This is not different.

Your "set" is nothing else but a binary distance function, which is 0 if the two points are in your "set", and 1 otherwise! So your proposal is just a special case of distance based clustering!

Then run single-linkage or complete-linkage or another distance-based algorithm to get your desired result.


I would do the following:

Let the points in the set $S$ be $A_1, \dots, A_n$.

  1. Intially put each point as its own cluster.
  2. Find the first pairwise intersection $A_j \cap A_k$ that has cardinality at least $1$ and form a cluster $B_1 = A_j \cup A_k$.
  3. Find the intersection of the elements of $B_1$ and the rest of the $A_j$. If the cardinality is at least $1$, then $B_1 := B_1 \cup A_j$.
  4. Repeat for $S \ \backslash B_1$.
  5. If $A_i \cap A_j = \emptyset$ for all $j \neq i$ then $A_i$ is its own cluster.

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.