En informática y minería de datos , MinHash (o el esquema de hash sensible a la localidad de permutaciones independientes en sentido mínimo ) es una técnica para estimar rápidamente qué tan similares son dos conjuntos. El esquema fue inventado por Andrei Broder ( 1997 ), [1] y se usó inicialmente en el motor de búsqueda de 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 mínimos de hash
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 :
Este valor es 0 cuando los dos conjuntos están separados , 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.
Deje que h sea un función hash que mapea los miembros de U a números enteros distintos, deje perm ser un azar permutación de los elementos del conjunto U , y para cualquier conjunto S definen h min ( S ) para ser el miembro mínima de S con respecto a h ∘ perm , es decir, los miembros de 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 asumiendo 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:
- Pr [ h min ( A ) = h 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 la permanente a partir 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, porquesiempre es cero o uno. La idea del esquema MinHash es reducir esta 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 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 una cuando h min ( A ) = h min ( B ) y cero en caso contrario, y cada una 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 hay 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 .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 usando 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 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 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 ∪ B . El subconjunto Y = X ∩ h ( k ) ( A ) ∩ h ( k ) ( B ) es el conjunto de los 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 conducir a un número menor 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 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 tiene un error esperado O (1 / √ k ) , que coincide con el rendimiento del esquema de función hash múltiple.
Análisis de tiempos
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 sobre el tamaño del conjunto, por lo que cuando es necesario estimar muchas similitudes por pares, este método puede generar ahorros sustanciales 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 hash único es generalmente más rápida, requiriendo O ( n ) tiempo para mantener la cola de valores mínimos de hash asumiendo n >> k . [1]
Incorporando pesos
Se han desarrollado diversas técnicas para introducir pesos en el cálculo de MinHashes. El más simple lo extiende a pesos enteros. [4] Extienda nuestra función hash h para aceptar tanto un miembro de conjunto como un entero, luego genere múltiples hash para cada elemento, de acuerdo con 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 la probabilidad de colisión.
Se han desarrollado otras 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 usa hashes distribuidos exponencialmente. Un hash uniformemente aleatorio entre 0 y 1 se puede convertir para seguir una distribución exponencial mediante inversión CDF . Este método explota las muchas y hermosas propiedades del mínimo de un conjunto de variables exponenciales .
Esto da como probabilidad de colisión el índice de probabilidad de Jaccard [7]
Permutaciones independientes mínimas
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 porque hay n ! diferentes permutaciones, requeriría Ω ( n log n ) bits solo para especificar una permutación verdaderamente aleatoria, un número inviablemente grande para incluso 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-sabiamente 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 a nivel mínimo debe incluir al menos
diferentes permutaciones y, por lo tanto, necesita Ω ( n ) bits para especificar una única permutación, aún inviablemente grande. [2]
Debido a esta impracticabilidad, se han introducido dos nociones variantes de independencia mínima: familias de permutaciones independientes restringidas en función mínima y familias independientes aproximadas en función mínima. 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 de la independencia total. [9]
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] [10] 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. [11]
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 base de datos y una columna por atributo), utilizan aproximaciones basadas en MinHash para el índice de Jaccard para identificar pares candidatos de atributos que con frecuencia coinciden. ocurrir, y luego calcular el valor exacto del índice solo para esos pares para determinar aquellos cuyas frecuencias de co-ocurrencia están por debajo de un umbral estricto dado. [12]
El algoritmo MinHash se ha adaptado para la bioinformática, donde el problema de comparar las secuencias del genoma tiene un fundamento teórico similar al de comparar documentos en la web. Las herramientas basadas en MinHash [13] [14] 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 genomas de referencia 90000 en RefSeq ), y son adecuadas para la especiación y tal vez un grado limitado de microbios. subtipo. También hay aplicaciones para la metagenómica [13] y el uso de algoritmos derivados de MinHash para la alineación y el ensamblaje del genoma. [15] Se pueden generar valores precisos de identidad de nucleótidos promedio (ANI) de manera muy eficiente con algoritmos basados en MinHash. [dieciséis]
Otros usos
El esquema MinHash puede verse como una instancia 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 de coseno entre vectores ; El hash sensible a la localidad tiene aplicaciones importantes en los algoritmos de búsqueda de vecinos más cercanos . [17] 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. [18]
Evaluación y comparativas
Google realizó una evaluación a gran escala en 2006 [19] para comparar el rendimiento de los algoritmos Minhash y SimHash [20] . En 2007, Google informó sobre el uso de Simhash para la detección de duplicados en el rastreo web [21] y el uso de Minhash y LSH para la personalización de Google News . [22]
Ver también
- Filtro de floración
- SimHash
- w-tejas
- Esbozo de conteo mínimo
Referencias
- ^ a b c d Broder, Andrei Z. (1997), "Sobre la semejanza y la contención de documentos", Compresión y complejidad de secuencias: Actas, Positano, Costa de Amalfitán, Salerno, Italia, 11-13 de junio de 1997 (PDF) , IEEE , págs. 21–29, CiteSeerX 10.1.1.24.779 , doi : 10.1109 / SEQUEN.1997.666900 , ISBN 978-0-8186-8132-5, archivado desde el original (PDF) el 31 de enero de 2015 , consultado el 18 de enero de 2014.
- ^ a b c Broder, Andrei Z .; Charikar, Moisés; Frieze, Alan M .; Mitzenmacher, Michael (1998), "Permutaciones independientes a nivel mínimo", 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.
- ^ Vassilvitskii, Sergey (2011), COMS 6998-12: Dealing with Massive Data (notas de clase, Universidad de Columbia) (PDF) , archivado desde el original (PDF) el 2018-10-24.
- ^ 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
- ^ Shrivastava, Anshumali (2016), "Hash minwise ponderado exacto en tiempo constante", arXiv : 1602.08393 [ cs.DS ]
- ^ Ioffe, Sergey (2010), "Muestreo consistente mejorado, minhash ponderado y bosquejo L1" (PDF) , Minería de datos (ICDM), 2010 IEEE 10th International Conference on : 246-255, CiteSeerX 10.1.1.227.9749 , doi : 10.1109 / ICDM.2010.80 , ISBN 978-1-4244-9131-5
- ^ Moulton, Ryan; Jiang, Yunjiang (2018), "Maximally Consistent Sampling and the Jaccard Index of Probability Distributions", IEEE International Conference on Data Mining (ICDM) 2018 , págs. 347–356, arXiv : 1809.04052 , doi : 10.1109 / ICDM.2018.00050 , ISBN 978-1-5386-9159-5
- ^ Matoušek, Jiří ; Stojaković, Miloš (2003), "Sobre la independencia mínima restringida de las permutaciones", Estructuras y algoritmos aleatorios , 23 (4): 397–408, CiteSeerX 10.1.1.400.6757 , doi : 10.1002 / rsa.10101.
- ^ Saks, M .; Srinivasan, A .; Zhou, S .; Zuckerman, D. (2000), "Los conjuntos de discrepancia baja producen familias de permutación 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.
- ^ Manasse, Mark (2012). Sobre la determinación eficiente de la mayoría de los vecinos 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.
- ^ Chum, Ondřej; Philbin, James; Isard, Michael; Zisserman, Andrew (2007), "Detección de tomas e imágenes casi idénticas escalables", Actas de la 6a Conferencia Internacional ACM sobre Recuperación de Imágenes y Vídeos (CIVR'07) , págs. 549–556, doi : 10.1145 / 1282280.1282359 , ISBN 9781595937339; 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) , 3 , p. 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.
- ^ a b 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 distancia de 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; Landolin, 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 .
- ^ Jain, 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 genomas procarióticos 90K revela límites claros de especies" . Comunicaciones de la naturaleza . 9 (1): 5114. doi : 10.1038 / s41467-018-07641-9 . PMC 6269478 . PMID 30504855 .
- ^ Andoni, Alexandr; 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.
- ^ Zadeh, Reza; Goel, Ashish (2012), "Cálculo de semejanza independiente de dimensión", arXiv : 1206.2082 [ cs.DS ].
- ^ 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 , págs. 284 , doi : 10.1145 / 1148170.1148222 , ISBN 978-1595933690.
- ^ Charikar, Moses S. (2002), "Técnicas de estimación de similitudes a partir de algoritmos de redondeo", Actas del 34º Simposio Anual de ACM sobre Teoría de la Computación , p. 380, doi : 10.1145 / 509907.509965 , ISBN 978-1581134957.
- ^ Gurmeet Singh, Manku; Jain, Arvind; Das Sarma, Anish (2007), "Detección de casi duplicados para rastreo web", Actas de la 16ª Conferencia Internacional sobre World Wide Web (PDF) , p. 141, doi : 10.1145 / 1242572.1242592 , ISBN 9781595936547.
- ^ 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.