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 Plantilla:Harvs,[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]

Similitud Jaccard y valores de hash mínimosEditar

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

 

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 función de hash que mapea los miembros de A y B a enteros distintos, y que para cada conjunto S define hmin(S) como el miembro x de S con el valor mínimo de h(x). Luegohmin(A) = hmin(B) exactamente cuando el valor mínimo AB esta en la intersección de AB. Por tanto,

Pr[hmin(A) = hmin(B)] = J(A,B).

En otras palabras, si r es una variable aleatoria que es 1 cuando hmin(A) = hmin(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.

AlgoritmoEditar

Variante con muchas funciones hashEditar

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 hmin(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 hmin(A) = hmin(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 hmin(A) = hmin(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 por standard límite Chernoff para sumas de variables aleatorias 0-1, su error esperado es O(1/√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 hashEditar

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. Seah una función de hash, y sea k un entero fijo. SiS es cualquier conjunto de k o más valores en el dominio de h, definenh(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. LuegoX = h(k)(h(k)(A) ∪ h(k)(B)) = h(k)(AB) sea un conjunto de k elementos de AB, 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 deAB. El subconjunto Y = Xh(k)(A) ∩ h(k)(B) es el conjunto de los miembros de X que pertenecen a la intersección AB. 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 a los tamaños de los conjuntos, esta diferencia es insignificante.

Por estándar límite Chernoffs para el muestreo sin reemplazo, este estimador tiene error esperado O(1/√k), igualando el desempeño del esquema hash-función-múltiple.

Análisis de tiempoEditar

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ínimoEditar

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

 

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 restingidas 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]

AplicacionesEditar

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]

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.[7]

Otros usosEditar

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.[8]​ 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.[9]

Evaluación y puntos de referenciaEditar

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


Véase tambiénEditar

Enlaces externosEditar

ReferenciasEditar

  1. 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 ..
  2. 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 ..
  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 .; 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 ..
  7. 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 ..
  8. 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 ..
  9. Zadeh, Reza; Goel, Ashish (2012), Dimension Independent Similarity Computation, arXiv:1206.2082 ..
  10. 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 ..
  11. Charikar, Moses S. (2002), «Similarity estimation techniques from rounding algorithms», Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. ACM ..
  12. Gurmeet Singh, Manku; Das Sarma, Anish (2007), «Detecting near-duplicates for web crawling», Proceedings of the 16th international conference on World Wide Web. ACM, ..
  13. Das, Abhinandan S., et al. (2007), «Google news personalization: scalable online collaborative filtering», Proceedings of the 16th international conference on World Wide Web. ACM, ..