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

Question

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!

Answer 1

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.