MinHash

Técnica de minería de datos

En informática y minería de datos , MinHash (o el esquema de hash sensible a la localidad de permutaciones independientes min-wise ) es una técnica para estimar rápidamente cuán similares son dos conjuntos. El esquema fue inventado por Andrei Broder  (1997), ^[1] y utilizado inicialmente en el motor de búsqueda AltaVista para detectar páginas web duplicadas y eliminarlas de los resultados de búsqueda. ^[2] También se ha aplicado en problemas de agrupamiento a gran escala , como el agrupamiento de documentos por la similitud de sus conjuntos de palabras. ^[1]

Similitud de Jaccard y valores hash mínimos

El coeficiente de similitud de Jaccard es un indicador de uso común de la similitud entre dos conjuntos. Sea U un conjunto y A y B subconjuntos de U , entonces el índice de Jaccard se define como la relación entre el número de elementos de su intersección y el número de elementos de su unión :

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

Este valor es 0 cuando los dos conjuntos son disjuntos , 1 cuando son iguales y estrictamente entre 0 y 1 en caso contrario. Dos conjuntos son más similares (es decir, tienen relativamente más miembros en común) cuando su índice de Jaccard está más cerca de 1. El objetivo de MinHash es estimar J ( A , B ) rápidamente, sin calcular explícitamente la intersección y la unión.

Sea h una función hash que asigna los miembros de U a números enteros distintos, sea perm una permutación aleatoria de los elementos del conjunto U y, para cualquier subconjunto S de U, defina h _min ( S ) como el miembro mínimo de S con respecto a h ∘ perm —es decir, el miembro x de S con el valor mínimo de h ( perm ( x )) . (En los casos en los que se supone que la función hash utilizada tiene propiedades pseudoaleatorias, no se utilizaría la permutación aleatoria).

Ahora, aplicando h _min tanto a A como a B , y suponiendo que no hay colisiones hash, vemos que los valores son iguales ( h _min ( A ) = h _min ( B ) ) si y solo si entre todos los elementos de , el elemento con el valor hash mínimo se encuentra en la intersección . La probabilidad de que esto sea cierto es exactamente el índice de Jaccard, por lo tanto: ${\displaystyle A\cup B}$ ${\displaystyle A\cap B}$

Pr[ h _mín ( A ) = h _mín ( B ) ] = J ( A , B ),

Es decir, la probabilidad de que h _min ( A ) = h _min ( B ) sea verdadera es igual a la similitud J ( A , B ) , suponiendo que se extrae perm de una distribución uniforme. En otras palabras, si r es la variable aleatoria que es uno cuando h _min ( A ) = h _min ( B ) y cero en caso contrario, entonces r es un estimador insesgado de J ( A , B ) . r tiene una varianza demasiado alta para ser un estimador útil para la similitud de Jaccard por sí solo, porque siempre es cero o uno. La idea del esquema MinHash es reducir esta varianza promediando juntas varias variables construidas de la misma manera. ${\displaystyle r}$

Algoritmo

Variante con muchas funciones hash

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

Para estimar J ( A , B ) utilizando esta versión del esquema, sea y el número de funciones hash para las cuales h _min ( A ) = h _min ( B ) , y use y / k como la estimación. Esta estimación es el promedio de k diferentes variables aleatorias 0-1, cada una de las cuales es uno cuando h _min ( A ) = h _min ( B ) y cero en caso contrario, y cada una de las cuales es un estimador insesgado de J ( A , B ) . Por lo tanto, su promedio también es un estimador insesgado, y por desviación estándar para sumas de 0-1 variables aleatorias, su error esperado es O(1/ √ k ) . ^[3]

Por lo tanto, para cualquier constante ε > 0 existe una constante k = O(1/ε ² ) tal que el error esperado de la estimación es como máximo  ε . Por ejemplo, se requerirían 400 hashes para estimar J ( A , B ) con un error esperado menor o igual a 0,05.

Variante con una única función hash

Puede resultar computacionalmente costoso calcular múltiples funciones hash, pero una versión relacionada del esquema MinHash evita esta penalización al usar solo una única función hash y la usa para seleccionar múltiples valores de cada conjunto en lugar de seleccionar solo un único valor mínimo por función hash. Sea h una función hash y sea k un entero fijo. Si S es cualquier conjunto de k o más valores en el dominio de h , defina h _{( k )} ( S ) como el subconjunto de los k miembros de S que tienen los valores más pequeños de h . Este subconjunto h _{( k )} ( S ) se usa como una firma para el conjunto S , y la similitud de dos conjuntos cualesquiera se estima comparando sus firmas.

En concreto, sean A y B dos conjuntos cualesquiera. Entonces X = h _{( k )} ( h _{( k )} ( A ) ∪ h _{( k )} ( B )) = h _{( k )} ( A ∪ B ) es un conjunto de k elementos de A ∪ B , y si h es una función aleatoria entonces cualquier subconjunto de k elementos tiene la misma probabilidad de ser elegido; es decir, X es una muestra aleatoria simple de A ∪ B . El subconjunto Y = X ∩ h _{( k )} ( A ) ∩ h _{( k )} ( B ) es el conjunto de miembros de X que pertenecen a la intersección A ∩ B . Por lo 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 hash pueden llevar a un número menor de elementos muestreados debido a la posibilidad de que dos funciones hash diferentes puedan 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.

Según los límites de Chernoff estándar para muestreo sin reemplazo, este estimador tiene un error esperado O(1/ √ k ) , que coincide con el rendimiento del esquema de funciones hash múltiples.

Análisis del tiempo

El estimador | Y |/ k puede calcularse en tiempo O( k ) a partir de las dos firmas de los conjuntos dados, en cualquier variante del esquema. Por lo tanto, cuando ε y k son constantes, el tiempo para calcular la similitud estimada a partir de las firmas también es constante. La firma de cada conjunto puede calcularse en tiempo lineal sobre el tamaño del conjunto, por lo que cuando se necesitan estimar muchas similitudes por pares, este método puede llevar a un ahorro sustancial en el tiempo de ejecución 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 O( n k ) tiempo. La variante de un solo hash es generalmente más rápida, requiriendo O( n ) tiempo para mantener la cola de valores hash mínimos suponiendo que n >> k . ^[1]

Incorporando pesos

Se han desarrollado diversas técnicas para introducir pesos en el cálculo de MinHashes. La más simple la extiende a pesos enteros. ^[4] Extendemos nuestra función hash h para que acepte tanto un miembro del conjunto como un entero, luego generamos múltiples hashes para cada elemento, según su peso. Si el elemento i aparece n veces, generamos hashes . Ejecutamos el algoritmo original en este conjunto expandido de hashes. Al hacerlo, obtenemos el índice Jaccard ponderado como la probabilidad de colisión. ${\displaystyle h(i,1),h(i,2),\ldots ,h(i,n)}$

${\displaystyle J_{\mathcal {W}}(x,y)={\frac {\sum _{i}\min(x_{i},y_{i})}{\sum _{i}\max(x_{i},y_{i})}}}$

Se han desarrollado extensiones adicionales que logran esta probabilidad de colisión en pesos reales con un mejor tiempo de ejecución, una para datos densos, ^[5] y otra para datos dispersos. ^[6]

Otra familia de extensiones utiliza hashes distribuidos exponencialmente. Un hash uniformemente aleatorio entre 0 y 1 se puede convertir para que siga una distribución exponencial mediante inversión de CDF . Este método explota las muchas y hermosas propiedades del mínimo de un conjunto de variables exponenciales .

${\displaystyle H(x)={\underset {i}{\operatorname {arg\,min} }}{\frac {-\log(h(i))}{x_{i}}}}$

Esto da como probabilidad de colisión el índice de probabilidad de Jaccard ^[7]

${\displaystyle J_{\mathcal {P}}(x,y)=\sum _{x_{i}\neq 0 \atop y_{i}\neq 0}{\frac {1}{\sum _{j}\max \left({\frac {x_{j}}{x_{i}}},{\frac {y_{j}}{y_{i}}}\right)}}}$

Permutaciones independientes min-por-min

Para 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 a comparar. Pero debido a que hay n ! permutaciones diferentes, se requerirían Ω( n log n ) bits solo para especificar una permutación verdaderamente aleatoria, un número inviablemente grande incluso para valores moderados de n . Debido a este hecho, por analogía con la teoría del hash universal , ha habido un trabajo significativo para encontrar una familia de permutaciones que sea "min-wise independiente", lo que significa que para cualquier subconjunto del dominio, cualquier elemento tiene la misma probabilidad de ser el mínimo. Se ha establecido que una familia de permutaciones independiente min-wise debe incluir al menos

${\displaystyle \operatorname {lcm} (1,2,\cdots ,n)\geq e^{n-o(n)}}$

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

Funciones hash independientes min-wise prácticas

Debido a la impracticabilidad antes mencionada, se han introducido dos nociones variantes de independencia mínima: familias de permutaciones independientes mínimas restringidas y familias independientes mínimas aproximadas. La independencia mínima restringida es la propiedad de independencia mínima restringida a ciertos conjuntos de cardinalidad como máximo k . ^[8] La independencia mínima aproximada tiene como máximo una probabilidad fija ε de variar con respecto a la independencia completa. ^[9]

En 1999, Piotr Indyk demostró ^[10] que cualquier familia de funciones hash independientes en el orden de k es también aproximadamente independiente en el orden de min para valores suficientemente grandes. En particular, existen constantes tales que si , entonces ${\displaystyle k}$ ${\displaystyle c,c'>0}$ ${\displaystyle k\geq c\log {\tfrac {1}{\epsilon }}}$

${\displaystyle \Pr _{h\in {\mathcal {H}}}[h(x)<\min h(X)]={\frac {1}{|X|+1}}(1\pm \epsilon ),}$

para todos los conjuntos y . (Nota: aquí significa que la probabilidad es, como máximo, un factor demasiado grande y, como máximo, demasiado pequeña). ${\displaystyle |X|\leq \epsilon nc'}$ ${\displaystyle x\not \in X}$ ${\displaystyle (1\pm \epsilon )}$ ${\displaystyle 1+\epsilon }$ ${\displaystyle 1-\epsilon }$

Esta garantía es, entre otras cosas, suficiente para dar el límite de Jaccard requerido por el algoritmo MinHash. Es decir, si y son conjuntos, entonces ${\displaystyle A}$ ${\displaystyle B}$

${\displaystyle \Pr _{h\in {\mathcal {H}}}[\min h(A)=\min h(B)]={\frac {|A\cap B|}{|A\cup B|}}\pm \epsilon .}$

Dado que las funciones hash independientes k-wise se pueden especificar usando solo bits, este enfoque es mucho más práctico que usar permutaciones completamente independientes min-wise. ${\displaystyle k\log n}$

Otra familia práctica de funciones hash que brindan una independencia aproximada en términos mínimos es el hash de tabulación .

Aplicaciones

Las aplicaciones originales de MinHash implicaban la agrupación y eliminación de duplicados casi totales entre documentos web, representados como conjuntos de palabras que aparecían en esos documentos. ^{[1] [2] [11]} También se han utilizado técnicas similares para la agrupación y eliminación de duplicados casi totales para otros tipos de datos, como imágenes: en el caso de los datos de imágenes, una imagen puede representarse como un conjunto de subimágenes más pequeñas recortadas de ella, o como conjuntos de descripciones de características de imágenes más complejas. ^[12]

En minería de datos , Cohen et al. (2001) utilizan MinHash como una herramienta para el aprendizaje de reglas de asociación . Dada una base de datos en la que cada entrada tiene múltiples atributos (vista como una matriz 0-1 con una fila por entrada de base de datos y una columna por atributo), utilizan aproximaciones basadas en MinHash al índice de Jaccard para identificar pares candidatos de atributos que coocurren con frecuencia y luego calculan el valor exacto del índice solo para esos pares para determinar aquellos cuyas frecuencias de coocurrencia están por debajo de un umbral estricto dado. ^[13]

El algoritmo MinHash ha sido adaptado para la bioinformática, donde el problema de comparar secuencias genómicas tiene un fundamento teórico similar al de comparar documentos en la web. Las herramientas basadas en MinHash ^{[14] [15]} permiten una comparación rápida de datos de secuenciación del genoma completo con genomas de referencia (alrededor de 3 minutos para comparar un genoma con los 90000 genomas de referencia en RefSeq ), y son adecuadas para la especiación y tal vez un grado limitado de subtipificación microbiana. También existen aplicaciones para la metagenómica ^[14] y el uso de algoritmos derivados de MinHash para la alineación y el ensamblaje del genoma. ^[16] Se pueden generar valores precisos de identidad de nucleótido promedio (ANI) de manera muy eficiente con algoritmos basados ​​en MinHash. ^[17]

Otros usos

El esquema MinHash puede verse como un ejemplo de hash sensible a la localidad , una colección de técnicas para usar funciones hash para mapear grandes conjuntos de objetos a valores hash más pequeños de tal manera que, cuando dos objetos tienen una pequeña distancia entre sí, sus valores hash probablemente sean los mismos. En este caso, la firma de un conjunto puede verse como su valor hash. Existen otras técnicas de hash sensibles a la localidad para la distancia de Hamming entre conjuntos y la distancia de coseno entre vectores ; el hash sensible a la localidad tiene aplicaciones importantes en algoritmos de búsqueda del vecino más cercano . ^[18] Para sistemas distribuidos grandes, y en particular MapReduce , existen versiones modificadas de MinHash para ayudar a calcular similitudes sin dependencia de la dimensión del punto. ^[19]

Evaluación y puntos de referencia

En 2006, Google realizó una evaluación a gran escala ^[20] para comparar el rendimiento de los algoritmos Minhash y SimHash ^[21] . En 2007, Google informó que utilizaba Simhash para la detección de duplicados en el rastreo web ^[22] y que utilizaba Minhash y LSH para la personalización de Google News . ^[23]

Véase también

• Filtro Bloom  : estructura de datos para la pertenencia aproximada a un conjunto
• Esquema de conteo mínimo  : estructura de datos probabilística en informática
• tejas w

Referencias

1. Broder, Andrei Z. (1998), "Sobre la semejanza y la contención de los documentos", Proceedings. Compression and Complexity of SEQUENCES 1997 (Cat. No.97TB100171) (PDF) , IEEE , págs. 21–29, CiteSeerX  10.1.1.24.779 , doi :10.1109/SEQUEN.1997.666900, ISBN 978-0-8186-8132-5, S2CID  11748509, archivado desde el original (PDF) el 31 de enero de 2015 , consultado el 18 de enero de 2014.
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) , Nueva York, NY, EE. UU.: Association for Computing Machinery , págs. 327–336, CiteSeerX 10.1.1.409.9220 , doi :10.1145/276698.276781, ISBN  978-0897919623, Número de identificación del sujeto  465847.
3. Vassilvitskii, Sergey (2011), COMS 6998-12: Cómo manejar datos masivos (notas de clase, Universidad de Columbia) (PDF) , archivado desde el original (PDF) el 24 de octubre de 2018.
4. Chum, Ondrej; Philbin, James; Zisserman, Andrew (2008), "Detección de imágenes casi duplicadas: ponderación min-Hash y tf-idf". (PDF) , BMVC , 810 : 812–815
5. Shrivastava, Anshumali (2016), "Hash minwise ponderado exacto en tiempo constante", arXiv : 1602.08393 [cs.DS]
6. Ioffe, Sergey (2010). "Muestreo consistente mejorado, Minhash ponderado y esbozo L1". Conferencia internacional IEEE sobre minería de datos de 2010 (PDF) . pp. 246–255. CiteSeerX 10.1.1.227.9749 . doi :10.1109/ICDM.2010.80. ISBN .  978-1-4244-9131-5.S2CID 9970906  .
7. Moulton, Ryan; Jiang, Yunjiang (2018), "Muestreo de consistencia máxima y el índice Jaccard de distribuciones de probabilidad", 2018 IEEE International Conference on Data Mining (ICDM) , págs. 347–356, arXiv : 1809.04052 , doi :10.1109/ICDM.2018.00050, ISBN 978-1-5386-9159-5, Número de identificación del sujeto  49746072
8. Matoušek, Jiří ; Stojaković, Miloš (2003), "Sobre la independencia restringida de permutaciones en términos mínimos", Algoritmos y estructuras aleatorias , 23 (4): 397–408, CiteSeerX 10.1.1.400.6757 , doi :10.1002/rsa.10101, S2CID  1483449 .
9. Saks, M. ; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000), "Los conjuntos de baja discrepancia producen familias de permutación independientes aproximadas en orden min", Information Processing Letters , 73 (1–2): 29–32, CiteSeerX 10.1.1.20.8264 , doi :10.1016/S0020-0190(99)00163-5 .
10. Indyk, Piotr. "Una pequeña familia de funciones hash independientes, aproximadamente en orden min." Journal of Algorithms 38.1 (2001): 84-90.
11. Manasse, Mark (2012). Sobre la determinación eficiente de los vecinos más cercanos: herraduras, granadas de mano, búsquedas en la Web y otras situaciones en las que lo cercano es lo suficientemente cercano . Morgan & Claypool. pág. 72. ISBN 9781608450886.
12. Chum, Ondřej; Philbin, James; Isard, Michael; Zisserman, Andrew (2007), "Detección escalable de imágenes y disparos casi idénticos", Actas de la 6.ª Conferencia internacional de la ACM sobre recuperación de imágenes y vídeos (CIVR'07) , pp. 549–556, doi :10.1145/1282280.1282359, ISBN 9781595937339, Número de identificación del sujeto  3330908; Chum, Ondřej; Philbin, James; Zisserman, Andrew (2008), "Detección de imágenes casi duplicadas: ponderación min-hash y tf-idf", Actas de la Conferencia Británica de Visión Artificial (PDF) , vol. 3, pág. 4.
13. Cohen, E. ; Datar, M. ; Fujiwara, S. ; Gionis, A. ; Indyk, P. ; Motwani, R. ; Ullman, JD ; Yang, C. (2001), "Encontrar asociaciones interesantes sin poda de soporte", IEEE Transactions on Knowledge and Data Engineering , 13 (1): 64–78, CiteSeerX 10.1.1.192.7385 , doi :10.1109/69.908981 .
14. Ondov, Brian D.; Treangen, Todd J.; Melsted, Páll; Mallonee, Adam B.; Bergman, Nicholas H.; Koren, Sergey; Phillippy, Adam M. (20 de junio de 2016). "Mash: estimación rápida de la distancia del genoma y metagenoma utilizando MinHash". Biología del genoma . 17 (1): 132. doi : 10.1186/s13059-016-0997-x . ISSN  1474-760X. PMC 4915045 . PMID  27323842. 
15. "Bienvenido a Sourmash! — Documentación de Sourmash 1.0". sourmash.readthedocs.io . Consultado el 13 de noviembre de 2017 .
16. Berlín, Konstantin; Koren, Sergey; Chin, Chen-Shan; Drake, James P; Landolin, Jane M; Phillippy, Adam M (25 de mayo de 2015). "Ensamblaje de genomas grandes con secuenciación de moléculas individuales y hash sensible a la localidad". Nature Biotechnology . 33 (6): 623–630. doi :10.1038/nbt.3238. ISSN  1546-1696. PMID  26006009. S2CID  17246729.
17. Jain, Chirag; Rodriguez-R, Luis M.; Phillippy, Adam M.; Konstantinidis, Konstantinos T.; Aluru, Srinivas (diciembre de 2018). "El análisis ANI de alto rendimiento de 90K genomas procariotas revela límites claros entre especies". Nature Communications . 9 (1): 5114. Bibcode :2018NatCo...9.5114J. doi : 10.1038/s41467-018-07641-9 . PMC 6269478 . PMID  30504855. 
18. Andoni, Alexandr; Indyk, Piotr (2008), "Algoritmos de hash casi óptimos para el vecino más cercano aproximado en dimensiones altas", Communications of the ACM , 51 (1): 117–122, CiteSeerX 10.1.1.226.6905 , doi :10.1145/1327452.1327494, S2CID  6468963 .
19. Zadeh, Reza; Goel, Ashish (2012), "Cálculo de similitud independiente de la dimensión", arXiv : 1206.2082 [cs.DS].
20. Henzinger, Monika (2006), "Encontrar páginas web casi duplicadas: una evaluación a gran escala de algoritmos", Actas de la 29.ª Conferencia anual internacional ACM SIGIR sobre investigación y desarrollo en recuperación de información , pp. 284, doi :10.1145/1148170.1148222, ISBN 978-1595933690, Número de identificación del sujeto  207160068.
21. Charikar, Moses S. (2002), "Técnicas de estimación de similitud a partir de algoritmos de redondeo", Actas del 34º Simposio Anual de la ACM sobre Teoría de la Computación , pág. 380, doi :10.1145/509907.509965, ISBN 978-1581134957, Número de identificación del sujeto  4229473.
22. Gurmeet Singh, Manku; Jain, Arvind; Das Sarma, Anish (2007), "Detección de duplicados cercanos para el rastreo web", Actas de la 16.ª Conferencia Internacional sobre la World Wide Web (PDF) , pág. 141, doi : 10.1145/1242572.1242592, ISBN 9781595936547, S2CID1414324 ​.
23. Das, Abhinandan S.; Datar, Mayur; Garg, Ashutosh; Rajaram, Shyam; et al. (2007), "Personalización de noticias de Google: filtrado colaborativo en línea escalable", Actas de la 16.ª Conferencia Internacional sobre la World Wide Web , pág. 271, doi :10.1145/1242572.1242610, ISBN 9781595936547, Número de identificación del sujeto  207163129.