¿Cómo funciona la búsqueda del vecino KD más cercano?

Question

Estoy mirando la página de Wikipedia para árboles KD. Como ejemplo, implementé, en python, el algoritmo para construir un árbol kd en la lista.

El algoritmo para realizar búsquedas KNN con un árbol KD, sin embargo, cambia de idioma y no está totalmente claro. La explicación en inglés comienza a tener sentido, pero partes de ella (como el área donde "desenrollan la recursión" para verificar otros nodos de hoja) realmente no tienen ningún sentido para mí.

¿Cómo funciona esto, y cómo se puede hacer una búsqueda KNN con un árbol KD en python? Esto no pretende ser una pregunta de tipo "send me the code!", y no espero eso. Sólo una breve explicación favor :)

Answer 1

Este book introduction, página 3:

Dado un conjunto de n puntos en un espacio de dimensión d, el kd-árbol se construye recursivamente de la siguiente manera. Primero, se encuentra una mediana de los valores de las coordenadas ith de los puntos (inicialmente, i = 1). Es decir, se calcula un valor M, , de modo que al menos el 50% de los puntos tenga su coordenada i-ésima igual a a M, mientras que al menos el 50% de los puntos tenga su coordenada i-ésima menor que o igual a M. El valor de x se almacena, y el conjunto P se divide en en PL y PR, donde PL contiene solo los puntos con su coordenada ith menor o igual a M, y | PR | = | PL | ± 1. El proceso se repite luego recursivamente tanto en PL como en PR, con i reemplazado por i + 1 (o 1, si i = d). Cuando el conjunto de puntos en un nodo tiene el tamaño 1, la recursión se detiene.

En los siguientes párrafos se explica su uso para resolver al vecino más cercano.

O, aquí está el original 1975 paper by Jon Bentley.

EDIT: Debo añadir que SciPy tiene una aplicación kdtree:

• scipy.spatial
• another Stack Overflow question

Answer 2

acabo de pasar algún tiempo descifrando la descripción Wikipedia del algoritmo de mí mismo, y se le ocurrió la siguiente implementación de Python que puede ayudar: https://gist.github.com/863301

La primera fase de closest_point es una primera búsqueda de profundidad simple para encontrar el nodo de hoja coincidente.

En lugar de simplemente devolviendo el mejor nodo encontrado de nuevo la pila de llamadas, un segundo controles de fase para ver si puede haber un nodo más cercano en el lado "distancia": (diagrama arte ASCII)

  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 

El nodo actual n divide el espacio a lo largo de una línea, por lo que solo tenemos que mirar en el lado "ausente" si el "error" entre el punto p y la mejor coincidencia es mayor que la distancia desde el punto p y la línea n . Si es así, entonces verificamos si hay algún punto en el lado "ausente" que esté más cerca.

Como nuestro mejor nodo coincidente se pasa a esta segunda prueba, no tiene que hacer un recorrido completo de la bifurcación y se detendrá bastante rápido si está en la pista incorrecta (solo se dirige hacia los nodos secundarios "cercanos" hasta que llega a una hoja.)

para calcular la distancia entre el punto de p y la división borde del espacio a través del nodo n, podemos simplemente "proyecto" el punto hacia abajo sobre el eje copiando el apropiado coordinar como los ejes son todos ortogonales (horizontales o verticales).