La búsqueda de 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 está más cerca (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 son los objetos, mayores son 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 para asignar a una residencia la oficina de correos más cercana. Una generalización directa de este problema es una búsqueda de 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 métrica de distancia , que es simétrica y satisface la desigualdad del triángulo . Aún más común, M se toma como el espacio vectorial d- dimensional donde la disimilitud se mide usando 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 del triángulo. [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 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 a todos los demás puntos de la base de datos, manteniendo un registro de lo "mejor hasta ahora". Este algoritmo, a veces referido como el 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 de espacio en espacios de dimensiones superiores. [3]
Desde la década de 1970 se ha aplicado al problema la metodología de ramificación y acotación . En el caso del espacio euclidiano, este enfoque abarca el índice espacial o métodos de acceso espacial. Se han desarrollado varios métodos de partición de espacio para resolver el problema de 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 las ramas vecinas que puedan contener coincidencias también deban evaluarse. Para un 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 caso 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 dinámica contexto, ya que tiene algoritmos eficientes para inserciones y eliminaciones como el árbol R * . [6] Los árboles R pueden producir vecinos más cercanos no solo para la distancia euclidiana, sino que también pueden usarse con otras distancias.