Issue 1:
Description

Building a kd-Tree can be done in O(n(k+log(n)) time and should (to my knowledge) not depent on the details of the data. However, the KDTree implementation in scikit-learn shows a really poor scaling behavior for my data. I cannot produce this behavior with data generated by sklearn.datasets.samples_generator.make_blobs

Steps/Code to Reproduce

download numpy data (search.npy) from https://webshare.mpie.de/index.php?6b4495f7e7 and run the following code on python 3

import numpy as np
from sklearn.neighbors import NearestNeighbors
from sklearn.datasets.samples_generator import make_blobs
from scipy.spatial import KDTree as KDTree_Scipy
from sklearn.neighbors import KDTree as KDTree_Sklearn
from time import sleep, perf_counter as pc

search_raw_artificial, dev_null = make_blobs(n_samples=6830160,n_features=5,centers=1000,cluster_std=0.4,random_state=0)
search_raw_real = np.load('search.npy')

N = [240000,2400000,4800000,6000000]

for search_raw in [search_raw_artificial,search_raw_real]:
for i,n in enumerate(N):

search = search_raw[0:n,:]
print('data shape',search.shape)
print('delta',np.amax(search,0)-np.amin(search,0))
t0 = pc()
neigh = NearestNeighbors(algorithm='ball_tree').fit(search)
print('sklearn.neighbors (ball_tree) build finished in {}s'.format(pc()-t0))
t0 = pc()
neigh = NearestNeighbors(algorithm='kd_tree').fit(search)
print(' sklearn.neighbors (kd_tree) build finished in {}s'.format(pc()-t0))
t0 = pc()
neigh = KDTree_Sklearn(search)
print(' sklearn.neighbors KD tree build finished in {}s'.format(pc()-t0))
t0 = pc()
neigh = KDTree_Scipy(search)
print(' scipy.spatial KD tree build finished in {}s'.format(pc()-t0))
print('')

Expected Results

Time complexity scaling of scikit-learn KDTree should be similar to scaling of scipy.spatial KDTree

Actual Results

Artificial Data, scikit-learn outperforms scipy.spatial

data shape (240000, 5)

delta [ 22.7311549 22.61482157 22.57353059 22.65385101 22.77163478]

sklearn.neighbors (ball_tree) build finished in 0.1524970519822091s

sklearn.neighbors (kd_tree) build finished in 0.17296032601734623s

sklearn.neighbors KD tree build finished in 0.172917598974891s

scipy.spatial KD tree build finished in 2.265735782973934s

data shape (2400000, 5)

delta [ 23.38025743 23.22174801 22.88042798 22.8831237 23.31696732]

sklearn.neighbors (ball_tree) build finished in 3.462802237016149s

sklearn.neighbors (kd_tree) build finished in 3.7110973289818503s

sklearn.neighbors KD tree build finished in 3.5682168990024365s

scipy.spatial KD tree build finished in 19.92274082399672s

data shape (4800000, 5)

delta [ 23.38025743 23.26302877 23.22210673 22.97866792 23.31696732]

sklearn.neighbors (ball_tree) build finished in 8.922708058031276s

sklearn.neighbors (kd_tree) build finished in 9.238389031030238s

sklearn.neighbors KD tree build finished in 8.879073369025718s

scipy.spatial KD tree build finished in 38.43681587401079s

data shape (6000000, 5)

delta [ 23.42236957 23.26302877 23.22210673 23.20207953 23.31696732]

sklearn.neighbors (ball_tree) build finished in 12.75000820402056s

sklearn.neighbors (kd_tree) build finished in 13.30022174998885s

sklearn.neighbors KD tree build finished in 12.794657755992375s

scipy.spatial KD tree build finished in 48.33784791099606s

My Data, scipy.spatial outperforms scikit-learn for increasing data size

data shape (240000, 5)

delta [ 2.14487407 2.14472508 2.14499087 8.86612151 0.15491879]

sklearn.neighbors (ball_tree) build finished in 0.39374090504134074s

sklearn.neighbors (kd_tree) build finished in 0.21525143302278593s

sklearn.neighbors KD tree build finished in 0.21449304796988145s

scipy.spatial KD tree build finished in 2.244567967019975s

data shape (2400000, 5)

delta [ 2.14502773 2.14502543 2.14502904 8.86612151 1.59685522]

sklearn.neighbors (ball_tree) build finished in 4.199425678991247s

sklearn.neighbors (kd_tree) build finished in 4.40237572795013s

sklearn.neighbors KD tree build finished in 4.295626600971445s

scipy.spatial KD tree build finished in 26.322200270951726s

data shape (4800000, 5)

delta [ 2.14502773 2.14502864 2.14502904 8.86612151 3.19371044]

sklearn.neighbors (ball_tree) build finished in 110.31694995303405s

sklearn.neighbors (kd_tree) build finished in 112.8703724470106s

sklearn.neighbors KD tree build finished in 114.07325625402154s

scipy.spatial KD tree build finished in 51.79352715797722s

data shape (6000000, 5)

delta [ 2.14502838 2.14502902 2.14502914 8.86612151 3.99213804]

sklearn.neighbors (ball_tree) build finished in 2458.668528069975s

sklearn.neighbors (kd_tree) build finished in 2451.2438263060176s

sklearn.neighbors KD tree build finished in 2801.8054143560003s

scipy.spatial KD tree build finished in 62.066240190993994s

Comments

cKDTree from scipy.spatial behaves even better

I cannot use cKDTree/KDTree from scipy.spatial because calculating a sparse distance matrix (sparse_distance_matrix function) is extremely slow compared to neighbors.radius_neighbors_graph/neighbors.kneighbors_graph and I need a sparse distance matrix for DBSCAN on large datasets (n_samples >10 mio) with low dimensionality (n_features = 5 or 6)

Versions

Linux-4.7.6-1-ARCH-x86_64-with-arch

Python 3.5.2 (default, Jun 28 2016, 08:46:01) [GCC 6.1.1 20160602]

NumPy 1.11.2

SciPy 0.18.1

Scikit-Learn 0.18

Issue 2:
I don't know if this is related to #6147. I am using "The scikit-learn version is 0.18.dev0" and I have no exception though, so this is different.

In any case, this is my code (the data I am using is the same as the data for the Santander kaggle competition, too big to attach).

alg = XGBClassifier(max_depth=4, min_child_weight = 1, n_estimators=1000, learning_rate=0.0202, gamma=0, nthread=4, subsample=0.6815, colsample_bytree=0.701, seed=1, silent=False)

param_test1 = {
'max_depth':range(3,10,2),
'min_child_weight':range(1,10,2)
}

gsearch1 = GridSearchCV(estimator = alg, param_grid = param_test1, scoring='roc_auc', iid=False, n_jobs=4, cv=5)
gsearch1.fit(train_data[predictors].as_matrix(),train_data[target].as_matrix())

The program will not crash, will not throw an exception, but will not do anything (activity monitor shows no activity). Quick debugging shows the program enters _fit in grid_search.py but never reaches line 564. I did not debug further. A quick search brought me to issue #6147 and tried removing the n_jobsvariable.

Removingn_jobs from the GridSearchCV call solves the issue.