Clustering list of list of integers

Question

I have ~100 sets of samples with integer IDs. For example, 3 of them could be:

a = [0, 1, 3, 4, 6...]
b = [1, 5, 9, 102...]
c = [1, 7, 10, 42...]

I am looking to cluster/group together these sets such that within each cluster, all the elements have at least X% common IDs with each other, where X is an input parameter.

I was thinking about using Agglomerative Clustering with 1 - %X as the distance metric, but was unsure how to modify it to account for each clusters 'information' being the common set of IDs between sets within it. Any advice would be appreciated (including a different technique/algorithm clustering was just what came to mind)

Answer 1

Welcome to the community!

I would use the Mutual Information between two sets as the criterion of similarity. In your special case, set the mutual information of those sets whose intersection is less than X% to $0$. Run your clustering and see what comes out. With the same similarity matrix, you can also construct a weighted graph and cluster nodes (which is called Community Detection). This link gives you a proper overview starting from slide 37 and in slide 48 you find your own idea! If you have more questions about Community Detection, e.g. implementation, please drop a comment here.

Answer 2

So if I got you right you wanna have is something like an overlap matrix O, i.e.:

O[i,j] = len(set(a[i]) & set(a[j]))/len(a[i]) # supposing len(a[i])==len(a[j]) and len(a[i]) == len(set(a[i])), saying all samples have same length and no repeated values

Here a is the data matrix with each row being one sample.

To avoid that pairs of samples being clustered together which have less than %X overlap you can set the overlap to zero for these pairs:

O[O < X_perc] = 0

Now, if you use any clustering approach that works with dissimilarity matrices you get some clustering that sort of respects your condition ("all the elements have at least X% common IDs with each other"). The key problem, however, is that your condition is dependent on the grouping itself and there is no guarantee for your problem to find a solution where all samples are clustered nicely given the condition. Now, to avoid a crazy recursive combinatoric search to some solution that is not even guaranteed to be existing I would just use some clustering (probably agglomerative as you suggested) on the D=1-O dissimilarity matrix (did you mean that by 1-X% ?) and checkout the dendrogram. I would set the threshold for the cluster labeling at some value in the linkage at where a reasonable set of samples is not part of a singular cluster (having only that data point). Finally, for each cluster I would remove all the samples which do not fulfill your condition to end up with "clean" clusters.