糞糞糞ネット弁慶

読んだ論文についてメモを書きます.趣味の話は http://repose.hatenablog.com

Collaborative Location and Activity Recommendations With GPS History Data (WWW 2010) 読んだ

概要

Collaborative Location and Activity Recommendations With GPS History Data - Microsoft Research
位置情報にまつわる情報推薦の研究をサーベイする必要が生じており,真っ先に読むべき論文っぽかったので読む.
位置 (location) からそこでの行動 (activity),行動から位置,という2種類の推薦を実現する.

方法

使う情報は3種類.
location x activityの行列における欠損値を予測するために,location x feature の行列と, activity x activity の correlation に関する行列を使う.
それぞれの行列の構成法を以下に述べる.

location x activity matrix

まずGPSデータから location を取得する.生のデータを時系列順に並べて連続する2点が一定時間内かつ一定距離内にある集合に対して,それらの平均座標を stay point とする.その上で stay point の集合をクラスタリングして region という単位にする.
region へ変換するためのクラスタリングは d x d メートル (実験では 300m ) の grid を考えてそこの近傍を greedy にクラスタに変換していく.何故このような手法を取るかというと,stay point の集合から region を構成するときに k-means などでは region の広さ (size) を制約に取ることができない,と主張している (あまりに広い stay point をひとつの region に変換するのはよくない,ということだろう).
これで生の位置情報を region という単位に変換する.

その上で, region に紐付いたコメントの中から特定の単語 (e.g. delicious, restaurant) を抽出し,それを activity (e.g. Food and Drink) に紐付ける.そうすると, region ごとに activity 次元のベクトルが構成される.これが location x activity matrix.
論文で採用された activity は Food and Drink, Shopping, Movie and Shows, Sports and Exercise, Tourism and Amusement の5種類.どういう単語がどの activity に紐付くか,という点については明らかにされていない.

location x feature matrix

続いて, location x feature matrix.
ある region の領域,すなわち region のプラスマイナス d/2 メートルの矩形において,そこに含まれる POI のカテゴリを数え上げ,TF-IDF で重み付けする.
そうすると, location x feature (cateogory) の matrix ができあがる.

activity x activity correlation matrix

2つの activity で AND 検索を行い,そのヒット数を加工する.
行列の要素
この時 は i と j の AND 検索のヒット数.

推定

location x activity matrix はスパースなので,これを推定して予測に用いる.
手法は,3つの行列をまとめて因子分解する.
具体的には location x activity matrix を X ,location x feature matrix を Y ,activity x activity correlation matrix を Z とすると
という感じで,それぞれの共通する軸で因子行列を揃えて低次元表現してやる.
目的関数としては,各行列の因子分解から再構成した時の誤差の最小化と,因子行列 U/V/W にL2正則化をかける.

同じ著者の同じデータを使った論文が同年の AAAI にも出ていたはずなのでそれもあとで読む.