DEIM Forum 2016 H1-2

時間帯を考慮したパーソナライズ目的地予測
瀧本

祥章†

西田

京介††

遠藤 結城††

戸田

浩之††

澤田

宏††

石川 佳治†† 名古屋大学大学院情報科学研究科 〒 464–8601 愛知県名古屋市千種区不老町†† 日本電信電話株式会社 NTT サービスエボリューション研究所 〒 239–0847 神奈川県横須賀市光の丘 1-1
E-mail: † takimoto@db.ss.is.nagoya-u.ac.jp, ishikawa@is.nagoya-u.ac.jp†† {nishida.kyosuke,endo.yuki,toda.hiroyuki,sawada.hiroshi}@lab.ntt.co.jp
あらまし

近年，スマートフォンなどの GPS 機能がついたモバイルデバイスの普及により，パーソナルアシスタント

サービスなど，個人の移動軌跡を利活用した新たなサービスの需要が高まっている．本研究では，ユーザの移動軌跡
集合から学習を行った後，出発地から現在地までの移動軌跡を入力として，そのユーザの目的地を予測する手法の提案をする．最新の目的地予測手法である SubSyn アルゴリズムをベースにパーソナライズした予測を行うため，デー
タスパースネス問題の解決と，予測時間帯を考慮した確率モデルの導入を実施した．25 人の被験者の実際の移動軌跡を用いた実験を行い，提案手法がベースラインに比べて高精度に目的地を予測できたことを示す．
キーワード

時空間データマイニング，軌跡マイニング，目的地予測，移動軌跡

1. は じ め にの向上を図るため，軌跡に付加されているタイムスタンプを利用して時間帯を考慮する目的地予測を提案し，SubSyn アルゴ

近年，スマートフォンなどの GPS 機能がついたモバイルデバ

リズムとの併用を行う．最後に，25 人の被験者の実際の移動軌

イスやカーナビゲーションシステムの普及により，個人の移動跡を用いた評価実験を行い，提案手法が従来の SubSyn アルゴ

軌跡を容易に収集できるようになった．それに伴い，パーソナリズムよりも高精度なパーソナライズ目的地予測ができること

ルアシスタントサービスなど，収集した移動軌跡を利活用したを示す．

新たなサービスの需要が高まっている．例えば，ユーザの現在

本稿の主な貢献は以下の通りである．

の移動軌跡から目的地を予測し，目的地周辺のレストランや娯•楽施設など POI (Point Of Interest) のレコメンドを行うサー

データスパースネス問題を考慮したパーソナライズ目的

地予測の提案

ビスが想定される．このサービスを行うには，高精度な目的地•

時間帯を考慮したパーソナライズ目的地予測の提案

予測技術が必要であり，様々な手法が提案されている [2–17]．

•予測モデルの併用によるパーソナライズ目的地予測の精

しかし，既存手法にはいくつかの共通の課題がある．例えば，度向上収集した移動軌跡のデータ量が不十分な場合に，予測可能な•問合せ（出発地から現在地までの移動軌跡）や目的地が制限さ

本稿の構成は以下の通りである．まず，2. で関連研究としれるといったデータスパースネス問題である．最新の目的地予て，目的地予測に関する研究を紹介する．次に 3. で本研究に測技術である SubSyn アルゴリズム [15, 16] は収集した移動軌

おける基本的な概念の定義や問題設定を行う．4. で拡張を行う

跡を部分軌跡に分割して合成することにより，問合せや目的地

SubSyn アルゴリズム [15, 16] を紹介し，5. で提案手法の詳細の制限を緩和し，データスパースネス問題に対応した．だが，を述べる．6. で提案手法を評価するために行った実験についてパーソナライズについては述べられていない．パーソナライズ

述べる．最後に，7. で本稿のまとめと今後の課題について述した目的地予測では，単一のユーザの軌跡を用いて処理を行う

べる．

ため，収集できる移動軌跡のデータ量が非常に少なくなる傾向がある．この場合，SubSyn アルゴリズムによるデータスパー

評価実験による提案手法の有効性の確認

2. 関 連 研 究

スネス問題への対策は不十分であり，予測可能な問合せや目的

本章では，目的地予測の関連研究を紹介する．目的地予測に地が制限されてしまう．また，SubSyn アルゴリズムは移動軌

おける先行研究は多数存在するが，目的地予測をパーソナライ

跡に付加されているタイムスタンプを考慮していないため，収ズする研究と外部情報を追加することにより予測精度向上を図集した移動軌跡を十分に活用できていない．

る研究の２つの方向性がある．順にこれらの先行研究について

そこで本稿では，単一のユーザの軌跡からデータスパース
ネス問題を考慮して目的地予測を行う手法を提案する．まず，述べ，本研究との相違点について述べる．その後，本研究で拡張する SubSyn アルゴリズムについて簡単に述べる．

SubSyn アルゴリズムのデータスパースネス問題を，学習デー

2. 1 パーソナライズされた目的地予測

タに仮想的な軌跡を追加することにより解決する．次に，精度パーソナライズされた目的地予測では，個々のユーザの軌跡

を用いて，各ユーザに合わせた予測を行う．例えば，Marmasse
らは現在地までの軌跡と部分一致する軌跡をユーザ自身の過去の軌跡から抽出して予測を行っている [10]．Tiesyte らは軌跡間の距離を定義することにより，現在地までの軌跡と部分一致する軌跡ではなく，最近傍の軌跡を抽出して予測を行ってSubSyn アルゴリズムの詳細は 4. で述べる．

3. 問 題 設 定
本章では，本研究における基本的な概念の定義や問題設定を行う．また，本稿で用いる記号の一覧を表 1 に示す.

いる [14]．また，Patterson らは教師なし学習により交通手段
表 1: 本稿で用いる記号一覧（e.g., バス，車）を推定し，交通手段特有の制限（e.g., バス停，道路情報）や移動距離を考慮することにより予測を行ってい記号

意味る [11]．Ashbrook らは過去に訪れた地点を抽出し，地点間のli , ls , lc , ld

観測地，出発地，現在地，目的地

移動確率を考慮して目的地予測を行っている [3]．他にも，道lat, lon, t

緯度，経度，時刻

路情報を用いる研究 [9, 13] や携帯電話の基地局を利用する研

ni (, ns , nc , nd )（出発地，現在地，目的地）セル

究 [12]，軌跡データの欠損を考慮する研究 [4]，軌跡から POI

m

セルの数

を抽出し，曜日や時刻に依存するユーザの習慣を利用する研D軌跡データセット究 [2] など多数の先行研究がある．

To

観測軌跡

これらの研究では単一のユーザの軌跡を用いて目的地予測を

T

離散化軌跡

行う．しかし，単一のユーザの軌跡を用いて予測を行う場合にTi

セル ni を通過する軌跡

は，利用できる軌跡が少ないため，予測可能な入力軌跡や目的

Ti,j

セル ni , nj を連続して通過する軌跡

地が極端に少なくなるといったデータスパースネス問題が生じ

Tstart=ns

出発地セルが ns の軌跡

る．本研究はデータスパースネス問題を考慮して目的地予測を

Tdest=nd

目的地セルが nd の軌跡行うという点でこれらの先行研究と異なる．

Tstart=ns ,dest=nd

出発地セルが ns ，目的地セルが nd の軌跡

Top , T p

問合せ観測軌跡，問合せ軌跡

pi,j

セル ni からセル nj への遷移確率

pi→j

セル ni からセル nj への総遷移確率

M, M T

遷移行列，総遷移行列

k

出力数

L

セル間のマンハッタン距離wi

i 番目の予測モデルの重みH

時間帯

2. 2 外部情報の追加
軌跡情報だけでなく，外部情報を追加して利用することにより，予測精度の向上を図った先行研究を紹介する．Horvitz ら
は現在地から 1 時間以内で行ける交差点を交差点の位置情報と軌跡情報から抽出して目的地候補とし，ユーザの移動による到達可能時間の変化を用いて予測目的地を決定する [6]．また，Krumm らは場所の特性（e.g., 商店街，海）に関する情報や人々の移動時間の分布を用いて予測を行う [7, 8]．他にも，事故や工事，イベント，天気といったリアルタイムの情報や道路情報を用いる研究 [5, 17] など多数の先行研究がある．
これらの研究では多数のユーザの軌跡や外部情報が得られる
ことを前提としている．しかし，多数のユーザの軌跡や上記のような外部情報は常に得られるとは限らない．本研究は単一の

3. 1 基本的な概念
本研究では Geohash [1] などのグリッドによって，セルに分割された空間上で目的地予測を行う．
まず，目的地予測に用いる観測軌跡と離散化軌跡を以下のよ

ユーザの軌跡から外部情報を用いずに，目的地予測を行うというに定義する．

う点でこれらの先行研究と異なる．

［定義 1］ 観測軌跡 To = {ls , . . . , ld } は移動物体の位置をある

2. 3 SubSyn アルゴリズム

一定の時間間隔で観測した点の系列である．観測軌跡中の各点

SubSyn アルゴリズムは Xue らが [16] で提案し，[15] で改良

li は緯度 lat，経度 lon，タイムスタンプ t を持つ．各観測軌跡を行った外部情報を必要としないアルゴリズムである．SubSynの長さ |To | は観測軌跡ごとに異なっていても良いものとする．

アルゴリズムでは多数のユーザから得た軌跡を部分軌跡に分［定義 2］ 離散化軌跡 T = {ns , . . . , nd } は観測軌跡 To の各点解し，合成して目的地予測に用いる．これにより，目的地予測を，その点が属するセルに置き換えたものである．ただし，同において問題となるデータスパースネス問題に対処している．

一セルが連続する場合には，2 番目以降のセルを削除し，同一

また，オフラインで行う学習フェーズとオンラインで行う予測

セルが連続しないようにする．また，離散化した軌跡内で連続フェーズの２つのフェーズを持つように構築されており非常にするセル ni , nj において，セル nj はセル ni の東西南北のいず

効率的である．

れかの方向に位置する４近傍となる．連続したセルが近傍とな

SubSyn アルゴリズムはデータスパースネス問題に対処してらない場合には，観測軌跡を線形的に補間をすることによりセいるが，今回のように単一ユーザの軌跡のみを用いた予測を行ルを補う．本稿では以降，あるセルが他のセルの４近傍に位置う場合など，データ量が非常に少ない場合にはその取組みは不することを隣接すると呼ぶ．

十分である．本研究では SubSyn アルゴリズムの学習データへ

例えば，図 1 のように観測軌跡 To が得られたとき，離散化軌の仮想軌跡の追加や時間帯を考慮した予測モデルの併用によ

跡 T は {n7 , n4 , n5 , n2 , n3 } となる．本稿では以降離散化軌跡

り，パーソナライズされた目的地予測の精度向上を実現する．

を単に軌跡と呼ぶ．

pi,j = P (nj |ni ) =|Ti,j ||Ti |(1)

［定義 6］ 遷移行列 M は各隣接セル間の遷移確率を表す m×mの二次元行列である．M の一方の次元は現在のセルを表し，他方は遷移後のセルを表す．即ち，M の要素 Mi,j は pi,j である．
例えば，図 1 の遷移行列 M は以下のようになる．
観測軌跡
観測軌跡の線形補間
離散化軌跡

図 1: 観測軌跡と離散化した軌跡の例

次に，目的地を予測する領域を以下のように定義する．
［定義 3］ 予測対象領域 {n1 , n2 , . . . nm } は予測目的地として出力しうるセルの集合である．本研究では，ユーザの過去の軌



0

p2,1


 0


p4,1

M =
 0

 0


 0

 0

0

p1,2

0

p1,4

0

0

0

0

0

p2,3

0

p2,5

0

0

0

p3,2

0

0

0

p3,6

0

0

0

0

0

p4,5

0

p4,7

0

p5,2

0

p5,4

0

p5,6

0

p5,8

0

p6,3

0

p6,5

0

0

0

0

0

p7,4

0

0

0

p7,8

0

0

0

p8,5

0

p8,7

0

0

0

0

0

p9,6

0

p9,8

0




0 


0 


0 

0 


p6,9 

0 

p8,9 

0(2)

跡に対する最小外接矩形と重なるセルとする．ここで，最小外

M は１回の遷移でセル間を移動する確率を表し，r 乗すること

接矩形は観測軌跡中の全ての点を内側または境界線上に含む最により，r 回の遷移で移動できる確率を表せる．

小の矩形を表す．
また，特定のセルを通過する軌跡を以下のように表す．

次に実際の移動で生じる迂回を考慮して，セル間を複数回の遷移で移動する確率を定義する．

［定義 4］ セルを通過する軌跡 Ti はセル ni を通過する軌跡で［定義 7］ 総遷移確率 pi→j は L 回から ⌈1.2L⌉ 回の遷移でセあり，Ti,j はセル ni , nj を連続して通過する軌跡である．例えル ni から任意のセル nj に移動する確率である．ただし，L はば，図 1 の離散化軌跡 T = {n7 , n4 , n5 , n2 , n3 } は T4,5 である

隣接セル間の距離を 1 としたときの，セル ni とセル nj の間のが，T4,2 ではない．また，出発地が ns である軌跡を Tstart=nsと表し，目的地が nd である軌跡を Tdest=nd と表す．加えて，出発地が ns であり，目的地が nd である軌跡を Tstart=ns ,dest=nd

マンハッタン距離である．また，1.2 は２点間を実際に移動する際に考慮する迂回路の最大の長さを表す定数である．定式化
すると以下のようになる．
⌈1.2L⌉と表す．

pi→j =

3. 2 問 題 設 定
本研究では，ユーザの出発地 ls から現在地 lc までの移動履歴である問合せ観測軌跡 Top = {ls , . . . , lc } を入力として受け取り，ユーザが目的地としているセルを予測し，その確率が高い

k 個のセル {nd1 , . . . ndk } を出力する．また，学習データとしてユーザ自身の過去の軌跡集合 D を用いる．

4. SubSyn アルゴリズムによる目的地予測
本章では，本研究で拡張する SubSyn アルゴリズム [15, 16]を紹介する．まず，[16] における SubSyn アルゴリズムの目的地予測確率について述べる．次に，[15] による SubSyn アルゴ
リズムの拡張について述べ，最後に，パーソナライズすることで生じる問題について述べる．なお，SubSyn アルゴリズムは

3. 2 節で説明した問題設定に従うが，学習データは単一のユー
ザに限定されるものでなく，多数のユーザから得られた軌跡集合にも適用可能である．

4. 1 目的地予測確率
SubSyn アルゴリズムはグリッドの各セルをマルコフモデル
における状態とみなし，目的地予測を行う．以下に目的地を予［定義 5］ 隣接セル間の遷移確率 pi,j はセル ni を通過する軌跡のうち，セル ni の直後にセル nj を通過する軌跡の割合である．定式化すると以下のようになる．

r
Mi,j

(3)

r=L

例えば，図 1 で p7→3 は L = 4,

⌈1.2 × 4⌉ = 5 となるため，

4
5
p7→3 = M7,3
+ M7,3となる．

［定義 8］ 総遷移確率行列 M T はセル間の総遷移確率を表す

m × m の二次元行列である．M T の一方の次元は現在のセルをT表し，他方は移動後のセルを表す．即ち，M T の要素 Mi,j
は

pi→j である．
例えば，図 1 の総遷移行列 M T は以下のようになる．


0

p2→1


p3→1


p4→1

T
M =
p5→1

p6→1


p7→1

p8→1

p9→1

p1→2

p1→3

p1→4

p1→5

p1→6

p1→7

p1→8

0

p2→3

p2→4

p2→5

p2→6

p2→7

p2→8

p3→2

0

p3→4

p3→5

p3→6

p3→7

p3→8

p4→2

p4→3

0

p4→5

p4→6

p4→7

p4→8

p5→2

p5→3

p5→4

0

p5→6

p5→7

p5→8

p6→2

p6→3

p6→4

p6→5

0

p6→7

p6→8

p7→2

p7→3

p7→4

p7→5

p7→6

0

p7→8

p8→2

p8→3

p8→4

p8→5

p8→6

p8→7

0

p9→2

p9→3

p9→4

p9→5

p9→6

p9→7

p9→8

p1→9




p2→9 

p3→9 

p4→9 

p5→9 

p6→9 

p7→9 

p8→9 

0(4)

最後に各々のセルが目的地である確率を定義する．
［定義 9］ 目的地予測確率 Pa (nd |T p ) は問合せ軌跡が T p のとき，nd が目的地のセルである確率であり，以下の式のように定義される．

Pa (nd |T p ) =測するために必要な定義を順に述べる．まず，隣接するセル間の遷移確率を以下のように定義する．

∑

pc→d· P (nd )
ps→d

(5)

ここで，P (nd ) は学習データセット内の軌跡のうち，目的地のセルが nd である軌跡の割合であり，以下の式のように定義される．

P (nd ) =|Tdest=nd |
|D|

(6)

4. 2

[15] における SubSyn アルゴリズムの拡張

Xue らは [15] において，目的地予測確率の求め方を変更している．また，改善したアルゴリズムとして SubSynE アルゴ
リズムと SubSynEA アルゴリズムを提案している．これらに

5. 提 案 手 法
本章では，提案手法の基本的なアイデアを 5. 1 節で述べ，具体的な手法を 5. 2 節，5. 3 節で述べる．

ついて順に述べる．

5. 1 基本アイデア

予測確率の求め方の変更提案手法では SubSyn アルゴリズムを単一のユーザの軌跡に[16] では目的地予測確率を式 5 によって求めたが，目的地予測

適用し，パーソナライズを行うが，以下の２つのアイデアに基確率はその大小がわかれば正確な値は必要ない．そのため，[15]づいて予測精度の向上を図る．

では以下の式を用いて目的地予測を行う．

仮想軌跡の追加Pb (nd |T p ) ∝前述のように，SubSyn アルゴリズムを単純に単一のユーザのpc→d· P (nd |ns )
ps→d

(7)

なお，P (nd |ns ) はセル ns を出発地とする軌跡のうち，セル

nd を目的地とする軌跡の割合であり，以下の式のように定義される．

P (nd |ns ) =|Tstart=ns ,dest=nd ||Tstart=ns |(8)

この変更によって，出発地と目的地の関係を考慮した目的地軌跡に適用すると収集できる学習データの量が少ないため，予測可能な問合せや目的地が制限されるデータスパースネス問題が生じる．そこで，ユーザ自身の軌跡に仮想的な軌跡を加えて，学習データを補うことにより，4. 3 節の問題を解決する．
予測モデルの併用
パーソナライズされた目的地予測の精度を向上するために，互いに独立な複数の予測モデルを組み合わせる．各々の予測モデ予測が可能となる．

ルが互いに独立に予測を行うため，外部情報の追加や異なる要

SubSynE アルゴリズム

素の考慮がしやすいといった利点がある．本研究では，軌跡にSubSyn アルゴリズムは遷移行列 M の乗算を繰り返し行う必要があり，時間計算量が O(m3.5) となるという欠点があった．

しかし，SubSynE アルゴリズムでは，遷移行列 M が非常にス
パースであることに着目し，時間計算量を O(m2.5) まで削減することに成功し, 効率良く目的地予測を行うことができる．

SubSynEA アルゴリズム

付加されているタイムスタンプから，時間帯を考慮して予測を行う時間モデルを提案する．

5. 2 仮想軌跡の追加
4. 3 節で述べた問題を解決するため，学習データに仮想的な軌跡を追加することにより，P (nd ) と M T の平滑化を行う．
まず，P (nd ) は式 6 に示すように学習データ内の軌跡がセル

SubSyn アルゴリズムでは，一次マルコフモデルを利用して目

nd を目的地としている割合を示す．この値が 0 のとき，式 5

的地の予測を行っている．これに対し，SubSynEA アルゴリズ

より目的地予測確率が 0 となり，セル nd を目的地として予測

ムでは二次マルコフモデルを利用して目的地の予測を行う．そできない．そこで，D に含まれる軌跡において目的地となる頻のため，より精度を向上させた目的地予測が可能となるが，学度がゼロのセル nd についても確率値が割り当てられるように習に必要となるデータが多くなるといった欠点も存在する．具

仮想軌跡を追加し，P (nd ) > 0 とする．式で表すと以下のよう

体的には，SubSyn アルゴリズムが各セル（i.e., ni ）を状態とになる．

して一次マルコフモデルを用いているのに対し，SubSynEA ア
ルゴリズムでは隣接セル間の遷移（i.e., {ni , nj }）を一次マル
コフモデルの状態として扱うことにより，各セル（i.e., ni ）をP (nd ) =|Tdest=nd | + 1|D| + m(9)

次に，M T がスパースであるとき，式 5 の ps→d ，pc→d の値状態とする二次マルコフモデルに拡張する．

が 0 になりやすいため，目的地予測確率は定義されない．もし4. 3 データ不足により生じる問題点

くは値が 0 となる．そのため，セル nd を目的地として予測でSubSyn アルゴリズムはデータスパースネス問題に対処しているが，単一ユーザの軌跡のみを用いて予測を行う場合など，
学習データが非常に少ない場合に以下のような問題が生じる．

きない．そこで，隣接セル間を遷移する軌跡を仮想的に追加することにより，式 1 の pi,j を以下のように拡張して，M T のス
パース性を緩和する．

pi,j =(a) P (nd ) が 0 となる．
(b) M T がスパースになり，多くの pi→j が 0 となる．
(c) P (nd |ns ) が 0 となる．または定義されない．
これらの問題によって，目的地予測確率 P (nd |T ) の値が 0p|Ti,j | + vi,j|Ti | + vi

(10)

なお，vi,j と vi は仮想的に追加した軌跡において，それぞれセル ni から nj に移動する回数，セル ni から移動する回数である．仮想軌跡の追加方法として，均一追加法，単方向軌跡拡張法，双方向軌跡拡張法の３種類を提案する．これらの軌跡の追になる，あるいは，定義されない．そのため，予測可能な目的

加方法の詳細は以下の通りである．

地セルが，学習データ内に存在する軌跡の目的地に制限されて

均一追加法

しまう．

全ての問合せと目的地に対しての予測を可能にするため，予測対象領域内の全ての隣接セル間の軌跡を追加する．このとき，
予測対象領域の端の影響を無視すると，任意の i, j について

vi,j = 1，vi = 4 である．
単方向軌跡拡張法
学習データの軌跡が通過するセルから隣接するセルへの単方向の軌跡を追加する．この仮想軌跡の追加方法は，ユーザは訪れたことがあるセルの周囲のセルにも移動しやすいという考えに基づいている．
双方向軌跡拡張法
学習データの軌跡が通過するセルとそれに隣接するセル間に双(a) 学習データ(b) 均一追加法(c) 単方向軌跡拡張法(d) 双方向軌跡拡張法

方向の軌跡を追加する．この仮想軌跡の追加方法は，実際に訪れたことの無いセルから訪れたことのあるセルへの遷移を追加するため，単方向軌跡拡張法より強い平滑化を実施することになる．
例えば，図 2a のように学習データが与えられたとき，均一追加法では図 2b のように領域全体に一様に軌跡が追加される．
対して，単方向軌跡拡張法と双方向軌跡拡張法では，それぞれ
図 2c，図 2d のように学習データの周囲に軌跡が追加される．

図 2: 仮想軌跡の追加例

5. 3 予測モデルの併用
予測精度を向上させるため，互いに独立な複数の予測モデル

図 2a の学習データ（i.e., 橙の矢印）が与えられたとき，各手法は図 2b,を併用する．まず，予測モデルの併用方法について述べる．次

図 2c, 図 2d のように仮想軌跡（i.e., 青の矢印）を追加し，学習データを補う．

に，本研究で導入する時間モデルについて述べる．

5. 3. 1 予測モデルの併用方法
各予測モデルは各々独立して予測対象領域内の各セルの目的

6. 評 価 実 験

地予測確率を求める．その後，セルごとに各予測モデルで求めた目的地予測確率に重みをかけて加算する．そのため，予測モ
デルの数が N 個のときセル nd の目的地予測確率 P (nd |Top ) は
以下のようになる．

P (nd |Top ) =N∑

本章では，提案手法によるパーソナライズ目的地予測の精度向上を確認するため，実データによる評価実験について述べる．
まず，データや実行環境など実験条件について述べる．次に評
価指標について述べる．その後，行った実験について述べる．

wi Pi (nd |Top )(11)

6. 1 実 験 条 件
本研究での実験の条件は以下の通りである．

i=1

なお，wi は i 番目の予測モデル Pi (nd |Top ) に対する重みを表∑N
し，0 <= wi <= 1, i=1 wi = 1 を満たす．特に予測モデルが２

実験環境つの場合に，式 11 は以下の式で表せる．

いて，グリッドは Geohash [1] を用いる．

P (nd |Top ) = wP1 (nd |Top ) + (1 − w)P2 (nd |Top )マシンの CPU は Intel Xeon X7560@2.27GHz で，メモリは 512GB である．また，実装には Python 2.7.10 を用
データセット(12)

25 人のユーザの実際の移動軌跡をタブレット型

PC（Nexus 7 ver.2012）の GPS 及び Wi-Fi により，３秒ごと複数の予測モデルで独立して予測を行うため，複数の要因をに測位し，３週間程度収集したものであり，滞留点により分割考慮しやすい，個々の予測モデルを改善しやすいといった利点

して軌跡とする．そのため，各軌跡の出発地と目的地はユーザがある．

が滞留を行った地点となる．１ユーザ当たりの軌跡の数は平均

5. 3. 2 時間モデルの導入

60 個で，軌跡の平均の長さは 4.7km である．なお，滞留点は一般に，人は決まった時間帯に特定の場所（e.g., 勤務先，自ユーザ自身によるラベリングにより決定した．

宅）にいる傾向がある．そのため，現在時刻から目的地を予測

各ユーザの軌跡のうち，７割を学習データとして用いて，残することが可能である．本研究では，現在地における時刻を平りの３割をテストデータとして用いる．問合せ観測軌跡 Top は日午前，平日午後，休日午前，休日午後の４つの時間帯に分類

テストデータの各軌跡の先頭からセル５つ分とする．ただし，

し，各々の時間帯 H においてユーザがセル nd にいる可能性を

元の軌跡の長さがセル５つ分以下の場合，最終セルは除く．正

目的地予測確率 P (nd |H) とする．そのため，問合せ観測軌跡

解データは各問合せ軌跡の元の軌跡の最終セル nd である．

Top の現在地 lc における時刻 tc が時間帯 H に分類される場合，

6. 2 評 価 指 標

目的地予測確率は以下のようになる．

本研究では，目的地予測の精度を評価するため P dest@k，P (nd |Top ) = P (nd |Top , H) =|lt∈H ∈ nd ||lt∈H |SD dest@k の２つの評価指標を提案する．これらの評価指標の(13)

なお，lt∈H は学習データの時間帯 H における観測点を表し，lt∈H ∈ nd はそのうち，セル nd 内での観測点を表す．

詳細は以下の通りである．

P dest@k
予測モデルによって予測した k 個の目的地セル中に，正解デー

8

12

35
31.0

4
3
SubSyn (式5)

10

25
20

17.4

15
10

SD_dest@ (km)5

2

SubSyn (式7)1

5SubSynEA
1

2

3

4

5

6

7

8

9

0.6

3

0.5

2.5

SubSynE

1

0.3
0.2

SubSyn (式5)
SubSyn (式7)

0.1

5

6

7

8

9

10

6

7

8

9

10

0.5

1.5

0.4
平滑化なし

0.3

均一追加法

1
0.5

0.2

単方向軌跡拡張法

0.1

双方向軌跡拡張法

0
SubSynSubSynE

SubSynEA(b) 予測時間

図 4: 実験 2 結果

図 3: 実験 1 結果

タが含まれている確率を表す．式で表すと以下の式になる．
正解数|Top |

50.6

2(b) P dest@k

P dest@k =

4

2.2

0
4

3

0.7
2.4

SubSynEA
02(a) SD dest@k

P_dest@予測時間 (mS)

0.4

3

4

SubSynEA

2.7

2

双方向軌跡拡張法
6(a) 学習時間(a) SD dest@k1

単方向軌跡拡張法

0
SubSyn

10

均一追加法

8

2

2.9

0

0

P_dest@

平滑化なし

30

6

学習時間 (S)SD_dest@ (km)

7

1

2

3

4

5

6

7

8

9

10

(b) P dest@k

図 5: 実験 3 結果

SubSyn(式 7) では，SubSyn(式 5) の方が性能が良いことがわ
かる．これは，式 6 より式 8 の方が，出発地を考慮している(14)分，データ量の減少の影響を受けやすいためである．
［実験 2］ SubSyn アルゴリズムの実行速度の比較

SD dest@k
予測モデルによって予測した k 個の目的地セルのうち，正解
データに最も近いセルと正解セルとの距離を表す．距離はセルの中心間の距離を pyproj ライブラリにより求めた．式で表すと以下の式になる．

本実験では SubSyn アルゴリズムの実行速度の比較を行う．
比較を行うのは，SubSyn(式 5)，SubSynE(式 5)，SubSynEA
である．
図 4a から，学習時間では SubSynE の効率が最も良いことがわかる．一方で，図 4b から，予測時間ではどのアルゴリズ

SD dest@k = min (dist(nd , ni ))
1<
= i<
=k

(15)

ムも 3ms 以内と実用的な時間内に予測できることがわかる．

SubSyn(式 5) と SubSynE(式 5) の目的地予測確率は等しい

なお，ni は予測モデルによって予測した目的地セルを表し，nd

ので，実験 1，2 から SubSynE(式 5) が最も精度が良く，効率は実際の目的地セルを表す．

が良いためパーソナライズに最も適していることがいえる．

6. 3 SubSyn アルゴリズムの比較

6. 4 仮想軌跡追加手法の比較

SubSyn アルゴリズムには，4. で述べたとおり，目的地予測

5. 2 節で導入した３種類（i.e., 均一追加法，単方向軌跡拡張

確率が異なる２種類 (i.e., 式 5，式 7)，アルゴリズムが異なる

法，双方向軌跡拡張法）の仮想軌跡追加手法によるパーソナラ

３種類がある (i.e., SubSyn，SubSynE，SubSynEA)．そのた

イズ目的地予測の精度向上の効果を確認する．

め，SubSyn アルゴリズムには全部で５種類存在する (i.e., Sub-［実験 3］ 仮想軌跡追加手法の比較

Syn(式 5)，SubSyn(式 7)，SubSynE(式 5)，SubSynE(式 7)，

本実験では，上記のように最もパーソナライズに適していた

SubSynEA)．これらの SubSyn アルゴリズムのうち，どのア

SubSynE(式 5) をベースとし，３種類の仮想軌跡追加手法によルゴリズムがパーソナライズに適しているか比較を行う．

る平滑化を行い，精度の変化を観察する．

［実験 1］ SubSyn アルゴリズムの目的地予測精度の比較

図 5a，図 5b から k > 1 で単方向軌跡拡張法がベースライン

初めに，SubSyn アルゴリズムによるパーソナライズ目的地の精度を上回っており，平滑化により精度が向上していることの精度の比較を行う．比較を行うのは目的地予測確率が異なるが確認できる．しかし，k = 1 のときはベースラインが最も精

SubSyn(式 5)，SubSyn(式 7)，SubSynEA の３種類である．

度が良く平滑化により精度が悪くなっている．これは，平滑化実験結果 (図 3a，図 3b) から SubSynEA の精度が最も低により予測可能な目的地が増えるため，出力数が少ない場合にいことがわかる．これは，単一のユーザの軌跡のみではデー

は，正解セル以外を出力する可能性が高くなるためと考えれら

タ量が大きく不足しているためである．また，SubSyn(式 5)，れる．

均一追加法は他の２つの仮想軌跡追加手法と比較し，その精10

精度が劣っている．これは，仮想軌跡を過去の軌跡とは無関係9に追加するため，一部の仮想軌跡がノイズになってしまったと考えられる．
単方向軌跡拡張法と双方向軌跡拡張法を比較すると，

P dest@k で は 単 方 向 軌 跡 拡 張 法 の 方 が 高 精 度 で あ る が ，SD_dest@ (km)度が劣っており，ベースラインと比較しても k が小さい場合に

列5
列4
列3
列2
列1

8
7
6

（時間モデル）（SubSynE’）

543

SD dest@k では k によって異なる．このことから，単方向2軌跡拡張法は正解セルを出力しやすいが，正解セル以外を出力1するとき，双方向軌跡拡張法の方が正解セルに近いセルを出力

0
1

2

3

4

5

6

7

8

9

10

できることがわかる．

6. 5 時間モデル導入の効果(a) SD dest@k

5. 3 節で導入した時間モデルの併用によるパーソナライズ目
的地予測の精度向上の効果を確認する．

0.8［実験 4］ 時間モデルの併用

0.7
0.6

もの（以降，SubSynE’ と呼ぶ）と時間モデルを併用し，重みを変化させたときの精度の変化を観察する．本実験で併用するモデルは２つであるため，目的地予測確率は式 12 を用いる．なお，式 12 の P1 (nd |Top ) が SubSynEの目的地予測確率，P2 (nd |Top ) が時間モデルの目的地予測確率を表すとする．
本実験では w = 0, 0.25, 0.5, 0.75, 1 と，w を 0.25 刻みに変化

P_dest@

本実験では，SubSynE(式 5) に単方向軌跡拡張法を行った

0.5
0.4

列1
列2
列3
列4
列5

0.3
0.2
0.1

（時間モデル）（SubSynE’）

0
1

2

3

4

5

6

7

8

9

10

させて精度の比較を行う．そのため，w = 0 のとき SubSynE’の重みが 0 となり，時間モデル単独での目的地予測となる．同様に，w = 1 のとき時間モデルの重みが 0 となり，SubSynE’(b) P dest@ k

図 6: 実験４

結果

単独での目的地予測となる．
図 6a から k > 1 で SubSynE’ の SD dest@k と時間モデルの SD dest@k を各併用モデル（i.e., w = 0.25, 0.5, 0.75）のSD dest@k が上回っていることが確認でき，モデルの併用が有効であることがわかる．しかし，k = 1 では SubSynE’ が各併用モデルの精度を上回っている．これは，時間モデルの

k = 1 での精度が SubSynE’ の精度に比べて大きく劣っているためと考えられる．また，図 6b から k < 4 では SubSynE’ の

P dest@k が最も高いものの，k > 4 では，w = 0.5, 0.75 の併用モデルの P dest@k が上回っていることがわかる．そのため，

k が大きい程，モデルの併用の効果が大きいといえる．

7. まとめと今後の課題
本稿では，データスパースネス問題を考慮したパーソナライ
ズ目的地予測手法を提案した．最新の目的地予測手法である

SubSyn アルゴリズムをベースにパーソナライズした予測を行うため，３種類の仮想軌跡の追加手法を提案した．また，予測精度を向上するため，モデルの併用を提案し，時間モデルの導入を行った．さらに，実データを用いた実験により，SubSyn
アルゴリズムと比較を行い，提案手法のうち単方向軌跡拡張法，
双方向軌跡拡張法の２種類の追加手法，時間モデル導入が k が

1 よりも大きいときに精度が向上することを確認した．これは，目的地予測に基づく POI レコメンドサービスにおいて，複数個の推薦を行う際の精度向上に繋がるため有効な特徴といえる．
今後の課題として，具体的なアプリケーションを考慮した評

価指標の考慮や，モデル間の重みのパーソナライズ，併用モデ
ルを用いた柔軟な外部情報の利用などが挙げられる．
文

献[1] http://geohash.org/site/tips.html.
[2] J. Alvarez-Lozano, J. A. Garcı́a-Macı́as, and E. Chávez.
Learning and user adaptation in location forecasting. In
Proceedings of the 2013 ACM conference on Pervasive andubiquitous computing adjunct publication, pages 461–470.
ACM, 2013.
[3] D. Ashbrook and T. Starner. Using gps to learn significant locations and predict movement across multiple users.
Personal and Ubiquitous Computing, 7(5):275–286, 2003.
[4] L. Chen, M. Lv, and G. Chen. A system for destination andfuture route prediction based on trajectory mining. Pervasive and Mobile Computing, 6(6):657–676, 2010.
[5] V. Gogate, R. Dechter, B. Bidyuk, C. Rindt, and J. Marca.
Modeling transportation routines using hybrid dynamic
mixed networks. arXiv preprint arXiv:1207.1384, 2012.
[6] E. Horvitz and J. Krumm. Some help on the way: Opportunistic routing under uncertainty. In Proceedings ofthe 2012 ACM conference on Ubiquitous Computing, pages
371–380. ACM, 2012.
[7] J. Krumm and E. Horvitz. Predestination: Inferring destinations from partial trajectories. In UbiComp 2006: Ubiquitous Computing, pages 243–260. Springer, 2006.
[8] J. Krumm and E. Horvitz. Predestination: Where do you
want to go today? Computer, 40(4):105–107, 2007.
[9] L. Liao, D. J. Patterson, D. Fox, and H. Kautz. Learningand inferring transportation routines. Artificial Intelligence,
171(5):311–331, 2007.
[10] N. Marmasse and C. Schmandt. A user-centered location

[11]

[12]

[13]

[14]

[15]

[16]

[17]

model. Personal and ubiquitous computing, 6(5-6):318–321,
2002.
D. J. Patterson, L. Liao, D. Fox, and H. Kautz. Inferring high-level behavior from low-level sensors. In UbiComp
2003: Ubiquitous Computing, pages 73–89. Springer, 2003.
D. Qiu, P. Papotti, and L. Blanco. Future locations prediction with uncertain data. In Machine Learning and Knowledge Discovery in Databases, pages 417–432. Springer, 2013.
R. Simmons, B. Browning, Y. Zhang, and V. Sadekar.
Learning to predict driver route and destination intent.
In Intelligent Transportation Systems Conference, 2006.
ITSC’06. IEEE, pages 127–132. IEEE, 2006.
D. Tiesyte and C. S. Jensen. Similarity-based predictionof travel times for vehicles traveling on known routes. In
Proceedings of the 16th ACM SIGSPATIAL international
conference on Advances in geographic information systems,
page 14. ACM, 2008.
A. Y. Xue, J. Qi, X. Xie, R. Zhang, J. Huang, and Y. Li.
Solving the data sparsity problem in destination prediction.
The VLDB Journal, 24(2):219–243, Apr. 2015.
A. Y. Xue, R. Zhang, Y. Zheng, X. Xie, J. Huang, andZ. Xu. Destination prediction by sub-trajectory synthesis
and privacy protection against such prediction. In Data
Engineering (ICDE), 2013 IEEE 29th International Conference on, pages 254–265. IEEE, 2013.
B. D. Ziebart, A. L. Maas, A. K. Dey, and J. A. Bagnell.
Navigate like a cabbie: Probabilistic reasoning from observed context-aware behavior. In Proceedings of the 10thinternational conference on Ubiquitous computing, pages
322–331. ACM, 2008.