Jaccard 係数とコサイン類似度の違い

それぞれの定義

Jaccard 係数

Jaccard 係数とは、2 つの集合 $A, B$ の類似度を測るための指標のひとつです。ここでは $J(A, B)$ と書くことにしましょう。ただし $A$ と $B$ がどちらも空集合の場合は考えません。

$$J(A, B) = \frac{|A \cap B|}{|A \cup B|}$$

コサイン類似度

コサイン類似度とは, 2 つのベクトル $a, b$ の類似度を測るための指標のひとつです。ここでは $C(a, b)$ と書くことにしましょう。ただし $a$ か $b$ のどちらかがゼロベクトルのときは考えません。

$$C(a, b) = \frac{a \cdot b}{\|a\| \|b\|}$$

モチベーション

上で見たように、Jaccard 係数は 2 つの集合に対して定義される値であるのに対し、コサイン類似度は 2 つのベクトルに対して定義される値です。したがってそのままでは比較しようがないのですが、集合とベクトルが同一視できる状況においてはその意義が生まれます。

集合とベクトルの対応

ここでは要素数 $n$ の有限集合 $U$ を全体集合とします。$U$ の要素を $u_1, u_2, \ldots, u_n$ のように整列させ、番号を振っておきます。すると以下のルールのもとで集合 $A \subset U$ はベクトル $a \in \{0, 1\}^n$ と一対一に対応します。ただし $a_i$ は $a$ の第 $i$ 成分を表します。

• $u_i \in A \iff a_i = 1$
• $u_i \notin A \iff a_i = 0$

たとえばこんな感じです。

$$A = \{u_1, u_3\} \quad\leftrightsquigarrow\quad a = (1, 0, 1, ..., 0)$$

こんなふうに集合をベクトルにエンコードすれば、集合同士にコサイン類似度を適用することができます。また定義から、得られるコサイン類似度は $U$ の整列の仕方によらないことがわかります。

これが発生する状況

そもそもなぜ Jaccard 係数とコサイン類似度を比較しようと思ったのかというと、このような状況が実際にあったからです。

具体的には implicit feedback を用いた協調フィルタリングで出てきました。ユーザーの閲覧履歴は、閲覧済みアイテムの集合としても表現できますし、エンコードしてベクトルとして扱うこともできます。するとユーザー同士の類似度を測る際に Jaccard 係数とコサイン類似度の両方が使えるわけです。

2つの類似度の違い

では2つの類似度の違いを見ていきましょう。以下では集合 $A, B$ がそれぞれ $a, b$ に対応しているとします。

取りうる値の範囲

定義から Jaccard 係数の範囲は $0 \leq J(A, B) \leq 1$ ですね。

エンコードされたベクトルの各成分は非負であるため、コサイン類似度も同じ範囲 $0 \leq C(a, b) \leq 1$ を取ります。

端点の条件は同じ

まずは $J(A, B) = 0$ となる場合を考えてみます。これは $|A \cap B| = 0$、すなわち $A$ と $B$ の共通部分がないことを意味します。つまり任意の $i$ に対し $a_i$ と $b_i$ がどちらも 1 になることはないということです。したがって $a \cdot b = 0$ となります。逆も確かめられますから、結局以下が成り立ちます。

$$J(A, B) = 0 \iff C(a, b) = 0$$

次に $J(A, B) = 1$ となる場合を考えてみます。これは $|A \cap B| = |A \cup B|$、すなわち $A = B$ を意味します。このとき $C(a, b) = C(a, a) = 1$ となります。逆も確かめられますから、結局以下が成り立ちます。

$$J(A, B) = 1 \iff C(a, b) = 1$$

両指標の大小関係

端点 ($0$ と $1$) を取る条件は等しいことがわかりましたが、それ以外のところではどうでしょうか。詳細は省きますが、2次関数の最大値問題を考えることで以下が確かめられます。

$$J(A, B) < C(a, b)$$

端点の場合と合わせれば $J(A, B) \leq C(a, b)$ が得られます。

単調性はあるのか？

以上により2つの類似度の間には大小関係があることがわかりましが、それよりも気になるのは単調性です。ここでの単調性とは以下の性質のことを言っています (この記事だけの用語です)。

$$J(A, B) < J(A, C) \iff C(a, b) < C(a, c)$$

これが成り立たないとどうなるかというと、Jaccard 係数で測ると $A$ にとって $B$ よりも $C$ のほうが似ているけど、コサイン類似度で測ると $c$ よりも $b$ のほうが似ている、という逆転現象が起きます。

それですぐさま困ることがあるわけではありませんが、例えば推薦アルゴリズムに用いるのであれば、どちらの類似度を選ぶかで推薦結果が変わる可能性があるということになります。

さて結果を言ってしまうと、単調性は成り立ちません。以下が反例です。

$$\begin{align} a &= (1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0)\\ b &= (1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0)\\ c &= (1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1) \end{align}$$

まとめ

集合はベクトルにエンコード可能なので、ベクトル同士の類似度を測るコサイン類似度を集合同士に適用することができます。

しかし単調性は成り立たないため、使う類似度によって推薦結果等が変わる可能性があります。

どっちの類似度を選ぶべきかというのはまた別問題です。みんなどうやって選んでんだろね。