Jaccard-Koeffizient

Der Jaccard-Koeffizient oder Jaccard-Index, auch Intersection over Union nach dem Schweizer Botaniker Paul Jaccard (1868–1944) ist eine Kennzahl für die Ähnlichkeit von Mengen. Oft wird er auch nach seiner Definition als IoU (Intersection over Union) bezeichnet.

Schnittmenge (oben) und Vereinigungsmenge (unten) von zwei Mengen A und B

Geschichte

Jaccard entwickelte den „Jaccard-Koeffizienten“ in seiner 1902 erschienenen Schrift Lois de distribution florale dans la zone alpine auf Seite 72. Er nannte ihn „coefficient de communauté florale“.

Der Jaccard-Koeffizient konnte sich in der Mathematik etablieren und wird als Ähnlichkeitsmaß für Mengen, Vektoren und ganz allgemein für Objekte genutzt. Speziell wird der Jaccard-Koeffizient für automatische Texterkennung und Interpretation eingesetzt.

Definition

Um den Jaccard-Koeffizient zweier Mengen zu berechnen, teilt man die Anzahl der gemeinsamen Elemente (Schnittmenge) 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

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\}|}}={\frac {3}{7}}=0{,}428\dotso$

Jaccard-Metrik

Aus dem Jaccard-Koeffizienten lässt sich die Jaccard-Metrik (auch „Jaccard-Distanz“ genannt) ableiten. Diese ist ein Maß für die Unähnlichkeit. Diese Metrik berechnet sich nach der Formel

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

Allgemein:

$J_{\delta }(S_{1},S_{2},\dotsc ,S_{n})=d_{J}(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}|}}$.

Je näher die Jaccard-Metrik an 0 liegt, desto näher liegen die Mengen A und B beieinander, weil sie sich sehr ähnlich sind. Der maximale Wert der Jaccard-Metrik ist 1. Dann sind die Mengen überschneidungsfrei.

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