Ejemplo

En esta sección presentaremos el método que se sigue para encontrar los $K$ vecinos más cercanos, paso a paso, esto se ilustrará con una serie de imágenes presentadas en esta sección.

Los 14 puntos mostrados en la figura corresponden a una base de datos, donde los primeros 4 puntos (círculos no rellenos del 1 al 4), corresponden a los puntos seleccionados como pivotes (cabe mencionar que estos puntos son escogidos al azar), los 10 puntos restantes de la imagen (círculos rellenos del número 5 al 14) corresponden a los puntos de la base de datos que no son pivotes, también se puede apreciar en el lado derecho de esta imagen, que cada punto cuenta con una cola de prioridad (su descripción puede verse en el apéndice ), donde se almacenarán los $K$ (para este ejemplo $K$=3) vecinos más cercanos y la distancia máxima a la que se encuentra el elemento más lejano con respecto a ese punto, esta cola de prioridad esta ordenada de acuerdo a la distancia, por lo tanto el punto más a la izquierda en la cola de prioridad (heap) de cada uno, en la imagen corresponde al punto más alejado, caso contrario para el punto que se encuentra en el lado derecho.

En la figura se pueden observar que los puntos que no son pivotes inicialmente contienen en su cola de prioridad los $K$ pivotes más cercanos al punto en cuestión, la explicación a este criterio fue explicada anteriormente, nótese que para este cálculo no es necesario hacer ningún cálculo de distancia extra. En la figura se puede observar los puntos 1, 2, 3 y 4 (pivotes), tiene a sus $K$ vecinos más cercanos en su cola de prioridad, debido a que por ser pivotes, estos puntos saben exactamente a que distancia están todos los elementos de cada uno de ellos, y el radio en la cola de prioridad (por ejemplo $r_1$ es la distancia al punto 7) corresponde al radio del punto más alejado; finalmente el circulo (línea punteada) que se muestra en esta figura en torno a cada elemento, tiene como radio, el valor máximo del radio en la cola de prioridad.

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Puntos iniciales

Como se puede apreciar en la figura el circulo formado cuyo centro es el punto 5, tiene como radio máximo la distancia al punto 1, obsérvese que los elementos que se encuentran en la cola de prioridad corresponden (por estar inicializado así la cola de prioridad) solo a los pivotes, no a los $K$ vecinos más cercanos. Resulta obvio que si los elementos iniciales en la cola de prioridad son aquellos $K$ pivotes más cercanos, los $K$ vecinos más cercanos es seguro que se encuentren dentro del radio inicial máximo, esto es sin realizar ningún cálculo de distancia extra.

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Estado inicial del punto 5

En la siguiente figura se muestra el resultado de aplicar una consulta de rango al mismo punto que en la imagen (punto número 5), el cual ya tiene en su cola de prioridad sus $K$ vecinos más cercanos, como se puede observar el radio máximo fue modificado () y ahora ese punto contiene ya a todos sus $K$ vecinos más cercanos, algo que es importante enfatizar, es que no solo fue modificado el radio del punto 5, sino también el radio de los puntos 6, 7, y 13 debido a que todos los cálculos de distancia realizados son aprovechados al máximo, es decir, si un cálculo de distancia realizado mejora el radio máximo de algún otro punto, la cola de prioridad de ese otro punto es actualizado, como es el caso de los puntos 6, 7 y 13.

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Punto número 5

La siguiente figura muestra el radio máximo inicial (circulo mas grande) y el radio máximo final (circulo más pequeño) del punto 6, así como también sus $K$ vecinos más cercanos, como puede observarse solo se realizó un cálculo de distancia para conocer a todos sus $K$ vecinos más cercanos y la única cola de prioridad actualizada fue la de este punto.

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Punto número 6. Radio inicial (círculo exterior), radio final (círculo interior.

En la figura , se puede observar que el elemento tratado es el número 7, y se realizaron 2 cálculos de distancia extras para conocer los $K$ vecinos más cercanos de este punto, nótese que la cola de prioridad del otro elemento (12) también fue modificada por haber realizado un cálculo de distancia que lo involucraba.

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Punto número 7

Para algunos puntos es necesario hacer más cálculos de distancia que para otros, esto es debido a la posición en la que se encuentren con respecto a los pivotes, para el caso del punto número 8, se realizaron tres cálculos de distancia extras, y estos cálculos son usados para modificar las colas de prioridades de los elementos 10 y 11, así finalmente este elemento tiene sus $K$ vecinos más cercanos. Como puede verse en la figura .

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Punto número 8

Para el punto número 9 de esta base de datos, se calcularon tres distancias extras para conocer sus $K$ vecinos más cercanos y como en los puntos anteriores, estos cálculos sirvieron para modificar la cola de prioridad de otros puntos, en este caso son los puntos 13 y 14, para ilustrar esto obsérvese la figura

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Punto número 9

En el punto 10 mostrado en la figura solo fue necesario realizar un cálculo de distancia extra y al igual que en los otros casos, se modifica la cola de prioridad del elemento 11.

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Punto número 10

Como puede observarse en las figuras , , no se realizo ningún cálculo de distancia extra para conocer los $K$ vecinos más cercanos de cada punto, debido a que la cola de prioridad de cada uno de estos elementos ya contenía sus $K$ vecinos más cercanos.

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Punto número 11

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Punto número 12

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Punto número 13

Finalmente para el punto 14, solo se tuvo que realizar un cálculo de distancia extra, esto puede obsérvese en la figura

Figura: Ejemplo de la búsqueda de los $K$ vecinos más cercanos. Punto número 14