Groonga Advent Calendar 2015の23日目の記事です。
はじめに
GroongaでJaccard係数を計算するプラグインを作る - CreateField Blog こちらの記事では、GroongaでJaccard係数を計算できるプラグインを作りました。しかしながら、毎回すべてのレコードについて類似度を計算すると非常に計算量が多くなってしまいます。
そこで、b Bit MinHashという方法を使って高速にJaccard係数を推定する方法を実装して試してみました。
naoa/groonga-minhash · GitHub
ハッシュ関数にはMurmur3のc port、乱数の生成にはXorShiftを利用しています。
MinHashとは
２つの集合に対するランダムなハッシュ関数による最小ハッシュ値が一致する確率は、Jaccard係数に等しいという性質を持ちます。
こちらでかなりわかりやすく説明されています。
乱択データ構造の最新事情 −MinHash と HyperLogLog の最近の進歩− - iwiwiの日記
www.slideshare.net
これ、結構おもしろい性質ですね。
１文書の集合の要素数をｋ個の最小ハッシュ値に削減することができます。kを大きくすればするほど、正しい確率に近づきます。
b Bit MinHashとは
MinHashでは集合の要素をk個の最小ハッシュ値で表現することができますが、さらに容量削減、演算量削減のため、提案されたのがb Bit MinHashです。b Bit MinHashは最小ハッシュ値の下位bビットのみを保存して演算に使うという方法です。当然ハッシュ値を少ない数値に落としますので衝突しまくります。1ビットなら50%の確率で間違っているはずです。
しかし、そのぶんkを大きくして、衝突確率を考慮して補正することにより、そこそこの精度で高速、且つ空間効率が良くJaccard係数が推定できるとして、良く利用されているようです。
b-Bit MinHashによる高速かつ省スペースな類似度判定 | SmartNews 開発者ブログ
1ビットの場合、ビット演算のみで２つの集合の最小ハッシュ値の一致数を計算できるので、非常に高速に計算できそうです。
精度
実際にどのくらいの精度が得られるか簡単に試してみました。
{A,B,C,D,....}、{B,C,D,.....}と６５次元ぐらいの集合を１つずつずれていくように用意してb=１ビット、k=64のb Bit MinHashでJaccard係数を推定してみます。正しければアルファベット順に類似度が低くなっていくはずです。
[
1000,
[ "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa" ]
],
[
968,
[ "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab" ]
],
[
937,
[ "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae" ]
],
[
937,
[ "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad" ]
],
[
937,
[ "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac" ]
],
[
906,
[ "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah", "ai", "aj" ]
],
[
906,
[ "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah" ]
],
[
906,
[ "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah", "ai" ]
],
[
906,
[ "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af" ]
],
[
906,
[ "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag" ]
],
[
843,
[ "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah", "ai", "aj", "ak" ]
],
[
843,
[ "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "1", "2", "3", "4", "5", "6", "7", "8", "9", "0", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z", "aa", "ab", "ac", "ad", "ae", "af", "ag", "ah", "ai", "aj", "ak", "al", "am" ]
],
類似度は都合により1000倍してます。1000は1です。
B>C>[F,E,D]>[K,I,J,G,H]>[L,N]
と概ね正しい順番が得られています。ただ、結構同じ類似度になってしまっていますね。
上のスライドにあるようにb Bit MinHashで高類似度は狭い範囲でスケッチを比較することにより、少し精度を出すのが難しいようです。*1
ただ、kを128とかもっと増やせば多少改善できそうですし、1ビット*kの数値だけ保存しておけば良いので、空間効率が良く類似度の演算も簡単なので結構使えそうですね*2。
性能
単純にJaccard係数を求めるのと、b Bit MinHashでJaccard係数を推定する速度を比較してみました。
集合の要素数はすべて10です(k個の最小ハッシュ値しか保存してないので集合の要素数は類似度の計算には関係ありません)。
| 文書数 |
Jaccard係数 |
b Bit MinHash (b=1, k=64) |
b Bit MinHash (b=1, k=64) ソートなし |
| 1K |
0.408026218414307 sec |
0.000944852828979492 sec |
- |
| 10K |
3.95593476295471 sec |
0.0039210319519043 sec |
- |
| 100K |
27.2713441848755 sec |
0.034470796585083 sec |
- |
| 1M |
363.50066947937 sec |
0.344359159469604 sec |
0.0878760814666748 sec |
| 5M |
- |
1.81920456886292 sec |
0.420000314712524 sec |
かなりはやいですね。５百万でも2秒かかりません。なお、この2秒は500万件のクイックソートがほとんどの時間を占めています。ソートなしだと0.4秒です。実際は高類似度だけを閾値で切ればいいので、5Mでも0.数秒で上位を計算できそうです。
おわりに
b Bit MinHashを使えば数百万以上の文書数でも高速且つそこそこの精度で類似検索ができることがわかりました。
結構使えそうなので、これを使ってレコメンドとかやってみたいなぁと考えています。
つぶやき
現在コマンドで実装されていますが、スコア関数のほうがselectで使えて使い勝手がいいのかなぁ。対象スケッチをコマンド実行中にキャッシュできればそっちでもいい気がする。
あと重み付きJaccardとかもできないか検討しよう。
上位の部分だけをあとで真のJaccard係数を計算するのもいいかもしれない。
このMinHash結構色々使えそう。たとえば文字Ngramを作って編集距離の前にざっくり文字列の類似度を求めてから編集距離を求めるとあいまい検索がはやくなりそう
