![[輪読会]
Gravity of Location-Based Service:
Analyzing the Effects for Mobility
Pattern and Location Prediction
東京大学大学院工学系研究科 修士1年
小島駿](https://image.slidesharecdn.com/reading2020kojimacopy-200729040320/85/Gravity-of-Location-Based-Service-Analyzing-the-Effects-for-Mobility-Pattern-and-Location-Prediction-1-320.jpg)
![Location Prediction
? ユーザが次に訪れる場所を事前に予測
? 位置情報データの蓄積に伴い研究が活発化
? スマートフォンの急速な普及
? Location-Based Service(LBS)の普及
? パーソナルアシスト，都市計画，
マーケティング，公衆衛生など
多くの応用先
[1] Lian, Defu, Vincent W. Zheng, and Xing Xie. "Collaborative filtering meets next check-in location prediction.
" Proceedings of the 22nd International Conference on World Wide Web. 2013.
3
代表的なLBS
Location Predictionのイメージ [1]](https://image.slidesharecdn.com/reading2020kojimacopy-200729040320/85/Gravity-of-Location-Based-Service-Analyzing-the-Effects-for-Mobility-Pattern-and-Location-Prediction-4-320.jpg)
![Location Predictionの課題
? 人間の規則的な移動は予測可能性が高い[2]
? 人はほとんどの時間を自宅、職場、そして頻繁に訪れるいくつかの
場所で過ごし、これらの場所を定期的に行き来している
? ユーザが新しい場所へ行く場合の位置予測は依然として困難
? ユーザは通常の場所よりも新規の場所の情報を必要とするため，
新規場所の位置予測は重要なテーマ
4
しかし
[2] Wang, Yingzi, et al. "Regularity and conformity: Location prediction using heterogeneous mobility data.
" Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 2015.](https://image.slidesharecdn.com/reading2020kojimacopy-200729040320/85/Gravity-of-Location-Based-Service-Analyzing-the-Effects-for-Mobility-Pattern-and-Location-Prediction-5-320.jpg)
![先行研究
? 基本的なフレームワークとしてユーザベースのCFを採用し、影響
を与える要因を追加で考慮して予測精度の向上を目指す
? 地理的要因
? POIの地理的近接性がユーザのチェックイン行動に影響を与える[3]
? 社会的要因
? 信頼できる友人の行動がユーザのチェックイン行動に影響を与える[3]
? “Friend-based Collaborative Filtering”
? 時間的要因
? 1日における時間帯がユーザのチェックイン行動に影響を与える[4]
10
特定のLBS利用ログを位置予測に適用することを検討したものはない
友人同士で映画を一緒に観にいく
昼にレストランを訪れ、夜にバーを訪れる
[3] Ye, Mao, et al. "Exploiting geographical influence for collaborative point-of-interest recommendation.
" Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval. 2011.
[4] Yuan, Quan, et al. "Time-aware point-of-interest recommendation.
" Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval. 2013.
よく行く場所の近くの店に行く](https://image.slidesharecdn.com/reading2020kojimacopy-200729040320/85/Gravity-of-Location-Based-Service-Analyzing-the-Effects-for-Mobility-Pattern-and-Location-Prediction-11-320.jpg)
![論文概要
① 大規模なチェックインデータを用いて、特定のLBSがユーザの
移動パターンにどのような影響を与えているか定量的に検証
② LBSに固有のチェックイン場所の傾向を反映した新しい位置予
測手法を提案し，LBSが位置予測の精度に与える影響を分析
11
[仮説]
特定のLBSの使用を考慮することで新規位置予測の精度が向上する](https://image.slidesharecdn.com/reading2020kojimacopy-200729040320/85/Gravity-of-Location-Based-Service-Analyzing-the-Effects-for-Mobility-Pattern-and-Location-Prediction-12-320.jpg)
![チェックイン回数
非ユーザーと比べて，
Pokemon Goユーザは4.43倍，
Instagramユーザは約4分の1
15
CFにおいて，データ密度が高いほど予測性能は高くなる[5]
→Pokemon Goユーザに関しての予測性能は高くなると
予想される
[5] Su, Xiaoyuan, and Taghi M. Khoshgoftaar. "A survey of collaborative filtering techniques." Advances in artificial intelligence 2009 (2009).](https://image.slidesharecdn.com/reading2020kojimacopy-200729040320/85/Gravity-of-Location-Based-Service-Analyzing-the-Effects-for-Mobility-Pattern-and-Location-Prediction-16-320.jpg)
![チェックイン場所
? 各場所 ? についてリフト値[6] ???? ? ?
? を計算
? 各LBSごとに，ユーザの各場所への訪れやすさをスコア化
16
[6] Geng, Liqiang, and Howard J. Hamilton. "Interestingness measures for data mining: A survey.
" ACM Computing Surveys (CSUR) 38.3 (2006): 9-es.
LBSごとにユーザのチェックイン場所に偏りがあるかどうか
???? ? ?
? =
? ? ? ?
? ? ? ? ? ? ? + ? ? ? ? ? ? ?
(1)
? ?：Pokemon Goユーザー or Instagramユーザー
? ?：LBS非ユーザー
? ? ? ：ユーザーが場所 ? を訪れた割合
? ? ：ユーザーの割合](https://image.slidesharecdn.com/reading2020kojimacopy-200729040320/85/Gravity-of-Location-Based-Service-Analyzing-the-Effects-for-Mobility-Pattern-and-Location-Prediction-17-320.jpg)
![? 正規化したリフト値で上位20箇所を抽出した結果
ポケモンセンター
公園 景勝地 史跡
チェックイン場所
17
イベント会場
LBSごとにユーザのチェックイン場所に特徴的な傾向
[Pokeon Go] [Instagram]](https://image.slidesharecdn.com/reading2020kojimacopy-200729040320/85/Gravity-of-Location-Based-Service-Analyzing-the-Effects-for-Mobility-Pattern-and-Location-Prediction-18-320.jpg)
![基本的なUser-based Collaborative Filtering[4]
? ユーザ ? とユーザ ? の類似度 ??,?
? ユーザ ? が場所 ? を新しく訪れるかどうかの予測スコア ??,?
20
ユーザによるPOIへのチェックインのグラフ表現[3]
??：各POI ?：全POI集合
??,?：ユーザ ? が場所 ? を訪れたかどうか ([0,1])
??,? =
? ?∈? ??,? ? ?,?
? ?∈? ??,?
2
? ?∈? ? ?,?
2
(5)
??,? =
? ?∈? ??,? ? ?,?
? ?∈?
??,?
(4)
? ?：各ユーザ
?：全ユーザ集合](https://image.slidesharecdn.com/reading2020kojimacopy-200729040320/85/Gravity-of-Location-Based-Service-Analyzing-the-Effects-for-Mobility-Pattern-and-Location-Prediction-21-320.jpg)
![提案手法の検証 – 評価指標と評価方法
? 評価指標
precision@N：推薦をしたN箇所のうち実際に訪れた割合
recall@N ：全テストデータのうち正しく推薦した場所の割合
accuracy@N：少なくとも1箇所は正しく推薦できたユーザーの割合
? 評価方法
? 3つの評価指標に基づき，N=1, 5, 10, 20でそれぞれスコア算出
? 算出したスコアを提案手法とベースライン手法とで比較
? 2つのベースライン手法
① 基本的なUser-based Collaborative Filtering
② 地理的要因を考慮したUser-based Collaborative Filtering[4]
? POI間の距離を考慮に入れたチェックインの条件付き確率を計算
? 計算コストが高いためPokemon Goユーザについてのみ実行
23](https://image.slidesharecdn.com/reading2020kojimacopy-200729040320/85/Gravity-of-Location-Based-Service-Analyzing-the-Effects-for-Mobility-Pattern-and-Location-Prediction-24-320.jpg)
Gravity of Location-Based Service:Analyzing the Effects for Mobility Pattern and Location Prediction
- 1. [輪読会] Gravity of Location-Based Service: Analyzing the Effects for Mobility Pattern and Location Prediction 東京大学大学院工学系研究科 修士1年 小島駿
- 2. 書誌情報 ? タイトル Gravity of Location-Based Service: Analyzing the Effects for Mobility Pattern and Location Prediction ? 著者 ? Keiichi Ochiai, … (NTT DOCOMO, 東京大学) ? 会議 ? ICWSM2020 Best Paper Award ? https://aaai.org/ojs/index.php/ICWSM/article/view/7316 ? 選定理由 ? 人の位置情報データを用いた研究をしている ? Location Predictionへの興味 1
- 3. 背景 2
- 4. Location Prediction ? ユーザが次に訪れる場所を事前に予測 ? 位置情報データの蓄積に伴い研究が活発化 ? スマートフォンの急速な普及 ? Location-Based Service(LBS)の普及 ? パーソナルアシスト，都市計画， マーケティング，公衆衛生など 多くの応用先 [1] Lian, Defu, Vincent W. Zheng, and Xing Xie. "Collaborative filtering meets next check-in location prediction. " Proceedings of the 22nd International Conference on World Wide Web. 2013. 3 代表的なLBS Location Predictionのイメージ [1]
- 5. Location Predictionの課題 ? 人間の規則的な移動は予測可能性が高い[2] ? 人はほとんどの時間を自宅、職場、そして頻繁に訪れるいくつかの 場所で過ごし、これらの場所を定期的に行き来している ? ユーザが新しい場所へ行く場合の位置予測は依然として困難 ? ユーザは通常の場所よりも新規の場所の情報を必要とするため， 新規場所の位置予測は重要なテーマ 4 しかし [2] Wang, Yingzi, et al. "Regularity and conformity: Location prediction using heterogeneous mobility data. " Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining. 2015.
- 6. 新規場所の位置予測アプローチ ? 協調フィルタリング（Collaborative Filtering : CF） ? レコメンデーションシステムが未訪問の場所ごとに訪問確率を計算 5 場所1 場所2 場所3 場所4 場所5 ユーザXとの 類似度 ユーザX 0 1 0 0 1 1.000 ユーザA 1 0 0 0 0 ユーザB 0 1 1 0 1 ユーザC 0 1 1 1 0 ユーザD 1 1 1 0 1 予測確率 ①ユーザのチェックインデータを取得
- 7. 新規場所の位置予測アプローチ ? 協調フィルタリング（Collaborative Filtering : CF） ? レコメンデーションシステムが未訪問の場所ごとに訪問確率を計算 6 場所1 場所2 場所3 場所4 場所5 ユーザXとの 類似度 ユーザX 0 1 0 0 1 1.000 ユーザA 1 0 0 0 0 0.167 ユーザB 0 1 1 0 1 0.800 ユーザC 0 1 1 1 0 0.500 ユーザD 1 1 1 0 1 0.612 予測確率 ②チェックインデータに基づきユーザ間の類似度を計算
- 8. 新規場所の位置予測アプローチ ? 協調フィルタリング（Collaborative Filtering : CF） ? レコメンデーションシステムが未訪問の場所ごとに訪問確率を計算 7 場所1 場所2 場所3 場所4 場所5 ユーザXとの 類似度 ユーザX 0 1 0 0 1 1.000 ユーザA 1 0 0 0 0 0.167 ユーザB 0 1 1 0 1 0.800 ユーザC 0 1 1 1 0 0.500 ユーザD 1 1 1 0 1 0.612 予測確率 ③ターゲットのユーザに対して似ているユーザを抽出
- 9. 新規場所の位置予測アプローチ ? 協調フィルタリング（Collaborative Filtering : CF） ? レコメンデーションシステムが未訪問の場所ごとに訪問確率を計算 8 場所1 場所2 場所3 場所4 場所5 ユーザXとの 類似度 ユーザX 0 1 0 0 1 1.000 ユーザA 1 0 0 0 0 0.167 ユーザB 0 1 1 0 1 0.800 ユーザC 0 1 1 1 0 0.500 ユーザD 1 1 1 0 1 0.612 予測確率 0.40 1.00 0.30 ④似ているユーザのデータを元に未訪問場所の訪問確率を算出
- 10. 新規場所の位置予測アプローチ ? 協調フィルタリング（Collaborative Filtering : CF） ? レコメンデーションシステムが未訪問の場所ごとに予測確率を計算 9 場所1 場所2 場所3 場所4 場所5 ユーザXとの 類似度 ユーザX 0 1 0 0 1 1.000 ユーザA 1 0 0 0 0 0.167 ユーザB 0 1 1 0 1 0.800 ユーザC 0 1 1 1 0 0.500 ユーザD 1 1 1 0 1 0.612 予測確率 0.40 1.00 0.30 ⑤訪問する新規場所を予測
- 11. 先行研究 ? 基本的なフレームワークとしてユーザベースのCFを採用し、影響 を与える要因を追加で考慮して予測精度の向上を目指す ? 地理的要因 ? POIの地理的近接性がユーザのチェックイン行動に影響を与える[3] ? 社会的要因 ? 信頼できる友人の行動がユーザのチェックイン行動に影響を与える[3] ? “Friend-based Collaborative Filtering” ? 時間的要因 ? 1日における時間帯がユーザのチェックイン行動に影響を与える[4] 10 特定のLBS利用ログを位置予測に適用することを検討したものはない 友人同士で映画を一緒に観にいく 昼にレストランを訪れ、夜にバーを訪れる [3] Ye, Mao, et al. "Exploiting geographical influence for collaborative point-of-interest recommendation. " Proceedings of the 34th international ACM SIGIR conference on Research and development in Information Retrieval. 2011. [4] Yuan, Quan, et al. "Time-aware point-of-interest recommendation. " Proceedings of the 36th international ACM SIGIR conference on Research and development in information retrieval. 2013. よく行く場所の近くの店に行く
- 13. ① LBSユーザの行動分析 12
- 14. Dataset ? ユーザのチェックインデータ ? Twitter経由でFoursquareとInstagramのチェックインデータを収集 ? 日本語のTweetをもとに日本国内のPOIを抽出 ? LBSユーザの識別方法 ? Pokemon Go ? プロフィールに“pokemon go”などの表記 ? Pokemon Goに関連するツイートを3回以上 ? Instagram ? Instagram経由でツイートを1回以上 13
- 15. Dataset ? 集計期間 ? 2018年1月4日?2018年7月15日 ? 収集したデータ 14 ユーザ数 チェックイン件数 総数 161,963 7,118,598 Pokeon Goユーザ 667 154,985 Instagramユーザ 86,897 1,517,121
- 16. チェックイン回数 非ユーザーと比べて， Pokemon Goユーザは4.43倍， Instagramユーザは約4分の1 15 CFにおいて，データ密度が高いほど予測性能は高くなる[5] →Pokemon Goユーザに関しての予測性能は高くなると 予想される [5] Su, Xiaoyuan, and Taghi M. Khoshgoftaar. "A survey of collaborative filtering techniques." Advances in artificial intelligence 2009 (2009).
- 17. チェックイン場所 ? 各場所 ? についてリフト値[6] ???? ? ? ? を計算 ? 各LBSごとに，ユーザの各場所への訪れやすさをスコア化 16 [6] Geng, Liqiang, and Howard J. Hamilton. "Interestingness measures for data mining: A survey. " ACM Computing Surveys (CSUR) 38.3 (2006): 9-es. LBSごとにユーザのチェックイン場所に偏りがあるかどうか ???? ? ? ? = ? ? ? ? ? ? ? ? ? ? ? + ? ? ? ? ? ? ? (1) ? ?：Pokemon Goユーザー or Instagramユーザー ? ?：LBS非ユーザー ? ? ? ：ユーザーが場所 ? を訪れた割合 ? ? ：ユーザーの割合
- 18. ? 正規化したリフト値で上位20箇所を抽出した結果 ポケモンセンター 公園 景勝地 史跡 チェックイン場所 17 イベント会場 LBSごとにユーザのチェックイン場所に特徴的な傾向 [Pokeon Go] [Instagram]
- 19. その他 ? チェックイン時間 Instagramユーザは非ユーザに比べて ? 早朝から正午のチェックインが少ない ? 夜のチェックインが多い ? 連続するチェックイン間の距離 ? Pokemon GoとInstagramのユーザは非ユーザに比べて より近くの場所にチェックインする傾向 18
- 21. 基本的なUser-based Collaborative Filtering[4] ? ユーザ ? とユーザ ? の類似度 ??,? ? ユーザ ? が場所 ? を新しく訪れるかどうかの予測スコア ??,? 20 ユーザによるPOIへのチェックインのグラフ表現[3] ??：各POI ?：全POI集合 ??,?：ユーザ ? が場所 ? を訪れたかどうか ([0,1]) ??,? = ? ?∈? ??,? ? ?,? ? ?∈? ??,? 2 ? ?∈? ? ?,? 2 (5) ??,? = ? ?∈? ??,? ? ?,? ? ?∈? ??,? (4) ? ?：各ユーザ ?：全ユーザ集合
- 22. ? Lift-weighted User-based Collaborative Filtering ? 対象ユーザが特定のLBSを利用しているか否かを考慮 ? 同じLBSのユーザは似たような場所を訪れる傾向があると仮定 ? 基本的なUser-based CFにリフト値を組み込む ? 1回の乗算が加わるだけなので計算コストが低い ? LBSユーザ ? が場所 ? を新しく訪れるかどうかの予測スコア ??,? (?) ??,? (?) = 1 + ???? ?? × ? ?∈? ? ??,? ? ?,? ? ?∈? ? ??,? (6) cf. 従来のCFの予測スコア ??,? = ? ?∈? ??,? ? ?,? ? ?∈? ??,? (4) 提案手法 21 ???? ?? ：LBSごとに計算した場所 ? のリフト値 ? ?：LBSユーザ集合 LBSユーザのチェックイン場所に偏りがある性質を位置予測に反映
- 23. 提案手法の検証 – タスクとデータセット ? タスク ? 入力：ユーザのチェクイン履歴データ ? 出力：LBSごとに，各ユーザが新しく訪れそうな場所をN個推薦 ? データセット ? 行動分析で用いたデータセットをフィルタリング ? 5箇所以上訪れたユーザのデータを抽出 ? 20人以上のユーザが訪れたPOIを抽出 ? ユーザが訪問したPOIの20%をテストデータとしてランダム抽出 ? 残り80%のチェックインデータで学習 22 ユーザ数 チェックイン件数 Pokeon Goユーザ 542 12,063 Instagramユーザ 28,971 22,513 (N = 1, 5, 10, 20)
- 24. 提案手法の検証 – 評価指標と評価方法 ? 評価指標 precision@N：推薦をしたN箇所のうち実際に訪れた割合 recall@N ：全テストデータのうち正しく推薦した場所の割合 accuracy@N：少なくとも1箇所は正しく推薦できたユーザーの割合 ? 評価方法 ? 3つの評価指標に基づき，N=1, 5, 10, 20でそれぞれスコア算出 ? 算出したスコアを提案手法とベースライン手法とで比較 ? 2つのベースライン手法 ① 基本的なUser-based Collaborative Filtering ② 地理的要因を考慮したUser-based Collaborative Filtering[4] ? POI間の距離を考慮に入れたチェックインの条件付き確率を計算 ? 計算コストが高いためPokemon Goユーザについてのみ実行 23
- 25. ? precision@1, recall@1, accuracy@1を除いた全てのケースでLift- weighted User-based CFが最も良いスコア ? 両側t検定でそれぞれの手法に有意な差があることが確認された ? ?：有意水準 0.05 ? ?：有意水準 0.005 ? 最大で20%の予測性能向上が確認された (recall@5) 検証結果 - Pokemon Goユーザー 24
- 26. 検証結果 - Instagramユーザー ? 全てのケースでLift-weighted User-based CFがUser-based CFを上 回った ? 両側t検定で有意な差があることが全てのケースで確認された ? 有意水準 0.001 ? 最大で43.9%の予測性能向上が確認された (recall@5) 25
- 27. 結論 ? 特定のLBS利用者と非利用者では移動パターンが異なることがわ かった ? LBSに固有のチェックイン場所の傾向を反映した新しい位置予測 手法を提案した ? 提案手法を用いると，Pokemon GoとInstagramの利用者は，非利 用者と比較して，それぞれ最大20.0%と43.9%高い新規位置予測精 度を達成できることがわかった 26
- 28. 今後の課題 ? チェックイン場所以外のLBSに固有な要素(チェックイン回数， チェックイン時間帯，連続チェックイン間の距離など)も考慮した 位置予測手法の構築 ? Pokemon GoやInstagram以外のLBS利用者の移動効果分析 27