El problema de encontrar k-Nearest Neighbours (también llamado k-NN en resumen) es el siguiente: dado un conjunto [matemático] S [/ matemático] de puntos en un espacio [matemático] M [/ matemático] y un punto de consulta [ matemática] q [/ matemática] ∈ [matemática] M [/ matemática], encuentre los puntos [matemática] K [/ matemática] más cercanos en [matemática] S [/ matemática] a [matemática] q [/ matemática] . Resulta que resolver este problema requiere mucho cálculo y, por lo tanto, es demasiado lento. En la práctica, a menudo estamos de acuerdo con el intercambio de cierta precisión por una gran ganancia de velocidad. Y así, en lugar de resolver el problema exactamente, tratamos de encontrar un conjunto de puntos [matemáticos] K [/ matemáticos] en S que sean aproximadamente [1] los puntos k más cercanos a [matemáticos] q [/ matemáticos].
El hashing sensible a la localidad (LSH en resumen) es una clase de algoritmos para resolver este problema. La idea principal es la siguiente:
- Tome [matemáticas] C [/ matemáticas] planos aleatorios [2] en el espacio. Estos planos dividen la región [matemáticas] M [/ matemáticas] en un grupo de subregiones.
- Hash cada punto en [matemática] S [/ matemática] a una secuencia binaria de [matemática] 0 [/ matemática] sy [matemática] 1 [/ matemática] de longitud [matemática] C [/ matemática] tal que la [matemática ] El bit i ^ {th} [/ math] en esta secuencia es [math] 0 [/ math] si el punto está en un lado del plano [math] i ^ {th} [/ math] (por ejemplo, el lado con proyección negativa) y [matemática] 1 [/ matemática] si está del otro lado.
- Intuitivamente, los puntos que están cerca uno del otro estarían en el mismo lado de muchos de estos planos. Como resultado, sus representaciones binarias serían idénticas en muchos bits.
- Realice un preprocesamiento tal que encontrar los puntos con un cierto patrón de bits (por ejemplo, el bit 3 sea 0, el bit 4 sea 1 y el bit 7 también sea 1) se vuelva eficiente.
- Cuando entra un punto de consulta [math] q [/ math], divídelo usando el mismo conjunto de planos.
- Luego, itere sobre un conjunto de bits que deben ser idénticos entre los valores hash del punto de consulta y los puntos en [math] S [/ math] y recopile todos esos puntos en un gran conjunto de candidatos [math] R [/ math].
- Evalúe la distancia exacta entre [matemática] q [/ matemática] y cada punto en [matemática] R [/ matemática] y devuelva los puntos superiores [matemática] K [/ matemática].
Dependiendo de cómo se elija el patrón de bits en el paso 6, esto puede considerarse como la construcción de un árbol de todos los puntos en [matemática] S [/ matemática] tal que:
- ¿Cuál es el número de elementos comunes en dos conjuntos de permutación?
- ¿Cómo se implementan las matrices de JavaScript internamente?
- Cómo entender el algoritmo maestro del documento sobre la resolución del isomorfismo gráfico en tiempo cuasi polinomial
- ¿Qué sitios web o aplicaciones usan el algoritmo de correspondencia para el cual los profesores Roth y Shapley ganaron el Premio Nobel en 2012?
- ¿Por qué a la mayoría de la gente le cuesta resolver problemas de algoritmos?
- Hay un plano en cada nodo interno del árbol.
- Los puntos van al subárbol izquierdo o al subárbol derecho dependiendo del lado del avión que los enfrenta
- Cuando llega un punto de consulta, el conjunto de candidatos consta de todos los puntos que van a la misma hoja (o una cercana) que el punto de consulta.
Si bien esto funciona bien, aún no encontrará todos los puntos más cercanos al punto de consulta. La razón es simple: dependiendo de cómo se eligieron los planos iniciales, algunos puntos podrían estar muy cerca del punto de consulta, pero desafortunadamente irían a hojas algo distantes (por ejemplo, porque no estaban en el mismo lado de algunos hiperplanos).
Para darle a nuestro algoritmo una mejor oportunidad de descubrir más puntos cercanos, podríamos cultivar un bosque de árboles independientes con sus propios planos aleatorios y devolver los puntos superiores [matemáticos] K [/ matemáticos] obtenidos de todos los árboles. Este algoritmo se llama algoritmo LSH-forest.
También puede leer una descripción más detallada pero probablemente más fácil de seguir del algoritmo en la excelente publicación de blog de Erik Bernhardsson: Vecinos más cercanos y modelos vectoriales – parte 2 – algoritmos y estructuras de datos.
[1] Hay maneras de hacer que esta idea de ‘aproximación’ sea más rigurosa, pero eso no es demasiado útil para esta respuesta.
[2] Hay muchas formas diferentes de elegir estos planos y diferentes formas pueden tener diferentes propiedades, por ejemplo, hacer que el árbol sea un árbol binario equilibrado.
