Hispanopedia Wiki
Articulo de referencia

MinHash

En informática y minería de datos , MinHash (o el esquema de hash sensible a la localidad de permutaciones independientes mínimas ) es una técnica para estimar rápidamente la si...

Hispanopedia WikiContenido en espanolLectura gratuita

En informática y minería de datos , MinHash (o el esquema de hash sensible a la localidad de permutaciones independientes mínimas ) es una técnica para estimar rápidamente la similitud entre dos conjuntos. El esquema fue publicado por Andrei Broder en una conferencia de 1997 [ 1 ] y se utilizó 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 según 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 comúnmente utilizado para medir 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 razón entre el número de elementos de su intersección y el número de elementos de su unión :

J(A,B)=|A∩B||A∪B|.{\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, en caso contrario, se encuentra estrictamente entre 0 y 1. Dos conjuntos son más similares (es decir, tienen relativamente más elementos en común) cuando su índice de Jaccard se acerca a 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 a los miembros de U enteros distintos, sea perm una permutación aleatoria de los elementos del conjunto U , y para cualquier subconjunto S de U definamos 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 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 de hash, vemos que los valores son iguales ( h min ( A ) = h min ( B ) ) si y solo si entre todos los elementos deA∪B{\displaystyle A\cup B}, el elemento con el valor hash mínimo se encuentra en la intersecciónA∩B{\displaystyle A\cap B}La probabilidad de que esto sea cierto es exactamente el índice de Jaccard, por lo tanto:

Pr[hmin(A)=hmin(B)]=J(A,B),{\displaystyle {\text{Pr}}[h_{\text{min}}(A)=h_{\text{min}}(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í sola, porquer{\displaystyle r}siempre es cero o uno. La idea del esquema MinHash es reducir esta varianza promediando varias variables construidas de la misma manera.

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 mediante los k valores 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 use y / k como estimación. Esta estimación es el promedio de k variables aleatorias 0-1 diferentes, 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 variables aleatorias 0-1, su error esperado es O(1/ √ k ) . [ 3 ]

Por lo tanto, para cualquier constante ε > 0 existe una constante k = O(1/ ε 2 ) 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 una sola función hash y utilizarla 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 k un entero fijo. Si S es cualquier conjunto de k o más valores en el dominio de h , definimos 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 utiliza como firma para el conjunto S , y la similitud de dos conjuntos cualesquiera se estima comparando sus firmas.

Específicamente, 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 generado por múltiples funciones hash radica en que X siempre tiene exactamente k elementos, mientras que el uso de múltiples funciones hash puede resultar en un menor número de elementos muestreados debido a la posibilidad de que dos funciones hash diferentes tengan los mismos mínimos. Sin embargo, cuando k es pequeño en relación con el tamaño de los conjuntos, esta diferencia es insignificante.

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

Análisis del tiempo

El estimador | Y | / k se puede calcular en tiempo O( k ) a partir de las dos firmas de los conjuntos dados, en cualquiera de las variantes 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 se puede calcular en tiempo lineal con respecto al tamaño del conjunto, por lo que cuando se necesitan estimar muchas similitudes por pares, este método puede generar un ahorro sustancial en el tiempo de ejecución en comparación con realizar una comparación completa de los miembros de cada conjunto. Específicamente, para un tamaño de conjunto n, la variante de múltiples hashes toma un tiempo O( n k ) . La variante de un solo hash es generalmente más rápida, requiriendo un tiempo O( n ) 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 sencilla lo extiende a pesos enteros. [ 4 ] Extendemos nuestra función hash h para que acepte tanto un miembro del conjunto como un entero, y luego generamos múltiples hashes para cada elemento, según su peso. Si el elemento i aparece n veces, generamos hashes.h(i,1),h(i,2),…,h(i,norte){\displaystyle h(i,1),h(i,2),\ldots ,h(i,n)}Ejecute el algoritmo original sobre este conjunto ampliado de hashes. Al hacerlo, se obtiene el índice de Jaccard ponderado como probabilidad de colisión.

JW(incógnita,y)=∑imin(incógnitai,yi)∑imáximo(incógnitai,yi){\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 funciones hash con distribución exponencial. Una función hash aleatoria uniforme entre 0 y 1 puede convertirse para que siga una distribución exponencial mediante la inversión de la función de distribución acumulada (CDF) . Este método aprovecha las numerosas y excelentes propiedades del mínimo de un conjunto de variables exponenciales .

H(incógnita)=argramometroinortei−registro⁡(h(i))incógnitai{\displaystyle H(x)={\underset {i}{\operatorname {arg\,min} }}{\frac {-\log(h(i))}{x_{i}}}}

Esto produce como su probabilidad de colisión el índice de probabilidad de Jaccard [ 7 ]

JPAG(incógnita,y)=∑incógnitai≠0yi≠01∑jmáximo(incógnitajincógnitai,yjyi){\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 mínimas

Para implementar el esquema MinHash descrito 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 hashing universal , se ha trabajado significativamente en encontrar una familia de permutaciones que sea "independiente en cuanto al mínimo", 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 en cuanto al mínimo debe incluir al menos

lcm⁡(1,2,⋯,norte)≥minorte−o(norte){\displaystyle \operatorname {lcm} (1,2,\cdots ,n)\geq e^{no(n)}}

diferentes permutaciones, y por lo tanto que necesita Ω ( n ) bits para especificar una sola permutación, todavía inviablemente grande. [ 2 ]

Funciones hash independientes prácticas de mínimo a mínimo

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

En 1999, Piotr Indyk demostró [ 10 ] que cualquier familia de funciones hash k-independiente es también aproximadamente min-independiente parak{\displaystyle k}lo suficientemente grande. En particular, hay constantesdo,do′>0{\displaystyle c,c'>0}de tal manera que sik≥doregistro⁡1ϵ{\displaystyle k\geq c\log {\tfrac {1}{\epsilon }}}, entonces

Prh∈H[h(incógnita)<minh(incógnita)]=1|incógnita|+1(1±ϵ),{\displaystyle \Pr _{h\in {\mathcal {H}}}[h(x)<\min h(X)]={\frac {1}{|X|+1}}(1\pm \epsilon ),}

para todos los conjuntos|incógnita|≤ϵnortedo′{\displaystyle |X|\leq \epsilon nc'}yincógnita∉incógnita{\displaystyle x\not \in X}. (Nota, aquí)(1±ϵ){\displaystyle (1\pm \epsilon )}significa que la probabilidad es como máximo un factor1+ϵ{\displaystyle 1+\epsilon }demasiado grande y como máximo1−ϵ{\displaystyle 1-\epsilon }demasiado pequeño.)

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

Prh∈H[minh(A)=minh(B)]=|A∩B||A∪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-ésimas se pueden especificar utilizando solokregistro⁡norte{\displaystyle k\log n}bits, este enfoque es mucho más práctico que usar permutaciones completamente independientes min-wise.

Otra familia práctica de funciones hash que proporciona una independencia mínima aproximada es el hash por tabulación .

Aplicaciones

Las aplicaciones originales de MinHash implicaban la agrupación y eliminación de duplicados cercanos entre documentos web, representados como conjuntos de las palabras que aparecen en esos documentos. [ 1 ] [ 2 ] [ 11 ] Técnicas similares también se han utilizado para la agrupación y eliminación de duplicados cercanos para otros tipos de datos, como imágenes: en el caso de datos de imagen, 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 imagen más complejas. [ 12 ]

En minería de datos , Cohen et al. (2001) utilizan MinHash como 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 binaria con una fila por entrada de la 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 se ha adaptado para la bioinformática , donde el problema de comparar secuencias genómicas tiene una base teórica similar a la de comparar documentos en la web. Las herramientas basadas en MinHash [ 14 ] [ 15 ] permiten una comparación rápida de datos de secuenciación de genomas completos 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 quizás 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 de genomas. [ 16 ] Los valores precisos de identidad nucleotídica promedio (ANI) se pueden generar de manera muy eficiente con algoritmos basados ​​en MinHash. [ 17 ]

Otros usos

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

Evaluación y puntos de referencia

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

Véase también

Referencias

  1. 1 2 3 4 Broder, Andrei Z. (1998), "Sobre la semejanza y la contención de documentos", Actas. Compresión y complejidad de SECUENCIAS 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 del original (PDF) el 31-01-2015 , recuperado el 18-01-2014 .
  2. 1 2 3 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 , pp. 327– 336, CiteSeerX 10.1.1.409.9220 , doi : 10.1145/276698.276781 , ISBN   978-0897919623, S2CID 465847 .
  3. ↑ Vassilvitskii, Sergey (2011), COMS 6998-12: Manejo de datos masivos (apuntes de clase, Universidad de Columbia) (PDF) , archivado del original (PDF) el 24/10/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), "Exact weighted minwise hashing in constant time", arXiv : 1602.08393 [ cs.DS ]
  6. ↑ Ioffe, Sergey (2010). "Muestreo consistente mejorado, Minhash ponderado y esbozo L1". Conferencia Internacional IEEE de Minería de Datos de 2010 (PDF) . págs. 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 máximamente consistente y el índice de Jaccard de distribuciones de probabilidad", 2018 IEEE International Conference on Data Mining (ICDM) , pp. 347–356 , arXiv : 1809.04052 , doi : 10.1109/ICDM.2018.00050 , ISBN  978-1-5386-9159-5, S2CID 49746072 
  8. ↑ Matoušek, Jiří ; Stojaković, Miloš (2003), "Sobre la independencia restringida de permutaciones en términos mínimos", Estructuras y algoritmos aleatorios , 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 generan familias de permutaciones independientes mínimas aproximadas", 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 aproximadamente independientes en 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úsqueda web y otras situaciones en las que estar cerca es suficiente . 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 tomas casi idénticas", Actas de la 6.ª Conferencia Internacional ACM sobre Recuperación de Imágenes y Vídeo (CIVR'07) , págs. 549–556 , doi : 10.1145/1282280.1282359 , ISBN  9781595937339, S2CID 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 por Computadora (PDF) , vol. 3, pág. 4  .
  13. ↑ Cohen, E .; Datar, M.; Fujiwara, S.; Gionis, A.; Indyk, P .; Motwani, R.; Ullman , JD ; Yang, C. (2001), "Finding interesting associations without support pruning", IEEE Transactions on Knowledge and Data Engineering , 13 (1): 64–78 , Bibcode : 2001IDSO...13...64C , CiteSeerX 10.1.1.192.7385 , doi : 10.1109/69.908981 .
  14. 1 2 Ondov, Brian D.; Treangen, Todd J.; Melsted, Páll; Mallonee, Adam B.; Bergman, Nicholas H.; Koren, Sergey; Phillippy, Adam M. (2016-06-20). "Mash: estimación rápida de distancias de genoma y metagenoma usando MinHash" . Genome Biology . 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. ↑ Berlin, Konstantin; Koren, Sergey; Chin, Chen-Shan; Drake, James P; Landolin, Jane M; Phillippy, Adam M (2015-05-25). "Ensamblaje de genomas grandes con secuenciación de molécula única y hash sensible a la localidad". Nature Biotechnology . 33 (6): 623– 630. Bibcode : 2015NatBi..33..623B . 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). "Análisis ANI de alto rendimiento de 90.000 genomas procariotas revela límites de especies claros" . 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 altas dimensiones", 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), "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 , pp. 284 , doi : 10.1145/1148170.1148222 , ISBN  978-1595933690, S2CID 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ágs. 380–388 , doi : 10.1145/509907.509965 , ISBN  978-1581134957, S2CID 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, S2CID 1414324 .
  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, S2CID 207163129 .