Buscar vecinos más cercanos
La búsqueda de los vecinos más cercanos , o los k vecinos más cercanos , es un problema algorítmico clásico. Informalmente el problema consiste, dado un punto que se encuentra en un conjunto de otros puntos, que son los k más cercanos.
La búsqueda de vecindad se usa en muchos campos, como el reconocimiento de patrones , agrupamiento , aproximación de funciones , predicción de series de tiempo e incluso algoritmos de compresión (busque un grupo de datos lo más cerca posible del grupo de datos que se comprimirá para minimizar la entrada de información). En particular, este es el paso principal del método de los k vecinos más cercanos en el aprendizaje automático .
Definición
La formulación clásica del problema es la siguiente. Dado un conjunto A de n puntos , en un espacio métrico E, un número entero k menor que n , y un punto adicional x , encuentre los k puntos de A más cercanos a x .
Un caso clásico es el de la búsqueda del vecino más cercano, es decir, el caso k = 1. Una hipótesis clásica es que el espacio subyacente E es un espacio vectorial de dimensión acotada.
Métodos exactos
Búsqueda lineal
El algoritmo de búsqueda de vecindad ingenua consiste en repasar el conjunto de n puntos de A y ver si este punto está más cerca o no que uno de los vecinos más cercanos ya seleccionados, y si es así, insertarlo. Entonces obtenemos un tiempo de cálculo lineal en el tamaño de A: O ( n ) (siempre que k << n ). Este método se llama búsqueda secuencial o búsqueda lineal.
Algoritmo ingenuo:
pour i allant de 1 à k mettre le point D[i] dans proches_voisins fin pour pour i allant de k+1 à n si la distance entre D[i] et x est inférieure à la distance d'un des points de proches_voisins à x supprimer de proches_voisins le point le plus éloigné de x mettre dans proches_voisins le point D[i] fin si fin pour proches_voisins contient les k plus proches voisins de xLa investigación lineal adolece de un problema de lentitud. Si el conjunto A es grande, entonces es extremadamente caro probar los n puntos en el espacio.
Las optimizaciones de este algoritmo se basan a menudo en casos particulares del problema. En la mayoría de los casos, la optimización consiste en realizar previamente un algoritmo (preprocesamiento) que puede tener una complejidad superior a O ( n ) pero que luego permite realizar un gran número de búsquedas de forma muy rápida. Se trata entonces de encontrar un término medio entre el momento de los cálculos previos y el número de búsquedas que se realizarán a partir de entonces.
Particionamiento del espacio
Existen algoritmos de búsqueda eficientes cuando la dimensión D es pequeña (menos de ~ 15). La estructura más conocida es el árbol k -d , introducido en 1975.
Un problema importante de estos métodos es sufrir la maldición de la dimensión : cuando la dimensión D es demasiado grande, estos métodos tienen rendimientos comparables o inferiores a una búsqueda lineal.
La búsqueda de los vecinos más cercanos de un punto C en un árbol k -d se realiza de la siguiente manera:
- Intentamos colocar el punto C en el árbol, entonces aplicamos el algoritmo de inserción.
- Una vez llegado a una hoja, este punto se guarda como el "mejor candidato por ahora".
- Subimos al árbol:
- Si el nodo actual está más cerca, se convierte en el mejor candidato;
- Se determina si una parte de la celda ubicada al otro lado del hiperplano delimitado por el nodo puede contener un punto más cercano. Para hacer esto, determinamos la intersección del hiperplano con la bola de búsqueda:
- si la bola de búsqueda cruza el hiperplano, se realiza una búsqueda descendiendo la rama correspondiente;
- de lo contrario, quitamos la rama y seguimos trepando por el árbol.
- Nos detenemos en la raíz.
Métodos aproximados
Hash sensible a la localidad
Los puntos en el espacio E se reemplazan por una huella dactilar, normalmente un número, calculado por una función hash . En lugar de hacer una búsqueda por las coordenadas m (para un espacio E con m dimensiones), hacemos una búsqueda de los vecinos más cercanos por el valor de la huella. Se buscan varias huellas digitales, utilizando una familia de funciones hash, hasta que se encuentra un candidato estadísticamente satisfactorio.
Aplicaciones
Respecto a un espacio geométrico:
- probabilidad de colisión : en el caso de un sistema dinámico, podemos buscar los vecinos más cercanos de un objeto para comprobar si existe riesgo de colisión; por ejemplo, en el caso de un videojuego, para saber si el personaje puede ser bloqueado por un obstáculo;
- interacciones a distancia: en física, la intensidad de las interacciones disminuye con la distancia y la presencia de partículas puede tener un efecto de pantalla; por lo tanto, es útil determinar los vecinos más cercanos de una partícula, para limitar los cálculos de interacción;
- gestión administrativa de un territorio: para determinar de qué establecimiento (correos, escuela, etc.) depende una persona, buscamos el establecimiento más cercano al domicilio; a veces hablamos del "problema de la oficina de correos".
El espacio también puede ser un espacio abstracto: si un objeto está representado por un número m de parámetros encriptados, podemos representar este objeto por un punto en el espacio m- dimensional, entonces el algoritmo hace posible encontrar el objeto (s) que tiene el propiedades más cercanas. Por ejemplo, puede ser una cuestión de encontrar el mejor candidato para una sustitución de un objeto dado, el mejor candidato para una aplicación determinada (el vecino más cercano del objeto ideal), o bien encontrar el objeto que mejor se corresponda con una huella dactilar en relieve. ( identificación, investigación).
Ver también
Notas y referencias
- (en) Jon Louis Bentley , " Árboles de búsqueda binarios multidimensionales utilizados para la búsqueda asociativa " , Comunicaciones de la ACM , vol. 18, n o 9,1975, p. 509-517 ( DOI 10.1145 / 361002.361007 )
- (in) Piotr Indyk y Rajeev Motwani , " Vecinos más cercanos aproximados: hacia la eliminación de la maldición de la dimensionalidad". » , Actas del 30º Simposio de Teoría de la Computación ,1998( leer en línea )
-
para un punto C dado ( c 1 , c 2 ,…, c n ) y un radio R dado, y para una norma elegida L m , la bola de búsqueda es el conjunto de puntos X ( x 1 , x 2 ,…, x n ) verificar ; si m = 2 (norma euclidiana), la bola de búsqueda es la hiperesfera
- Problema de la oficina de correos , cf. (en) Donald E. Knuth , El arte de la programación informática , vol. 3: clasificación y búsqueda ,1998, 2 nd ed. [ detalle de la edición ]. Este término también se usa para describir el problema del círculo mínimo ; es entonces una cuestión de encontrar dónde colocar una oficina de correos para servir mejor a un conjunto de domicilios determinados.
