¿Cómo entender el hashing sensible a la localidad?

¿Cómo entender el hashing sensible a la localidad?

El mejor tutorial que he visto para LSH está en el libro:Minería de conjuntos de datos masivos. Consulte el Capítulo 3:Encontrar elementos similares http://infolab.stanford.edu/~ullman/mmds/ch3a.pdf

También recomiendo la siguiente diapositiva:http://www.cs.jhu.edu/%7Evandurme/papers/VanDurmeLallACL10-slides.pdf. El ejemplo de la diapositiva me ayuda mucho a comprender el hash para la similitud del coseno.

Tomo prestadas dos diapositivas de Benjamin Van Durme y Ashwin Lall, ACL2010 y trato de explicar un poco las intuiciones de LSH Families for Cosine Distance.

  • En la figura, hay dos círculos con rojo y amarillo de color, que representan dos puntos de datos bidimensionales. Estamos tratando de encontrar su similitud de coseno usando LSH.
  • Las líneas grises son algunos planos uniformemente elegidos al azar.
  • Dependiendo de si el punto de datos se ubica por encima o por debajo de una línea gris, marcamos esta relación como 0/1.
  • En la esquina superior izquierda, hay dos filas de cuadrados blancos y negros, que representan la firma de los dos puntos de datos, respectivamente. Cada cuadrado corresponde a un bit 0 (blanco) o 1 (negro).
  • Entonces, una vez que tenga un grupo de aviones, puede codificar los puntos de datos con su ubicación respectiva a los aviones. Imagine que cuando tenemos más aviones en el grupo, la diferencia angular codificada en la firma está más cerca de la diferencia real. Porque solo los planos que residen entre los dos puntos darán a los dos datos un valor de bit diferente.

  • Ahora observamos la firma de los dos puntos de datos. Como en el ejemplo, usamos solo 6 bits (cuadrados) para representar cada dato. Este es el hash LSH para los datos originales que tenemos.
  • La distancia de hamming entre los dos valores hash es 1, porque sus firmas solo difieren en 1 bit.
  • Teniendo en cuenta la longitud de la firma, podemos calcular su similitud angular como se muestra en el gráfico.

Tengo un código de muestra (solo 50 líneas) en python aquí que usa similitud de coseno. https://gist.github.com/94a3d425009be0f94751


Los tweets en espacio vectorial pueden ser un gran ejemplo de datos de alta dimensión.

Consulte mi publicación de blog sobre la aplicación de hashing sensible a la localidad a los tweets para encontrar otros similares.

http://micvog.com/2013/09/08/storm-first-story-detection/

Y como una imagen vale más que mil palabras, revisa la siguiente imagen:

http://micvog.files.wordpress.com/2013/08/lsh1.png

Espero que ayude.@mvogiatzis


Aquí hay una presentación de Stanford que lo explica. Hizo una gran diferencia para mí. La segunda parte es más sobre LSH, pero la primera parte también lo cubre.

Una imagen de la descripción general (hay mucho más en las diapositivas):

Búsqueda de vecinos cercanos en datos de alta dimensión - Parte 1:http://www.stanford.edu/class/cs345a/slides/04-highdim.pdf

Búsqueda de vecinos cercanos en datos de alta dimensión - Parte 2:http://www.stanford.edu/class/cs345a/slides/05-LSH.pdf