MinHash

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 e inicialmente usado en el motor de búsqueda AltaVista para detectar páginas web duplicadas y eliminarlas de los resultados de búsqueda. También ha sido aplicado en problemas de clustering, tales como agrupación de documentos por la similitud de las palabras que contienen.

En la mayoría de los casos, se utilizan funciones hash para separar y ocultar los datos, de modo que datos similares tengan claves diferentes. Sin embargo, se propone utilizar funciones hash para el propósito opuesto: detectar similitudes entre datos.

La detección de similitudes y la clasificación es un problema bien estudiado, pero normalmente se involucran n² comparaciones por pares. Al utilizar una función hash que convierte datos similares en valores similares, la similitud se puede detectar simplemente comparando valores de clave hash preclasificados. El reto es encontrar una función hash de similitud que minimice los falsos positivos.

SimHash produce claves hash con valores enteros, se recurrió a datos auxiliares para mejorar las pruebas de similitud. Los valores clave se basaron en contar las ocurrencias de ciertas cadenas binarias dentro de un fichero y combinando estas sumas. No obstante, los valores clave seguían siendo aproximadamente proporcionales al tamaño del fichero, lo que provocaba muchos falsos positivos.

Se estableció como objetivo la creación de una "función hash de similitud". Normalmente, las funciones hash se diseñan para minimizar las colisiones (cuando dos entradas diferentes tienen el mismo valor de clave). Con las funciones hash criptográficas, se espera que las colisiones sean casi imposibles, y que los datos casi idénticos correspondan a claves muy distintas. Sin embargo, la función hash de similitud tenía la intención opuesta: se buscaba que datos similares correspondieran a claves hash muy similares o incluso a la misma clave hash, y que la distancia entre las claves fuera una medida de la diferencia entre los datos.

Similitud Jaccard y valores de hash mínimos

El coeficiente de similitud de Jaccard de dos conjuntos Plantilla:Math and Plantilla:Math se define como

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

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 una función hash que mapea los miembros de Plantilla:Math y Plantilla:Math a enteros distintos, y que para cada conjunto S define Plantilla:Math como el miembro Plantilla:Math de Plantilla:Math con el valor mínimo de Plantilla:Math. LuegoPlantilla:Math exactamente cuando el valor mínimo Plantilla:Math esta en la intersección de Plantilla:Math. Por tanto,

Plantilla:Math

En otras palabras, si Plantilla:Math es una variable aleatoria que es 1 cuando Plantilla:Math y 0 en otro caso, entonces Plantilla:Math es un estimador insesgado de Plantilla:Math, 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.

Algoritmo

Variante con muchas funciones hash

La versión más simple del esquema MinHash usa Plantilla:Math funciones hash diferentes, donde Plantilla:Math es un parámetro entero fijo, y representa cada conjunto Plantilla:Math por los valores Plantilla:Math de Plantilla:Math para estas Plantilla:Math funciones.

Para estimar Plantilla:Math usando esta versión del esquema, sea Plantilla:Math el número de funciones hash para las cuales Plantilla:Math, y usamos Plantilla:Math como el estimado. Este estimado es el promedio de Plantilla:Math variables aleatorias 0-1, cada una de las cuales es 1 cuando Plantilla:Math y 0 de otra forma, y cada uno de los cuales es un estimador insesgado de Plantilla:Math. Por tanto, su promedio es también un estimador insesgado, y para la desviación estándar para sumas de variables aleatorias 0-1, su error esperado es Plantilla:Math.

Por tanto, para cualquier constante Plantilla:Math hay una constante Plantilla:Math tal que el error esperado del estimado es a lo sumo  Plantilla:Math. Por ejemplo, se necesitarían 400 hashes para estimar Plantilla:Math con un error esperado menor o igual a .05.

Variante con una sola función de hash

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. SeaPlantilla:Math una función de hash, y sea Plantilla:Math un entero fijo. SiPlantilla:Math es cualquier conjunto de Plantilla:Math o más valores en el dominio de Plantilla:Math, definenPlantilla:Math como el subconjunto de Plantilla:Math miembros de Plantilla:Math que tienen los valores más pequeños de Plantilla:Math. Este subconjunto Plantilla:Math es usado como una firma para el conjunto Plantilla:Math, 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. LuegoPlantilla:Math sea un conjunto de k elementos de Plantilla:Math, y si h es una función aleatoria de k elementos con igualdad de probabilidad de ser escogidos; o sea, Plantilla:Math es un muestra aleatoria simple dePlantilla:Math. El subconjunto Plantilla:Math es el conjunto de los miembros de Plantilla:Math que pertenecen a la intersección Plantilla:Math. Por tanto, |Plantilla:Math|/Plantilla:Math es un estimador insesgado de Plantilla:Math. La diferencia entre este estimador y el estimador producido por múltiples funciones hash es que Plantilla:Math siempre tiene exactamente Plantilla:Math 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 Plantilla:Math es pequeño en relación con los tamaños de los conjuntos, esta diferencia es insignificante.

Para cotas de Chernoff estándar para el muestreo sin reemplazo, este estimador tiene error esperado Plantilla:Math, igualando el desempeño del esquema hash-función-múltiple.

Análisis de tiempo

El estimador Plantilla:Math puede ser computado en Plantilla:Math dadas las dos firmas de los conjuntos dados, en cualquier variante del esquema. Por tanto, cuando Plantilla:Math y Plantilla:Math 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 Plantilla:Math la variante de muchos hash toma tiempo Plantilla:Math. La variante de un solo hash es generalmente más rápido, lo que requiere tiempo Plantilla:Math para mantener la lista ordenada de los mínimos.Plantilla:Citation needed

Permutaciones independientes al mínimo

Con el fin de implementar el esquema MinHash como se describió anteriormente, se necesita la función hash Plantilla:Math para definir una permutación aleatoria en Plantilla:Math elementos, donde Plantilla:Math es el número total de elementos distintos en la unión de todos los conjuntos que compararse. Pero como hay Plantilla:Math permutaciones distintas, se requerirían Plantilla:Math bits sólo para especificar una permutación verdaderamente aleatoria, un gran número impracticable, incluso para valores moderados de Plantilla:Math. 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

$lcm(1,2,...,n)\ge e^{n-o(n)}$

permutaciones diferentes, y por lo tanto que necesita Plantilla:Math bits para especificar una única permutación, todavía impracticablemente grande.

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 restringidas 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 Plantilla:Math. La independencia respecto al mínimo aproximado tiene como máximo una probabilidad fija e de la variación de la plena independencia.

Aplicaciones

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

En minería de datos,Plantilla:Harvtxt 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.

El objetivo de SimHash se centró en la detección de semejanzas. Dos ficheros con una disparidad de tamaño son implícitamente diferentes y las relaciones de contención entre ambos no necesariamente hacen que los dos sean "similares" según la métrica.

Para que dos les sean similares según la métrica, deben contener un gran número de piezas comunes. Otra división en las técnicas de detección de similitud es la granularidad y la cobertura de estas piezas. SimHash opera con una granularidad muy reducida, a nivel de bytes o palabras. No intentamos obtener una cobertura completa, sino que se enfoca solo en las partes de aquel fichero que coinciden con el conjunto de patrones de bits.

Dada una métrica de similitud, es necesario establecer un umbral para determinar cuán cercanas deben estar dentro de esa métrica para considerarse similares. Nos centramos en les que tienen un alto grado de similitud, idealmente entre el 1% y el 2%.

Otros usos

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

Evaluación y puntos de referencia

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

Véase también

• Problema del conjunto de cobertura
• Distancia de Levenshtein

Enlaces externos

• Mining of Massive Datasets, Ch. 3. Finding similar Items
• Simple Simhashing
• Set Similarity & MinHash - C# implementation
• Minhash with LSH for all-pair search (C# implementation)
• MinHash – Java implementation
• All pairs similarity search (Google Research)
• Distance and Similarity Measures(Wolfram Alpha)
• Nilsimsa hash (Python implementation)
• Simhash
• SimHash: Hash-based Similarity Detection