kompleksitas komputasi k-NN

Apa kompleksitas waktu dari algoritma k -NN dengan pendekatan pencarian naif (tidak ada pohon kd atau similars)?

Saya tertarik pada kompleksitas waktunya mempertimbangkan juga hyperparameter k . Saya telah menemukan jawaban yang bertentangan:

1. O (nd + kn), di mana n adalah kardinalitas set pelatihan dan d dimensi masing-masing sampel. [1]

2. O (ndk), di mana lagi n adalah kardinalitas set pelatihan dan d dimensi masing-masing sampel. [2]

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

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

Dengan asumsi adalah tetap (seperti yang dilakukan oleh kedua kuliah terkait), maka pilihan algoritmik Anda akan menentukan apakah perhitungan Anda membutuhkan runtime O ( n d + k n ) runtime atau runtime O ( n d k ) .$k$$O(nd+kn)$$O(ndk)$

Pertama, mari kita pertimbangkan algoritma runtime :$O(nd+kn)$

• Inisialisasi untuk semua pengamatan saya pada set pelatihan$selected_i = 0$$i$
• Untuk setiap pelatihan set observasi , hitung d i s t i , jarak dari observasi baru ke training set observasi $i$$dist_i$$i$
• Untuk hingga k : Lewati semua pengamatan set pelatihan, pilih indeks i dengan nilai d i s t i terkecil dan untuk mana s e l e c t e d i = 0 . Pilih pengamatan ini dengan mengatur s e l e c t e d i = 1 .$j=1$$k$$i$$dist_i$$selected_i=0$$selected_i=1$
• Kembalikan indeks yang dipilih $k$

Setiap perhitungan jarak membutuhkan runtime , sehingga langkah kedua membutuhkan runtime O ( n d ) . Untuk setiap iterate pada langkah ketiga, kami melakukan pekerjaan O ( n ) dengan mengulang melalui pengamatan set pelatihan, sehingga langkah keseluruhan membutuhkan pekerjaan O ( n k ) . Langkah pertama dan keempat hanya membutuhkan O ( n ) bekerja, jadi kami mendapatkan runtime O ( n d + k n ) .$O(d)$$O(nd)$$O(n)$$O(nk)$$O(n)$$O(nd+kn)$

Sekarang, mari kita pertimbangkan algoritma runtime :$O(ndk)$

• Inisialisasi untuk semua pengamatan saya pada set pelatihan$selected_i = 0$$i$
• Untuk hingga k : Lewati semua pengamatan set pelatihan dan hitung jarak d antara observasi set pelatihan yang dipilih dan observasi baru. Pilih indeks i dengan nilai d terkecil yang s e l e c t e d i = 0 . Pilih pengamatan ini dengan mengatur s e l e c t e d i = 1 .$j=1$$k$$d$$i$$d$$selected_i=0$$selected_i=1$
• Kembalikan indeks yang dipilih $k$

Untuk setiap iterate pada langkah kedua, kita menghitung jarak antara pengamatan baru dan setiap pengamatan pelatihan set, membutuhkan bekerja untuk iterasi dan karena itu O ( n d k ) kerja secara keseluruhan.$O(nd)$$O(ndk)$

Perbedaan antara kedua algoritma adalah bahwa yang pertama precomputes dan menyimpan jarak (membutuhkan memori tambahan), sedangkan yang kedua tidak. Namun, mengingat bahwa kita sudah menyimpan seluruh rangkaian pelatihan, membutuhkan memori O ( n d ) , serta vektor s e l e c t e d , membutuhkan penyimpanan O ( n ) , penyimpanan kedua algoritma tersebut asimptotik. sama. Hasilnya, runtime asimptotik yang lebih baik untuk k > 1 membuat algoritma pertama lebih menarik.$O(n)$$O(nd)$$selected$$O(n)$$k > 1$

Perlu dicatat bahwa dimungkinkan untuk mendapatkan runtime menggunakan peningkatan algoritmik:$O(nd)$

• Untuk setiap pelatihan set observasi , hitung d i s t i , jarak dari observasi baru ke training set observasi $i$$dist_i$$i$
• Jalankan algoritma QuickSelect untuk menghitung jarak terkecil di O ( n ) runtime$k^{th}$$O(n)$
• Kembali semua indeks tidak lebih besar dari yang dihitung jarak terkecil$k^{th}$

Pendekatan ini mengambil keuntungan dari fakta bahwa pendekatan yang efisien ada untuk menemukan nilai terkecil dalam array disortir.$k^{th}$