złożoność obliczeniowa k-NN

Jaka jest złożoność czasowa algorytmu k -NN z naiwnym podejściem wyszukiwania (bez drzewa kd lub podobnych)?

Interesuje mnie jego złożoność czasowa, biorąc pod uwagę również hiperparametr k . Znalazłem sprzeczne odpowiedzi:

1. O (nd + kn), gdzie n jest licznością zbioru treningowego, a d jest wymiarem każdej próbki. [1]

2. O (ndk), gdzie znowu n jest licznością zbioru treningowego, a d jest wymiarem każdej próbki. [2]

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

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

Zakładając, że jest ustalony (tak jak robią to oba połączone wykłady), wówczas twoje algorytmy określą, czy twoje obliczenia będą działać w środowisku uruchomieniowym O ( n d + k n ), czy w środowisku uruchomieniowym O ( n d k ) .$k$$O(nd+kn)$$O(ndk)$

Najpierw rozważmy algorytm czasu wykonania :$O(nd+kn)$

• Zainicjuj dla wszystkich obserwacji i w zestawie treningowym$selected_i = 0$$i$
• Dla każdej obserwacji zestawu treningowego oblicz d i s t i , odległość od nowej obserwacji do obserwacji zestawu treningowego $i$$dist_i$$i$
• Dla do k : Zapętlaj wszystkie obserwacje zestawu treningowego, wybierając indeks i o najmniejszej wartości d i s t i dla którego s e l e c t e d i = 0 . Wybierz tę obserwację, ustawiając s e l e c t e d i = 1 .$j=1$$k$$i$$dist_i$$selected_i=0$$selected_i=1$
• Zwraca wybranych indeksów$k$

Każde obliczenie odległości wymaga czasu wykonania , więc drugi krok wymaga czasu wykonania O ( n d ) . Dla każdej iteracji w trzecim kroku wykonujemy pracę O ( n ) , zapętlając obserwacje zestawu treningowego, więc ogólny krok wymaga pracy O ( n k ) . Pierwszy i czwarty krok wymagają tylko pracy O ( n ) , więc otrzymujemy środowisko wykonawcze O ( n d + k n ) .$O(d)$$O(nd)$$O(n)$$O(nk)$$O(n)$$O(nd+kn)$

Rozważmy teraz algorytm wykonawczy :$O(ndk)$

• Zainicjuj dla wszystkich obserwacji i w zestawie treningowym$selected_i = 0$$i$
• Dla do k : Zapętl wszystkie obserwacje zestawu treningowego i oblicz odległość d pomiędzy obserwacją wybranego zestawu treningowego a nową obserwacją. Wybierz indeks i o najmniejszej wartości d, dla której s e l e c t e d i = 0 . Wybierz tę obserwację, ustawiając s e l e c t e d i = 1 .$j=1$$k$$d$$i$$d$$selected_i=0$$selected_i=1$
• Zwraca wybranych indeksów$k$

Dla każdej iteracji w drugim kroku obliczamy odległość między nową obserwacją a każdą obserwacją zestawu treningowego, wymagając pracy dla iteracji, a zatem O ( n d k ) pracy ogólnej.$O(nd)$$O(ndk)$

Różnica między tymi dwoma algorytmami polega na tym, że pierwsze wstępnie oblicza i przechowuje odległości (wymagające dodatkowej pamięci ), a drugie nie. Biorąc jednak pod uwagę, że już przechowujemy cały zestaw szkoleniowy, wymagający pamięci O ( n d ) , a także wektora s e l e c t e d , wymagającego pamięci O ( n ) , pamięć dwóch algorytmów jest asymptotycznie podobnie. W rezultacie lepszy asymptotyczny czas działania dla k > 1 sprawia, że ​​pierwszy algorytm jest bardziej atrakcyjny.$O(n)$$O(nd)$$selected$$O(n)$$k > 1$

Warto zauważyć, że możliwe jest uzyskanie środowiska wykonawczego za pomocą ulepszenia algorytmu:$O(nd)$

• Dla każdej obserwacji zestawu treningowego oblicz d i s t i , odległość od nowej obserwacji do obserwacji zestawu treningowego $i$$dist_i$$i$
• Uruchom algorytm szybkiego wyboru, aby obliczyć najmniejszą odległość w środowisku wykonawczym O ( n $k^{th}$$O(n)$
• Zwróć wszystkie wskaźniki nie większe niż obliczona najmniejsza odległość$k^{th}$

Podejście to wykorzystuje fakt, że istnieją wydajne podejścia do znalezienia najmniejszej wartości w nieposortowanej tablicy.$k^{th}$