Buscando similitudes en grandes datasets — Shingling, Min hashing y Locality-sensitive hashing

En esta publicación vamos a hablar acerca Shingling, Min hashing y Locality-sensitive hashing, y cómo estas técnicas nos pueden servir para encontrar similudes en grandes conjuntos de datos.

Para comenzar es necesario entender el problema, hay escenarios en los que la amplia variedad de elementos que se tratan es muy grande. Si en este escenario queremos encontrar elementos repetidos, podría no parecer tan difícil, bastaría con comparar elementos concretos con el resto del conjunto, ¿no? En la vida real puede no ser tan sencillo, puesto que pequeñas variaciones en los elementos podríamos querer que pasen desapercibidas (puesto que igual no son significativas). O tal vez establecer un umbral de similitud para poder determinar si esos elementos son tan iguales como nos interesa, a pesar de ser distintos. Y eso por no hablar del coste computacional asociado.

Pongamos algunos ejemplos:

• Un ejemplo típico (y un caso real) podría ser el de un buscador. El buscador quiere indexar el mayor número de páginas posible, pero también quiere ofrecer contenido de calidad a sus usuarios. Es por ello que descartar resultados repetidos podría ser una necesidad. En ocasiones hay webs que se dedican a copiar contenido (como por ejemplo muchas que hacen black SEO), o tal vez exista una fuente común de información para un determinado tipo de webs. Podríamos incluso estar hablando de Google News, que quiere mostrar todas las noticias, pero no le interesa que todas sean la misma pero de distintas fuentes (aunque sí podría querer mostrar distintos puntos de vista para un mismo tema). El problema es que, aunque la página o la noticia sean la misma, el formato puede variar. Cada sitio tendrá un estilo distinto, más o menos publicidad, etc. Incluso podría tener el texto ordenado de otra forma. ¿Cómo de similares han de ser dos páginas para descartar una de ellas? ¿Cómo medimos esa similitud? ¿Cómo afrontamos todas estas comparaciones a nivel computacional?
• Un ejemplo aún más obvio podría ser un sistema de detección de plagio. Como sabemos, el plagio no tiene por qué ser de forma directa, sino que el supuesto plagiador podría modificar palabras concretas o alterar el orden de algunos párrafos, eliminar información, etc. Es por ello que sería necesario poder comparar la similitud y establecer el umbral a partir del cual se decide que el documento comete plagio. Hay que tener en cuenta que no estamos hablando del significado del texto, sino de contener los mismos términos.
• Otro ejemplo sería un sistema que determina a qué usuario se parece el comprador de una tienda online. De modo que el sistema pueda recomendarle productos que otros compradores con gustos y tendencias similares suelan comprar. Está claro que por muy parecidos que sean dos usuarios, es difícil que sus compras sean las mismas, por lo que habría que buscar similitudes entre los usuarios teniendo en cuenta que tenemos que establecer un umbral más amplio.
• Otro caso (y este es mi favorito) podría ser en la clasificación de malware. Es frecuente crear variaciones del mismo malware para confundir a los antivirus. De modo que si un antivirus ha marcado una muestra en concreto como malware, crear una variación de la misma modificando los puntos adecuados podría resultar en la indetectabilización de esa muestra, o en una dificultad para clasificar esa muestra como una de la misma familia que la que ya conocemos. O también podríamos querer detectar que dos muestras que son la misma, pero tienen alguna pequeña variación (como un usuario, una dirección a la que conecta, etc), son la misma. La tarea de buscar qué muestras son iguales comparando cada una de ellas con un gran conjunto de muestras, no solo es una tarea computacionalmente compleja, sino que vuelve a plantear el problema de cómo podemos decidir que dos elementos distintos tienen una similitud suficiente.

Para poder procesar toda esta información de forma comprimida, una idea puede ser utilizar el hash de cada elemento. Un hash identifica perfectamente a un elemento mediante una cadena de una longitud acotada de caracteres. El problema de esto es que en los hashes lo normal suele ser querer que no existan colisiones, de modo que nunca hayan dos entradas que den el mismo resultado (por más parecidas que puedan ser), y que dos entradas sean similares no implica que los resultados sean ni remotamente parecidos. Un ejemplo, con un hash que sí que tiene colisiones conocidas a día de hoy (y que por lo tanto ya no es seguro) es el MD5. Aquí tenemos dos hashes para dos entradas parecidas:

• baca → 683dcbc167745a402a828953baec4c88
• vaca → 90f077d7759d0d4d21e6867727d4b2bd

Para tratar de solventar esto aparecen los hashes difusos (fuzzy hashes), con el objetivo de que dos entradas similares sí generen dos salidas similares. Y que incluso podamos estimar con preción cómo de similares son. A continuación veremos una técnica que nos aproxima a cómo podemos operar estas entradas para generar hashes con los que medir la similitud.

¿Por qué shingling, min hashing y LSH? Porque min hashing parte de shingling, y LSH parte de min hashing. En shingling transformamos los elementos en conjuntos, en min hashing reducimos la dimensionalidad y generamos hashes, y en LSH determinamos las coincidencias entre estos hashes.

Shingling

Esta idea que nos acerca a lo que buscamos, consiste en convertir el interior de un documento en un conjunto de cadenas de un tamaño concreto (al que llamaremos k, y a las cadenas las llamaremos k-shingles), con el objetivo de luego así poder compararlas con las de otros documentos sin importar el orden.

Por ejemplo, para el caso que veíamos anteriormente, se haría del siguiente modo:

• Primero elegimos una k apropiada. Cuanto más pequeño sea este valor, más k-shingles obtendremos y más fácil será interpretar dos elementos como similares. Lo mejor, para un conjunto de elementos grandes y con muchas posibilidades, es elegir un valor k grande (por ejemplo, un valor de 9). En nuestro caso, como nuestros elementos son solo dos palabras, elegimos k=2.
• Dividimos cada elemento en k-shingles, formando agrupaciones de cada letra con sus letras vecinas, de tamaño 2:
  baca → {ba, ac, ca} | vaca → {va, ac, ca}
• A simple vista ya podemos ver que se parecen, puesto que ambos conjuntos comparten dos cadenas iguales. Para computar esta similitud podemos utilizar el llamado índice Jaccard.

El índice Jaccard no es más que la división de la intersección de dos conjuntos entre su unión, es decir, dividir los elementos comunes entre el total de posibles elementos. El resultado simpre será entre 0 y 1, siendo 0 que no se parecen en nada, y 1 que son idénticos.

Índice Jaccard

A = {ba, ac, ca}, B ={va, ac, ca}

Intersección y unión de “vaca” y “baca”

A ∩ B = {ac, ca} → 2, A∪B = {ba, ac, ca, va} → 4

J(A,B) = 2 / 4 = 0.5

La similitud para estas dos palabras, utilizando k = 2 y el índice Jaccard, es de 0.5.

Podríamos calcular lo mismo de forma gráfica:

Represantamos A y B poniendo 1 en caso de que contengan cada uno de los shingles, o 0 en caso de que no.

• Numerador: Contamos los 1’s que tienen en común → 2.
• Denominador: Contamos todos en los que al menos uno de los dos tiene un 1 → 4.

El resultado sería el mismo: J(A,B) = 2 / 4

• Si hubiéramos elegido k=1, el resultado sería:

A = {b, a, c}, B ={v, a, c}

A ∩ B = {a, c} → 2, A∪B = {b, v, a, c} → 4

J(A,B) = 2 / 4 = 0.5

• Si hubiéramos elegido k=3, el resultado sería:

A = {bac, aca}, B ={vac, aca}

A ∩ B = {aca} → 1, A∪B = {bac, vac, aca} → 3

J(A,B) = 1 / 3

La potencia de este método es que si los párrafos de un documento apareciesen en un orden alterado, esto no afectaría al resultado. O podría producir resultados muy similares si las palabras son las mismas pero en diferente orden.

Para nuestro caso, en el que solamente comparamos palabras, parece un método viable. Pero tenemos que tener en cuenta que, por ejemplo, si estuvieramos comparando documentos, necesitamos dividir cada documento en conjuntos de letras y luego comparar todos los conjuntos de letras con todos los demás documentos.

En grandes conjuntos de datos calcular el índice Jaccard puede ser muy ineficiente. Su eficiencia es: O(n)=0.5*(n²-n).

Nota: Para ahorrar algo de espacio los shingles pueden comprimirse. Por ejemplo, a bac podríamos llamarle 0, a vac llamarle 1, y así.

Min hashing

Este método nos permite generar firmas para los documentos gracias a los shingles, para intentar compararlos de un modo más eficiente al índice Jaccard. Vamos a verlo directamente con un ejemplo.

Partiendo el caso anterior, tenemos dos documentos:

• A = {ba, ac, ca}
• B ={va, ac, ca}

Vamos a representar los documentos en una tabla:

En la columna de la izquierda hemos puesto todos los shingles posibles, mientras que en las siguientes columnas hemos puesto un 1 si ese documento contiene ese shingle o un 0 si no lo contiene, representando cada columna a un documento.

Nota: Hemos utilizados los shingles generados en el caso anterior, pero no tiene que ser necesariamente esto lo que utilicemos. Podrían ser palabras o cualquier otro método que consideremos oportuno para fraccionar el elemento en otros subelementos que sean significativos.

Ahora vamos a generar de forma aleatoria varias permutaciones distintas de los shingles, por ejemplo:

Cada columna es una permutación de shingles. Cada casilla contiene un índice, el cual indica en qué posición se computará cada fila. Por ejemplo, para la permutación representada por el color rosa: la primera fila en computarse será la segunda, la segunda la primera, la tercera será la última y la cuarta será la tercera.

Ahora, partiendo de este orden en el que hemos permutato los shingles, tenemos que indicar en qué fila aparecerá por primera cada shingle para cada documento. Generando de este modo una firma para cada documento de una longitud igual al número de permutaciones que hayamos establecido. El objetivo es obtener un valor similar al índice Jaccard, cuanta más longitud tengan estas firmas, menor será el error.

El nombre que se les da a estas estructuras es (de izquierda a derecha):

• Permutaciones π.
• Input Matrix: Tabla en las que tenermos los documentos A y B representados en binario respecto a los shingles.
• Signature Matrix: Tabla que ahora mismo tenemos vacía, donde obtendremos las firmas de cada documento como resultado.

Para la primera permutación, la primera fila en computarse es la primera. En esta fila tenemos un 1 para el documento A, pero no tenemos valor para el documento B. Colocamos el índice en la casilla que corresponde con el documento A:

Solo tenemos en cuenta la primera ocurrencia, obteniendo de este modo un hash reducido (por eso recibe el nombre de MinHash).

Vamos a la segunda fila según la permutación. En este caso sí encontramos un 1 para el documento B, de modo que colocamos el índice en el que lo hemos encontrado:

Como ya tenemos un valor para todos los documentos en la primera permutación, pasamos a la siguiente. En este caso la última fila es la primera, y aquí encontramos el primer valor para el documento B, de modo que colocamos el índice 1 para dicho documento:

Continuamos con la siguiente fila para buscar el valor que nos falta. En este caso tenemos un resultado positivo para el documento A, de modo que colocamos el índice como corresponde:

Pasamos a la siguiente permutación. En este caso ambos documentos tienen un resultado positivo, así que colocamos en ambos el índice 1.

Hemos generado dos firmas, uno para cada documento que queremos comparar:

MinHash(A) = [1, 2, 1]

MinHash(B) = [2, 1, 1]

Estas firmas obtenidas podrían ser nuestros hashes difusos para estos documentos.

Ahora realizaremos una comparación entre ambos documentos partiendo de este resultado. Hay que comparar los resultados de cada permutación de un documento con los de todos los demás documentos, para poder determinar el índice de similitud de todos con todos.

En este caso solo tenemos dos, por lo solo compararemos 1–2:

La similitud entre el documento A y el documento B, para este caso en el que hemos usado k=2 y 3 permutaciones, es de 1/3. Recordemos que anteriormente habíamos obtenido J(A,B) = 1/3. Por lo que cumplimos nuestro objetivo de obtener un índice similar al obtenido con Jaccard.

• MinHashSimilarity(A,B) = 1/3
• J(A,B) = 1/3

Cuantas más permutaciones usemos, más fácil será que nos acerquemos al índice Jaccard.

En este ejemplo tan reducido no queda constancia de la potencia de esto. Tenemos que imaginar un documento que podría estar conformado por, por ejemplo, 1000 shingles distintos. Ese documento tal vez podría quedar representado en 100 permutaciones. Por lo que estariamos reduciendo enormemente la dimensión de nuestra matriz sin perder la representación.

Locality-sensitive hashing (LSH)

Este método parte de la Signature Matrix que obtenemos con el min hashing (o con otras técnicas parecidas), con el objetivo de poder establecer si las firmas obtenidas para dos documentos convierten a estos en candidatos a ser similares o no, de un modo más eficiente que el cálculo de la similitud que hacíamos en el apartado anterior.

Para llevar a cabo este método crearemos una segunda tabla a la que llamaremos hash table, la cual estará dividida en un número concreo de huecos (buckets — b). Esta tabla será la que nos permitirá encontrar candidatos.

Supongamos que partimos de una Signature Matrix como esta:

Lo que haremos será dividir la tabla en bandas (b), englobado cada franja varias filas (r):

El número de bandas o de filas que engloba cada banda hay que elegirlo en función del caso que estemos tratando. Podemos probar con distintos valores y quedarnos con el que mejor resultados nos ofrezca. Esto último quiere decir quedarnos con el que más colisiones provoque en la hash table evitando los falsos positivos. Un falso positivo es cuando estimamos que dos documentos no similares sí son candidatos a serlo.

En cada banda aplicaremos una función hash a cada porción de columna y ese resultado lo guardaremos en un bucket de la hash table, de modo que puede haber columnas que tengan el mismo resultado (colisiones), puesto que el hash es el mismo.

Vamos a ver un ejemplo:

• MinHash(A) = [1, 2, 1, 1, 2, 1]
• MinHash(B) = [2, 1, 1, 1, 2, 1]
• MinHash(C) = [3, 4, 2, 4, 3, 1]
• MinHash(F) = [1, 2, 1, 2, 1, 1]

Vamos a separar cada MinHash en grupos de tres elementos:

• MinHash(A) = [1, 2, 1, 1, 2, 1] -> [121, 121]
• MinHash(B) = [2, 1, 1, 1, 2, 1] -> [211, 121]
• MinHash(C) = [3, 4, 2, 4, 3, 1] -> [342, 431]
• MinHash(D) = [1, 2, 1, 2, 1, 1] -> [121, 211]

O lo que es lo mismo:

Esto nos daría que:

• 121 identifica a A, B y D.
• 211 identifica a B y D.
• 342 identifica a C.
• 431 identifica a C.

• B y D tienen una probabilidad de ser parecidos del 100%.
• A y B tienen una probabilidad de ser parecidos del 50%.
• A y D tienen una probabilidad de ser parecidos del 50%.
• C tiene una probabilidad del 0% con el resto.

No hemos aplicado un hash por la sencillez del caso, pero podríamos haber utilizado cualquier función hash, como MD5:

• 121 -> a7625f2478bba123a77864a797cd05ec
• 211 -> 6cd131e70fbde5042e42d18436605d6d
• […]

El MD5 se compone de 32 caracteres. Si nuestra columna en esa banda fuera mucho más grande de eso, el hash MD5 seguiría siendo de 32 caracteres, por lo que podríamos ahorrar espacio. En la tabla podríamos tener tantos buckets como valores posibles pueda resultar la función hash elegida.

Que dos documentos tengan colisiones no significa que sean parecidos. Pero sí significa que al menos una pequeña parte de ellos coincide. Es tarea nuestra en cada caso definir el umbral que marcará cuántas colisiones han de tener dos documentos para considerarlos candidatos a ser similares.

Una vez seleccionados los elementos que consideramos candidatos a ser similares, podríamos quedarnos con ellos directamente, o aplicar una segunda verificación sobre estos. Realizando por ejemplo el MinHashSimilarity o el Índice Jaccard, teniendo en cuenta de que el problema ahora es mucho más acotado.

En este repositorio de GitHub podemos aprender más acerca de la implementación en un caso práctico: https://github.com/santhoshhari/Locality-Sensitive-Hashing

Se ha escrito mucho sobre el problema de buscar similitudes en grandes conjuntos de datos, por lo que podemos encontrar otras técnicas o mejoras y variantes de esta. En una próxima publicación veremos algunas herramientas para buscar similitudes que aplican hashes difusos, y que podrían aplicarse para buscar malwares similares en muestras distintas.