Detección de duplicados aproximados con similitud de Jaccard y MinHash

Encontrar documentos similares: similitud de Jaccard y MinHash

• Definición del problema
  • Se analiza cómo identificar documentos similares en una colección documental a gran escala
  • Por ejemplo, al obtener la misma página varias veces mediante web crawling, se pueden tener varias versiones con ligeras diferencias en los metadatos o después de pequeñas ediciones
  • Este artículo explora un método de deduplicación aproximada usando similitud de Jaccard y MinHash

Similitud

• Definición de similitud
  • Se define la similitud entre dos documentos y cómo encontrar pares cuyo valor de similitud sea mayor o igual que un umbral específico
  • Se define una función de similitud S:U×U→[0,1], y si S(A,B)≥S_crit, los dos documentos se consideran duplicados aproximados

Similitud de Jaccard

• Similitud de Jaccard
  • Función que expresa la similitud entre dos conjuntos finitos como la proporción entre su intersección y su unión
  • J(A,B)=∣A∩B∣/∣A∪B∣
  • Cuanto más similares sean dos conjuntos, más elementos idénticos comparten

Extensión de la similitud de Jaccard

• Método de extensión
  • Se convierten los documentos en conjuntos de características y se buscan conjuntos con alta similitud de Jaccard
  • En corpus pequeños puede aplicarse directamente, pero en corpus grandes resulta ineficiente

Aproximación de la similitud de Jaccard

• Firmas MinHash
  • Se usa muestreo para aproximar la similitud de Jaccard
  • Se precalcula para cada documento una firma de tamaño fijo para estimar eficientemente la similitud

Uso de más funciones hash

• Múltiples funciones hash
  • Se usan varias funciones hash para resumir cada documento como un vector de k elementos
  • Se aproxima la similitud de Jaccard contando cuántos hashes coinciden entre dos firmas

Comparación de todos los documentos

• Agrupación de documentos
  • Los documentos se agrupan para comparar solo los que son similares
  • Se usan los valores de MinHash como clave de agrupación para encontrar eficientemente duplicados aproximados

Detección de duplicados más flexible

• Uso de múltiples claves
  • Se usan varias claves para colocar documentos en varios buckets y compararlos dentro de cada bucket
  • Esto permite detectar duplicados incluso con valores de similitud más bajos

Conclusión

• Conclusión
  • Con algoritmos como MinHash es posible encontrar documentos similares de forma eficiente
  • Se espera que este artículo ayude a más ingenieros a conocer y comprender estos algoritmos

Apéndice: representar documentos como conjuntos

• n-gramas

  • Los documentos se representan como n-gramas para compararlos
  • La precisión de la comparación varía según el valor de n

• Segmentación en palabras

  • Los documentos se dividen en palabras o tokens para usarlos como características
  • También pueden usarse tokenizadores más sofisticados

La opinión de GN⁺

• Importancia de detectar documentos similares

  • Eliminar duplicados en datasets a gran escala es importante para mejorar la calidad de los datos y ahorrar espacio de almacenamiento
  • Es especialmente esencial en procesos de web crawling o recolección de datos

• Ventajas de MinHash

  • MinHash permite detectar documentos similares de forma eficiente y escalable
  • Es más flexible que los métodos tradicionales de deduplicación basados en hash

• Otras técnicas similares

  • Otros algoritmos de sketch, como HyperLogLog, también pueden usarse para resolver problemas similares
  • Combinar ambos algoritmos puede dar lugar a una solución más potente

• Consideraciones para aplicarlo en la práctica

  • Importancia de elegir bien la función hash: la elección de la función hash influye mucho en la precisión de los resultados
  • Equilibrio entre rendimiento y precisión: usar más funciones hash mejora la precisión, pero aumenta el costo en rendimiento

• Tecnologías recomendadas

  • Puede aplicarse fácilmente con herramientas como la implementación de MinHashLSH de Spark
  • Se recomienda aprovechar activamente estas técnicas para una deduplicación eficiente en datasets a gran escala

[GN⁺]

Opiniones de Hacker News

• La similitud de Jaccard y la puntuación F1 también pueden usarse de la misma forma en conjuntos difusos

  • En conjuntos difusos, hay que elegir un par adecuado de T-Norm/T-Conorm
  • Este método es útil para validar la segmentación de imágenes médicas
  • La mayoría de la gente establece el umbral en 0.5 y usa conjuntos binarios
  • Esto reduce considerablemente la precisión del operador de validación

• Tengo experiencia implementando la deduplicación de la base de datos del gobierno francés con Python

  • Actualmente recomiendo datasketch
  • También existe una herramienta nueva llamada rensa
  • rensa es una versión más rápida escrita en Rust

• Es una tecnología desarrollada en los inicios de Google para la deduplicación

  • Se explica en detalle en "Mining Massive Datasets" de Jeffrey Ullman
  • Esta tecnología se desarrolló primero en AltaVista

• Tengo experiencia implementando un sistema de Minhash

  • Resolvía el problema de encontrar la matriz inversa (aproximada) de submatrices dentro de matrices grandes
  • Usé Minhashing para encontrar matrices similares
  • Ajusté la selectividad de búsqueda usando hashes de múltiples resoluciones

• Como Minhash y sus variantes son difíciles de entender, estoy desarrollando una herramienta de visualización

  • Planeo incluir el cálculo de similitud de Jaccard

• Es más fácil entender la tecnología mediante ejemplos de código

  • Aprendí esta técnica de Douglas Eck de Google
  • Se usa para agrupar canciones

• Un equipo de NVIDIA lanzó un algoritmo de deduplicación difusa acelerado por GPU

  • Proporcionan un repositorio de GitHub y documentación
  • También incluye ejemplos en Python

• Es común una estrategia de deduplicación que combina hashing o una red neuronal pequeña con un motor de búsqueda vectorial

  • Existen el modelo RETSim de Google y el proyecto del motor USearch

• Le señalé una errata al autor

  • Debería ser S(A,C) en lugar de S(A,B)

• Estoy resolviendo en Postgres el problema de reducir elementos de noticias similares a uno solo

  • Hay 600,000 elementos de feeds
  • El contenido y el resumen son muy similares