Amélioration des performances (vitesse) du classificateur kNN

Question

En tant qu'affectation, je dois créer mon propre classificateur kNN, sans utiliser de boucles for. J'ai réussi à utiliser scipy.spatial.KDTree pour trouver le (s) voisin (s) le plus proche de chaque vecteur dans l'ensemble de tests, puis j'utilise scipy.stats.mode pour retourner la liste des classes prédites. Cependant, cela prend extrêmement longtemps lorsque la taille de l'ensemble est très grande. Par exemple, j'ai créé l'exemple suivant inspiré par this page

import numpy as np 
from sklearn.model_selection import train_test_split 
from scipy import spatial 
from scipy.stats import mode 

def predict(X_test): 
    X = Y_train[tree.query(X_test, k=k)[1]] 
    Y = mode(X, axis=-1)[0].T[0] 
    return Y 

def load_data(): 
    x1 = 1.5 * np.random.randn(100) + 1 
    y1 = 1.5 * np.random.randn(100) + 2 
    x2 = 1.5 * np.random.randn(100) + 3 
    y2 = 1.5 * np.random.randn(100) + 4 
    X = np.vstack((np.hstack((x1,x2)),np.hstack((y1,y2)))).T 
    y = 1.0*np.hstack((np.zeros(100), np.ones(100))) 
    return X, y 

if __name__ == '__main__': 
    X, y = load_data() 
    X_train, X_test, Y_train, Y_test = train_test_split(X, y) 

    k = 7 
    Z = predict(np.c_[xx.ravel(), yy.ravel()]) 
    Z = Z.reshape(xx.shape) 

Cela prend beaucoup de temps (40-60 secondes) en raison de la partie X = Y_train[tree.query(X_test, k=k)[1]]. Est-il possible que je peux améliorer la vitesse de cette implémentation spécifique, ou devrais-je penser à une autre façon de le faire? Par exemple, l'implémentation de sklearn ne prend que 0,4 seconde, ce qui est incroyablement rapide par rapport à mon implémentation.

Answer 1

Vous avez dû lire votre code plusieurs fois, mais ensuite j'ai vu que vous utilisez KDTree et non cKDTree. Ce dernier est implémenté en Cython (au lieu de plain python et numpy) et devrait vous donner une accélération décente.