Description

Performance issue, DBScan running time is largely increased.

Steps/Code to Reproduce

import numpy as np
from timeit import default_timer as timer
from sklearn.cluster import DBSCAN
X=np.random.random((7000, 2))
X[:,0] =X[:,0]/100+23.59
X[:,1] =X[:,1]/100+58.43
start =timer()
dbscan = DBSCAN(eps=0.01, min_samples=2000, algorithm='kd_tree', metric='manhattan')
dbscan.fit(X)
end = timer()
print("running time is {} seconds".format(end-start))

Expected Results

running time is 0.679255008698 (0.17.1 version)

Actual Results

running time is 1.64027285576 seconds (0.18.0 version)

Versions

Darwin-14.5.0-x86_64-i386-64bit
('Python', '2.7.12 |Continuum Analytics, Inc.| (default, Jul 2 2016, 17:43:17) \n[GCC 4.2.1 (Based on Apple Inc. build 5658) (LLVM build 2336.11.00)]')
('NumPy', '1.12.1')
('SciPy', '0.19.0')
('Scikit-Learn', '0.18')