Minhash com Python

MinHash é uma técnica utilizada para estimar o coeficiente de semelhança de dois conjuntos sem a necessidade de contar os elementos na intersecção ou união dos conjuntos.

A Teoria


Introdução

Antes de apresentar a solução eu gostaria reservar um espaço para falar de maneira breve sobre o problema que o MinHash se propõe a resolver, que é o cálculo do coeficiente de Jaccard entre dois conjuntos de maneira eficaz.

O Coeficiente de semelhança de Jaccard

Proposto pelo biólogo francês, Paul Jaccard em 1901, para descrever a semelhança a entre dois conjuntos. O coeficiente de Jaccard( ) de dois conjuntos é dado pela quantidade de elementos presentes na intersecção dos conjuntos dividida pela quantidade de elementos na união dos conjuntos. De maneira mais precisa podemos escrever o seguinte:

O coeficiente é caso não exista intersecção entre os conjuntos, se os conjuntos forem idênticos e entre esses valores para todos os outros casos.

A popularidade desse coeficiente está relacionada à generalidade de sua definição - os conjuntos não precisam ter nenhuma forma ou propriedade especial - e ao fato de que é uma métrica - ou seja de maneira simplificada podemos dizer que é uma função especial que associa um par de conjuntos a um número real.

Se você está interessado em comparar apenas alguns ecossistemas e cada um com apenas algumas dezenas de espécies não há grandes problemas nesse método mas, por outro lado, se você está interessado em comparar dezenas de milhares de conjuntos e cada um com, possivelmente, milhares de elementos essa abordagem não é viável.

MinHash para quê?

MinHash é uma técnica utilizada para estimar o coeficiente de semelhança de dois conjuntos sem a necessidade de contar os elementos na intersecção ou união dos conjuntos.

Como?

Antes de executarmos o algoritmo precisamos preparar nossos dados. Não é necessário fazer nada muito nada muito complexo, basta garantirmos que cada elemento possua um identificador numérico único. Para esclarecer, vejamos um exemplo:

Note que os elementos podem ser qualquer coisa! Palavras, imagens, documentos ou objetos no bd são elementos válidos. A única coisa importante é que cada elemento possua um identificador e que elementos iguais tenham o mesmo identificador.

Agora que temos tudo pronto podemos falar sobre o funcionamento do algoritmo, ele pode ser dividido basicamente em 5 etapas, as quais são:

  1. Gere uma função de hash
  2. Aplique essa função em todos seus conjuntos
  3. Guarde apenas o menor valor da função para cada conjunto em um vetor
  4. Repita os passos 1-3 muitas vezes
  5. Compare os vetores resultantes para estimar o coeficiente de semelhança

Considerando o exemplo acima, ao final do passo 4 você deve ter dois vetores com valores onde é o número de vezes que você repetiu os passos 1-3.

Mágica?

Após essa breve descrição você poderia imaginar que se esse algoritmo realmente funciona - quem garante? - é por alguma mágica da matemática mas você estaria enganado.

Perceba que o coeficiente de Jaccard pode ser interpretado como “Escolhendo-se ao acaso um elemento do conjunto A, qual a probabilidade de que ele esteja em B?” com isso em mente não é muito difícil perceber o que o algoritmo está fazendo. Ele está pegando um elemento qualquer do conjunto - aquele que produz o menor valor quando calculado na função de hash - e comparando com o hash armazenado dos outros conjuntos. Como a função de hash é escolhida de forma que, geralmente, cada entrada produz uma saída única, ao comparar esses valores podemos obter uma aproximação para o coeficiente de semelhança de Jaccard.

Qual a precisão do método?

Falando sobre a precisão do algoritmo, é normal encontrar afirmações de que o erro é limitado por onde é o número de funções de hash utilizadas. Essa afirmação não está errada mas, ao mesmo tempo, não signifiga muita coisa afinal é basicamente o desvio padrão da média de estimadores não tendenciosos.

De maneira mais precisa podemos dizer que para obter um erro limitado por , com confiança devemos satizfazer:

Outra propriedade interessante deste algoritmo é que o seu erro não está ligado ao tamanho dos conjuntos. O erro depende apenas do tamanho da assinatura escolhido.

A Prática


Falar é facil, me mostra o código!

O código a seguir é praticamente um pseudo-código disfarçado de Python, por isso não espere que ele vá funcionar só com um Ctrl-c, Ctrl-v. Algumas alterações serão necessárias para que ele funcione e essas alterações estão relacionadas à forma como os seus dados estão armazenados.

Hash

Existem várias maneiras de calcular o hash de alguma coisa mas eu vou me deter ao hash modular por ser simples e bastante robusto. De maneira mais específica, utilizaremos uma função da forma:

Onde é o valor que você quer calcular o hash, está entre 1 e , está entre 0 e e é um número primo maior do que o maior valor possível para .

Para criar as funções de hash em Python podemos fazer o seguinte:

from random import randint

def obter_funcao_hash(p):
    a = randint(1, p-1)
    b = randint(0, p-1)
    def hash(x):
        return (a*x+b) % p
    return hash

Dessa maneira obter_funcao_hash() retorna uma função e para calcular o hash de um valor basta fazer:

p = 6113
funcao_hash = obter_funcao_hash(p)
hash =  funcao_hash(x)

Não esqueça de alterar o valor de de acordo com a dimensão do problema que você está trabalhando.

Vetor assinatura

Agora que você tem uma função que calcula o hash de um elemento basta aplicar essa função em todos os elementos do conjunto e salvar o menor valor.

menor_hash = p
for elemento in elementos_do_conjunto:
    valor_hash = funcao_hash(elemento)
    if valor_hash < menor_hash:
        menor_hash = valor_hash

Mas apenas uma função de hash não é o suficiente, vamos calcular funções em todos os elementos de todos os conjuntos e salvar os valores em um vetor.

vetor_assinatura = dict()
for conjunto in lista_conjuntos:
    vetor_assinatura[conjunto.id] = list()

k = 200
for i in range(k):
    funcao_hash = obter_funcao_hash(p)
    for conjunto in lista_conjuntos:
        for elemento in conjunto.elementos:
            valor_hash = funcao_hash(elemento)
            if valor_hash < menor_hash:
                menor_hash = valor_hash
        vetor_assinatura[conjunto.id].append(menor_hash)

Comparando assinaturas

Por fim, agora só falta comparar as assinaturas de cada conjunto para que possamos obter uma aproximação do coeficiente de semelhança de Jaccard.

contador = 0
for (s1, s2) in zip(vetor_assinatura[id1], vetor_assinatura[id2]):
    if s1 == s2:
        contador += 1
coeficiente = contador/float(k)

Considerações finais


Apesar de ser uma grande melhoria se comparado a uma técnica de força bruta, o MinHash não é capaz de resolver problemas em escalas muito grandes. A sua principal limitação é o número de comparações necessárias, que é algo da ordem de , onde é o número de conjuntos. Isso deixa claro porque essa não é a melhor técnica para utilizar quando se está trabalhando com algumas dezenas de milhares de conjuntos. Para esses casos existem algumas modificações que podem ser feitas nesse algoritmo para torná-lo ainda mais eficaz, mas isso é assunto para outro post.

Além disso, gostaria de agradecer ao Juan Lopes que me ajudou a arrumar algumas questões que não haviam ficado muita claras, em especial a parte sobre o limitante do erro, e além disso recomendou vários artigos interessantes sobre o assunto.

Leitura adicional


Se você gostaria de se aprofundar um pouco mais no assunto, deixarei aqui uma lista documentos que você poderia considerar úteis.


Se você gostou deste post, compartilhe com seus seguidores via twitter, e se você quiser ficar sabendo quando houverem novas publicações, me acompanhe no Twitter.