Estimativa da similaridade de dois ou mais conjuntos¶

Visão geral¶

Normalmente, o coeficiente de similaridade (ou índice) Jaccard é usado para comparar a similaridade entre dois conjuntos. Para dois conjuntos, A e B, o índice Jaccard é definido como a relação entre o tamanho de sua interseção e o tamanho de sua união:

J(A,B) = (A ∩ B) / (A ∪ B)

Entretanto, este cálculo pode consumir recursos e tempo significativos e, portanto, não é ideal para grandes conjuntos de dados.

Em contraste, o objetivo do esquema MinHash é estimar J(A,B) rapidamente, sem computar a interseção ou a união.

Funções SQL¶

As seguintes Funções de agregação são fornecidas para estimar a similaridade aproximada usando MinHash:

• MINHASH: Retorna um estado MinHash contendo uma matriz MinHash de comprimento k (argumento de entrada).

• MINHASH_COMBINE: Combina dois (ou mais) estados de entrada MinHash em um único estado de saída MinHash.

• APPROXIMATE_SIMILARITY (ou APPROXIMATE_JACCARD_INDEX): Retorna uma estimativa da similaridade (índice Jaccard) dos conjuntos de entrada com base em seus estados MinHash.

Detalhes de implementação¶

Como detalhado em MinHash (na Wikipedia):

“A função hash H mapeia os membros de A e B para valores inteiros distintos e, para qualquer conjunto S, define H_min(S) como o membro mínimo de S em relação a H, ou seja, o membro s de S com o valor mínimo de H(s), como expresso na seguinte equação:

H_min(S) = argmin_{s in S} (H(s))

Se aplicarmos H_min a ambos A e B, obteremos o mesmo valor exatamente quando o elemento da união A ∪ B com valor de hash mínimo estiver na interseção A ∩ B. A probabilidade de isto ser verdade é a razão acima, portanto:

Pr[H_min(A) = H_min(B)] = J(A,B)

Considerando os conjuntos escolhidos aleatoriamente A e B, a probabilidade de que H_min(A) = H_min(B) seja verdade é igual a J(A,B). Em outras palavras, se X é a variável aleatória que é 1 quando H_min(A) = H_min(B) e 0 em caso contrário, então X é um estimador imparcial de J(A,B). Note que X tem uma variação muito grande para ser um bom estimador para o índice Jaccard por si só (já que é sempre 0 ou 1).

O esquema MinHash reduz esta variação ao fazer uma média conjunta de várias variáveis construídas da mesma forma usando um número k de diferentes funções de hash.”

Para conseguir isto, a função MINHASH inicialmente cria um número de k diferentes funções hash e as aplica a cada elemento de cada conjunto de entrada, mantendo o mínimo de cada um, para produzir uma matriz MinHash (também chamada estado MinHash) para cada conjunto. Mais especificamente, para i = 0 to k-1, a entrada i da matriz MinHash do conjunto A (mostrado por MinHash_A) corresponde ao valor mínimo da função hash H_i aplicado a cada elemento do conjunto A.

Finalmente, uma aproximação para a similaridade dos dois conjuntos A e B é calculada como:

J_apprx(A,B) = (# of entries MinHash_A and MinHash_B agree on) / k

Exemplos¶

No exemplo a seguir, mostramos como este esquema e as funções correspondentes podem ser utilizados a fim de aproximar a similaridade de dois conjuntos de elementos.

Primeiro, crie duas tabelas de exemplo e insira alguns dados de exemplo:

CREATE OR REPLACE TABLE mhtab1(c1 NUMBER,c2 DOUBLE,c3 TEXT,c4 DATE);
CREATE OR REPLACE TABLE mhtab2(c1 NUMBER,c2 DOUBLE,c3 TEXT,c4 DATE);

INSERT INTO mhtab1 VALUES
    (1, 1.1, 'item 1', to_date('2016-11-30')),
    (2, 2.31, 'item 2', to_date('2016-11-30')),
    (3, 1.1, 'item 3', to_date('2016-11-29')),
    (4, 44.4, 'item 4', to_date('2016-11-30'));

INSERT INTO mhtab2 VALUES
    (1, 1.1, 'item 1', to_date('2016-11-30')),
    (2, 2.31, 'item 2', to_date('2016-11-30')),
    (3, 1.1, 'item 3', to_date('2016-11-29')),
    (4, 44.4, 'item 4', to_date('2016-11-30')),
    (6, 34.23, 'item 6', to_date('2016-11-29'));

Copy

Em seguida, aproxime a similaridade dos dois conjuntos (tabelas mhtab1 e mhtab2) usando seus estados MinHash:

SELECT APPROXIMATE_SIMILARITY(mh) FROM
    ((SELECT MINHASH(100, *) AS mh FROM mhtab1)
    UNION ALL
    (SELECT MINHASH(100, *) AS mh FROM mhtab2));

+----------------------------+
| APPROXIMATE_SIMILARITY(MH) |
|----------------------------|
|                       0.79 |
+----------------------------+

Copy

O índice de similaridade destas duas tabelas é aproximado como 0,79, ao contrário do valor exato 0,8 (ou seja, 4/5).