WWW2010メモ: GEOSEARCH session

Filed under 学会

Foursquareに代表されるように今後数年はきっとGeographical search/miningが流行るんだろうと思いこのセッションを聴講.そのときのメモ.3つ発表があったが位置情報付きUGCをマイニングするという話がほとんど.Foursquareのように確かに位置情報を使ったサービスが今後数年は流行るんだろうが,”+位置情報マイニング”的な研究ではぶっ飛んで面白いサービスは出てこないだろうなぁ.

来年あたりはFoursquareのデータを使ったマイニングの話が出てきそうな気分.

 

“Collaborative Location and Activity Recommendations with GPS History Data”
Vincent W. Zheng (Hong Kong University of Science and Technology), Yu Zheng (Microsoft Research Asia), Xing Xie (Microsoft Research Asia), Qiang Yang (Hong Kong University of Science and Technology)

売り:

ある位置におけるある活動の人気度を計算するためのモデルの提案.

背景

GPSの普及により位置情報付きUGC情報が増えてきている.
例: 何処どこの店はおいしい,○○の場所では△△が有名

ゴール

位置情報付きアノテーションデータをマイニング・集約して以下の質問に答えられる検索システムを実装

  • 訪問先で何ができるか
  • ○○がしたい場合どこに行くべきか

データモデル

Q. location-activity 関係をどうモデル化するか?
A. “(場所 × 活動) = 実際にそこでそれを行った人数”  という行列

問題: こういう行列を作るとほとんどの要素がspareseになる
解決策: 場所間の類似性,活動間の類似性を考慮する

実際のシステムフロー

  1. GPSログの位置情報をマイニング,クラスタリングして人気のある場所を発見する
  2. 場所名間の類似性,活動間の類似性を計算し,(場所×場所)行列,(活動×活動)行列を作る
  3. 作成した行列を基に「場所にあった活動」「活動にあった場所」を推薦(推薦の基準は人気度,人気度はある場所である活動をしたユーザの数)

特徴的な位置情報の抽出

  • まず滞在時間が長い場所(stay spot)を抽出
  • Stay spotをクラスタリングする by Grid clustering (滞在人数が多いstay spotを中心としてある範囲以内のstay spot集合をクラスタとする??)

場所間,活動間の類似性の計算

  • 場所の類似性: 場所特徴ベクトル間のコサイン類似度を測る(場所特徴ベクトルの属性はレストラン,ショッピング,etcみたいに予め決められた属性.値はたぶんある場所の周辺における各属性の要素の頻度)
  • 活動の類似性: Webページにおける活動名の共起性

感想

  • 質疑にもあったけどGPS情報を使う必要があったのか?それが無くても「○○の場所で△△な活動がどの程度人気があるか」はWebのみからある程度抽出できそう.少なくともそれはベースラインとして必要かと.
  • 手堅い研究.データがあるからできるんだろうなぁ.ストーリー自体は普通.

 

“Find Me If You Can: Improving Geographical Prediction with Social and Spatial Proximity”
Lars Backstrom (Facebook, Inc.), Eric Sun (Facebook, Inc.), Cameron Marlow (Facebook, Inc.)

目的

  • Facebookの友達情報から所在地の分からないFacebookユーザの所在地を予想する
  • 0.1マイル×0.1マイルレベルで所在地を調べる?

解析用データ

  • Facebookユーザの所在地情報(IPアドレス or ユーザが登録したプロフィール情報)

Facebookユーザの所在地に関わる統計データ

  • 3,000,000ユーザがプロフィールに自分の所在地情報を登録 @ US (3%のユーザ)
  • 20%の友達が2マイル以内に済んでいる
  • 50%の友達が12マイル以内
  • 20%の友達が100マイル以上離れたところにいる
  • Xマイル離れたところにいるユーザが実際に友達である確率などもユーザの滞在する年の人口密度別に調査
  • などなど

所在地が未知のユーザの所在地の推定アルゴリズム

  • 仮説: あるユーザの所在地は友達の所在地に近いはず
  • 事前確率: Xマイル離れたところにいるユーザが実際に友達である確率
    # これは既に統計情報として持っている
  • ユーザの所在地間の距離を変数とする確率を考慮して尤度が最大になる位置を所在地が未知のユーザの所在地とする
    直感的な定式化: ターゲットユーザの所在地をluとしたときの尤度: Π p(|lu −lv|) Π (1−p(|lu −lv|))
    # lv: ある友達ユーザの所在地,  第一項: 友達ユーザを考慮,第二項: 非友達ユーザを考慮
  • 実際には人口密度とかなんとか複雑な要素があるし,しかも計算量がとてつもないので最適化された尤度計算方法があるみたい.

結果: 友達の数が16人以上いると70%以上の精度で可能?

感想: Facebookユーザの所在地の統計情報が色々分かる研究として面白かった

 

“Equip Tourists with Knowledge Mined from Travelogues”
Qiang Hao (Tianjin University), Rui Cai (Microsoft Research, Asia), Changhu Wang (Microsoft Research, Asia), Rong Xiao (Microsoft Research, Asia), Jiang-Ming Yang (Microsoft Research, Asia), Yanwei Pang (Tianjin University), Lei Zhang (Microsoft Research, Asia)

目的:  ある位置における特徴的なトピックを旅行UGCコンテンツから抽出

感想:

  • イントロを聴いてすごくつまらない話な気がしたので聞くのを放棄.
  • 論文をちょっとみたらトピックモデルの図が載っていたので,LDAに位置情報に関する変数を増やしたんだろうと思っていたらやっぱりその通りだった…
  • これもいわゆる位置情報を使った典型的なデータマイニング.