# Clustering methods based off set membership

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.

• 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]"? – missingdataguy May 27 '15 at 17:13
• 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. – 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!

Let the points in the set $S$ be $A_1, \dots, A_n$.
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.