Come funziona la ricerca vicino più vicino al KD-tree?

Question

Sto guardando la pagina di Wikipedia per gli alberi KD. Ad esempio, ho implementato, in python, l'algoritmo per la costruzione di un albero kd elencato.

L'algoritmo per eseguire la ricerca KNN con un albero KD, tuttavia, cambia lingua e non è completamente chiaro. La spiegazione inglese ha senso, ma alcune parti di esso (come l'area in cui "svolgono la ricorsione" per controllare altri nodi foglia) non hanno alcun senso per me.

Come funziona e come si può eseguire una ricerca KNN con un albero KD in python? Questo non vuole essere una domanda tipo "send me the code!", e non me lo aspetto. Basta una breve spiegazione si prega :)

Answer 1

Questa book introduction, pagina 3:

Dato un insieme di n punti in uno spazio d-dimensionale, il kd-albero è costruito ricorsivamente come segue. Per prima cosa, si trova una mediana dei valori delle coordinate i ith dei punti (inizialmente, i = 1). Cioè, viene calcolato un valore M, in modo che almeno il 50% dei punti abbia la loro coordinata ith uguale o uguale a a M, mentre almeno il 50% dei punti ha la loro coordinata ith minore di uguale o uguale a M. Il valore di x è memorizzato e l'insieme P è partizionato in PL e PR, dove PL contiene solo i punti con la loro coordinata ith minore o uguale a M, e | PR | = | PL | ± 1. Il processo viene quindi ripetuto in modo ricorsivo su PL e PR, con i sostituito da i + 1 (o 1, se i = d). Quando la serie di punti su un nodo ha dimensione 1, la ricorsione si interrompe.

I seguenti paragrafi ne discutono l'uso nella risoluzione del vicino più prossimo.

Oppure, ecco lo original 1975 paper by Jon Bentley.

EDIT: Vorrei aggiungere che SciPy dispone di un'implementazione kdtree:

• scipy.spatial
• another Stack Overflow question

Answer 2

Ho appena passare un po 'di tempo sconcertante out la descrizione Wikipedia dell'algoritmo me stesso, e ha trovato la seguente implementazione Python che può aiutare: https://gist.github.com/863301

La prima fase di closest_point è una semplice prima ricerca di profondità per trovare il miglior nodo foglia corrispondente.

Invece di limitarsi a restituire il miglior nodo ritrovato lo stack di chiamate, un secondo controllo di fase per vedere se ci potrebbe essere un nodo più vicino sul lato "via": (diagramma ASCII art)

  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 

Il nodo corrente n divide lo spazio lungo una linea, quindi dobbiamo solo cercare sul lato "lontano" se l'"errore" tra il punto p e la corrispondenza migliore b è maggiore della distanza dal punto p e la linea è n . Se lo è, quindi controlliamo se ci sono punti sul lato "lontano" che sono più vicini.

Poiché il nostro miglior nodo di corrispondenza è passato in questo secondo test, non deve fare un attraversamento completo del ramo e si fermerà abbastanza rapidamente se si trova sulla traccia sbagliata (solo dirigendosi verso il basso nei "vicini" nodi figli

Per calcolare la distanza tra il punto p e la linea che divide lo spazio attraverso il nodo n, possiamo semplicemente "proiettare" il punto verso il basso sull'asse copiando la coordinata appropriata come gli assi sono tutti ortogonali (orizzontali o verticali).