Pourquoi NearestNeighbors (SKlearn) prend-il plus de temps lorsque n_neighbors est inférieur au nombre total d'éléments?

Question

Je veux calculer les 20 éléments les plus similaires pour chacun des N éléments de l'ensemble de données. Chaque élément est représenté en utilisant les caractéristiques de M dimensions Ainsi, la taille des données est N_items X M_features.

Lorsque je ne spécifie pas n_neighbors (la valeur par défaut est 5), la fonction kneighbors prend beaucoup de temps. Mais quand je spécifie n_neighbors = N_items, il donne des résultats presque instantanément. Il faut beaucoup de temps pour trouver kneighbors, mais NN_object = NearestNeighbors(n_neighbors=N_items) donne des résultats assez rapidement Quelqu'un peut-il expliquer ce qui se passe exactement derrière la scène?

PS: N_items dans mon cas est ~ 50K et M_features est ~ 10K.

Answer 1

Peut-être cela est parce que quand vous fournissez n_neigbors=n_samples dans le premier cas, le nombre total de calculs de distance métriques pour chaque point est combinaisonC(n_samples, n_neigbors) qui est 1. Mais quand vous faites n_neigbors=21 alors le nombre de calculs augmente beaucoup plis. Cela attribue à l'exécution accrue. Jetez un oeil à l'algorithme pour les voisins les plus proches. J'espère que vous aurez de la clarté en le parcourant.