La búsqueda del vecino más cercano ( NNS ), como una forma de búsqueda de proximidad , es el problema de optimización que consiste en encontrar el punto de un conjunto dado que sea más cercano (o más similar) a un punto dado. La proximidad se expresa normalmente 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 el vol. 3 de The Art of Computer Programming (1973) lo llamó el problema de la oficina postal , refiriéndose a una aplicación de asignar a una residencia la oficina postal 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 triangular . Aún más común, se considera que M es el espacio vectorial de dimensión d 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 no se cumple la desigualdad triangular. [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 las estructuras de datos de búsqueda que se deben mantener. La observación informal, a la que se suele denominar la maldición de la dimensionalidad, afirma que no existe una solución exacta de propósito general para las NNS en el espacio euclidiano de alta dimensión que utilice preprocesamiento polinómico y tiempo de búsqueda polilogarítmico.
La solución más simple al problema de NNS es calcular la distancia desde el punto de consulta hasta cada uno de los demás puntos de la base de datos, manteniendo un registro del "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 a los enfoques de partición espacial en espacios de dimensiones superiores. [5]
Para la comparación de distancias no se necesita la distancia absoluta, sino solo 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á arrojando resultados idénticos.
Desde la década de 1970, la metodología de ramificación y acotación se ha aplicado al problema. En el caso del espacio euclidiano, este enfoque abarca métodos de índice espacial o de acceso espacial. Se han desarrollado varios métodos de partición espacial 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 mediante el recorrido del á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, también puede ser necesario evaluar las ramas vecinas que podrían contener resultados. 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 del peor caso es O ( kN ^(1-1/ k )) [7] Alternativamente, la estructura de datos del árbol R se diseñó 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 generar vecinos más cercanos no solo para la distancia euclidiana, sino que también pueden usarse con otras distancias.
En el caso del espacio métrico general, el método de ramificación y acotación se conoce como método de árbol métrico . Algunos ejemplos concretos son los métodos de árbol vp y árbol BK .
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, una posible solución al problema de encontrar el punto de nube de puntos más cercano al punto de consulta se da en la siguiente descripción de un algoritmo.
(En sentido estricto, no puede existir tal punto, porque puede no ser único. Pero en la práctica, normalmente sólo nos interesa encontrar cualquiera de los subconjuntos de todos los puntos de la nube de puntos que existen a la distancia más corta de un punto de consulta dado). La idea es, para cada ramificación del árbol, suponer que el punto más cercano en la nube reside en el semiespacio que contiene el punto de consulta. Puede que no sea el caso, pero es una buena heurística. Después de haber pasado recursivamente por todo el problema de resolver el problema para el semiespacio supuesto, 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 hay entre el punto de consulta y el punto más cercano posible que podría 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 semiespacio. Si existe tal necesidad, entonces debe tomarse la molestia de resolver el problema para la otra mitad del espacio, y luego comparar su resultado con el resultado anterior, y luego devolver el resultado correcto. El rendimiento de este algoritmo es más cercano al tiempo logarítmico que al tiempo lineal cuando el punto de consulta está cerca de la nube, porque como la distancia entre el punto de consulta y el punto de nube de puntos más cercano se acerca a cero, el algoritmo solo necesita realizar una búsqueda utilizando el punto de consulta como clave para obtener el resultado correcto.
Se permite que un algoritmo de búsqueda de vecino más cercano aproximado devuelva puntos cuya distancia desde la consulta sea, en la mayoría de los casos, 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 uno 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 mundo pequeño navegables [10] y HNSW [11] [12] ) se consideran el estado del arte actual para la búsqueda aproximada de vecinos más cercanos.
Los métodos se basan en el recorrido voraz en grafos 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 grafo . El algoritmo básico, búsqueda voraz, 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 la 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 grafos de vecindad de proximidad fue explotada en múltiples publicaciones, incluyendo el artículo seminal de Arya y Mount, [13] en el sistema VoroNet para el plano, [14] en el sistema RayNet para el , [15] y en los algoritmos Navigable Small World, [10] Metrized Small World [16] y HNSW [11] [12] para el caso general de espacios con una función de distancia. Estos trabajos fueron precedidos por un artículo pionero de Toussaint, en el que introdujo el concepto de un grafo de vecindad relativa . [17]
El hashing sensible a la localidad (LSH) es una técnica para agrupar puntos en el espacio en "cubos" en función de una métrica de distancia que opera sobre los puntos. Los puntos que están cerca entre sí según la métrica elegida se asignan al mismo cubo 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 son un mapa 3D 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 por una proyección a una cuadrícula bidimensional y supone que los datos son uniformes espacialmente 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 trabaja con datos de sensores 3D en aplicaciones como topografía, robótica y visión estereoscópica, 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 ) o O ( K ) para el problema del vecino k más cercano cuando se aplica a datos de visión estereoscópica 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 prefiltrar 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 el cálculo de la distancia. [19]
El método VA-file 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 cuantificació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, índices basados en árboles y escaneo secuencial. [20] [21] También hay que tener en cuenta los paralelismos entre el agrupamiento y LSH.
Existen numerosas variantes del problema NNS y las dos más conocidas son la búsqueda del vecino más cercano k y la búsqueda del vecino más cercano aproximado ε .
La búsqueda de k -vecinos más cercanos identifica los k vecinos más cercanos a la consulta. Esta técnica se utiliza comúnmente en análisis predictivos para estimar o clasificar un punto en función del consenso de sus vecinos. Los gráficos de k -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 ser aceptable recuperar una "buena estimación" del vecino más cercano. En esos casos, podemos utilizar 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 esté consultando.
Los algoritmos que respaldan la búsqueda aproximada del vecino más cercano incluyen el hash sensible a la localidad , el mejor bin primero y la búsqueda basada en árbol de descomposición de caja equilibrada. [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 de esta que depende de la distancia al vecino anterior. Se utiliza en CBIR para recuperar imágenes a través de una "consulta por ejemplo" utilizando la similitud entre características locales. En términos más generales, se utiliza en varios problemas de coincidencia .
Los vecinos cercanos de radio fijo son un problema en el que se desea encontrar de manera eficiente todos los puntos dados en el espacio euclidiano dentro de una distancia fija dada 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 ), podemos tener N puntos de datos y desear saber cuál es el vecino más cercano para cada uno de esos N puntos . Esto podría, por supuesto, lograrse ejecutando una búsqueda de vecino más cercano una vez para cada punto, pero una estrategia mejorada sería un algoritmo que explote la redundancia de información entre estas N consultas para producir una búsqueda más eficiente. Como 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 (que incluye 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 pueden encontrar en tiempo O ( mn log n ). [23] [24]
{{cite journal}}: Requiere citar revista |journal=( ayuda )