# A smart way of clustering a collection of sets based on an inherent hierarchy

Given a collections of sets, which have an inherent but unknown (at runtime) hierarchy, I would like to cluster them based on the sub/super-relationships with respect to their elements. Let me try and illustrate this with a overly simplified example:

Set 1 = {a, b, c, d, e, f}
Set 2 = {a, b}
Set 3 = {a, b, c ,d}
Set 4 = {a, c, d, f, g, h}
Set 5 = {d, f}


In this example, there would be two main clusters with the following relations; cluster 1:

Set 1 $\supset$ Set 3 $\supset$ Set 2;
Set 1 $\supset$ Set 5

... and cluster 2:

Set 4 $\supset$ Set 5

The way I see it, the complications here from a standard clustering approach are;

1) I can not come up with a good measure of correlation between sets that are to be clustered. I was initially thinking of using the number of common elements but then the following scenario (which is essentially rather likely) complicates things:

$_s(Set1 \cap Set2) = 10$

$_s(Set1 \cap Set3) = 10$

$_s(Set3 \cap Set2) = 0$

2) In theory there is no reason for a small set to not be sub-set under more than one superset. This effectively makes any Tree-based data structure unusable, or am I mistaken on this point?

I did some googling, checked on both StackOverflow and here briefly but havent really found something that is useful. Before I start implementing something in Java from scratch I was wondering if anyone had ideas or previous experiences on something like this. If there are libraries/functions one can use for this purpose it would be pretty cool, although I doubt there is something like written in Java.

I know that most of you use R, but as I said, the rest of the software is written in Java so I'd prefer to keep things there, if at all possible.

Thanks,

EDIT: Following @whuber's comments I'll try and clarify the question further. I believe a significant portion of reasoning behind the question got lost when I tried to generalize and abstract the concept. So here it goes:

The sets mentioned above are gene/protein sets, and the elements are then genes/proteins. As these entities work in connection with one another, one speaks of functional groups/sets. However the databases that hold this data usually have a high degree of redundancy, in the sense that Set A usually has all the elements of Set B, C .. etc. My whole project is based on analyzing these sets, and when I am done with the analysis and present my results I have a long set of these sets with associated scores. However highly scoring sets sometimes cluster, they may or may not be in the same super-sets. Thus the need/desire to cluster these in a structure like a dendogram. Thus one can overlay the scoring data, with the hierarchy data.

On a side-note: I was recommended by a colleague of mine to consider spectral clustering, on which I will read more in the coming days to see whether or not the method can be used here or not.

I hope these notes make things more clear now, I'd do my best to further develop the ideas if necessary.

Thanks again!

• In brief, this question in its current form appears to ask "how can I cluster a poset". As your point #1 indicates, this question is not answerable (nor is it of any statistical interest) until you can quantify similarity or dissimilarity of subsets. You have provided a nice example of what you're looking for but all you reveal about the basis of the clustering is that you "imagined it"! So: can you specify what would constitute a "cluster"? – whuber Apr 6 '11 at 15:42
• @whuber: thanks for the link, I was not familiar with the concept, I'll read further into it. Regarding your comments; I realize that the question is perhaps not well formulated, though I think your critique is slightly harsh; because it's not completely irrelevant to want to find underlying hierarchies in the data, is it? Furthermore the reasoning behind the question is to minimize the effects of redundancy in databases from which the data comes. I'll try and clarify the question, giving more details about the underlying problem; and if it's still no good, you can close the question... – posdef Apr 6 '11 at 17:46
• @posdef I apologize for sounding harsh; that was not intended. The point was that the current formulation isn't a statistical problem at all, because essential information is missing, which suggests there's more going on that you haven't yet shared with us. (The poset already is a set of "underlying hierarchies".) – whuber Apr 6 '11 at 18:00
• @whuber: no need to apologize, I recall having a similar "mini-discussion" with you on another question of mine. Such misses in communication seem to happen often in cross-disciplinary projects and people that work in different fields. Please see the edits, and let me know if further clarifications are necessary. If the question is still not a suitable one for this forum, I'd be happy to see referrals or suggestions on how to proceed with the problem. – posdef Apr 6 '11 at 18:40
• I think whuber's point still hasn't been answered: you need some notion of similarity or distance to complete the specification of the problem. – Suresh Venkatasubramanian Apr 8 '11 at 4:10

If I understood you correctly, you have a list of scores for subsets, and you want to identify the items that contribute most to a high score, but you cannot score arbitrary subsets.

This corresponds to a high-dimensional binary regression problem with features $item\in Subset$. You can run a linear or logistic regression on the dataset.

If you want a multiset or partition instead of an itemwise regression, you'll have to specify the goal and scoring model further.

• well it's actually the other way around; I have scores for all sets, independent of the hierarchy. The problem is that, the results given in a table form, is rather large and unintuitive. What I would like to do, is to group the sets, by checking out their relationships with one another, and thus re-creating the hierarchy. In this fashion, one would easily see if a whole branch of the hierarchy has scored high, or if small subsets (leaves of the tree) have scored high. That said, I don't quite follow how regression could be of use here. – posdef Apr 11 '11 at 7:41
• I meant that you have scored subsets of the set of all elements. Some form of binary regression will assign scores to the individual elements. The form of regression depends on how you model the score of a set depending on its elements. You cannot build a unique hierarchy of sets, since you stated some overlapping sets are not in a hierarchical relationship. You could have an inclusion graph, but that's not a partition and has little to do with clustering. – sesqu Apr 12 '11 at 14:29