Possible error with high dimensional sparse distanse matrix about hdbscan

[lmcinnes]

I think a sparse distance matrix is not actually supported (it should be, it's a valid use case). Sparse matrix input as feature vectors works, but the distance matrix its a little trickier. I believe it could be implemented, but it would be very slow on the size matrix you have -- the main difficulty is computing the core distance for each point, which involves sorting every row (or column, but I see you have a csr, so let's deal with rows). That is a lot of sorts to run, even if each is small. Let me know if you're interested and I'll try and get this implemented when I get a chance.

[lmcinnes]

I have implemented support for this now -- last changes commited to master should cover it. I can't speak for performance (I suspect it won't be super) at this time, but it shouldn't be too bad. I leaned heavily on scipy's sparse matrix csgraph minimum spanning tree implementation, so hopefully that will suffice if your distance matrix is sparse enough.

[moi90]

Does the hdbscan implementation depend on a specific sparse matrix implementation? Can I use all flavours in scipy.sparse? What about Pysparse?

[lmcinnes]

I believe (as with scikit-learn) it depends on scipy.sparse. I'm unfamiliar with Pysparse, but hopefully there is some ability to interchange with scipy.sparse format.

…

On Fri, Sep 29, 2017 at 5:38 PM, moi90 ***@***.***> wrote: Does the hdbscan implementation depend on a specific sparse matrix implementation? Can I use all flavours in scipy.sparse? What about Pysparse? — You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub <#40 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ALaKBUrolul9ixThoDHDN4-4hCYMsbpgks5snWNngaJpZM4I3N37> .

[moi90]

Thanks! Another question: Does your implementation of MST inherit the following property? "This routine uses undirected graphs as input and output. That is, if graph[i, j] and graph[j, i] are both zero, then nodes i and j do not have an edge connecting them. If either is nonzero, then the two are connected by the minimum nonzero value of the two." Or (equivalently): Is it enough to store just one direction of every edge?

[lmcinnes]

If you are using the sparse distance matrix input format (i.e. sparse matrix as X,metric='precomputed' then in principle yes. The catch comes that the distance matrix needs to be converted into a mutual-reachability distance matrix. That step will alter the requirement to be "If either is nonzero, then the two are connected by the maximum nonzero value of the two." because of the way things get calculated. I think you might actually also need the full symmetric matrix to compute core-distance correctly in that step, but I would have to look through the code and think a little more about that.

[moi90]

Thanks! It seems that precomputing the distance matrix for a large dataset is not the best idea...