Jaccard-Index – Wikipedia

Maß für Ähnlichkeit und Vielfalt zwischen Sets

Die Jaccard-Index, auch bekannt als die Jaccard-Ähnlichkeitskoeffizient, ist eine Statistik, die zum Messen der Ähnlichkeit und Vielfalt von Stichprobensätzen verwendet wird. Es wurde von Paul Jaccard entwickelt und gab ursprünglich den französischen Namen Koeffizient de communauté,^[1] und unabhängig wieder von T. Tanimoto formuliert.^[2] Und so kam es dass der Tanimoto-Index oder Tanimoto-Koeffizient werden auch in einigen Bereichen verwendet. Sie sind jedoch identisch, indem sie im Allgemeinen das Verhältnis von Kreuzung über Union. Der Jaccard-Koeffizient misst die Ähnlichkeit zwischen endlichen Stichprobensätzen und ist definiert als die Größe des Schnittpunkts geteilt durch die Größe der Vereinigung der Stichprobensätze:

${displaystyle J(A,B)={{|Acap B|} over {|Acup B|}}={{|Acap B|} over {|A|+|B| -|Acap B|}}.}$

Beachten Sie, dass konstruktionsbedingt

${displaystyle 0leq J(A,B)leq 1.}$

Wenn EIN und B sind beide leer, definieren J(EIN,B) = 1. Der Jaccard-Koeffizient wird häufig in der Informatik, Ökologie, Genomik und anderen Wissenschaften verwendet, in denen binäre oder binarisierte Daten verwendet werden. Für die Hypothesenprüfung mit dem Jaccard-Koeffizienten stehen sowohl die exakte Lösungs- als auch die Näherungsmethode zur Verfügung.^[3]

Jaccard-Ähnlichkeit gilt auch für Taschen, dh Multisets. Dies hat eine ähnliche Formel,^[4] aber die Symbole bedeuten Sackschnitt und Sacksumme (nicht Vereinigung). Der Höchstwert ist 1/2.

${displaystyle J(A,B)={{|Acap B|} over {|Aupplus B|}}={{|Acap B|} over {|A|+|B| }}.}$

Die Jackcard-Abstand, welche Maßnahmen disÄhnlichkeit zwischen Stichprobenmengen, ist komplementär zum Jaccard-Koeffizienten und wird durch Subtrahieren des Jaccard-Koeffizienten von 1 oder äquivalent durch Dividieren der Differenz der Größen der Vereinigung und der Schnittmenge zweier Mengen durch die Größe der Vereinigung erhalten:

${displaystyle d_{J}(A,B)=1-J(A,B)={{|Acup B|-|Acap B|} over |Acup B|}.}$

Eine alternative Interpretation des Jaccard-Abstands ist das Verhältnis der Größe der symmetrischen Differenz

${displaystyle Adreieck B=(Acup B)-(Acap B)}$

zur Gewerkschaft. Die Jaccard-Distanz wird häufig verwendet, um an . zu berechnen n × n Matrix zum Clustern und multidimensionalen Skalieren von n Mustersets.

Dieser Abstand ist eine Metrik für die Sammlung aller endlichen Mengen.^[5][6][7]

Es gibt auch eine Version der Jaccard-Distanz für Maße, einschließlich Wahrscheinlichkeitsmaßen. Wenn

${displaystylemu}$

ist ein Maß auf einem messbaren Raum

${displaystyle X}$

, dann definieren wir den Jaccard-Koeffizienten durch

${displaystyle J_{mu}(A,B)={{mu(Acap B)} over {mu(Acup B)}},}$

und die Jaccard-Distanz um

${displaystyle d_{mu}(A,B)=1-J_{mu}(A,B)={{mu(ADreieck B)}over {mu(Acup B)} }.}$

Vorsicht ist geboten, wenn

${displaystyle mu(Acup B)=0}$

oder

${displaystyleinfty}$

, da diese Formeln in diesen Fällen nicht gut definiert sind.

Das min-weise unabhängige Permutationen-Hashing-Schema von MinHash kann verwendet werden, um effizient eine genaue Schätzung des Jaccard-Ähnlichkeitskoeffizienten von Paaren von Mengen zu berechnen, wobei jede Menge durch eine Signatur konstanter Größe repräsentiert wird, die aus den Minimalwerten einer Hash-Funktion abgeleitet wird .

Ähnlichkeit asymmetrischer binärer Attribute[edit]

Bei zwei Objekten, EIN und B, jeder mit n binären Attributen ist der Jaccard-Koeffizient ein nützliches Maß für die Überlappung, die EIN und B mit ihren Attributen teilen. Jedes Attribut von EIN und B kann entweder 0 oder 1 sein. Die Gesamtzahl jeder Kombination von Attributen für beide EIN und B sind wie folgt angegeben:

${displaystyle M_{11}}$

stellt die Gesamtzahl der Attribute dar, bei denen EIN und B beide haben einen Wert von 1.

${displaystyle M_{01}}$

stellt die Gesamtzahl der Attribute dar, bei denen das Attribut von EIN ist 0 und das Attribut von B ist 1.

${displaystyle M_{10}}$

stellt die Gesamtzahl der Attribute dar, bei denen das Attribut von EIN ist 1 und das Attribut von B ist 0.

${displaystyle M_{00}}$

stellt die Gesamtzahl der Attribute dar, bei denen EIN und B beide haben den Wert 0.

EIN B	0	1
0	${displaystyle M_{00}}$	${displaystyle M_{10}}$
1	${displaystyle M_{01}}$	${displaystyle M_{11}}$

Jedes Attribut muss in eine dieser vier Kategorien fallen, was bedeutet, dass

${displaystyle M_{11}+M_{01}+M_{10}+M_{00}=n.}$

Der Jaccard-Ähnlichkeitskoeffizient, J, ist gegeben als

${displaystyle J={M_{11} over M_{01}+M_{10}+M_{11}}.}$

Die Jackcard-Distanz, D_J, ist gegeben als

${displaystyle d_{J}={M_{01}+M_{10} over M_{01}+M_{10}+M_{11}}=1-J.}$

Statistische Schlußfolgerungen können basierend auf den Jaccard-Ähnlichkeitskoeffizienten und folglich verwandten Metriken gemacht werden.^[3] Gegeben zwei Beispielsätze EIN und B mit n Attribute kann ein statistischer Test durchgeführt werden, um festzustellen, ob eine Überlappung statistisch signifikant ist. Die genaue Lösung ist verfügbar, obwohl die Berechnung kostspielig sein kann, da n erhöht sich.^[3] Schätzverfahren stehen entweder durch Approximation einer Multinomialverteilung oder durch Bootstrapping zur Verfügung.^[3]

Differenz zum einfachen Matching-Koeffizienten (SMC)[edit]

Bei Verwendung für binäre Attribute ist der Jaccard-Index dem einfachen Matching-Koeffizienten sehr ähnlich. Der Hauptunterschied besteht darin, dass der SMC den Begriff

${displaystyle M_{00}}$

in Zähler und Nenner, während dies beim Jaccard-Index nicht der Fall ist. Somit zählt die SMC sowohl die gegenseitige Anwesenheit (wenn ein Attribut in beiden Sets vorhanden ist) als auch die gegenseitige Abwesenheit (wenn ein Attribut in beiden Sets fehlt) als Übereinstimmungen und vergleicht sie mit der Gesamtzahl der Attribute im Universum, während der Jaccard-Index zählt nur die gegenseitige Anwesenheit als Übereinstimmung und vergleicht sie mit der Anzahl der Attribute, die von mindestens einem der beiden Sets ausgewählt wurden.

Bei der Warenkorbanalyse beispielsweise enthält der Warenkorb von zwei Verbrauchern, die wir vergleichen möchten, möglicherweise nur einen kleinen Bruchteil aller verfügbaren Produkte im Geschäft, so dass der SMC in der Regel sehr hohe Ähnlichkeitswerte zurückgibt, selbst wenn die Warenkörbe sehr wenig Ähnlichkeit, was den Jaccard-Index in diesem Zusammenhang zu einem geeigneteren Maß für die Ähnlichkeit macht. Betrachten Sie zum Beispiel einen Supermarkt mit 1000 Produkten und zwei Kunden. Der Korb des ersten Kunden enthält Salz und Pfeffer und der Korb des zweiten enthält Salz und Zucker. In diesem Szenario würde die Ähnlichkeit zwischen den beiden Körben, gemessen durch den Jaccard-Index, 1/3 betragen, aber die Ähnlichkeit beträgt 0,998 unter Verwendung des SMC.

In anderen Kontexten, in denen 0 und 1 äquivalente Informationen (Symmetrie) tragen, ist der SMC ein besseres Ähnlichkeitsmaß. Beispielsweise würden Vektoren von demografischen Variablen, die in Dummy-Variablen wie Geschlecht gespeichert sind, besser mit dem SMC verglichen als mit dem Jaccard-Index, da der Einfluss des Geschlechts auf die Ähnlichkeit gleich sein sollte, unabhängig davon, ob männlich als 0 und weiblich definiert ist als 1 oder umgekehrt. Wenn wir jedoch symmetrische Dummy-Variablen haben, könnte man das Verhalten des SMC replizieren, indem man die Dummys in zwei binäre Attribute (in diesem Fall männlich und weiblich) aufteilt und sie so in asymmetrische Attribute umwandelt, was die Verwendung des Jaccard-Index ohne . ermöglicht jegliche Voreingenommenheit einführen. Der SMC bleibt jedoch im Fall von symmetrischen Dummy-Variablen recheneffizienter, da er keine zusätzlichen Dimensionen erfordert.

Gewichtete Jaccard-Ähnlichkeit und Entfernung[edit]

Wenn

${displaystyle mathbf{x} =(x_{1},x_{2},ldots,x_{n})}$

und

${displaystyle mathbf{y} =(y_{1},y_{2},ldots,y_{n})}$

sind zwei Vektoren mit allen reellen

${displaystyle x_{i},y_{i}geq 0}$

, dann ist ihr Jaccard-Ähnlichkeitskoeffizient (damals auch als Ruzicka-Ähnlichkeit bekannt) definiert als

${displaystyle J_{mathcal{W}}(mathbf{x},mathbf{y})={frac{sum_{i}min(x_{i},y_{i})}{ sum_{i}max(x_{i},y_{i})}},}$

und Jaccard-Distanz (damals auch als Soergel-Distanz bekannt)

${displaystyle d_{J{mathcal{W}}}(mathbf{x},mathbf{y})=1-J_{mathcal{W}}(mathbf{x},mathbf{y} ).}$

Noch allgemeiner gesagt, wenn

${displaystyle f}$

und

${displaystyle g}$

sind zwei nicht-negativ messbare Funktionen auf einem messbaren Raum

${displaystyle X}$

mit Maß

${displaystylemu}$

, dann können wir definieren

${displaystyle J_{mathcal{W}}(f,g)={frac {int min(f,g)dmu }{int max(f,g)dmu}}, }$

wo

${displaystyle max}$

und

${displaystyle min}$

sind punktweise Operatoren. Dann ist die Jackcard-Distanz

${displaystyle d_{J{mathcal{W}}}(f,g)=1-J_{mathcal{W}}(f,g).}$

Dann zum Beispiel für zwei messbare Mengen

${displaystyle A,Bsubseteq X}$

, wir haben

${displaystyle J_{mu}(A,B)=J(chi_{A},chi_{B}),}$

wo

${displaystyle chi_{A}}$

und

${displaystyle chi_{B}}$

sind die charakteristischen Funktionen der entsprechenden Menge.

Wahrscheinlichkeit Jaccard-Ähnlichkeit und Entfernung[edit]

Die oben beschriebene gewichtete Jaccard-Ähnlichkeit verallgemeinert den Jaccard-Index auf positive Vektoren, wobei eine Menge einem binären Vektor entspricht, der durch die Indikatorfunktion gegeben ist, dh

${displaystyle x_{i}in {0,1}}$

. Es verallgemeinert den Jaccard-Index jedoch nicht auf Wahrscheinlichkeitsverteilungen, bei denen eine Menge einer einheitlichen Wahrscheinlichkeitsverteilung entspricht, dh

${displaystyle x_{i}={begin{cases}{frac {1}{|X|}}&iin X\0&{text{otherwise}}end{cases}}}$

Es ist immer weniger, wenn sich die Sets in der Größe unterscheiden. Wenn

${displaystyle |X|>|Y|}$

${displaystyle x_{i}=mathbf {1} _{X}(i)/|X|,y_{i}=mathbf {1} _{Y}(i)/|Y|}$

dann

${displaystyle J_{mathcal{W}}(x,y)={frac {|Xcap Y|}{|Xsetminus Y|+|X|}}$

Stattdessen ist eine zwischen Wahrscheinlichkeitsverteilungen und ihren entsprechenden Unterstützungsmengen stetige Verallgemeinerung

${displaystyle J_{mathcal{P}}(x,y)=sum_{x_{i}neq 0,y_{i}neq 0}{frac {1}{sum _{j} max left({frac {x_{j}}{x_{i}}},{frac {y_{j}}{y_{i}}}right)}}}$

die heißt die “Wahrscheinlichkeit” Jaccard.^[8] Es hat die folgenden Grenzen gegenüber dem Weighted Jaccard auf Wahrscheinlichkeitsvektoren.

${displaystyle J_{mathcal{W}}(x,y)leq J_{mathcal{P}}(x,y)leq {frac {2J_{mathcal{W}}(x,y) }{1+J_{mathcal{W}}(x,y)}}}$

Hier ist die obere Schranke der (gewichtete) Sørensen-Dice-Koeffizient. Der entsprechende Abstand,

${displaystyle 1-J_{mathcal{P}}(x,y)}$

, ist eine Metrik über Wahrscheinlichkeitsverteilungen und eine Pseudometrik über nicht-negativen Vektoren.

Der Probability Jaccard Index hat eine geometrische Interpretation als die Fläche einer Schnittmenge von Simplizes. Jeder Punkt einer Einheit

${displaystyle k}$

-simplex entspricht einer Wahrscheinlichkeitsverteilung auf

${displaystyle k+1}$

Elemente, weil die Einheit

${displaystyle k}$

-simplex ist die Punktmenge in

${displaystyle k+1}$

Dimensionen, die sich zu 1 summieren. Um den Wahrscheinlichkeits-Jaccard-Index geometrisch abzuleiten, stellen Sie eine Wahrscheinlichkeitsverteilung als Einheitssimplex dar, unterteilt in Subsimplices entsprechend der Masse jedes Elements. Wenn Sie zwei so dargestellte Verteilungen übereinander legen und die zu jedem Element gehörenden Simplizes schneiden, entspricht die verbleibende Fläche dem Wahrscheinlichkeits-Jaccard-Index der Verteilungen.

Optimalität des Wahrscheinlichkeits-Jaccard-Index[edit]

Betrachten Sie das Problem, Zufallsvariablen so zu konstruieren, dass sie so weit wie möglich miteinander kollidieren. Das heißt, wenn

${displaystyle Xsim x}$

und

${displaystyle Ysim y}$

, wir möchten bauen

${displaystyle X}$

und

${displaystyle Y}$

maximieren

${displaystyle Pr[X=Y]}$

. Wenn wir uns nur zwei Verteilungen ansehen

${displaystyle x,y}$

isoliert, das Höchste

${displaystyle Pr[X=Y]}$

wir erreichen können ist gegeben durch

${displaystyle 1-{text{TV}}(x,y)}$

wo

${displaystyle {text{TV}}}$

ist die Gesamtvariationsdistanz. Angenommen, es geht uns nicht nur um die Maximierung dieses bestimmten Paares, sondern wir möchten die Kollisionswahrscheinlichkeit eines beliebigen Paares maximieren. Man könnte unendlich viele Zufallsvariablen konstruieren, eine für jede Verteilung

${displaystyle x}$

, und versuchen zu maximieren

${displaystyle Pr[X=Y]}$

für alle Paare

${displaystyle x,y}$

. Der Probability Jaccard Index ist in einem ziemlich starken Sinne, der unten beschrieben wird, ein optimaler Weg, um diese Zufallsvariablen abzugleichen.

Für jede Probenahmemethode

${displaystyle G}$

und diskrete Verteilungen

${displaystyle x,y}$

, wenn

${displaystyle Pr[G(x)=G(y)]>J_{mathcal{P}}(x,y)}$

${displaystyle z}$

wo

${displaystyle J_{mathcal{P}}(x,z)>J_{mathcal{P}}(x,y)}$

${displaystyle J_{mathcal{P}}(y,z)>J_{mathcal{P}}(x,y)}$

${displaystyle Pr[G(x)=G(z)]$

oder

${displaystyle Pr[G(y)=G(z)]$

.^[8]

Das heißt, keine Sampling-Methode kann mehr Kollisionen erreichen als

${displaystyle J_{mathcal{P}}}$

auf einem Paar, ohne weniger Kollisionen zu erzielen als

${displaystyle J_{mathcal{P}}}$

auf einem anderen Paar, bei dem das reduzierte Paar ähnlicher ist unter

${displaystyle J_{mathcal{P}}}$

als das erhöhte Paar. Dieser Satz gilt für den Jaccard-Index von Mengen (wenn er als Gleichverteilung interpretiert wird) und die Wahrscheinlichkeit Jaccard, aber nicht für den gewichteten Jaccard. (Der Satz verwendet das Wort “Probenahmeverfahren” eine gemeinsame Verteilung über alle Verteilungen auf einem Raum zu beschreiben, da sie sich aus der Verwendung von gewichteten Minhashing-Algorithmen ableitet, die dies als ihre Kollisionswahrscheinlichkeit erreichen.)

Dieser Satz hat einen visuellen Beweis für drei Elementverteilungen unter Verwendung der Simplex-Darstellung.

Tanimoto Ähnlichkeit und Entfernung[edit]

In der Literatur und im Internet kommen verschiedene Formen von Funktionen vor, die als Tanimoto-Ähnlichkeit und Tanimoto-Distanz beschrieben werden. Die meisten davon sind Synonyme für Jaccard-Ähnlichkeit und Jaccard-Distanz, aber einige sind mathematisch unterschiedlich. Viele Quellen^[9] einen IBM Technical Report zitieren^[2] als wegweisende Referenz. Der Bericht ist erhältlich bei mehrere Bibliotheken.

In “Ein Computerprogramm zur Klassifizierung von Pflanzen”, veröffentlicht im Oktober 1960,^[10] ein Klassifikationsverfahren basierend auf einem Ähnlichkeitsverhältnis und einer abgeleiteten Distanzfunktion wird angegeben. Dies scheint die maßgeblichste Quelle für die Bedeutung der Begriffe zu sein “Tanimoto-Ähnlichkeit” und “Tanimoto-Distanz”. Das Ähnlichkeitsverhältnis entspricht der Jaccard-Ähnlichkeit, aber die Distanzfunktion ist nicht das gleiche wie die Jackcard-Distanz.

Tanimotos Definitionen von Ähnlichkeit und Distanz[edit]

In diesem Papier, a “Ähnlichkeitsverhältnis” wird über Bitmaps gegeben, wobei jedes Bit eines Arrays fester Größe das Vorhandensein oder Fehlen eines Merkmals in der modellierten Anlage darstellt. Die Definition des Verhältnisses ist die Anzahl der gemeinsamen Bits geteilt durch die Anzahl der gesetzten Bits (dh ungleich Null) in beiden Beispielen.

Mathematisch dargestellt, wenn Stichproben x und Ja sind Bitmaps,

${displaystyle X_{i}}$

ist der ichth bisschen x, und

${displaystyle land,lor}$

sind bitweise und, oder Operatoren, dann ist das Ähnlichkeitsverhältnis

${displaystyle T_{s}}$

ist

${displaystyle T_{s}(X,Y)={frac {sum_{i}(X_{i}land Y_{i})}{sum_{i}(X_{i}lor Y_{i})}}}$

Wenn jede Stichprobe stattdessen als ein Satz von Attributen modelliert wird, entspricht dieser Wert dem Jaccard-Koeffizienten der beiden Sätze. Jaccard wird in der Arbeit nicht zitiert, und es ist wahrscheinlich, dass die Autoren sich dessen nicht bewusst waren.

Tanimoto fährt fort, a . zu definieren “Distanzkoeffizient” basierend auf diesem Verhältnis, das für Bitmaps mit einer Ähnlichkeit ungleich null definiert ist:

${displaystyle T_{d}(X,Y)=-log_{2}(T_{s}(X,Y))}$

Dieser Koeffizient ist bewusst kein Distanzmaß. Es wurde gewählt, um die Möglichkeit zu ermöglichen, dass zwei Exemplare, die sich stark voneinander unterscheiden, einem dritten ähneln. Es ist leicht, ein Beispiel zu konstruieren, das die Eigenschaft der Dreiecksungleichung widerlegt.

Andere Definitionen von Tanimoto-Distanz[edit]

Tanimoto-Distanz wird fälschlicherweise oft als Synonym für Jaccard-Distanz bezeichnet

${displaystyle 1-T_{s}}$

. Diese Funktion ist eine geeignete Distanzmetrik. “Tanimoto-Distanz” wird oft als richtige Distanzmetrik angegeben, wahrscheinlich wegen der Verwechslung mit der Jaccard-Distanz.

Wenn Jaccard- oder Tanimoto-Ähnlichkeit über einen Bitvektor ausgedrückt wird, kann sie geschrieben werden als

${displaystyle f(A,B)={frac {Acdot B}{|A|^{2}+|B|^{2}-Acdot B}}}$

wobei dieselbe Berechnung als Vektorskalarprodukt und Betrag ausgedrückt wird. Diese Darstellung beruht auf der Tatsache, dass für einen Bitvektor (bei dem der Wert jeder Dimension entweder 0 oder 1 ist) dann

${displaystyle Acdot B=sum _{i}A_{i}B_{i}=sum _{i}(A_{i}land B_{i})}$

und

${displaystyle |A|^{2}=sum_{i}A_{i}^{2}=sum_{i}A_{i}.}$

Dies ist eine potenziell verwirrende Darstellung, da die über Vektoren ausgedrückte Funktion allgemeiner ist, es sei denn, ihr Bereich ist explizit eingeschränkt. Eigentum von

${displaystyle T_{s}}$

nicht unbedingt erweitern auf

${displaystyle f}$

. Insbesondere die Differenzfunktion

${displaystyle 1-f}$

behält die Dreiecksungleichung nicht bei und ist daher keine richtige Distanzmetrik, wohingegen

${displaystyle 1-T_{s}}$

ist.

Es besteht die reale Gefahr, dass die Kombination von “Tanimoto-Distanz” definiert mit dieser Formel zusammen mit der Anweisung “Die Tanimoto-Distanz ist eine richtige Distanzmetrik” führt zu dem falschen Schluss, dass die Funktion

${displaystyle 1-f}$

ist in der Tat eine Distanzmetrik über Vektoren oder Mehrfachmengen im Allgemeinen, wohingegen ihre Verwendung in Ähnlichkeitssuch- oder Clusteralgorithmen möglicherweise keine korrekten Ergebnisse liefert.

Lipkus^[6] verwendet eine Definition der Tanimoto-Ähnlichkeit, die äquivalent zu ist

${displaystyle f}$

, und bezieht sich auf die Tanimoto-Distanz als Funktion

${displaystyle 1-f}$

. In der Arbeit wird jedoch klargestellt, dass der Kontext durch die Verwendung eines (positiven) Gewichtungsvektors eingeschränkt wird

${displaystyle W}$

so dass für jeden Vektor EIN in Betracht gezogen werden,

${displaystyle A_{i}in {0,W_{i}}.}$

Unter diesen Umständen ist die Funktion eine geeignete Distanzmetrik, und so bildet ein Satz von Vektoren, der von einem solchen Gewichtungsvektor bestimmt wird, einen metrischen Raum unter dieser Funktion.

Jaccard-Index in Verwirrungsmatrizen für binäre Klassifikationen[edit]

In Konfusionsmatrizen, die für die binäre Klassifikation verwendet werden, kann der Jaccard-Index in die folgende Formel eingerahmt werden:

${displaystyle {text{Jaccard-Index}}={frac {TP}{TP+FP+FN}}}$

wobei TP die wahren Positiven sind, FP die falschen Positiven sind und FN die falschen Negativen sind und TN die wahren Negative sind.^[11]

Siehe auch[edit]

Verweise[edit]

Weiterlesen[edit]

Externe Links[edit]