コサイン距離ベースのLSHをRubyで - <s>gnarl,</s>技術メモ”’<marquee><textarea>￥
参考文献:Web+DB press vol.49 レコメンド特集のPart3など。 アルゴリズムの概要 詳細(特に数学的な)はぐぐれ。 モチベーションとしては、高次元における近傍点探索を高速で行いたい。まじめにやるとどう工夫しても計算量がすごいことになるので、近似で。 どうするかというと、「距離が近いと同じような値になるハッシュ関数」を使う。あるベクトルの近傍を求めたい場合、そのベクトルのハッシュと同じ(もしくは近い)値のハッシュを持つベクトルをテーブルから引いてきて返す。計算量がどうなるかはややこしいけど、とりあえず全部探すよりは速い。 で、どういう関数をハッシュとするのか。これは距離の定義によって異なる。ハミング距離、コサイン距離、ユークリッド距離などにはそういった関数の存在が知られている。 コサイン距離の場合、ランダムなベクトルをいくつか用意して、入力されたベクトルがそれらと似ている
「確率モデルによるwebデータ解析法」8章メモ - <s>gnarl,</s>技術メモ”’<marquee><textarea>￥
昔書いたやつを発掘してきた。また読み返す必要があるなー。 8章は商用アプリケーションの話、レコメンダシステムと顧客行動解析。 ここで扱うレコメンダシステムは、ユーザの行動履歴に基づきユーザに対してアイテムを推薦するようなもの。 興味深い問題として、欠損をすべて0と考えた場合、ユーザiがチェックしなかった項目jに関する行列V中の欠損地の扱いがある。これら欠損データは、必ずしも完全にランダムに欠損しているわけではなく、ユーザが好まない項目に対して「どちらかといえば選ばない」という負のバイアスが 影響していると思われる(Breese,J.S.,Heckerman,D. and Kadie,C. 1988 Empirical analysis of predictive algorithms for collaborative filtering.)。リコメンダシステムに関する多くの研究において、
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
