ジャカール指数

ジャカール指数（じゃかーるしすう、）は、標本集合のと多様性を測るための統計量である。一般には、2つの大きさ（面積や体積）の比、すなわち共通部分の大きさを和集合の大きさで割った値として定義され、和集合上の共通部分（intersection over union、IoU）とも呼ばれる。

この概念は1884年にグローブ・カール・ギルバートによって、地質学的予測評価の文脈における「検証比」として最初に導入された。現在では気象学においてクリティカル・サクセス・インデックスと呼ばれることが多い。その後、によって独立に発展させられ、当初はフランス語で（共同体係数）と名付けられた。さらに、タフィー・タダシ・タニモト（Taffee Tadashi Tanimoto）によっても独立に定式化された。そのため、分野によっては谷本指数（Tanimoto index）や谷本係数（Tanimoto coefficient）とも呼ばれる。

概要ジャカール指数は、有限で空でない標本集合間の類似度を測るもので、共通部分の大きさを和集合の大きさで割った値として定義される。

ジャカール指数は、2つの集合間の重なりを正規化した尺度として解釈できる。ここで共通部分は共有された要素を、和集合は相異なる要素全体を表す。定義よりとなる。集合とに共通の要素が無ければ共通部分は空集合となり、であるからとなる。もう一方の極端な例は2つの集合が等しい場合で、このときであるからとなる。ジャカール指数は、二値データまたは二値化されたデータが用いられる計算機科学、生態学、ゲノミクスなどの分野で広く使われている。

ジャカール指数を用いた仮説検定については、厳密解と近似手法の双方が利用できる。ジャカール類似度は多重集合（バッグ）にも適用でき and p. 76–77 in an earlier version.、同様の式で表せるが、使われる記号はバッグの共通部分とバッグの和（和集合ではない）を表す。この場合の最大値は1/2である。

ジャカール距離は標本集合間の非類似度を測るもので、ジャカール指数を補完する尺度であり、1からジャカール指数を引くか、あるいは同等に、2つの集合の和集合と共通部分の大きさの差を和集合の大きさで割ることで得られる。

ジャカール距離の別の解釈として、対称差の大きさと和集合の大きさの比とみなす方法がある。ジャカール距離は、n 個の標本集合のクラスタリングや多次元尺度構成法のために行列を計算する際によく用いられる。これらの距離尺度はクラスター分析において類似した観測値をグループ化するためによく使われる。

この距離は、すべての有限集合の族の上の距離（メトリック）である。

ジャカール距離には、確率測度を含む測度に対する版も存在する。を可測空間上の測度とすると、ジャカール指数は次のように定義される。

また、ジャカール距離は次のように定義される。

この定義はまたはの場合には well-defined ではない。

MinHash（最小独立置換に基づく局所性鋭敏型ハッシュ方式）を用いると、各集合をハッシュ関数の最小値から導かれる固定長の署名で表現することで、集合対のジャカール類似度指数の正確な推定値を効率的に計算できる。

ジャカール指数は、現代のデータマイニング応用における大規模かつ疎なデータセットの分析に特に有用である。

非対称二値属性の類似度 2つの対象 A と B がそれぞれ n 個の二値属性を持つとき、ジャカール指数は A と B が属性において共有する重なりを測る有用な尺度となる。A と B の各属性は0または1のいずれかを取り得る。A と B 双方の属性の組み合わせごとの総数は次のように表される。

は、A と B の両方が値1を持つ属性の総数を表す。は、A の属性が0で B の属性が1である属性の総数を表す。は、A の属性が1で B の属性が0である属性の総数を表す。は、A と B の両方が値0を持つ属性の総数を表す。

0 1 0 1

各属性はこれら4つの区分のいずれか1つに必ず該当するため、

となる。

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

ジャカール距離 dJ は次のように与えられる。

ジャカール類似度指数、および関連する指標に基づいて統計的推測を行うことができる。n 個の属性を持つ2つの標本集合 A と B が与えられたとき、その重なりが統計的に有意かどうかを検定できる。厳密解は存在するが、n が大きくなるにつれて計算コストが高くなり得る。多項分布による近似、またはブートストラップ法による推定手法も利用できる。

単純一致係数（SMC）との違い二値属性に用いる場合、ジャカール指数はと非常によく似ている。主な違いは、SMCが分子・分母に項を含むのに対し、ジャカール指数はこれを含まない点である。すなわちSMCは、両方の集合に属性が存在する場合（相互存在）と両方の集合に存在しない場合（相互不在）の両方を一致とみなし、全体の属性数と比較するのに対し、ジャカール指数は相互存在のみを一致とみなし、2つの集合のうち少なくとも一方に選ばれた属性の数と比較する。

例えばマーケットバスケット分析では、比較したい2人の消費者のバスケットが、店にある全商品のごく一部しか含まないことがある。そのためSMCは、バスケット同士がほとんど似ていない場合でも非常に高い類似度を返すことが多い。これはが一般に大きくなる疎なデータセットでは不適切となり得るため、そのような文脈ではジャカール指数の方がより適切な類似度尺度となる。例えば、1000種類の商品を扱うスーパーマーケットと2人の顧客を考える。1人目の顧客のバスケットには塩と胡椒が、2人目の顧客のバスケットには塩と砂糖が入っているとする。この場合、ジャカール指数で測った2つのバスケットの類似度は1/3となるが、SMCを用いると類似度は0.998になる。

一方、0と1が等価な情報を持つ（対称的な）他の文脈では、SMCの方が優れた類似度尺度となる。例えば性別のようなダミー変数として格納された人口統計変数のベクトルは、男性を0・女性を1とするか、あるいはその逆とするかによらず性別が類似度に与える影響が等しくなるべきであるため、ジャカール指数よりもSMCで比較する方が適切である。ただし、対称的なダミー変数がある場合でも、ダミーを2つの二値属性（この例では男性・女性）に分割することで非対称属性に変換し、バイアスを導入することなくジャカール指数を用いてSMCと同様の挙動を再現することもできる。もっとも、対称的なダミー変数の場合には、余分な次元を追加する必要がない分、SMCの方が計算効率に優れる。

ジャカール指数は、属性の存在がその不在よりも情報量が多いとみなされる非対称な二値データや有無データに一般的に用いられる。このようなデータでは、共有された不在は無情報として扱われ、計算から除外される。このためこの尺度は、ある特徴の出現がその非出現よりも意味を持つ疎な二値データに特に適している。一方、対称的な二値変数については、共有された存在と共有された不在の両方を数える単純一致係数のような尺度の方が好まれる場合がある。共同不在を含めるか除外するかという類似度尺度間の違いは、数値分類学や分類学の文献で広く議論されてきた。ジャカール指数は次のように定義される。

ここでは両方の値が1である属性の数、は A のみが1である属性の数、は B のみが1である属性の数である。

重み付きジャカール類似度と距離

とを、すべての実数値がを満たす2つのベクトルとするとき、それらのジャカール類似度指数（このときルジチカ類似度とも呼ばれる）は次のように定義される。

またジャカール距離（このときゾルゲル距離とも呼ばれる）は

さらに一般化すると、とが測度を持つ可測空間上の2つの非負可測関数であるとき、次のように定義できる。

ここでとは各点ごとの演算子である。このときジャカール距離は

となる。例えば、2つの可測集合に対してが成り立つ。ここでとはそれぞれの集合の指示関数である。

2つのベクトルに対する重み付きジャカール類似度指数の計算は、通常データを一度だけ走査すればよく、次元数をとすると計算量はの線形時間となる。データサイエンスの応用では、非ゼロ要素のみを反復処理することで疎なベクトルに対して最適化されることが多く、これにより高次元データセットの処理時間が大幅に削減される。この最適化により計算量はとなる。ここでは非ゼロ属性の数である。# O(k) の計算量のための擬似コード function jaccardIndex(vector_A, vector_B): intersection_sum = 0 union_sum = 0

# すべてのユニークなキーを取得する all_keys = unique_keys(vector_A.keys() + vector_B.keys())

for key in all_keys: val_a = vector_A.get(key, 0) val_b = vector_B.get(key, 0)

intersection_sum += min(val_a, val_b) union_sum += max(val_a, val_b)

return intersection_sum / union_sum 処理時間をさらに削減するため、MinHashingや局所性鋭敏型ハッシュといった手法を用いて、コンパクトな署名によって指数を近似することもある。これらのアルゴリズム上の工夫により、データ量や次元数が増加しても類似度尺度の拡張性と効率性が保たれる。

確率ジャカール類似度と距離

上記の重み付きジャカール類似度は、集合が指示関数（すなわち）で与えられる二値ベクトルへとジャカール指数を一般化したものである。しかし、集合が一様確率分布（すなわち以下）に対応する場合へのジャカール指数の一般化にはなっていない。

これは、集合の大きさが異なる場合には常により小さい値となる。であり、であるとき、

となる。

代わりに、確率分布とそれに対応する台集合との間で連続的な一般化として、次のものがある。

これは「確率」ジャカールと呼ばれる。確率ベクトル上の重み付きジャカールに対して、次の上下限を持つ。

ここで上限は（重み付き）ソレンセン・ダイス係数である。対応する距離は、確率分布上の距離（メトリック）であり、非負ベクトル上の擬距離（プソイドメトリック）である。

確率ジャカール指数には、単体同士の共通部分の面積としての幾何学的解釈がある。単位 -単体上のすべての点は個の要素上の確率分布に対応する。これは単位 -単体が、和が1になる次元の点の集合であるためである。確率ジャカール指数を幾何学的に導くには、確率分布を、各項目の質量に応じて部分単体に分割された単位単体として表現する。このように表現した2つの分布を重ね合わせ、各項目に対応する単体同士の共通部分を取ると、残る面積が分布の確率ジャカール指数に等しくなる。

確率ジャカール指数の最適性

互いにできるだけ多く一致するように確率変数を構成する問題を考える。すなわち、、であるとき、を最大化するようにとを構成したいとする。2つの分布のみを単独で見た場合、達成できる最大のはで与えられる。ここでは全変動距離である。しかし、その特定の1組を最大化することだけに関心があるのではなく、任意の組の衝突確率を最大化したいとする。分布ごとに1つずつ、無限個の確率変数を構成し、すべての組についてを最大化することを試みることができる。以下で述べるかなり強い意味において、確率ジャカール指数はこれらの確率変数を整合させるための最適な方法である。

任意の標本抽出法と離散分布について、もしであるならば、かつであるような z が存在し、またはのいずれかが成り立つ。

すなわち、どのような標本抽出法も、ある組においてより多くの衝突を達成しようとすると、それよりの下でより類似した別の組においてより少ない衝突しか達成できなくなる。この定理は（一様分布として解釈した場合の）集合のジャカール指数と確率ジャカールについて成り立つが、重み付きジャカールについては成り立たない。（この定理では「標本抽出法」という語を、ある空間上のすべての分布にわたる同時分布を表すために用いている。これは、衝突確率としてこれを達成する重み付きMinHashアルゴリズムの利用に由来するためである。）

この定理には、単体表現を用いた3要素分布上での視覚的証明がある。

谷本類似度と距離

谷本類似度・谷本距離として説明されるさまざまな形の関数が、文献やインターネット上に見られる。これらの大半はジャカール類似度・ジャカール距離の同義語であるが、中には数学的に異なるものもある。多くの文献For example は、IBMのテクニカルレポートを原典として引用している。

1960年10月に発表された「植物を分類するためのコンピュータプログラム」において、類似度比とそこから導かれる距離関数に基づく分類手法が示されている。これが「谷本類似度」および「谷本距離」という用語の意味について、最も権威ある出典であると考えられる。この類似度比はジャカール類似度と等価であるが、距離関数はジャカール距離とは異なる。

谷本による類似度と距離の定義

その論文では、ビットマップ上で「類似度比」が与えられている。固定長配列の各ビットは、モデル化されている植物における、ある特徴の有無を表す。この比の定義は、共通のビット数を、いずれかの標本で立っている（すなわち非ゼロの）ビット数で割ったものである。

数学的に表すと、標本 X と Y がビットマップであり、が X の i 番目のビットであり、がそれぞれ論理積（AND）・論理和（OR）のビット演算子であるとき、類似度比は次のようになる。

各標本を属性の集合としてモデル化した場合、この値は2つの集合のジャカール指数に等しい。この論文ではジャカールは引用されておらず、著者らはジャカールの研究を知らなかった可能性が高い。

谷本はさらに、この比に基づく「距離」を、類似度が非ゼロであるビットマップに対して次のように定義している。

この係数は、意図的に距離のメトリックにはなっていない。これは、互いに大きく異なる2つの標本が、いずれも第3の標本と類似しているという可能性を許容するために選ばれている。三角不等式の性質を反証する例を作ることは容易である。

谷本距離のその他の定義

谷本距離は、しばしばジャカール距離の同義語として言及される。この関数は正しい距離のメトリックである。実用上、谷本距離は正しい距離のメトリックとしてのジャカール距離と有害な形で混同されることがある。

ジャカール類似度または谷本類似度をビットベクトル上で表現する場合、次のように書くことができる。

これは同じ計算をベクトルのスカラー積と大きさの言葉で表現したものである。この表現は、ビットベクトル（各次元の値が0か1のいずれかである場合）については次が成り立つという事実に依拠している。

および

これは紛らわしい表現になり得る。というのも、ベクトル上で表現されたこの関数は、その定義域を明示的に制限しない限り、より一般的なものになるからである。の性質は必ずしもには及ばない。特に差分関数は三角不等式を保存しないため、正しい距離のメトリックではないが、はそうである。

「谷本距離」がこの式で定義されるということと、「谷本距離は正しい距離のメトリックである」という主張とが組み合わさることで、関数が実際にはベクトルや多重集合一般にわたる距離のメトリックであるという誤った結論に導かれてしまう危険が実際に存在する。この誤解により、類似度検索やクラスタリングアルゴリズムでの利用において正しい結果が得られない場合がある。

Lipkusはと等価な谷本類似度の定義を用い、谷本距離を関数として言及している。ただし論文内では、その文脈が（正の）重みベクトルの使用によって制限されており、考慮されるどのベクトル A についてもであることが明確にされている。このような条件下では、この関数は正しい距離のメトリックとなり、そのため、そのような重みベクトルに支配されるベクトルの集合は、この関数の下で距離空間をなす。

二値分類の混同行列におけるジャカール指数二値分類で用いられる混同行列において、ジャカール指数は次の式で表すことができる。

ここで TP は真陽性、FP は偽陽性、FN は偽陰性である。

ジャカール指数の二値分類の式は、予測された陽性の結果が実際の陽性の結果とどれだけ一致するかを測る。これは、モデルが真陽性であると予測したケースが、実際の陽性ケースとどれだけ重なっているかを示す。ジャカール指数が高いほど、予測が実際の結果に近いことを意味する。

ジャカール指数は、混同行列の要素を用いて定義できる重なりの指標である。真陽性は、陽性と予測され実際にも陽性であるケースを表し、両群の重なりを生み出す。偽陽性は、陽性と予測されたが実際にはそうでないケースである。同様に、偽陰性は陰性と予測されたが実際には陽性であるケースである。ジャカール指数は、真陽性を関連情報の集合と比較する。 +混同行列予測陽性予測陰性実際陽性TPFN実際陰性FPTN ジャカール指数は、予測結果を実際の結果と比較する際に有用である。二値分類とジャカール指数を併用することで、予測モデルがどれだけ信頼できるかを説明しやすくなる。この手法は多くの分野で用いられており、医学における検査でも一般的に使われている。

計算機科学とグラフ理論への応用計算機科学において、ジャカール指数はグラフ内の頂点間の類似度を、それぞれの隣接集合を比較することで測るために用いられる。2つの頂点が与えられたとき、その類似度は近傍の共通部分の大きさを、それらの和集合の大きさで割ることで計算される。この尺度は、、コミュニティ検出、グラフ分類などで広く用いられ、ネットワーク中の2つのノード間に辺が形成される可能性を推定する指標として機能する。

2つの頂点間のジャカール類似度の計算は、以下のようにそれぞれの隣接集合を用いて表すことができる。// JavaScriptのコード: function jaccardSimilarity(graph1, graph2){ const numNodes1 = graph1.length; const numNodes2 = graph2.length; let similarity = 0;

// 両方のグラフのすべてのノードの組を反復する for(let i = 0; i < numNodes1; i++){ for(let j = 0; j < numNodes2; j++){ // 近傍集合の共通部分と和集合の大きさを計算する const intersectionSize = intersection(graph1[i],graph2[j]).length; const unionSize = union(graph1[i],graph2[j]).length;

// ジャカール類似度を計算し、合計に加える similarity += intersectionSize / unionSize;

// 合計類似度をノード対の数で割って平均を求める return similarity / (numNodes1 * numNodes2); }

// 2つの配列の共通部分を計算する補助関数 function intersection(a, b) { return a.filter(value => b.includes(value)); }

// 2つの配列の和集合を計算する補助関数 function union(a, b){ return [...new Set([...a, ...b])]; }

上記は、隣接リストに対する集合演算に基づく実装例である。実際には、隣接リストのようなグラフ表現が、共通部分と和集合の計算を効率化するために用いられる。大規模なグラフでは、すべての頂点対にわたって類似度を計算することは計算コストが高くなり得る。プログラマーは、この計算の全コストを負担しないよう近似手法を用いることがある。

ジャカール指数

Źródło i licencja