The 28th Annual Conference of theJapanese Society for ArtificialIntelligence, 2014
- 1 -
手法
行動軌跡
ン検出
時空間情報
視化
Detection of Trajectory Patterns and Visualization of Spatio-Temporal Information Based on a Data
Stream Approach
王
一驄
*1
関
和広
*1
原
邦昭
*1
Yicong Wang Kazuhiro Seki Kuniaki Uehara
*1
神戸大学大学院
情報学研究科計算科学専攻
Department of Computational Science, Graduate School of System Informatics, Kobe University
As the rapid increase of mobile GPS devices such as smartphones, it is meaningful to mine or analyze the massive trajectory data streams from those devices. Though there are many algorithms that can find patterns from massive static trajectory data or a dynamic data stream by a batch process, what we need now is a new algorithm that can deal with a massive data stream with limited resources. Our proposed algorithm is aimed at discovering the place at which people always stop when they moves or the place which is becoming crowded from massive trajectory data stream by online process.
1.
研究背景
1.1
人の流れプロジェクト
近年 防災や防犯 ン 交通 都市計
い 時々刻々 変動 人々 動 面的
把握 必要性 出 い [PF-project 2011]
東京大学空間情報科学研究 ン 人 流
行わ い 大量 人々 流
関 品質 確保 そ 処理 共通 処理
基 や 処理技術 あ 方 い 概観 研究者や実
務者 対象 時空間 ビ 実現 目指
あ 本研究 提供 人 移動
軌跡 実験用 利用 い
2008年 10月 1日一日 人 移動軌跡 あ 一日当
量 70GByte 内訳 ユ ID 時刻 経緯
度 性 年齢 職業 交通手段 構成 い
1.2
既存ア
ゴ
ズム
近年 DenStream [Cao 2006] DBscan 基 く
場 い DenStream 検索半径 十分 設
定 移動軌跡 ータ 人 密度 高い場所 見 け
あ DenStream 扱 う
得 パターン あ 地点 密度 高いあ
い 低い あ 時点 静的 情報 過 い 人 単
集 動 い場合 人々 動 関 頻出 ン
見 い 本研究 求 う パターン 動的 情
報 人 密度 増え い 場所 人 集 場所
あ 例えば 短い時間間隔 あ 場所 大量 人 流入
場所 大 交通問題 生 う
状況 見 本研究 目的 あ
一方 人 移動軌跡 頻 出 ン 見 け
T-pattern miner [T-pattern miner] 呼ば ソ あ T-pattern miner 文 献 [Trajectory Pattern
Mining 2007] 基 い い T-pattern miner
処 理 前提 適用
い 本 研 究 用 い 人 移 動 軌 跡 一 日 間
70GByte 単 純 処 理
70GByte 必要 消費 抑
え 扱 う オン ン型 ン
頻度計算 必要
1.3
頻出パターンの検出
文献 [Anand 2010] 頻出 ン
検出 手法 提案 い 手法 目的
現 各 ン 頻度 計算 あ
新 い 重 大 特徴
あ 具体的 各 ン 関
い 分け 例えば
ン ン ”a”, ”b”, ”c” ”a”
表現 作 考え 具体的
i番目 ン ン ”a” ”a”
i番目 1 そう け ば0 以
Stream
Stream: c b a b a ⋯ ⋯ time
以 う 変換
Substream"a"= 0 0 1 0 1⋯ ⋯
Substream"b"= 0 1 0 1 0⋯ ⋯
Substream"c"= 1 0 0 0 0⋯ ⋯
各 ン 頻度 Popularity
Popularity"a"= 0∙c4+ 0∙c3+ 1∙c2+ 0∙c1+ 1∙c0+⋯ ⋯
Popularity"b"= 0∙c4+ 1∙c3+ 0∙c2+ 1∙c1+ 0∙c0+⋯ ⋯
Popularity"c"= 1∙c4+ 0∙c3+ 0∙c2+ 0∙c1+ 0∙c0+⋯ ⋯
先頭 5 個 ン ン
列 各 ン Popularity 考え
Popularity"a"=c2+1
Popularity"b"=c3+c
Popularity"c"=c4
Popularity"a" > Popularity"b" > Popularity"c"
連絡先：王 一驄，神戸大学大学院 情報学研究科，神
戸市灘区六 1-1 ，[email protected]
The 28th Annual Conference of theJapanese Society for ArtificialIntelligence, 2014
- 2 -
a い時
stream
先頭 i番目 ン ン a 時Stream ン ン aの時
Stream ン ン a い時
"c" 出現回数 1回 あ "a"や"b"
少 いこ "a" "b" 両方 2 回出現し い
"a" 最近出現した popularity 高い いう事実
一致し い Popularity 計算 数式 表
Popularity
a=
aict−i ti=0
c 近い定数 例えば1-10
-7
at−i= 10
手 法 出現 回数 多 最近出現 ン ン
高い Popularity 実際 入力 計算
式 極 簡単 形 実現 わ あ
時点ｔ ン a Popularity Popularitya@t
Popularitya@t+1= c∙Popularitya@t+δ
Popularitya@0= 0 あ δ 以 う
定義
δ= 1 0
以 式 ア ゴ ム 入 過去 保存
Popularity 計算 う 以 式
基 い 本 提案
2.
提案手法
大量 移動軌跡 入力 一
……
(x
t, y
t), (x
t+1, y
t+1)
……
う 流 人 動
ン 表 あ ータ 人 軌
跡 止 断 検討 時間
順 流
(x
t-2, y
t-2)
≠
(x
t-1, y
t-1)
=
(x
t, y
t)
○
1
(xt, yt) 止 断 実装 時
一 変数 構成 ン
視 新 い(xt, yt) 来 ば 式○1
を用い 人 止まった う を判断す
地図 出現 適当 m∙n個
分け 本稿 辺長 50ｍ 設定 い
新 い ン ン 考え 新 い
ン 全部 m∙n種類 1.3 節
1 元 考え x, y
2 元 拡張 各 Popularity 計算 い
実装 ン (xt, yt) 相当す
移動軌跡 止 検出 1.3 節 手順 各
Popularity 計算 具体的 (xt, yt) 相当
Popularity 定数 c け 1 足 そ 同時
Popularity c け う ば 人
立 止 Popularity 他 比べ 大 く
例 し 図 う あ 移動軌跡 右上
止まった場合 右上 PopularityUR＝PopularityUR*c+1
他 Popularityelse= Popularityelse*c
図 Popularity 計算
以 動作 表 擬似 示
表 Popularityを計算す プロ タイプ
stop-point = the cell which (xt, yt) fall at;
for obj in cells[m][n]{
if(obj==stop-point) obj.popularity= cell.popularity*constant+1;
else obj.popularity*=constant; }
表 点 あ
第一 一 移動軌跡 止 断 後
べ popularityをアップ ー す た 計算時
間 Ο(m*n)を 要 す 地 図 大 い場合 計算
時間 削減 必要 あ
第 Popularity 出現回数 出現時刻 要素
影響 け 出 現回数 影響 方 大 い 例 えば
A駅 Popularity 何時間 高 最近
10分間 A駅 遠 い場所 B 件 起
場合 B 人 集ま 可能性 高い 本ア ゴ ム
A駅 Popularity 依然 B 遥 高い
動 頻出 ン 見 い
以 問題 解決 地図 分
割 Popularity 計算時間 減
過去 影響 大 いう問題
対 最近 計算 方法 考え えば
過去 10分間 計算 場合 10 分間
ン け Array List 後 保 存
Array List 先頭 現在時刻 10分前 相当 先
頭 当 Popularity c
10
を引く 以上
操 作 先 頭 ー タ を 削除 す 先頭
10分間前 各 及 影 響 除去
擬似 表 ペ 示
手法 処理 10分間前 各
及 影響 除去 表 比べ
計算量 増や 前10分間 保存
いう特徴 あ
最後 本 計算時間 い 分析
数 n 数 m 空
The 28th Annual Conference of theJapanese Society for ArtificialIntelligence, 2014
- 3 -
い ン ン 保存用変数 3 示 変数 1
必要 ン Ο(n)
表 最近 ータを考慮したプロ タイプ
initialize Array List databuffer; for (xt, yt) in data stream{
top-point = the cell which (xt, yt) fall at;
add (stop-point, timestamp) to databuffer;
while(timestamp of the 1st element of databuffer == current time - 10 minutes){
(the cell which the 1st element of databuffer point to).popularity -= c^10;
remove first element of databuffer; }
for obj in subarea{
if (obj==stop-point) obj.popularity= obj.popularity*constant+1;
else obj.popularity*=constant; }}
時間的 考え 一 ン ン 式○1 断
一 ン ン 対 時間 Ο(1)
一 ン ン 対 時間 考え 理
扱う 通常 異
わ 扱う
ン ン 来 前 直 前 ン ン 関 計算
終わ 重要 あ
扱う 一 ン ン 対 時間
評価指標
Popularity 保存 行列 い 空間的
考え m 個変数 あ Ο(m) 時
間的 考え べ popularity
時間 Ο( 数)
全体的 考え Ο(m+n) 一
ン ン 対 時間 Ο( 数) あ
例えば 東京都全域 入力 50万 場合 考え
東京都全域 面積 2,188km2 辺長 50m
最 低2188*106/502*4Byte(Float)+ 5*105*4*28Byte(Float*2*3+Int)=56MByte 10分間前
保存 Array List 考え 人 流
提供 東京 一日当 70GByte
10分間当 量 0.486GBｙte
ン け 全部 保存 負荷 高 い
3.
実験結果
今回 実験 東京大学空間情報科学研究 ン
人 流 人 移動軌跡 使 特
JR東京駅 中心 半径3ｋｍ以内 一日分 入力
ン ン ユ 数 76,685人 あ Google Maps
基 い 計算結果 視的 出力 図2 示
図 昼12時頃 新橋駅付近 様子 あ 10分間 新
橋駅 降 乗客 予想通 多 深い黒
い 同時 銀行新橋中央支店 所 新橋駅
薄い あ 同 時間帯 銀行 来客 多
表 い 人 密度 いえば 新橋駅 銀行
高い DBScan系 ン
ば 新橋駅 見 銀行
そ 見 い 予想
図2 本 動 ン 検出
実際 DenStreamア ゴ ムを用い 昼 12時頃
新橋駅付近 計算 結果 図 示 銀
行新橋中央支店 所 予想通 見 い
い
図3 DenStream 動 ン 検出
4.
今後について
本稿 人 移動軌跡 人 止 場所 見 け
今後 見 場所 基 い 人 動 ン 検
出 研究 行う予定 あ
参考文献
[Anand 2010] Anand Rajaraman and Jeffrey David Ullman: Mining of Massive Datasets, Cambridge University Press, 2010.
[PF-project 2011] http://pflow.csis.u-tokyo.ac.jp/index-j.html [T-pattern miner] http://sourceforge.net/projects/t-patterns/ [Trajectory Pattern Mining 2007] F. Giannotti, M. Nanni, D.
Pedreschi and F. Pinelli: Trajectory Pattern Mining, Proc. of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 332-339, 2007. [Cao 2006] Feng Cao, Martin Ester, Weining Qian and Aoying
