Jaccard-Koeffizient

Der Jaccard-Koeffizient oder Jaccard-Index nach dem Schweizer Botaniker Paul Jaccard (1868–1944) ist eine Kennzahl für die Ähnlichkeit von Mengen.

Definition

Um den Jaccard-Koeffizient zweier Mengen zu berechnen, teilt man die Anzahl der gemeinsamen Elemente durch die Größe der Vereinigungsmenge:

$J(A,B) = \frac{|A \cap B|}{|A \cup B|}.$

Für $n$ Mengen gilt

$J(S_1, S_2, ..., S_n) = \frac{|S_1 \cap S_2 \cap\ldots\cap S_n |}{|S_1 \cup S_2 \cup\ldots\cup S_n |}.$

Je näher der Jaccard-Koeffizient an 1 liegt, desto größer ist die Ähnlichkeit der Mengen.

Beispiel

Die beiden Mengen $A=\{1,2,3,4,7\}$ und $B=\{1,4,5,7,9\}$ haben die Jaccard-Koeffizienten

$\frac{|A\cap B|}{|A\cup B|}=\frac{|\{1,4,7\}|}{|\{1,2,3,4,5,7,9\}|}=\frac37=0{,}429\ldots$

Jaccard-Metrik

Aus dem Jaccard-Koeffizienten lässt sich die Jaccard-Metrik ableiten. Diese Metrik berechnet sich nach der Formel

$J_{\delta}(A,B) = 1 - J(A,B) = { { |A \cup B| - |A \cap B| } \over |A \cup B| }$.

Allgemein:

$J_{\delta}(S_1, S_2, \ldots, S_n) = 1 - J(S_1, S_2, \ldots, S_n) = \frac{|S_1 \cup S_2 \cup \ldots\cup S_n | - |S_1 \cap S_2 \cap \ldots\cap S_n |}{|S_1 \cup S_2 \cup \ldots \cup S_n |}$.

Anwendungen

Im Bereich Textmining und hier insbesondere der Duplikaterkennung ist die Jaccard-Ähnlichkeit ein bekanntes Maß für die Ähnlichkeit zweier Elemente. Dabei werden zwei Strings in Token zerlegt (z.B. geteilt an den Leerzeichen oder unter Verwendung von N-Grammen (n > 1)). Die daraus entstehenden Mengen an „String-Schnippseln“ werden wie oben beschrieben zur Berechnung der Ähnlichkeit der beiden Mengen verwendet.