La búsqueda de vecino más cercano ( NNS ), como forma de búsqueda de proximidad , es el problema de optimización de encontrar el punto en un conjunto dado que sea más cercano (o más similar) a un punto determinado. La cercanía se expresa típicamente en términos de una función de disimilitud: cuanto menos similares sean los objetos, mayores serán los valores de la función.
Formalmente, el problema de búsqueda del vecino más cercano (NN) se define de la siguiente manera: dado un conjunto S de puntos en un espacio M y un punto de consulta q ∈ M , encuentre el punto más cercano en S a q . Donald Knuth en vol. 3 de The Art of Computer Programming (1973) lo llamó el problema de la oficina de correos , refiriéndose a una aplicación de asignar a una residencia la oficina de correos más cercana. Una generalización directa de este problema es una búsqueda k -NN, donde necesitamos encontrar los k puntos más cercanos.
Lo más común es que M sea un espacio métrico y la disimilitud se exprese como una métrica de distancia , que es simétrica y satisface la desigualdad del triángulo . Aún más común, se considera que M es el espacio vectorial d -dimensional donde la disimilitud se mide utilizando la distancia euclidiana , la distancia de Manhattan u otra métrica de distancia . Sin embargo, la función de disimilitud puede ser arbitraria. Un ejemplo es la divergencia asimétrica de Bregman , para la cual la desigualdad del triángulo no se cumple. [1]
El problema de búsqueda del vecino más cercano surge en numerosos campos de aplicación, entre ellos:
Se han propuesto varias soluciones al problema de las NNS. La calidad y utilidad de los algoritmos están determinadas por la complejidad temporal de las consultas, así como por la complejidad espacial de cualquier estructura de datos de búsqueda que deba mantenerse. La observación informal generalmente conocida como la maldición de la dimensionalidad establece que no existe una solución exacta de propósito general para NNS en el espacio euclidiano de alta dimensión utilizando preprocesamiento polinómico y tiempo de búsqueda polilogarítmico.
La solución más sencilla al problema NNS es calcular la distancia desde el punto de consulta a todos los demás puntos de la base de datos, realizando un seguimiento de lo "mejor hasta ahora". Este algoritmo, a veces denominado enfoque ingenuo, tiene un tiempo de ejecución de O ( dN ), donde N es la cardinalidad de S y d es la dimensionalidad de S. No hay estructuras de datos de búsqueda que mantener, por lo que la búsqueda lineal no tiene complejidad espacial más allá del almacenamiento de la base de datos. La búsqueda ingenua puede, en promedio, superar los enfoques de partición de espacio en espacios de dimensiones superiores. [5]
La distancia absoluta no es necesaria para comparar distancias, sólo la distancia relativa. En los sistemas de coordenadas geométricas, el cálculo de la distancia se puede acelerar considerablemente omitiendo el cálculo de la raíz cuadrada del cálculo de la distancia entre dos coordenadas. La comparación de distancias seguirá dando resultados idénticos.
Desde la década de 1970, se ha aplicado al problema la metodología de rama y encuadernación . En el caso del espacio euclidiano, este enfoque abarca el índice espacial o métodos de acceso espacial. Se han desarrollado varios métodos de partición del espacio para resolver el problema NNS. Quizás el más simple sea el árbol kd , que biseca iterativamente el espacio de búsqueda en dos regiones que contienen la mitad de los puntos de la región principal. Las consultas se realizan atravesando el árbol desde la raíz hasta una hoja evaluando el punto de consulta en cada división. Dependiendo de la distancia especificada en la consulta, es posible que también sea necesario evaluar las ramas vecinas que puedan contener visitas. Para un tiempo de consulta de dimensión constante, la complejidad promedio es O (log N ) [6] en el caso de puntos distribuidos aleatoriamente, la complejidad en el peor de los casos es O ( kN ^(1-1/ k )) [7] Alternativamente, los datos del árbol R La estructura fue diseñada para admitir la búsqueda del vecino más cercano en un contexto dinámico, ya que tiene algoritmos eficientes para inserciones y eliminaciones como el árbol R* . [8] Los árboles R pueden producir vecinos más cercanos no sólo para distancias euclidianas, sino que también pueden usarse con otras distancias.
En el caso del espacio métrico general, el enfoque de ramificación y límite se conoce como enfoque de árbol métrico . Ejemplos particulares incluyen los métodos vp-tree y BK-tree .
Utilizando un conjunto de puntos tomados de un espacio tridimensional y colocados en un árbol BSP , y dado un punto de consulta tomado del mismo espacio, se proporciona una posible solución al problema de encontrar el punto de la nube de puntos más cercano al punto de consulta. en la siguiente descripción de un algoritmo.
(Estrictamente hablando, tal punto puede no existir, porque puede no ser único. Pero en la práctica, generalmente solo nos preocupamos por encontrar cualquiera del subconjunto de todos los puntos de la nube de puntos que existen a la distancia más corta a un punto de consulta determinado. ) La idea es, para cada ramificación del árbol, adivinar que el punto más cercano en la nube reside en el medio espacio que contiene el punto de consulta. Puede que este no sea el caso, pero es una buena heurística. Después de haber pasado por todos los problemas de forma recursiva para resolver el problema del medio espacio adivinado, ahora compare la distancia devuelta por este resultado con la distancia más corta desde el punto de consulta hasta el plano de partición. Esta última distancia es la que existe entre el punto de consulta y el punto más cercano posible que pueda existir en el semiespacio no buscado. Si esta distancia es mayor que la devuelta en el resultado anterior, entonces claramente no hay necesidad de buscar en el otro medio espacio. Si existe tal necesidad, entonces debe tomarse la molestia de resolver el problema para la otra mitad del espacio, luego comparar su resultado con el resultado anterior y luego devolver el resultado correcto. El rendimiento de este algoritmo está más cerca del tiempo logarítmico que del tiempo lineal cuando el punto de consulta está cerca de la nube, porque a medida que la distancia entre el punto de consulta y el punto de la nube de puntos más cercano se acerca a cero, el algoritmo solo necesita realizar una búsqueda usando el punto de consulta como clave para obtener el resultado correcto.
Un algoritmo de búsqueda de vecino más cercano aproximado puede devolver puntos cuya distancia desde la consulta es, como máximo, la distancia desde la consulta hasta sus puntos más cercanos. El atractivo de este enfoque es que, en muchos casos, un vecino más cercano aproximado es casi tan bueno como el exacto. En particular, si la medida de la distancia captura con precisión la noción de calidad del usuario, entonces las pequeñas diferencias en la distancia no deberían importar. [9]
Los métodos de gráficos de proximidad (como los gráficos de mundos pequeños navegables [10] y HNSW [11] [12] ) se consideran el estado actual del arte para la búsqueda aproximada de vecinos más cercanos.
Los métodos se basan en el recorrido codicioso en gráficos de vecindad de proximidad en los que cada punto está asociado de forma única con el vértice . La búsqueda de los vecinos más cercanos a una consulta q en el conjunto S toma la forma de búsqueda del vértice en el gráfico . El algoritmo básico (búsqueda codiciosa) funciona de la siguiente manera: la búsqueda comienza desde un vértice de punto de entrada calculando las distancias desde la consulta q a cada vértice de su vecindad , y luego encuentra un vértice con el valor de distancia mínimo. Si el valor de distancia entre la consulta y el vértice seleccionado es menor que el valor entre la consulta y el elemento actual, entonces el algoritmo se mueve al vértice seleccionado y se convierte en un nuevo punto de entrada. El algoritmo se detiene cuando alcanza un mínimo local: un vértice cuya vecindad no contiene un vértice que esté más cerca de la consulta que el propio vértice.
La idea de los gráficos de vecindad de proximidad se explotó en múltiples publicaciones, incluido el artículo fundamental de Arya y Mount, [13] en el sistema VoroNet para el avión, [14] en el sistema RayNet para el , [15] y en Navigable Small. World, [10] Metrized Small World [16] y HNSW [11] [12] algoritmos para el caso general de espacios con función de distancia. Estos trabajos fueron precedidos por un artículo pionero de Toussaint, en el que introdujo el concepto de gráfico de vecindad relativa . [17]
El hash sensible a la localidad (LSH) es una técnica para agrupar puntos en el espacio en "cubos" en función de alguna métrica de distancia que opera en los puntos. Los puntos que están cerca entre sí según la métrica elegida se asignan al mismo segmento con alta probabilidad. [18]
El árbol de cobertura tiene un límite teórico que se basa en la constante de duplicación del conjunto de datos. El límite del tiempo de búsqueda es O ( c 12 log n ) donde c es la constante de expansión del conjunto de datos.
En el caso especial en el que los datos sean un mapa tridimensional denso de puntos geométricos, la geometría de proyección de la técnica de detección se puede utilizar para simplificar drásticamente el problema de búsqueda. Este enfoque requiere que los datos 3D estén organizados mediante una proyección en una cuadrícula bidimensional y supone que los datos son espacialmente uniformes en las celdas de la cuadrícula vecinas con la excepción de los límites de los objetos. Estas suposiciones son válidas cuando se trata de datos de sensores 3D en aplicaciones como topografía, robótica y visión estéreo, pero pueden no ser válidas para datos no organizados en general. En la práctica, esta técnica tiene un tiempo de búsqueda promedio de O ( 1 ) u O ( K ) para el k problema del vecino más cercano cuando se aplica a datos de visión estéreo del mundo real. [4]
En espacios de alta dimensión, las estructuras de indexación de árboles se vuelven inútiles porque de todos modos es necesario examinar un porcentaje cada vez mayor de los nodos. Para acelerar la búsqueda lineal, se utiliza una versión comprimida de los vectores de características almacenados en la RAM para filtrar previamente los conjuntos de datos en una primera ejecución. Los candidatos finales se determinan en una segunda etapa utilizando los datos sin comprimir del disco para calcular la distancia. [19]
El enfoque de archivos VA es un caso especial de búsqueda basada en compresión, donde cada componente de característica se comprime de manera uniforme e independiente. La técnica de compresión óptima en espacios multidimensionales es la Cuantización Vectorial (VQ), implementada mediante agrupamiento. La base de datos se agrupa y se recuperan los grupos más "prometedores". Se han observado enormes avances con respecto a VA-File, los índices basados en árboles y el escaneo secuencial. [20] [21] Tenga en cuenta también los paralelismos entre la agrupación y la LSH.
Existen numerosas variantes del problema NNS y las dos más conocidas son la k -búsqueda de vecino más cercano y la búsqueda de vecino más cercano ε -aproximada .
La búsqueda de k vecinos más cercanos identifica los k vecinos más cercanos a la consulta. Esta técnica se utiliza habitualmente en análisis predictivo para estimar o clasificar un punto en función del consenso de sus vecinos. Los k gráficos de vecinos más cercanos son gráficos en los que cada punto está conectado a sus k vecinos más cercanos.
En algunas aplicaciones puede resultar aceptable recuperar una "buena suposición" del vecino más cercano. En esos casos, podemos usar un algoritmo que no garantiza devolver el vecino más cercano real en todos los casos, a cambio de una mayor velocidad o ahorro de memoria. A menudo, un algoritmo de este tipo encontrará el vecino más cercano en la mayoría de los casos, pero esto depende en gran medida del conjunto de datos que se consulta.
Los algoritmos que admiten la búsqueda aproximada del vecino más cercano incluyen hash sensible a la localidad , mejor contenedor primero y búsqueda equilibrada basada en árbol de descomposición de cajas. [22]
La relación de distancia del vecino más cercano no aplica el umbral a la distancia directa desde el punto original al vecino retador, sino a una relación que depende de la distancia al vecino anterior. Se utiliza en CBIR para recuperar imágenes mediante una "consulta por ejemplo" utilizando la similitud entre características locales. De manera más general, está involucrado en varios problemas de emparejamiento .
Los vecinos cercanos de radio fijo son el problema en el que se desea encontrar de manera eficiente todos los puntos dados en el espacio euclidiano dentro de una distancia fija determinada desde un punto específico. Se supone que la distancia es fija, pero el punto de consulta es arbitrario.
Para algunas aplicaciones (por ejemplo, estimación de entropía ), es posible que tengamos N puntos de datos y deseemos saber cuál es el vecino más cercano para cada uno de esos N puntos . Por supuesto, esto podría lograrse ejecutando una búsqueda del vecino más cercano una vez por cada punto, pero una estrategia mejorada sería un algoritmo que aproveche la redundancia de información entre estas N consultas para producir una búsqueda más eficiente. Como un ejemplo simple: cuando encontramos la distancia del punto X al punto Y , eso también nos dice la distancia del punto Y al punto X , por lo que el mismo cálculo se puede reutilizar en dos consultas diferentes.
Dada una dimensión fija, una norma positiva semidefinida (incluyendo así cada norma L p ) y n puntos en este espacio, el vecino más cercano de cada punto se puede encontrar en tiempo O ( n log n ) y los m vecinos más cercanos de cada punto se puede encontrar en tiempo O ( mn log n ). [23] [24]
{{cite journal}}: Citar diario requiere |journal=( ayuda )