Determinação de pares candidatos

Mesmo com a redução drástica obtida com as assinaturas, ter de comparar todos os pares é algo que tem de ser evitado

Precisamos de reduzir o número de pares a comparar

O nosso objetivo é encontrar documentos com similaridade, de Jaccard, superior a um determinado limiar

Segundo o MinHash

Selecionar um limiar de semelhança s (0 < s < 1)

As colunas x e y da matriz de assinaturas são um par candidato se as suas assinaturas concordarem em pelo menos uma fração s das suas linhas

• M (i, x) = M (i, y) para pelo menos a fração s valores de i

Espera-se que os documentos x e y tenham a mesma similaridade (de Jaccard) que as suas assinatura

Ideia base do método LSH

Objectivo: Encontrar documentos com similaridade de Jaccard de pelo menos s

• Para um determinado limiar, por exemplo s = 0.8

Ideia base:

• Utilizar uma função de dispersão f(x,y) que indica se x e y constituem um par candidato

  • Par de elementos cuja similaridade tem de ser avaliada

• Aplicar a função às colunas da matriz de assinaturas

  • Cada par de colunas que resultam no mesmo valor da função de dispersão é um par candidato

LSH aplicado à matriz de MinHash

Grande ideia: Aplicar funções de dispersão às colunas da matriz várias vezes

Fazer com que (apenas) colunas similares tenham elevada probabilidade de terem o mesmo hash code

Pares candidatos são aqueles que resultam no mesmo hash code

Na prática

Na prática aplica-se a cada coluna várias funções de dispersão

Divide-se a matriz de assinaturas em b bandas

• de r linhas

Aplica-se a função de dispersão a cada banda

• Que mapeia numa de k posições

Pares candidatos são mapeados para a mesma posição pela função de dispersão para pelo menos uma das bandas