Detecção de duplicatas aproximadas com similaridade de Jaccard e MinHash

Encontrando documentos semelhantes: similaridade de Jaccard e MinHash

• Definição do problema
  • Discute como identificar documentos semelhantes em uma grande coleção de documentos
  • Por exemplo, ao fazer web crawling e obter a mesma página várias vezes, pode haver várias versões com pequenas diferenças nos metadados ou após pequenas edições
  • Este artigo explora um método de deduplicação aproximada usando similaridade de Jaccard e MinHash

Similaridade

• Definição de similaridade
  • Define a similaridade entre dois documentos e como encontrar pares cujo valor de similaridade esteja acima de um determinado limiar
  • Define a função de similaridade S:U×U→[0,1], e considera dois documentos como duplicatas aproximadas quando S(A,B)≥S_crit

Similaridade de Jaccard

• Similaridade de Jaccard
  • Uma função que expressa a similaridade entre dois conjuntos finitos como a razão entre sua interseção e sua união
  • J(A,B)=∣A∩B∣/∣A∪B∣
  • Quanto mais semelhantes forem os dois conjuntos, maior será a quantidade de elementos idênticos entre eles

Expansão da similaridade de Jaccard

• Método de expansão
  • Converte documentos em conjuntos de características e busca conjuntos com alta similaridade de Jaccard
  • Em corpora pequenos, isso pode ser aplicado diretamente, mas em corpora grandes é ineficiente

Aproximação da similaridade de Jaccard

• Assinatura MinHash
  • Usa amostragem para aproximar a similaridade de Jaccard
  • Pré-calcula uma assinatura de tamanho fixo para cada documento para estimar a similaridade com eficiência

Uso de mais funções de hash

• Múltiplas funções de hash
  • Usa várias funções de hash para resumir cada documento em um vetor de k elementos
  • Aproxima a similaridade de Jaccard contando quantos hashes coincidem entre duas assinaturas

Comparação de todos os documentos

• Agrupamento de documentos
  • Agrupa documentos para comparar apenas os documentos semelhantes
  • Usa valores de MinHash como chaves de agrupamento para encontrar duplicatas aproximadas com eficiência

Detecção de duplicatas mais flexível

• Uso de múltiplas chaves
  • Usa várias chaves para colocar documentos em vários buckets e comparar dentro de cada bucket
  • Permite detectar duplicatas mesmo com valores de similaridade mais baixos

Conclusão

• Conclusão
  • Algoritmos como MinHash permitem encontrar documentos semelhantes de forma eficiente
  • Espera-se que este artigo ajude mais engenheiros a conhecer e compreender esses algoritmos

Apêndice: representando documentos como conjuntos

• n-gramas

  • Representa documentos como n-gramas para comparação
  • A precisão da comparação varia de acordo com o valor de n

• Segmentação de palavras

  • Divide documentos em palavras ou tokens para usá-los como características
  • Também é possível usar tokenizadores mais sofisticados

Opinião do GN⁺

• Importância da detecção de documentos semelhantes

  • Remover duplicatas em grandes conjuntos de dados é importante para melhorar a qualidade dos dados e economizar espaço de armazenamento
  • Isso é especialmente essencial em processos de web crawling ou coleta de dados

• Vantagens do MinHash

  • O MinHash permite detectar documentos semelhantes de maneira eficiente e escalável
  • É mais flexível do que métodos tradicionais de deduplicação baseados em hash

• Outras técnicas semelhantes

  • Outros algoritmos de sketch, como o HyperLogLog, também podem ser usados para resolver problemas semelhantes
  • Combinar os dois algoritmos pode criar uma solução mais poderosa

• Pontos a considerar na aplicação prática

  • Importância da escolha da função de hash: a escolha da função de hash tem grande impacto na precisão dos resultados
  • Equilíbrio entre desempenho e precisão: quanto mais funções de hash forem usadas, maior a precisão, mas também aumenta o custo de desempenho

• Tecnologias recomendadas

  • Ferramentas como a implementação MinHashLSH do Spark permitem aplicação com facilidade
  • Recomenda-se usar ativamente essas técnicas para uma deduplicação eficiente em grandes conjuntos de dados

[GN⁺]

Comentários do Hacker News

• A similaridade de Jaccard e a pontuação F1 também podem ser usadas da mesma forma em conjuntos fuzzy

  • Em conjuntos fuzzy, é preciso escolher um par adequado de T-Norm/T-Conorm
  • Esse método é útil para validar segmentação de imagens médicas
  • A maioria das pessoas define o limiar em 0,5 e usa conjuntos binários
  • Isso reduz bastante a precisão do operador de validação

• Já houve experiência implementando deduplicação do banco de dados do governo francês em Python

  • Atualmente, a recomendação é datasketch
  • Também existe uma nova ferramenta chamada rensa
  • rensa é uma versão mais rápida escrita em Rust

• É uma tecnologia desenvolvida nos primórdios do Google para deduplicação

  • Explicada em detalhes em "Mining Massive Datasets", de Jeffrey Ullman
  • Essa tecnologia foi desenvolvida primeiro no AltaVista

• Já houve experiência implementando um sistema de Minhash

  • Resolveu o problema de encontrar a (pseudo)inversa de submatrizes de matrizes grandes
  • Usou Minhashing para encontrar matrizes semelhantes
  • Ajustou a seletividade da busca usando hash multirresolução

• Como é difícil entender Minhash e suas variações, está sendo desenvolvida uma ferramenta de visualização

  • Deve incluir o cálculo de similaridade de Jaccard

• É mais fácil entender a técnica por meio de exemplos de código

  • A técnica foi aprendida com Douglas Eck, do Google
  • É usada para clustering de músicas

• A equipe da NVIDIA lançou um algoritmo de deduplicação fuzzy acelerado por GPU

  • Fornece repositório no GitHub e documentação
  • Também inclui exemplos em Python

• Estratégias de deduplicação que combinam hashing ou pequenas redes neurais com mecanismos de busca vetorial são comuns

  • Há o modelo RETSim do Google e o projeto de mecanismo USearch

• Foi apontado um erro de digitação ao autor

  • Deveria ser S(A,C), e não S(A,B)

• Está sendo resolvido um problema no Postgres para reduzir itens de notícias semelhantes a um só

  • Existem 600.000 itens de feed
  • O conteúdo e os resumos são muito parecidos