Inferring Movement Trajectories from GPS Snippets
- 1. Inferring Movement Trajectories from GPS Snippets Mu Li, Amr Ahmed, Alexander J. Smola 2015.5.13 @WSDM2015読み会 担当：金 秀明
- 2. 概要 スマホやタブレット経由で得られるGPSログと地図情報か ら，ユーザの移動軌跡を推定＆予測するための手法を提案． エネルギーコスト等の理由でGPSログが散発的である点 が難しいところ（GPS Snippet）． 空間と時間の両方をモデル化する • 空間：移動にマルコフ性，観測ノイズに正規分布． • 時間：移動時間に逆正規分布（速度と絡めてポイント）． US cities のデータで性能を確認．
- 3. 問題設定 観測 {Oi}： o1 o2 ok ok+1 ・・・ 緯度，経度，向き，時刻 状態 {Si}： s1 s2 sk sk+1 ・・・ Segment 情報（長さ，高速，レーン数など）
- 4. モデル（空間） sk-1 → i’1 → i’2 → ... → sk → i1 → i2 → ... → sk+1 → → → ok-1 ok ok+1 (1) (2) } (3) (1) 遷移行列： (2) 軌道確率： (3) 観測雑音： l
- 5. モデル（時間） sk-1 → i’1 → i’2 → ... → sk → i1 → i2 → ... → sk+1 → → → ok-1 ok ok+1 (1) (1) 観測雑音（移動時間） 地図から得られる特徴量 !"： 道路形態，レーン数，走行形態，市・州・ZIP，時間帯や曜日，・・・ Data from a road segment
- 6. パラメータの学習 周辺尤度最大化 × Dynamic programming(EM)
- 7. 推定・予測方法 過去の推定 (s-, s+, t given) 将来の予測 (s- given) ": 最尤経路 s- s+ s"- t- t s- t |"-|のミス(p. 330) " "’ すべての経路 " の 所用時間の平均 s " "’ "’’ s- t 経路 " ごとに所要 時間が t となる位 置を計算
- 10. 実験：基礎統計 速度分布 •SFは移動速度が遅い •Salinaは２ピーク ⇒ 主要な高速道路が１つ有り •方向分布が局在 ⇒ 道路の区画レイアウトを反映
- 11. 実験：推定/予測結果 推定 生データ •速度分布は推定側で < 10m/s の部分が消えてる・・・ ⇒ segment の端の赤信号とかの影響はモデルでは segment でつぶしちゃってるので仕方ない． •ラッシュ時の速度が落ちるのは予想通り． •Salina でラッシュの影響が見られない ⇒ 交通の主が高速道路だから．
- 12. 実験：推定/予測結果 • 全軌道データの 30% をテストデータとする． • 過去の軌道の推定：各テスト軌道からランダムにGPS点を抽出し，それを当てる． • 将来の軌道の予測：各テスト軌道の最後のGPS点から最も近いroad segment を当てる． Full-Model: 全乗せ． GPS-speed: 速度を推定せず生のまま使用． common: 軌道IDを特徴量に入れない． Shortest-path: 最短経路のみを考慮
- 13. 実験：推定/予測結果 推定 予測 • SalinaとBoston は精度が良い ⇒ 高速なメインで速度のばらつきが小さいため. • GPS-speedの精度が悪い ⇒ GPS “snippet” 故に観測速度がばらつくため. 特にNew York は交通がぐちゃぐちゃ・・・ • 提案技術の良さが予測タスクで際立っている ⇒ 個々の軌道の特徴的な速度を推定している、 ということは個々の軌道の移動モードを捉えて いるから．