Cálculo das Assinaturas

Assinaturas

Uma das etapas importantes do processo é a redução da representação dos conjuntos

Ideia base

Mapear cada conjunto Ci para uma pequena assinatura Sig(Ci ) através de funções rápidas, tal que:

  1. Sig(C) é suficientemente pequena para que a assinatura de um número muito grande de conjuntos possa ser mantida em memória RAM

  2. A similaridade das assinaturas Sig(C1 ) e Sig(C2 ) é aproximadamente igual à sim(C1, C2 )

Desafio

Obter uma função de dispersão h() tal que:

  • Se sim(C1 , C2 ) é elevada, então com elevada probabilidade h(C1 ) = h(C2 )

  • Se sim(C1 , C2 ) é baixa, então h(C1 ) ≠ h(C2 ) com elevada probabilidade

A função h() depende da métrica de similaridade

Para a similaridade de Jaccard a função Min-Hash cumpre os requisitos

Redução do conjunto usando permutações

Uma forma de reduzir o conjunto C representativo de um documento é considerar apenas um subconjunto

A seleção pode ser feita usando permutações aleatórias:

  • Aplicação de uma permutação aleatória π às linhas da matriz booleana

  • Reter o valor do índice da primeira linha (na ordem permutada) correspondente a um Shingle (ou equivalente) existente

Mínimo da função

Esta operação pode ser vista como a aplicação de uma função de dispersão hπ (C) = índice da primeira linha (na ordem permutada ) na qual a coluna C tem valor 1

  • h_pi(C) = min_pi pi(C)

Repetir para várias permutações independentes, por exemplo 100, para obter um vetor (assinatura)

  • Este processo de repetição com permutações independentes pode ser visto como a aplicação de várias funções h_π()

Propriedade de h_π

A função h_π() permite obter assinaturas pois estas mantêm informação sobre a similaridade dos documentos devido à seguinte propriedade

Last updated