DEIM Forum 2017 H7-5

ジオタグ付き写真の被写体を考慮した意味的な移動軌跡の分析
瀧本

祥章†

杉浦

健人†

石川

佳治†

† 名古屋大学大学院情報科学研究科 〒 464–8601 愛知県名古屋市千種区不老町
E-mail: † {takimoto, sugiura}@db.ss.is.nagoya-u.ac.jp, ishikawa@is.nagoya-u.ac.jp
あらまし GPS を搭載したモバイルデバイスの普及に伴い，ジオタグ付き写真などにより構成される意味的な移動軌跡が増加している．従来の移動軌跡はいつ，どこにユーザがいたのかのみを表す．これに対し，意味的な移動軌跡はその地点でユーザが何に注目しているのかを表し，関連する研究が盛んに行われている．本研究では，重み付きタグ
集合により構成される意味的な移動軌跡に対して頻出パターン抽出を行う．まず，意味的な移動軌跡から多くのユーザが訪問し，同じものに注目した領域を抽出する．次に，頻出する領域間の移動を抽出する．最後に，実データを用いた実験により，提案手法の有用性を示す．
キーワード 時空間分析，意味的な移動軌跡，Flickr，軌跡マイニング，時空間データマイニング

1. は じ め にGPS を搭載したモバイルデバイスの普及に伴い，位置情報に関連するサービスが増加している．例えば Twitter [5] であれば，ツイートが「どこで」つぶやかれたかをジオタグ付きツ

𝑇1

𝑝1

𝑇2

𝑝5
𝑝9 𝑇3
𝑝13

イートで表している．他にも，Flickr [2] であれば，写真が「ど

𝑝2
𝑟1

𝑝10
𝑟3

𝑝3 𝑟

𝑃1
𝑝6
𝑝14

𝑝4

2

𝑝11
𝑃2

𝑟4

𝑝7

𝑝8 𝑝12

𝑝15

𝑝16

𝑇4

こで」撮影されたのか，Swarm [4] であればユーザが「どこに」チェックインしたのかを表す．

軌跡

このような位置情報付きのデータは，意味的な移動軌跡とし

T1て近年注目されている [19]．従来の移動軌跡では，ユーザが

T2

「いつ」
・
「どこに」いたのかのみが表されるのに対し，意味的な移動軌跡はその地点に関する追加情報を持つ．例として Flickrのジオタグ付き写真を考える．あるユーザが観光地で写真を撮影し，Flickr にアップロードしたとする．このとき，アップ

T3
T4

意味的な移動軌跡[(p1 , {(鳥居, 0.8), (寺, 0.7), . . . }), (p2 , {(鳥居, 0.9), (神社, 0.8) . . . }),(p3 , {(寺, 0.8), (神社, 0.5), . . . }), (p4 , {(中国式建築物, 0.7), (寺, 0.6) . . . })][(p5 , {(木, 0.8), (川, 0.6), . . . }), (p6 , {(神社, 0.9), (鳥居, 0.7) . . . }),(p7 , {(寺, 0.9), (神社, 0.6), . . . }), (p8 , {(庭, 0.8), (公園, 0.6) . . . })][(p9 , {(花, 0.9), (池, 0.6), . . . }), (p10 , {(花, 0.9), (低木, 0.6) . . . }),(p11 , {(花, 0.8), (チューリップ, 0.5), . . . }), (p12 , {(花, 0.9), (木, 0.6) . . . })][(p13 , {(木, 0.8), (低木, 0.8), . . . }), (p14 , {(低木, 0.7), (花, 0.6) . . . }),(p15 , {(花, 0.9), (チューリップ, 0.6), . . . }), (p16 , {(川, 0.8), (池, 0.5) . . . })]図 1: パターン例（注 1）

ロードされた写真を時刻順に並べることで，図 1 のような写真に関する意味的な移動軌跡が生成できる．つまり，この例における追加情報は写真であり，ユーザが注目しているものを示す．
このような意味的な移動軌跡を解析することにより，ユーザが
「いつ」
・
「どこで」
・
「何に」注目していたのかを把握できる．
意味的な移動軌跡を活用するために，著者らの研究グループ
では頻出パターン抽出 [14] を行っている．つまり，複数のユー
ザが同じように移動し，同じ何かに注目した軌跡をパターンとして抽出している．図 1 の例であれば，軌跡 T1 と軌跡 T2 が同じように移動し，{p2 , p6 } では鳥居，{p3 , p7 } では寺と，同じものに注目している．そのため，{p2 , p6 } から {p3 , p7 } へ移動
するパターンを抽出できる．
しかし，上述の文献 [14] には 2 つの問題がある．1 つ目の問
題は，適用できる意味的な移動軌跡が制限されることである．
文献 [14] では，追加情報としてタグを持つ意味的な移動軌跡を対象とする．例えば，チェックインデータであればチェックイ
ンした POI（Point Of Interest）のカテゴリ情報をタグとして利用できる．しかし，ツイートや写真により構成される意味的な移動軌跡はタグを持たないため，適用できない．また，人手によるタグ付けも考えられるが，データ量によっては現実的ではない．2 つ目の問題は，前提条件として，注目すべき地点が全て既知，即ち有名な観光地や施設であるとする点である．そのため，「境内で紫陽花が綺麗に咲く場所」，「漫画のシーンの元になった場所」など，興味を持つ人が一定数いるが有名ではない場所に対応できない．
そこで本研究では，各点の特徴を重み付きタグ集合で表し，注目すべき場所である ROI（Region Of Interest）の動的な抽出により，上述の問題を解決する．まず 1 つ目の問題は，機械学習による追加情報の重み付きタグ集合への変換により解決する．例えば，ツイートであればトピック分析，写真であればGoogle Cloud Vision API [3]（以降，Vision API と呼ぶ）な
どの一般物体認識技術が利用できる．これにより，機械的に処理できるためビッグデータにも対応可能である．次に 2 つ目の問題は，観光地などの背景知識を用いずに，機械学習の分析結果のみから ROI を抽出することにより解決する．これにより，（注 1）：写真は Flickr から収集したデータセット中の画像（以下同様）

上述のような有名でない場所も ROI として抽出できる．

本研究では，追加情報として重み付きタグ集合を持つ意味的

地をアイテムとしてとらえ，シーケンスパターンとして抽出すな移動軌跡を対象とし，それらから頻出パターンを抽出する手る．しかし，滞在地ベースのパターンは，近傍に存在するほぼ法を提案する．まず，各意味的な移動軌跡の位置情報と重み付

同一の滞在地を区別してしまうという問題があった．

きタグ集合から，多くのユーザが訪問し同じものに注目した領

これに対し，Zhang らや Jiang らは近傍に存在する同一の滞域である ROI を抽出する．次に，抽出した ROI 間の移動から在地をまとめることにより，この問題を解決した [14, 21]．こ頻出するパターンの抽出を行う．例えば，図 1 のような意味的

れらの研究では，ユーザが訪れた POI のカテゴリ情報を追加

な移動軌跡 {T1 , T2 , T3 , T4 } と最小支持度 2 が与えられたとす情報とする意味的な移動軌跡を対象とし，近隣に存在する同一る．位置情報のみに注目すると，各移動軌跡は同じ移動パター

カテゴリを持つ POI をクラスタリングにより，1 つのグルーンを持つように見える．しかし実際には，各ユーザは異なるもプとしてまとめてシーケンスパターンを抽出した．なお，クラのに注目しており，2 つの移動パターンが得られる．まず，点スタリングは，Zhang らが mean-shift [7] ベース，Jiang らがp2 と点 p6 は鳥居など同じタグを持ち，近傍に存在する点であDBSCAN [9] ベースで行っている．しかしこれらの研究には，ることから，ROI r1 として抽出できる．同様に，p3 と p7 から

POI の一覧とそのカテゴリ情報が既知であり，ユーザが訪れた

r2 ，p10 と p14 から r3 ，p11 と p15 から r4 を抽出できる．次に，POI も明らかであることを前提とするという問題がある．これ

ROI 間の移動の内，最小支持度以上のものを抽出する．この例に対し我々の研究では，意味的な移動軌跡から ROI の特定及では最小支持度が 2 であるため，P1 = [r1 , r2 ] と P2 = [r3 , r4 ]び，特徴を抽出するため，未知の ROI に対応可能であり，事前を抽出できる．

情報を必要としない．一方，Ying ら [20] はユーザの位置予測

本稿の構成は以下のとおりである．まず 2. で関連研究としのために意味的なパターンの抽出を行った．しかし，パターンて，移動軌跡からのパターン抽出などについて述べる．次に 3.

抽出の際には位置情報に注目せず，ラベルのみに注目している．

で提案手法の概要について述べ，ROI の抽出について詳細を 4.

そのため，得られるパターンは「学校 → 公園 → レストラン」

で述べる．5. では，実データを用いた実験について述べ，最後などのラベルで表され，位置情報は無視される．これに対し，に，6. で本稿のまとめと今後の課題について述べる．

我々の研究では，位置情報も活用してパターンの抽出を行う．

Kim らの TOPTRAC [15] はテキストを追加情報として持つ

2. 関 連 研 究

意味的な移動軌跡からパターンの抽出を行った．具体的には，本章ではまず，移動軌跡からパターンを抽出する研究を紹介

同一トピックのテキストが多く投稿される領域を特定し，そのする．次に機械学習により，タグを付与するツールを紹介する．

領域間の遷移の内，頻出するものをパターンとして抽出する．

2. 1 移動軌跡からのパターン抽出

しかし与えるパラメータに，領域数やトピック数が必要である

移動軌跡からパターン抽出を行う研究は，対象の移動軌跡のが，これらの値を分析前に適切な値を設定することは困難である．これに対し本研究では，与えるパラメータは全て閾値であ

種類によって以下の 2 種類にわけられる．

•

り，抽出したいパターンの性質から設定できる．

従来の移動軌跡を対象とする研究

2. 2 機械学習によるタグの付与

移動軌跡の各点は位置情報及び時刻を持つ．

•

本節では実験で用いる分析ツールである ClarifaiAPI [1] やVision API [3] について述べる．

意味的な移動軌跡を対象とする研究
移動軌跡の各点は位置情報，時刻だけでなく，訪問した

Clarifai API はアメリカの Clarifai Inc. が提供しているサー

POI の情報やテキスト，画像などの意味的な情報を持つ．

ビスであり，一般物体認識や職場閲覧不適切画像判定を行える．
一方，Vision API は Google Inc. が提供しているサービスであ

これらの移動軌跡を対象とする研究について順に説明する．

2. 1. 1 従来の移動軌跡を対象とするパターン抽出

実行する分析を入力として受け取り，分析結果を出力する．各

従来の移動軌跡を対象とするパターン抽出の代表的な研究に∆tり，一般物体認識や OCR などを行える．両サービスは画像と∆t

1
2
T-Pattern [10] がある．T-Pattern では ROI0 −−→
ROI1 −−→

∆t

n
··· −
−−
→
ROIn と表されるパターンを抽出する．ここで，ROIi

は多くの軌跡が通過する領域であり，∆ti は ROI 間の遷移時

分析結果はその分析の確からしさを表す確信度が付加されている．例えば，両サービスを用いて伏見稲荷大社の鳥居の写真を
一般物体認識すると，図 2 のように複数のタグと確信度を得られる．

間を表す．他にも一定時間以上の間一定距離以内を共に移動するパターンである flock [16] や，swarm [17]，convoy [13]，gathering [22]，CACT [12] などさまざまなパターンが提案されている．また，ストリームデータからリアルタイムにパターンを抽出する研究 [8] も行われている．

2. 1. 2 意味的な移動軌跡を対象とするパターン抽出
意味的な移動軌跡を対象とするパターン抽出は Alvares ら [6]が初めに行った．Alvares らは従来の移動軌跡からユーザの滞在地を抽出し，その属性を地図から識別する．その後，各滞在

3. 提案手法の概観
提案手法は「ROI 系列への変換」と「意味的な軌跡パターンの抽出」の 2 ステップに分けられる．本章では，これらについて順に述べる．また，表 1 に本稿で用いる記号の一覧を示す．

3. 1 ROI 系列への変換
このステップでは，意味的な移動軌跡の集合 T raj を入力として受け取り，多くのユーザが同一のものに注目する領域である ROI を抽出する．その後，意味的な移動軌跡をその軌跡が

次に，本稿で抽出する ROI を以下のように定義する．
［定義 4］ ROI ri は近傍に存在する類似した点の集合である．
ただし，近傍や類似の基準はユーザやシナリオにより異なり，

ROI を抽出する際にはこれらを柔軟に変化させる必要がある．
（a） Clarifai API（b） Vision API

本稿における具体的な定義及び導出は 4. で述べる．
最後に，以下の手順で各軌跡を通過する ROI の系列に置き

タグ

確信度

タグ

確信度

people0.986

chinese architecture

0.982

換える．まず，各点 pi をそれが属する ROI rj に置換する．こfestival

0.966

torii

0.906

こで，点 pi がいずれの ROI にも属さない場合は削除する．次tourist0.961

shinto shrine

0.851に，連続する同一の ROI を削除をする．例えば，ROI の系列

group

0.953

temple0.848[r1 , r1 , r1 , r2 , r2 , r3 , r1 ] は [r1 , r2 , r3 , r1 ] になる．

temple0.949

building

.
.
.

..
.

0.814

..
.

..
.

図 2: 分析ツールによる写真の分析結果例
表 1: 本稿で用いる記号一覧

3. 2 意味的な軌跡パターンの抽出
このステップでは，入力として ROI 系列の集合と最小支持
度 M inSup を受け取り，頻出する ROI 系列を意味的な軌跡パターンとして出力する．本稿における意味的な軌跡パターンの定義は以下のとおりである．

記号

意味

T raj

意味的な移動軌跡の集合（データセット）［定義 5］ 意味的な軌跡パターン pattern = [r1 , . . . , rm ] は与pi

点えられた最小支持度 M inSup 以上の軌跡が順序どおりに

traj

意味的な移動軌跡

通過する ROI の系列である．

pattern

意味的な軌跡パターン

ri

ROI

本稿では以降，意味的な軌跡パターンを単にパターンと呼ぶ．
本稿では PrefixSpan [11] により ROI 系列からパターンを抽

tj

タグ

ctji

p

点 pi のタグ tj の確信度出する．PrefixSpan ではまず，長さ 1 の頻出するパターンを抽

ε

距離閾値

出する．次に，発見済みの頻出パターンの末尾に長さ 1 の頻出

τ

類似度閾値

パターンを追加したパターンについて，各々頻出であるか調べ

M inP ts密度閾値る．そして，頻出であったパターンに対し，更に長さ 1 の頻出

M inSup 最小支持度

パターンを追加して頻出であるか調べる．以後，同様の処理を頻出パターンが発見できなくなるまで繰り返す．

通過する ROI の系列に置き換える．以下では，入力である意

4. ROI の抽出

味的な移動軌跡の定義及び，抽出する ROI について述べる．
まず，意味的な移動軌跡を以下のように定義する．

本章では，ROI の抽出について述べる．ROI は多くのユー
ザが同一のものに興味を持つ領域である．そのため，軌跡中の［定義 1］ 意味的な移動軌跡 traj = [p1 , . . . , pn ] は同一ユーザが生成した点を時系列順に並べた系列である．各意味的な移動軌跡の長さ n は異なってもよいものとする．

どの点が同一のものを表し，同領域に含まれることをどのように判断するかが重要となる．本稿では，各点の特徴はタグ集合により表されるため，タグ集合間の類似度を定め，分析者が与

ここで，軌跡上の各点 pi ∈ traj は (pi .loc, pi .tags, pi .con) のえる閾値以上の類似度を持つ点を同一とみなす．また，同領域

タプルで定義される．pi .loc は位置を表す二次元の座標であり，の判断には Jiang らと同様に DBSCAN [9] を用いる．ただし，

pi .tags はタグ集合である．また，pi .con は各タグの確信度を

DBSCAN では類似度を考慮することができないため，類似度表す．タグ集合及び確信度の詳細な定義は後述する．なお，本を考慮するように拡張した SimDBSCAN を提案する．最後に稿では移動軌跡の時刻情報を各点の前後関係を定めるためだけ

ROI の特徴を特定するため，ROI に含まれる点の重み付きタに用いるため，この定義では省略している．本稿では以降，意グ集合からトピックを抽出する．

4. 1 点間の類似度

味的な移動軌跡を単に軌跡と呼ぶ．
各点が保持するタグ集合及び確信度を以下のように定義する．
［定義 2］ タグ集合 pi .tags = {t1 , . . . , tl } は各点 pi が保持するタグ tj の集合である．

各点は重み付きタグ集合を持っているため，2 点間の類似度
をタグ集合間の類似度と定義する．タグ集合間の類似度には

Jaccard 係数を用いることが考えられるが，Jaccard 係数では確信度と各タグの価値の違いを考慮できないため，以下の拡張［定義 3］ 確信度 pi .con = {ct1i , . . . , ctli } は確信度の集合であppる．各確信度は点 pi が保持するタグ tj の確からしさを表pi <1 である．なお，タグ tj がタグ集合 pi .tags
し，0 <= ctj =に含まれない場合，その確信度は 0 である．

を行う．
各タグの確信度各点が保持するタグ集合は機械学習により統一的な基準で付加されたものであるため，類似する点は同一のタグを同程度の確信度で保持すると予想される．しかし，Jaccard 係数はタグ

sim

p1

の有無のみを用いて定義され，確信度の情報が失われる．そこ

p1

1.0 0.4 0.4 0.1

p2

0.4 1.0 0.6 0.3

グの確信度を重みとして使用する．この拡張を行った重み付き

p3

0.4 0.6 1.0 0.6

Jaccard 係数の式は以下のようになる．
∑
pjpi
tk min(ctk , ctk )′Jaccard (pi , pj ) = ∑pjpi
tk max(ctk , ctk )p4

0.1 0.3 0.6 1.0

で，同程度の確信度であるときに類似度が大きくなるようにタ𝜀𝑝1 𝑝2 𝑝3 𝑝4

p2

p3

p4

図 3: SimDBSCAN の例（表は 2 点間の類似度を表す）

(1)
である．

各タグの価値の違い

次に DBSCAN では，密度が大きい部分の繋がりを調べるた

タグ集合に含まれるタグには，多くの点が共通して保持する
ものと，そうでないものが存在すると予想され，実際に本稿の実験で用いたデータセットにもそのような傾向がみられた（5. 1 節 参照）．前者のタグを共通して持っている 2 点と後者のタグを共通して持っている 2 点では，後者の方がより類似していると考えられる．そこで，各タグ t の逆文書頻度 [18] を以め，直接密度到達可能や密度到達可能，密度接続を定義している．類似する点が多く存在する領域の繋がりを調べるため，

SimDBSCAN ではこれらに拡張を行い，直接類似到達可能，類似到達可能，類似接続をそれぞれ以下のように定義する．
まず，コアポイントとその周囲の関係を表す直接類似到達可能を以下のように定義する．

下のように定義し，重みとして使用する．

idft = log

N|{pi |t ∈ pi .tags}|［定義 8］ 点 pi , pj 及び，閾値 ε, τ, M inP ts が与えられ，以下(2)に関して直接類似到達可能である．

ただし，N はデータセット中の点の数である．
これらの拡張から，2 点 pi , pj 間の類似度を以下のように定義する．

∑

min(cptki , ctkj ) × idftk

pjpitk max(ctk , ctk ) × idftki) pj ∈ N eighborε,τ (pi )ii) M inP ts <= |N eighborε,τ (pi )|
例えば，図 3 中の点 p2 は点 p1 及び点 p3 に (ε, 0.3, 2) に関

ptsim(pi , pj ) = ∑ kの条件を全て満たすとき，点 pi は点 pj に (ε, τ, M inP ts)(3)

なお，sim(pi , pj ) は Jaccard 係数と同様に 0 <=1= sim(pi , pj ) <を満たし，その値が大きいほど，点 pi , pj は類似する．

4. 2 密度と類似度を考慮したクラスタリング
本節ではまず，密度と類似度を考慮したクラスタリングである SimDBSCAN に必要となる概念を順に定義する．その後，SimDBSCAN のアルゴリズムを示す．
4. 2. 1 概念の定義

して直接類似到達可能であるが，(ε, 0.5, 2) に関しては点 p2 がコアポイントとならないため，直接類似到達可能でない．
次に，直接類似到達可能の推移的関係である類似到達可能を
以下のように定義する．
［定義 9］ 一連の点 p1 , . . . , pi , . . . , pk があり，pi+1 は pi (1 <=i < k) に (ε, τ, M inP ts) に関して直接類似到達可能である
とき，点 p1 は点 pk に (ε, τ, M inP ts) に関して類似到達可能である．

SimDBSCAN に必要となる概念の定義について述べる．

例えば，図 3 中の点 p3 は点 p1 に (ε, 0.3, 2) に関して類似到DBSCAN では密集した点をクラスタにするため，周囲に点達可能であるが，(ε, 0.5, 2) に関しては類似到達可能でない．こが密集している点をコアポイントとして定義している．SimDB-

こで，点 p3 から点 p1 は (ε, 0.3, 2) に関して類似到達可能であSCAN では拡張を行い，周囲に類似した点が密集している点をるが，点 p1 から点 p3 は類似到達可能でない．このように類

コアポイントとして以下のように定義する．

似到達可能は対称性を持たない．そこで，DBSCAN と同様に，［定義 6］ (ε, τ )-近 傍 N eighborε,τ (pi ) = {pj |dist(pi , pj ) <=対称性を持つ類似接続を以下のように定義する．

| j} は点 pi から距離 ε 以内であε, τ <= sim(pi , pj ), i =［定義 10］ 点 po , pi , pj があり，点 po が点 pi 及び，点 pj にり，点 pi との類似度が τ 以上の点の集合である．なお，(ε, τ, M inP ts) に関して類似到達可能であるとき，点 pi とdist(pi , pj ) は点 pi , pj 間のユークリッド距離である．

点 pj は (ε, τ, M inP ts) に関して類似接続するという．

［定義 7］ (ε, τ )-近傍の点が M inP ts 以上ある点 pi をコアポ

例えば，図 3 中の点 p1 , p4 は (ε, 0.3, 2) に関して類似接続すイントという．

るが，(ε, 0.5, 2) に関しては類似接続しない．
最後に SimDBSCAN では ROI（クラスタ）を以下のように例えば図 3 のように点があるとき，点 p2 から距離 ε 内に存定義する．

在しかつ類似度が 0.3 以上である点は p1 と p3 であるため，点p2 の (ε, 0.3)-近傍は {p1 , p3 } である．一方，類似度が 0.5 以上［定義 11］ ROI r = {p1 , . . . pk } は以下の条件を全て満たすの点は p3 のみであるため，(ε, 0.5)-近傍は {p3 } となる．また，

点の集合である．

(ε, τ, M inSup) = (ε, 0.3, 2) の場合，コアポイントは p2 , p3 でi) r 中の点 pi に (ε, τ, M inP ts) に関して類似接続するあり，(ε, τ, M inSup) = (ε, 0.5, 2) の場合，コアポイントは p3

点 pj は r に属する．

ii) r 中の任意の点の組 pi , pj は (ε, τ, M inP ts) に関してアルゴリズム 1: SimDBSCAN

類似接続する．

Input: D, ε, τ, M inpts

例えば，図 3 のように点があり，(ε, τ, M inSup) = (ε, 0.3, 2)

Output: C// ROI の集合としたときには，全ての点が類似接続するため 1 つの ROI r1 =1C←ϕ{p1 , p2 , p3 , p4 } が得られる．これに対し，(ε, τ, M inSup) =2

foreach p ∈ D do(ε, 0.5, 2) としたとき，p2 がコアポイントでなくなるため，

3

p1 が他の点に類似接続しない．そのため，得られる ROI は
ここで，SimDBSCAN で得られる ROI は類似接続した点の集合であるため，ROI 内の任意の 2 点間の類似度が小さくなる恐れがある．実際，前述の ROI r1 中の 2 点 p1 , p4 の類似度

sim(p1 , p4 ) は 0.1 であり，類似度閾値 τ 未満になってしまう．

// 抽出した ROI 集合

if is visited(p) thencontinue45

r2 = {p2 , p3 , p4 } となる．

// D は軌跡上の全ての点の集合

p を visited とマーキング

6

N eighbors ← rangeQuery(p.loc, ε,τ )7

if sizeOf(N eighbors) < M inP ts thenp をノイズとマーキング

89// (ε, τ )-近傍の点// コアポイントでない

else

10

r←ϕ

このように SimDBSCAN によるクラスタリングは ROI 中の

11

expandCluster(p, N eighbors, p, ε, M inP ts, τ )任意の 2 点間の類似度の大きさを保証しない．この問題につい12

r を C に追加// 新しい ROIては，5. 2 節の実験により検証する．

4. 2. 2 アルゴリズム

アルゴリズム 2: expandCluster

SimDBSCAN のア ルゴリズム をア ルゴリ ズ ム 1 に示 す．

Input: p, N eighbors, r, ε, τ, M inP ts

SimDBSCAN は入力として，軌跡上の全ての点の集合 D 及び，

1

p を ROI r に追加

距離閾値 ε，類似度閾値 τ ，密度閾値 M inP ts を受け取り，ク

2

foreach p′ ∈ N eighbors do

ラスタ（ROI）の集合 C を抽出し出力する．処理の流れは次の3

とおりである．まず，データセット内の各点について順に処理

4

済み（is visited）か確認する．処理済みである場合には処理を

5

行わなず（3–4 行目），次の点を調べる．未処理の場合には，

if ¬is visited(p′ ) thenp′ を visited とマーキング
N eighbors′ ← rangeQuery(p′ .loc, ε,τ )if sizeOf(N eighbors) >= M inP ts then6

N eighbors に N eighbors′ の要素を追加

7

処理済みのマーキングを行い，点がコアポイントであるか確認する．コアポイントでない場合はその点はノイズとなる（6–88行目）．コアポイントである場合は関数 expandCluster（アル9if p′ が未割当の場合 thenp′ を r に追加

ゴリズム 2）により同一の ROI に含まれる点を全て抽出する（10–12 行目）．関数 expandCluster（アルゴリズム 2）は入力

表 2: 地域別のデータ数

として，点 p，点 p の (ε, τ )-近傍 N eighbors，ROI r，距離閾

京都

神奈川

値 ε，類似度閾値 τ ，密度閾値 M inP ts を受け取り，次のよう

点の数

41866

33594

に処理を行う．まず，点 p を ROI r に追加する（1 行目）．次

軌跡数

7533

6283

5.56 ± 9.91

5.35 ± 8.48

1139

797

に N eighbors 内の未処理（¬is visited）の点 p′ を処理済みとし，コアポイントであるか調べる（5–6 行目）．コアポイントである場合は点 p′ の (ε, τ )-近傍である点を N eighbors に追加

軌跡の長さ（mean ± SD）
ユーザ数

ユーザごとの点の数（mean ± SD） 36.8 ± 101.7 42.2 ± 241.5

する（7 行目）．更に，p′ が既に ROI に割り当てられていない
場合に ROI r に追加する（8–9 行目）．この処理を N eigjborsて用いる．まず，Flickr から 2015 年に京都及び神奈川で撮らが空になるまで行う．
各 ROI の特徴を明らかにするため，ROI 内の各点のタグを分析する．まず，ROI ri の各タグ tj のスコア（scoreij ）を以下の式で計算し，値が大きい k 個のタグを ri のトピックとする．
∑ p(4)scoreij =ctjl × idftj
pl ∈ri

5. 実

各写真の被写体を分析して得られた結果をデータセットとし験れた写真を収集した．次に各写真に対し，Clarifai API 及び，

Vision API を用いて分析を行い，被写体を表すタグと確信度を求めた．これにより，4 つのデータセットを得た．各データセットに対し，ユーザごと，撮影日ごとに点を分け，意味的な移動軌跡とした．地域ごとの写真数や軌跡数は表 2 のとおりである．軌跡の最大の長さは京都が 230 個，神奈川が 240 個であり，ユーザごとの点の数の最大数は京都が 1495 個であり，本章では，提案手法によるパターン抽出手法の有効性を確認

神奈川が 6009 個である．また，各データセットのタグと確信するため，実データを用いた実験について紹介する．まず，実度について，タグの種類の総数，1 点当たりのタグ数などは，験に用いたデータについて説明する．その後，抽出した ROI や

表 3 のようになった．Clarifai API と Vision API を比較する

パターンについて述べる．

と Clarifai API の方が各タグの確信度が高く，1 点当たりの平5. 1 実験データ

均タグ数が 20 個と多い．その一方，京都と神奈川で比較する

本稿では，写真から構成される意味的な移動軌跡に対して，と点の数が京都の方が多いにもかかわらず，神奈川の方がタグ

2400

表 3: タグの数と確信度
神奈川（Clarifai）（Clarifai）（Vision）（Vision）

2905

3198

2744

3254

841400673840375609321418

1 点当たりのタグ数

20.0 ± 0.0

20.0 ± 0.0

9.0 ± 5.0

9.5 ± 5.2

確信度（mean ± SD）

0.92 ± 0.06

0.93 ± 0.06 0.72 ± 0.13 0.73 ± 0.13

神奈川（Vision）
1600

𝑦 = 6.0 × 107 𝑥 −2.202

10

104
103

点の数

105

𝑦 = 41866

105

0.0

0.4

0

0.5

0.0

0.1

0.2

𝜏

0.3

0.4

0.5

（b） 最低類似度の平均

図 5: 類似度閾値 τ の影響
0.6

900

700
京都（Clarifai）
京都（Vision）
神奈川（Clarifai）
神奈川（Vision）

500
100

タグ

（a） 京都（Clarifai）

0.3

[個]

ROIの数

100

103

𝜏

0.5

100

102

0.2

103

101
101

0.1

（a） ROI の数

104

101
100

神奈川（Vision）

0.2
0.1

800

𝑦 = 33594

102

102

神奈川（Clarifai）
0.3

1200

𝑦 = 7.0 × 106 𝑥 −1.925

106

6

京都（Vision）

0.4

神奈川（Clarifai）

107

107

点の数

2000

最低類似度

京都

ROIの数

神奈川

108

京都（Clarifai）

京都（Vision）

101

102

103

タグ

（b） 神奈川（Vision）

図 4: タグごとの保持する点の数

300
2.5

5.0

7.5

10.0 [m]

最低類似度

タグの総数

0.5

京都（Clarifai）

京都
タグの種類数

[個]

0.4
0.3

京都（Clarifai）
京都（Vision）
神奈川（Clarifai）
神奈川（Vision）

0.2
0.1

0
2.5

5.0

7.5

10.0

[m]

𝜀

𝜀

（a） ROI の数（b） 最低類似度の平均

図 6: 距離閾値 ε の影響の種類数が多く，多様な点を含んでいるといえる．
次に，4. 1 節で予想したタグごとの保持される点の数につい影響がないことがわかる．以上のことから 4. 2. 1 項で述べた，て確認を行った結果，各タグとそのタグを保持する点の数の関

SimDBSCAN の ROI 内の任意の 2 点間の最小類似度が小さく係は図 4 のようになった．図 4 の y 軸は各タグを保持する点なる恐れについて，実データセット上では問題ないといえる．

の数を表し，x 軸は保持する点の数で降順に並べたタグの ID

5. 2. 2 ROI の例

を表す両対数グラフである．青い点は実際の点の数を，青い点

パラメータを (ε, M inP ts) = (10, 3) に設定し，類似度閾値

線はデータを対数変換して直線近似した関数，橙の線はデータ

τ を 0, 0.3, 0.5 と変化させたときの実行結果の変化を観察する．

セットの写真数を表す．図 4 から確かに 4. 1 節で予想したよう

図 7 は，神奈川（Vision）に提案手法を用いたときに長谷寺に，多くの点が共通して保持するタグと，一部の点のみが保持付近で得られた ROI の分布を表し，表 4 は図 7 内のいくつかするタグが存在することがわかる．この傾向は京都（Vision）の ROI のトピックである．図 7 の各図内の色付きの多角形はや神奈川（Clarifai）でもみられた．

ROI の凸包を表しており，一部の ROI は重なって存在する．

5. 2 ROI の抽出結果
4. で提案した ROI の抽出方法の評価を行うため，各データ

類似度を考慮せずに ROI の抽出を行った図 7（a）中では，

ROI r1 のように非常に大きな ROI が長谷寺を覆っている．そセットに対し，SimDBSCAN による ROI の抽出を行った．この一方，類似度を考慮して ROI の抽出を行った図 7（b）では，のとき，パラメータの変化により，抽出できる ROI の数など

r1 がいくつかの ROI にその被写体ごとに分かれている．例えの変化を観察した．また，実際に抽出した ROI の例を示す．

ば，ROI r2 に含まれる写真の多くは紫陽花を写したものであ

5. 2. 1 パラメータの影響

り，ROI r3 に含まれる写真の多くは観音堂を写したものであ距離閾値 ε を 10 m に固定し，類似度閾値 τ の値を変化させる．しかし，r2 は石造釈迦如来坐像の写真など紫陽花以外の写たときに抽出できる ROI の数の変化を計測した．また 4. 2. 1 項

真を含んでいる．これに対し，より厳しい条件で類似度を考慮で述べた，SimDBSCAN が ROI 中の 2 点間の類似度の大きさ

している図 7（c）では，ROI r4 に含まれる写真は紫陽花の写を保証しない問題について検証するため，各 ROI 中に含まれ真のみであるなど，より正確に被写体別に分かれた ROI を得る点間の最低類似度の平均の変化を計測した．同様に，類似度られる．また，ROI r5 では紫陽花が撮影され，ROI r6 では電閾値 τ を 0.5 に固定し，距離閾値 ε を変化させ，計測を行った．

車が撮影されていた．これらの領域は有名なスポットではない

図 5 から全てのデータセットで，類似度閾値 τ が大きくなる

ため，未知の ROI といえる．以上のように，長谷寺などの有につれ，抽出できる ROI の数が減り，最低類似度の平均が上名な既知の ROI 内では，より細かな ROI が発見できること，

昇することが観察された．これは類似度閾値 τ が大きくなるこ

r5 や r6 のような未知の ROI を発見できることが確認できた．

とにより，直接類似到達可能な点が少なくなり，より精練され5. 3 パターンの抽出結果

た ROI のみが抽出されるためである．

まず，SimDBSCAN のパラメータにより，得られるパター

一方，図 6 では距離閾値 ε が大きくなるにつれ，抽出できる

ROI の数が増加している．これは距離閾値 ε が大きくなるこ

ン数などの変化を観察する．その後，各分析ツールによって得られたパターンの違いを観察する．

とにより，直接類似到達可能な点が多くなるためである．一方

5. 3. 1 パラメータの影響で，最低類似度の平均は京都ではゆるやかに減少しており，神距離閾値 ε を 10 m に固定し，類似度閾値 τ の値を変化させ

奈川ではほぼ横ばいである．そのため，距離閾値 ε を大きくし，たときに得られるパターンの数とその長さを計測した．ただし，ROI に多くの点が含まれるようにしても，最低類似度には殆ど

1 人のユーザの軌跡のみが要因となるパターンは，複数のユー

𝑟2

𝑟1

𝑟4

𝑟3
𝑟6
𝑟5
地図データ ©2017 Google, ZENRIN

地図データ ©2017 Google, ZENRIN

地図データ ©2017 Google, ZENRIN（a） τ = 0（b） τ = 0.3（c） τ = 0.5

図 7: 長谷寺付近の ROI の分布
表 4: 図 7 中の ROI のトピック
ROI

トピック

score

flower

398.8

r1

plant

r2

16.0
15.9
9.7

botany354.1

garden45.4

hydrangea

botany38.5

flower

36.6
26.8

temple23.5

historic site

20.6

18.6

natureland plantchinesearchitecturer3

hydrangea
r4

361.9

𝑟7

トピック score

ROI

𝑟8
地図データ ©2017 Google, ZENRIN

r5

hydrangeaceae

8.9

flora

6.8

tram

19.2

land vehicle

17.7

electricity

13.5

r6

𝑟7

𝑟8

表 5: 閾値のパターン数への影響（a） 類似度閾値 τ
類似度

図 8: 京都（Vision）のパターン例（b） 距離閾値 ε
距離パターンの長さ

6

閾値 ε

2

3

4

妥当な ROI である．京都（Vision）では伏見稲荷大社付近に0.01056 323 83 15 2

2.5

2

0

0

別のパターンを複数発見することができたが，京都（Clarifai）

0.1

324

81

11

0

0

5.0

32

0

0

では 1 つのパターンしか発見できなかった．

0.2

345

96

19

1

0

7.5

139 20

1

0.3

191

35

4

0

0

10.0

191 35

4

0.4

102

25

4

0

0

0.5

34

3

0

0

0

閾値 τ

パターンの長さ

2

3

4

5

一方，図 9 は京都（Clarifai）でのみ得られたパターン例（ROI r10 は円中の小さな三角形）であり，二条城内を移動するパターンである．パターン中の各 ROI の top-3 のトピック
は表 7 のとおりである．このパターン中の ROI は各々異なる

ザの軌跡が要因となるパターンより，価値が低いと考えられるため除外した．同様に，類似度閾値 τ を 0.3 に固定し，距離閾値 ε を変化させたときについても計測を行った．
表 5（a），（b）は京都（Vision）から得られたパターン数とその長さを表す．これらの表から得られるパターン数は類似度
閾値 τ が大きいほど少なく，距離閾値 ε が大きいほど多くなり，その影響を大きく受けることがわかる．この傾向は他のデータセットにおいてもみられた．これは閾値が変化することにより，抽出できる ROI 数が変化することに起因する．

5. 3. 2 分析ツールの違い
パラメータを (M inP ts, ε, τ, M inSup) = (3, 10, 0.5, 3) に設定し，京都（Clarifai），京都（Vision）に対して提案手法を実行した際に得られるパターンの違いを観察した．
図 8 は京都（Vision）でのみ得られたパターン例である．パ
ターン中の各 ROI の top-3 のトピックは表 6 のとおりである．

ROI r7 は JR の奈良線の電車や稲荷駅が撮影されている ROIである．一方，ROI r8 は比較的広範囲の ROI となっているが，ROI 中の写真は全て伏見稲荷大社の楼門や本殿を撮影しており，

ROI と領域が重なっている．ここで，r10 の撮影対象が二の丸′御殿であるのに対し，r10の撮影対象は二の丸庭園であり，そ′の撮影対象は大きく異なっている．また，ROI r11 と ROI r11′についても同様に r11 が建物，r11
が庭園と撮影対象が大きく異なっている．以上のことから，このパターンを持つユーザは，
特に建築物に興味を持ったことが示唆される．各 ROI のトピッ
クもそれを指し示す．京都（Clarifai）では二条城内に別のパターンを複数発見することができたが，京都（Vision）では 1
つのパターンしか発見できなかった．
このように分析ツールによって，発見できるパターンが変化することがわかった．これはツールによって，識別できる被写体の得手不得手があり，求められるタグが変化し，タグ間の類似度がその影響を受けるためと考えられる．また，京都（Clarifai）から得られるパターンのように，ユーザの嗜好を推定できるパターンが存在することがわかった．

6. ま と め
本稿では，重み付きタグ集合を持つ意味的な移動軌跡からのび文部科学省「実社会ビッグデータ利活用のためのデータ統合・

表 6: 図 8 中の ROI のトピック
rail transport

32.2

train

30.9

r7

track

28.5

chinese architecture

247.9

shinto shrine

179.2

temple

166.4

r8

′
𝑟11

解析技術の研究開発」による.

トピック score

ROI

文
[1]
[2]
[3]
[4]
[5]
[6]

′
𝑟10

𝑟11

[7]

𝑟10
𝑟9
𝑟9′

[8]

地図データ ©2017 Google, ZENRIN

𝑝9

[9]

𝑝10

[10]
[11]

𝑝11

[12]

図 9: 京都（Clarifai）のパターン例
表 7: 図 9 中の ROI のトピック
ROI
r9

r10

r11

トピック

score

castle45.1

marquee43.8

templeeaves
expression[13]

ROI トピック score
castle117.5

ancient

111.4

43.4

temple

108.9

20.4

pool

71.5

stone

61.6

12.6

r9′

′
r10

construction

12.6

lake

60.7

roof

42.5

lake

25.0

mountain

40.0

river

23.9

home

36.2

bridge

19.0

′
r11

[14]

[15]
[16]

[17]

意味的な軌跡パターンの抽出手法を提案した．まず，同様の点が多く存在する ROI を明らかにするため，タグ集合間の類似[18]

度を定義し，類似度と密度に基づくクラスタリング手法を提案
した．提案手法の有効性を確認するために，写真の分析結果を[19]用いた評価実験では，提案手法により，被写体別に ROI を分類できることを確認した．更に得られたパターンは，ユーザの嗜好を示唆する場合があることを確認できた．
本研究ではデータセットに対して，一律のパラメータで分析[20]を行った．しかし，現実には都市部と郊外など，多くの点が存在する地点とそうでない地点が存在する．このばらつきを考慮[21]

した適応的なクラスタリング手法については今後の課題としたい．また他の課題として，より大規模なデータセットや，異なる性質を持つデータセットに対する評価実験が挙げられる．
謝辞

本研究の一部は，科研費（16H01722，26540043）及

[22]

献

Clarifai API. https://www.clarifai.com/api.
Flickr. https://www.flickr.com/.
Google cloud vision api. https://cloud.google.com/vision/.
Swarm. https://www.swarmapp.com/.
Twitter. https://twitter.com/.
L. O. Alvares, V. Bogorny, B. Kuijpers, B. Moelans, J. A.
Fern, E. Macedo, and A. T. Palma. Towards semantic trajectory knowledge discovery. Data Mining and Knowledge
Discovery, 2007.
D. Comaniciu and P. Meer. Mean shift: A robust approach toward feature space analysis. IEEE Transactions
on Pattern Analysis and Machine Intelligence, 24(5):603–
619, 2002.
T. L. C. da Silva, K. Zeitouni, J. A. de Macêdo, and M. A.
Casanova. A framework for online mobility pattern discovery from trajectory data streams. In International Conference on Mobile Data Management (MDM 2016), volume 1,
pages 365–368, 2016.
M. Ester, H.-P. Kriegel, J. Sander, and X. Xu. A densitybased algorithm for discovering clusters in large spatial
databases with noise. In KDD, pages 226–231, 1996.
F. Giannotti, M. Nanni, F. Pinelli, and D. Pedreschi. Trajectory pattern mining. In KDD, pages 330–339, 2007.
J. Han, J. Pei, B. Mortazavi-Asl, H. Pinto, Q. Chen,
U. Dayal, and M. Hsu. Prefixspan: Mining sequential
patterns eﬃciently by prefix-projected pattern growth. In
ICDE, pages 215–224, 2001.
C.-C. Hung, W.-C. Peng, and W.-C. Lee. Clustering andaggregating clues of trajectories for mining trajectory patterns and routes. The VLDB Journal, 24(2):169–192, 2015.
H. Jeung, M. L. Yiu, X. Zhou, C. S. Jensen, and H. T. Shen.
Discovery of convoys in trajectory databases. Proceedingsof the VLDB Endowment, 1(1):1068–1080, 2008.
R. Jiang, J. Zhao, T. Dong, Y. Ishikawa, C. Xiao, and
Y. Sasaki. A density-based approach for mining movement
patterns from semantic trajectories. In TENCON 20152015 IEEE Region 10 Conference, pages 1–6. IEEE, 2015.
Y. Kim, J. Han, and C. Yuan. Toptrac: Topical trajectory
pattern mining. In KDD, pages 587–596, 2015.
P. Laube and S. Imfeld. Analyzing relative motion withingroups oftrackable moving point objects. In International
Conference on Geographic Information Science, pages 132–
144. Springer, 2002.
Z. Li, B. Ding, J. Han, and R. Kays. Swarm: Mining relaxed temporal moving object clusters. Proceedings of the
VLDB Endowment, 3(1-2):723–734, 2010.
C. D. Manning, P. Raghavan, H. Schütze, et al. Introduction
to Information Retrieval, volume 1. Cambridge university
press Cambridge, 2008.
C. Parent, S. Spaccapietra, C. Renso, G. Andrienko, N. Andrienko, V. Bogorny, M. L. Damiani, A. Gkoulalas-Divanis,J. Macedo, N. Pelekis, Y. Theodoridis, and Z. Yan. Semantic trajectories modeling and analysis. ACM Computing
Surveys, 45(4), 2013.
J. J.-C. Ying, W.-C. Lee, T.-C. Weng, and V. S. Tseng. Semantic trajectory mining for location prediction. In ACM
SIGSPATIAL GIS, pages 34–43, 2011.
C. Zhang, J. Han, L. Shou, J. Lu, and T. La Porta. Splitter:
Mining fine-grained sequential patterns in semantic trajectories. PVLDB, 7(9):769–780, 2014.
K. Zheng, Y. Zheng, N. J. Yuan, and S. Shang. On discovery of gathering patterns from trajectories. In ICDE, pages
242–253, 2013.