DEIM Forum 2013 F9-4

移動軌跡からの MPR 及び時間帯の検出
伊藤和馬†

黄宏軒††

川越 恭二††† 立命館大学大学院 情報理工学研究科 〒 525–8577 滋賀県草津市野路東 1-1-1†† 立命館大学 情報理工学部 〒 525–8577 滋賀県草津市野路東 1-1-1
E-mail: †kito@coms.ics.ritsumei.ac.jp, ††huang@fc.ritsumei.ac.jp, † † †kawagoe@is.ritsumei.ac.jp
あらまし

近年の GPS デバイスの普及により，位置情報からオブジェクトの移動軌跡を抽出し，経路を発見する研究が盛んに行われている．その中で，不慣れな地域での移動を支援するために，与えられた始点から終点までを結ぶMost Popular Route（以下，MPR）を検出する研究がある．しかし，与えられた大量の移動軌跡集合から MPR を検出するため，検出した MPR が実際には MPR ではない特定の時間帯が存在する可能性がある．そこで本稿では，時間情報を含む大量の移動軌跡から特定の時間帯で有効な MPR を検出する方法を提案する．提案する方法では，最小単位の時間セグメントに関して MPR を検出したのち，条件を満たす隣接時間セグメントを反復的に結合していくことで，時間帯と MPR を求める．
キーワード

移動軌跡，位置情報，時間帯，時間セグメント

Detection of MPR and its Eﬀective Time Segments from Trajectories
Kazuma ITO† , Hung-Hsuan HUANG†† , and Kyoji KAWAGOE††† Graduate School of Science and Engineering, Ritsumeikan University
Nojihigashi 1―1―1, Kusatsu, Shiga, 525―8577 Japan†† Colledge of Information Science and Engineering, Ritsumeikan University
Nojihigashi 1―1―1, Kusatsu, Shiga, 525―8577 Japan
E-mail: †kito@coms.ics.ritsumei.ac.jp, ††huang@fc.ritsumei.ac.jp, † † †kawagoe@is.ritsumei.ac.jp
Abstract There have been a lot of studies on route planning based on moving object trajectories extracted fromposition devices. A method to find the Most Popular Route (MPR) was lately proposed. The MPR is the route
between two locations on which many users frequently move. The MPR can be found by observing the past trajectories of many users. The found MPR can be utilized by a user who is unfamiliar in a certain region to movearound in the area eﬀectively. However, in the existing method to find the MPR, the MPR is found only from all
the past trajectories, without any consideration on the time of trajectories. Therefore, there is a case where thefound MPR is not the actual MPR in a specific time interval. In this paper, we propose a method for detecting
proper time segments in which the MPR is eﬀective. The time segments can be obtained by iteratively combining
adjacent smaller time segments according to the proposed combination rules.
Key words Trajectory, Location Information, Time Zone, Time Segment

1. は じ め にいる．MPR は，与えられた始点から終点までを結ぶ経路の中で，最も多くのオブジェクトが実際に移動したことを示す経路

近年，スマートフォンや GPS ナビゲーションデバイス等である．MPR は，比較的信頼性の高い安全な経路と考えられの GPS デバイスの普及に伴い，膨大な量の位置情報を取得るため，不慣れな地域を移動する場合に，MPR は非常に有益することが容易になった．また，位置情報のシーケンスとしな情報であると考えられる．て移動軌跡を表し，ユーザにとって有益な経路を発見する研究 [1] [2] [3] [4] [5] [6] が行われている．

しかし，MPR は時間帯に影響されるという特徴がある．例
えば，京都の主要な通りの一つである河原町通りは，夕方にはZaiben ら [1] は，複数オブジェクトの過去の移動軌跡から，タクシーや市内バスが多く渋滞しやすいが，夜の時間帯ではMost Popular Route(以下，MPR) を検出する方法を提案して車通りも少なくなる．また，外環と呼ばれる京都の環状道路で

3. 時間帯を考慮した MPR(MPR-T) の検出
MPR を検出する際には，適切な時間帯指定が必要である．
しかし，単純に時間帯を指定して MPR を検出する場合，以下の 2 つの問題点がある．
図 1 MPR-T 検出の例

は，ショッピングに出かける家族が多い休日は渋滞が発生するが，平日は車の流れもスムーズである．つまり，時間帯や曜日によって，MPR は変化することがわかる．
そこで本稿では，GPS デバイスにより収集した多数の移動軌跡から，与えられた始点から終点までの最もよく使われる経路を時間帯を考慮して求める方法を提案する．ここで，時間帯を考慮した与えられた始点から終点までの最もよく使われる経路を Most Popular Route in Time zone(MPR-T) と呼ぶ．

2. 時間帯を考慮した MPR(MPR-T)
2. 1 最も使われる経路 (MPR) の検出
これまで，Zaiben らは過去のオブジェクトが通過した点のシーケンスから，最も使われる経路を検出する方法を提案した．
彼らはまず，複数の移動軌跡の交点を求め，その交点であるノードと，ノード間を結んだエッジから成る Transfer Networkを構築した．次に，ノード間を移動するオブジェクトの頻度を示す Transfer Probability を，吸収マルコフ連鎖を用いて算出した．最後に，始点と終点を結ぶ経路の中から，TransferProbability の総乗で算出される Route Popularity が最も大きい経路を MPR として検出した．
彼らは，すべての移動軌跡から Transfer Network を構成し，上記の指標を算出している．この方法では，時間帯が考慮されない MPR が発見されるため，ある時間においては MPR でない可能性がある．

2. 2 MPR-T の概念
図 1 に示す簡単な例を用いて，MPR-T の概念を説明する．
図 1(a) と (b) は，異なる時間帯での移動軌跡を示している．
図 1(a) では，2 つの異なる経路 (Route1 と Route2) と 3 つの移動軌跡 (Tra1， Tra2，Tra3) がある．２つの移動軌跡 Tra1と Tra2 は同一の経路である Route1 を用いて移動している．一方，移動軌跡 Tra3 は別の経路 Route2 を用いて移動している．
図 1(a) に示す移動軌跡の状況から，Route2 よりも Route1 を移動する移動軌跡の方が多いため，Route1 が MPR として抽出できる．
一方，図 1(b) は図 1(a) とは異なる時間帯での移動軌跡の使用経路状況を示す．図 1(b) では，図 1(a) とは異なり，Route1よりも Route2 を移動する移動軌跡の数が多いため，Route2 がMPR として抽出できる．すなわち，時間帯を考えずに MPRを求めると，特定の時間帯では MPR でない経路が得られることとなる．

1 つ目は，指定した時間帯の間に MPR が変化するという問題である．道路の交通量は分刻みで変動する．そのため，例えば 13 時台と時間帯を指定しただけでは，適切な MPR を検出することができない．

2 つ目は，指定した時間帯に，MPR が変化する境界線が存在するという問題である．ある経路が MPR である時間と，異なる経路が MPR である時間は一定ではない．したがって，例
えば 13 時から 15 時までのどの時間で，MPR が変化するかを判断することは困難である．
そこで本稿では，道路の交通量から MPR とその有効な時間帯を検出する．時間帯を検出する方法として，小さな時間セグメントを結合して大きな時間セグメントにしていくボトムアップ法を用いる．

3. 1 有効な時間帯の検出方法
まず最初に，時間 T を以下のように定義する．
定義 1 (時間) 時間 T は時間軸上で表すと，t1 から始まり，tMまでの M 個の点であるとする．M は便宜上，ある整数 K の倍数とする．
次に，時間を固定数の時間セグメントに分割し，時間セグメントを以下のように定義する．
定義 2 (時間セグメント) 時間セグメント ∆T は，時刻 ∆T.sから時刻 ∆T.e までの区間である．定義 1 で示すように時間は離散時刻の点で表されるため，時間セグメント ∆T は ∆T.s と∆T.e との間の ∆T.e − ∆T.s + 1 個の点からなる．したがって，
T = ∪mj=1 ∆Tj (∆Ti ∩ ∆Tj = 0) である．
そして，後述の結合条件の内の 1 つを用いて 2 つの隣接する時間セグメント ∆Ta と ∆Tb を結合する．このとき，2 つの時間セグメント ∆Ta と ∆Tb は連続した時間セグメントである
ため，∆Ta .e + 1 = ∆Tb .s である．結合したのち，新しい時間セグメント ∆Tab を T に加え，T から ∆Ta と ∆Tb を削除する．これらの処理を繰り返し，T のすべての要素に変化がなくなれば処理を終了する．時間セグメント結合のアルゴリズムをAlgorithm1 に示す．
3. 2 時間セグメントの結合条件（1）経路を通過する移動軌跡の個数を表すために，Zaibenらの研究で用いられている移動ネットワークの概念を導入する．
移動ネットワークは，移動軌跡の交点であるノードと，ノード間を結ぶエッジの集合で表される有向グラフである．与えられたすべてのオブジェクトの GPS ポイント P = (p1 , p2 , · · · , pn )に対し，移動ネットワークの生成過程を以下に示す．

Step1 : クラスターの作成
GPS ポイント pk (∈ P ) をクラスターの中心として，中心との関連度が高い GPS ポイントをクラスターの要素とする．

Step2 : ノードの決定
クラスターの中心（移動軌跡の交点）と，移動軌跡の端点とな

（2）これらの手法による結合条件を簡単な例を用いて以下

Algorithm 1 Time Segments Combination[INITIALIZATION]に定義する．結合条件は，条件 Avg，条件 All，条件 Most，条Tset ← {∆T1 , · · · ,∆Tm }件 NumberAvg，条件 NumberAll，条件 NumberMost の 6 種[ITERATION]類である．すべての例は，時刻点でのエッジを通過する移動軌

for ∀∆Ta ,∆Tb ∈ Tset (∆Ta =| ∆Tb ) do

跡数を表しており，手法を図示するためにエッジ 1 のみを表示

if ((CHECK ∆Tab (∆Ta , ∆Tb )) is true) thenしている．結合する時間セグメントは，∆T4 と ∆T5 とする．

∆Tab =COMBINE(∆Ta , ∆Tb )条件 AvgTset ← Tset ∪ ∆Tab - ∆Ta - ∆Tb

結合した時間セグメント ∆Tab 内のエッジの標準

end if

偏差 std(∆Tab ) がすべて閾値 α 以下である，かつ，結合前の 2

end for

つの時間セグメント ∆Ta ,∆Tb において，すべてのエッジの平[STOP CONDITION]

均差 davg が閾値 β 以下である

There exists no ∆Tab where CHECK ∆Tab (∆Ta ,∆Tb ) is true

図 2 では，点線間の std(∆T45 ) が標準偏差，破線間の davg がfor any combination of a pair,∆Ta ,∆Tb ∈ Tset (∆Ta =| ∆Tb )平均差を表しており，時間セグメント ∆T45 内のすべてのエッジで閾値以下ならば結合する．

る GPS ポイントをノードとする．

条件 All 結合した時間セグメント ∆Tab のエッジの標準偏差Step3 : エッジの決定

std(∆Tab ) がすべて閾値 α 以下である

各ノードと，隣接したノード間で，移動軌跡を含む場合，ノー

図 3 では，点線間の std(∆T45 ) が標準偏差を表しており，時ド同士を連結してエッジ生成を行う．

間セグメント ∆T45 内のすべてのエッジで閾値以下ならば結合

移動ネットワークのエッジを通過する移動軌跡数を用いて，する．

以下に示す 3 つの手法による時間セグメントの結合条件を設定

条件 Most 結合した時間セグメント ∆Tab の大多数 (閾値 γ%Mする．時間セグメントの時刻点 ∆T.s + i (0 <= i < m ) でエッ以上) のエッジの標準偏差 std(∆Tab ) が閾値 α 以下である

ジを通過する移動軌跡数を wi とし，平均差を davg ，標準偏差

図 4 では，点線間の std(∆T45 ) が標準偏差を表している．条件

を std(∆Tm )，最小値を min(∆Tm ) とし，以下に各々の定義

Most では，時間セグメント ∆T45 内の大多数のエッジが閾値を表す．

以下ならば結合する．

•

条件 NumberAvg

平均差結合した時間セグメント ∆Tab のエッジ結合する 2 つの時間セグメント ∆Ta ，∆Tb における，各時間の標準偏差 std(∆Tab ) がすべて閾値 α 以下である，かつ，結合セグメントの移動軌跡数の平均差 davg を以下の式で求める．

前の 2 つの時間セグメント ∆Ta ,∆Tb において，すべてのエッdavg = |avg(∆Ta ) − avg(∆Tb )|∑M−1mi=0
Mmavg(∆Tm ) =•(1)

ジの平均差 davg が閾値 β 以下である，かつ，エッジの移動軌跡の個数がすべて閾値  以上である
図 5 では，点線間の std(∆T45 ) が標準偏差，破線間の davg がwi(2)平均差，縦軸の目盛に引かれた線分が最小値を表しており，条件 Avg に加えて，最小値以上の移動軌跡が存在すれば結合する．

標準偏差

条件 NumberAll

結合した時間セグメント ∆Tab のエッジの結合した時間セグメント ∆Tm 内の各時刻点における移動軌跡

標準偏差 std(∆Tab ) がすべて閾値 α 以下である，かつ，エッジ数のばらつき std(∆Tm ) を以下の式で求める．の移動軌跡の個数が閾値  以上である√std(∆Tm ) =•∑M−1mi=0(wi − avg(∆Tm ))2Mm

図 6 では，点線間の std(∆T45 ) が標準偏差，縦軸の目盛に引か(3)れた線分が最小値を表しており，条件 All に，最小値以上の移動軌跡が存在すれば結合する．

最小値

条件 NumberMost

結合した時間セグメント ∆Tab の大多結合した時間セグメント内の各時刻点における移動軌跡数の最数 (閾値 γ% 以上) のエッジの標準偏差 std(∆Tab ) が閾値 α 以

小値 min(∆Tm ) を以下のようにして求める．

下である，かつ，すべてのエッジの移動軌跡の個数が閾値  以min(∆Tm ) = wk (∀wi ∈ W, wk <= wi )(4)

ここで，W = (w0 , · · · , w M )m

MPR を含む時間セグメントと，MPR を含まない時間セグ上である
図 7 では，点線間の std(∆T45 ) が標準偏差，縦軸の目盛に引かれた線分が最小値を表しており，条件 Most に，最小値以上の移動軌跡が存在すれば結合する．

メントを結合すると，結合した時間セグメントで MPR が検出時間セグメントの結合条件のアルゴリズムを Algorithm2 にされない可能性がある．したがって，結合する 2 つの時間セグ示す．なお，Algorithm2 では各々の条件をシリアルに記述しメントにおいて，平均差と標準偏差を用いて移動軌跡の個数がているが，実際には条件の 1 つを適用して結合する．

類似しているかを判断する．また，移動軌跡数が極端に少ないと信頼性の低い MPR を検出してしまうため，移動軌跡数の最小値を設定する．

3. 3 時間セグメントの結合例
24 個の時刻点をもつ時間 T を，∆T1 から ∆T8 までの 8 つの時間セグメントに分割し，3 つのエッジ L1 ，L2 ，L3 が存在Algorithm 2 CHECK ∆Tab (∆Ta , ∆Tb )INPUT : Time Segment ∆Ta , ∆Tb ; Parameter α, β, γ, ;
OUTPUT :combineflag;boolean combineflag;∆Tab = COMBINE(∆Ta ,∆Tb )[CONDITION Avg]

図2

条 件 Avg

if (std(∆Tab ) of all edges) <= α and (the diﬀerence of the average< β thenvalue for each edge) =combineflag = true;end if[CONDITION All]
if (All of the std(∆Tab )) <= α then
combineflag = true;end if[CONDITION Most]
if (Most of the std(∆Tab )) <= α then

図3

条 件 Allcombineflag = true;end if[CONDITION NumberAvg]
if (std(∆T ) of all edges) <= α and (the diﬀerence of the averagevalue for each edge) <= β and (the number of trajectories of all<edges) =  thencombineflag = true;end if

図 4 条件 Most

[CONDITION NumberAll]
if (All of the std(∆T )) <= α and (the number of trajectories ofall edges) <=  thencombineflag = true;end if[CONDITION NumberMost]
if (Most of the std(∆T )) <= α and (the number of trajectoriesof all edges) <=  then
combineflag = true;end if
RETURN combineflag;

図 5 条件 NumberAvg

図 6 条件 NumberAll

図8

時刻点における移動軌跡数の例

する場合においての時間セグメント結合処理を考える．ここで，結合条件に用いる閾値 α を 5.0，閾値 β を 5.0，閾値 γ を 60%，閾値  を 10 と設定する．それぞれの時刻点における移動軌跡数を図 8 に示す．
まず，式 (3) を用いて，時間セグメント ∆T1 から ∆T8 までのすべてのエッジの標準偏差 std(∆Tm ) を算出する．算出した
図 7 条件 NumberMost

標準偏差を表 1 に示す．
また，式 (2) を用いて算出した，時間セグメントにおける移動軌跡数の平均 avg(∆Tm ) を表 2 に示す．

表 1 時間セグメントの標準偏差std ∆T1 ∆T2 ∆T3 ∆T4 ∆T5 ∆T6 ∆T7 ∆T8
L1

1.70 4.11 4.50 3.74 4.90 0.94 0.94 2.05

L22.94 4.50 4.11 1.70 1.89 1.70 1.70 6.34

L32.49 4.32 4.50 1.70 0.94 1.63 1.70 12.4表 2 時間セグメントにおける移動軌跡数の平均avg ∆T1 ∆T2 ∆T3 ∆T4 ∆T5 ∆T6 ∆T7 ∆T8
L117.3 32.7 24.7 20.0 15.0 8.33 8.33 26.7

L226.0 20.3 26.7 12.7 12.3 17.7 7.67 13.3

L36.67 15.0 31.7 17.7 17.7 20.0 7.67 18.7

条件 Avg この条件では，閾値 α=5.0，β=5.0 であるため，α 以下の標準偏差 std(∆Tm ) でかつ，β 以下の平均差 davg の時間セグメントが結合可能となる．すなわち，この条件を満たす時間セグメントは，∆T4 と ∆T5 の組である．
条件 All この条件では，閾値 α=5.0 であるため，α 以下の標準偏差 std(∆Tm ) の時間セグメントが結合可能となる．すな
わち，∆T7 と ∆T8 の組のみが結合不可能であり，それ以外の時間セグメントは結合可能である．
条件 Most この条件では，閾値 α=5.0，γ=60% であるため，α 以下の標準偏差 std(∆Tm ) である時間セグメントが γ% 以上あれば，結合可能となる．すなわち，すべての時間セグメント

図 9 GPS ポイントと生成したノードがこの条件を満たす．
条 件 NumberAvg こ の 条 件 で は ，閾 値 α=5.0，β=5.0，=10 であるため，α 以下の標準偏差 std(∆Tm ) でかつ，β以下の平均差 davg でかつ， 以上の移動軌跡数を持つ時間セグメントが結合可能となる．すなわち，すべての時間セグメントがこの条件を満たさない．
条件 NumberAll この条件では，閾値 α=5.0，=10 である
ため，α 以下の標準偏差 std(∆Tm ) でかつ， 以上の移動軌跡数を持つ時間セグメントが結合可能となる．すなわち，この条件を満たす時間セグメントは，∆T2 と ∆T3 ，∆T3 と ∆T4 の組である．
条件 NumberMost この条件では，閾値 α=5.0，γ=60%，=10 であるため，α 以下の標準偏差 std(∆Tm ) である時間セグメントが γ% 以上でかつ， 以上の移動軌跡数を持つ時間セグメントが結合可能となる．すなわち，この条件を満たす時間セグメントは，∆T2 と ∆T3 ，∆T3 と ∆T4 の組である．
以上の結合例をまとめると，表 3 のような結果を得た．表 3に示すように，条件 NumberAvg で結合可能な時間セグメン
トの組が最も少なくなり，条件 Most で最も多くなることがわかる．

4. 評 価 実 験
4. 1 実 験 条 件
従 来 法 の MPR と ，本 稿 で 提 案 し た 時 間 帯 に お け る

MPR(MPR-T) について，実際の移動軌跡データセット [7]を用いて経路の比較を行った．まず，移動軌跡データセットから移動ネットワークを生成し，時刻毎の各エッジを通過する移動軌跡数を算出する．次に，時間セグメントに結合条件を適用して時間帯を検出した後，MPR-T を求める．本実験で使用した移動軌跡データセットは，アテネ市内を走る 700 台のトラックの移動軌跡で，9792 個の GPS ポイントから構成される．

4. 2 評価結果ならびに考察
GPS ポイントと，Zaiben らの移動ネットワークを用いて生成したノードを図 9 に示す．黒い点は GPS ポイント，赤い点は生成されたノードを表している．これにより，9792 個の GPSポイントを，819 個のノードに変換した．
移動ネットワークから，それぞれのエッジにおける時間別の移動軌跡数を算出した．移動軌跡の最初の記録時刻から，最後の記録時刻までの間隔が 1 時間以上であることから，本実験では時間 T を 24 時間として，t1 から t24 の 24 個の点で定義し

表 3 各条件における結合結果例
結合可能な組た．時間セグメントは，標準偏差を算出する際，母集団から抜き出した標本が，最低 3 つ以上でなければ統計的の正確さを期

条件 Avg(∆T4 ,，∆T5 )条件 All(∆T7 ,，∆T8 ) 以外の組

条件 Most

すべての組義した．したがって，AM0 時から AM2 時 59 分まで（∆T1 ），条件 NumberAvg

なし

AM3 時から AM5 時 59 分まで（∆T2 ），AM6 時から AM8 時

条件 NumberAll(∆T2 , ∆T3 )，(∆T3 ，∆T4 )59 分まで（∆T3 ），AM9 時から AM11 時 59 分まで（∆T4 ），条件 NumberMost (∆T2 , ∆T3 )，(∆T3 ，∆T4 )待できないことから，1 つの時間セグメントを 3 時間として定PM12 時から PM14 時 59 分まで（∆T5 ），PM15 時 00 分から
PM17 時 59 分まで（∆T6 ），PM18 時から PM20 時 59 分まで

の MPR を検出可能か検討する必要がある．

5. 関 連 研 究Kai-Ping ら [2] は，それぞれのユーザに適した経路を発見するためのフレームワークを提案した．まず最初に，ユーザの過去の移動軌跡から Familiar Road Segments を抽出し，それらを用いて Familiar Road Network を構築した．次に，Familiar

Road Network から、Backtracking Algorithm と，EﬃcientRouting Algorithm をによって k 個の Personalized Route を得た．そして，ユーザの熟知度と，経路の長さから Route Score

Function を用いて，k 個の経路を順位づけすることで，パーソ図 10 MPR と MPR-T

ナライズされた経路を検出した．しかし，ユーザに適した経路を検出するためにそのユーザの過去の移動軌跡を用いる必要が（∆T7 ），PM21 時 00 分から PM23 時 59 分まで（∆T8 ）の 8あるため，過去のすべての移動軌跡を利用している点で本研究つの時間セグメントに分割される．また，結合条件適用前の時と異なる．

間セグメント (∆T1 , ∆T2 , · · · , ∆T8 ) から最低 1 組が結合される

GPS から取得した移動軌跡を用いて経路を発見する研究は，ように，閾値 α を 10.0，閾値 β を 10.0，閾値 γ を 60%，閾値

他にも多く存在する．Liao ら [3] は，低いサンプリングレート

 を 20 として設定した．結合条件を適用した結果を，以下の表で取得された移動軌跡から Transfer Network を構築し，吸収4 に示す．

マルコフ連鎖を用いて位置間の経路を発見した．Zheng ら [4]表 4 各結合条件適用後の結合結果

は，複数ユーザの移動軌跡から，広場やショッピングモールな適用後の時間セグメントどの公共施設と，移動順序のマイニングを行った．Ling ら [5]条件 Avg∆T1 , ∆T2 , ∆T3 , ∆T4 , ∆T5 , ∆T6 , ∆T7 , ∆T8はチェックインサービスを用いて，曖昧な移動軌跡から，ポピュ条件 All∆T1 , ∆T2 , ∆T3 , ∆T4 , ∆T5 , ∆T6 , ∆T7 , ∆T8

ラーな経路を検出するためのフレームワーク (RICK) の提案を条件 Most∆T12 , ∆T345 , ∆T6 , ∆T7 , ∆T8

条件 NumberAvg∆T1 , ∆T2 , ∆T3 , ∆T4 , ∆T5 , ∆T6 , ∆T7 , ∆T8

条件 NumberAll∆T1 , ∆T2 , ∆T3 , ∆T4 , ∆T5 , ∆T6 , ∆T7 , ∆T8以上に挙げた研究では，複数オブジェクトの移動軌跡からの条件 NumberMost∆T1 , ∆T2 , ∆T345 , ∆T6 , ∆T7 , ∆T8

み経路を検出している．本研究は，移動軌跡から経路を発見す行なった．

る際の有効な時間帯を検出しているため，検出方法が異なる．
条件 Avg，条件 All，条件 NumberAvg，条件 NumberAll では，結合可能な時間セグメントの組が検出されなかった．これ

6. お わ り には，時間帯によって移動軌跡の数に大きな差があるために，す

本稿では，時間帯を考慮した MPR 検出手法の提案を行った．

べてのエッジで結合条件を満たすことができなかったことが提案手法では，移動軌跡の時間情報を基に時間セグメント結原因として挙げられる．条件 Most と条件 NumberMost では，合を繰り返し，MPR 検出の適切な時間帯を求めた．実験の結時間セグメント ∆T3 と ∆T4 と ∆T5 が結合された．この結果，

果，特定の時間帯で有効な MPR を発見することが可能となっAM6 時から PM14 時 59 分までの時間帯において，午前中をた．今後は，時間セグメントの結合条件の考察をする予定であ通して移動軌跡の数が変わらないことがわかる．さらに，条件る．また，時間帯を検出する際の適切な指標の検討を行う必要

Most では，∆T1 と ∆T2 の組も結合されたことから，深夜の時がある．

間帯ではほとんどの経路で移動軌跡が少ないことがわかる．
結合結果より検出した ∆T12 の時間帯 (AM0 時から AM5 時59 分まで) での MPR-T(a) と，すべての時間帯 (AM0 時からPM23 時 59 分まで) での MPR(b) を，図 10 に示す．図 10 から，MPR-T 及び MPR による移動軌跡が異なることがわかる．

MPR-T は黄色で示された大通りを含んでいる．これは，深夜の時間帯による移動軌跡が安全を考慮して移動していたと考えられる．また，このように MPR では生成されなかった経路が，深夜の時間帯における MPR-T で検出されたことから，条件

Most は MPR-T を求める適切な時間帯を検出したと言える．
今後は，各結合条件によって検出した MPR-T に関して評価実験を行う予定である．また，単に時間帯を指定して検出した

MPR と，本手法を用いて検出した MPR-T を比較する評価実験を行う必要がある．さらに，閾値の設定を行うことで，同一文

献[1] Z. Chen, H. T. Shen, and X. Zhou. Discovering popularroutes from trajectories. In ICDE ’11, pp.900-911, 2011.
[2] K. Chang, L. Y. Wei, and M. Y. Yeh, and W. C. Peng.
Discovering personalized routes from trajectories. In LBSN
’11, pp.33-40,2011.
[3] C. Liao, J. Lu, and H.Chen. Synthesizing routes for low
sampling trajectories with absorbing Markov chains. In
WAIM’11, pp.614-626, 2011.
[4] Y. Zheng, L. Zhang, X. Xie, and W.-Y. Ma. Mining interesting locations and travel sequences from gps trajectories.
In WWW ’09, pp.791-800, 2009.
[5] L. Y. Wei, Y. Zheng, W. C. Peng. Constructing PopularRoutes from Uncertain Trajectories. In KDD ’12, pp.195203, 2012.
[6] J.Yuan, Y.Zheng, X.Xie, G.Sun. Driving with Knowledge
from the Physical World. In KDD ’11, pp.316-324,2011.
[7] Trucks Data Set:http://www.rtreeportal.org/