Estimation de la similarité de deux ensembles ou plus¶

Vue d’ensemble¶

Généralement, le coefficient (ou indice) de similarité de Jaccard est utilisé pour comparer la similarité entre deux ensembles. Pour deux ensembles, A et B, l’indice de Jaccard est défini comme étant le rapport de la taille de leur intersection et de la taille de leur union :

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

Cependant, ce calcul peut consommer beaucoup de ressources et de temps et n’est donc pas idéal pour les grands ensembles de données.

En revanche, l’objectif du schéma MinHash est d’estimer J(A,B) rapidement, sans calculer l’intersection ou l’union.

Fonctions SQL¶

Les Fonctions d’agrégation suivants sont fournis pour estimer la similarité approximative à l’aide de MinHash :

• MINHASH : retourne un état MinHash contenant un tableau MinHash de longueur k (argument d’entrée).

• MINHASH_COMBINE : combine deux (ou plus) états d’entrée MinHash en un seul état de sortie MinHash.

• APPROXIMATE_SIMILARITY (ou APPROXIMATE_JACCARD_INDEX) : renvoie une estimation de la similarité (indice de Jaccard) des ensembles d’entrée en fonction de leurs états MinHash.

Détails de l’implémentation¶

Comme détaillé dans MinHash (dans Wikipédia) :

« Soit H une fonction de hachage qui mappe les membres de A et de B avec des valeurs entières distinctes et, pour tout ensemble S, définit H_min(S) comme étant le membre minimal de S par rapport à H, c’est-à-dire le membre s de S avec la valeur minimale de H(s), comme exprimée par l’équation suivante :

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

Si nous appliquons H_min à A et B, nous obtiendrons la même valeur exactement au moment où l’élément de l’union A ∪ B avec la valeur minimale de hachage se trouve dans l’intersection A ∩ B. La probabilité que cela soit vrai est correspond donc au rapport ci-dessus :

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

En supposant que les ensembles choisis au hasard A et B, la probabilité que H_min(A) = H_min(B) soit vrai est égale à J(A,B). En d’autres termes, si X est la variable aléatoire qui est 1 quand H_min(A) = H_min(B) et 0 dans les autres cas, alors X est un estimateur non biaisé de J(A,B). Notez que X a une variance trop grande pour être un bon estimateur pour l’indice de Jaccard seul (puisqu’il est toujours de 0 ou 1).

Le schéma MinHash réduit cette variance en faisant la moyenne de plusieurs variables construites de la même manière en utilisant un nombre k de fonctions de hachage différentes. »

Pour ce faire, la fonction MINHASH crée d’abord un nombre k de fonctions de hachage différentes, et les applique à chaque élément de chaque ensemble d’entrée, en conservant le minimum de chacune, pour produire un tableau MinHash (aussi appelé état MinHash) pour chaque ensemble. Plus spécifiquement, pour i = 0 to k-1, l’entrée i du tableau MinHash de l’ensemble A (indiqué par MinHash_A) correspond à la valeur minimale de la fonction de hachage H_i appliquée à chaque élément de l’ensemble A.

Enfin, une approximation de la similarité des deux ensembles A et B est calculée comme suit :

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

Exemples¶

Dans l’exemple suivant, nous montrons comment ce schéma et les fonctions correspondantes peuvent être utilisés afin d’estimer la similarité de deux ensembles d’éléments.

Tout d’abord, créez deux tables d’échantillon et insérez quelques données d’échantillon :

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

Ensuite, estimez la similarité des deux ensembles (tables mhtab1 et mhtab2) en utilisant leurs états 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

L’indice de similarité de ces deux tables est d’environ 0,79, par opposition à la valeur exacte de 0,8 (c.-à-d. 4/5).