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

ruby

昨日に引き続き、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開発者ブログにも書いてあるけれど、本文抽出や特徴語抽出などの前処理の結果が類似度の計算には結構響いてくると思う。

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

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

RubyでMinHashを実装してみた。

ruby

SmartNews開発者ブログのb-Bit MinHashによる高速かつ省スペースな類似度判定を見て、おもしろそうだったのでMinHashをRubyで実装してみた。

MurmurHash3の実装はmurmurhash3-rubyを使わせてもらった。

% bundle init
% vi Gemfile
gem 'murmurhash3'

% bundle install

で準備完了。

require 'murmurhash3'
require 'benchmark'

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

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

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

    correct = 0.0
    seeds.each do |seed|
        minhash_a = calc_minhash(str_a, seed)
        minhash_b = calc_minhash(str_b, seed)
        correct += 1 if minhash_a == minhash_b
    end

    correct/ k
end

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

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

calc_jaccardのkでHash関数の個数を調整できる。

実行すると

% bundle exec ruby minhash.rb
0.3984375
0.390625
0.4453125
0.5
0.40625
0.4296875
0.4609375
0.4140625
0.3671875
0.4140625
avg = 0.42265625
  0.000000   0.000000   0.000000 (  0.005013)

のようになる

4/9 = 0.4444… となるのが理想なので、だいたい合っていると思う。

結構値がバラつく感じ。

次はb-Bit MinHashを実装してみたいと思う。

「データサイエンティスト養成読本」を読んだ。

book

連休で時間があるうちに積読本をどんどん消化しています。

内容的には機械学習やインフラにまつわることがゴリゴリ書いてあるわけではなく、データサイエンティストの守備範囲やビジネスの話まで幅広く書いてある感じでした。

データサイエンス分野の人たちが使っているツールであったり、この分野を勉強するにあたって抑えておきたい知識を知りたいという人向けに書かれているのかなと思います。

個人的に良かったと思ったのは特別記事の「Fluentd入門」。

fluentdのアーキテクチャやfluentdとtd-agentの関係、growthforecastとの連携まで解説されています。

Fluentdの記事はググればたくさん出てくるんですが、自分が調べた時に結構混乱した記憶があるので、これからFluentdを触り始める人にはこの本の記事を読むのがおすすめです。

Fluentdはアーキテクチャがシンプルで好きなんですが、いざ自分がやりたいことをさせようとするとmatch条件の設定とかでつまづいたりするので、設定パターン集みたいなものがほしいです。

Fluentdはあちこちで使われていると思うんですけど、まとまった書籍はまだ出ていないんですよね。

Fluentdの技術書どこかから出してくれないかなー。

データサイエンティスト養成読本 [ビッグデータ時代のビジネスを支えるデータ分析力が身につく! ] (Software Design plus)

データサイエンティスト養成読本 [ビッグデータ時代のビジネスを支えるデータ分析力が身につく! ] (Software Design plus)

「Webを支える技術」を読んだ。

book

「Backbone.jsガイドブック」を読んだ後にREST周りの知識をもう一度抑えておきたいと思い、積読本となっていたものを読んでみました。

副題のとおり、内容はHTTPやURIに関する話題が中心で、自分としては今まで理解したつもりになっていたところを勉強し直せたのが良かったです。

特に第5部Webサービスの設計はRESTfulなAPIを設計するときに抑えておきたいポイントがまとまっていて参考になりました。

これまでに自分が読んだことのある「Webの仕組み」を解説している本の中では一番わかりやすかったです。

この本を読めば「告白されたときの正しいステータスコードの返しかた」で自信を持って笑えるようになるはずｗ。

（関連するネタがあったと思って、はてブを検索したらもう4年近く前の記事だとわかってちょっとショックを受けた。）

Webを支える技術 -HTTP、URI、HTML、そしてREST (WEB+DB PRESS plus)

Webを支える技術 -HTTP、URI、HTML、そしてREST (WEB+DB PRESS plus)

grunt-contrib-lessでlessファイルのコンパイルを自動化する。

automation

ブログデザインの変更にあたって、lessファイルのコンパイルをgrunt-contrib-lessを使って自動化してみた。

デザインベースは公式のboilerplateを使わせてもらった。

フォルダ構成

boilerplateからboilerplate.lessとlessディレクトリ配下のlessファイルをコピーしてくる。

dist配下にコンパイルしたcssファイルを格納するようにした。

views配下に自分のブログのhtmlファイルをダウロードしてきて、dist配下のcssファイルを読み込むように編集する。

% tree -L 1
 .
├── Gruntfile.js
├── dist
├── less
├── node_modules
├── package.json
├── tachikoma.less
└── views

grunt-contrib-lessのインストール

gruntモジュールのインストールはいつも通り。

% npm install grunt-contrib-less --save-dev

Gruntタスクの編集

lessのoptionsで@importディレティブのディレクトリやソースファイルを指定する。

yuicompressオプションでcssmin.jsを使った圧縮を有効にできる。

% vi Gruntfile.js

module.exports = function (grunt) {
  'use strict';
  var pkg = grunt.file.readJSON('package.json');
  grunt.initConfig({
    pkg: grunt.file.readJSON("package.json"),
    less: {
      development: {
        options: {
          paths: ["less"]
        },
        files: {
          "dist/tachikoma.css": "tachikoma.less"
        }
      },
      production: {
        options: {
          paths: ["less"],
          yuicompress: true
        },
        files: {
          "dist/tachikoma.min.css": "tachikoma.less"
        }
      }
    },
    connect: {
      livereload: {
        options: {
          port: 9000
        }
      }
    },
    watch: {
      html: {
        files: 'views/*.html',
        tasks: [],
        options: {
          livereload: true,
          nospawn: true
        }
      },
      less: {
        files: ['*.less', 'less/*.less'],
        tasks: ['less:development'],
        options: {
          livereload: true,
          nospawn: true
        }
      }
    }
  });
  var taskName;
  for(taskName in pkg.devDependencies) {
    if(taskName.substring(0, 6) == 'grunt-') {
      grunt.loadNpmTasks(taskName);
    }
  }
  grunt.registerTask('live', ['connect', 'watch']);
  grunt.registerTask('default', ['less:development', 'live']);
};

gruntタスクの実行

% grunt

を実行するとlessファイルがコンパイルされて、lessファイルとhtmlファイルが監視対象になったLiveReloadが有効になる。

lessファイルの編集と画面確認を繰り返してデザインを整え終えたら、

% grunt less:production

で圧縮したcssファイルがdist配下に作成される。

あとはできたmin.cssファイルをブログ管理画面で貼り付けれればアップデート完了。

Grunt便利!!