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に載ってたやつをほぼ忠実に実装している方もいるみたいです。

のんびり読書日記
http://d.hatena.ne.jp/mjmania/20090307/1236359739

WEB+DB PRESSで興味をもった人はこちらの方が参考になるかもしれません。コサイン尺度での実装です。

Algorithm::LSHは、色々なハッシュ関数を動的に組み込める設計にしてあるので、コサイン尺度のやつとか追加しようと思うんですが、疲れたから、ちょっと様子見。

興味ある人がいれば、codereposから引っ張って来て自由に弄ってみて下さい。そのままcommitしてくれてオKです。

今日はもう眠いので、そのうちもう少し具体的な解説でもかきます。