昨日に引き続き、SmartNews開発者ブログの「b-Bit MinHashによる高速かつ省スペースな類似度判定」を参考に、Rubyでb-Bit MinHashを実装してみた。

ビット数は1、ハッシュ関数の個数は128で計算させている。

ただし、1ビット値は最初から50％の確率で衝突するので、単に一致した回数をkで割っただけでは、真のJaccard係数が0の場合でも0.5くらいの推定値が出てきてしまいます。

とのことなので、一致数をハッシュ関数の個数で割った値から0.5を引いて2倍したものを表示させてみた。（calc_jaccardのコメントを外すと表示される）

だいたい0.4に近い値が出るので多分合っているはず。

ベンチマーク的にはMinHashと大差がなかったけれど、popcountの処理をきちんと実装すれば速くなるかもしれない。

ソースコード

require 'murmurhash3'
require 'benchmark'

def init_seeds(num)
    seeds = Array.new
    num.times do
        seeds << Random.rand(999999999)
    end
    seeds
end

def calc_bbitminhash(targets, seed)
    hash_values = Array.new
    targets.each do |str|
         hash_values << MurmurHash3::V32.str_hash(str, seed)
    end
    hash_values.sort[0] & 0b00000001
end

def calc_jaccard(str_a, str_b)
    k = 128
    seeds = init_seeds(k)

    bits_a = 0
    bits_b = 0
    seeds.each do |seed|
        bits_a <<= 1; bits_a |= calc_bbitminhash(str_a, seed)
        bits_b <<= 1; bits_b |= calc_bbitminhash(str_b, seed)
    end

    k - (bits_a ^ bits_b).to_s(2).count("1")
    #2.0 * ((k - (bits_a ^ bits_b).to_s(2).count("1")) / k.to_f - 0.5)
end

puts Benchmark.measure {
    str_a = %w(巨人 中井 左膝 靭帯 損傷 登録 抹消)
    str_b = %w(中井 左膝 登録 抹消 歩行 問題)

    i = 10
    sum = 0.0
    i.times do
        jaccard = calc_jaccard(str_a, str_b)
        sum += jaccard
        puts jaccard
    end
    puts "avg = #{(sum / i.to_f)}"
}

実行結果

% bundle exec ruby bbitminhash.rb 
84
94
97
101
90
92
100
85
95
91
avg = 92.9
  0.010000   0.000000   0.010000 (  0.005646)

# 補正後
0.46875
0.484375
0.4375
0.484375
0.515625
0.546875
0.328125
0.296875
0.578125
0.40625
avg = 0.4546875
  0.000000   0.000000   0.000000 (  0.005636)

まとめ

MinHashとb-Bit MinHashをRubyで実装してみた。

前にLSHを触ったことがあるからか、あまり違和感なく実装することができた。（ちょっと調べてみたところ、ベクトルの近さの指標にjaccard距離を用いたLSH＝MinHashであるらしい。）

SmartNews開発者ブログにも書いてあるけれど、本文抽出や特徴語抽出などの前処理の結果が類似度の計算には結構響いてくると思う。

そういう部分の実装に各サービスのノウハウがありそう。

内部の仕組みを想像しながら勉強すると理解が深まりそうでよさげな感じがする。