2 Similitud y minhashing

En la primera parte del curso tratamos un problema fundamental en varias tareas de análisis de datos:

  • ¿Cómo medir similitud entre objetos o casos?
  • ¿Cómo encontrar vecinos cercanos en un conjunto de datos?
  • ¿Cómo hacer uniones de tablas por similitud?

Algunos ejemplos son:

  • Encontrar documentos similares en una colección de documentos. Esto puede servir para detectar plagio, deduplicar noticias o páginas web, hacer matching de datos de dos fuentes (por ejemplo, nombres completos de personas), etc. Ver por ejemplo Google News.
  • Encontrar usuarios similares (Netflix), en el sentido de que tienen gustos similares, o películas similares, en el sentido de qe le gustan a las mismas personas.
  • Encontrar imágenes similares en una colección grande, ver por ejemplo Pinterest.
  • Uber: rutas similares que indican (fraude o abusos)[https://eng.uber.com/lsh/].
  • Deduplicar registros de usuarios de algún servicio (por ejemplo, beneficiarios de programas sociales).

Estos problemas no son triviales por dos razones:

  • Los elementos que queremos comparar muchas veces están naturalmente representados en espacios de dimensión alta, y es relativamente costoso comparar un par (documentos, imágenes, usuarios, rutas). Muchas veces es preferible construir una representación más compacta y hacer comparaciones con las versiones comprimidas.
  • Si la colección de elementos es grande (\(N\)), entonces el número de pares posibles es del orden de \(N^2\), y no es posible hacer todas las posibles comparaciones para encontrar los elementos similares (por ejemplo, comparar \(100\) mil documentos, con unas \(10\) mil comparaciones por segundo, tardaría alrededor de \(5\) días).

Si tenemos que calcular todas las similitudes, no hay mucho qué hacer. Pero muchas veces nos interesa encontrar pares de similitud alta, o completar tareas más específicas como contar duplicados, etc. En estos casos, veremos que es posible construir soluciones probabilísticas aproximadas para resolver estos problemas de forma escalable.

Aunque veremos más adelante métricas de similitud comunes como la dada por la distancia euclideana o distancia coseno, por ejemplo, en esta primera parte nos concentramos en discutir similitud entre pares de textos. Los textos los podemos ver como colecciones de palabras, o de manera más general, como colecciones de cadenas.

2.1 Similitud de conjuntos

Muchos de estos problemas de similitud se pueden pensar como problemas de similitud entre conjuntos. Por ejemplo, los documentos son conjuntos de palabras, conjuntos de pares de palabras, sucesiones de caracteres, una película se puede ver como el conjunto de personas a las que le gustó, o una ruta como un conjunto de tramos, etc.

Hay muchas medidas que son útiles para cuantificar la similitud entre conjuntos. Una que es popular, y que explotaremos por sus propiedades, es la similitud de Jaccard:

La similitud de Jaccard de los conjuntos \(A\) y \(B\) está dada por

\[sim(A,B) = \frac{|A\cap B|}{|A\cup B|}\]

Esta medida cuantifica qué tan cerca está la unión de \(A\) y \(B\) de su intersección. Cuanto más parecidos sean \(A\cup B\) y \(A\cap B\), más similares son los conjuntos. En términos geométricos, es el área de la intersección entre el área de la unión.

2.2 Representación de documentos como conjuntos

Hay varias maneras de representar documentos como conjuntos. Las más simples son:

  1. Los documentos son colecciones de palabras, o conjuntos de sucesiones de palabras de tamaño \(n\).
  2. Los documentos son colecciones de caracteres, o conjuntos de sucesiones de caracteres (cadenas) de tamaño \(k\).

La primera representación se llama representación de n-gramas, y la segunda representación de k-tejas, o \(k\)-shingles. Nótese que en ambos casos, representaciones de dos documentos con secciones parecidas acomodadas en distintos lugares tienden a ser similares.

Consideremos una colección de textos cortos:

Abajo mostramos la representacion en bolsa de palabras (1-gramas) y la representación en bigramas (2-gramas) de los primeros dos documentos:

## [[1]]
## [1] "el"       "perro"    "persigue" "al"       "gato"     "pero"     "no"      
## [8] "lo"       "alcanza" 
## 
## [[2]]
## [1] "el"       "gato"     "persigue" "al"       "perro"    "pero"     "no"      
## [8] "lo"       "alcanza"
## [[1]]
## [1] "el perro"       "perro persigue" "persigue al"    "al gato"       
## [5] "gato pero"      "pero no"        "no lo"          "lo alcanza"    
## 
## [[2]]
## [1] "el gato"       "gato persigue" "persigue al"   "al perro"     
## [5] "perro pero"    "pero no"       "no lo"         "lo alcanza"

La representación en k-tejas es otra posibilidad:

## [[1]]
##  [1] "el" "l " " p" "pe" "er" "rr" "ro" "o " "rs" "si" "ig" "gu" "ue" "e " " a"
## [16] "al" " g" "ga" "at" "to" "o," ", " " n" "no" " l" "lo" "lc" "ca" "an" "nz"
## [31] "za"
## 
## [[2]]
##  [1] "el" "l " " g" "ga" "at" "to" "o " " p" "pe" "er" "rs" "si" "ig" "gu" "ue"
## [16] "e " " a" "al" "rr" "ro" "o," ", " " n" "no" " l" "lo" "lc" "ca" "an" "nz"
## [31] "za"
## [[1]]
##  [1] "el p" "l pe" " per" "perr" "erro" "rro " "ro p" "o pe" "pers" "ersi"
## [11] "rsig" "sigu" "igue" "gue " "ue a" "e al" " al " "al g" "l ga" " gat"
## [21] "gato" "ato," "to, " "o, p" ", pe" "pero" "ero " "ro n" "o no" " no "
## [31] "no l" "o lo" " lo " "lo a" "o al" " alc" "alca" "lcan" "canz" "anza"
## 
## [[2]]
##  [1] "el g" "l ga" " gat" "gato" "ato " "to p" "o pe" " per" "pers" "ersi"
## [11] "rsig" "sigu" "igue" "gue " "ue a" "e al" " al " "al p" "l pe" "perr"
## [21] "erro" "rro," "ro, " "o, p" ", pe" "pero" "ero " "ro n" "o no" " no "
## [31] "no l" "o lo" " lo " "lo a" "o al" " alc" "alca" "lcan" "canz" "anza"

Observaciones:

  1. Los tokens son las unidades básicas de análisis. Los tokens son palabras para los n-gramas (cuya definición no es del todo simple) y caracteres para las k-tejas. Podrían ser también oraciones, por ejemplo.
  2. Nótese que en ambos casos es posible hacer algo de preprocesamiento para obtener la representación. Transformaciones usuales son:
  • Eliminar puntuación y/o espacios.
  • Convertir los textos a minúsculas.
  • Esto incluye decisiones acerca de qué hacer con palabras compuestas (por ejemplo, con un guión), palabras que denotan un concepto (Reino Unido, por ejemplo) y otros detalles.
  1. Si lo que nos interesa principalmente similitud textual (no significado, o polaridad, etc.) entre documentos, entonces podemos usar \(k\)-tejas, con un mínimo de preprocesamiento. Esta representación es simple y flexible en el sentido de que se puede adaptar para documentos muy cortos (mensajes o tweets, por ejemplo), pero también para documentos más grandes.

Por estas razones, no concentramos por el momento en \(k\)-tejas

Tejas (shingles)

Sea \(k>0\) un entero. Las \(k\)-tejas (\(k\)-shingles) de un documento d es el conjunto de todas las corridas (distintas) de \(k\) caracteres sucesivos.

Escogemos \(k\) suficientemente grande, de forma que la probabilidad de que una teja particular ocurra en un texto dado sea relativamente baja.

Ejemplo

Documentos textualmente similares tienen tejas similares:

Podemos calcular todas las similitudes:

## # A tibble: 6 x 4
##    id_1  id_2 tejas_1    tejas_2   
##   <int> <int> <list>     <list>    
## 1     1     2 <chr [42]> <chr [42]>
## 2     1     3 <chr [42]> <chr [28]>
## 3     1     4 <chr [42]> <chr [50]>
## 4     2     3 <chr [42]> <chr [28]>
## 5     2     4 <chr [42]> <chr [50]>
## 6     3     4 <chr [28]> <chr [50]>
## # A tibble: 6 x 3
##    id_1  id_2    sim
##   <int> <int>  <dbl>
## 1     1     2 0.739 
## 2     1     3 0     
## 3     1     4 0.0595
## 4     2     3 0     
## 5     2     4 0.0595
## 6     3     4 0.167

pero nótese que, como señalamos arriba, esta operación será muy costosa incluso si la colección de textos es de tamaño moderado.

  • Si los textos son cortos, entonces basta tomar valores como \(k=4,5\), pues hay un total de \(27^4\) tejas de tamaño \(4\), y el número de tejas de un documento corto (mensajes, tweets) es mucho más bajo que \(27^4\) (nota: ¿puedes explicar por qué este argumento no es exactamente correcto?)

  • Para documentos grandes, como noticias o artículos, es mejor escoger un tamaño más grande, como \(k=9,10\), pues en documentos largos puede haber cientos de miles de caracteres. Si \(k\) fuera más chica entonces una gran parte de las tejas aparecerá en muchos de los documentos, y todos los documentos tendrían similitud alta.

  • Evitamos escoger \(k\) demasiado grande, pues entonces los únicos documentos similares tendrían que tener subcadenas largas exactamente iguales. Por ejemplo: “Batman y Robin” y “Robin y Batman” son algo similares si usamos tejas de tamaño 4, pero son muy distintas si usamos tejas de tamaño 8:

2.3 Representación matricial

Podemos usar una matriz binaria para guardar todas las representaciones en k-tejas de nuestra colección de documentos. Puede usarse una representación rala (sparse) si es necesario:

## # A tibble: 107 x 5
##    tejas  doc_1 doc_2 doc_3 doc_4
##    <chr>  <dbl> <dbl> <dbl> <dbl>
##  1 " al "     1     1     0     0
##  2 " alc"     1     1     0     0
##  3 " ani"     0     0     0     1
##  4 " de "     0     0     1     1
##  5 " doc"     0     0     1     1
##  6 " eje"     0     0     1     0
##  7 " el "     0     0     1     0
##  8 " es "     0     0     1     0
##  9 " gat"     1     1     0     1
## 10 " hab"     0     0     0     1
## # … with 97 more rows

¿Cómo calculamos la similitud de Jaccard usando estos datos?

Calcular la unión e intersección se puede hacer haciendo OR y AND de las columnas, y entonces podemos calcular la similitud

## [1] 0.739

El cálculo para todos los documentos podríamos hacerlo con:

##        doc_1  doc_2  doc_3
## doc_2 0.7391              
## doc_3 0.0000 0.0000       
## doc_4 0.0595 0.0595 0.1667

2.4 Minhash y reducción probabilística de dimensionalidad

Para una colección grande de documentos la representación binaria de la colección de documentos puede tener un número muy grande de renglones. Puede ser posible crear un número más chico de nuevos features (ojo: aquí los renglones son las “variables”, y los casos son las columnas) con los que sea posible obtener una buena aproximación de la similitud.

Los mapeos que usaremos son escogidos al azar, y son sobre el espacio de enteros.

  • Sea \(\pi\) una permutación al azar de los renglones de la matriz.
  • Permutamos los renglones de la matriz tejas-documentos según \(\pi\).
  • Definimos una nuevo descriptor, el minhash del documento: para cada documento (columna) \(d\) de la matriz permutada, tomamos el entero \(f_\pi (d)\) que da el número del primer renglón que es distinto de \(0\).

2.4.0.1 Ejercicio

Considera la matriz de tejas-documentos para cuatro documentos y cinco tejas dada a continuación, con las permutaciones \((2,3,4,5,1)\) (indica que el renglón \(1\) va al \(2\), el \(2\) a \(3\), el \(5\) al \(1\), etc.) y \((2,5,3,1,4)\). Calcula el descriptor definido arriba.

##     d_1 d_2 d_3 d_4
## abc   1   0   0   1
## ab    0   0   1   0
## xyz   0   1   0   1
## abx   1   0   1   1
## abd   0   0   1   0

Ejemplo

Ahora regresamos a nuestro ejemplo de \(4\) textos chicos. Por ejemplo, para una permutación tomada al azar:

## # A tibble: 107 x 5
##    tejas  doc_1 doc_2 doc_3 doc_4
##    <chr>  <dbl> <dbl> <dbl> <dbl>
##  1 igue       1     1     0     0
##  2 os a       0     0     0     1
##  3 "rro "     1     0     0     0
##  4 pero       1     1     0     0
##  5 l ga       1     1     0     0
##  6 sigu       1     1     0     0
##  7 , pe       1     1     0     0
##  8 to h       0     0     0     1
##  9 erro       1     1     0     1
## 10 " lo "     1     1     0     0
## # … with 97 more rows

Los minhashes para cada documentos con estas permutaciones son:

## # A tibble: 1 x 4
##   doc_1 doc_2 doc_3 doc_4
##   <int> <int> <int> <int>
## 1     1     1    23     2

Ahora repetimos con otras permutaciones:

## # A tibble: 20 x 5
##    firma doc_1 doc_2 doc_3 doc_4
##    <chr> <int> <int> <int> <int>
##  1 h_1       2     4     7     1
##  2 h_2       2     2     1     4
##  3 h_3       5     1     2     2
##  4 h_4       3     3     1     2
##  5 h_5       3     3     2     1
##  6 h_6       2     2     1     1
##  7 h_7       3     3     1     5
##  8 h_8       4     1     6     2
##  9 h_9       5     3     4     1
## 10 h_10      2     2     8     1
## 11 h_11      1     1     4     2
## 12 h_12      2     1    10     4
## 13 h_13      2     5     7     1
## 14 h_14      4     4     1     1
## 15 h_15      1     1     3     2
## 16 h_16      6     3     4     1
## 17 h_17      3     3     2     1
## 18 h_18      4     4     2     1
## 19 h_19      1     1     3     2
## 20 h_20      2     1     3     5

A esta nueva matriz le llamamos matriz de firmas de los documentos. La firma de un documento es una sucesión de enteros.

Cada documento se describe ahora con 20 entradas, en lugar de 107.

Nótese que por construcción, cuando dos documentos son muy similares, es natural que sus columnas de firmas sean similares, pues la mayor parte de los renglones de estos dos documentos son \((0,0)\) y \((1,1)\). Resulta ser que podemos cuantificar esta probabilidad. Tenemos el siguiente resultado simple pero sorprendente:

Sea \(\pi\) una permutación escogida al azar, y \(a\) y \(b\) dos columnas dadas. Entonces \[P(f_\pi(a) = f_\pi(b)) = sim(a, b)\] donde \(sim\) es la similitud de Jaccard basada en las tejas usadas. Sean \(\pi_1, \pi_2, \ldots \pi_n\) permutaciones escogidas al azar de manera independiente. Si \(n\) es grande, entonces por la ley de los grandes números \[sim(a,b) \approx \frac{|\pi_j : f_{\pi_j}(a) = f_{\pi_j}(b)|}{n},\] es decir, la similitud de Jaccard es aproximadamente la proporción de elementos de las firmas que coinciden.

Ejemplo

Antes de hacer la demostración, veamos como aplicaríamos a la matriz de firmas que calculamos arriba. Tendríamos, por ejemplo :

que comparamos con las similitudes de Jaccard

Ahora veamos qué sucede repetimos varias veces:

Que indica que nuestro procedimiento da estimaciones razonables de las similitudes de Jaccard.

Observación: si la similitud de dos documentos es cero, entonces este procedimiento siempre da la respuesta exacta. ¿Por qué?

Ahora damos un argumento para demostrar este resultado. Consideremos dos columnas \(a,b\) de la matriz de 0’s y 1’s, con conjuntos de tejas asociados \(A,B\).

  • Permutamos los reglones de las dos columnas \(a\) y \(b\).
  • Sea \(k\) la posición donde aparece el primer \((0,1)\), \((1,0)\) o \((1,1)\).
  • Hay tantos renglones \((1,1)\) como elementos en \(A\cap B\). Y hay tantos renglones \((0,1)\), \((1,0)\) o \((1,1)\) como elementos en \(A\cup B\).
  • Todos estos \(|A\cup B|\) reglones tienen la misma probabilidad de aparecer en la posición \(k\).
  • Entonces, la probabilidad condicional de que el renglón \(k\) sea de tipo \((1,1)\), dado que es de algún tipo de \((1,0), (0,1), (1,1)\), es \[\frac{|A\cap B|}{|A\cup B|},\] que es la similitud de Jaccard de los dos documentos.

2.5 Cálculo de firmas por documento

Podemos evitar permutar matrices (una operación costosa) de varias formas. Una manera de hacer esto es trabajar documento por documento, lo cual es natural para colecciones grandes de textos.

En este caso, es fácil ver que para una permutación dada, la firma de un documento puede encontrarse de la siguiente forma:

Cálculo de la firma de un documento

  1. Para la columna \(d\) (documento), tomamos todos los valores de los índices igual a 1.
  2. Aplicamos la permutación \(\pi\) a cada uno de estos índices.
  3. Calculamos el mínimo de los valores resultantes para obtener \(f_\pi (d)\).
  4. Repetimos para cada permutación para obtener la firma del documento.

Ejemplo

Consideremos el documento 1 de nuestro ejemplo. Extraemos

##   [1] 1 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0
##  [38] 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 0 0 0 1 1 0 1 1 0 0 0 0 1 0 1 0 0 1 1 1
##  [75] 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0 0
##  [1]   1   2   9  11  12  14  17  21  23  26  28  31  36  43  46  47  48  51  52
## [20]  54  58  59  61  62  67  69  72  73  74  75  80  81  82  83  84  88  91  96
## [39] 102 105

Ahora convertimos las permutaciones a funciones:

Para calcular el primer elemento de la firma, transformamos los índices de arriba y calculamos el mínimo:

## [1] 2

Para el tercer elemento de la firma

## [1] 5

Y la firma completa es

##  [1] 2 2 5 3 3 2 3 4 5 2 1 2 2 4 1 6 3 4 1 2

Escribimos ahora una implementación para calcular tejas y calcular firmas:

Nótese que en el código de arriba utiiizamos funciones en lugar de vectores para representar permutaciones. Este correspondencia es como sigue:

## # A tibble: 20 x 5
##     hash doc_1 doc_2 doc_3 doc_4
##    <int> <dbl> <dbl> <dbl> <dbl>
##  1     1     2     4     7     1
##  2     2     2     2     1     4
##  3     3     5     1     2     2
##  4     4     3     3     1     2
##  5     5     3     3     2     1
##  6     6     2     2     1     1
##  7     7     3     3     1     5
##  8     8     4     1     6     2
##  9     9     5     3     4     1
## 10    10     2     2     8     1
## 11    11     1     1     4     2
## 12    12     2     1    10     4
## 13    13     2     5     7     1
## 14    14     4     4     1     1
## 15    15     1     1     3     2
## 16    16     6     3     4     1
## 17    17     3     3     2     1
## 18    18     4     4     2     1
## 19    19     1     1     3     2
## 20    20     2     1     3     5

Observación: nótese que no estamos permutando ningún vector o matriz en este cálculo. Esto nos da la siguiente idea importante:

2.6 Funciones hash

Con la técnica de firmas derivadas de permutaciones logramos reducir la dimensionalidad de nuestro problema, y este es un primer paso para encontrar pares similares en una colección grande de documentos. Sin embargo, es necesario simular y almacenar las distintas permutaciones (quizá usamos cientos, para estimar con más precisión las similitudes) que vamos a utilizar. Estas permutaciones son relativamente grandes y quizá podemos encontrar una manera más rápida de “simular” las permutaciones.

Ejercicio: ¿cómo sustituir permutaciones?

En nuestro ejemplo anterior, tenemos \(107\) tejas. Consideramos una funciones de la forma (como se sugiere en (Leskovec, Rajaraman, and Ullman 2014)):

\[h(x) = (ax + b) \bmod 107\] donde escogemos \(a\) al azar entre 1 y 106, y \(b\) se escoge al azar entre \(0\) y \(106\). Recuerda que \(A \bmod p\) es el residuo que se obtiene al dividir \(A\) entre \(p\).¿Por qué es apropiada una función de este tipo?

  • Demuestra primero que la función \(h(x)\) es una permutación de los enteros \(\{ 0,1,\ldots, 106 \}\). Usa el hecho de que \(107\) es un número primo.
  • Si escogemos \(a, b\) al azar, podemos generar distintas permutaciones.
  • Esta familia de funciones no dan todas las posibles permutaciones, pero pueden ser suficientes para nuestros propósitos, como veremos más adelante.

Observación: si \(p\) no es primo, nuestra familia tiene el defecto de que algunas funciones pueden nos ser permutaciones. Por ejemplo, si \[h(x) = 4x + 1 \bmod 12,\] entonces \(h\) mapea el rango \(\{0,1,\ldots, 11\}\) a

##  [1] 1 5 9 1 5 9 1 5 9 1 5 9

Vamos a resolver nuestro problema simple usando funciones hash modulares:

Para calcular las firmas de los documentos, en lugar de permutaciones podemos utilizar funciones hash modulares (suponemos que las tejas están numeradas) de la siguiente forma: \[h(x) = (ax + b) \bmod p,\] donde \(p\) es un primo más grande que el número de tejas, y \(a\) y \(b\) se seleccionan al azar con \(0 < a, b \leq p-1\).

Esta función genera funciones hash modulares seleccionadas al azar:

Ejemplo

Podemos examinar algunas de estas funciones:

##   [1]  96  32  75  11  54  97  33  76  12  55  98  34  77  13  56  99  35  78
##  [19]  14  57 100  36  79  15  58 101  37  80  16  59 102  38  81  17  60 103
##  [37]  39  82  18  61 104  40  83  19  62 105  41  84  20  63 106  42  85  21
##  [55]  64 107  43  86  22  65   1  44  87  23  66   2  45  88  24  67   3  46
##  [73]  89  25  68   4  47  90  26  69   5  48  91  27  70   6  49  92  28  71
##  [91]   7  50  93  29  72   8  51  94  30  73   9  52  95  31  74  10  53
## [1] FALSE
## [1] FALSE

No es neceario reescribir nada en nuestro código anterior . Pero en lugar de usar permutaciones, usaremos familias de funciones hash extraidas al azar como mostramos arriba Reescribimos entonces nuestra función calc_firmas para usar las funciones hash en lugar de permutaciones, lo cual evita simular y guardar las permutaciones.

## # A tibble: 20 x 5
##     hash doc_1 doc_2 doc_3 doc_4
##    <int> <dbl> <dbl> <dbl> <dbl>
##  1     1     3     3     1     2
##  2     2     1     1     7     2
##  3     3     2     2     7     1
##  4     4     3     3     1     2
##  5     5     6     3     1     2
##  6     6     3     3    10     1
##  7     7     8     8     2     1
##  8     8     2     1     3     2
##  9     9     4     4     2     1
## 10    10     3     3     2     1
## 11    11     2     2     1     4
## 12    12     8     8     2     1
## 13    13     2     2    10     1
## 14    14     1     1     2     4
## 15    15     1     3     2     4
## 16    16     5     5     3     1
## 17    17     3     3     1     1
## 18    18     2     5     1     7
## 19    19     3     2     4     1
## 20    20     1     1     7     4

Y checamos

Cuando el número de tejas no exactamente un primo, hacemos lo siguiente:

Hash de tejas numeradas

Supongamos que tenemos \(\{0,1,\ldots, m-1\}\) tejas numeradas. Seleccionamos un primo \(p\geq m\), y definimos las funciones \[H =\{ h_{a,b}(x) = (ax + b) \bmod p \}\] En lugar de escoger una permutación al azar, escogemos \(a \in \{1,\cdots, p-1\}\), y \(b \in \{0,\cdots, p-1\}\) al azar. Usamos en el algoritmo estas funciones \(h_i\) como si fueran permutaciones.

Observación: El único detalle que hay que observar aquí es que los valores hash o cubetas a donde se mapean las tejas ya no están en el rango \(\{0,1,\ldots, m-1\}\) , de manera que no podemos interpretar como permutaciones. Pero pensando un poco vemos no hay ninguna razón para interpretar los valores de \(h_i(r)\) como renglones de una matriz permutadas, y no necesariamente \(h_i\) tiene que ser una permutación de los renglones. \(h_i\) puede ser una función que mapea renglones (tejas) a un rango grande de enteros, de forma que la probabilidad de que distintos renglones sean mapeados a un mismo hash sea muy baja.

Obtener el minhash es simplemente encontrar el mínimo entero de los valores hash que corresponden a tejas que aparecen en cada columna.

Funciones hash: discusión

En consecuencia, como solución para nuestro problema de minhashing podemos seleccionar un primo \(p\) muy grande y utiliar la familia de congruencias \(ax+b\bmod p\), seleccionando \(a\) y \(b\) al azar (ver implementación de Spark, donde se utiliza un primo fijo MinHashLSH.HASH_PRIME).

Más en general, podemos usar familias de funciones hash que cumplan:

  • Cada teja se mapea a un entero.
  • La probabilidad de que dos tejas diferentes colisionen en un mismo entero es baja.

La segunda propiedad es lo que usualmente define funciones hash apropiadas.

Otro enfoque es hacer hash directamente de las tejas (caracteres). En este caso, buscamos una función hash de cadenas a enteros grandes que “revuelva” las cadenas a un rango grande de enteros. Es importante la calidad de la función hash, pues no queremos tener demasiadas colisiones aún cuando existan patrones en nuestras tejas.

Por ejemplo, podemos utilizar la función hash_string del paquete textreuse (Mullen 2016) (implementada en C++):

Para obtener otras funciones hash, podemos usar una técnica distinta. Escogemos al azar un entero, y hacemos bitwise xor con este entero al azar. En laa implementación de textreuse, por ejemplo, se hace:

## [1] 488241107
## [1] -1656159112
##    user  system elapsed 
##   0.063   0.012   0.074

Otra opción es utilizar como función básica otra función hash estándar, como murmur32 o xxhash32 (la segunda es más rápida que la primera), que también pueden recibir semillas para obtener distintas funciones:

## [1] 1089553513
## [1] 450837119
##    user  system elapsed 
##    0.02    0.00    0.02

Ejemplo

Usando estas funciones hash de cadenas, nuestro ejemplo ser vería como sigue

Y ahora calculamos las firmas minhash:

## # A tibble: 20 x 5
##     hash       doc_1       doc_2       doc_3       doc_4
##    <int>       <dbl>       <dbl>       <dbl>       <dbl>
##  1     1 -2145249379 -2145249379 -2145840920 -1997807419
##  2     2 -2133827718 -2133827718 -2006817721 -2006817721
##  3     3 -1884418976 -1884418976 -2143971110 -2146981560
##  4     4 -2024619081 -2024619081 -1764752233 -1888364178
##  5     5 -2070806998 -2070806998 -2141400852 -2053842170
##  6     6 -2060442488 -2060442488 -2022399001 -1785960917
##  7     7 -2138035973 -2138035973 -1752820242 -2044591959
##  8     8 -2018744507 -1794103946 -2092547303 -2102640087
##  9     9 -2092358592 -2119669214 -2087751190 -2087751190
## 10    10 -2028499635 -2028499635 -1954147223 -2067618928
## 11    11 -2098546388 -2129826956 -2079152079 -2064898166
## 12    12 -2100317383 -2100317383 -2001366699 -1971443001
## 13    13 -2070535003 -2080895401 -2132510299 -2132510299
## 14    14 -2142238047 -2142238047 -2040348657 -2110539920
## 15    15 -2141243890 -2141243890 -2107245278 -2046970013
## 16    16 -1963446604 -1963446604 -1832774023 -2139172251
## 17    17 -2096591879 -2114868561 -1840777972 -2105929370
## 18    18 -2140053327 -2084187751 -2096068692 -2096068692
## 19    19 -2044840847 -2044840847 -1943591912 -1945441787
## 20    20 -1995311481 -2134379053 -2133899855 -2071660569

Podemos estimar similitudes igual que en los ejemplos anteriores:

2.7 Ejemplo: tweets

Ahora buscaremos tweets similares en una colección de un dataset de kaggle.

## Parsed with column specification:
## cols(
##   ID = col_double(),
##   lang = col_character(),
##   Date = col_datetime(format = ""),
##   Source = col_character(),
##   len = col_double(),
##   Orig_Tweet = col_character(),
##   Tweet = col_character(),
##   Likes = col_double(),
##   RTs = col_double(),
##   Hashtags = col_character(),
##   UserMentionNames = col_character(),
##   UserMentionID = col_character(),
##   Name = col_character(),
##   Place = col_character(),
##   Followers = col_double(),
##   Friends = col_double()
## )
##  [1] "Only two goalkeepers have saved three penalties in penalty shoot out Ricardo vs"                         
##  [2] "scores the winning penalty to send into the quarter finals where they will face Russia"                  
##  [3] "Tonight we have big game"                                                                                
##  [4] "We get stronger Turn the music up now We got that power power"                                           
##  [5] "Only two goalkeepers have saved three penalties in penalty shoot out Ricardo vs"                         
##  [6] "We re looking strong going into the knockout stage We caught up with ahead of"                           
##  [7] "am happy for winning Especially since you know we colluded and all Russia eliminates Spain after penalty"
##  [8] "When you see me When we feel the same feeling Power power"                                               
##  [9] "Kasper Schmeichel takes the final award of the day"                                                      
## [10] "After Years Global Puma Ambassador LG Mobile Ambassador CocaCola WorldCup Kookmin Bank UNICEF"

Seleccionamos funciones hash al azar:

##    user  system elapsed 
##   4.373   0.049   4.422
##    user  system elapsed 
##     110       0     110

Y ahora podemos utilizar esta representación compacta de firmas para estimar similitud. Por ejemplo, ¿cuáles son tweets similares al primero?

## [1] 912

Nótese que estos podemos llamarlos más apropiadamente candidatos a elementos similares, pues todavía no conocemos la similitud exacta. Esto podemos hacerlo recuperando las tejas que ya calculamos, y calculando la similitud exacta:

Observación: para hacer esta búsqueda tenemos que recorrer todos los documentos. Aunque usamos las firmas, que son más compactas, veremos una forma más eficiente de hacer esta búsqueda.

2.8 Buscando los pares similares

Aunque hemos reducido el trabajo para hacer comparaciones de documentos, no hemos hecho mucho avance en encontrar todos los pares similares de la colección completa de documentos. Intentar calcular similitud para todos los pares (del orden \(n^2\)) es demasiado trabajo, incluso aproximando con minhashes:

##    user  system elapsed 
##    3.03    0.02    3.05
## # A tibble: 3,937 x 5
##    doc_id firma      doc_id_1 firma_1      sim
##     <int> <list>        <int> <list>     <dbl>
##  1      1 <dbl [50]>        5 <dbl [50]>     1
##  2      1 <dbl [50]>      885 <dbl [50]>     1
##  3      2 <dbl [50]>       75 <dbl [50]>     1
##  4      2 <dbl [50]>      496 <dbl [50]>     1
##  5      3 <dbl [50]>      113 <dbl [50]>     1
##  6      5 <dbl [50]>      885 <dbl [50]>     1
##  7      6 <dbl [50]>      210 <dbl [50]>     1
##  8      6 <dbl [50]>      434 <dbl [50]>     1
##  9      6 <dbl [50]>      625 <dbl [50]>     1
## 10      6 <dbl [50]>      708 <dbl [50]>     1
## # … with 3,927 more rows

Nótese que si tuviéramos \(10\) veces más tweets (una fracción todavía del conjunto completo) el número de comparaciones se multiplica por \(100\) aproximadamente. En la siguiente parte veremos como aprovechar estos minhashes para hacer una búsqueda más eficiente de pares similares.

2.9 Locality sensitive hashing (LSH) para documentos

Calcular todas las posibles similitudes de una colección de un conjunto no tan grande de documentos es difícil. Sin embargo, muchas veces lo que nos interesa es simplemente agrupar colecciones de documentos que tienen alta similitud.

Una técnica resolver este problema es Locality Sensitive Hashing (LSH), que generalizamos en la sección siguiente. Comenzamos construyendo LSH basado en las firmas de minhash. La idea general es:

Idea general de Minshashing LSH

  • Recorremos la matriz de firmas documento por documento
  • Asignamos el documento a una cubeta dependiendo de sus valores minhash (su firma).
  • Todos los pares de documentos que caen en una misma cubeta son candidatos a pares similares. Generalmente tenemos mucho menos candidatos que el total de posibles pares.
  • Checamos la similitud exacta todos los pares candidatos dentro de cada cubeta que contenga más de un elemento, y filtramos si es necesario.

Veremos qie con este método hemos resuelto de manera aproximada nuestro problema de encontrar pares similares. En la siguiente parte discutiremos cómo decidir si es o no una buena aproximación. Veremos también formas de diseñar las cubetas para obtener candidatos con la similitud que busquemos (por ejemplo, mayor a \(0.5\), mayor a \(0.9\), etc.).

2.9.1 Ejemplo: cubetas de firmas completas

Calculamos los minhashes, y creamos una cubeta para cada firma minhash diferente. Los candidatos a similitud son pares que caen en una misma cubeta. Como usamos todos los hashes, los candidatos tienden a ser textos muy similares.

##  [1] "el perro persigue al gato, pero no lo alcanza"        
##  [2] "el gato persigue al perro, pero no lo alcanza"        
##  [3] "este es el documento de ejemplo"                      
##  [4] "el documento habla de perros, gatos, y otros animales"
##  [5] "el gato persigue al perro, pero no lo alcanza"        
##  [6] "este es el Documento de Ejemplo"                      
##  [7] "el gato persigue al perro, pero no lo alcanza!"       
##  [8] "texto diferente a todos"                              
##  [9] "un gato negro"                                        
## [10] "mi gato negro"
## # A tibble: 10 x 2
##    doc_id cubeta                                                                
##     <int> <chr>                                                                 
##  1      1 -1989387375/-2021416650/-2122567993/-2052651591/-1884113438/-21336478…
##  2      2 -1989387375/-2106759175/-2102938509/-2064792904/-1884113438/-21336478…
##  3      3 -2008375395/-2058702117/-2097264483/-2102209649/-1790764534/-19288478…
##  4      4 -2144961535/-2017337584/-2034543648/-2042771159/-1925690417/-20312810…
##  5      5 -1989387375/-2106759175/-2102938509/-2064792904/-1884113438/-21336478…
##  6      6 -2008375395/-2106596085/-2034543648/-2102209649/-1851922373/-19551314…
##  7      7 -1989387375/-2106759175/-2102938509/-2064792904/-1884113438/-21336478…
##  8      8 -2078753679/-1954870263/-2089149592/-2102209649/-1867523748/-13340201…
##  9      9 -2139765501/-1758376448/-1841300360/-1837902152/-1840072156/-15937177…
## 10     10 -2139765501/-1758376448/-1841300360/-1174395171/-1942704868/-15937177…

Podemos hacer hash de la cadena de la cubeta:

## # A tibble: 10 x 2
##    doc_id cubeta_2                        
##     <int> <chr>                           
##  1      1 88d6f4edadeea1f0ae7489160a7e65b4
##  2      2 cd58eb94b1de193f91fe29a08e58aa9c
##  3      3 38d54a429b62dd086291af6a58b280b4
##  4      4 c2b4d261f0cb5811638b26c65c7ff135
##  5      5 cd58eb94b1de193f91fe29a08e58aa9c
##  6      6 ae697838127c18d5528f0a6fb53d63ae
##  7      7 cd58eb94b1de193f91fe29a08e58aa9c
##  8      8 3d494e6a8dff18207ddc55dd39362732
##  9      9 da28c918f01dbf6e903d0eb9b272c048
## 10     10 21777396501ba392afa2699a770a0cc3

Ahora agrupamos por cubetas:

y filtramos las cubetas con más de un elemento:

## # A tibble: 1 x 3
##   cubeta_2                         docs      n_docs
##   <chr>                            <list>     <int>
## 1 cd58eb94b1de193f91fe29a08e58aa9c <int [3]>      3

Y los candidatos de alta similud se extraen de estas cubetas que tienen más de \(1\) elemento. Son:

## [[1]]
## [1] 2 5 7

Ahora podemos extraer los pares candidatos de similitud alta. Nótese que creamos todos los pares dentro de cada cubeta:

2.9.2 Ejemplo: algún grupo de minhashes coincide

Si quisiéramos capturar como candidatos pares de documentos con similitud más baja, podríamos pedir que coincidan solo algunos de los hashes. Por ejemplo, para agrupar textos con algún grupo de \(2\) minshashes iguales, podríamos hacer:

## $`1`
## [1] 1 2
## 
## $`2`
## [1] 3 4
## 
## $`3`
## [1] 5 6
##                            1                            2 
## "12|-1989387375/-2021416650" "34|-2122567993/-2052651591" 
##                            3 
## "56|-1884113438/-2133647824"
## # A tibble: 30 x 2
##    doc_id cubeta                    
##     <int> <chr>                     
##  1      1 12|-1989387375/-2021416650
##  2      1 34|-2122567993/-2052651591
##  3      1 56|-1884113438/-2133647824
##  4      2 12|-1989387375/-2106759175
##  5      2 34|-2102938509/-2064792904
##  6      2 56|-1884113438/-2133647824
##  7      3 12|-2008375395/-2058702117
##  8      3 34|-2097264483/-2102209649
##  9      3 56|-1790764534/-1928847885
## 10      4 12|-2144961535/-2017337584
## # … with 20 more rows

Ahora agrupamos por cubetas:

y filtramos las cubetas con más de un elemento:

## # A tibble: 4 x 3
##   cubeta                     docs      n_docs
##   <chr>                      <list>     <int>
## 1 12|-1989387375/-2106759175 <int [3]>      3
## 2 12|-2139765501/-1758376448 <int [2]>      2
## 3 34|-2102938509/-2064792904 <int [3]>      3
## 4 56|-1884113438/-2133647824 <int [4]>      4

Ahora podemos calcular similitud exacta y agrupar:

Por ejemplo, podemos hacer clustering con las similitudes de Jaccard:

## IGRAPH clustering label propagation, groups: 2, mod: 0.24
## + groups:
##   $`1`
##   [1] "2" "5" "1" "7"
##   
##   $`2`
##   [1] "9"  "10"
##

Usando de la idea de las cubetas podemos entonces resolver eficientemente los siguientes:

Vecinos cercanos

  • Para encontrar grupos de documentos similares podemos usar las cubetas. Nótese que un documento puede estar en varias cubetas.
  • Para encontrar vecinos cercanos de un documento X, extraemos todos los elementos de sus cubetas, y calculamos similitud de esos documentos contra el documento X. Filtramos si es necesario para eliminar pares de similitud baja.
  • Para encontrar vecinos cercanos de un nuevo documento, calculamos sus tejas, firma y finalmente cubetas. Recuperamos los elementos que caen en sus cubetas. Evaluamos similitud y filtramos si es necesario.

Pares de similitud alta

  • Para encontrar pares de similitud alta, calculamos los pares solo dentro de cada cubeta. Eliminamos pares duplicados, calculamos similitud exacta y filtramos si es necesario para eliminar pares de baja similitud que por azar cayeron en una misma cubeta.

Clustering

  • Podemos hacer clustering con los datos de pares similares, por ejemplo, con un algoritmo de detección de comunidades (como hicimos arriba).

2.10 Ejemplo: pares similares de tweets

En primer lugar, podemos deduplicar tweets idénticos. Esto lo podemos hacer con una sola función hash:

Calculamos firmas

##    user  system elapsed 
##   2.910   0.008   2.918
##    user  system elapsed 
##    18.8     0.0    18.8

Y ahora calculamos cubetas. En este caso, habrá dos cubetas por documento, cada una con 6 hashes:

## $`1`
## [1] 1 2 3 4 5 6
## 
## $`2`
## [1]  7  8  9 10 11 12
##                                                                                   1 
##    "123456|-2023656247/-2112001395/-2013285124/-2055981208/-2099430998/-2102822692" 
##                                                                                   2 
## "789101112|-2099337985/-2140123240/-1961096623/-2096611895/-2070344527/-2098661439"
##    user  system elapsed 
##   9.697   0.004   9.701
## # A tibble: 10 x 3
##    cubeta                                                         docs         n
##    <chr>                                                          <list>   <int>
##  1 789101112|-1966318327/-2043868337/-2143690673/-1830018782/-13… <int [1…    19
##  2 123456|-1997369272/-2143786891/-2020059395/-2090443285/-20281… <int [1…    16
##  3 789101112|-2144697372/-2145752511/-2098900185/-2131328141/-21… <int [1…    16
##  4 789101112|-2085403383/-2034628536/-2146807097/-2029964822/-21… <int [1…    15
##  5 789101112|-2068860743/-2102616697/-2058902173/-2114672701/-21… <int [1…    14
##  6 789101112|-2144697372/-1957253233/-2089047173/-2057929271/-19… <int [1…    13
##  7 123456|-2142045021/-2054826468/-2129777399/-2069799085/-20922… <int [1…    12
##  8 123456|-2110688584/-2094323986/-2106738844/-2137978549/-20539… <int [1…    11
##  9 789101112|-2090171109/-2056793443/-2112368831/-1961937447/-21… <int [1…    11
## 10 789101112|-2142359553/-2001956537/-2107804680/-1924184205/-19… <int [1…    11

Nótese que

## [1] "Exo Please play of"  "BBH Please play of"  "Please play of"     
## [4] "X Please play of"    "Please play of Aeri" "NEW Please play of"
## [1] "Thanks for lighting up my profile pic am behind all the way they are going to this FIFA Russia"    
## [2] "Thanks for lighting up my profile pic am behind all the way they are going to this FIFA support"   
## [3] "Thanks for lighting up my profile pic am behind all the way they are going to this FIFA to France" 
## [4] "Thanks for lighting up my profile pic am behind England all the way they are going to this FIFA"   
## [5] "Thanks for lighting up my profile pic am behind all the way they are going to this FIFA dlala pois"
## [6] "Thanks for lighting up my profile pic am behind all the way they are going to"
## [1] "Dear France Congratulations on winning the of your team is African cut out the racism and xenophobia of your team are Muslims cut out the Islamophobia Africans and Muslims delivered you second World Cup now"                                         
## [2] "Dear France Congratulations on winning the of your team is African cut out the racism and xenophobia of your team are Muslims cut out the Islamophobia Africans and Muslims just delivered you second World Cup now deliver them justice Khaled Beydoun"
## [3] "Dear France Congratulations on winning the of your team is African cut out the racism and xenophobia of your team are Muslims cut out the Islamophobia Africans and Muslims delivered you second World Cup now deliver them justice Repost"             
## [4] "Retweeted Khaled Beydoun Dear France Congratulations on winning the of your team is African cut out the racism and xenophobia of your team are Muslims cut out the Islamophobia Africans and Muslims delivered you second Wo"                           
## [5] "France Congratulations on winning the of your team is African cut out the racism and xenophobia of your team are Muslims cut out the Islamophobia Africans and Muslims delivered you second World Cup now deliver them justice"                         
## [6] "Dear France Congratulations on winning the of your team is African cut out the racism of your team are Muslims cut out the Islamophobia Africans and Muslims just delivered you second World Cup now deliver them justice"
## [1] 643

Ahora podemos calcular similitud exacta y agrupar. El número de pares es manejable. Filtramos aquellas similitudes que nos interesen:

Podemos hacer clustering con las similitudes de Jaccard, filtrando los que estén por debajo de una similitud predeterminada:

## IGRAPH clustering label propagation, groups: 375, mod: 0.98
## + groups:
##   $`1`
##   [1] "12494" "78789" "93577"
##   
##   $`2`
##   [1] "52414"  "81003"  "3477"   "91277"  "105559"
##   
##   $`3`
##   [1] "39602"  "74770"  "55998"  "103453"
##   
##   $`4`
##   + ... omitted several groups/vertices

Y con esto hemos terminado nuestro ejercicio de deduplicación.

Preguntas:

  1. ¿Puedes aproximar el tiempo que tardaría calcular similitud exacta entre todos los pares? Compara con el proceso mostrado arriba
  2. Piensa en aplicaciones interesantes del proceso que acabamos de mostrar, quizá pensando en otro tipo de textos.
  3. ¿Qué efecto tiene el número de hashes que escogimos? ¿El número de cubetas que formamos? (Discutiremos más en la siguiente parte)

2.11 Ejemplo: encontrar vecinos cercanos de documentos nuevos

Aplicamos la transformación a cubetas:

## [1] "Croatia are through"                                                                       
## [2] "Yes Croatia are through"                                                                   
## [3] "So Croatia are through barely"                                                             
## [4] "So cool from Rakitic Croatia are through"                                                  
## [5] "If Croatia score they are through"                                                         
## [6] "And Croatia are through"                                                                   
## [7] "One of these teams will be in the final Russia Croatia Sweden Switzerland Colombia"        
## [8] "One of these teams will be in the final Russia Croatia Sweden Switzerland Colombia England"
## [9] "Russia Croatia Sweden Switzerland Colombia England One of these teams will be in the final"

2.12 Resumen

Veamos qué resolvimos con cada uno de los pasos, desde la conversión a tejas hasta vecinos cercanos resumen adaptado de aquí:

  1. Método de tejas: partes de documentos similares pueden ocurrir en distinto orden.
  2. Firmas de minhashing: Representación de documentos en tejas puede utilizar mucha memoria. Con minhashing tenemos una versión más compacta que preserva similitud
  3. LSH y cubetas: no es necesario comparar todos los pares posibles, sino solamente aquellos con firmas similares.

2.13 Algoritmo por renglón

Aunque la implementación por documento que mostramos arriba es efectiva porque podemos paralelizar por grupos de documentos, y generalmente esto funciona bien, tiene el defecto de que hacemos una cantidad considerable de cálculos repetidos: cada vez que encontramos una teja calculamos de nuevo su hash para formar las firmas.

En (Leskovec, Rajaraman, and Ullman 2014) se propone un algoritmo por renglón o por teja, que funciona de la siguiente forma:

Supongamos que tenemos \(h_1,\ldots, h_k\) permutaciones. Denotamos por \(SIG_{i,c}\) el elemento de la matriz de firmas para la \(i\)-ésima permutación y el documento \(c\).

Cálculo de matriz de firmas Inicializamos la matriz de firmas como \(SIG_{i,c}=\infty\). Para cada renglón \(r\) de la matriz original: - Para cada columna \(c\): 1. Si \(c\) tiene un cero en el renglón \(r\), no hacemos nada. 2. Si \(c\) tiene un uno en el renglón \(r\), ponemos para cada \(i\) \[SIG_{i,c} = \min\{SIG_{i,c}, h_i(r)\}.\]

Ejemplo: tweets

##    user  system elapsed 
##   4.175   0.012   4.187
##    user  system elapsed 
##  39.801   0.264  40.066

Que en este caso es considerablemente más rápido que el algoritmo por documento.

Referencias

Leskovec, Jure, Anand Rajaraman, and Jeffrey David Ullman. 2014. Mining of Massive Datasets. 2nd ed. New York, NY, USA: Cambridge University Press. http://www.mmds.org.

Mullen, Lincoln. 2016. Textreuse: Detect Text Reuse and Document Similarity. https://CRAN.R-project.org/package=textreuse.