Locality Sensitive Hashing に挑んでみた
久々のエントリです。
Locality Sensitive Hashing を perl で使うためのモジュールを書いてみました。Algorithm::LSHと名付けました。
先ほどDeveloper ReleaseとしてCPANにあげましたが、反映されるまで時間かかるので、興味ある方はcodereposからみてください。
Algorithm::LSH
CPAN: http://search.cpan.org/~miki/Algorithm-LSH/
coderepos: http://coderepos.org/share/browser/lang/perl/Algorithm-LSH
超アルファバージョンな状態ですが、そのうちgithubにもupする予定。
そうそう、そう言えば WEB+DB PRESS Vol.49 にレコメンドエンジンの特集があって、その中に偶然にもLocality Sensitive Hashingの話が載っていました!
が、自分が以前から調べていたものとは、なんだか雰囲気が違ってんだよなー。というか、Locality Sensitive Hashing ってハッシュ関数の実装方法が色々あるみたいなんで、ただ単にそれだけの問題かもしれませんが。
とりあえず自分はHamming距離を使ったものでハッシュ関数を書いてみました。unary化とか本当は良くわからんのですが、たまたま参考にしていたサイトとか論文とかがHamming距離だったので、それをすごく勝手な解釈で模倣しています。
ちなみにWEB+DB PRESSに載ってたやつをほぼ忠実に実装している方もいるみたいです。
WEB+DB PRESSで興味をもった人はこちらの方が参考になるかもしれません。コサイン尺度での実装です。
Algorithm::LSHは、色々なハッシュ関数を動的に組み込める設計にしてあるので、コサイン尺度のやつとか追加しようと思うんですが、疲れたから、ちょっと様子見。
興味ある人がいれば、codereposから引っ張って来て自由に弄ってみて下さい。そのままcommitしてくれてオKです。
今日はもう眠いので、そのうちもう少し具体的な解説でもかきます。