ジャカード指数

Jaccard指数は、サンプルセットの類似性と多様性を測定するために使用される統計です。これは通常、2 つのサイズ (面積または体積) の比率、つまり交差サイズを和集合サイズで割った値( IoU ) で定義されます。

これは、 1884年にカール・ギルバート・グローブによって検証比（v）^[1]として開発され、現在では気象学では臨界成功指数と呼ばれることが多い。^{[2]その後、}ポール・ジャカールによって独立に開発され、当初はフランス語でcoefficient de communauté（コミュニティ係数）と呼ばれ、^{[3] [4]} T. Tanimotoによって再び独立に定式化された。^{[5]そのため、一部の分野では}タニモト指数またはタニモト係数とも呼ばれる。

Jaccard 指数は有限のサンプル セット間の類似性を測定し、共通部分のサイズをサンプル セットの 和集合のサイズで割ったものとして定義されます。

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

設計上、A交差点Bが空の場合、J ( A、  B )=0となることに注意してください。ジャカード指数は、バイナリまたはバイナリ化されたデータが使用されるコンピュータサイエンス、生態学、ゲノミクス、およびその他の科学で広く使用されています。ジャカード指数を使用した仮説検定には、正確な解法と近似法の両方が利用できます。^[6]${\displaystyle 0\leq J(A,B)\leq 1.}$

ジャカード類似度はバッグ、つまり多重集合にも適用されます。これは同様の式を持ちますが^[7]、使用される記号はバッグの交差とバッグの合計（結合ではない）を表します。最大値は1/2です。

${\displaystyle J(A,B)={\frac {|A\cap B|}{|A\uplus B|}}={\frac {|A\cap B|}{|A|+|B|}}.}$

サンプル セット間の不類似性を測定するJaccard距離は、Jaccard 指数の補完であり、Jaccard 指数を 1 から引くか、または同等に、2 つのセットの和集合と積集合のサイズの差を和集合のサイズで割ることによって得られます。

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

Jaccard 距離の別の解釈は、対称差 のサイズと和集合の比率です。Jaccard 距離は、通常、nサンプル セット のクラスタリングと多次元スケーリングのn × n行列を計算するために使用されます。 ${\displaystyle A\mathbin {\triangle } B=(A\cup B)-(A\cap B)}$

この距離はすべての有限集合の集合に対する測定基準である。 ^{[8] [9] [10]}

確率測度を含む測度に対するジャカード距離のバージョンもある。 が測定可能空間上の測度である場合、ジャカード指数は次のように定義される。 ${\displaystyle \mu}$ ${\displaystyle X}$

${\displaystyle J_{\mu }(A,B)={\frac {\mu (A\cap B)}{\mu (A\cup B)}},}$

そしてジャカード距離は

${\displaystyle d_{\mu }(A,B)=1-J_{\mu }(A,B)={\frac {\mu (A\mathbin {\triangle } B)}{\mu (A\カップ B)}}.}$

または の場合、これらの式は適切に定義されていないため、 注意が必要です。${\displaystyle \mu (A\cup B)=0}$${\displaystyle \infty}$

MinHashの最小単位の独立順列局所性敏感ハッシュスキームは、各セットがハッシュ関数の最小値から導出された一定サイズの署名によって表されるセットのペアの Jaccard 類似度指数の正確な推定値を効率的に計算するために使用できます。

それぞれn 個のバイナリ属性を持つ2 つのオブジェクトAとB がある場合、Jaccard 指数はAとB が属性で共有する重複を測定するのに役立ちます。AとBの各属性は 0 または1のいずれかになります。AとBの両方の属性の各組み合わせの合計数は、次のように指定されます。

${\displaystyle M_{11}}$AとB の両方の値が 1 である属性の合計数を表します。

${\displaystyle M_{01}}$Aの属性が 0 で、 Bの属性が 1 である属性の合計数を表します。

${\displaystyle M_{10}}$Aの属性が 1 で、 Bの属性が0 である属性の合計数を表します。

${\displaystyle M_{00}}$AとB の両方の値が 0 である属性の合計数を表します。

各属性はこれら4つのカテゴリのいずれかに該当する必要があり、

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

ジャカード類似度指数Jは次のように与えられる。

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

ジャカード距離d _{J は}次のように与えられる。

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

統計的推論は、ジャカード類似度指数とそれに関連する指標に基づいて行うことができます。^[6] n個の属性を持つ2つのサンプルセットAとBが与えられた場合、重複が統計的に有意であるかどうかを確認する統計テストを実施できます。正確な解は利用可能ですが、 nが増加すると計算コストが高くなる可能性があります。^{[6]推定方法は、}多項分布を近似するか、ブートストラップによって利用できます。^[6]

バイナリ属性に使用する場合、Jaccard 指数は単純な一致係数と非常によく似ています。主な違いは、SMC には分子と分母に項があるのに対し、Jaccard 指数にはないことです。したがって、SMC は相互存在 (属性が両方のセットに存在する場合) と相互不在 (属性が両方のセットに存在しない場合) の両方を一致としてカウントし、それをユニバース内の属性の総数と比較しますが、Jaccard 指数は相互存在のみを一致としてカウントし、それを 2 つのセットの少なくとも 1 つによって選択された属性の数と比較します。 ${\displaystyle M_{00}}$

たとえば、マーケット バスケット分析では、比較する 2 人の消費者のバスケットには、店舗で入手可能なすべての製品のごく一部しか含まれていない可能性があるため、バスケットの類似性がほとんどない場合でも、SMC は通常、非常に高い類似度の値を返します。そのため、このコンテキストでは、Jaccard 指数の方が類似度の適切な尺度になります。たとえば、1,000 個の製品と 2 人の顧客がいるスーパーマーケットを考えてみましょう。最初の顧客のバスケットには塩とコショウが入っており、2 番目の顧客のバスケットには塩と砂糖が入っています。このシナリオでは、Jaccard 指数で測定された 2 つのバスケットの類似度は 1/3 になりますが、SMC を使用すると類似度は 0.998 になります。

0 と 1 が同等の情報 (対称性) を持つ他のコンテキストでは、SMC は類似性のより優れた尺度です。たとえば、性別などのダミー変数に格納された人口統計変数のベクトルは、男性が 0 で女性が 1 と定義されているか、またはその逆であるかに関係なく、性別が類似性に与える影響は等しいはずなので、Jaccard 指数よりも SMC と比較する方が適切です。ただし、対称ダミー変数がある場合は、ダミーを 2 つのバイナリ属性 (この場合は男性と女性) に分割して SMC の動作を再現し、それらを非対称属性に変換して、バイアスを導入せずに Jaccard 指数を使用できます。ただし、対称ダミー変数の場合は、余分な次元を追加する必要がないため、SMC の方が計算効率が高くなります。

と がいずれも実数のベクトルである場合、それらのジャカード類似度指数（ルジカ類似度とも呼ばれる）は次のように定義される。 ${\displaystyle \mathbf {x} =(x_{1},x_{2},\ldots ,x_{n})}$${\displaystyle \mathbf {y} =(y_{1},y_{2},\ldots ,y_{n})}$${\displaystyle x_{i},y_{i}\geq 0}$

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

ジャカード距離（当時はゼルゲル距離とも呼ばれていた）

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

さらに一般化すると、と が測度 の可測空間上の2つの非負可測関数である場合、次のように定義できます。 ${\displaystyle f}$${\displaystyle g}$${\displaystyle X}$${\displaystyle \mu}$

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

ここで、およびは点ごとの演算子です。すると、ジャカード距離は ${\displaystyle \max}$${\displaystyle \min }$

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

すると、例えば、2 つの測定可能な集合 に対して、 となります。ここで、 と は対応する集合の特性関数です。 ${\displaystyle A,B\subseteq X}$${\displaystyle J_{\mu }(A,B)=J(\chi _{A},\chi _{B}),}$${\displaystyle \chi _{A}}$${\displaystyle \chi _{B}}$

上で説明した重み付きJaccard類似度は、Jaccard指数を正のベクトルに一般化します。ここで、集合は指示関数によって与えられたバイナリベクトルに対応します。つまり、 。しかし、Jaccard指数を確率分布に一般化することはなく、集合は一様確率分布に対応します。つまり、 ${\displaystyle x_{i}\in \{0,1\}}$

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

集合の大きさが異なる場合は常に小さくなります。 の場合 、${\displaystyle |X|>|Y|}$${\displaystyle x_{i}=\mathbf {1} _{X}(i)/|X|,y_{i}=\mathbf {1} _{Y}(i)/|Y|}$

${\displaystyle J_{\mathcal {W}}(x,y)={\frac {|X\cap Y|}{|X\setminus Y|+|X|}}<J(X,Y).}$

代わりに、確率分布とそれに対応するサポートセットの間で連続的な一般化は

${\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)}}}$

これは「確率」ジャカードと呼ばれます。^[11]確率ベクトル上の重み付きジャカードに対して、次の境界があります。

${\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)}}}$

ここで、上限は（重み付き）Sørensen–Dice係数です。対応する距離 は、確率分布上の計量であり、非負ベクトル上の 疑似計量です。${\displaystyle 1-J_{\mathcal {P}}(x,y)}$

確率ジャカード指数は、単体の交差面積として幾何学的に解釈されます。単位単体は、合計が 1 になる次元の点の集合であるため、単位単体上のすべての点は、要素上の確率分布に対応します。確率ジャカード指数を幾何学的に導くには、各項目の質量に応じてサブ単体に分割された単位単体として確率分布を表します。このように表された 2 つの分布を重ね合わせ、各項目に対応する単体を交差させると、残った面積は分布の確率ジャカード指数に等しくなります。 ${\displaystyle k}$${\displaystyle k+1}$${\displaystyle k}$${\displaystyle k+1}$

できるだけ衝突するようにランダム変数を構築する問題について考えてみましょう。つまり、およびの場合、を最大化するようにおよび を構築します。2 つの分布だけを個別に見ると、達成できる最大値は で与えられます。ここで、は総変動距離です。ただし、特定のペアを最大化することだけに関心がなく、任意のペアの衝突確率を最大化したいとします。分布 ごとに 1 つずつ、無限の数のランダム変数を構築し、すべてのペア を最大化するように努めることができます。以下で説明するかなり強い意味で、確率ジャカード指数は、これらのランダム変数を揃える最適な方法です。 ${\displaystyle X\sim x}$${\displaystyle Y\sim y}$${\displaystyle X}$${\displaystyle Y}$${\displaystyle \Pr[X=Y]}$${\displaystyle x,y}$${\displaystyle \Pr[X=Y]}$${\displaystyle 1-{\text{TV}}(x,y)}$${\displaystyle {\text{TV}}}$${\displaystyle x}$${\displaystyle \Pr[X=Y]}$${\displaystyle x,y}$

任意のサンプリング法と離散分布に対して、およびであるある に対して、 または のいずれかとなる。^[11]${\displaystyle G}$${\displaystyle x,y}$${\displaystyle \Pr[G(x)=G(y)]>J_{\mathcal {P}}(x,y)}$${\displaystyle z}$${\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)]<J_{\mathcal {P}}(x,z)}$${\displaystyle \Pr[G(y)=G(z)]<J_{\mathcal {P}}(y,z)}$

つまり、サンプリング法では、減少したペアが増加ペアよりも類似している場合、別のペアよりも衝突を少なくすることなく、あるペアよりも多くの衝突を達成することはできません。この定理は、集合の Jaccard 指数 (一様分布として解釈される場合) と Jaccard 確率には当てはまりますが、重み付けされた Jaccard には当てはまりません。(定理では、空間上のすべての分布に対する結合分布を説明するために「サンプリング法」という単語を使用しています。これは、衝突確率としてこれを実現する重み付けされた minhashing アルゴリズムの使用から派生しているためです。) ${\displaystyle J_{\mathcal {P}}}$${\displaystyle J_{\mathcal {P}}}$${\displaystyle J_{\mathcal {P}}}$

この定理は、単体表現を使用した 3 要素分布に関する視覚的な証明を持っています。

タニモト類似度やタニモト距離として説明されるさまざまな形式の関数が、文献やインターネット上に存在します。これらのほとんどはジャカード類似度やジャカード距離の同義語ですが、数学的に異なるものもあります。多くの情報源^[12]は、 IBMテクニカルレポート^[5]を重要な参考文献として引用しています。

1960年10月に出版された「植物を分類するためのコンピュータプログラム」^[13]では、類似度比と派生距離関数に基づく分類方法が紹介されています。これは、「タニモト類似度」と「タニモト距離」という用語の意味に関する最も権威のある情報源であると思われます。類似度比はジャカード類似度に相当しますが、距離関数はジャカード距離と同じではありません。

その論文では、ビットマップ上の「類似度比」が示されています。ここで、固定サイズの配列の各ビットは、モデル化されているプラ​​ントの特性の有無を表します。比率の定義は、共通ビットの数を、いずれかのサンプルで設定されているビット数 (つまり、ゼロ以外のビット数) で割ったものです。

数学的に表現すると、サンプルXとYがビットマップ、がXのi番目のビット、がそれぞれビット演算子、またはビット演算子である場合、類似度比は ${\displaystyle X_{i}}$${\displaystyle \land ,\lor }$ ${\displaystyle T_{s}}$

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

各サンプルが属性のセットとしてモデル化される場合、この値は 2 つのセットの Jaccard 指数に等しくなります。Jaccard は論文では引用されておらず、著者はそれを知らなかったようです。^{[引用が必要]}

Tanimoto は、この比率に基づいて、類似性がゼロでないビットマップに対して定義された「距離」を定義します。

${\displaystyle T_{d}(X,Y)=-\log _{2}(T_{s}(X,Y))}$

この係数は、意図的に距離の測定基準ではありません。これは、互いにまったく異なる 2 つの標本が両方とも 3 番目の標本に類似している可能性を考慮して選択されています。三角不等式の特性を反証する例を簡単に作成できます。

タニモト距離は、しばしば誤ってジャカード距離の同義語として言及されます。この関数は適切な距離メトリックです。「タニモト距離」は、ジャカード距離と混同されるためか、適切な距離メトリックであるとよく言われます。^{[説明が必要] [引用が必要]}${\displaystyle 1-T_{s}}$

ジャカード類似度またはタニモト類似度をビットベクトル上で表現すると、次のように書ける。

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

ここで、同じ計算はベクトルのスカラー積と大きさで表現されます。この表現は、ビットベクトル（各次元の値が0または1）の場合、

${\displaystyle A\cdot B=\sum _{i}A_{i}B_{i}=\sum _{i}(A_{i}\land B_{i})}$

そして

${\displaystyle \|A\|^{2}=\sum _{i}A_{i}^{2}=\sum _{i}A_{i}.}$

これは潜在的に混乱を招く表現です。なぜなら、ベクトル上で表現される関数は、その定義域が明示的に制限されない限り、より一般的だからです。 の特性は、必ずしも に拡張されるわけではありません。特に、差分関数は三角不等式 を保存しないため、適切な距離計量ではありませんが、は です。 ${\displaystyle T_{s}}$${\displaystyle f}$${\displaystyle 1-f}$${\displaystyle 1-T_{s}}$

この式を使用して定義される「タニモト距離」と、「タニモト距離は適切な距離メトリックである」という記述を組み合わせると、関数が実際には一般にベクトルまたはマルチセット上の距離メトリックであるという誤った結論につながり、類似性検索またはクラスタリング アルゴリズムで使用すると正しい結果が得られない可能性があるという実際の危険性があります。 ${\displaystyle 1-f}$

Lipkus ^[9]は、 と同等のタニモト類似度の定義を使用し、タニモト距離を関数 と呼んでいます。ただし、論文では、コンテキストが（正の）重みベクトルの使用によって制限されていることが明確にされており、検討対象の任意のベクトルAに対して、このような状況下では、関数 は適切な距離メトリックであり、そのような重みベクトルによって制御されるベクトルの集合は、この関数の下でメトリック空間を形成します。 ${\displaystyle f}$${\displaystyle 1-f}$${\displaystyle W}$${\displaystyle A_{i}\in \{0,W_{i}\}.}$

バイナリ分類に使用される混同行列では、Jaccard 指数は次の式で表すことができます。

${\displaystyle {\text{Jaccard index}}={\frac {TP}{TP+FP+FN}}}$

ここでTPは真陽性、FPは偽陽性、FNは偽陰性である。^[14]

• 重複係数
• 単純マッチング係数
• ハミング距離
• セーレンセン・ダイス係数は、次式と等価です。および（：ジャカード指数、：セーレンセン・ダイス係数）${\displaystyle J=S/(2-S)}$${\displaystyle S=2J/(1+J)}$${\displaystyle J}$${\displaystyle S}$
• トヴェルスキー指数
• 相関
• 相互情報量。その正規化された計量化された変形は、エントロピー Jaccard 距離です。

• Tan、Steinbach、Kumar によるデータマイニング入門の講義ノート
• Kaggle Dstl 衛星画像の特徴検出 - 評価