I am looking for a clustering algorithm for the purposes of combining routing information.
Suppose we have the following sets:
A={1,2,3,4,5}
B={2,3,4,6}
C={3,4,7,8}
D={8,9,10,11}
If we want 3 groups, you could have arranged a variety of combinations ({1A;2B;3CD},{1A;2BC;3D}, etc.). If we consider the overlap in elements as a scoring metric, something like 1A, 2B, and 3CD would have a score of 2 since only one element (8) overlaps between C and D. However, if we group 1AB, 2C, 3D then the score would be 6 since three elements (2,3,4) overlap between A and B. If we specified 2 groups, you might get even higher: 1AB, 2CD with a score of 7. I should also mention that the initial sets can also be weighted, representing multiple occurences of the set equal to its weight. The output of the algorithm would provide a table of set assignments to a group index. Is there any algorithm that can accomplish this efficiently (there are hundreds of million records to cluster).
I have looked into the Apriori algorithm, which appears to be doing something similar but doesn't provide final clusters (just counts of instances for overlaps, it doesn't do the assignment; though I could be misunderstanding). Other similar threads have taken an approach of conducting k-means clustering based on a distance metric of overlap--however this doesn't seem quite right either because it doesn't tell you which elements are overlapping (again I could be missing something here). It seems like hierarchical (agglomerative) clustering would be a good approach in principle, but again it is unclear what metric would be clustered on (again since overlaps don't actually contain any information about the elements in the sets).
