Programming Collective Intelligence#4

cip reading

間を空けすぎて、前にどこまでやったか覚えてないや・・・Item-Basedか。
そうだそうだ。

Item based filtering

今までやってきたUser based filteringは

  • User数が増えると計算量がだーい爆発
  • Item数が増えると今度はオーバラップが少なく User間の関係が希薄になる＝本当に意味のある集計ができない

じゃあもう少し絞り込みましょう、となって、でも実は難しくも何ともなく、前計算で事前にある程度グルーピングをしちゃいましょう、というよくある手法。
前計算では各itemについてuserの評価値を特徴ベクトルとして「似た者」を抽出する。これは頻繁にはかわらない情報。なので一度計算しておけばしばらくはそのままで良い＝各クエリに対するユーザへのレスポンスは速く見せかけられる。前計算の手続きは

  1. 評価行列(Preference Matrix)を転置して item-matching(本書では Product Matchingと呼んでいる)の準備をする。
  2. すべての itemに対して topMatch を辞書 ItemMatchに格納しておく。

と本当に単純。topMatchの数(n)はこの前計算関数に引数で指定する（sampleコードでのデフォルトは１０）。
で、本番：「指定したユーザーに推奨するitemを出せ」という問題に対して以下のように辞書 ItemMatchを利用して計算する。

  1. 指定したユーザーの評価済みitem(=item_user)を順に見ていく
    1. 各item_userに対して、辞書ItemMatchを調べる→item_userと良く似た評価がされているitemを取得（=item_similar)。
    2. そのitemそれぞれについてスコアを更新

ということをやって、最後に正規化すればできあがり。考えてみれば当たり前の方法であんまり感動できない気もする。
実際にこのアルゴリズムでやる為には ItemMatchの更新タイミングというのを綿密に設計する必要があり（まあ、非同期で更新しても良いので、案外いい加減でも良いのかもしれないけれども）、そっちまで考えると面白い問題なのかもしれにあ。

Using the MovieLens Dataset

例によって例題。 GroupLensプロジェクトとか言うのがミネソタ大学で行われていたらしく。
http://www.grouplens.org/node/12 からダウンロードできる。..
と書いてあるんだけど現在はMovieLensだけは
http://www.movielens.org/
に移動してるっぽい。登録面倒だったのでやってない。全部読み終わって気が向いたらやるかも。

User-Based or Item-Based Filtering

Item-based

  • 速い
  • 疎なデータセットでもかなり正確（の基準がわからない）
    • でも前計算が重い
    • 辞書のメモリ食い

User-based

  • 単純、わかりやすい
  • 前計算なんてマンドクサイことしなくて良い　：頻繁に変更されうるデータセットではこちらが良い
  • 密なデータセットならまあまあItem-basedとおんなじくらい正しいっぽい
    • おっそい。

http://citeseer.ist.psu.edu/sarwar01itembased.html
暇な気分になったら読む。

Exercise

1. Tanimoto score
2. Tag similarity
3. User-based Efficiency
4. Item-based bookmark filtering.
5. Audioscrobbler.