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