Depende de la métrica que use para juzgar la similitud entre los datos. LSH intenta mezclar elementos similares al mismo cubo y la forma de hacerlo depende de lo que usemos como medida de similitud / distancia.
Si usa Jaccard como su medida de distancia / similitud, entonces LSH se puede construir a través de hashes mínimos. Si usa la distancia euclidiana, LSH se basa en proyecciones aleatorias.
Considere que usa la distancia euclidiana. Sus datos consisten en vectores en n dimensiones y su objetivo es hacer hash vectores que estén cerca del mismo cubo.
- ¿Cómo explicarías un 'arreglo' a un principiante en programación?
- ¿Debería considerar C ++ sobre Python para las entrevistas de Silicon Valley?
- ¿Alguien está usando algoritmos epigenéticos?
- Cómo hacer un motor de búsqueda usando un algoritmo
- ¿Cuál es un buen algoritmo para el problema de la mochila 0-1 cuando los pesos están positivamente relacionados con los valores?
Por lo tanto, puede crear un vector aleatorio de n dimensiones y calcular el producto de punto entre ese vector aleatorio y sus datos. Los resultados son números reales, por lo que proyecta desde n dimensiones hasta una línea aleatoria. Entonces, si tienes b cubos, divides los números reales en intervalos b. Entonces la función hash es
H (x) = punto (r, x) / w
Donde r es un vector de proyección aleatorio yw es un parámetro.
Piensa ahora en 2d imagina que tus puntos están muy separados en la dimensión y pero área igual en x si tu proyección aleatoria es paralela a x, entonces la función dividirá los puntos en el mismo cubo. Para evitar falsos negativos y falsos positivos, debe utilizar no una sino varias funciones hash y tablas hash y luego combinar sus resultados.
Luis.
