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:
Sig(C) é suficientemente pequena para que a assinatura de um número muito grande de conjuntos possa ser mantida em memória RAM
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