Schätzung der Ähnlichkeit von zwei oder mehr Sets¶

Übersicht¶

Typischerweise wird der Jaccard-Ähnlichkeitskoeffizient (oder Index) verwendet, um die Ähnlichkeit zwischen zwei Sets zu vergleichen. Für zwei Sätze, A und B, ist der Jaccardindex definiert als das Verhältnis der Größe ihrer Schnittmenge (Intersection) und der Größe ihrer Vereinigung (Union):

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

Diese Berechnung kann jedoch erhebliche Ressourcen und Zeit in Anspruch nehmen und ist daher nicht ideal für große Datasets.

Im Gegensatz dazu ist das Ziel des MinHash-Schemas, J(A,B) schnell zu schätzen, ohne den Schnittpunkt oder die Vereinigung zu berechnen.

SQL-Funktionen¶

Die folgenden Aggregatfunktionen sind für die Schätzung der ungefähren Ähnlichkeit mit MinHash vorgesehen:

• MINHASH: Gibt einen MinHash-Status zurück, der ein MinHash-Array der Länge k (Eingabeargument) enthält.

• MINHASH_COMBINE: Kombiniert zwei (oder mehr) MinHash-Eingabezustände zu einem einzigen MinHash-Ausgabezustand.

• APPROXIMATE_SIMILARITY (oder APPROXIMATE_JACCARD_INDEX): Gibt eine Schätzung der Ähnlichkeit (Jaccard-Index) von Eingabesets basierend auf deren MinHash-Zuständen zurück.

Implementierungsdetails¶

Wie auf der englischen Wikipedia-Seite zu MinHash beschrieben:

„H sei eine Hash-Funktion, die die Elemente von A und B auf unterschiedliche ganzzahlige Werte abbildet, und für jede Menge S sei H_min(S) definiert als minimales Element von S in Bezug auf H, d. h. als das Element s von S mit dem Mindestwert H(s), wie in der folgenden Gleichung ausgedrückt:

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

Wenn wir H_min auf A und B anwenden, erhalten wir den gleichen Wert genau dann, wenn das Element der Vereinigung A ∪ B mit dem minimalen Hash-Wert in der Schnittmenge A ∩ B liegt. Die Wahrscheinlichkeit, dass dies wahr ist, ist daher das obige Verhältnis, daher gilt:

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

Das heißt, bei zwei zufällig ausgewählten Mengen A und B ist die Wahrscheinlichkeit, dass H_min(A) = H_min(B) gilt, gleich J(A,B). Mit anderen Worten, wenn X die Zufallsvariable ist, die 1 ist, wenn H_min(A) = H_min(B), und sonst 0 ist, dann ist X ein neutraler Schätzer von J(A,B). Beachten Sie, dass X eine zu große Varianz hat, um ein guter Schätzer für den Jaccardindex allein zu sein (da er immer 0 oder 1 ist).

Das MinHash-Schema reduziert diese Varianz, indem es für mehrere gleich konstruierte Variablen den Mittelwert bildet, indem k verschiedene Hash-Funktionen verwendet werden.“

Um dies zu erreichen, erstellt die Funktion MINHASH zunächst k verschiedene Hash-Funktionen und wendet diese auf jedes Element jedes Eingabesets an, wobei das Minimum von jedem einzelnen beibehalten wird, um ein MinHash-Array (auch MinHash-Status genannt) für jedes Set zu erstellen. Genauer gesagt, für i = 0 to k-1 entspricht der Eintrag i des MinHash-Arrays für Set A (dargestellt durch MinHash_A) dem Minimalwert der Hash-Funktion H_i, die auf jedes Element von Set A angewendet wird.

Schließlich wird eine Approximation für die Ähnlichkeit der beiden Sets A und B wie folgt berechnet:

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

Beispiele¶

Im folgenden Beispiel zeigen wir, wie dieses Schema und die entsprechenden Funktionen verwendet werden können, um die Ähnlichkeit von zwei Elementesets zu approximieren.

Erstellen Sie zunächst zwei Beispieltabellen, und fügen Sie einige Beispieldaten ein:

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

Approximieren Sie dann die Ähnlichkeit der beiden Mengen (Tabelle mhtab1 und mhtab2) unter Verwendung der MinHash-Status:

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

Der Ähnlichkeitsindex dieser beiden Tabellen wird auf 0,79 approximiert, während der genaue Wert bei 0,8 (d. h. 4/5) liegt.