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 qué tan 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 agrupación a gran escala , como la agrupación 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 comúnmente utilizado 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 :

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 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 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 \circ 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á la permutación aleatoria).

Ahora, aplicando $h min$ tanto a $A$ como $a B$ , y suponiendo que no haya 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 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: $A\taza B$ $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 obtenga $permanente$ 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 de la similitud de Jaccard por sí solo, porque siempre es cero o uno. La idea del esquema MinHash es reducir esta varianza promediando varias variables construidas de la misma manera. $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$ 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$ 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/ \sqrt 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 necesitarí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 ser computacionalmente costoso calcular múltiples funciones hash, pero una versión relacionada del esquema MinHash evita esta penalización al usar solo una función hash y la usa para seleccionar múltiples valores de cada conjunto en lugar de seleccionar solo un valor mínimo por función hash. Sea $h$ una función hash y sea $k$ un número 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 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) \cup h (k) (B)) = h (k) (A \cup B)$ es un conjunto de k elementos de $A \cup B$ , y si h es un función aleatoria, entonces es igualmente probable que se elija cualquier subconjunto de k elementos; es decir, $X$ es una muestra aleatoria simple de $A \cup B$ . El subconjunto $Y = X \cap h (k) (A) \cap h (k) (B)$ es el conjunto de miembros de $X$ que pertenecen a la intersección $A \cap 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 conducir 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 estándar de Chernoff para el muestreo sin reemplazo, este estimador ha esperado un error $O(1/ \sqrt k)$ , igualando el rendimiento del esquema de función hash múltiple.

Análisis de tiempo

El estimador $| Y |/ k$ se puede calcular en el 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 se puede calcular en tiempo lineal en el tamaño del conjunto, por lo que cuando es necesario estimar muchas similitudes por pares, este método puede generar 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 un tamaño de conjunto $n,$ la variante de muchos hash requiere $O(n k)$ tiempo. La variante de hash único es generalmente más rápida y requiere $O(n)$ tiempo para mantener la cola de valores de hash mínimos suponiendo $n >> k$ . ^[1]

Incorporando pesas

Se han desarrollado una variedad de técnicas para introducir pesos en el cálculo de MinHashes. El más simple lo extiende a pesos enteros. ^[4] Amplíe nuestra función hash $h$ para aceptar tanto un miembro del conjunto como un número entero, luego genere múltiples hashes para cada elemento, según su peso. Si el elemento $i$ aparece $n$ veces, genera hashes . Ejecute el algoritmo original en este conjunto ampliado de hashes. Al hacerlo, se obtiene el índice Jaccard ponderado como probabilidad de colisión. $h(i,1),h(i,2),\ldots,h(i,n)$

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

Se han desarrollado más extensiones que logran esta probabilidad de colisión en pesos reales con 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 CDF . Este método explota las hermosas propiedades del mínimo de un conjunto de variables exponenciales .

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

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

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 como se describe 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 porque hay $n!$ diferentes permutaciones, se requerirían $Ω(n log n)$ bits solo para especificar una permutación verdaderamente aleatoria, un número inviable incluso para valores moderados de $n$ . Debido a este hecho, por analogía con la teoría del hash universal , se ha realizado un trabajo significativo para encontrar una familia de permutaciones que sea "min-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 independientes mínimas debe incluir al menos

\operatorname {lcm} (1,2,\cdots,n)\geq e^{no(n)}

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

Prácticas funciones hash independientes mínimas

Debido a la impracticabilidad anterior, 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 desde la independencia total. ^[9]

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

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

para todos los conjuntos y . (Tenga en cuenta que aquí significa que la probabilidad es, como máximo, un factor demasiado grande y, como máximo, demasiado pequeño). $|X|\leq \epsilon nc'$ $x\no \en X$ $(1\pm \epsilon )$ $1+\epsilon$ $1-\epsilon$

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

\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 de k se pueden especificar usando solo bits, este enfoque es mucho más práctico que usar permutaciones completamente independientes de min. $k\log n$

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

Aplicaciones

Las aplicaciones originales de MinHash implicaban agrupar y eliminar casi duplicados entre documentos web, representados como conjuntos de palabras que aparecen en esos documentos. ^[1]^[2]^[11] También se han utilizado técnicas similares para agrupar y eliminar casi duplicados para otros tipos de datos, como imágenes: en el caso de datos de imágenes, una imagen se puede representar como un conjunto de subimágenes más pequeñas. recortadas de él, 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 0-1 con una fila por entrada de la base de datos y una columna por atributo), utilizan aproximaciones basadas en MinHash al índice Jaccard para identificar pares candidatos de atributos que frecuentemente coinciden. ocurren, y luego calcular el valor exacto del índice solo para aquellos pares para determinar aquellos cuyas frecuencias de co-ocurrencia están por debajo de un umbral estricto determinado. ^[13]

El algoritmo MinHash se ha adaptado a 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 los datos de secuenciación del genoma completo con los 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 microbios. subtipificación. 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 promedio precisos de identidad de nucleótidos (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 asignar 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í , es probable que sus valores hash 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 del coseno entre vectores ; El hash sensible a la localidad tiene aplicaciones importantes en los algoritmos de búsqueda de vecinos más cercanos . ^[18] Para grandes sistemas distribuidos, 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

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ó que utilizaba Simhash para la detección de duplicados en el rastreo web ^[22] y utilizaba Minhash y LSH para la personalización de Google News . ^[23]

Ver también

Filtro Bloom : estructura de datos para la membresía aproximada del conjunto
Bosquejo de conteo mínimo : estructura de datos probabilística en informática
w-tejas

Referencias

^ abcd Broder, Andrei Z. (1998), "Sobre la semejanza y la contención de los documentos", Actas. Compresión y complejidad de 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.
^ abc Broder, Andrei Z .; Charikar, Moisés; Friso, Alan M .; Mitzenmacher, Michael (1998), "Permutaciones independientes mínimas", Proc. 30.º Simposio ACM sobre Teoría de la Computación (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, S2CID 465847.
^ Vassilvitskii, Sergey (2011), COMS 6998-12: Manejo de datos masivos (notas de conferencias, Universidad de Columbia) (PDF) , archivado desde el original (PDF) el 24 de octubre de 2018.
^ Amigo, 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
^ Shrivastava, Anshumali (2016), "Hash minwise ponderado exacto en tiempo constante", arXiv : 1602.08393 [cs.DS]
^ Ioffe, Sergey (2010). "Muestreo consistente mejorado, Minhash ponderado y bocetos L1". Conferencia internacional IEEE 2010 sobre minería de datos (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.
^ Moulton, Ryan; Jiang, Yunjiang (2018), "Muestreo máximamente consistente y el índice Jaccard de distribuciones de probabilidad", Conferencia internacional IEEE sobre minería de datos (ICDM) de 2018 , págs. 347–356, arXiv : 1809.04052 , doi : 10.1109/ICDM.2018.00050, ISBN 978-1-5386-9159-5, S2CID 49746072
^ 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 .
^ Saks, M .; Srinivasan, A.; Zhou, S.; Zuckerman, D. (2000), "Los conjuntos de baja discrepancia producen familias de permutaciones independientes aproximadas en términos mínimos", Information Processing Letters , 73 (1–2): 29–32, CiteSeerX 10.1.1.20.8264 , doi :10.1016/S0020- 0190(99)00163-5 .
^ Indyk, Piotr. "Una pequeña familia independiente de funciones hash aproximadamente mínimas". Revista de Algoritmos 38.1 (2001): 84-90.
^ Manasse, Mark (2012). Sobre la determinación eficiente de los vecinos más cercanos: herraduras, granadas de mano, búsqueda en la web y otras situaciones en las que estar cerca es lo suficientemente cerca . Morgan y Claypool. pag. 72.ISBN 9781608450886.
^ Amigo, Ondřej; Philbin, James; Isard, Michael; Zisserman, Andrew (2007), "Detección de disparos e imágenes casi idénticas escalables", Actas de la sexta conferencia internacional ACM sobre recuperación de imágenes y archivos digitales (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 Artificial (PDF) , vol. 3, pág. 4.
^ 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 .
^ ab Ondov, Brian D.; Treangen, Todd J.; Derretido, Páll; Mallonee, Adam B.; Bergman, Nicolás 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.
^ "¡Bienvenido a sourmash! - documentación de sourmash 1.0". sourmash.readthedocs.io . Consultado el 13 de noviembre de 2017 .
^ Berlín, Konstantin; Koren, Sergey; Chin, Chen-Shan; Drake, James P; Landolín, Jane M; Phillippy, Adam M (25 de mayo de 2015). "Ensamblaje de genomas grandes con secuenciación de una sola molécula y hash sensible a la localidad". Biotecnología de la Naturaleza . 33 (6): 623–630. doi :10.1038/nbt.3238. ISSN 1546-1696. PMID 26006009. S2CID 17246729.
^ Jainista, Chirag; Rodríguez-R, Luis M.; Phillippy, Adam M.; Konstantinidis, Konstantinos T.; Aluru, Srinivas (diciembre de 2018). "El análisis ANI de alto rendimiento de 90.000 genomas procarióticos revela límites claros entre especies". Comunicaciones de la naturaleza . 9 (1): 5114. Código bibliográfico : 2018NatCo...9.5114J. doi : 10.1038/s41467-018-07641-9 . PMC 6269478 . PMID 30504855.
^ Andoni, Alejandro; Indyk, Piotr (2008), "Algoritmos de hash casi óptimos para el vecino más cercano aproximado en dimensiones altas", Comunicaciones del ACM , 51 (1): 117–122, CiteSeerX 10.1.1.226.6905 , doi :10.1145/1327452.1327494, S2CID 6468963 .
^ Zadeh, Reza; Goel, Ashish (2012), "Cálculo de similitud independiente de dimensiones", arXiv : 1206.2082 [cs.DS].
^ Henzinger, Monika (2006), "Encontrar páginas web casi duplicadas: una evaluación de algoritmos a gran escala", Actas de la 29ª Conferencia Internacional Anual ACM SIGIR sobre Investigación y Desarrollo en Recuperación de Información , págs.284, doi :10.1145/ 1148170.1148222, ISBN 978-1595933690, S2CID 207160068.
^ Charikar, Moses S. (2002), "Técnicas de estimación de similitud a partir de algoritmos de redondeo", Actas del 34º Simposio anual ACM sobre teoría de la computación , p. 380, doi :10.1145/509907.509965, ISBN 978-1581134957, S2CID 4229473.
^ Gurmeet Singh, Manku; Jainista, Arvind; Das Sarma, Anish (2007), "Detección de casi duplicados para el rastreo web", Actas de la 16ª Conferencia Internacional sobre la World Wide Web (PDF) , p. 141, doi :10.1145/1242572.1242592, ISBN 9781595936547, S2CID 1414324.
^ 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. 271, doi :10.1145/1242572.1242610, ISBN 9781595936547, S2CID 207163129.