La búsqueda del vecino más cercano ( NNS ), como una forma de búsqueda de proximidad , es el problema de optimización de encontrar el punto en un conjunto dado que es más cercano (o más similar) a un punto dado. 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 el 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.
Más comúnmente , M es un espacio métrico y la disimilitud se expresa como una distancia métrica , que es simétrica y satisface la desigualdad triangular . Aún más común, M se toma como 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]
Se han propuesto varias soluciones al problema NNS. La calidad y la 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 a la que generalmente se hace referencia 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 polinomial y tiempo de búsqueda polilogarítmica.
La solución más simple al problema de NNS es calcular la distancia desde el punto de consulta hasta todos los demás puntos de la base de datos, realizando un seguimiento de los "mejores 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 M . No hay estructuras de datos de búsqueda que mantener, por lo que la búsqueda lineal no tiene complejidad de espacio más allá del almacenamiento de la base de datos. La búsqueda ingenua puede, en promedio, superar los enfoques de partición espacial en espacios de dimensiones superiores. [3]
Desde la década de 1970, la metodología de sucursal y límite se ha aplicado al problema. En el caso del espacio euclidiano, este enfoque abarca el índice espacial o los 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 es 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 a través del 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, es posible que también deban evaluarse las ramas vecinas que pueden contener hits. Para tiempo de consulta de dimensión constante, la complejidad promedio es O(log N ) [4] en el caso de puntos distribuidos aleatoriamente, la complejidad del peor de los casos es O ( kN ^(1-1/ k )) [5] Alternativamente, la estructura de datos del árbol R se diseñó para admitir la búsqueda del vecino más cercano en forma dinámica . contexto, ya que cuenta con algoritmos eficientes para inserciones y eliminaciones como el árbol R* . [6] 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.