Jak działa wyszukiwanie najbliższego sąsiada KD?

Question

Patrzę na stronę Wikipedii dla drzew KD. Jako przykład zaimplementowałem w pythonie algorytm budowania drzewa kd.

Algorytm wyszukiwania KNN z drzewem KD przełącza języki i nie jest całkowicie jasny. Angielskie wyjaśnienie zaczyna mieć sens, ale jego części (takie jak obszar, w którym "odradzają rekursję" w celu sprawdzenia innych węzłów liści) nie mają dla mnie żadnego sensu.

Jak to działa i jak wykonać wyszukiwanie KNN z drzewem KD w pythonie? To nie jest pytanie typu "send me the code!" i nie spodziewam się tego. Tylko krótkie wyjaśnienie proszę :)

Answer 1

ten book introduction, strona 3:

Biorąc pod uwagę zbiór n punktów w przestrzeni d-wymiarowej, KD-drzewo jest skonstruowany rekurencyjnie w następujący sposób. Najpierw znajduje się mediana wartości współrzędnych ith punktów (początkowo i = 1). Oznacza to, że obliczana jest wartość M, , tak że co najmniej 50% punktów ma ich współrzędną i, większą lub równą do M, podczas gdy co najmniej 50% punktów ma ich współrzędną i mniejszą niż niższą lub równą M. Wartość x jest przechowywana, a zbiór P jest podzielony na partycje na PL i PR, gdzie PL zawiera tylko punkty o ich współrzędnej ith i mniejsze lub równe M i | PR | = | PL | ± 1. Proces ten jest następnie powtarzany rekurencyjnie na obu PL i PR, gdzie i zastępowany jest przez i + 1 (lub 1, jeśli i = d). Gdy zestaw punktów w węźle ma rozmiar 1, rekursja zatrzymuje się.

Poniższe akapity omawiają jego zastosowanie w rozwiązywaniu problemu najbliższego sąsiada.

Albo, tutaj jest original 1975 paper by Jon Bentley.

EDIT: Dodam że scipy ma wdrożenie kdtree:

• scipy.spatial
• another Stack Overflow question

Answer 2

ja po prostu spędzić trochę czasu zagadkowe opis algorytmu Wikipedia siebie, i wprowadzono następującą implementację Pythona, która może pomóc: https://gist.github.com/863301

Pierwsza faza closest_point to proste pierwsze wyszukiwanie głębi, aby znaleźć najlepiej pasujący węzeł liści.

Zamiast po prostu powrocie najlepszy węzeł powrot górę stosu wywołań, drugi sprawdza fazowe aby sprawdzić, czy nie może być bliżej węzła na „Away” z boku: (ASCII schemacie sztuki)

  n  current node 
b   |  best match so far 
|  p |  point we're looking for 
|< >| |  error 
     |< >|  distance to "away" side 
     |< | >| error "sphere" extends to "away" side 
      | x possible better match on the "away" side 

Bieżący węzeł n dzieli przestrzeń wzdłuż linii, więc wystarczy spojrzeć na stronę "od hotelu", jeśli "błąd" między punktem p a najlepszym dopasowaniem b jest większy niż odległość od punktu p i linia jest jednak równa n . Jeśli tak, to sprawdzamy, czy są jakieś punkty na stronie "z dala", które są bliżej.

Ponieważ nasz najlepszy węzeł dopasowujący jest przekazywany do tego drugiego testu, nie musi wykonywać pełnego przejścia gałęzi i zatrzyma się dość szybko, jeśli znajduje się na niewłaściwym torze (tylko zmierza w stronę "pobliskich" węzłów potomnych dopóki nie uderzy w liść).

Aby obliczyć odległość między punktem p a linią dzielącą przestrzeń przez węzeł n, możemy po prostu "rzutować" punkt w dół na oś, kopiując odpowiednią współrzędną jako osie są wszystkie ortogonalne (poziome lub pionowe).