Complexité de calcul k-NN

18

Quelle est la complexité temporelle de l' algorithme k -NN avec une approche de recherche naïve (pas d'arbre kd ou similaire)?

Je suis intéressé par sa complexité temporelle compte tenu également de l'hyperparamètre k . J'ai trouvé des réponses contradictoires:

  1. O (nd + kn), où n est la cardinalité de l'ensemble d'apprentissage et d la dimension de chaque échantillon. [1]

  2. O (ndk), où encore n est la cardinalité de l'ensemble d'apprentissage et d la dimension de chaque échantillon. [2]

[1] http://www.csd.uwo.ca/courses/CS9840a/Lecture2_knn.pdf (Pag. 18/20)

[2] http://www.cs.haifa.ac.il/~rita/ml_course/lectures/KNN.pdf (p. 18/31)

Daniel López
la source

Réponses:

20

En supposant que est fixe (comme le font les deux conférences liées), vos choix algorithmiques détermineront si votre calcul prend O ( n d + k n ) runtime ou O ( n d k ) runtime.kO(nd+kn)O(ndk)

Considérons d'abord un algorithme d'exécution :O(nd+kn)

  • Initialiser pour toutes les observations i dans l'ensemble d'apprentissageselectedi=0i
  • Pour chaque ensemble d'entraînement, observation , calculer d i s t i , la distance entre la nouvelle observation et l'observation d'ensemble d'apprentissage iidistii
  • Pour à k : boucle à travers toutes les observations de l'ensemble d'apprentissage, en sélectionnant l'indice i avec la plus petite valeur d i s t i et pour lequel s e l e c t e d i = 0 . Sélectionnez cette observation en définissantj=1kidistiselectedi=0 .selectedi=1
  • Renvoie les indices sélectionnésk

Chaque calcul de distance nécessite un runtime , donc la deuxième étape nécessite un runtime O ( n d ) . Pour chaque itération de la troisième étape, nous effectuons un travail O ( n ) en parcourant les observations de l'ensemble d'apprentissage, de sorte que l'étape nécessite globalement un travail O ( n k ) . Les première et quatrième étapes ne nécessitent qu'un travail O ( n ) , nous obtenons donc un runtime O ( n d + k n ) .O(d)O(nd)O(n)O(nk)O(n)O(nd+kn)

Considérons maintenant un algorithme d'exécution :O(ndk)

  • Initialiser pour toutes les observations i dans l'ensemble d'apprentissageselectedi=0i
  • Pour à k : parcourez toutes les observations de l'ensemble d'apprentissage et calculez la distance d entre l'observation de l'ensemble d'apprentissage sélectionné et la nouvelle observation. Sélectionnez l'indice i avec la plus petite valeur d pour laquelle s e l e c t e d i = 0 . Sélectionnez cette observation en définissant s e l e c t e d i = 1 .j=1kdidselectedi=0selectedi=1
  • Renvoie les indices sélectionnésk

Pour chaque itération de la deuxième étape, nous calculons la distance entre la nouvelle observation et chaque observation d'ensemble d'apprentissage, nécessitant travail pour une itération et donc O ( n d k ) de travail global.O(nd)O(ndk)

La différence entre les deux algorithmes est que le premier précalcule et stocke les distances (nécessitant de mémoire supplémentaire), tandis que le second ne le fait pas. Cependant, étant donné que nous stockons déjà l'ensemble de la formation, nécessitant O ( n d ) mémoire, ainsi que le vecteur s e l e c t e d , nécessitant OO(n)O(nd)selectedstockage ( n ) , le stockage des deux algorithmes est asymptotiquement le même. En conséquence, le meilleur temps d'exécution asymptotique pour k > 1 rend le premier algorithme plus attrayant.O(n)k>1

Il est à noter qu'il est possible d'obtenir un runtime utilisant une amélioration algorithmique:O(nd)

  • Pour chaque observation d'ensemble d'entraînement , calculer d i s t i , la distance entre la nouvelle observation et l'observation d'ensemble d'apprentissage iidistii
  • Exécutez l' algorithme de sélection rapide pour calculer la plus petite distance dans le temps d'exécution O ( n )kthO(n)
  • Renvoie tous les indices non supérieurs à la plus petite distance calculée kth

Cette approche tire parti du fait qu'il existe des approches efficaces pour trouver la plus petite valeur dans un tableau non trié.kth

josliber
la source
1
Excellente réponse et j'aime particulièrement les conseils d'utilisation quickselect.
usεr11852 dit Réintégrer Monic le
Une autre question: pour la troisième option, je crois que la complexité temporelle devrait être O (nd + k), car il vous reste à calculer l'étiquette la plus courante parmi les k voisins les plus proches pour émettre une prédiction, non?
Daniel López
@Daniel Puisque , O ( n d + k ) est identique à O ( n d ) . knO(nd+k)O(nd)
josliber
La dernière fois que je vous dérange: essayer de déterminer la complexité de calcul d'une version modifiée de k -NN sur laquelle je travaille, j'obtiens ce qui suit: O (nd + nd / p) Où par définition n , d et p sont des entiers supérieurs à zéro. Puis-je simplifier cela en O (nd) ?
Daniel López
O(nd)