[FEA] [algorithms/hdbscan] Reduce Memory footprint while performing soft clustering using HDBSCAN

[abhijithp135]

Is your feature request related to a problem? Please describe.
It is not related to any problem. I would like to generate soft clustering data for a sample having size of 1.5 million. Number of clusters generated after clustering : 15,000
In order to run soft clustering, I need at least 1.5 * 10^6 * 15000 * 4 = 90 GB memory to store the result.
This is clearly not scalable if we want to run clustering on even large data.

Describe the solution you'd like
Instead of storing the probabilities of a point belonging to all the clusters, expose a param in the constructor and store only those many probabilities after sorting. And also store the probability of this point being a noise point in separate array.
At least for my use case, I don't need more than top 10 probabilities and the noise probability

Describe alternatives you've considered
A clear and concise description of any alternative solutions or features you've considered.

Additional context
Add any other context, code examples, or references to existing implementations about the feature request here.

[csadorf]

Thank you for your proposal!

@tarang-jain Could you comment on feasibility of this?

[tarang-jain]

Thanks for the tag! The number of clusters is huge. As a quick fix, I can recommend increasing min_samples to reduce the number of clusters.

Answering this feature request: although we have batching to compute distance based memberships (which is the first step for computing the probabilities), we do not perform batching for the rest of the parts in the computation. So we do have to accommodate the entire membership vector (num_queries * num_clusters) on the GPU unless a user externally does batching by supplying batches of data to the membership_vectors function. Based on what I gather from this issue, the user wants to reduce both -- CPU and GPU memory pressure (so neither have to store the entire membership vector at any given time). To achieve this, we will have to do two things:

1. Expose another batch size parameter that computes the membership vector for one batch of queries at a time.
2. Perform a top-k on that and return the top-k probabilities.
3. Repeat steps 1 and 2 for each batch.
   This can certainly be implemented.

Feasibility:

1. The reason we had batching on only distance based memberships to store PW distances was because that was easily the main memory bottleneck. We typically do not expect such a high number of clusters as 15000 in the final clustering. But if there are several use-cases where users cannot (or do not wish to) reduce the number of clusters, we can consider implementing this (or the user can themselves do batching as I had described above).
2. If memory is not the main issue and the requirement is to actually do a top-k on the GPU to extract only the top-k cluster labels and probabilities, that should be an easy add-on on top of the final assignments and probabilities.
   So I think we can attempt step 2 before step 1.

[abhijithp135]

@tarang-jain Thank you for the detailed explanation.

If I increase the min_samples it is reducing number of clusters but at the same number of points classified as noise are also getting increased which I do not want. And yes, memory is the main bottleneck.

Inside all_points_membership_vectors function, an array of size numbers of clusters * num of samples is created before starting any computation either distance based or outlier based. How can I do external batching if I want to generate soft clusters for the data on which I performed clustering. This is because, some points are classified as noise and I want to know to the probabilities of noise belonging to the generated clusters.

I went through hdbscan docs. From what I have understood so far, soft clusters for one point do not have any effect/dependency on the soft clusters for any other point. Can you confirm this for both distance based and outlier based?

Diverging a bit, let me ask few more questions

1. If I feel like outlier based membership does not make any sense for my use case and want to explore soft clustering based on distance alone, can I do that using cuML?
2. I tried a sample example using original hdbscan and clustered a sample dataset. Then I performed soft clustering on the data using all_points_membership_vector and using membership_vector passing the same data. They gave different probabilities. am expecting them to give same probabilities. But they did not. GPU implementation is also similar to this?

[tarang-jain]

If I increase the min_samples it is reducing number of clusters but at the same number of points classified as noise are also getting increased which I do not want. And yes, memory is the main bottleneck.

Lowering min_cluster_size might help so that small clusters are treated as individual clusters and not noise. But then again the tradeoff is that the number of clusters can increase.

Inside all_points_membership_vectors function, an array of size numbers of clusters * num of samples is created before starting any computation either distance based or outlier based. How can I do external batching if I want to generate soft clusters for the data on which I performed clustering. This is because, some points are classified as noise and I want to know to the probabilities of noise belonging to the generated clusters.

That is correct, which is why I was suggesting the use of membership_vector

I went through hdbscan docs. From what I have understood so far, soft clusters for one point do not have any effect/dependency on the soft clusters for any other point. Can you confirm this for both distance based and outlier based?

Soft cluster probabilities would only depend on where the point is in relation to the original clustering. So that statement is true for membership_vector. For all_points_membership_vectors, there would be an indirect dependence because the points in the dataset are what form the hierarchy in the first place. But there is no coupling as such while computing the soft clustering itself.

1. Decoupling distance and outlier based membership is not supported in the public API. Outlier based memberships and probability of a point belonging to some cluster are crucial steps in the computation of soft clustering probabilities.
2. Yes I would expect them to give different probabilities. The cluster label assignments for membership_vector would be approximate since that is intended for points that are not in the original clustering.

[csadorf]

@abhijithp135 do you have any further questions?

[abhijithp135]

@csadorf Thank you for checking. I don’t have any further questions. You can close this thread.