Siéntete en la libertad de divulgar nuestros tutoriales y códigos en tus redes sociales, apóyanos para hacer crecer nuestra comunidad.
Solución:
Esto es muy tarde, pero para la posteridad:
En realidad, existe una técnica para convertir algoritmos procesados por lotes como KD-Tree en algoritmos incrementales: se llama static-a-transformación dinámica.
Para generar una variante incremental de un KD-Tree, almacena un conjunto de árboles en lugar de solo un árbol. cuando hay norte elementos en su estructura vecina más cercana, su estructura tendrá un árbol para cada bit “1” en la representación binaria de norte. Además, si el árbol T_i corresponde a la i-th bit de norteentonces árbol T_i contiene 2^i elementos.
Entonces, si tiene 11 elementos en su estructura, entonces norte = 11, o 1011 en binario, y por lo tanto tienes tres árboles: T_3, T_1y T_0 – con 8 elementos, 2 elementos y 1 elemento, respectivamente.
Ahora, insertemos un elemento. mi en nuestra estructura. Después de la inserción, tendremos 12 elementos o 1100 en binario. Comparando el binario nuevo y el anterior stringvemos eso T_3 no cambia, tenemos un nuevo árbol T_2 con 4 elementos, y árboles T_1 y T_0 ser eliminado Construimos el nuevo árbol. T_2 haciendo una inserción por lotes de mi junto con todos los elementos en los árboles “abajo” T_2que son T_1 y T_0.
De esta manera, creamos una estructura de consulta de puntos incrementales a partir de una static estructura básica. Sin embargo, hay una desaceleración asintótica en la “incrementalización” static estructuras como esta en forma de un extra registro (N) factor:
- insertando norte elementos en estructura: O(N log(N) log(n))
- consulta de vecino más cercano para la estructura con norte elementos: O(registro(n) registro(n))
Creo que el problema con la construcción incremental de un árbol KD o KNN es, como mencionaste en un comentario, que el árbol eventualmente se desequilibrará y no puedes hacer una rotación simple del árbol para solucionar los problemas de equilibrio y mantener consistencia. Como mínimo, la tarea de reequilibrio no es trivial y uno definitivamente no querría hacerlo en cada inserción. A menudo, uno elegirá construir un árbol con un método por lotes, insertar un montón de puntos nuevos y permitir que el árbol se desequilibre hasta cierto punto, y luego volver a equilibrarlo.
Algo muy similar a hacer es construir la estructura de datos por lotes para puntos M, usarla para puntos M’ y luego reconstruir la estructura de datos por lotes con puntos M+M’. Dado que el reequilibrio no es un algoritmo normal y rápido con el que estamos familiarizados para los árboles, la reconstrucción no es necesariamente lenta en comparación y, en algunos casos, puede ser más rápida (dependiendo de cómo sea la secuencia de los puntos que ingresan a su algoritmo incremental).
Dicho esto, la cantidad de código que escribe, la dificultad de depuración y la facilidad de comprensión de su código por parte de otros pueden ser significativamente menores si adopta el enfoque de reconstrucción. Si lo hace, puede usar un método por lotes y mantener una lista externa de puntos que aún no se han insertado en el árbol. Se puede usar un enfoque de fuerza bruta para garantizar que ninguno de estos esté más cerca que los del árbol.
Algunos enlaces a implementaciones/discusiones de Python están a continuación, pero no he encontrado ninguno que afirme explícitamente ser incremental. Buena suerte.
http://www.scipy.org/Cookbook/KDTree
http://cgi.di.uoa.gr/~compgeom/pycgalvisual/kdppython.shtml
http://sites.google.com/site/mikescoderama/Home/kd-tree-knn
http://en.wikipedia.org/wiki/Kd-tree
Nota: Mis comentarios aquí se aplican a espacios de alta dimensión. Si está trabajando en 2D o 3D, lo que he dicho puede no ser apropiado. (Si trabaja en espacios de dimensiones muy altas, use la fuerza bruta o el vecino más cercano).
Hay. El sitio web de Scipy Cookbook incluye una implementación completa de un algoritmo kNN que se puede actualizar de forma incremental.
Tal vez unas pocas líneas de antecedentes serían útiles para cualquier persona interesada pero que no esté familiarizada con la terminología.
Un motor kNN funciona con cualquiera de dos representaciones de datos: las distancias por pares entre todos los puntos en el conjunto de datos almacenados en un formato multidimensional. array (un matriz de distancia), o un árbol kdque solo almacena los puntos de datos en un árbol binario multidimensional.
Estas son solo dos operaciones que necesita un algoritmo KNN basado en árboles kd: crea el árbol a partir del conjunto de datos (análogo al capacitación paso realizado en modo por lotes en otros algoritmos ML), y busca en el árbol para encontrar ‘vecinos más cercanos’ (análogo al pruebas paso).
El entrenamiento en línea o incremental en el contexto de un algoritmo KNN (siempre y cuando esté basado en un árbol kd) significa insertar nodos a un árbol kd ya construido.
Volviendo a la implementación de kd-Tree en SciPy Cookbook: las líneas de código específicas responsables de la inserción de nodos aparecen después de la línea de comentario “insertar nodo en kd-tree” (de hecho, todo el código después de ese comentario se dirige a la inserción de nodos ).
Finalmente, hay una implementación de kd-tree en el módulo espacial de la biblioteca SciPy (scipy.espacial módulo) llamado KDTree (scipy.espacial.KDTree) pero no creo que admita la inserción de nodos, al menos esa función no está en los Documentos (no he mirado la fuente).
Te mostramos reseñas y puntuaciones
Agradecemos que desees añadir valor a nuestro contenido informacional colaborando tu experiencia en las críticas.