złożoność obliczeniowa k-NN

18

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)

Daniel López
źródło

Odpowiedzi:

20

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 ) .kO(nd+kn)O(ndk)

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

  • Zainicjuj dla wszystkich obserwacji i w zestawie treningowymselectedi=0i
  • Dla każdej obserwacji zestawu treningowego oblicz d i s t i , odległość od nowej obserwacji do obserwacji zestawu treningowego iidistii
  • 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=1kidistiselectedi=0selectedi=1
  • Zwraca wybranych indeksówk

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 treningowymselectedi=0i
  • 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=1kdidselectedi=0selectedi=1
  • Zwraca wybranych indeksówk

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)selectedO(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 iidistii
  • Uruchom algorytm szybkiego wyboru, aby obliczyć najmniejszą odległość w środowisku wykonawczym O ( n )kthO(n)
  • Zwróć wszystkie wskaźniki nie większe niż obliczona najmniejsza odległośćkth

Podejście to wykorzystuje fakt, że istnieją wydajne podejścia do znalezienia najmniejszej wartości w nieposortowanej tablicy.kth

josliber
źródło
1
Świetna odpowiedź, a szczególnie podoba mi się rada dotycząca użycia quickselect.
usεr11852 mówi: Przywróć Monic
Jeszcze jedno pytanie: w przypadku trzeciej opcji uważam, że złożoność czasu powinna wynosić O (nd + k), ponieważ nadal musisz obliczyć najczęstszą etykietę wśród najbliższych sąsiadów, aby wyemitować prognozę, prawda?
Daniel López,
knO(nd+k)O(nd)
Ostatni raz przeszkadzam: próbując określić złożoność obliczeniową zmodyfikowanej wersji k -NN, nad którą pracuję, otrzymuję następujące: O (nd + nd / p) Gdzie z definicji n , d i p są liczbami całkowitymi większymi niż zero. Czy mogę to uprościć do O (nd) ?
Daniel López,
@Daniel Yes, in that case O(nd) works.
josliber