DEIM Forum 2015 E8-3

密度に基づく意味的な軌跡パターンの発見
姜

仁河†

菁†

趙

董テイテイ†

佐々木勇和††

石川 佳治†,†††† 名古屋大学大学院情報科学研究科†† 名古屋大学未来社会創造機構††† 国立情報学研究所
E-mail: {jiang,zhao,dongtt,yuya}@db.ss.is.nagoya-u.ac.jp, ishikawa@is.nagoya-u.ac.jp
あらまし

近年，軌跡処理に関連した研究分野において，研究の重点は単純な移動軌跡データから意味的な移動軌跡

データへ変化しつつある．特に，意味的な情報と空間的な情報を両方兼ね備える意味的な軌跡パターンの発見という新しい研究が最近出現してきた．系列パターンの発見の技術と軌跡のクラスタリングの技術の組合せが鍵となる．本
研究では，先行研究を参考にした上で，密度に基づく意味的な軌跡パターンを提案する．そして，提案した意味的な軌跡パターンが持つ性質について述べる．最後に，発見した性質を利用することで効率よく意味的な軌跡データベー
スからすべての密度に基づく意味的な軌跡パターンを発見可能な手法を提案する．
キーワード

軌跡, 意味的な軌跡, 系列パターン, クラスタリング, DBSCAN
ある．TPMFP の研究で，タクシーの移動軌跡データを利用し1. は じ め にて実験が行われた．

GPS デバイス，センサ，ソーシャルネットワークサービス

以上の研究で取り扱っていた単純な GPS 移動軌跡データはなどの，いろいろな情報源から膨大な軌跡データが発生してい以下のような時刻 (t) と位置 (l) のペアで構成された一連のシーる．移動軌跡データには，人間活動の情報がたくさん含まれてケンス {Oid, (t1 ，l1 )，(t2 ，l2 )，．
．
．
，(tn ，ln )} で表現可能である．

いる. そこから検出された人間活動の習慣やパターンを利用し車などの GPS デバイスから収集してきた単純な軌跡データて，我々の日常生活への支援を提供できるとされる. そのため，に対して，Facebook や Twitter，Foursquare などのソーシャ

移動軌跡データを対象にした問合せ処理やマイニング処理に関ルネットワークサービスにおいても，大量の意味的な移動軌跡する研究が積極的に行われている. それに関する研究は主に以データが得られる．例えば，Foursquare において，あるユーザ

下の三つに分けられる．

はオフィス，レストラン，家で前後して 3 回チェックインした(1) 軌跡のクラスタリング：TRACLUS (Trajectory Cluster-

とき，「オフィス → レストラン → 家」という一つの意味的なing) [6] は入力された軌跡データを短い軌跡セグメントに分割

移動軌跡が生成されたと考えることができる．意味的な移動軌

して，それらの短い軌跡セグメントに対してクラスタリングを跡データには，時刻情報と位置情報に加えて，オフィスやレス行うという軌跡のクラスタリング手法である．TRACLUS の研

トランや家などのカテゴリ情報も含まれる．従来の単純な移動究において，動物と台風の移動軌跡データが研究対象とされた．

軌跡データの拡張として，意味的な移動軌跡データは時刻 (t)，(2) 軌跡からのパターンの発見: T-Pattern (Trajectory Pat-

位置 (l)，カテゴリ (c) のトリプルで構成された一連のシーケン

tern) [7] は代表的な軌跡パターンの発見に関する研究である．
t

t

t

1
2
n
T-Pattern の研究では RoI0 −→RoI
1 −→ ... −→ RoIn のような一連のシーケンスで軌跡パターンを表す．RoIi (Region ofス {Oid, (t1 ，l1 ，c1 )，(t2 ，l2 ，c2 )，．
．
．
，(tn ，ln ，cn )} で表現可能である．
そのような意味的な軌跡データから意味的な軌跡パターンをInterest) は発見された多くの軌跡により経由された領域であ発見する代表的な研究は Splitter [1] である．研究の本質は軌跡

り，ti は二つの RoI 間の遷移時間である．T-Pattern の研究にのマイニング処理で，軌跡のクラスタリングの研究と軌跡からおいて，トラックの移動軌跡データが用いられた．T-Patternのパターンの発見の研究の組合せだと考えられる．Splitter にの他，flock [11], swarm [12], convoy [10], gathering [13] の四つより発見されたパターンは意味的な情報と空間的な情報を両方の軌跡パターンも提案された．

兼ね備えるのが最大の特徴になる．また，Splitter の研究にお(3) 軌跡からの最適経路の発見: MPR (Most Popular Route)[8] は起点と終点を入力として，軌跡データをもとに，二点間のいて，Foursquare におけるチェックインデータを実データとして実験が行われた．

一番人気がある経路を発見するという人気経路に関する問合せ

本研究は先行研究 Splitter をベースにして，Splitter で考慮処理の研究である．MPR の研究では，T-Pattern の研究と同されていない問題点に対して，密度に基づく概念 [5] で意味的

じく，トラックの移動軌跡データが利用されていた．TPMFP

な軌跡パターンを再定義して，さらにその定義と合わせた効率(Time Period-based Most Frequent Path) [9] は起点と終点に的なマイニング手法を提案する．最後に評価実験により提案手加えて，時間帯も入力として，その時間帯の二点間の一番頻繁法の有効性と効率性を示す．先行研究 Splitter の具体的な内容な経路を発見するという頻繁経路に関する問合せ処理の研究で及び問題点は次の章で紹介する．

オブジェクト 意味的な軌跡

系列パターン 頻度

SID 系列 (Sequence)
1

A B C D2

A E B C

3

A B C

4

A C D E(a) 系列データベース

4o1< p 3 , p1 , p7 , p9 >3o2

< p5 , p7 , p2 , p7 , p10 >

C

4

o3

< p 3 , p6 >

A B

3

o4

< p2 , p1 , p6 , p8 , p11 >

A C

4

o5

< p12 , p8 , p11 , p4 >

B C

3

A B C

3

A
B

図 2 軌跡データベース(b) 系列パターン

図 1 系列データベースと系列パターン

2. 問題の概要
2. 1 既 存 研 究
2. 1. 1 系列パターンの発見に関する研究
系列パターンの発見（sequential pattern mining）[2] は，系
列データベースから，ユーザが指定した閾値を満たす出現順序

図 3 意味的な軌跡パターンの発見を維持した部分列を系列パターンとして発見するデータマイニ
ング分野で非常に有名な研究である．

いずれのカテゴリに属する．

系列データベース (sequence database) は複数の ID 付きのこのような軌跡データベースを系列データベースとして処理

系列データ (sequence data) により構成され，系列データはア

して，各場所 pi をアイテムとして取り扱う．すると，最小支持イテム (item) により構成される．系列データベースの例を図度が 3 の場合，場所 pi で構成された系列パターンは一つも発1(a) に示す．全部合わせて四つの系列データ，五つのアイテム

見できない．しかし，距離が近く同じカテゴリに属する場所を(A B C D E) がある．ユーザにより指定された閾値が 3 の場

一つのグループにして，このようなグループをアイテムとして合，図 1(a) の系列データベースから，図 1(b) が示すように，取り扱うと，最小支持度が 3 の場合，図 3 に示すように，系列

頻度が 3 以上の 7 個の系列パターンを発見可能である．その閾パターン G1 → G2 → G3 を発見可能になる．

値は最小支持度 (minimum support) という．部分列がデータ

以上のような空間的な情報（位置）と意味的な情報（カテ

ベースで出現した最低頻度を制限する．すなわち，部分列の頻ゴリ）の両方を兼ね備える系列パターンを発見するために，度が最小支持度より小さくなければ，系列は頻出系列になり，

Splitter 手法は二つのステップでマイニング処理を行う．

すなわち，系列パターンになる．

•

まず，意味的な軌跡データベースをカテゴリで構成さ系列パターンの発見の研究 [2] で提案された AprioriAll 手

れた系列データベースへ変換して，系列パターンの発見手法

法より，Pei らは，効率的な PrefixSpan [3] 手法を提案した．

PrefixSpan [3] により粗粒度パターン（Coarse Pattern）を発PrefixSpan は系列パターンの発見問題への有効な手法として，見する．同時に，Snippet と呼ばれる粗粒度パターンに対応すよく使われる．

る部分軌跡の集合も求められる．例えば，図 3 に示す「オフィスまた，系列パターンを効率よく発見することを可能にした重要なポイントは以下の Apriori 性質である．

•

Apriori 性質：頻出する系列の部分系列も頻出する．

→ ジム → レストラン」の粗粒度パターンに対応する Snippet
は < p1 , p7 , p9 >（o1 の部分軌跡）, < p2 , p7 , p10 >（o2 の部分軌跡）, o4 の < p1 , p8 , p11 >（o4 の部分軌跡）の三つがある．

例えば，表 1(b) に示すように，長さ 3 の頻出系列 A B C の部分系列はすべて頻出である．Apriori 性質に基づいて，長さk の系列パターンを検出するとき，長さ k − 1 の系列パターンが活用可能になる．本研究も意味的な軌跡パターンの発見へ

Apriori 性質の応用を基礎にする．
2. 1. 2 意味的な軌跡パターンの発見に関する研究
この節で本研究の基礎となる意味的な軌跡パターンの発見の研究 Splitter [1] を紹介する．
先に紹介した通り，Splitter の研究で取り扱っていた軌跡デー
タは従来の単純の軌跡データに加えてカテゴリ情報も付いた意
図 4 細粒度系列パターンの例

味的な軌跡データになる．具体的に，図 2 に示すような場所 piのシーケンスで表示された軌跡のデータベースがあるとする．
各場所 pi は図 3 に示すように，オフィス，ジム，レストランの•次に，粗粒度パターンに対応する部分軌跡をクラスタリ

ングすることで，距離が近い軌跡により構成されたクラスタを得表 1 本稿で用いる記号

る．そのようなクラスタを最終の結果となる細粒度系列パターン記号

意味に対応する部分軌跡を Snippet と呼ぶ．図 4 を例に説明すると，

T

軌跡データ

粗粒度パターン「オフィス → レストラン」が発見され，それにOid

移動オブジェクトの ID(ti , li )i 番目の時刻と位置のペア(ti , li , ci )i 番目の時刻，位置，カテゴリのトリプル（Fine-Grained Sequential Pattern）と呼ぶ．粗粒度パターン

対応する Snippet が五つがあり，それから二つの細粒度パターン{Snippet1 , Snippet2 } と {Snippet3 , Snippet4 , Snippet5 } が発Ci

意味的なパターンの i 番目のアイテム

S

SnippetSS

Snippet の集合

本研究の基礎である [1] の問題点には主に以下の二つがある．

p

Point または場所

•

S.pi

Snippet のポジション i での Point

M inSup

パターン発見のための最小支持度

η

DBSCAN 手法における距離の閾値

見可能になる．

2. 2 既存研究の問題点と本研究のポイント(1) Snippet の距離関数が定義されていない．細粒度系

列パターンの本質は，距離が近い Snippet により構成されたクラスタである．Splitter は空間的な偏差（spatial variance），

M inObjs DBSCAN 手法における密度の閾値

すなわち，座標値の偏差に基づいた細粒度系列パターンの定義を提案し，距離の制約を実現した．具体的には，細粒度パター∑
ン G1 → G2 → ．
．
．→ Gk に対し， k1 ki=1 V ar(Gi ) <= ρ という制約条件がある．V ar(Gi ) は Gi にある場所 pi の座標値の偏差で，ρ は閾値である．Splitter 手法は二つ目のステップでSnippet を処理対象としてクラスタリングを行うが，直観的で計算しやすい Snippet の距離関数が提案されていない．そのため，Splitter 手法のクラスタリングのステップでの処理はとても複雑になる．

•(2) すべての粗粒度パターンから細粒度系列パターンを効率よく発見する手法は提案されていない．Chao らは [1] で一つだけの粗粒度パターンに対して細粒度系列パターンを発見することに着目して，有効性と効率性がある Splitter 手法を提案
したが，一つ目の処理ステップで PrefixSpan 手法により発見されたすべての粗粒度パターンに対して，どのように効率よく細粒度系列パターンを発見するべきかについて議論しなかった．
以上の問題点に対して，本研究のポイントは以下の三つがある．(a) 直観的で実用性が高い Snippet 間の距離関数を提案して，DBSCAN [5] で効率よく Snippet をクラスタリングすることを実現する．(b) Snippet 間の距離関数の性質に基づいて，空間索引構造 M-tree [4] でクラスタリングを効率化する．(c) すべてのパターンの発見に対する Apriori 性質をベースにした効率よいマイニング手法を提案する．

•

Snippet 集合：本研究でデフォルトとして，Snippet 集

合はすべて同じ長さの Snippet により構成される．SS で表す．

•

Point 及びポジション： Snippet の i 番目の位置 li を

Snippet のポジション (Position)i での Point と呼ぶ．S.pi で表す．図 3 にある各場所 pi と同じ意味となるので，本稿で区別しない．そして，これから本稿において p のシーケンス{p1 , p2 , ..., pn } で Snippet を表す．
•

軌跡パターン： [1] における細粒度系列パターン，すな

わち，距離が近い Snippet により構成された Snippet のクラス
タを本稿で軌跡パターンと呼ぶ．

•

極大の軌跡パターン： 二つの長さ k の Snippet クラス

タ A と B があり，もし A ∩ B =| ∅ であれば，A と B は重なるという．そして，他の Snippet クラスタと重なりがなく，サイズが極大の Snippet クラスタを極大の軌跡パターンと呼ぶ．本
研究の目標はこのような極大の軌跡パターンを発見することなので，これから本稿では極大の軌跡パターンを軌跡パターンとして述べる．

3. 2 Snippet の距離関数
意味的なパターンから意味的な軌跡パターンを発見するとき，処理対象である Snippet はすべて意味的なパターンと同じ長さを持つ．この前提条件のもとで，Snippet の距離関数を以下のように定義する．

3. 問題の定義

nd(S1 , S2 ) = max |EuclideanDistance(S1 .pi , S2 .pi )|i=1

本稿で説明に用いる記号を表 1 に示す．

3. 1 基 本 概 念

二つの Snippet 間の距離は各対応する点の間のユークリッド•

距離の最大値になる．

意味的な軌跡：意味的な軌跡は時刻，位置，カテゴリのトリプルで構成されたシーケンスである．簡単のため、これ

3. 3 Snippet の密度に関する概念から本稿で意味的な軌跡を軌跡と呼ぶ．T = Oid, (t1 ，l1 ，c1 )DBSCAN [5] は任意形状のクラスタの抽出を目的とした密度，．
．
．
，(tn ，ln ，cn ) で表す．

•

（density）に基づくクラスタリング手法である．要求されるパ

意味的なパターン： [1] における粗粒度パターン，すな

ラメータは二つがあり，一つ目は距離閾値 η で，二つ目は密わち，カテゴリ（ci ）により構成された系列パターンを本稿で度閾値 M inObjs である．DBSCAN [5] で Neighbor Object,

意味的なパターンと呼ぶ．C1 → C2 → ... → Cn で表す.

Core Object, Direct Density-Reachable, Density-Reachable,•

Snippet： [1] における Snippet の概念をそのまま使う．

Snippet は意味的なパターンに対応する部分軌跡であり，軌跡と同様に表現できる．これから本稿では軌跡の代わりに，Snippet
をキーワードにして述べる．

Density-Connected という五つの概念が提案された．改めてSnippet に拡張したこの五つの概念を説明する．
•

Neighbor Snippet（近傍 Snippet）：距離が η の Snippet

は近傍 Snippet になる．図 5 において，S2 の近傍 Snippet はことができる．具体的には，Snippet を元々の DBSCAN の処
理対象である Point として取り扱い，前章で提案した Snippet
距離関数により Snippet 間の距離を計算して，これ以外は元々の DBSCAN と同じようなプロセスで処理する．元々の DB-

SCAN と区別するために，Snippet に拡張した DBSCAN をSDBSCAN と呼ぶ．
図 5 Snippet の Density-Connected の例，M inObjs = 2

4. 1. 2 SDBSCAN の効率化
元々の DBSCAN 手法においては，空間索引構造 R-tree のS1 , S3 となる．
•

利用で，時間がかかる範囲問合せを効率よく処理可能になる．

Core Snippet：近傍 Snippet の数が M inObjs 以上の

しかし，SDBSCAN において，ある Snippet の η 以内の近傍

Snippet は Core Snippet となる．図 5 に S2 , S3 は Core Snip-

Snippet 集合を求めるという Snippet の範囲問合せ処理が必要

pet となる．

である．前章で提案した Snippet の距離関数はユークリッド距•Snippet の Directly Density-Reachable：Snippet P ,Q

離でないので，直接 R-tree を利用できない．したがって，ボトがあり，Q は P の近傍 Snippet で，P は Core Snippet である

ルネックである Snippet の範囲問合せ処理に対して，R-tree のなら，Q は P から Directly Density-Reachable となる．図 5

代わりに，もう一つのよく使われる空間索引構造である M-tree

において，S1 は S2 から Directly Density-Reachable である．

を利用した改善手法を提案する．

•

Snippet の Density-Reachable：一連の Snippet S1 S2 ...

M-tree は距離に基づく検索に対する有効な空間索引である．

Si ...Sn が あ り, P = S1 , Q = Sn , Si+1 は Si か ら Di-

以下の四つの性質を満たすと，関数 d(Oi , Oj ) は距離関数でrectly Density-Reachable であるならば，Q は P から Density-ある．

Reachable となる．図 5 におい て，S1 は S3 から Density-•

同一律 (reflexivity): d(Oi , Oi ) = 0

Reachable である．

•

非負性 (non-negativity): d(Oi , Oj ) >=0

Snippet の Density-Connected：Snippet P ，Q，O が•対称性 (symmetry): d(Oi , Oj ) = d(Oj , Oi )あり，P は O から Density-Reachable であり, Q も O から•

三 角 不 等 式 (triangular inequality):•

Density-Reachable であれば，P と Q は Density-Connectedd(Oi , Ok ) +d(Ok , Oj ) >= d(Oi , Oj )となる．図 5 において，S1 と S4 は Density-Connected である.

3. 4 密度に基づく軌跡パターン
同じ長さの Snippet により構成された Snippet 集合 SS があり，以下の二つの条件を満たせば，SS を密度に基づく軌跡パターンと呼ぶ．

(1) 集合 SS のサイズ >=M inSup．
(2) 集合 SS 中の Snippet は η と M inObjs 条件のもとでDensity-Connected である．
3. 5 密度に基づく意味的な軌跡パターン
意味的なパターン C1 → C2 → ．
．
．→ Ck があり，それに対応

図 6 Snippet 間の距離が三角不等式を満たすことの例

する長さ k の Snippet 集合 SS があるとする．SS が密度に基づく軌跡パターンになれば，密度に基づく意味的な軌跡パター定理 1. Snippet 間の距離は距離の公理を満たす.

ンにもなる．

証明. P ，R，Q の三つの Snippet があり，i，j ，m 三つのポ

3. 6 密度に基づく意味的な軌跡パターンの発見

ジションがあり，P ，Q 間の距離 d(P, Q) = d(P.pm , Q.pm )，本研究の最終の問題定義である密度に基づく意味的な軌跡パ

R，Q 間 の 距 離 d(R, Q) = d(R.pi , Q.pi )，P ，R 間 の 距 離ターンの発見の定義は以下になる．
与えられた M inSup, η, M inObjs の条件のもとで，意味的な軌跡データベースからすべての密度に基づく意味的な軌跡パ
ターンを発見する．

4. 提 案 手 法
4. 1 密度に基づく軌跡パターンの発見
4. 1. 1 SDBSCAN
密度に基づく軌跡パターンの発見は実際には Snippet のクラd(P, R) = d(P.pj , R.pj ) となるとする．Snippet 間の距離関数により，d(R.pi , Q.pi ) >= d(R.pm , Q.pm )，d(P.pj , R.pj ) >=(P.pm , R.pm ) がある．
∵ d(R.pi , Q.pi ) >=d(R.pm , Q.pm )， d(P.pj , R.pj )>=(P.pm , R.pm )∴ d(R.pi , Q.pi ) + d(P.pj , R.pj )>=d(R.pm , Q.pm ) +d(P.pm , R.pm )∵ d(R.pm , Q.pm ) + d(P.pm , R.pm ) >= d(P.pm , Q.pm )∴ d(R, Q) + d(P, R) >= d(P, Q)

スタリングとなる．前章で提案した Snippet の密度に基づく

以上で三角不等式の性質を満たすことを証明した．また同一概念に基づいて，DBSCAN で Snippet をクラスタリングする

律，非負性，対称性を満たすことは簡単に証明可能で，本稿で

補助定理 1. Snippet 集合 SS があり，SS にある Snippet S がは省略する．
定理 1 により，入力された Snippet 集合に対して M-tree を作って，M-tree で Snippet の範囲問合せを処理することが可能になる．これで SDBSCAN を効率化する．

与えられた η と M inObjs について Core Snippet であるとき，

SS のポジション i での Point 集合において，S のポジション
i での P oint S.pi は同じ条件のもとで Core Point である．

4. 2 密度に基づくすべての意味的な軌跡パターンの発見

補助定理 2. Snippet 集合 SS があり，SS にある Snippet X

4. 2. 1 単純な発見手法と Y が与えられた η と M inObjs について Directly Density-

単純な発見手法の処理の流れをアルゴリズム 1 にまとめ

Reachable であるとき，SS のポジション i での Point 集合にる．前述の通り，二つのステップでマイニング処理を行う．(1)

おいて，X.pi と Y.pi は同じ条件のもとで Directly Density-

すべての意味的なパターンの発見: 軌跡データベースをカテ

Reachable である．

ゴリにより構成された系列パターンのデータベースに変換する．PrefixSpan 手法ですべての意味的なパターンと対応する

Snippet 集合を得る．データ構造でパターンと Snippet 集合
をペアとして格納する．(2) 意味的なパターンに対する密度に基づくすべての軌跡パターンの発見: Snippet 集合を一つずつ

補助定理 3. Snippet 集合 SS があり，SS にある Snippet X とY が与えられた η と M inObjs について Density-Reachable であるとき，SS のポジション i での Point 集合において，X.piと Y.pi は同じ条件のもとで Density-Reachable である．

SDBSCAN でクラスタリングする．η と M inObjs の条件のも定理 2. Snippet が Density-Connected であるならば，対応するとで Density-Connected な Snippet のクラスタ集合を候補集

Point は Density-Connected である． すなわち，Snippet 集合

合に追加する．最後に候補集合からサイズが M inSup 以上のSS が与えられた η と M inObjs について Density-Connected

Snippet クラスタを最後の結果集合に追加する．

な Snippet のクラスタであれば，SS のポジション i での Point

4. 2. 2 成長型の発見手法

集合は同じ条件のもとで Density-Connected な Point のクラス

単純な発見手法は各 Snippet 集合を独立で一つずつ処理する

タである．

ことで，すべての密度に基づく意味的な軌跡パターンを発見す
る．M-tree を利用した SDBSCAN でクラスタリング処理を効証明. 先に示した補助定理により定理 2 が成立する．

率化できるが，すべてのパターンを発見するには，まだ不十分

性質 1. Snippet が Density-Connected であるならば，対応だと考えられる．長い軌跡パターンを発見する時，処理済の短する部分 Snippet は Density-Connected である.

い軌跡パターンを活用できれば効率をさらに改善可能であるとSnippet 集合は与えられた η と M inObjs について Density-

すなわち，考える．以下で，これに関連して導出した性質を列挙する．

Connected な Snippet のクラスタであれば，同じポジションで前提条件. Snippet 集合 SS があり，SS にある N 個の Snippetの部分 Snippet により構成された Snippet 集合は同じ条件のもが同じポジションで同じ Point を持つ場合，N 個のユークリッとで Density-Connected な Snippet のクラスタである．

ド距離がゼロの Point と見なす．以下の補助定理や性質はすべてこの前提条件に基づく．

例を用いて説明する．図 2 にある Snippet S1 {p1 , p7 , p9 },S2 {p2 , p7 , p10 }, S3 {p1 , p8 , p11 } は同じポジション 1, 3 での部分
Snippet をそれぞれ S1′ {p1 , p9 }, S2′ {p2 , p10 }, S3′ {p1 , p11 } とな

Algorithm 1 Naive Mining
1: 入力：T rajectorySet, M inSup, η, M inObjs▷ 軌跡集合，最小支持度の閾値，距離の閾値，密度の閾値2:

も Density-Connected である．
性質 1 は本質的に Apriori 性質と同じである．すなわち，

3: 出力： Snippet Cluster Set
4:

る．S1 , S2 , S3 が Density-Connected であるならば，S1′ , S2′ , S3′▷ 条件を満たした密度に基づく意味的な軌跡パターンの集合

5: アルゴリズム：
6: R ← ∅;▷ Result Snippet Cluster Set

7: C ← ∅;▷ Candiadate Snippet Cluster Set

Snippet の Density-Connected は Apriori 性質を満たす．
性質 2. 長さ k の Snippet 集合 SS があり，その中の Snippet の
長さ k − 1 の接頭辞（注 1）により構成された長さ k − 1 の Snip′

8: SequenceSet ← T ransf orm(T rajectorySet);

pet 集合 SS があるとする．SS が与えられた η と M inObjs に

9: P atternSet ← P ref ixSpan(SequenceSet, M inSup);

ついて Density-Connected な Snippet クラスタであれば，SS

10: foreach pattern ∈ P atternSet doは同じ条件のもとで Density-Connected な Snippet クラスタで11:

SnippetSet ← GetSnippetSet(pattern);

12:

C ← SDBSCAN (SnippetSet, η, M inObjs);

13:

foreach cluster ∈ C do
> M inSup thenif cluster.size =14:

R ← R ∪ cluster;

15:
16:
17:

end ifend for

18: end for
19: output R;′ある．
注 1. 長さ k の Snippet{p1 , p2 , ..., pk } の長さ k − 1 の接頭辞は Snippet{p1 , p2 , ..., pk−1 } となる．たとえば，長さ 4 のSnippet{p1 , p2 , p3 , p4 } の長さ 3 の接頭辞は Snippet{p1 , p2 , p3 }となる．簡単のため，長さ k の Snippet{p1 , p2 , ..., pk } の長さ

k − 1 の接頭辞を直接 Snippet の接頭辞と呼ぶ．
ここからは性質 2 に基づいた成長型の発見手法を提案する．

の処理結果が存在する場合，Apriori 性質により，接頭辞の処理結果で Snippet 集合をいくつかの Snippet クラスに分割して，各 Snippet クラスを別々に処理することが可能になる．これは 22 行目までの処理となる．サイズが M inSup より小さい Snippet クラスを直接枝刈りできる．サイズが M inSup より小さくない Snippet クラスを一つずつ SDBSCAN でクラス
タリングする．η と M inObjs の条件で Density-Connected な

Snippet のクラスタ集合を候補集合に追加する．以上は 23 行
目から 27 行目までの処理となる．最後に候補集合からサイズ
が M inSup より小さくない Snippet クラスタをパターンの結図 7 成長型の発見手法

処理の流れをアルゴリズム 2 にまとめる．手法の概要は以下の四点になる．

果集合に追加する．これは 30 行目以降の処理となる．

Algorithm 2 Growth-Type Mining
入力：T rajectorySet, M inSup, η, M inObjs(1) 辞書順でソートされたパターンを一つずつ処理(2) 接頭辞の処理結果により Snippet 集合をクラスに分割(3) 条件に満足したクラスを一つずつ SDBSCAN で処理(4) 条件に満足した Snippet のクラスタを結果集合に追加
図 7 を例にして概要を説明すると，パターン C1 → C2 は辞書順でパターン C1 の後で処理される．C1 → C2 に対応するSnippet 集合 SS = {S1 , S2 , S3 , S4 , S6 , S7 , S8 , S9 } がある．SS

出力：Snippet クラスタの集合
4:

アルゴリズム：P atternSet ← P ref ixSpan(SequenceSet, M inSup);
8: SortedP atternSet ← Sort(P atternSet);

foreach pattern ∈ SortedP atternSet do
10:

M inSup を満たすかを判断し，クラスタとするかを決める．例

end forSnippetSet ← GetSnippetSet(pattern);
14:

C ←∅

16:

C ← SDBSCAN (SnippetSet, η, M inObjs);
else

18:

if pattern.pref ix.result=∅ then

20:

else

C ← ∅;

でクラスタリングする．
これから成長型の発見手法を具体的に説明する．軌跡データ

pResult ← pattern.pref ix.result;

ベースの変換と PrefixSpan 手法により意味的なパターンを発見することは前の手法と一致する．本手法のポイントは，長さk の Snippet 集合を処理するとき，長さ k − 1 の Snippet 集合

22:

SnippetClassSet ← Classif y(pResult, SnippetSet);

24:

foreach class ∈ SnippetClassSet do
if class.size >= M inSup thenの処理結果を参照することである．それを実現するために，まず，パターンと Snippet 集合のペアを格納するデータ構造に加C ← C ∪ SDBSCAN (class, η, M inObjs);
end if26:

えて，パターンと処理結果のペアを格納するデータ構造も必要になる．また，パターンを辞書順でソートする必要もある．例

end for28:

つ処理する．ここまでは 6 行目から 11 行目までの処理になる．
次に，長さ k のパターンの長さ k − 1 の接頭辞 (prefix) を求める．15 行目でパターンの接頭辞があるかどうかを判断し，パターンの長さが 1 の場合，すなわち，接頭辞がない場合，単純に SDBSCAN 手法でクラスタリングする．パターンの接頭辞

end ifend ifえば，辞書順でパターンをソートすると，パターン C1 C2 はパ
ターン C1 G2 G3 の前になる．ソートされたパターンを一つず▷ Candiadate Snippet Cluster Set

if pattern.pref ix = null then

えば，M inSup = 5 の場合，二つのクラスともクラスタとはしない．M inSup = 3 の場合，二つのクラスを別々に SDBSCAN

P rocessing(pattern);

12: function Processing(pattern)

二つのクラスにわける．それぞれをクラス 1{S1 , S2 , S3 , S4 } とクラス 2{S6 , S7 , S8 , S9 } と呼ぶ．この時点でクラスのサイズが▷ 条件を満たした密度に基づく意味的な軌跡パターンの集合

6: SequenceSet ← T ransf orm(T rajectorySet);

をクラスタリングする前に，C1 → C2 の接頭辞である C1 の処理結果，すなわち，クラスタ 1 とクラスタ 2 により SS を

▷ 軌跡集合，最小支持度の閾値，距離の閾値，密度の閾値

2:

30:

32:

foreach cluster ∈ C do
if cluster.size >= M inSup thenpattern.result ← pattern.result ∪ cluster;end if34:

end foroutput pattern.result;36: end functionがあるが，発見された接頭辞と対応する Snippet クラスタ，すなわち，接頭辞の処理結果が存在しない場合，Apriori 性質に本手法における Apriori 性質の応用には二箇所がある．いずより，本パターンから Snippet クラスタを一つも発見できないれも前で述べた性質 2 の直接応用になる．(1) 接頭辞の Snippetと決められるので，直接候補集合を空にする．これは 19 行目

集合から Snippet クラスタを発見できない場合，パターンのの処理となる．一方，パターンの接頭辞があり，かつ，接頭辞

Snippet 集合から Snippet クラスタも発見できない．(2) 接頭辞の処理結果によりパターンに対応する Snippet 集合を分割して別々に処理する．

5. 2 実 験 内 容
本章で用いるそれぞれの手法の略称を表 3 に示す．MSDB-SCAN は，M-tree を用いて効率化した SDBSCAN を表す．実5. 評 価 実 験験内容として，提案手法の正確性の検証実験，効率性の検証実5. 1 実 験 概 要

験，およびパラメータに関する実験の三つである．

5. 1. 1 実験データ

表3

評価実験に用いる各提案手法の略称

本研究では，人工データとして，Brinkhoﬀ 生成器 [14] を用い提案手法の略称

提案手法てオブジェクトの軌跡データを生成した．Brinkhoﬀ の生成器は，NaiveS

SDBSCAN を用いた単純な発見手法

道路ネットワーク上のオブジェクトの軌跡データを生成する．道NaiveM

MSDBSCAN を用いた単純な発見手法

路ネットワークとして，サンフランシスコの道路ネットワーク

GrowthS

SDBSCAN を用いた成長型の発見手法を用いた．軌跡データは座標が空間範囲 (0, 0) ∗ (30000, 30000)

GrowthM

MSDBSCAN を用いた成長型の発見手法

内の点により構成される．長さ 3 の軌跡データセットと，長さ6 の軌跡データセットを得るための処理プロセスは以下になる．
(1) 特定の長さの軌跡の作成．意味的な軌跡データの特徴として，サンプリングレートが低いことが挙げられる．そのため，生成した軌跡データをさらにサンプリングすることで，軌跡データを作成した．具体的には，生成した軌跡を 1/10 のレー

5. 2. 1 正確性の検証実験
以上の二つのデータセットに対して，NaiveM，GrowthS，GrowthM はすべて NaiveS と同じ処理結果を得た．さらに，他のデータセットに対して実行した場合でも，同じ結果が得られたため，提案手法の正確性が検証された．

長さ3の軌跡データセット

トでサンプリングした．本実験では，生成器のタイムスタンプ
数を 30 および 60 として生成した軌跡データを，1/10 のレー
トでサンプリングすることにより，長さ 3 および 6 の軌跡デー
タをそれぞれ作成した．

(2) 意味的な軌跡データの作成．ここで，本手法の有効性を検証するためには，長さ 3 の軌跡パターンの発見ができれば十分であることを例を用いて示す．C1 → C2 → C3 に対応する
意味的な軌跡パターンを発見できれば，C1 → C2 に対応する
意味的な軌跡パターンも発見できる．これは，すべてのパターンを発見可能であることを示し，手法の有効性を十分に検証できる．(1) の処理により作成した長さ 3 と 6 の軌跡データのそ

350

長さ6の軌跡データセット

308.1

300
) 250
S
(

間時200
行150
実
100
50
0

20.8
NaiveS

48.6
6.4

6.5 13.6

2.3 3.9

NaiveM

GrowthS

GrowthM

れぞれのポイントに，カテゴリ情報を付与する．具体的には，長さ 3 の軌跡データの三つのポイントそれぞれに A，B，C を

図 8 各手法の実行時間

カテゴリ情報として付与し，長さ 6 の軌跡データの六つのポイ
ントそれぞれに A，B，C，D，E，F を付与する．これにより，

5. 2. 2 効率性の検証実験
本実験で各手法の実行時間を比較する．各パラメータの値は意味的な軌跡データを生成した．

(3) 人工データセットの作成．まず，サイズが 3000 の軌跡
データセットを生成器により 20 個作成して，それぞれのデー
タセットに対して，クラスタリング手法により，軌跡パターンとなる軌跡データを抽出する．20 個のデータセットから軌跡パ
ターンとなる 5000 個の軌跡データを抽出する．その後，無作為の軌跡を 5000 個作成して，抽出した 5000 個の軌跡と合わせ

M inSup = 50, η = 2.0, M inObjs = 1 である.
図 8 に示す通り，軌跡データの長さが 3 の場合，NaiveM はNaiveS の約 1/3 程度の実行時間になり，GrowthM も GrowthSの約 1/3 程度の実行時間になる. 軌跡データの長さが 6 の場合，NaiveM は NaiveS の約 1/6 程度の実行時間になり，GrowthM
は GrowthS の約 1/3 程度の実行時間になる. この結果により，

MSDBSCAN の効率性が検証された．また，軌跡データの長さて，サイズが 10000 のデータセットを作成した．

が 3 の場合，GrowthS は NaiveS の約 1/3 程度の実行時間にな

5. 1. 2 実 験 環 境
実験で用いた計算機のスペックを表 2 に示す．実装は Java

り，NaiveM とほぼ同じ実行時間になるが，軌跡データの長さが 6 になると，GrowthS は NaiveS の約 1/25 程度の実行時間で行い，コンパイルには Eclipse を使用した．

になり，NaiveM の約 1/4 程度の実行時間になる．この結果に
表 2 実行マシンのスペック

OS

Windows7 Professional 64bit

CPU Intel(R) Core(TM) i7-4770 CPU @ 3.4GHz
CPU コア数
メモリ

より，成長型の発見手法の効率性が検証された．

5. 2. 3 パラメータに関する実験

8

最小支持度 M inSup と距離閾値 η を変化させて実験を行っ8GB

た．η = 2.0, M inObjs = 1 の条件のもとで，最小支持度

M inSup による発見された軌跡パターンの数の変化を図 9に示す．系列パターンと同じように，最小支持度が大きくなると，発見された軌跡パターンの数が少なくなる．また，両方とも Apriori 性質を満たすので，クラスタリング部分の処

M inSup = 50, M inObjs = 1 の条件のもとで，距離閾値 η に理を系列パターンの発見の処理に組み込むことが考えられる．

よる発見された軌跡パターンの数の変化を図 10 に示す．距離閾

それにより，より効率を上げられると予想している．最後に，値が大きくなると，発見された軌跡パターンの数はほぼ変わら

本研究で意味的な軌跡データに対して，カテゴリ情報と空間情ないことがわかる．原因は以下のように考えられる．Brinkhoﬀ

報を利用するが，時間情報を取り扱っていない．軌跡パターン

生成器により生成された軌跡データは道路ネットワークと合わの特性である空間的な近さに対して，時間的に近いという制限

せる軌跡データであるので，生成された軌跡は道路セグメントの追加も考えられる．そうすると，カテゴリ情報，空間情報，の近くに集積する．そのため，軌跡データの密度が高く，発見

時間情報の三つともを含めることができる．これにより，さらされた軌跡パターンの数は距離閾値によりあまり影響されない．

に実用性がある意味的な軌跡パターンをユーザに提供することが可能になる．

500
450
400
350
300
250
200
150
100
50
0

数
の
ンー
タパ
跡
軌
たれ
さ見
発
図9

441

謝

本研究の経費の一部は科学研究費（25280039）および地球環
境情報統融合プログラム（DIAS-P）による.
150

文

64

20

40

60

23

19

7

80

100

120

最小支持度

最小支持度 M inSup により発見された軌跡パターンの数

160

数
140
の
ンー120
タパ100
80
跡
軌
たれ60
さ見40
発200
図 10

辞

139
103

98

2

4

6

80

80

78

82

81

12

14

16

18

20

66

66

8

距離閾値

10

距離閾値 η により発見された軌跡パターンの数

6. まとめと今後の課題
本研究では，[1] で提案された意味的な軌跡パターンの発見の問題について述べ，改良手法を提案した．具体的には，軌跡の距離関数を提案して，それを用いて密度に基づく意味的な軌跡パターンを定義した．また，距離に基づく空間索引構造である M-tree で軌跡に拡張した DBSCAN 手法を効率化した．さらに，密度に基づく意味的な軌跡パターンが Apriori 性質を持つことを示した．最後に，この Apriori 性質に基いて，意味的な軌跡データベースから密度に基づくすべての意味的な軌跡パターンを効率よく発見する手法を提案した．実験を行うことで，本手法は軌跡データが長ければ長いほど有効性があると示した．
今後の課題として，まず，実際に SNS にある意味的な軌跡
データ，すなわち，チェックインデータを収集して，実データ
上で実験を行い，有効性を検証する．また，今の段階でクラスタリングと系列パターンの発見は二つのステップで行われるが，

献[1] Chao Zhang, Jiawei Han, Lidan Shou, Jiajun Lu, andThomas F. La Porta. Splitter: Mining fine-grained sequential patterns in semantic trajectories. PVLDB, Vol. 7, No. 9,
pp. 769–780, 2014.
[2] Rakesh Agrawal and Ramakrishnan Srikant. Mining sequential patterns. In ICDE, pp. 3–14, 1995.
[3] Jian Pei, Jiawei Han, Behzad Mortazavi-Asl, Helen Pinto,
Qiming Chen, Umeshwar Dayal, and Mei-Chun Hsu. PrefixSpan: Mining sequential patterns eﬃciently by prefixprojected pattern growth. In ICDE, pp. 0215–0215, 2001.
[4] Paolo Ciaccia, Marco Patella, and Pavel Zezula. M-tree:
An eﬃcient access method for similarity search in metricspaces. In VLDB, pp. 426–435, 1997.
[5] Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei
Xu. A density-based algorithm for discovering clusters inlarge spatial databases with noise. In KDD, Vol. 96, pp.
226–231, 1996.
[6] Jae-Gil Lee, Jiawei Han, and Kyu-Young Whang. Trajectory clustering: a partition-and-group framework. In SIGMOD, pp. 593–604, 2007.
[7] Fosca Giannotti, Mirco Nanni, Fabio Pinelli, and Dino Pedreschi. Trajectory pattern mining. In KDD, pp. 330–339,
2007.
[8] Zaiben Chen, Heng Tao Shen, and Xiaofang Zhou. Discovering popular routes from trajectories. In ICDE, pp. 900–911,
2011.
[9] Wuman Luo, Haoyu Tan, Lei Chen, and Lionel M Ni. Finding time period-based most frequent path in big trajectorydata. In SIGMOD, pp. 713–724, 2013.
[10] Hoyoung Jeung, Man Lung Yiu, Xiaofang Zhou, Christian S
Jensen, and Heng Tao Shen. Discovery of convoys in trajectory databases. PVLDB, Vol. 1, No. 1, pp. 1068–1080,
2008.
[11] Patrick Laube and Stephan Imfeld. Analyzing relative motion within groups oftrackable moving point objects. In
Geographic information science, pp. 132–144. 2002.
[12] Zhenhui Li, Bolin Ding, Jiawei Han, and Roland Kays.
Swarm: Mining relaxed temporal moving object clusters.
PVLDB, Vol. 3, No. 1-2, pp. 723–734, 2010.
[13] Kai Zheng, Yu Zheng, Nicholas Jing Yuan, and Shuo Shang.
On discovery of gathering patterns from trajectories. In
ICDE, pp. 242–253, 2013.
[14] Thomas Brinkhoﬀ. A framework for generating networkbased moving objects. GeoInformatica, Vol. 6, pp. 153–180,
2002.