Análise do LSH
Análise do processo
Assumimos que:
existem posições (buckets) suficientes para que as colunas não sejam suscetíveis de mapeamento para a mesma posição a menos que sejam idênticas num banda específica
Em consequência, assumimos que “mesma posição” significa “idêntico nessa banda”
Esta simplificação é necessária apenas para simplificar a análise, não para a correção do algoritmo
Exemplo de aplicação
100 000 documentos (=> 100 000 colunas de M)
Assinaturas de 100 inteiros (linhas)
Com b = 20 bandas de r = 5 inteiros/banda
Objetivo: encontrar pares de documentos que apresentem s ≥ 0.8
Caso 1: sim(C1 , C2 ) =0.8
Vejamos primeiro o que acontecerá a dois documentos com similaridade elevada (0.8)
Probabilidade de C1 , C2 idênticas numa banda específica:
J^r = (0.8)^5 = 0.329
Probabilidade C1 , C2 não serem semelhantes em todas as 20 bandas:
(1 − 0.328)^20 = 0.00035
Cerca de 1/3000 dos pares de colunas semelhantes a 80% são falsos negativos
Encontraríamos 99.97% de pares de documentos verdadeiramente semelhantes
Caso 1: sim(C1 , C2 ) =0.3
Considerando agora documentos com baixa similaridade sim(C1 ,C2 ) = 0.3
Probabilidade de C1 , C2 idênticas numa banda específica:
J^r = (0.3)^5 = 0.00243
Probabilidade C1 , C2 não serem semelhantes em todas as 20 bandas:
1−(1−0.00243)20 = 0.0474
Aproximadamente 4.74% pares de documentos com similaridade de 0.3% acabam como pares candidatos, aparecendo como falsos positivos
Otimização do processo
A aplicação do LSH obriga a um compromisso entre os falsos positivos e falsos negativos
Este compromisso pode ser efetuado através de:
número de funções de dispersão, que resultam no número de linhas da matriz de assinaturas
número de bandas
número de linhas por banda
Last updated