# 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!

-

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