MinHash
En informática y minería de datos , MinHash (o el esquema de hashing sensible a la localidad de permutaciones independientes min-wise ) es una técnica para estimar rápidamente qué tan similares son dos conjuntos. El esquema fue inventado por Andrei Broder ( 1997 ), [1] e inicialmente utilizado 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 agrupamiento a gran escala , como agrupar documentos por la similitud de sus conjuntos de palabras. [1]
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 :
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 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.
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 ∘ perm —es decir, el miembro x de S con el valor mínimo de h ( perm ( x )). (En los casos en que se suponga que la función hash utilizada tiene propiedades pseudoaleatorias, no se utilizará la permutación aleatoria).
Ahora, aplicando h min a A y 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:
Es decir, la probabilidad de que h min ( A ) = h min ( B ) sea verdadera es igual a la similitud J ( A , B ) , suponiendo dibujar 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 altapara ser un estimador útil para la similitud de Jaccard por sí solo, porquesiempre es cero o uno. La idea del esquema MinHash es reducir esta varianza promediando varias variables construidas de la misma manera.
