I am looking for a clustering algorithm for the purposes of combining routing information.

Suppose we have the following sets:





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).


You can use any clustering technique by defining an appropriate distance metric. In the case of set data, one common distance metric is Jaccard. Jaccard Index is defined as the size of the intersection divided by the size of the union.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.