make_blobs(5000, n_features=100, centers=10)[0] clusters (with eps=45, min_samples=5) takes 13.4s in master, 3.2s in this branch.

Note because this permutes over a different array, results will not be identical to previous versions for a fixed random state.

I have extended this PR from its initial purpose, such that DBSCAN now supports sample weights. Ping @robertlayton

Hmm... just realised this leaves fit_predict without a sample_weight parameter. Is overriding the best solution?

Hmm... just realised this leaves fit_predict without a sample_weight parameter. Is overriding the best solution?

I think so.

This looks great. +1 for merge. Don't forget to update the whats_new.rst file prior to merging.

Thanks for the review (and the +1), @ogrisel! Your comments have been addressed.

+1 for merge. nice job @jnothman !

Hmm... I just noticed that DBSCAN isn't really well-tested, and in particular the boundary case of min_samples == number within radius isn't tested, despite the note:

    # Calculate neighborhood for all samples. This leaves the original point
    # in, which needs to be considered later (i.e. point i is the
    # neighborhood of point i. While True, its useless information)

This PR broke the previous behaviour but correctly matched the min_samples docstring in my understanding (this PR tests n_neighbors > min_samples, while the previous used >=). I think we need a PR to revert to the previous behaviour, make the docstring more precise, and test this boundary case.