LARS: A Location Aware Recommender Systemを読んだ
ICDE2012のBest papersになった"LARS: A Location Aware Recommender System"を読んだのでメモ。
http://www.icde12.org/Site/?page_id=418
内容としては、ざっと言うと、位置情報付きのレーティング(評価したユーザの位置が分かっている)や、位置情報付きのアイテムなどを上手く使って、スケーラブルで精度の高い推薦システムを作るよーっていう内容。
- モチベーション
- 位置情報サービス(foursquareやtwitter,facebookなど)の普及によって、位置情報を考慮した推薦システムが求められるようになった。
- 位置情報を加味した評価情報には以下の3つがある。これらを上手く使ってスケーラブルかつ精度の高い推薦システムを作る。
- spatial user ratings for non-spatial items: 評価したユーザの位置は分かっているが、アイテムの位置は分からない(そもそもない)
- e.g.) 自宅で、読んだ本の評価
- non-spatial user ratings for spatial items: 評価したユーザの位置は分からないが、アイテムの位置は分かる
- e.g.) 以前訪れたレストランの評価
- spatial user ratings for spatial items: 評価したユーザの位置も、アイテムの位置も分かる
- e.g.) レストランの評価をその場で
- spatial user ratings for non-spatial items: 評価したユーザの位置は分かっているが、アイテムの位置は分からない(そもそもない)
- 位置情報を加味した評価情報には次の二つの特性がある
- Preference locality: アイテム(例えば映画)に対する評価は地域ごとに異なる
- 推薦対象ユーザがいる場所ごとに推薦すれば精度が上がるはず!
- Travel locality: ほとんどのユーザは近くにある場所にしか訪れない(foursquareのチェックインなど)
- 推薦対象ユーザから遠いアイテムは推薦対象に入れない(スケーラブル!)
- Preference locality: アイテム(例えば映画)に対する評価は地域ごとに異なる
- 貢献
- Preference localityとTravel localityを考慮に入れた推薦システムの構築
- 推薦対象ユーザの位置情報を加味すると、多大な計算コストがかかってしまうため、pyramid structureという構造を取り入れて計算コストを削減
- pyramid structureの逐次更新方法も示す
- 推薦対象ユーザと全アイテムとの距離を計算するのにはこれもまた計算コストがかかってしまうため、全てのアイテムと距離計算を行わずにすむアルゴリズムを示す(Early termination)
- Foursquare、MovieLens(ユーザのZIPコード付き)のデータを用いて実験をし、提案システムが従来のものよりスケーラブルで精度が高いことを示す
- モデル
- 基本的に協調フィルタリング(CF)と同じ
- 入力に推薦対象ユーザの現在位置も必要となるところが違う
- 推薦対象ユーザの現在位置に近い所で行われた評価情報のみを考慮してモデルを構築する(Pyramid structure)
- 推薦対象ユーザの現在位置から遠いアイテムは推薦対象に入れない(Early termination)
- 扱えるクエリとしてはSnap-shot query(一回の入力でひとつの出力)とContinuous queryを想定
- Pyramid structure
- Early Termination
- 入力された推薦対象ユーザから遠いアイテムは推薦対象としない
- これによって、計算コストの削減ができるが、そもそもすべてのアイテムとユーザの距離を計算していてはコストが高い
- すべてのアイテムと距離計算をしなくてすむアルゴリズムを提案(余白が・・・)
- 評価実験
- だいぶ良くなったよ!