I have a problem that is about identifying clusters of highly correlated items. I initially focused on building a model and features that put similar data items close to each other. The main challenge is that I have a case of imbalanced data, as follows:

  • Tens of Millions of items are random and not necessarily correlated.
  • Hundreds of clusters of items (composed of 10-1000s of elements) exist* or may emerge. *I do have partial ground truth for the existing ones.
  • Clusters are very different, in size and properties.

I'd like to return the identified clusters, and the elements within each cluster. F1 should be a good measure.

To move forward, I can think of threshold-based hierarchical clustering. Are there other techniques to consider?

  • 1
    $\begingroup$ Are you thinking along the lines of DBSCAN, OPTICS, BIRCH? $\endgroup$
    – Vlad_Z
    Commented Jun 29, 2020 at 19:36
  • $\begingroup$ Thanks! Would these work efficiently in the imbalanced case? @Vlad_Z $\endgroup$
    – DED
    Commented Jun 29, 2020 at 20:13
  • $\begingroup$ DBSCAN works well on imbalanced data in my experience $\endgroup$ Commented Jun 30, 2020 at 11:59
  • $\begingroup$ If you're measuring F1, I'm assuming you have some ground truth for each of the clusters. In which case, you might look at a nearest neighbor classifier where the ground truth is used as a label... or some variant of nn that works well on imbalanced data. $\endgroup$ Commented Jun 30, 2020 at 12:01
  • $\begingroup$ @ItamarMushkin I have the ground truth for some clusters. but new ones can emerge. $\endgroup$
    – DED
    Commented Jul 17, 2020 at 15:38

1 Answer 1


As you have the partial ground-truth (assuming for ALL clusters) I would suggest following a creative idea derived from Region Growing in image segmentation.

As your clusters are imbalanced in number of the points thus density, they are probably captured by localy using DBSCAN. Run DBSCAN with different parameters and evaluate on capturing your ground-truth into right clusters. The partitioning which gives the best result on your ground-truth evaluation will be your final clustering.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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