blog.foresta.meこんにちは、 @kz_morita です。
今回は類似度を測る指標について、Cos 類似度と、Jaccard係数 そしてそれを高速に処理するための MinHash について調べたことをまとめていきます。
類似度の計算の必要性
ベクトルの類似度を計算することは、例えばベクトル化された文書間の類似検索であったり、重複するドキュメントを検出したりする際に有効とされています。
今回は、類似度の指標である
- Cos 類似度
- Jaccard 係数
と高速化のための MinHash というアルゴリズムついて見ていきます。
Cos 類似度の定義
Cos 類似度は、ベクトル同士の類似度 (≒ ちかさ) を表すことができる式です。
ベクトル $\vec{a}$ と $\vec{b}$ の Cos 類似度はを表す式は以下のような形になります。
$$ cos \theta = \frac{\vec{a}\cdot\vec{b}}{|\vec{a}||\vec{b}|} = \frac{\sum_{i=1}^{N} a_{i}b_{i}}{\sqrt{\sum_{i=1}^{N} a^2_{i}} \sqrt{\sum_{i=1}^{N} b^2_i}} $$
これは、ベクトルの内積の式である
$$ \vec{a}\cdot\vec{b} = |\vec{a}||\vec{b}| cos \theta $$
から変形したものになります。
つまり二つのベクトルが成す角 $\theta$ の $cos$ の値を類似度として使うということで、その値の範囲は $$ -1 \leq Cos 類似度\leq 1 $$ になり、1に近づくほど角度が近い = 類似度が近いとなり、0 に近づくほど直交していて、-1 ほど反対になるというものになります。
Jaccard 係数について
Jaccard 係数も、ベクトル同士の類似度を表すものになり、以下の式で表されます。
$$ J(\vec{a}, \vec{b}) = \frac{|\vec{a} \cap \vec{b}|}{|\vec{a} \cup \vec{b}|} $$
内容は単純で、ベクトル a とベクトル b の共通部分の要素数を和集合の要素数で割った値になります。 全て一致するベクトル同士では 1 になり、全く被っていない場合は 0 となります。(0 ~ 1 の間の値をとります)
MinHash について
高速化のモチベーション
MinHash は、類似度として Jaccard 係数を考えるときに高速化する手法になります。
例えば、すでにいくつかの文書のベクトルに登録されているとします。 そこに新しく文書が登録された際に、重複した文書かどうか計算したいとします。
DBに入っている大量のベクトルと、新しい文書の Jaccard 係数を求めるのは、DB のレコード分のベクトルと集合演算を行わなければいけないためコストの高い操作になります。
MinHash ではあらかじめハッシュ値の最小値を保存しそれを比較することで Jaccard 係数の推定量として使用しようというアルゴリズムになります。
MinHash の説明
MinHashのアルゴリズムでやることは、以下の通りです。
- k 個のハッシュ関数を用意する
- 比較したい 2 つのベクトルに対して以下の操作を行う
- 各要素に対してハッシュ関数を適用し最小値を記録
- k 個のハッシュ関数全てで上記を行う
- それぞれのハッシュ関数に対して
minhash が一致した件数 / kをJaccard係数の推定量として使用する
二つの文書の比較でハッシュ関数をいくつか用意したとき、具体的に minhash を求めるのは疑似コードで書くと以下のようになるかと思います。
A = [ ... ]
B = [ ... ]
hash_functions = [ ... ]
match = 0
for (h <- hash_functions) {
minhash_A = A.map(a => h(a)).min()
minhash_B = B.map(b => h(n)).min()
if (minhash_A == minhash_B) match += 1
}
// ↓ が類似度
sim = match / hashes.length
k個のハッシュ関数それぞれのベクトルの最小値を求めておけば、ベクトルの要素同士の比較を行わなくて良いため高速化が期待されます。
なぜ MinHash が Jaccard 係数の推定量として使用できるのか
具体例をみながら説明します。
以下の二つのベクトルの類似度を計算したいとします。
$$ A = { 1, 3, 5, 7, 9 }, \space B = { 1, 2, 4, 6, 7, 8 } $$
Jaccard係数などを計算すると以下のようになります。
$$ A \cap B = {1, 7} $$ $$ A \cup B = {1,2,3,4,5,6,7,8,9} $$ $$ |A \cap B| = 2 $$ $$ | A \cup B | = 9 $$ $$ Jaccard(A, B) = \frac{2}{9} $$
これらを踏まえた上で、MinHash のアルゴリズムが何をやっているかみていきます。
MinHash のアルゴリズムでは、各ベクトルの要素に対し、ハッシュ関数を適用し最小値を比較しているのでした。
具体的にみていくために $ A \cap B = {1, 7}$ のうち 1 に着目してみてみます。
特定のhash関数で A と B 両方とも hash(1) が最小値になる場合とは、A と B を合わせた全ての要素の中で hash(1) が一番小さい場合です。
つまり、$A \cup B$ の中で hash(1) が一番小さいということです。
上では、1 に着目しましたが MinHash が一致するということは $A \cap B = {1,7}$ のいずれかがこの条件を満たせば良いわけになります。
そのためこの時に MinHash が一致する確率は、
$$ P[minhash(A) = minhash(B)] = \frac{|A \cap B|}{|A \cup B|} $$
と表すことができます。
これはつまり Jaccard 係数の式そのものになります。
ここで、hash 関数は完全なランダムではないので、いくつか (k 個) この操作を繰り返し平均をとる、つまり
$$ \frac{\sum_{i=1}^k 1[minhash_i(A) = minhash_i(B)]}{k} $$
とすることで、確からしい Jaccard係数の値 (推定量) を得ることができるというわけです。
まとめ
今回は、ベクトルの類似度について Cos 類似度と、Jaccard係数。そして 高速化の手法として MinHash のアルゴリズムをまとめました。
MinHash には色々なパターンがあるらしく実際に実装する際にはさらに調査が必要そうです。