(H)DBSCAN

[TomAugspurger]

Some interest in a parallel / distributed version of this

• https://github.com/scikit-learn-contrib/hdbscan
• http://nbviewer.jupyter.org/github/scikit-learn-contrib/hdbscan/blob/master/notebooks/How%20HDBSCAN%20Works.ipynb
• http://nbviewer.jupyter.org/github/scikit-learn-contrib/hdbscan/blob/master/notebooks/Comparing%20Clustering%20Algorithms.ipynb

Haven't looked to see if it's parallelizable.

[lmcinnes]

I believe an approximate version of this is parallelizable. Some of the relevant techniques are described in this paper: http://www.sysml.cc/doc/105.pdf

This is certainly of interest to me -- I had been planning something similar before the paper came out, and had already coded up a python version of NNDescent. That version is not parallel, but making it so would be interesting to try. One catch that comes to mind is that that implementation is currently using Numba instead of Cython for performance. Did the maintainers here have any strong feelings on Numba dependencies?

[TomAugspurger]

Great!

I’m happy to accept numba as a dependency (I have a branch moving our Cython k-means to numba. Using just numba would simplify our build and release process. )

[lmcinnes]

I'll see what I can put together then. I can't make any promises on getting it done soon, but I will definitely put it in the queue of things to work on.

[TomAugspurger]

Skimming the paper at http://www.sysml.cc/doc/105.pdf

https://github.com/lmcinnes/pynndescent would be great to make dask-friendly and include in dask-ml. If possible I'd like to re-use it for a top-level KNeighborsClassfier/Regressor API, and inside SpectralClustering (as an alternative to K-Means).

[mrocklin]

I chatted with @lmcinnes about this. It seems like this is slightly blocked on improved slicing of dask arrays with out-of-order indices. For example the following was inefficient

In [1]: import dask.array as da

In [2]: x = da.random.random((1000000, 100), chunks=(10000, 100))

In [3]: import numpy as np

In [4]: index = np.arange(len(x))

In [5]: np.random.shuffle(index)

In [6]: %time y = x[index]
/home/mrocklin/Software/anaconda/bin/ipython:1: PerformanceWarning: Slicing with an out-of-order index is generating 9900 times more chunks
  #!/home/mrocklin/Software/anaconda/bin/python
CPU times: user 4.48 s, sys: 188 ms, total: 4.67 s
Wall time: 4.68 s

In [7]: y.numblocks
Out[7]: (989999, 1)

[jakirkham]

So would solving issue ( dask/dask#3409 ) address this?

[mrocklin]

Possibly. It might also be that @lmcinnes would want to do more targetted indexing than an entirely random shuffle.

…

On Sun, Jul 15, 2018 at 1:18 PM, jakirkham ***@***.***> wrote: So would solving issue ( dask/dask#3409 <dask/dask#3409> ) address this? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#158 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AASszNY72sUiQpbPD5plw_7y33lEn5eCks5uG4dfgaJpZM4TOvYA> .

[mrocklin]

Although it may also be that we can improve things today if we index directly many times, but make sure that the index is sorted.

In [1]: import dask.array as da

In [2]: x = da.random.random((1000000, 100), chunks=(10000, 100))

In [3]: import numpy as np

In [4]: index = np.random.randint(0, len(x), size=10000)

In [5]: %time x[index].numblocks
/home/mrocklin/Software/anaconda/bin/ipython:1: PerformanceWarning: Slicing with an out-of-order index is generating 100 times more chunks
  #!/home/mrocklin/Software/anaconda/bin/python
CPU times: user 73.6 ms, sys: 3.8 ms, total: 77.4 ms
Wall time: 76.8 ms
Out[5]: (9907, 1)

In [6]: index.sort()

In [7]: %time x[index].numblocks
CPU times: user 4.74 ms, sys: 47 µs, total: 4.78 ms
Wall time: 4.15 ms
Out[7]: (100, 1)

[mrocklin]

I've laid out a plan in dask/dask#3409 (comment) to improve things a bit. That should be accessible for others to contribute if they're interested.

[TomAugspurger]

We've started to make progress on this on the Dask side: (dask/dask#3808 for slicing performance with as shuffled array).

@lmcinnes do you have a rough sketch of the next steps for a parallel / distributed pynndescent? On a brief examination, the random projections would be the first thing? I'm interested in working on this a bit.