0
$\begingroup$

Consider sklearn NearestNeighbors:

nbrs = NearestNeighbors(n_neighbors=2, algorithm=method  ).fit(X) # 'ball_tree'
distances, indices = nbrs.kneighbors(X)

There are several choices for 'algorithm' - ‘ball_tree’ will use BallTree ‘kd_tree’ will use KDTree ‘brute’ will use a brute-force search. ‘auto’ will attempt to decide the most appropriate algorithm based on the values passed to fit method.

Observe a strange thing - "brute" works faster, than tree methods, if the dimension of the space is large enough: enter image description here

Question 1 Is there any explanation why kd/ball tree work slower and why they are used as "auto" ? It seems like a bug in sklearn.

Let us look on the speed of kd_tree:

enter image description here

Question 2 what is the theoretical complexity of the kd_tree and ball_tree with respect to sample_size and dimension of the space ? (May be other things - the simulation is done for the uniformly sampled points [0,1]^d).

Remark: it is clear that for "brute" complexity grows quadratically with respect to sample size. As one can see from data above - kd_tree works quite linearly with respect to sample_size.

The code was running on colab.research.google.com

import time
from sklearn.neighbors import NearestNeighbors
import numpy as np
import pandas as pd


dim = 5
n_sample = 10**4

df_stat = pd.DataFrame() 
c = 0
t00 = time.time()
for i in range(1): # repeat test several times
  for dim in [5,10,20]: 
    for n_sample in [10**5]:
      X = np.random.rand(n_sample, dim)
      
      for method in ['brute','kd_tree','ball_tree','auto']:
        c += 1
        df_stat.loc[c, 'Method'] = method
        df_stat.loc[c, 'Dim'] = dim
        df_stat.loc[c, 'N_sample'] = n_sample
        t0 = time.time()
        nbrs = NearestNeighbors(n_neighbors=2, algorithm=method  ).fit(X) # 'ball_tree'
        distances, indices = nbrs.kneighbors(X)
        df_stat.loc[c, 'Time'] = time.time()-t0
        if method == 'brute':
          indices_save = indices.copy()
        difr = indices_save - indices
        df_stat.loc[c, 'Coincide with Brute'] = (np.sum( np.abs(difr)) == 0) 
        print(df_stat.tail(1))

df_stat

PS

The motivation to ask comes from:

https://cstheory.stackexchange.com/questions/47034/number-of-connected-components-of-a-random-nearest-neighbor-graph/47039?noredirect=1#comment104468_47039

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.