第10回

情報システム基礎論２：第 10 回 (担当：古賀)
Jaccard 係数と Min Hash
2014 年 6 月 24 日
レジュメ URL: http://sd.is.uec.ac.jp/koga/lecture/IF2/
今回の講義では集合間の類似検索について講義する。とくに集合間の類似度である Jaccard 係数を用い
た類似検索を取り扱う。
1
Jaccard 係数
３つの集合
C1 = { みかん、りんご、メロン、グレープフルーツ }
C2 = { みかん、いちご、梨、ぶどう }
C3 = { みかん、いちご、梨、桃 }
の類似性を考えてみよう。
Jaccard 係数は集合間類似度の代表例であり、式 (1) により定義される。直観的には 2 集合の共通要素
の割合を表し、値域は 0 から 1 の間。
sim(Ci , Cj ) =
|Ci ∩ Cj |
.
|Ci ∪ Cj |
(1)
上の例では、
sim(C1 , C2 ) =
sim(C2 , C3 ) =
sim(C3 , C1 ) =
1
.
7
3
.
5
1
.
7
Jaccard 係数は文書間の類似性判定やマーケット分析など様々な分野で使われる。
• マーケット分析
商品 Ci に対して、「Ci を購入した客」の集合を考える。Ci と Cj の Jaccard 係数大 → Ci と Cj は
同時に買われる商品
• 文書間の類似性判定
文書 Ci に対して、「Ci に含まれる単語」の集合を考える。
2
集合の 2 値ベクトル表現
集合は要素の種類数を次元とする 2 値ベクトルとして表現できる。例えば、1 章の例では、各 Ci は 8 種
類の果物 { みかん、りんご、メロン、グレープフルーツ、いちご、梨、ぶどう、桃 } を含むかどうかで 8
次元ベクトルとして表現できる。
C1 = (1, 1, 1, 1, 0, 0, 0, 0), C2 = (1, 0, 0, 0, 1, 1, 1, 0), C3 = (1, 0, 0, 0, 1, 1, 0, 1)。
1
Jaccard 係数を用いた類似検索
3
• n: データ数
• d: ベクトルの次元
とする (図 1)。
クエリ q との Jaccard 係数が大きいデータを検索する問題。全てのデータとの Jaccard 係数を計算する
と計算時間は O(nd)。しかも、一般に d は非常に大きい (1 万以上)。
また、Ci は疎ベクトル (多くの 0 を含む) になることが多い。
d
C1
n
Ci 1 1 0 0
...
1 0
Cj 1 1 1 1
...
0 0
Cn
図 1: データベース
4
Min Hash
Min Hash は要素が 0,1 で構成されるベクトルに対する確率的なハッシュ関数で、Jaccard 係数に対する
Locality-Sensitive Hashing である。
4.1
ハッシュ値 mh(Ci ) の計算
1. ランダムにベクトルの列を入れ替える規則 π を決定。
2. Ci の列の入れ替えたベクトルを Ci0 とする。
3. Ci0 を 1 列目から順に見て最初に非零要素が出てくる列を coli とする。
4. Ci のハッシュ値
mh(Ci ) = coli
例：列の入れ替え規則が以下の時、
12345678
↓π
23487165
2
• C20 = (0, 0, 0, 0, 1, 1, 1, 1). mh(C2 ) = 5.
• C30 = (0, 0, 0, 1, 0, 1, 1, 1). mh(C3 ) = 4.
定理 1 Ci と Cj のハッシュ値 mh(Ci ) と mh(Cj ) が一致する確率は Jaccard 係数 sim(Ci , Cj ) と等しい。
P [mh(Ci ) = mh(Cj )] =
|Ci ∩ Cj |
= sim(Ci , Cj ).
|Ci ∪ Cj |
定理 1 から Min Hash は locality sensitive hashing の 1 種。
Jaccard 係数の性質: 各列は Ci と Cj の値によって 4 タイプに分類できる。
タイプ A
タイプ B
タイプ C
タイプ D
sim(Ci , Cj ) =
Ci
1
1
0
0
Cj
1
0
1
0
|A|
.
|A| + |B| + |C|
タイプ D の列は Jaccard 係数とは関係ない。
定理 1 の証明: Min Hash では最初に非零要素が出てくる列まで飛ばす → Ci0 = 0 かつ Cj0 = 0 となる列は
ハッシュ値が一致するかどうかと無関係。つまり、タイプ D の列は無視される。
結局、列をランダムに入れ替えた時、タイプ A,B,C の中でどのタイプが一番最初に出現するかでハッ
シュ値が一致するかどうかが決まる。
• タイプ A → ハッシュ値一致する。
• タイプ B or C → ハッシュ値一致しない。
従って、
P [mh(Ci ) = mh(Cj )] =
5
|A|
.
|A| + |B| + |C|
実装
Min Hash の計算ではデータベースの列の入れ替えを行うが、ハードディスク上に存在するデータベー
スに対しては処理が重く現実的ではない。
実際には列の入れ替えを行わない。その代わりに第 t 列 (1 ≤ t ≤ d) の入れ替え後の列番号 r(t) を記憶
しておく。Ci のハッシュ値は次のようにして計算できる。但し、Ci [t] は Ci の第 t 列の値。
mh(Ci ) =
4 章の例では、
min
{t|Ci [t]==1}
12345678
↓π
23487165
t
r(t)
3
r(t);
1
6
2
1
3
2
4
3
5
8
6
7
7
5
8
4
C2 = (1, 0, 0, 0, 1, 1, 1, 0) なので、mh(C2 ) = min {6, 8, 7, 5} = 5。
利点：集合を d 次元 2 値ベクトルではなく、持っている要素によって表現可能。例えば、C2 = {1, 5, 6, 7}
と表現してもハッシュ値を計算できる。
6
Min Hash を用いた Jaccard 係数の近似計算
列の (ランダムな) 入れ替え規則を変えた k 個のハッシュ関数 mh1 , mh2 , · · · mhk を用意する。そして、
各 Ci に対して k 個のハッシュ値
mh1 (Ci ), mh2 (Ci ), · · · , mhk (Ci )
を得る。Ci と Cj の Jaccard 係数 sim(Ci , Cj ) を k 個のハッシュ値の内、何個が一致するかによって近似計
算できる。
アルゴリズム
match = 0;
for (1 ≤ t ≤ k){
if(mht (Ci )==mht (Cj )) match++;
}
return match
;
k
定理 1 から
1
match
= k · sim(Ci , Cj ) = sim(Ci , Cj ).
E
k
k
本技術は大量の集合間で Jaccard 係数を計算する必要がある時に有用。集合数を n とすると、O(ndk+n2 k)
で全ペア間の Jaccard 係数を近似計算できる。
• O(ndk): ダイジェストの生成
• O(n2 k): ダイジェストを用いた Jaccard 係数の近似計算 7
Min Hash を利用した類似検索
Min Hash を LSH として使用して、Jaccard 係数に対する類似検索が実現できる。Google News の recommendatation system で使われている。
• k 個のハッシュ値を連結して出力する関数を l 個用意する。g1 , g2 , · · · , gl とする。
for 1 ≤ j ≤ l,
gj (Ci ) = (mhj1 (Ci ), mhj2 (Ci ), · · · , mhjk (Ci ))
• l 個のハッシュテーブル T1 , T2 , · · · , Tl を作成する。各 Ci を l 個のハッシュテーブルに登録。テーブ
ル Tj 内で Ci をバケツ b(gj (Ci )) に格納する。
q と類似するデータの検索：
Tj (1 ≤ j ≤ l) のバケツ b(gj (q)) に格納されているデータを q の類似データの候補とする。類似データ候補
に対して、Jaccard 係数を計算し本当に類似しているデータを決定する。
4

Download Report