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 Jun 29 '20 at 19:36
  • $\begingroup$ Thanks! Would these work efficiently in the imbalanced case? @Vlad_Z $\endgroup$ – DED Jun 29 '20 at 20:13
  • $\begingroup$ DBSCAN works well on imbalanced data in my experience $\endgroup$ – Itamar Mushkin Jun 30 '20 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$ – Itamar Mushkin Jun 30 '20 at 12:01
  • $\begingroup$ @ItamarMushkin I have the ground truth for some clusters. but new ones can emerge. $\endgroup$ – DED Jul 17 '20 at 15:38

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, privacy policy and cookie policy

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