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. Oft wird er auch nach seiner Definition als IoU (Intersection over Union) bezeichnet.
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".[1][2]
Der Jaccard-Koeffizient konnte sich in der Mathematik etablieren und wird als Ähnlichkeitsmaß für Mengen, Vektoren und ganz allgemein für Objekte genutzt.[3][4] Speziell wird der Jaccard-Koeffizient für automatische Texterkennung und Interpretation eingesetzt.[5]
Definition
Um den Jaccard-Koeffizient zweier Mengen zu berechnen, teilt man die Anzahl der gemeinsamen Elemente (Schnittmenge) durch die Größe der Vereinigungsmenge:
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J(A,B) = \frac{|A \cap B|}{|A \cup B|}} .
Für Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Mengen gilt
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle A=\{1,2,3,4,7\}} und haben den Jaccard-Koeffizienten
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{|A\cap B|}{|A\cup B|}=\frac{|\{1,4,7\}|}{|\{1,2,3,4,5,7,9\}|}=\frac37=0{,}429\dotso}
Jaccard-Metrik
Aus dem Jaccard-Koeffizienten lässt sich die Jaccard-Metrik ableiten. Diese Metrik berechnet sich nach der Formel
- Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle J_{\delta}(A,B) = 1 - J(A,B) = { { |A \cup B| - |A \cap B| } \over |A \cup B| }} .
Allgemein:
- .
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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle N > 1} ). Die daraus entstehenden Mengen an Stringabschnitten werden wie oben beschrieben zur Berechnung der Ähnlichkeit der beiden Mengen verwendet.[6]
Einzelnachweise
- ↑ Paul Jaccard: Lois de distribution florale dans la zone alpine, Bulletin de la Société Vaudoise des Sciences Naturelles, Band 38 (1902), S. 72, doi:10.5169/seals-266762#110 Abgerufen am 23. November 2018.
- ↑ Huihuan Qian: Intelligent surveillance systems. Springer, Dordrecht 2011, ISBN 978-94-007-1137-2.
- ↑ Ähnlichkeitsmaße für Vektoren bei Fraunhofer. Abgerufen am 23. November 2018.
- ↑ Jaccard-Koeffizient in Hans Friedrich Eckey, Reinhold Kosfeld, Martina Rengers: Multivariate Statistik, Betriebswirtschaftlicher Verlag Dr. Th. Gabler GmbH, Wiesbaden, 2002, ISBN 3-409-11969-8, S. 219. Abgerufen am 23. November 2018.
- ↑ Jaccard-Koeffizient bei seo-suedwes. Abgerufen am 23. November 2018.
- ↑ Bing Liu: Web Data Mining: Exploring Hyperlinks, Contents, and Usage Data. 2. Auflage. Springer-Verlag, Berlin / Heidelberg 2011, ISBN 978-3-642-19459-7, S. 231 f.