método eficiente para encontrar KNN de todos los nodos de un árbol KD-

Actualmente estoy tratando de encontrar K vecino más cercano de todos los nodos de unequilibrada KD-árbol (con K = 2).método eficiente para encontrar KNN de todos los nodos de un árbol KD-

Mi implementación es una variación del código del Wikipedia article y es decentemente rápido encontrar KNN de cualquier nodo O (log N).

El problema radica en el hecho de que necesito encontrar KNN de cada nodo. Próximamente con aproximadamente O (N log N) si repito sobre cada nodo y realizo la búsqueda.

¿Hay alguna forma más eficiente de hacerlo?

Fuente

2010-03-26 St. John Johnson

¿Desea almacenar el resultado en alguna lista o iterar sobre las tuplas (t, knn1, knn2)? –

Solo iterando. Aunque tengo curiosidad, ¿cuál sería la diferencia en el enfoque? –

La principal diferencia entre la búsqueda KNN y su búsqueda es que todos sus valores de búsqueda ya están en el árbol. Entonces su búsqueda comienza en un nodo que no es el nodo raíz. A partir de cada nodo puede recorrer el árbol, buscar 2 candidatos y recorrer hasta que no pueda haber otro candidato más cercano. Esto puede proteger algunos recorridos de nodo pero sigue siendo O (n log n) si el árbol está equilibrado. Tal vez haya una forma de reutilizar los cálculos (que aún será O (n log n)). –

alt text http://www.cs.umd.edu/~mount/ANN/Images/annspeckle.gif

Dependiendo de sus necesidades, es posible que desee experimentar con técnicas aproximadas. Para obtener más información, consulte el trabajo de Arya and Mount sobre el tema. Un documento clave es here. Los detalles de complejidad de BigO se encuentran en su '98 paper.

He utilizado su biblioteca en conjuntos de datos de gran dimensión con cientos de miles de elementos. Es más rápido que cualquier otra cosa que encontré. La biblioteca maneja búsquedas exactas y aproximadas. El paquete contiene algunas utilidades de la CLI que puede usar para experimentar fácilmente con su conjunto de datos; e incluso visualice el árbol kd (ver arriba).

FWIW: Usé el R Bindings.

Desde el manual de ANN:

... se ha demostrado por Arya y el Monte [AM93b] y Arya, et al. [AMN + 98] que si el usuario está dispuesto a tolerar un pequeña cantidad de error en la búsqueda (volviendo a un punto que no puede ser el vecino más cercano, pero no es significativamente más lejos del punto de consulta de el verdadero vecino más cercano ), entonces es posible lograr mejoras significativas en tiempo de ejecución. ANN es un sistema para que responde a las consultas del vecino más cercano exactamente y aproximadamente.

Fuente

2010-03-26 17:46:46

Guau, gracias por la investigación, Ryan. Lamentablemente, estoy buscando resultados precisos. Si KNN usando un KD-Tree está limitado a esta velocidad, tal vez estoy haciendo esta búsqueda con estructuras de datos incorrectas. ¿Alguna sugerencia alternativa? –

Como señala la última frase de esa cita de su manual, también puede realizar búsquedas exactas con esta biblioteca. "ANN es un sistema para responder las consultas del vecino más cercano exactamente y aproximadamente" –

La búsqueda aproximada a veces es útil. Intente primero buscar el camino probable y utilice un cálculo de distancia que sepa sobre hiperplanos y puntos a lo largo del camino. Si el punto final no es tan cercano a un hiperplano, generalmente es el vecino más cercano. – htmlfarmer

Si los nodos en sí son puntos de consulta, entonces el tiempo de búsqueda puede ser menor. Puede comenzar con la etapa de retroceso y los primeros nodos probados ya están cerca del punto de consulta. Entonces grandes áreas del árbol pueden podarse pronto.

El vecino más cercano es una relación simétrica (si n1 es el vecino más cercano de n2, lo mismo aplica para n2) por lo que solo necesita buscar la mitad de los nodos omitiendo todos los nodos ya marcados como vecinos más cercanos. Solo una idea.

También puedes probar la búsqueda de KD-Tree BBF (Best-Bin First), que te ayudará a buscar los nodos más cercanos (contenedores) antes. Lo he implementado en C#, así que escríbeme si está interesado en el código fuente.

Por supuesto, el tiempo de ejecución real depende de la dimensionalidad, la estructura del árbol KD y la distribución de puntos en su conjunto de datos.

El agrupamiento de los puntos también podría ser apropiado.

Fuente

2010-12-03 15:18:23 Libor

Utilicé el árbol de portadas para este problema. Aquí está el enlace: http://hunch.net/~jl/projects/cover_tree/cover_tree.html

En un conjunto de datos para 50M de tamaño (todas las consultas kNN, k = 100), el árbol de portada tomó 5.5s para la creación y 120s para las consultas. Ann lib tomó 3.3s para crear el árbol, y 138s para consultar.

actualizado: El vecino más cercano no es una relación simétrica. Considere esto: A (0,0) B (1,0) C (3,0). B es el más cercano para C, mientras que C no es el más cercano para B

Fuente

2011-11-08 03:23:55 Kanglai

¿Se necesitan todos los datos para caber en la RAM o solo en el árbol? – mrgloom

El término a buscar es knn join. Más precisamente, es probable que desee hacer una auto-unión.

Tal vez estos resultados de búsquedas ayuda:

http://scholar.google.com/scholar?q=k-d-tree+knn+join

Sólo he visto knn unirse a los algoritmos para la -tree * R. Sin embargo, en mis propios experimentos, no fueron capaces de superar una consulta repetida. Puede que me falten algunas ideas de implementación. Pero, en general, mantener los datos de forma apropiada para una unión en árbol es mucho más complicado que una consulta de knn única.

Fuente

2012-12-18 09:04:00

método eficiente para encontrar KNN de todos los nodos de un árbol KD-

Respuesta

Cuestiones relacionadas