DEIM Forum 2019 H1-２

複数オブジェクトの移動軌跡からの周期的なパターン検出
和田 康嗣†

原田圭†

佐々木勇和†

鬼塚真†† 大阪大学大学院情報科学研究科 〒 565–0871 大阪府吹田市山田丘 1-5
E-mail: †{wada.koji,harada.kei,sasaki,onizuka}@ist.osaka-u.ac.jp
あらまし 近年，GPS が自動車や携帯電話など様々なものに搭載され，位置情報を簡単かつ大量に取得することができる．それに伴い，オブジェクトの移動軌跡に関する研究も盛んに行われており，移動軌跡の中から周期的なパターンを検出する技術もその一つである．周期的なパターンの検出に関する既存研究はいくつか存在するが，どれも単一
オブジェクトを対象としたもののみであり，複数オブジェクトの移動軌跡を考慮したものは存在しない．本稿では，複数オブジェクトの移動軌跡からの周期的なパターンの検出を目的とする．これに対し単純な手法を適用した場合，計算量が大きくなる．そのため，複数オブジェクトを対象とした効率的なアルゴリズムを提案する．提案アルゴリズム
では探索すべきパターンや空間を選別し，枝刈りを用いて計算量を減少する．実験には実世界のデータを用い、提案
アルゴリズムが効率的に周期的なパターンを検出可能であることを示す．
キーワード 移動軌跡，時空間データマイニング，パターンマイニング

1. は じ め に
近年，GPS センサが自動車やスマートフォンなどに搭載されるようになり，現在では様々なオブジェクトの位置情報が大量に収集可能である．そのため，位置情報を時系列順に並べた
移動軌跡に関するデータマイニングの研究が盛んに行われている [1]．移動軌跡に関するデータマイニングにおいて，移動軌跡
図 1 単一オブジェクトの移動軌跡の周期的なパターン検出がある．例えば，ある人の行動を GPSデータとして長期間収集した場合，その人が毎朝同じルートを通って会社に出勤する通勤ルートが周期的なパターンとして検出される．図 1 に周期的なパターンを示す．それぞれの点は，7時から 7 時半の間のユーザの位置情報を表し，点が同じグリッド内にあるときそれらは同じ位置に存在するとする．周期を一日間とした場合，三日間に重複する移動軌跡があるため，それを周期的なパターンとして検出できる．
既存研究は単一のオブジェクトを対象とした周期的なパター

図 2 複数オブジェクトの移動軌跡

ンの検出を目的としている．人や動物の生活には習慣や規則性があると考えられるため [2]，対象とするものの性質を知る上で周期性を考慮したパターンマイニングは重要である．しかべ，その課題を解決すべく効率的な探索手法を提案する．

1. 1 問題定義と技術概要

し，現在のところ既存研究では単一のオブジェクトを対象とし本稿では，複数オブジェクトの移動軌跡からの周期的なパた研究しか存在しない．図 2 は複数オブジェクトの移動軌跡を

ターンの検出を目的とする．しかし，単一オブジェクトの移動示し，同じ色であれば同じオブジェクトの移動軌跡である．こ

軌跡とは異なる点がいくつか存在する．

のとき，単一のオブジェクトのみでは周期的なパターンは存在•

同時刻に複数の移動軌跡が存在し得る．

しないが，複数オブジェクトを考えた場合周期的なパターンが•同時刻に周期的なパターンが複数存在し得る．

存在する．応用としては，複数の自動車の移動軌跡が収集でき

既存研究が対象としている単一オブジェクトの移動軌跡のるとそれらのデータから特定の時期や時間によく利用される道

データが，同時刻にただひとつの軌跡を持つことに対し，本研路を発見し，交通状況の改善に役立てられる．複数のオブジェ

究で対象とする複数オブジェクトのデータは，同時刻に複数のクトを対象とした周期的なパターンは，集団で存在するものの移動軌跡が存在し得る．このことはパターン探索時の探索先の性質を把握する上で単一オブジェクトのみを対象としたパター

データ量をオブジェクトの数に比例するように増加させ，計算ン以上に重要であると考える．

時間を大きくする．さらに，同時刻に複数の移動軌跡が存在す

本稿では，複数オブジェクトを対象とした周期的なパターンを定義する．また，定義したパターンを検出する際の課題を述ることにより，単一オブジェクトのみを考えたときと異なり同時刻に周期的なパターンが複数存在し得る．既存研究が対象とり，周期的なパターンを発見する手法を提案している．位置情

している単一オブジェクトの移動軌跡の周期的パターンでは，1報の順列である 1 つの長い移動軌跡が与えられたとき，初めつの周期につき見つけるべきパターンは同時刻に 1 つだったたに指定した周期の長さで分割しセグメント化する．そして，セめ，パターンを見つけ次第探索を切り上げ，計算時間を抑える

グメントにあらわれる閾値以上に出現するパターンを周期的なことができた．しかし，本稿で扱う複数オブジェクトの移動軌パターンとして検出する．その際まず長さが 1 のパターンを跡の場合，周期的なパターンとして同時刻に複数の移動軌跡が1-patterns として検出し，ボトムアップ的にもしくはトップダ検出される可能性があり，探索中に周期的なパターンが検出でウン的に探索し，最終的な周期的パターンを検出する．

きたとしてもその段階では探索を打ち切ることができず，再度Li ら [12, 13] はユーザが周期を指定することなく，長い移動

他のパターンが存在するかどうかを探索する必要がある．よっ

軌跡のデータから自動的に周期を特定する手法を提案している．

て，単一オブジェクトを扱う場合とは異なる方法で計算時間を

まず，移動軌跡の座標情報の密度に対してカーネル法を用いて削減しなければ，入力データ量の増加に対する計算時間の増加

よく訪れているポイント（Reference Spot）を抽出し，それ以を抑えることができない．

外の座標データと区別する．そして座標の順列で表されていた

本稿では 2 つの手法を提案する．探索先のデータ量が大きく

移動軌跡が， Reference Spot であるかそれ以外の場所であるなる問題に対しては，探索先のデータの集合が特定の地域情報

かの 2 値で表現する．次に，変換された移動軌跡に対してフーを含むかどうかによって，探索すべきかどうかを判断し枝刈り

リエ変換と自己相関を用いて周期を特定する．最後に，特定さを行う手法を提案する．探索回数が大きくなる問題に対しては，れたそれぞれの周期についてクラスタリングを用いて周期的なボトムアップ的な手法を含む手法を用い，パターンとなり得なパターンを発見する．

いようなものの探索を削減する手法を提案する．これら 2 つのこれら 2 つの既存手法において，対象とされる移動軌跡は単手法は，検出すべきパターンが複数存在していても適用可能で一のオブジェクトが作る軌跡のみであり，複数のオブジェクト

ある．

から生成される移動軌跡を包括的に取り扱い周期的なパターン

1. 2 本研究の貢献と構成を求めることは考えられていない．したがって，複数オブジェ

本研究の貢献を下記にまとめる．

クトから生成される移動軌跡の周期的パターンを新たに考えた•

とき，単一オブジェクトでの手法がそのまま使えない場合や，複数のオブジェクトの移動軌跡の集合から周期的なパターンを検出する問題を新たに定義する．

•

複数のオブジェクトの移動軌跡からの周期的なパターンを効率的に検出可能なアルゴリズムを提案する．

•

実データを用いた実験より，提案アルゴリズムが周期的パターンを効率的に検出可能であることを示す．

計算量が大きくなってしまう問題がある．
また，実データの移動軌跡を扱う上で議論すべきの要素として位置情報の地域化がある．これは，実際の GPS データを扱
う上で，座標データのあらゆる原因における数値の揺らぎを吸収するために行われる．Cao らは DBSCAN [14] のように密度

本稿の構成は，次の通りである． 2. 章にて関連研究についベースのクラスタリングを用いてグリッドベースの手法と比較て述べる．3. 章で本稿の前提となる知識について概説する．4.

実験を行っている．自動で周期を特定する手法においては，座章にて提案手法の詳細について説明し，5. 章において提案手法

標データの密度に対してカーネル法を用いて Reference Spotの評価と分析を行う．6. 章にて本稿をまとめ，今後の課題につとそれ以外の地域に分けている．後者は周期を特定するためのいて論ずる．

前処理でもあり，両者の地域化の意味合いは微妙に異なる．本2. 関 連 研 究
この章では，本稿の研究テーマである周期的なパターンマイ
ニングとその他のデータマイニングに関して述べる．

稿では，複数オブジェクトの移動軌跡から周期的パターンを発見するために，グリッドベースの手法で地域化を行う．

3. 移動軌跡の周期的なパターン

移動軌跡を活用した研究は，行動予想 [3]，異常値検知 [4–6]

この章では発見すべき移動軌跡の周期的なパターンについてや移動軌跡の分類 [7, 8] など多岐にわたる．パターンマイニン定義する．また，単一オブジェクトの移動軌跡と複数オブジェ

グも多数の研究が行われており，主に 4 つの主要なカテゴリがクトの移動軌跡との違いについて，複数オブジェクトから発見存在する [9]．ひとつは共に行動する対象を発見する Moving

される 2 種類の周期的なパターンについても言及する．

Together Pattern，次に似たような軌跡をまとめる Trajectory

まず，位置の情報を座標情報として定義し，それらが順列にClustering，3 つめに訪れた場所の順番に関する Sequential

並んだ移動軌跡を定義する．そして，位置に関する情報の実際

Pattern Mining があり，最後に本稿のテーマである周期的な的なユレを吸収するための地域化について触れ，最終的に検出パターンを発見する Periodical Pattern Mining が存在する．

したい複数オブジェクトの周期的なパターンを定義する．

移動軌跡に関する周期的なパターンマイニングには周期を指定する手法と自動で周期を特定する手法の 2 つの既存手法

定義 1 (座標情報) 位置的な情報を持つ座標情報 l は { 緯度が存在し，大きく Fixed Period Approach と Reference Spot

, 経度, タイムスタンプt} の 3 つの要素で構成されている．まApproach の 2 つに分けられる [1]．

た，タイムスタンプ t は 1 以上の整数とする．

Cao ら [10, 11] は任意の周期をあらかじめ与えることによ定義 2 (移動軌跡) 移動軌跡 s は s = ⟨l1 , l2 , . . . , ln ⟩ である．
ただし，li+1 .t − li .t = 1，n >= 2 である．
定義 3 (部分軌跡) ある移動軌跡 s を ⟨l1 , . . . , ln ⟩ としたとき，′⟨li , li+1 , . . . , lj−1 , lj ⟩(i >= 1, j <= n) を s の部分軌跡 s とする．

また，s 自身も s′ である．ただし，部分軌跡は移動軌跡の条件

図 3 検出手順の概略を満たす．
ここで S = {s1 , s2 , . . . , sN } と移動軌跡の集合が与えられた′

とき，S に含まれる全ての s の部分軌跡の集合を S とする．こ
こからは，最終的なパターンの定義と取り扱う実際的なデータ

定義 8 (周期的なパターンマイニング)

移動軌跡の集合 S ，周期 T ，閾値 θth ，θlow が与えられたとき，全ての周期的な極大パターンを検出する．

の性質に応じて必要となる定義をする．
座標情報 l は連続値であるため，特定の基準で離散的な値に区分することが必要となる．
定義 4 (地域)

4. 提 案 手 法
本稿では，複数オブジェクトから生成された移動軌跡 s の集

空間的範囲を持つ位置的な情報 w を地域と呼ぶ．また，ある座標情報 l の緯度と経度が w の空間的範囲内に存在すれば，{w, t} を地域化された座標 r と呼ぶ．このとき，

l は r に属する．そして，移動軌跡の座標情報を地域化された座標に置き換えたものを，地域化された軌跡 sr とする．また
r
移動軌跡同様，⟨ri , ri+1 , . . . , rj−1 , rj ⟩(i >= 1, j <= n) を s の部

分軌跡 sr ′ とする．

合 S が入力データとして与えられたとき，新たに定義した周期的なパターンを発見する．

4. 1 節にて検出手順を示し，複数オブジェクトの移動軌跡を入力とした特徴や問題点について論じる．また，入力データである移動軌跡の集合 S と本稿における座標の地域化についても論じる．4. 3 節，4. 4 節では 4. 1 節で述べた問題点や特徴に対応した手法を提案する．そして 4. 5 節ではアルゴリズムについて説明する．

定義 5 (地域化された軌跡に属する移動軌跡) 移動軌跡を s =⟨l1 , l2 , . . . , ln ⟩ としたとき，1 <=i<= n において，li が ri に属し

4. 1 検 出 手 順
周期的パターン検出手順の概略を図 3 に示す．初めに候補パていれば，移動軌跡 s は地域化された軌跡 sr = ⟨r1 , r2 , . . . , rn ⟩ターンを作成し，次にその候補パターンと同じ軌跡がデータ内

複数オブジェクトの周期的なパターンを定義する前に，記号ば周期的パターンであると認定し，存在しなければ周期的パの定義とその説明をする．

に存在するか探索する．あらかじめ決めた閾値以上に存在すれターンとはしない．これを有効な候補パターンが作成不可になS が与えられたとき周期 T を 1 以上の整数とし，m を 1 以
上の整数とするとき，LS = m · T は S の時間的長さであり，

LS >= t，∀l ∈ S かつ (m − 1) · T <= t となるタイムスタンプを持つ l が S 内に存在する．例えば，1 日を 600 のタイムスタン

るまで繰り返すことで，全ての極大パターン検出を目指す．

4. 1. 1 前 処 理
各ステップ毎に詳しく述べる前に，検出や提案手法の実行のための前処理について述べる．

プに分けたとき，LS = 6000 であれば，10 日分の移動軌跡が入力データとして移動軌跡の集合 S が与えられたとき，それS には含まれていることが分かる．
LS
Ci (0 <
− 1) は周期毎の移動軌跡の集合とする．この
=i<
=

LS
を Ci (0 <=i<= T ) に分割する．これにより，任意の周期 T 毎に移動軌跡を管理するのだが，S の中には周期をまたぐ移動軌

とき，s ∈ Ci の長さは T 以下であり，s の座標情報のタイムス跡も存在する．その場合は周期の境目でその移動軌跡が分割さタンプは i · T < t <= (i + 1) · T を満たす．

れ，それぞれの Ci に振り分けられる．よって，前処理された

T

定義 6 (移動軌跡の周期的なパターン)

移動軌跡の集合 S ，そLDの LS ，周期 T ，周期毎の移動軌跡の集合 Ci (0 <= T − 1)，=i<閾値 θth ，θlow が与えられたとする．ただし，C0 ∪ C1 ∪ . . . ∪C LS −1 = S である．また，p = ⟨r1 , r2 , . . . , rm ⟩(rm .t <= T) とT

後の移動軌跡の長さは全て Ci の時間的長さ以下となる．10 日分のデータを入力とし，周期を 1 日と設定したとき，入力デー
タは図 4 のように日ごとに管理される．
次に，座標と移動軌跡の地域化について述べる．座標データ
は連続値であり，それらの一致をいうためには一定の基準を設したとき，p のそれぞれの r のタイムスタンプ t に i · T を加えけなければならない．今回は地域という離散な値に変換するこLDたものを qi (0 <= T − 1) とする．このとき，qi に属する=i<とでその基準を設ける．今回提案する手法は地域の分け方によs′ が Ci ′ 内に θlow 本以上存在するという条件を満たす Ci の数が LTD · θα 以上であれば，p を移動軌跡の周期的なパターンとする．
定義 7 (極大パターン)する．なお，実装時はグリッドの範囲，水平方向と垂直方向のグリッドの数を定め，それぞれに等分している．そのため，各周期的パターン p において，p にいかなる r を加えても周期的パターンとならない場合，p を極大パ
ターンとする．

らず適用可能であるため，単純なグリッドベースにより地域化

座標につき 1 つのグリッドが対応し，前処理において座標をグ
リッドの値に変換している．

図 4 移動軌跡を分割して管理

図 5 トップダウンによる枝刈り

4. 1. 2 候補パターンの作成
候補パターンをどのように作成し，どのようなパターンを作成するかは計算時間削減に大きく影響する．単純に考えると，

S 内の全ての移動軌跡 s の部分軌跡集合 S ′ を全て候補パターンとすればよい．しかしその場合，移動軌跡の長さ，入力 S の大きさが増大することで候補パターンの数が爆発的に増加する．
候補パターンの増加は検出手順のループ回数に結びつき，全体的な実行時間が著しく増大することになる．一方，候補パター
ンの数を減らす方法を考える．例えば，S ′ の中からランダムに複数の軌跡を選出し，それらを候補パターンから外すことを考える．その場合，S ′ の大きさが減る，つまり候補パターンの数が減るため，検出手順のループ回数も減少し，全体の実行時間

図 6 ボトムアップによる枝刈りが短縮される．しかし，本来であれば周期的パターンとして検出されるはずであった候補も外す可能性があるため，不用意に認する．周期的パターンであった場合，極大パターンの定義に

候補パターンを削減することはできない．

より，それより短い軌跡については候補パターンとせず，候補

4. 1. 3 データ内探索

パターン作成を枝刈りする．

データ量の増加は探索する空間の拡大に直接結びつくため，

4. 3 ボトムアップ

大規模なデータを扱う上で有効な探索法を提案することは重要

候補パターン作成時の手法を提案する．複数のオブジェクトである．本稿では，4. 1. 1 項で述べたように周期毎に移動軌跡において周期的パターンを検出する際は，単一の場合と異なりを管理している．よって単純な手順として，C0 から C LS まで

ひとつひとつのオブジェクトが周期的でない移動軌跡を多く含T順にすべて探索し，閾値以上であれば周期的パターンとする方む可能性がある．また，周期的パターンではない sr ′ を含む軌法が考えられる．既存研究で扱われている，単一なオブジェク

跡 sr は周期的パターンとなり得ない．よって，無駄な候補パトを対象としたものであっても周期毎に分割されるが，複数オ

ターン作成を抑制する手法として，短い軌跡から候補パターン

ブジェクトの移動軌跡を入力として許すと単一オブジェクトとを作成するボトムアップが効果的だと考える．図 6 にボトムは違い，Ci が保持する移動軌跡の数が定まらない．S の増大にアップによる候補パターンの作成と枝刈りの様子を示す．図中

伴ってその数が増加し，単純な手法だと探索にかかる時間も大の丸で囲まれた各数字はボトムアップで候補パターンを作成す

きくなると考えられる．

る際の手順を表す．まず長さが一番短い軌跡を候補パターンと4. 2 ベースライン

し，それが周期的に出現するかをデータ内を探索して調べる．

既存研究 [10] では，トップダウン的に候補パターンを作成す

調べ終えると次にそれらを結合し，長さが 1 長い軌跡を候補パる．本稿ではこれをベースラインの候補パターン作成手法とす

ターンとしていくのだが，先ほど述べたように周期的パターン

る．また，データ内探索ステップでは単純に Ci を全て探索すでない軌跡は周期的パターンになり得ないので，候補パターン

る手法をベースラインに用いる．トップダウンで候補パターン

作成に関して枝刈りが可能である．よって，候補パターン集合を作成すると，p が周期的パターンであった場合その部分軌跡の大きさを小さくすることが可能である．候補パターンの数が′である p 以降の候補パターン作成を省くことができる．トップ

減ると，検出手法全体のループ回数が減少し実行時間を抑えらダウンによる候補パターン作成と枝刈りの様子を図 5 に示す．

れる．図 6 にボトムアップによる候補パターンの作成と枝刈り

図中の丸で囲まれた各数字はトップダウンで候補パターンを作の様子を示す．

成する際の手順を表す．長さの長い軌跡から候補パターンとし，

4. 4 空間的枝刈り

そのパターンが周期的に現れているかをデータ内を探索して確先の 4. 3 節では候補パターンを作成する段階においての問

題に対処する手法を提案したが，ここではデータ内を探索する

Algorithm 1 Periodical Pattern Mining(S, T, R, θth , θlow )段階に生じるであろう問題に対処する手法を提案する．データ

1: S r ← convert(S, R, T )内を探索する際は，周期毎に分けられた移動軌跡の集合を順に

2: for i = 0 to LD /T do

調べていくのだが，オブジェクトの数に比例して各集合に含ま

3:

Ci = ϕれる移送軌跡が増加し，探索にかかる時間も大きくなる問題が

4:

C ← Ci

あった．その問題に対して，本稿では各集合 Ci にそれぞれの集合に含まれる地域の情報を持たせ，その情報を用いて Ci が探

5: end for
6: for all sr ∈ S r do

8:

この手法を行うため，4. 1. 1 項で説明した前処理時に各 Ci に

9:は自身が含む全移動軌跡が持つ地域をメタ情報として付与する．

10:

そして，データ内探索時に探索しようとしている候補パターン

11:が持つ地域が探索先の Ci に含まれているかによって，Ci を探12:索するかしないかを決め枝刈りする．

4. 5 アルゴリズム

for i = 0 to LD /T do

7:

索すべき集合かどうかを判断し，枝刈りを行う手法を提案する．

if the timestamps of sr ∈ [i · T , (i + 1) · T − 1] thenCi ← Ci ∪ sr
break
end ifend for

13: end for
14: for all sr ∈ S r do
15:

if bottomup then

以上で提案手法の概略を述べた．この節では周期的パターン

16:

S r ′ ← ∀l ∈ sr

検出の全体的なアルゴリズム，また各手法のアルゴリズムにつ17:

P ← bottomup(sr , S r ′ , C, θth , θlow )いて説明する．

18:

else topdown

アルゴリズム 1 は各手法に共通する前処理を含む，フレーム

19:

S r ′ ← sr

ワークの手順である．1 行目の convert は 4. 1. 1 項で説明した

20:

P ← topdown(sr , S r ′ , C, θth , θlow )ように，地域集合 R に各座標を地域化し，移動軌跡の分割を行21:う関数である．2 行目から 13 行目で sr ∈ S r を周期毎の集合

Ci に分割する．最後に，15 行目から 22 行目で候補パターンの作成，データ内探索を行い周期的なパターンを検出する．候補パターンは bottomup，topdown でボトムアップ，トップダ
ウンの各手法に沿って作成する．

Algorithm 2 topdown(sr , S r ′ , C, θth , θlow )1: P ← ϕ
2: for all sr ′ ∈ S r ′ do4:

リズムである．search とはデータ内探索を行う関数であり，ア5:

ルゴリズム 4 と 5 に提案手法である空間的枝刈りの内容を示す．

6:

リズムである．3 行目から 4 行目では，sr ′ についてデータ内探索を行い，周期的パターンであればそのパターンを返す．5 行
r′目から 11 行目までは sが周期的パターンでない場合の処理

if search(sr ′ , C, θth , θlow ) then3:

アルゴリズム 2 と 3 は候補パターン作成時の各手法のアルゴ

アルゴリズム 2 は，ベースラインとするトップダウンのアルゴ

end if

22: end for

return sr ′else
if |sr ′ | is 1 thenreturn7:
8:

end if9:

S r ′ ← {sr ′ − l0 , sr ′ − l|sr | }10:

P ← P ∪ {topdown(sr , S r ′ , C)}
end if11:である．9 行目で sr ′ より長さが 1 短い部分軌跡を sr ′ から作

12: end for

成する．そして 10 行目で，先ほど作成した sr ′ の集合 S r ′ を入

13: return P

力として再帰的に topdown を呼び出す．アルゴリズム 3 は提案手法であるボトムアップのアルゴリズムである．2 行目からる．そして，探索先に一致する軌跡が θlow 以上存在する Ci の6 行目までは，sr ′ ∈ S r ′ が周期的パターンであるか判定するた

数が |C| · θth 以上であれば sr ′ を周期的パターンとする．アルめ，seartch でデータ内を探索する．周期的パターンが検出さゴリズム 5 は探索すべき集合を判定するアルゴリズムである．

れなかった場合，ここで候補パターンの作成を終える．7 行目

2 行目から 6 行目で，条件を満たす Ci を有効な探索すべき集から 13 行目までは，2 行目から 6 行目までにおいて周期的な合とする．そして 7 行目から 9 行目で，有効な集合の数 |V | がパターンが検出できた場合の処理である．11 行目では，検出さ|C| · θth 以上であれば，V 内の集合を探索すべき集合としてれた周期的なパターンの中で共通のタイムスタンプ t を持つパ

返す．

ターンを結合し，新たに長い候補パターンを作成する．そして新たに作成した候補パターンの集合 S r ′ を入力とし，再帰的にbottomup を呼び出す．

5. 評 価 実 験
本章では提案手法の評価として効率性を評価する. 実験はアルゴリズム 4 と 5 は空間的枝刈りに関連するアルゴリズム

Intel Core i7-8700K 3.70 GHz の CPU，メモリは 64 GB のである．アルゴリズム 4 はデータ内を探索するアルゴリズムでものを載せたコンピュータ上で行う．また，全ての手法は C++

ある．1 行目で valid set を呼び出し，探索すべき集合を取得で実装した．移動軌跡のデータセットとして，北京市内のタク

する．3 行目から 8 行目で，探索すべき集合 Ci ∈ V を探索先

シーから得られた GPS の軌跡データ T-drive [15, 16] を用いとして，候補パターンに一致する軌跡が含まれているか探索すAlgorithm 3 bottomup(sr , S r ′ , C, θth , θlow )まず，各提案手法がベースラインと比較し高速に周期的なパ1: P ← ϕ
2: for all sr ′ ∈ S r ′ do3:

if search(sr ′ , C, θth , θlow ) thenP ← P ∪ sr ′4:
5:

end if

6: end for
7: if P =| ϕ then8:

if P includes sr thenreturn P

9:5. 1 効 率 性
ターンを検出できることを示す．図 7 はデータセットより 1000本の移動軌跡を作成し，検出対象として入力したときの各手法
による実行時間の比較である．これによりベースラインと比べ，各提案手法は数倍から数十倍高速にパターンを検出していることが分かる．
候補パターンの作成時の違いであるベースラインとボトムアップを比較する．ボトムアップの方がベースラインに比べて10:

end if

効率的にパターンを検出できている．そのため，まず短い部分

11:

S r ′ ← join any pairs of periodical patterns

軌跡を調べそれが周期的なパターンでなかったときの候補パ

12:

P ← P ∪ {bottomup(sr , S r ′ , C)}

ターンの枝刈りが効果的に行われたと言える．次にデータ内探13: end if

索時の違いである，ベースラインと空間的枝刈り手法とを比較

14: return P

Algorithm 4 search(sr ′ , C, θth , θlow )1: V ← valid set(sr ′ , C, θth , θlow )する．実行時間が減少していることから，効果的に探索すべき集合を選択できていると考えられる．最後に提案手法両方を組み合わせた複合手法について述べる．実行時間から，これが最2: count = 0

も効率的に検出を行えていると言えるが，ベースラインと空間

3: for all Ci ∈ V do

的枝刈り手法との差ほどボトムアップとの差がない．この要因として空間的枝刈り手法の特徴が挙げられる．提案した空間的

5:m = |{sr ′ |sr ′ ∈ sr ∈ Ci }|if m >= θlow then6:

count = count + 1を行う手法であり，長い候補パターンが様々な地域を含んでい4:

7:

end if

8: end for
9: if count >= |C| · θth then10:

return true

枝刈り手法は，候補パターンが持つ地域情報に基づいて枝刈りるとそれだけ探索先の集合に課す条件が厳しくなる．例えば候補パターンが r1 = ⟨{w1 , 1}, {w2 , 1}, {w3 , 3}, {w4 , 4}⟩ としたとき，探索先の集合 Ci は w1 ，w2 ，w3 ，w4 全ての地域を含ん

11: end if

でいる必要があり，候補パターンを r2 = ⟨{w1 , 1}, {w2 , 1}⟩ と

12: return false

したときに比べ，探索先が満たす条件は厳しくなる．また，ボトムアップは効率よく候補パターンを削減できているため，そAlgorithm 5 valid set(sr ′ , C, θth , θlow )の手法が作成した候補パターンは短い段階で枝刈りされている

1: V ← ϕと考えられる．よって，ボトムアップに空間的枝刈りを併用す

2: for Ci do

ると短い候補パターンをもとに探索先を枝刈りすることが比較

3:

if Ci include all regions that sr ′ include thenV ← V ∪ Ci

4:
5:

end if

的多くなる．よって緩い条件で空間的枝刈りを試みる比率が，トップダウンで候補パターンを作成するときより大きくなった

6: end forと考えられる．そのためトップダウンに空間的枝刈りを行った

7: if |V | >= |C| · θth then

ほどの効果がなかったのだろう．

8:

return V

次に，入力データの大きさを変化させたとき，各手法の実行

9: end if

時間を計測する．図 8 は入力データ S に含まれる移動軌跡の

10: return ϕ

本数を 1000 から 10000 まで変化させた場合の実行時間である．
ベースラインでは入力データが大きくなると，実行時間が大幅る．このデータセットには 2008 年 2 月 2 日から 8 日まで北京に増加していることが分かる．各提案手法ではベースラインに市内を走行した 10,357 台のタクシーのデータが含まれており，比べ実行時間自体は抑えられているが，入力データの増加に伴

タクシーの識別子，緯度経度とタイムスタンプから構成される．

い実行時間が大きく増加する傾向がある．提案手法はベースラ

実験ではこのデータを 1 日を 100 としたタイムスタンプに分けインに比べ，実行時間を定数倍減らすことは可能だが，より巨サンプリングしたものを使用する．前処理における地域化の方大なデータに対して直接適用できない可能性がある．

法はグリッドベースを用い，実験を通して固定された枠内を水平，垂直方向それぞれ gh ，gv 個に等間隔で分割する．

実験を通して，最も高速であるのは複合手法である．これは，ボトムアップで候補パターンを作成し，その後の探索時に空間評価実験を通して，特に記述がない場合はデフォルトのパラ的枝刈りを行うものである．よって，探索時の手法の違いのみ

メータとして，T = 100，θth = 0.5，thetalow = 1，gh = 3000，であるベースラインと空間的枝刈り手法との間の差と同じよう

gv = 3000 を使用する．また，2 つの提案手法を組み合わせたな差があってよいはずである．しかし，その差は数倍程度に収複合手法についても検討する．

まっている．実験結果から，ボトムアップは候補パターンの数
を，空間的枝刈りは探索する集合の数を減らすことができたと

文

60

時間（秒）

50
40
30
20
10
0

ベ
﻿ ースライン

ボトムアップ

空間的枝刈り複合手法

図 7 移動軌跡 1000 本を入力としたときの実行時間

8000
7000

時間（秒）

6000
5000

ベースライン
ボトムアップ
空間的枝刈り
複合手法

4000
3000
2000
1000
0
1000 2000 3000 4000 5000 6000 7000 8000 9000 10000

移動軌跡の数
図 8 移動軌跡の数を変化させたときの実行時間

言える．

6. ま と め
本稿では複数オブジェクトから生成された移動軌跡の周期的なパターンを新たに定義した．さらにその周期的なパターンを検出することを目的とし，実用的な計算時間で処理を終えるた
めボトムアップと空間的枝刈りの 2 つの手法を提案した．評価
実験ではベースラインとした手法と比較し，提案手法が計算時間を削減し効率的に周期的なパターンを検出可能であることを示した．
今後の研究として三つの課題に取り組む．まず，計算量の削減が十分ではないため，大規模なデータセットに適応することがまだ難しい．そのため，事前計算を用いることや並列分散計
算などを用いたさらなる効率化が必要である．次に，地域の分割方法について十分な考察ができていない．本稿では座標情報を扱う際にグリッドベースで地域に分割して位置情報を扱ったが，その他の分割法を用いることにより，新たに有用なパターンが検出できる可能性がある．そのため地域で位置情報を扱う方法について，より考察する必要がある．最後に，使用するデータの傾向を考える必要がある．例えば，都市を移動するタ
クシーと鳥の群れでは移動傾向が全く異なる．そのため，データの性質を考慮した手法を考案する必要がある．

謝

辞

本研究は科学研究費（JP16H01722）の支援によって行われた．ここに記して謝意を表す．

献[1] Dongzhi Zhang, Kyungmi Lee, and Ickjai Lee. Periodic
pattern mining for spatio-temporal trajectories: a survey.
In Proceedings of Intelligent Systems and Knowledge Engineering (ISKE), pp. 306–313, 2015.
[2] Xiaopeng Chen, Dianxi Shi, Banghui Zhao, and Fan Liu.
Periodic pattern mining based on gps trajectories. In Proceedings of International Symposium on Advances in Electrical, Electronics and Computer Engineering, pp. 181–187,
2016.
[3] Anna Monreale, Fabio Pinelli, Roberto Trasarti, and Fosca
Giannotti. Wherenext: a location predictor on trajectory
pattern mining. In Proceedings of ACM SIGKDD, pp. 637–
646, 2009.
[4] Lei Zhang, Zimu Hu, and Guang Yang. Trajectory outlier
detection based on multi-factors. IEICE Transactions on
Information and Systems, Vol. 97, No. 8, pp. 2170–2173,
2014.
[5] Prithu Banerjee, Pranali Yawalkar, and Sayan Ranu.
Mantra: a scalable approach to mining temporally anomalous sub-trajectories. In Proceedings of ACM SIGKDD, pp.
1415–1424, 2016.
[6] Yanwei Yu, Lei Cao, Elke A Rundensteiner, and Qin Wang.
Detecting moving object outliers in massive-scale trajectorystreams. In Proceedings of ACM SIGKDD, pp. 422–431,
2014.
[7] Yin Zhu, Yu Zheng, Liuhang Zhang, Darshan Santani, Xing
Xie, and Qiang Yang. Inferring taxi status using gps trajectories. arXiv preprint arXiv:1205.4378, 2012.
[8] Timothy Sohn, Alex Varshavsky, Anthony LaMarca,
Mike Y Chen, Tanzeem Choudhury, Ian Smith, Sunny Consolvo, Jeﬀrey Hightower, William G Griswold, and Eyal
De Lara. Mobility detection using everyday gsm traces.
In Proceedigns of International Conference on Ubiquitous
Computing, pp. 212–224, 2006.
[9] Yu Zheng. Trajectory data mining: an overview. ACM
Transactions on Intelligent Systems and Technology, Vol. 6,
No. 3, p. 29, 2015.
[10] Huiping Cao, Nikos Mamoulis, and David W Cheung. Discovery of periodic patterns in spatiotemporal sequences.
IEEE Transactions on Knowledge and Data Engineering,Vol. 19, No. 4, pp. 453–467, 2007.
[11] Nikos Mamoulis, Huiping Cao, George Kollios, Marios Hadjieleftheriou, Yufei Tao, and David W Cheung. Mining,indexing, and querying historical spatiotemporal data. In
Proceedings of ACM SIGKDD, pp. 236–245, 2004.
[12] Zhenhui Li, Jiawei Han, Ming Ji, Lu-An Tang, Yintao Yu,
Bolin Ding, Jae-Gil Lee, and Roland Kays. Movemine: Mining moving object data for discovery of animal movement
patterns. ACM Transactions on Intelligent Systems andTechnology, Vol. 2, No. 4, p. 37, 2011.
[13] Zhenhui Li, Jiawei Han, Bolin Ding, and Roland Kays. Mining periodic behaviors of object movements for animal andbiological sustainability studies. Data Mining and Knowledge Discovery, Vol. 24, No. 2, pp. 355–386, 2012.
[14] Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu,
et al. A density-based algorithm for discovering clusters inlarge spatial databases with noise. In Proceedings of ACM
SIGKDD, Vol. 96, pp. 226–231, 1996.
[15] Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing
Xie, Guangzhong Sun, and Yan Huang. T-drive: driving directions based on taxi trajectories. In Proceedingsof SIGSPATIAL, pp. 99–108, 2010.
[16] Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun.
Driving with knowledge from the physical world. In Proceedings of ACM SIGKDD, pp. 316–324, 2011.