[TASK] Post HDBSCAN merge tasks

[divyegala]

These are tasks for cuML's HDBSCAN implementation after 21.06 release

• Move HDBSCAN out of experimental (this can be done after sections 1, 2, and 3 below are complete).

1. Necessary tech debt / cleanup (e.g. need to have)

• Reduce number of clusters in output struct after cluster selection occurs ([REVIEW] Reducing cluster size to number of selected clusters. Returning stability scores #3987)
• Output stability scores (e.g. persistent clusters Python attribute) ([REVIEW] Reducing cluster size to number of selected clusters. Returning stability scores #3987)
• Use lazy-loaded / @Property for plotting tools in estimator. ([REVIEW] HDBSCAN: Lazy-loading (and caching) condensed & single-linkage tree objects #3986)

2. Testing / Correctness verification

• Verify cluster_selection_method=eom for empty cluster tree and allow_single_cluster=True
• Add cluster condensing gtests with contrived examples ([REVIEW] Exposing condensed hierarchy through cython for easier unit-level testing #4004)
• Add docs describing for users when the GPU impl might not match CPU (due to difference in KNN and MST) #4042
• Allow reference HDBSCAN's CondensedTree object to be accepted to cuML and end-to-end run extract_clusters from that object. This is to help with robust testing of HDBSCAN by helping ignore divergences from KNN and MST solutions (Testing extract clusters in HDBSCAN #4009)
• Finish complete testing of cluster_selection_method=leaf and cluster_selection_epsilon != 0.0 with the help of above (Testing extract clusters in HDBSCAN #4009)

3. Test failures / bugs (e.g. must have)

• Cluster sizes for some tests seem to differ only on A100 ( see related issue) (HDBSCAN bug on A100 #4024)
• Intermittent crash that has appeared a couple times (see related issue) (Fixing intermittent HBDSCAN pytest failure in CI #4025)
• [BUG] HDBSCAN is marking points in dense regions as noise #4054

4. Additional tech debt / cleanup (e.g. nice to have)

• Some arrays are being used as int instead of bool due to inter-op issues between host and device bool. Update these
• Investigate potential parallelization of do_labelling()

5. External

• Submit patch to reference HDBSCAN for allow_single_cluster=True gets overwritten for cluster_selection_method=leaf scikit-learn-contrib/hdbscan#476 and update cuML when patch is accepted

6. Additional features before blog

• Accelerate reachability w/ ANN (e.g. try FAISS and RBC first) #4815
• Expose more HDBSCAN distances #4814
• "Official" benchmarking for blog

7. Additional features (e.g. like to have)

• Add outlier scores
• Sparse inputs
• Fuzzy clustering

[cjnolet]

Linking #3997

[cjnolet]

HDBSCAN has officially moved out of experimental!

[github-actions]

This issue has been labeled inactive-90d due to no recent activity in the past 90 days. Please close this issue if no further response or action is needed. Otherwise, please respond with a comment indicating any updates or changes to the original issue and/or confirm this issue still needs to be addressed.

[KukumavMozolo]

H there, i would be very much interested in sparse inputs being supported, is this planned?

[beckernick]

Hi @KukumavMozolo, thanks for reviving this issue! Would you be able to share any info about what kinds of use cases this might enable for you that don't currently work well with dense inputs?

[KukumavMozolo]

Hi @beckernick,
Currently I am working on crashreport deduplication. Essentially this entails transforming various device metrics like memory consumption, cpu utilization but also crashlogs like calltraces and register content into a very high dimensional vectorspace that is also very sparse. Crashreport-deduplication is than the process of finding Clusters in that vector space representing sources of errors.
Obtaining a dense representation of this kind of data seems difficult to me since slight variations of input e.g. a slightly different stacktrace can be a qualitative different source of error making it hard to compress. Yet still the number of possible errors at a given point in time is comparably small.