Saya telah membaca di banyak makalah tentang pencarian tetangga terdekat berdimensi lebih tinggi yang KD-Trees eksponensial dalam K, tetapi sepertinya saya tidak dapat menentukan mengapa.
Apa yang saya cari adalah analisis kompleksitas runtime yang menjelaskan aspek masalah ini.
ksecara efektif merupakan dimensi dari masalah dan karenanya menderita dari "kutukan dimensi."Jawaban:
kNN cenderung eksponensial karena ruang pencarian bertambah2k . Bayangkan Anda mempartisi ruang di sekitar titik pencarian Anda menjadi kuadran. Untuk k = 1 Anda hanya perlu mencari dua 'kuadran' (nilai lebih tinggi dan lebih rendah), untuk k = 2 kuadran itu, untuk k = 3 kuadran itu, yaitu pertumbuhan eksponensial ruang pencarian. Itulah yang diderita pohon kD, karena harus mencari2k cabang pembantu.
Pohon-pohon lain berkinerja lebih baik, misalnya CoverTree . Saya juga menemukan bahwa PH-Tree bekerja dengan sangat baik, tampaknya secara konsisten memakan waktu dua kali lipat selama CoverTree untuk dataset antara k = 8 dan k = 27 (Saya tidak memiliki dataset dengan k yang lebih tinggi).
sumber