Jaccard-Koeffizient

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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

Definition[Bearbeiten]

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, \dotsc, S_n) = \frac{|S_1 \cap S_2 \cap\dotsb\cap S_n |}{|S_1 \cup S_2 \cup\dotsb\cup S_n |}.

Je näher der Jaccard-Koeffizient an 1 liegt, desto größer ist die Ähnlichkeit der Mengen. Der minimale Wert des Jaccard-Koeffizienten ist 0.

Beispiel[Bearbeiten]

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

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

Jaccard-Metrik[Bearbeiten]

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, \dotsc, S_n) = 1 - J(S_1, S_2, \dotsc, S_n) = \frac{|S_1 \cup S_2 \cup \dotsb\cup S_n | - |S_1 \cap S_2 \cap \dotsb\cap S_n |}{|S_1 \cup S_2 \cup \dotsb \cup S_n |}.

Anwendungen[Bearbeiten]

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 mit N > 1). Die daraus entstehenden Mengen an Stringabschnitten werden wie oben beschrieben zur Berechnung der Ähnlichkeit der beiden Mengen verwendet.