MinHash

En ciencia de la computacion, MinHash (o el esquema sensible a localidad que trata permutaciones independientes relativos al mínimo) es una técnica para estimar rápidamente cuan similares son dos conjuntos. El esquema fue inventado por Andrei Broder en 1997^[1] e inicialmente usado en el motor de búsqueda AltaVista para detectar páginas web duplicadas y eliminarlas de los resultados de búsqueda.^[2] También ha sido aplicado en problemas de clustering, tales como agrupación de documentos por la similitud de las palabras que contienen.^[1]

En la mayoría de los casos, se utilizan funciones hash para separar y ocultar los datos, de modo que datos similares tengan claves diferentes. Sin embargo, se propone utilizar funciones hash para el propósito opuesto: detectar similitudes entre datos.

La detección de similitudes y la clasificación es un problema bien estudiado, pero normalmente se involucran n² comparaciones por pares. Al utilizar una función hash que convierte datos similares en valores similares, la similitud se puede detectar simplemente comparando valores de clave hash preclasificados. El reto es encontrar una función hash de similitud que minimice los falsos positivos.

SimHash produce claves hash con valores enteros, se recurrió a datos auxiliares para mejorar las pruebas de similitud. Los valores clave se basaron en contar las ocurrencias de ciertas cadenas binarias dentro de un fichero y combinando estas sumas. No obstante, los valores clave seguían siendo aproximadamente proporcionales al tamaño del fichero, lo que provocaba muchos falsos positivos.

Se estableció como objetivo la creación de una "función hash de similitud". Normalmente, las funciones hash se diseñan para minimizar las colisiones (cuando dos entradas diferentes tienen el mismo valor de clave). Con las funciones hash criptográficas, se espera que las colisiones sean casi imposibles, y que los datos casi idénticos correspondan a claves muy distintas. Sin embargo, la función hash de similitud tenía la intención opuesta: se buscaba que datos similares correspondieran a claves hash muy similares o incluso a la misma clave hash, y que la distancia entre las claves fuera una medida de la diferencia entre los datos.

Similitud Jaccard y valores de hash mínimos

El coeficiente de similitud de Jaccard de dos conjuntos $A$ and $B$ se define como

J(A,B)={{|A\cap B|} \over {|A\cup B|}}.

Es un número entre 0 y 1; es 0 cuando los dos conjuntos son disjuntos, 1 cuando son iguales, y estrictamente entre 0 y 1 en caso contrario. Es un indicador comúnmente utilizado de la similitud entre dos conjuntos: dos conjuntos son más similares cuando su índice de Jaccard está más cerca de 1, y más disímiles cuando su índice de Jaccard es más cercano a 0.

Sea h una función hash que mapea los miembros de $A$ y $B$ a enteros distintos, y que para cada conjunto S define $h min (S)$ como el miembro $x$ de $S$ con el valor mínimo de $h (x)$ . Luego $h min (A) = h min (B)$ exactamente cuando el valor mínimo $A \cup B$ esta en la intersección de $A \cap B$ . Por tanto,

Pr[h min (A) = h min (B)] = J (A, B).

En otras palabras, si $r$ es una variable aleatoria que es 1 cuando $h min (A) = h min (B)$ y 0 en otro caso, entonces $r$ es un estimador insesgado de $J (A, B)$ , a pesar de que tiene una varianza muy alta para ser útil por sí solo. La idea del esquema de MinHash es reducir la varianza promediando juntas varias variables construidas de la misma manera.

Algoritmo

Variante con muchas funciones hash

La versión más simple del esquema MinHash usa $k$ funciones hash diferentes, donde $k$ es un parámetro entero fijo, y representa cada conjunto $S$ por los valores $k$ de $h min (S)$ para estas $k$ funciones.

Para estimar $J (A, B)$ usando esta versión del esquema, sea $y$ el número de funciones hash para las cuales $h min (A) = h min (B)$ , y usamos $y / k$ como el estimado. Este estimado es el promedio de $k$ variables aleatorias 0-1, cada una de las cuales es 1 cuando $h min (A) = h min (B)$ y 0 de otra forma, y cada uno de los cuales es un estimador insesgado de $J (A, B)$ . Por tanto, su promedio es también un estimador insesgado, y para la desviación estándar para sumas de variables aleatorias 0-1, su error esperado es $O(1/\sqrt k)$ .^[3]

Por tanto, para cualquier constante $ε > 0$ hay una constante $k = O(1/ε 2)$ tal que el error esperado del estimado es a lo sumo $ε$ . Por ejemplo, se necesitarían 400 hashes para estimar $J (A, B)$ con un error esperado menor o igual a .05.

Variante con una sola función de hash

Puede ser costoso computacionalmente calcular múltiples funciones hash, pero una versión relacionada del esquema MinHash evita esta pena mediante el uso de una única función hash y lo utiliza para seleccionar varios valores de cada conjunto en lugar de seleccionar un solo valor mínimo por la función hash. Sea $h$ una función de hash, y sea $k$ un entero fijo. Si $S$ es cualquier conjunto de $k$ o más valores en el dominio de $h$ , definen $h (k) (S)$ como el subconjunto de $k$ miembros de $S$ que tienen los valores más pequeños de $h$ . Este subconjunto $h (k) (S)$ es usado como una firma para el conjunto $S$ , y la similitud de los dos conjuntos se estima mediante la comparación de sus firmas

Específicamente, sea A y B sean dos conjuntos cualesquiera. Luego $X = h (k) (h (k) (A) \cup h (k) (B)) = h (k) (A \cup B)$ sea un conjunto de k elementos de $A \cup B$ , y si h es una función aleatoria de k elementos con igualdad de probabilidad de ser escogidos; o sea, $X$ es un muestra aleatoria simple de $A \cup B$ . El subconjunto $Y = X \cap h (k) (A) \cap h (k) (B)$ es el conjunto de los miembros de $X$ que pertenecen a la intersección $A \cap B$ . Por tanto, | $Y$ |/ $k$ es un estimador insesgado de $J (A, B)$ . La diferencia entre este estimador y el estimador producido por múltiples funciones hash es que $X$ siempre tiene exactamente $k$ miembros, mientras que las múltiples funciones de hash pueden dar lugar a un menor número de elementos incluidos en la muestra debido a la posibilidad de que dos funciones hash diferentes pueden tener los mismos mínimos. Sin embargo, cuando $k$ es pequeño en relación con los tamaños de los conjuntos, esta diferencia es insignificante.

Para cotas de Chernoff estándar para el muestreo sin reemplazo, este estimador tiene error esperado $O(1/\sqrt k)$ , igualando el desempeño del esquema hash-función-múltiple.

Análisis de tiempo

El estimador $| Y |/ k$ puede ser computado en $O(k)$ dadas las dos firmas de los conjuntos dados, en cualquier variante del esquema. Por tanto, cuando $ε$ y $k$ son constantes, el tiempo para calcular la similitud estimada a partir de las firmas es también constante. La firma de cada conjunto se puede calcular en tiempo lineal en el tamaño del conjunto, por lo que cuando muchas similitudes parejas deben estimarse este método puede dar lugar a un ahorro sustancial en el tiempo de funcionamiento en comparación con hacer una comparación completa de los miembros de cada conjunto. Específicamente, para el tamaño de conjunto $n$ la variante de muchos hash toma tiempo $O(n k)$ . La variante de un solo hash es generalmente más rápido, lo que requiere tiempo $O(n log k)$ para mantener la lista ordenada de los mínimos.^{[cita requerida]}

Permutaciones independientes al mínimo

Con el fin de implementar el esquema MinHash como se describió anteriormente, se necesita la función hash $h$ para definir una permutación aleatoria en $n$ elementos, donde $n$ es el número total de elementos distintos en la unión de todos los conjuntos que compararse. Pero como hay $n!$ permutaciones distintas, se requerirían $Ω(n log n)$ bits sólo para especificar una permutación verdaderamente aleatoria, un gran número impracticable, incluso para valores moderados de $n$ . Debido a este hecho, por analogía con la teoría de hashing universal, ha habido un trabajo significativo en la búsqueda de una familia de permutaciones que es "independiente relativo al mínimo, lo que significa que para cualquier subconjunto del dominio, cualquier elemento es igualmente probable que sea el mínimo. Se ha establecido que una familia independiente-min racional de permutaciones debe incluir, al menos

lcm(1,2,...,n)\geq e^{n-o(n)}

permutaciones diferentes, y por lo tanto que necesita $Ω(n)$ bits para especificar una única permutación, todavía impracticablemente grande.^[2]

Debido a esta falta de sentido práctico, se han introducido dos nociones variantes de la independencia respecto al mínimo: familias de permutaciones independientes al mínimo restringidas y familias independientes al mínimo aproximadas. La independencia respecto al mínimo restringido es la propiedad de independencia de mínimo restringido a ciertos conjuntos de cardinalidad como máximo $k$ .^[4] La independencia respecto al mínimo aproximado tiene como máximo una probabilidad fija e de la variación de la plena independencia.^[5]

Aplicaciones

Las aplicaciones originales para MinHash involucraban agrupación y la eliminación de duplicados entre documentos web, representados como conjuntos de las palabras que aparecen en dichos documentos.^[1]^[2] Técnicas similares se han utilizado también para el agrupamiento y eliminación de los duplicados para otros tipos de datos, como imágenes: en el caso de los datos de imagen, una imagen puede ser representada como un conjunto de sub-imágenes pequeñas cortadas de él, o como conjuntos de descripciones de las características de imágenes más complejas.^[6]^[7]

En minería de datos,Cohen et al. (2001) utiliza MinHash como una herramienta para reglas de asociación. Dada una base de datos en la que cada entrada tiene múltiples atributos (visto como una matriz de 0-1 con una fila por la entrada de base de datos y una columna por cada atributo) utilizan aproximaciones basadas en MinHash al índice de Jaccard para identificar pares candidatos de atributos que co-ocurren frecuentemente, y luego calcular el valor exacto del índice para sólo los pares para determinar aquellos cuyas frecuencias de co-ocurrencia están por debajo de un umbral estricto dado.^[8]

El objetivo de SimHash se centró en la detección de semejanzas. Dos ficheros con una disparidad de tamaño son implícitamente diferentes y las relaciones de contención entre ambos no necesariamente hacen que los dos sean "similares" según la métrica.

Para que dos les sean similares según la métrica, deben contener un gran número de piezas comunes. Otra división en las técnicas de detección de similitud es la granularidad y la cobertura de estas piezas. SimHash opera con una granularidad muy reducida, a nivel de bytes o palabras. No intentamos obtener una cobertura completa, sino que se enfoca solo en las partes de aquel fichero que coinciden con el conjunto de patrones de bits.

Dada una métrica de similitud, es necesario establecer un umbral para determinar cuán cercanas deben estar dentro de esa métrica para considerarse similares. Nos centramos en les que tienen un alto grado de similitud, idealmente entre el 1% y el 2%.

Otros usos

El esquema MinHash puede ser visto como una instancia del hashing sensible a la localidad, una colección de técnicas para el uso de funciones hash para mapear grandes conjuntos de objetos a valores de hash más pequeños de tal manera que, cuando dos objetos tienen una pequeña distancia uno de otro, sus valores de hash es probable que sean la misma. En este caso, la firma de un conjunto puede ser visto como su valor hash. Existen otra localidad técnicas de hashing sensibles para Distancia Hamming entre conjuntos y similitud coseno entre vectores; el hash sensible a la localidad tiene importantes aplicaciones en algoritmos de búsqueda de vecino más cercano.^[9] Para grandes sistemas distribuidos, y en particular MapReduce, existen versiones de MinHash para ayudar a las similitudes de cómputo sin depender de la dimensión de punto modificados.^[10]

Evaluación y puntos de referencia

Una evaluación a gran escala fue realizada por Google en 2006^[11] para comparar el rendimiento de Minhash y Simhash^[12] algorithms. En 2007 Google reportó usar Simhash para la detección de duplicados durante web crawling^[13] y el uso de MinHash y LSH para la personalización de Google Noticias.^[14]

Véase también

Referencias

↑ ^a ^b ^c Broder, Andrei Z. (1997), «On the resemblance and containment of documents», Compression and Complexity of Sequences: Proceedings, Positano, Amalfitan Coast, Salerno, Italy, June 11-13, 1997, IEEE, pp. 21-29, doi:10.1109/SEQUEN.1997.666900, archivado desde el original el 31 de enero de 2015, consultado el 19 de diciembre de 2014 ..
↑ ^a ^b ^c Broder, Andrei Z.; Charikar, Moses; Frieze, Alan M.; Mitzenmacher, Michael (1998), «Min-wise independent permutations», Proc. 30th ACM Symposium on Theory of Computing (STOC '98), New York, NY, USA: Association for Computing Machinery, pp. 327-336, doi:10.1145/276698.276781 ..
↑ Vassilvitskii, Sergey (2011), COMS 6998-12: Dealing with Massive Data (lecture notes, Columbia university) ..
↑ Matoušek, Jiří; Stojaković, Miloš (2003), «On restricted min-wise independence of permutations», Random Structures and Algorithms 23 (4): 397-408, doi:10.1002/rsa.10101 ..
↑ Saks, M.; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000), «Low discrepancy sets yield approximate min-wise independent permutation families», Information Processing Letters 73 (1–2): 29-32, doi:10.1016/S0020-0190(99)00163-5 ..
↑ Chum, Ondřej; Philbin, James; Isard, Michael; Zisserman, Andrew (2007), «Scalable near identical image and shot detection», Proceedings of the 6th ACM International Conference on Image and Cideo Retrieval (CIVR'07), doi:10.1145/1282280.1282359 .
↑ Chum, Ondřej; Philbin, James; Zisserman, Andrew (2008), «Near duplicate image detection: min-hash and tf-idf weighting», Proceedings of the British Machine Vision Conference 3, p. 4, archivado desde el original el 24 de febrero de 2021, consultado el 19 de diciembre de 2014 ..
↑ Cohen, E.; Datar, M.; Fujiwara, S.; Gionis, A.; Indyk, P.; Motwani, R.; Ullman, J. D.; Yang, C. (2001), «Finding interesting associations without support pruning», IEEE Transactions on Knowledge and Data Engineering 13 (1): 64-78, doi:10.1109/69.908981 ..
↑ Andoni, Alexandr; Indyk, Piotr (2008), «Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions», Communications of the ACM 51 (1): 117-122, doi:10.1145/1327452.1327494 ..
↑ Zadeh, Reza; Goel, Ashish (2012), Dimension Independent Similarity Computation, arXiv:1206.2082 ..
↑ Henzinger, Monika (2006), «Finding near-duplicate web pages: a large-scale evaluation of algorithms», Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval. ACM .
↑ Charikar, Moses S. (2002), «Similarity estimation techniques from rounding algorithms», Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM ..
↑ Gurmeet Singh, Manku; Das Sarma, Anish (2007), «Detecting near-duplicates for web crawling», Proceedings of the 16th international conference on World Wide Web. ACM, ..
↑ Das, Abhinandan S., et al. (2007), «Google news personalization: scalable online collaborative filtering», Proceedings of the 16th international conference on World Wide Web. ACM, .

Enlaces externos

Datos: Q11091745

[b97-1] Broder, Andrei Z. (1997), «On the resemblance and containment of documents», Compression and Complexity of Sequences: Proceedings, Positano, Amalfitan Coast, Salerno, Italy, June 11-13, 1997, IEEE, pp. 21-29, doi:10.1109/SEQUEN.1997.666900, archivado desde el original el 31 de enero de 2015, consultado el 19 de diciembre de 2014 ..

[bcfm-2] Broder, Andrei Z.; Charikar, Moses; Frieze, Alan M.; Mitzenmacher, Michael (1998), «Min-wise independent permutations», Proc. 30th ACM Symposium on Theory of Computing (STOC '98), New York, NY, USA: Association for Computing Machinery, pp. 327-336, doi:10.1145/276698.276781 ..

[3] Vassilvitskii, Sergey (2011), COMS 6998-12: Dealing with Massive Data (lecture notes, Columbia university) ..

[4] Matoušek, Jiří; Stojaković, Miloš (2003), «On restricted min-wise independence of permutations», Random Structures and Algorithms 23 (4): 397-408, doi:10.1002/rsa.10101 ..

[5] Saks, M.; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000), «Low discrepancy sets yield approximate min-wise independent permutation families», Information Processing Letters 73 (1–2): 29-32, doi:10.1016/S0020-0190(99)00163-5 ..

[6] Chum, Ondřej; Philbin, James; Isard, Michael; Zisserman, Andrew (2007), «Scalable near identical image and shot detection», Proceedings of the 6th ACM International Conference on Image and Cideo Retrieval (CIVR'07), doi:10.1145/1282280.1282359 .

[7] Chum, Ondřej; Philbin, James; Zisserman, Andrew (2008), «Near duplicate image detection: min-hash and tf-idf weighting», Proceedings of the British Machine Vision Conference 3, p. 4, archivado desde el original el 24 de febrero de 2021, consultado el 19 de diciembre de 2014 ..

[8] Cohen, E.; Datar, M.; Fujiwara, S.; Gionis, A.; Indyk, P.; Motwani, R.; Ullman, J. D.; Yang, C. (2001), «Finding interesting associations without support pruning», IEEE Transactions on Knowledge and Data Engineering 13 (1): 64-78, doi:10.1109/69.908981 ..

[9] Andoni, Alexandr; Indyk, Piotr (2008), «Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions», Communications of the ACM 51 (1): 117-122, doi:10.1145/1327452.1327494 ..

[10] Zadeh, Reza; Goel, Ashish (2012), Dimension Independent Similarity Computation, arXiv:1206.2082 ..

[11] Henzinger, Monika (2006), «Finding near-duplicate web pages: a large-scale evaluation of algorithms», Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval. ACM .

[12] Charikar, Moses S. (2002), «Similarity estimation techniques from rounding algorithms», Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM ..

[13] Gurmeet Singh, Manku; Das Sarma, Anish (2007), «Detecting near-duplicates for web crawling», Proceedings of the 16th international conference on World Wide Web. ACM, ..

[14] Das, Abhinandan S., et al. (2007), «Google news personalization: scalable online collaborative filtering», Proceedings of the 16th international conference on World Wide Web. ACM, .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]