En informática , un árbol de bolas , balltree [1] o árbol métrico , es una estructura de datos de partición espacial para organizar puntos en un espacio multidimensional. Un árbol de bolas divide los puntos de datos en un conjunto anidado de bolas . La estructura de datos resultante tiene características que la hacen útil para varias aplicaciones, en particular la búsqueda del vecino más cercano .
Un árbol de bolas es un árbol binario en el que cada nodo define una bola de dimensión D que contiene un subconjunto de los puntos que se buscarán. Cada nodo interno del árbol divide los puntos de datos en dos conjuntos disjuntos que están asociados con diferentes bolas. Si bien las bolas pueden intersecarse, cada punto se asigna a una u otra bola en la partición según su distancia desde el centro de la bola. Cada nodo de hoja en el árbol define una bola y enumera todos los puntos de datos dentro de esa bola.
Cada nodo del árbol define la bola más pequeña que contiene todos los puntos de datos en su subárbol. Esto da lugar a la útil propiedad de que, para un punto de prueba dado t fuera de la bola, la distancia a cualquier punto en una bola B en el árbol es mayor o igual que la distancia desde t hasta la superficie de la bola. Formalmente: [2]
¿Dónde está la distancia mínima posible desde cualquier punto de la bola B hasta algún punto t ?
Los árboles de bolas están relacionados con el árbol M , pero solo admiten divisiones binarias, mientras que en el árbol M cada nivel se divide para plegarse, lo que conduce a una estructura de árbol más superficial, por lo tanto, necesita menos cálculos de distancia, lo que generalmente produce consultas más rápidas. Además, los árboles M se pueden almacenar mejor en el disco , que está organizado en páginas . El árbol M también mantiene las distancias desde el nodo principal precalculadas para acelerar las consultas.
Los árboles de puntos de vista también son similares, pero se dividen en una sola bola y los datos restantes, en lugar de usar dos bolas.
Existen varios algoritmos de construcción de árboles de bolas. [1] El objetivo de un algoritmo de este tipo es producir un árbol que admita de manera eficiente consultas del tipo deseado (por ejemplo, del vecino más cercano) en el caso promedio. Los criterios específicos de un árbol ideal dependerán del tipo de pregunta que se esté respondiendo y de la distribución de los datos subyacentes. Sin embargo, una medida generalmente aplicable de un árbol eficiente es aquella que minimiza el volumen total de sus nodos internos. Dadas las variadas distribuciones de los conjuntos de datos del mundo real, esta es una tarea difícil, pero existen varias heurísticas que particionan bien los datos en la práctica. En general, existe una compensación entre el costo de construir un árbol y la eficiencia lograda por esta métrica. [2]
En esta sección se describe brevemente el más simple de estos algoritmos. Stephen Omohundro ofreció un análisis más detallado de cinco algoritmos. [1]
El procedimiento más simple de este tipo se denomina " algoritmo de construcción k -d", por analogía con el proceso utilizado para construir árboles k -d . Se trata de un algoritmo fuera de línea , es decir, un algoritmo que opera sobre todo el conjunto de datos a la vez. El árbol se construye de arriba hacia abajo dividiendo recursivamente los puntos de datos en dos conjuntos. Las divisiones se eligen a lo largo de la única dimensión con la mayor dispersión de puntos, y los conjuntos se dividen por el valor medio de todos los puntos a lo largo de esa dimensión. Encontrar la división para cada nodo interno requiere un tiempo lineal en el número de muestras contenidas en ese nodo, lo que produce un algoritmo con complejidad temporal , donde n es el número de puntos de datos.
La función construct_balltree tiene como entrada: D , una matriz de puntos de datos. Salida: B , la raíz de un árbol de bolas construido. Si queda un solo punto , entonces crea una hoja B que contenga el único punto en D y devuelve B; de lo contrario, sea c la dimensión de mayor dispersión. Sea p el punto central seleccionado considerando c sean L , R los conjuntos de puntos que se encuentran a la izquierda y a la derecha de la mediana a lo largo de la dimensión c. Cree B con dos hijos: B.pivot := p B.child1 := construct_balltree(L), B.child2 := construct_balltree(R), sea B .radio la distancia máxima desde p entre los hijos devuelve B fin si fin de la función
Una aplicación importante de los árboles de bolas es acelerar las consultas de búsqueda del vecino más cercano , en las que el objetivo es encontrar los k puntos en el árbol que están más cerca de un punto de prueba dado por alguna métrica de distancia (por ejemplo, la distancia euclidiana ). Un algoritmo de búsqueda simple, a veces llamado KNS1, explota la propiedad de distancia del árbol de bolas. En particular, si el algoritmo está buscando la estructura de datos con un punto de prueba t y ya ha visto algún punto p que es el más cercano a t entre los puntos encontrados hasta ahora, entonces cualquier subárbol cuya bola esté más lejos de t que p puede ignorarse para el resto de la búsqueda.
El algoritmo de vecino más cercano del árbol de bolas examina los nodos en orden de profundidad, comenzando por la raíz. Durante la búsqueda, el algoritmo mantiene una cola de prioridad máxima (a menudo implementada con un montón ), denotada aquí como Q , de los k puntos más cercanos encontrados hasta el momento. En cada nodo B , puede realizar una de tres operaciones, antes de devolver finalmente una versión actualizada de la cola de prioridad:
Realizar la búsqueda recursiva en el orden descrito en el punto 3 anterior aumenta la probabilidad de que el siguiente elemento secundario se elimine por completo durante la búsqueda.
La función knn_search se ingresa: t, el punto de destino de la consulta k, el número de vecinos más cercanos de t a buscar Q, cola de máxima prioridad que contiene como máximo k puntos B, un nodo, o bola, en el árbol producción: Q, que contiene los k vecinos más cercanos dentro de B si distancia(t, B.pivot) - B.radius ≥ distancia(t, Q.first) entonces devuelve Q sin cambios ; de lo contrario, si B es un nodo hoja , entonces para cada punto p en B hazlo si distancia(t, p) < distancia(t, Q.first) entonces añadir p a Q si tamaño(Q) > k entonces eliminar el vecino más alejado de Q Fin si Fin si Repetir de lo contrario Sea child1 el nodo hijo más cercano a t Sea child2 el nodo hijo más alejado de t knn_search(t, k, Q, niño1) knn_search(t, k, Q, niño2) fin si retorna Q fin de función [2]
En comparación con varias otras estructuras de datos, se ha demostrado que los árboles de bolas funcionan bastante bien en el problema de búsqueda del vecino más cercano, particularmente a medida que aumenta su número de dimensiones. [3] [4] Sin embargo, la mejor estructura de datos del vecino más cercano para una aplicación determinada dependerá de la dimensionalidad, el número de puntos de datos y la estructura subyacente de los datos.
