stringtranslate.com

Búsqueda de vecino más cercano

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]

Aplicaciones

El problema de búsqueda del vecino más cercano surge en numerosos campos de aplicación, entre ellos:

Métodos

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.

Métodos exactos

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.

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

Métodos de aproximación

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]

Búsqueda codiciosa en gráficos de proximidad de vecindarios

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 vértice mismo.

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]

Hashing sensible a la localidad

El algoritmo de hash sensible a la localidad (LSH) es una técnica para agrupar puntos en el espacio en "grupos" según 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 grupo con alta probabilidad. [18]

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

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]

Archivos de aproximación vectorial

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.

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

k -vecinos más cercanos

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.

Vecino más cercano aproximado

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]

Relación de distancia del vecino más cercano

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. De manera más general, se utiliza en varios problemas de coincidencia .

Vecinos cercanos de radio fijo

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.

Todos los vecinos más cercanos

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]

Véase también

Referencias

Citas

  1. ^ Cayton, Lawerence (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.S2CID12169321  .​
  2. ^ Qiu, Deyuan, Stefan May y Andreas Nüchter. "Búsqueda del vecino más próximo acelerada por GPU para registro 3D". Conferencia internacional sobre sistemas de visión artificial. Springer, Berlín, Heidelberg, 2009.
  3. ^ Becker, Ducas, Gama y Laarhoven. "Nuevas direcciones en la búsqueda del vecino más próximo con aplicaciones al tamizado en red". Actas del vigésimo séptimo simposio anual ACM-SIAM sobre algoritmos discretos (pp. 10-24). Sociedad de Matemáticas Industriales y Aplicadas.
  4. ^ ab 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.
  5. ^ Weber, Roger; Schek, Hans-J.; Blott, Stephen (1998). "Un análisis cuantitativo y un estudio de rendimiento para 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 de Gran Tamaño . págs. 194–205.
  6. ^ Andrew Moore. "Un tutorial introductorio sobre árboles KD" (PDF) . Archivado desde el original (PDF) el 2016-03-03 . Consultado el 2008-10-03 .
  7. ^ 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 cuadráticos balanceados". Acta Informatica . 9 (1): 23–29. doi :10.1007/BF00263763. S2CID  36580055.
  8. ^ Roussopoulos, N.; Kelley, S.; Vincent, FDR (1995). "Consultas de vecino más próximo". Actas de la conferencia internacional ACM SIGMOD de 1995 sobre gestión de datos – SIGMOD '95 . p. 71. doi : 10.1145/223784.223794 . ISBN 0897917316.
  9. ^ Andoni, A.; Indyk, P. (1 de octubre de 2006). "Algoritmos de hash casi óptimos para el vecino más próximo aproximado en grandes dimensiones". 2006 47.° Simposio anual IEEE sobre fundamentos de la informática (FOCS'06) . pp. 459–468. CiteSeerX 10.1.1.142.3471 . doi :10.1109/FOCS.2006.49. ISBN .  978-0-7695-2720-8.
  10. ^ ab 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, págs. 132–147, doi :10.1007/978-3-642-32153-5_10, ISBN 978-3-642-32152-8, consultado el 16 de enero de 2024
  11. ^ ab Malkov, Yury; Yashunin, Dmitry (2016). "Búsqueda eficiente y robusta de vecino más cercano aproximado utilizando gráficos de mundo pequeño navegables jerárquicos". arXiv : 1603.09320 [cs.DS].
  12. ^ ab Malkov, Yu A.; Yashunin, DA (1 de abril de 2020). "Búsqueda eficiente y robusta del vecino más cercano aproximado mediante gráficos de mundo pequeño navegables jerárquicos". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . 42 (4): 824–836. arXiv : 1603.09320 . doi :10.1109/TPAMI.2018.2889473. ISSN  0162-8828. PMID  30602420.
  13. ^ Arya, Sunil; Mount, David (1993). "Consultas aproximadas de vecino más próximo en dimensiones fijas". Actas del Cuarto Simposio Anual {ACM/SIGACT-SIAM} sobre Algoritmos Discretos, 25-27 de enero de 1993, Austin, Texas. : 271–280.
  14. ^ 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 IEEE de procesamiento paralelo y distribuido de 2007. Vol. RR-5833. págs. 23–29. doi :10.1109/IPDPS.2007.370210. ISBN. 1-4244-0909-8.S2CID8844431  .​
  15. ^ Olivier, Beaumont; Kermarrec, Anne-Marie; Rivière, Etienne (2007). "Superposiciones multidimensionales de igual a igual: aproximación de estructuras complejas". Principles of Distributed Systems . Lecture Notes in Computer Science. Vol. 4878. págs. 315–328. CiteSeerX 10.1.1.626.2980 . doi :10.1007/978-3-540-77096-1_23. ISBN  978-3-540-77095-4.
  16. ^ Malkov, Yury; Ponomarenko, Alexander; Krylov, Vladimir; Logvinov, Andrey (2014). "Algoritmo aproximado del vecino más próximo basado en gráficos navegables de mundo pequeño". Sistemas de información . 45 : 61–68. doi :10.1016/j.is.2013.10.006. S2CID  9896397.
  17. ^ Toussaint, Godfried (1980). "El gráfico de vecindad relativa de un conjunto planar finito". Reconocimiento de patrones . 12 (4): 261–268. Código Bibliográfico :1980PatRe..12..261T. doi :10.1016/0031-3203(80)90066-7.
  18. ^ A. Rajaraman y J. Ullman (2010). "Extracción de conjuntos de datos masivos, cap. 3".
  19. ^ Weber, Roger; Blott, Stephen. "Una estructura de datos basada en aproximación para búsqueda de similitud" (PDF) . S2CID  14613657. Archivado desde el original (PDF) el 4 de marzo de 2017. {{cite journal}}: Requiere citar revista |journal=( ayuda )
  20. ^ Ramaswamy, Sharadh; Rose, Kenneth (2007). "Límites adaptativos de distancia de conglomerados para búsqueda de similitud en bases de datos de imágenes". ICIP .
  21. ^ Ramaswamy, Sharadh; Rose, Kenneth (2010). "Límites adaptativos de distancia de clúster para indexación de alta dimensión". TKDE .
  22. ^ 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) . Revista de la ACM . 45 (6): 891–923. CiteSeerX 10.1.1.15.3125 . doi :10.1145/293347.293348. S2CID  8193729. Archivado desde el original (PDF) el 2016-03-03 . Consultado el 2009-05-29 . 
  23. ^ Clarkson, Kenneth L. (1983), "Algoritmos rápidos para el problema de todos los vecinos más próximos", 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, S2CID16665268 ​.
  24. ^ Vaidya, PM (1989). "Un algoritmo O(n log n) para el problema de todos los vecinos más próximos". Geometría discreta y computacional . 4 (1): 101–115. doi : 10.1007/BF02187718 .

Fuentes

Lectura adicional

Enlaces externos