Efeito de k na Pfp
Falsos Positivos
Adicionando mais funções não diminui obrigatoriamente essa probabilidade
Decresce até um certo valor de k
Depois aumenta, porquê ?
Redução de falso positivos
FP podem ser reduzidos aumentando o tamanho do vetor B
neste caso à custa de mais memória
o efeito da relação n/m é ilustrado na figura
Também podem ser reduzidos aumentando o número de funções de dispersão
mas apenas até certo valor
Valor ótimo de k
É possível determinar o número de funções de dispersão que minimiza a probabilidade de falsos positivos
Para facilitar os cálculos minimiza-se ln(Pfp)
Aplicando ln() a Ppf = ( 1 - a^k )^k
temos ln(Ppf) = k * ln( 1 - a^k )
Minimização
Derivando, em ordem a k e igualando a zero
(1 - a^k) * ln(1 - a^k) - a^k * ln(a^k) = 0
Que tem por solução
a^k = 1/2
k ótimo
O valor ótimo de k pode ser obtido aplicando logaritmos e resolvendo em ordem a k:
K_ótimo = ln(1/2) / ln(a)
Substituindo o valor de a temos
K_ótimo = ln(1/2) / ( m * ln( 1 - 1/n ) )
Aproximando ln(1 − 1/n) pelo primeiro termo da série de Taylor (−1/n)
K_ótimo ~= ( n * ln(2) ) / m
Na prática utiliza-se o inteiro mais próximo
Last updated