Hispanopedia Wiki
Articulo de referencia

Búsqueda del vecino más cercano

La búsqueda del vecino más cercano ( NNS , por sus siglas en inglés), como una forma de búsqueda de proximidad , es el problema de optimización que consiste en encontrar el punt...

Hispanopedia WikiContenido en espanolLectura gratuita

La búsqueda del vecino más cercano ( NNS , por sus siglas en inglés), como una forma de búsqueda de proximidad , es el problema de optimización que consiste en encontrar el punto en un conjunto dado que sea el más cercano (o más similar) a un punto dado. La proximidad 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 consultaq∈METRO{\displaystyle q\in M}, encontrar el punto más cercano en S a q . Donald Knuth, en el volumen 3 de The Art of Computer Programming (1973), lo denominó el problema de la oficina de correos , refiriéndose a una aplicación que consiste en 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.

Generalmente, M es un espacio métrico y la disimilitud se expresa como una métrica de distancia , que es simétrica y satisface la desigualdad triangular . Aún más común es que M sea 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 de Bregman asimétrica , para la cual no se cumple la desigualdad triangular. [ 1 ]

Aplicaciones

El problema de la búsqueda del vecino más cercano surge en numerosos campos de aplicación, entre los que se incluyen:

Métodos

Se han propuesto diversas soluciones al problema NNS. La calidad y utilidad de los algoritmos dependen de la complejidad temporal de las consultas, así como de la complejidad espacial de las estructuras de datos de búsqueda que deben mantenerse. La observación informal conocida como la maldición de la dimensionalidad afirma que no existe una solución exacta de propósito general para NNS en espacios euclidianos de alta dimensión utilizando preprocesamiento polinomial y tiempo de búsqueda polilogarítmico.

Métodos exactos

La solución más sencilla al problema NNS consiste en calcular la distancia desde el punto de consulta a todos los demás puntos de la base de datos, registrando el "mejor resultado hasta el momento". 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 de espacio en espacios de mayor dimensión. [ 7 ]

Para comparar distancias, no se requiere la distancia absoluta, solo la relativa. En sistemas de coordenadas geométricas, el cálculo de la distancia se puede acelerar considerablemente omitiendo la raíz cuadrada. Aun así, la comparación de distancias dará resultados idénticos.

partición del espacio

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 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 padre. 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 coincidencias. Para un tiempo de consulta de dimensión constante, la complejidad promedio es O (log N ) [ 8 ] en el caso de puntos distribuidos aleatoriamente, la complejidad del peor caso es O ( kN ^(1-1/ k )) [ 9 ] Alternativamente, la estructura de datos del árbol R 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* . [ 10 ] Los árboles R pueden generar vecinos más cercanos no solo para la distancia euclidiana, sino que también se pueden usar con otras distancias. 

En el caso de espacios métricos generales, el método de ramificación y acotación se conoce como método del árbol métrico . Algunos ejemplos concretos son 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, una posible solución al problema de encontrar el punto de la nube de puntos más cercano al punto de consulta se presenta en la siguiente descripción de un algoritmo.

(Estrictamente hablando, tal punto podría no existir, ya que podría no ser único. Pero en la práctica, generalmente solo nos interesa encontrar cualquiera de los puntos del subconjunto de todos los puntos de la nube de puntos que se encuentran 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 semiplano que contiene el punto de consulta. Esto podría no ser cierto, pero es una buena heurística. Después de haber realizado recursivamente todo el proceso de resolver el problema para el semiplano supuesto, ahora se compara la distancia devuelta por este resultado con la distancia más corta desde el punto de consulta al plano de partición. Esta última distancia es la que existe entre el punto de consulta y el punto posible más cercano que podría existir en el semiplano no explorado. Si esta distancia es mayor que la devuelta en el resultado anterior, entonces claramente no hay necesidad de explorar el otro semiplano. Si existe tal necesidad, entonces deberá resolver el problema para la otra mitad del espacio, comparar su resultado con el anterior y, finalmente, devolver el resultado correcto. El rendimiento de este algoritmo se aproxima más al tiempo logarítmico que al lineal cuando el punto de consulta está cerca de la nube de puntos, ya que, a medida que la distancia entre el punto de consulta y el punto más cercano de la nube de puntos se acerca a cero, el algoritmo solo necesita realizar una búsqueda utilizando el punto de consulta como clave para obtener el resultado correcto.

Métodos de aproximación

Se permite que un algoritmo de búsqueda del vecino más cercano aproximado devuelva puntos cuya distancia desde la consulta sea como máximodo{\displaystyle c}veces la distancia desde la consulta hasta sus puntos más cercanos. El atractivo de este enfoque radica en que, en muchos casos, un vecino más cercano aproximado es casi tan bueno como el exacto. En particular, si la medida de distancia captura con precisión la noción de calidad del usuario, entonces las pequeñas diferencias en la distancia no deberían importar. [ 11 ]

Búsqueda voraz en gráficos de vecindario de proximidad

Los métodos de grafos de proximidad (como los grafos de mundo pequeño navegables [ 12 ] y HNSW [ 13 ] [ 14 ] ) 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.GRAMO(V,mi){\displaystyle G(V,E)}en el que cada puntoincógnitai∈S{\displaystyle x_{i}\in S}está asociado de forma única con el vérticevi∈V{\displaystyle v_{i}\in V}La búsqueda de los vecinos más cercanos a una consulta q en el conjunto S toma la forma de buscar el vértice en el grafoGRAMO(V,mi){\displaystyle G(V,E)}. El algoritmo básico – búsqueda voraz – funciona de la siguiente manera: la búsqueda comienza desde un vértice de punto de entradavi∈V{\displaystyle v_{i}\in V}calculando las distancias desde la consulta q a cada vértice de su vecindario.{vj:(vi,vj)∈mi}{\displaystyle \{v_{j}:(v_{i},v_{j})\en E\}}Luego, encuentra un vértice con el valor de distancia mínimo. Si la distancia entre la consulta y el vértice seleccionado es menor que la distancia entre la consulta y el elemento actual, el algoritmo se mueve al vértice seleccionado, que se convierte en un nuevo punto de entrada. El algoritmo se detiene al alcanzar un mínimo local: un vértice cuyo vecindario no contiene ningún vértice más cercano a 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, [ 15 ] en el sistema VoroNet para el plano, [ 16 ] en el sistema RayNet para elminorte{\displaystyle \mathbb {E} ^{n}}, [ 17 ] y en los algoritmos Navigable Small World, [ 12 ] Metrized Small World [ 18 ] y HNSW [ 13 ] [ 14 ] 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 . [ 19 ]

Hashing sensible a la localidad

El hashing sensible a la localidad (LSH) es una técnica para agrupar puntos en el espacio en "cubos" basándose en alguna 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. [ 20 ]

Búsqueda del vecino más cercano en espacios con dimensión intrínseca pequeña

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 que los datos sean un mapa 3D denso de puntos geométricos, la geometría de proyección de la técnica de detección puede utilizarse para simplificar drásticamente el problema de búsqueda. Este enfoque requiere que los datos 3D estén organizados mediante una proyección a una cuadrícula bidimensional y supone que los datos son espacialmente suaves entre celdas de cuadrícula vecinas, con la excepción de los límites de los objetos. Estas suposiciones son válidas al trabajar con 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 problema del k -vecino más cercano cuando se aplica a datos de visión estéreo del mundo real. [ 6 ]

Archivos de aproximación vectorial

En espacios de alta dimensionalidad, las estructuras de indexación de árboles se vuelven inútiles porque, de todos modos, es necesario examinar un porcentaje cada vez mayor de 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 distancias. [ 21 ]

El enfoque VA-file es un caso especial de búsqueda basada en compresión, donde cada componente de características se comprime de forma 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 grandes mejoras con respecto a VA-File, los índices basados ​​en árboles y el escaneo secuencial. [ 22 ] [ 23 ] Cabe destacar también los paralelismos entre el agrupamiento y LSH.

Variantes

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 ε-aproximada .

k vecinos más cercanos

La búsqueda de k vecinos más cercanos identifica los k vecinos más próximos a la consulta. Esta técnica se utiliza comúnmente en análisis predictivo para estimar o clasificar un punto basándose en el consenso de sus vecinos. Los grafos de k vecinos más cercanos son grafos en los que cada punto está conectado a sus k vecinos más próximos.

vecino más cercano aproximado

En algunas aplicaciones, puede ser aceptable obtener una estimación aproximada del vecino más cercano. En esos casos, podemos usar un algoritmo que no garantiza encontrar el vecino más cercano en todos los casos, a cambio de mayor velocidad o ahorro de memoria. A menudo, dicho algoritmo encontrará el vecino más cercano en la mayoría de los casos, pero esto depende en gran medida del conjunto de datos consultado.

Los algoritmos que admiten 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 árboles de descomposición de cajas balanceadas . [ 24 ]

Relación de distancia al vecino más cercano

La razón de distancia al vecino más cercano no aplica el umbral a la distancia directa desde el punto original al vecino retador, sino a una razó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 forma más general, interviene en varios problemas de correspondencia .

Vecinos cercanos de radio fijo

El problema de los vecinos cercanos de radio fijo consiste en encontrar de forma eficiente todos los puntos del espacio euclidiano que se encuentren a una distancia fija de un punto específico. Se supone que la distancia es fija, pero el punto de consulta es arbitrario.

Todos los vecinos más cercanos

Para algunas aplicaciones (por ejemplo, la 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 lograrse, por supuesto, realizando una búsqueda del vecino más cercano una vez para 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 ejemplo sencillo: cuando encontramos la distancia del punto X al punto Y , eso también nos indica la distancia del punto Y al punto X , por lo que el mismo cálculo puede reutilizarse en dos consultas diferentes.

Dada una dimensión fija, una norma positiva semidefinida (que incluye toda 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 ). [ 25 ] [ 26 ]   

Véase también

Referencias

Citas

  1. ↑ Cayton, Lawrence (2008). "Recuperación rápida del vecino más cercano para divergencias de Bregman". Actas de la 25.ª Conferencia Internacional sobre Aprendizaje Automático . págs. 112–119 . doi : 10.1145/1390156.1390171 . ISBN  9781605582054. S2CID 12169321 . 
  2. ↑ Qiu, Deyuan, Stefan May y Andreas Nüchter. «Búsqueda del vecino más cercano acelerada por GPU para el registro 3D». Conferencia internacional sobre sistemas de visión por computadora. Springer, Berlín, Heidelberg, 2009.
  3. ↑ Becker, Ducas, Gama y Laarhoven. «Nuevas direcciones en la búsqueda del vecino más cercano con aplicaciones al cribado reticular». Actas del vigésimo séptimo simposio anual ACM-SIAM sobre algoritmos discretos (págs. 10-24). Sociedad de Matemáticas Industriales y Aplicadas.
  4. ↑ "¿Qué es una base de datos vectorial y cómo funciona?" . Pinecone . Consultado el 5 de mayo de 2026 .
  5. ↑ Lewis, Patrick; Perez, Ethan; Piktus, Aleksandra; Petroni, Fabio; Karpukhin, Vladimir; Goyal, Naman; Kuttler, Heinrich; Lewis, Mike; Yih, Wen-tau; Rocktaschel, Tim; Riedel, Sebastian; Kiela, Douwe (2020). "Generación aumentada por recuperación para tareas de PLN intensivas en conocimiento" . Advances in Neural Information Processing Systems . Recuperado el 5 de mayo de 2026 .
  6. 1 2 Bewley, A.; Upcroft, B. (2013). Ventajas de explotar la estructura de proyección para segmentar nubes de puntos 3D densas (PDF) . Conferencia australiana sobre robótica y automatización.
  7. ↑ Weber, Roger; Schek, Hans-J.; Blott, Stephen (1998). "Análisis cuantitativo y estudio de rendimiento de métodos de búsqueda de similitud en espacios de alta dimensión" (PDF) . VLDB '98 Actas de la 24.ª Conferencia Internacional sobre Bases de Datos Muy Grandes . págs. 194–205 . 
  8. ↑ Andrew Moore. "Un tutorial introductorio sobre árboles KD" (PDF) . Archivado del original (PDF) el 3 de marzo de 2016. Consultado el 3 de octubre de 2008 .
  9. ↑ Lee, DT ; Wong, CK (1977). "Análisis del peor caso para búsquedas de regiones y regiones parciales en árboles de búsqueda binaria multidimensionales y árboles cuaternarios balanceados". Acta Informatica . 9 (1): 23–29 . doi : 10.1007/BF00263763 . S2CID 36580055 . 
  10. ↑ Roussopoulos, N.; Kelley, S.; Vincent, FDR (1995). «Consultas del vecino más cercano». Actas de la conferencia internacional ACM SIGMOD de 1995 sobre gestión de datos – SIGMOD '95 . pág. 71. doi : 10.1145/223784.223794 . ISBN  0897917316.
  11. ↑ Andoni, A.; Indyk, P. (1 de octubre de 2006). «Algoritmos de hash casi óptimos para el vecino más cercano aproximado en altas dimensiones». 47.º Simposio Anual IEEE sobre Fundamentos de la Informática (FOCS'06) de 2006. págs. 459–468 . CiteSeerX 10.1.1.142.3471 . doi : 10.1109/FOCS.2006.49 . ISBN   978-0-7695-2720-8.
  12. 1 2 Malkov, Yury; Ponomarenko, Alexander; Logvinov, Andrey; Krylov, Vladimir (2012), Navarro, Gonzalo; Pestov, Vladimir (eds.), "Algoritmo distribuido escalable para el problema de búsqueda aproximada del vecino más cercano en espacios métricos generales de alta dimensión" , Similarity Search and Applications , vol. 7404, Berlín, Heidelberg: Springer Berlin Heidelberg, pp. 132–147 , doi : 10.1007/978-3-642-32153-5_10 , ISBN   978-3-642-32152-8, consultado el 16 de enero de 2024{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
  13. 1 2 Malkov, Yury; Yashunin, Dmitry (2016). "Búsqueda aproximada eficiente y robusta del vecino más cercano utilizando grafos jerárquicos navegables de mundo pequeño". arXiv : 1603.09320 [ cs.DS ].
  14. 1 2 Malkov, Yu A.; Yashunin, DA (2020-04-01). "Búsqueda eficiente y robusta del vecino más cercano aproximado mediante grafos de mundo pequeño navegables jerárquicos". IEEE Transactions on Pattern Analysis and Machine Intelligence . 42 (4): 824– 836. arXiv : 1603.09320 . Bibcode : 2020ITPAM..42..824M . doi : 10.1109/TPAMI.2018.2889473 . ISSN 0162-8828 . PMID 30602420 .  
  15. ↑ Arya, Sunil; Mount, David (1993). "Consultas aproximadas del vecino más cercano en dimensiones fijas". Actas del Cuarto Simposio Anual {ACM/SIGACT-SIAM} sobre Algoritmos Discretos, 25-27 de enero de 1993, Austin, Texas. : 271-280 .
  16. ↑ Olivier, Beaumont; Kermarrec, Anne-Marie; Marchal, Loris; Rivière, Etienne (2006). "Voro Net : Una red de objetos escalable basada en teselaciones de Voronoi" (PDF) . Simposio Internacional de Procesamiento Paralelo y Distribuido IEEE 2007. Vol. RR-5833. pp. 23–29 . doi : 10.1109/IPDPS.2007.370210 . ISBN   1-4244-0909-8. S2CID 8844431 . 
  17. ↑ Olivier, Beaumont; Kermarrec, Anne-Marie; Rivière, Etienne (2007). «Superposiciones multidimensionales peer-to-peer: aproximación de estructuras complejas». Principios de sistemas distribuidos . Notas de clase en informática. Vol. 4878. pp. 315–328 . CiteSeerX 10.1.1.626.2980 . doi : 10.1007/978-3-540-77096-1_23 . ISBN    978-3-540-77095-4.
  18. ↑ Malkov, Yury; Ponomarenko, Alexander; Krylov, Vladimir; Logvinov, Andrey (2014). "Algoritmo aproximado del vecino más cercano basado en grafos de mundo pequeño navegables". Information Systems . 45 : 61–68 . doi : 10.1016/j.is.2013.10.006 . S2CID 9896397 . 
  19. ↑ Toussaint, Godfried (1980). "El grafo de vecindad relativa de un conjunto planar finito". Pattern Recognition . 12 (4): 261– 268. Bibcode : 1980PatRe..12..261T . doi : 10.1016/0031-3203(80)90066-7 .
  20. ↑ A. Rajaraman y J. Ullman (2010). "Minería de conjuntos de datos masivos, Cap. 3" .
  21. ↑ Weber, Roger; Blott, Stephen. "Una estructura de datos basada en aproximación para la búsqueda de similitud" (PDF) . S2CID 14613657. Archivado del original (PDF) el 4 de marzo de 2017. {{cite journal}}: Para citar una revista se requiere |journal=( ayuda )
  22. ↑ Ramaswamy, Sharadh; Rose, Kenneth (2007). "Límite adaptativo de distancia de clúster para la búsqueda de similitud en bases de datos de imágenes". ICIP .
  23. ↑ Ramaswamy, Sharadh; Rose, Kenneth (2010). "Acotación adaptativa de la distancia de clúster para la indexación de alta dimensión". TKDE .
  24. ↑ Arya, S.; Mount, DM ; Netanyahu, NS ; Silverman, R.; Wu, A. (1998). "Un algoritmo óptimo para la búsqueda aproximada del vecino más cercano" (PDF) . Journal of the ACM . 45 (6): 891– 923. CiteSeerX 10.1.1.15.3125 . doi : 10.1145/293347.293348 . S2CID 8193729. Archivado del original (PDF) el 3 de marzo de 2016. Recuperado el 29 de mayo de 2009 .  
  25. ↑ Clarkson, Kenneth L. (1983), "Algoritmos rápidos para el problema de todos los vecinos más cercanos", 24.º Simposio IEEE sobre Fundamentos de la Informática (FOCS '83) , págs. 226-232 , doi : 10.1109/SFCS.1983.16 , ISBN  978-0-8186-0508-6, S2CID 16665268 .
  26. ↑ Vaidya, PM (1989). "Un algoritmo O ( n log n ) para el problema de todos los vecinos más cercanos" . Geometría discreta y computacional . 4 (1): 101– 115. doi : 10.1007/BF02187718 .  

Fuentes

  • Andrews, L. (noviembre de 2001). "Una plantilla para el problema del vecino más cercano" . C/C++ Users Journal . 19 (11): 40– 49. ISSN 1075-2838 . 
  • Arya, S.; Mount, DM ; Netanyahu, NS ; Silverman, R .; Wu, AY (1998). "Un algoritmo óptimo para la búsqueda aproximada del vecino más cercano en dimensiones fijas". Journal of the ACM . 45 (6): 891– 923. CiteSeerX 10.1.1.15.3125 . doi : 10.1145/293347.293348 . S2CID 8193729 .  
  • Beyer, K.; Goldstein, J.; Ramakrishnan, R.; Shaft, U. (1999). "¿Cuándo es significativo el vecino más cercano?". Actas del 7º ICDT .
  • Chen, Chung-Min; Ling, Yibei (2002). "Un estimador basado en muestreo para consultas Top-k". ICDE : 617–627 .
  • Samet, H. (2006). Fundamentos de estructuras de datos multidimensionales y métricas . Morgan Kaufmann. ISBN 978-0-12-369446-1.
  • Zezula, P.; Amato, G.; Dohnal, V.; Batko, M. (2006). Búsqueda de similitud: el enfoque del espacio métrico . Springer. ISBN 978-0-387-29146-8.

Lecturas adicionales

  • Shasha, Dennis (2004). High Performance Discovery in Time Series . Berlín: Springer. ISBN 978-0-387-00857-8.
  • Búsqueda de Vecinos Más Cercanos y Similitud : un sitio web dedicado a materiales educativos, software, literatura, investigadores, problemas abiertos y eventos relacionados con la búsqueda de vecinos más cercanos. Mantenido por Yury Lifshits.
  • Wiki de búsqueda de similitud : una colección de enlaces, personas, ideas, palabras clave, artículos, diapositivas, código y conjuntos de datos sobre vecinos más cercanos.