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
quickselect
.