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

DEIM Forum 2016 H1-2

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

瀧本

祥章

†

_西田

_京介

††

_{遠藤 結城}

††

戸田

浩之

††

_澤田

_宏

††

_{石川 佳治}

†

†

名古屋大学大学院情報科学研究科 〒 464–8601 愛知県名古屋市千種区不老町

††

日本電信電話株式会社 NTT サービスエボリューション研究所 〒 239–0847 神奈川県横須賀市光の丘 1-1

E-mail:

†

[email protected], [email protected]

†† {

nishida.kyosuke,endo.yuki,toda.hiroyuki,sawada.hiroshi

}

@lab.ntt.co.jp

あらまし

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

サービスなど，個人の移動軌跡を利活用した新たなサービスの需要が高まっている．本研究では，ユーザの移動軌跡

集合から学習を行った後，出発地から現在地までの移動軌跡を入力として，そのユーザの目的地を予測する手法の提

案をする．最新の目的地予測手法である SubSyn アルゴリズムをベースにパーソナライズした予測を行うため，デー

タスパースネス問題の解決と，予測時間帯を考慮した確率モデルの導入を実施した．25 人の被験者の実際の移動軌跡

を用いた実験を行い，提案手法がベースラインに比べて高精度に目的地を予測できたことを示す．

キーワード

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

1.

は じ め に

近年，スマートフォンなどのGPS機能がついたモバイルデバ イスやカーナビゲーションシステムの普及により，個人の移動 軌跡を容易に収集できるようになった．それに伴い，パーソナ ルアシスタントサービスなど，収集した移動軌跡を利活用した 新たなサービスの需要が高まっている．例えば，ユーザの現在 の移動軌跡から目的地を予測し，目的地周辺のレストランや娯 楽施設などPOI (Point Of Interest)のレコメンドを行うサー ビスが想定される．このサービスを行うには，高精度な目的地 予測技術が必要であり，様々な手法が提案されている[2–17]． しかし，既存手法にはいくつかの共通の課題がある．例えば， 収集した移動軌跡のデータ量が不十分な場合に，予測可能な 問合せ（出発地から現在地までの移動軌跡）や目的地が制限さ れるといったデータスパースネス問題である．最新の目的地予 測技術であるSubSynアルゴリズム[15, 16]は収集した移動軌 跡を部分軌跡に分割して合成することにより，問合せや目的地 の制限を緩和し，データスパースネス問題に対応した．だが， パーソナライズについては述べられていない．パーソナライズ した目的地予測では，単一のユーザの軌跡を用いて処理を行う ため，収集できる移動軌跡のデータ量が非常に少なくなる傾向 がある．この場合，SubSynアルゴリズムによるデータスパー スネス問題への対策は不十分であり，予測可能な問合せや目的 地が制限されてしまう．また，SubSynアルゴリズムは移動軌 跡に付加されているタイムスタンプを考慮していないため，収 集した移動軌跡を十分に活用できていない． そこで本稿では，単一のユーザの軌跡からデータスパース ネス問題を考慮して目的地予測を行う手法を提案する．まず， SubSynアルゴリズムのデータスパースネス問題を，学習デー タに仮想的な軌跡を追加することにより解決する．次に，精度 の向上を図るため，軌跡に付加されているタイムスタンプを利 用して時間帯を考慮する目的地予測を提案し，SubSynアルゴ リズムとの併用を行う．最後に，25人の被験者の実際の移動軌 跡を用いた評価実験を行い，提案手法が従来のSubSynアルゴ リズムよりも高精度なパーソナライズ目的地予測ができること を示す． 本稿の主な貢献は以下の通りである． • データスパースネス問題を考慮したパーソナライズ目的 地予測の提案 • 時間帯を考慮したパーソナライズ目的地予測の提案 • 予測モデルの併用によるパーソナライズ目的地予測の精 度向上 • 評価実験による提案手法の有効性の確認 本稿の構成は以下の通りである．まず，2.で関連研究とし て，目的地予測に関する研究を紹介する．次に3.で本研究に おける基本的な概念の定義や問題設定を行う．4.で拡張を行う SubSynアルゴリズム[15, 16]を紹介し，5.で提案手法の詳細 を述べる．6.で提案手法を評価するために行った実験について 述べる．最後に，7.で本稿のまとめと今後の課題について述 べる．

2.

関 連 研 究

本章では，目的地予測の関連研究を紹介する．目的地予測に おける先行研究は多数存在するが，目的地予測をパーソナライ ズする研究と外部情報を追加することにより予測精度向上を図 る研究の２つの方向性がある．順にこれらの先行研究について 述べ，本研究との相違点について述べる．その後，本研究で拡 張するSubSynアルゴリズムについて簡単に述べる． 2. 1 パーソナライズされた目的地予測 パーソナライズされた目的地予測では，個々のユーザの軌跡

を用いて，各ユーザに合わせた予測を行う．例えば，Marmasse らは現在地までの軌跡と部分一致する軌跡をユーザ自身の過 去の軌跡から抽出して予測を行っている[10]．Tiesyteらは軌 跡間の距離を定義することにより，現在地までの軌跡と部分 一致する軌跡ではなく，最近傍の軌跡を抽出して予測を行って いる[14]．また，Pattersonらは教師なし学習により交通手段 （e.g.,バス，車）を推定し，交通手段特有の制限（e.g.,バス停， 道路情報）や移動距離を考慮することにより予測を行ってい る[11]．Ashbrookらは過去に訪れた地点を抽出し，地点間の 移動確率を考慮して目的地予測を行っている [3]．他にも，道 路情報を用いる研究 [9, 13]や携帯電話の基地局を利用する研 究[12]，軌跡データの欠損を考慮する研究[4]，軌跡からPOI を抽出し，曜日や時刻に依存するユーザの習慣を利用する研 究[2]など多数の先行研究がある． これらの研究では単一のユーザの軌跡を用いて目的地予測を 行う．しかし，単一のユーザの軌跡を用いて予測を行う場合に は，利用できる軌跡が少ないため，予測可能な入力軌跡や目的 地が極端に少なくなるといったデータスパースネス問題が生じ る．本研究はデータスパースネス問題を考慮して目的地予測を 行うという点でこれらの先行研究と異なる． 2. 2 外部情報の追加 軌跡情報だけでなく，外部情報を追加して利用することによ り，予測精度の向上を図った先行研究を紹介する．Horvitzら は現在地から1時間以内で行ける交差点を交差点の位置情報 と軌跡情報から抽出して目的地候補とし，ユーザの移動によ る到達可能時間の変化を用いて予測目的地を決定する[6]．ま た，Krummらは場所の特性（e.g.,商店街，海）に関する情報 や人々の移動時間の分布を用いて予測を行う[7, 8]．他にも，事 故や工事，イベント，天気といったリアルタイムの情報や道路 情報を用いる研究[5, 17]など多数の先行研究がある． これらの研究では多数のユーザの軌跡や外部情報が得られる ことを前提としている．しかし，多数のユーザの軌跡や上記の ような外部情報は常に得られるとは限らない．本研究は単一の ユーザの軌跡から外部情報を用いずに，目的地予測を行うとい う点でこれらの先行研究と異なる． 2. 3 SubSynアルゴリズム SubSynアルゴリズムはXueらが[16]で提案し，[15]で改良 を行った外部情報を必要としないアルゴリズムである．SubSyn アルゴリズムでは多数のユーザから得た軌跡を部分軌跡に分 解し，合成して目的地予測に用いる．これにより，目的地予測 において問題となるデータスパースネス問題に対処している． また，オフラインで行う学習フェーズとオンラインで行う予測 フェーズの２つのフェーズを持つように構築されており非常に 効率的である． SubSynアルゴリズムはデータスパースネス問題に対処して いるが，今回のように単一ユーザの軌跡のみを用いた予測を行 う場合など，データ量が非常に少ない場合にはその取組みは不 十分である．本研究ではSubSynアルゴリズムの学習データへ の仮想軌跡の追加や時間帯を考慮した予測モデルの併用によ り，パーソナライズされた目的地予測の精度向上を実現する． SubSynアルゴリズムの詳細は4.で述べる．

3.

問 題 設 定

本章では，本研究における基本的な概念の定義や問題設定を 行う．また，本稿で用いる記号の一覧を表1に示す. 表1: 本稿で用いる記号一覧 記号 意味 li, ls, lc, ld 観測地，出発地，現在地，目的地 lat, lon, t 緯度，経度，時刻 ni(, ns, nc, nd) （出発地，現在地，目的地）セル m セルの数 D 軌跡データセット To 観測軌跡 T 離散化軌跡 Ti セル niを通過する軌跡 Ti,j セル ni, njを連続して通過する軌跡 Tstart=ns 出発地セルが nsの軌跡 Tdest=n_d 目的地セルが ndの軌跡 Tstart=ns,dest=nd 出発地セルが ns，目的地セルが ndの軌跡 Top, Tp 問合せ観測軌跡，問合せ軌跡 pi,j セル niからセル njへの遷移確率 pi→j セル niからセル njへの総遷移確率 M, MT _{遷移行列，総遷移行列} k 出力数 L セル間のマンハッタン距離 wi i 番目の予測モデルの重み H 時間帯 3. 1 基本的な概念 本研究ではGeohash [1]などのグリッドによって，セルに分 割された空間上で目的地予測を行う． まず，目的地予測に用いる観測軌跡と離散化軌跡を以下のよ うに定義する． ［定義1］ 観測軌跡To={ls, . . . , ld}は移動物体の位置をある 一定の時間間隔で観測した点の系列である．観測軌跡中の各点 liは緯度lat，経度lon，タイムスタンプtを持つ．各観測軌跡 の長さ_|To|は観測軌跡ごとに異なっていても良いものとする． ［定義2］ 離散化軌跡T ={ns, . . . , nd}は観測軌跡Toの各点 を，その点が属するセルに置き換えたものである．ただし，同 一セルが連続する場合には，2番目以降のセルを削除し，同一 セルが連続しないようにする．また，離散化した軌跡内で連続 するセルni, njにおいて，セルnjはセルniの東西南北のいず れかの方向に位置する４近傍となる．連続したセルが近傍とな らない場合には，観測軌跡を線形的に補間をすることによりセ ルを補う．本稿では以降，あるセルが他のセルの４近傍に位置 することを隣接すると呼ぶ． 例えば，図1のように観測軌跡Toが得られたとき，離散化軌 跡T は_{n7, n4, n5, n2, n3}となる．本稿では以降離散化軌跡 を単に軌跡と呼ぶ．

観測軌跡 観測軌跡の線形補間 離散化軌跡 図1: 観測軌跡と離散化した軌跡の例 次に，目的地を予測する領域を以下のように定義する． ［定義3］ 予測対象領域{n1, n2, . . . nm}は予測目的地として 出力しうるセルの集合である．本研究では，ユーザの過去の軌 跡に対する最小外接矩形と重なるセルとする．ここで，最小外 接矩形は観測軌跡中の全ての点を内側または境界線上に含む最 小の矩形を表す． また，特定のセルを通過する軌跡を以下のように表す． ［定義4］ セルを通過する軌跡Tiはセルniを通過する軌跡で あり，Ti,jはセルni, njを連続して通過する軌跡である．例え ば，図1の離散化軌跡T ={n7, n4, n5, n2, n3}はT4,5である が，T4,2ではない．また，出発地がnsである軌跡をTstart=ns と表し，目的地がndである軌跡をTdest=ndと表す．加えて，出 発地がnsであり，目的地がndである軌跡をTstart=ns,dest=nd と表す． 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を通過する軌跡の割合であ る．定式化すると以下のようになる． pi,j = P (nj|ni) = |T i,j| |Ti| (1) ［定義6］ 遷移行列Mは各隣接セル間の遷移確率を表すm×m の二次元行列である．Mの一方の次元は現在のセルを表し，他 方は遷移後のセルを表す．即ち，Mの要素Mi,jはpi,jである． 例えば，図1の遷移行列Mは以下のようになる． M =                     0 p1,2 0 p1,4 0 0 0 0 0 p2,1 0 p2,3 0 p2,5 0 0 0 0 0 p3,2 0 0 0 p3,6 0 0 0 p4,1 0 0 0 p4,5 0 p4,7 0 0 0 p5,2 0 p5,4 0 p5,6 0 p5,8 0 0 0 p6,3 0 p6,5 0 0 0 p6,9 0 0 0 p7,4 0 0 0 p7,8 0 0 0 0 0 p8,5 0 p8,7 0 p8,9 0 0 0 0 0 p9,6 0 p9,8 0                     (2) Mは１回の遷移でセル間を移動する確率を表し，r乗すること により，r回の遷移で移動できる確率を表せる． 次に実際の移動で生じる迂回を考慮して，セル間を複数回の 遷移で移動する確率を定義する． ［定義7］ 総遷移確率pi→jはL回から⌈1.2L⌉回の遷移でセ ルniから任意のセルnjに移動する確率である．ただし，Lは 隣接セル間の距離を1としたときの，セルniとセルnjの間の マンハッタン距離である．また，1.2は２点間を実際に移動す る際に考慮する迂回路の最大の長さを表す定数である．定式化 すると以下のようになる． pi→j= ⌈1.2L⌉_∑ r=L Mi,jr (3) 例えば，図1でp7→3はL = 4, ⌈1.2 × 4⌉ = 5となるため， p7→3= M7,34 + M7,35 となる． ［定義8］ 総遷移確率行列MT _{はセル間の総遷移確率を表す} m× mの二次元行列である．MT_{の一方の次元は現在のセルを} 表し，他方は移動後のセルを表す．即ち，MTの要素Mi,jT は pi→jである． 例えば，図1の総遷移行列MT は以下のようになる． MT =                     0 p1→2 p1→3 p1→4 p1→5 p1→6 p1→7 p1→8 p1→9 p2→1 0 p2→3 p2→4 p2→5 p2→6 p2→7 p2→8 p2→9 p3→1 p3→2 0 p3→4 p3→5 p3→6 p3→7 p3→8 p3→9 p4→1 p4→2 p4→3 0 p4→5 p4→6 p4→7 p4→8 p4→9 p5→1 p5→2 p5→3 p5→4 0 p5→6 p5→7 p5→8 p5→9 p6→1 p6→2 p6→3 p6→4 p6→5 0 p6→7 p6→8 p6→9 p7→1 p7→2 p7→3 p7→4 p7→5 p7→6 0 p7→8 p7→9 p8→1 p8→2 p8→3 p8→4 p8→5 p8→6 p8→7 0 p8→9 p9→1 p9→2 p9→3 p9→4 p9→5 p9→6 p9→7 p9→8 0                     (4) 最後に各々のセルが目的地である確率を定義する． ［定義9］ 目的地予測確率Pa(nd|Tp)は問合せ軌跡がTpのと き，ndが目的地のセルである確率であり，以下の式のように定 義される． Pa(nd|Tp) = pc→d ps→d· P (nd) (5) ここで，P (nd)は学習データセット内の軌跡のうち，目的地の セルがndである軌跡の割合であり，以下の式のように定義さ れる． P (nd) = |T dest=nd| |D| (6)

4. 2 [15]におけるSubSynアルゴリズムの拡張 Xueらは[15]において，目的地予測確率の求め方を変更し ている．また，改善したアルゴリズムとしてSubSynEアルゴ リズムとSubSynEAアルゴリズムを提案している．これらに ついて順に述べる． 予測確率の求め方の変更 [16]では目的地予測確率を式5によって求めたが，目的地予測 確率はその大小がわかれば正確な値は必要ない．そのため，[15] では以下の式を用いて目的地予測を行う． Pb(nd|Tp)∝ pc→d ps→d· P (nd|ns) (7) なお，P (nd|ns)はセルns を出発地とする軌跡のうち，セル ndを目的地とする軌跡の割合であり，以下の式のように定義さ れる． P (nd|ns) = |T start=ns,dest=nd| |Tstart=ns| (8) この変更によって，出発地と目的地の関係を考慮した目的地 予測が可能となる． SubSynEアルゴリズム SubSynアルゴリズムは遷移行列M の乗算を繰り返し行う必 要があり，時間計算量がO(m3.5)となるという欠点があった． しかし，SubSynEアルゴリズムでは，遷移行列Mが非常にス パースであることに着目し，時間計算量をO(m2.5_{)まで削減す} ることに成功し,効率良く目的地予測を行うことができる． SubSynEAアルゴリズム SubSynアルゴリズムでは，一次マルコフモデルを利用して目 的地の予測を行っている．これに対し，SubSynEAアルゴリズ ムでは二次マルコフモデルを利用して目的地の予測を行う．そ のため，より精度を向上させた目的地予測が可能となるが，学 習に必要となるデータが多くなるといった欠点も存在する．具 体的には，SubSynアルゴリズムが各セル（i.e., ni）を状態と して一次マルコフモデルを用いているのに対し，SubSynEAア ルゴリズムでは隣接セル間の遷移（i.e.,{ni, nj}）を一次マル コフモデルの状態として扱うことにより，各セル（i.e., ni）を 状態とする二次マルコフモデルに拡張する． 4. 3 データ不足により生じる問題点 SubSynアルゴリズムはデータスパースネス問題に対処して いるが，単一ユーザの軌跡のみを用いて予測を行う場合など， 学習データが非常に少ない場合に以下のような問題が生じる． (a) P (nd)が0となる． (b) MTがスパースになり，多くのpi→jが0となる． (c) P (nd|ns)が0となる．または定義されない． これらの問題によって，目的地予測確率P (nd|Tp)の値が0 になる，あるいは，定義されない．そのため，予測可能な目的 地セルが，学習データ内に存在する軌跡の目的地に制限されて しまう．

5.

提 案 手 法

本章では，提案手法の基本的なアイデアを5. 1節で述べ，具 体的な手法を5. 2節，5. 3節で述べる． 5. 1 基本アイデア 提案手法ではSubSynアルゴリズムを単一のユーザの軌跡に 適用し，パーソナライズを行うが，以下の２つのアイデアに基 づいて予測精度の向上を図る． 仮想軌跡の追加 前述のように，SubSynアルゴリズムを単純に単一のユーザの 軌跡に適用すると収集できる学習データの量が少ないため，予 測可能な問合せや目的地が制限されるデータスパースネス問題 が生じる．そこで，ユーザ自身の軌跡に仮想的な軌跡を加えて， 学習データを補うことにより，4. 3節の問題を解決する． 予測モデルの併用 パーソナライズされた目的地予測の精度を向上するために，互 いに独立な複数の予測モデルを組み合わせる．各々の予測モデ ルが互いに独立に予測を行うため，外部情報の追加や異なる要 素の考慮がしやすいといった利点がある．本研究では，軌跡に 付加されているタイムスタンプから，時間帯を考慮して予測を 行う時間モデルを提案する． 5. 2 仮想軌跡の追加 4. 3節で述べた問題を解決するため，学習データに仮想的な 軌跡を追加することにより，P (nd)とMT の平滑化を行う． まず，P (nd)は式6に示すように学習データ内の軌跡がセル ndを目的地としている割合を示す．この値が0のとき，式5 より目的地予測確率が0となり，セルndを目的地として予測 できない．そこで，_Dに含まれる軌跡において目的地となる頻 度がゼロのセルndについても確率値が割り当てられるように 仮想軌跡を追加し，P (nd) > 0とする．式で表すと以下のよう になる． P (nd) = |T dest=nd| + 1 |D| + m (9) 次に，MTがスパースであるとき，式5のps→d，pc→dの値 が0になりやすいため，目的地予測確率は定義されない．もし くは値が0となる．そのため，セルndを目的地として予測で きない．そこで，隣接セル間を遷移する軌跡を仮想的に追加す ることにより，式1のpi,jを以下のように拡張して，MTのス パース性を緩和する． pi,j =|T i,j| + vi,j |Ti| + vi (10) なお，vi,jとviは仮想的に追加した軌跡において，それぞれセ ルniからnjに移動する回数，セルniから移動する回数であ る．仮想軌跡の追加方法として，均一追加法，単方向軌跡拡張 法，双方向軌跡拡張法の３種類を提案する．これらの軌跡の追 加方法の詳細は以下の通りである． 均一追加法 全ての問合せと目的地に対しての予測を可能にするため，予測 対象領域内の全ての隣接セル間の軌跡を追加する．このとき， 予測対象領域の端の影響を無視すると，任意のi, jについて

vi,j= 1，vi= 4である． 単方向軌跡拡張法 学習データの軌跡が通過するセルから隣接するセルへの単方向 の軌跡を追加する．この仮想軌跡の追加方法は，ユーザは訪れ たことがあるセルの周囲のセルにも移動しやすいという考えに 基づいている． 双方向軌跡拡張法 学習データの軌跡が通過するセルとそれに隣接するセル間に双 方向の軌跡を追加する．この仮想軌跡の追加方法は，実際に訪 れたことの無いセルから訪れたことのあるセルへの遷移を追加 するため，単方向軌跡拡張法より強い平滑化を実施することに なる． 例えば，図2aのように学習データが与えられたとき，均一 追加法では図2bのように領域全体に一様に軌跡が追加される． 対して，単方向軌跡拡張法と双方向軌跡拡張法では，それぞれ 図2c，図2dのように学習データの周囲に軌跡が追加される． 5. 3 予測モデルの併用 予測精度を向上させるため，互いに独立な複数の予測モデル を併用する．まず，予測モデルの併用方法について述べる．次 に，本研究で導入する時間モデルについて述べる． 5. 3. 1 予測モデルの併用方法 各予測モデルは各々独立して予測対象領域内の各セルの目的 地予測確率を求める．その後，セルごとに各予測モデルで求め た目的地予測確率に重みをかけて加算する．そのため，予測モ デルの数がN個のときセルndの目的地予測確率P (nd|Top)は 以下のようになる． P (nd|Top) = N ∑ i=1 wiPi(nd|Top) (11) なお，wiはi番目の予測モデルPi(nd|Top)に対する重みを表 し，0 <_{= w}i<_{= 1,} ∑N i=1wi= 1を満たす．特に予測モデルが２ つの場合に，式11は以下の式で表せる． P (nd|Top) = wP1(nd|Top) + (1− w)P2(nd|Top) (12) 複数の予測モデルで独立して予測を行うため，複数の要因を 考慮しやすい，個々の予測モデルを改善しやすいといった利点 がある． 5. 3. 2 時間モデルの導入 一般に，人は決まった時間帯に特定の場所（e.g.,勤務先，自 宅）にいる傾向がある．そのため，現在時刻から目的地を予測 することが可能である．本研究では，現在地における時刻を平 日午前，平日午後，休日午前，休日午後の４つの時間帯に分類 し，各々の時間帯Hにおいてユーザがセルndにいる可能性を 目的地予測確率P (nd|H)とする．そのため，問合せ観測軌跡 Topの現在地lcにおける時刻tcが時間帯Hに分類される場合， 目的地予測確率は以下のようになる． P (nd|Top) = P (nd|Top, H) =|l t∈H∈ nd| |lt∈H| (13) なお，lt∈Hは学習データの時間帯Hにおける観測点を表し， lt∈H ∈ ndはそのうち，セルnd内での観測点を表す． (a) 学習データ (b) 均一追加法 (c) 単方向軌跡拡張法 (d) 双方向軌跡拡張法 図2: 仮想軌跡の追加例 図 2a の学習データ（i.e., 橙の矢印）が与えられたとき，各手法は図 2b, 図 2c, 図 2d のように仮想軌跡（i.e., 青の矢印）を追加し，学習データ を補う．

6.

評 価 実 験

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

実験環境 マシンのCPUはIntel Xeon [email protected]で， メモリは512GBである．また，実装にはPython 2.7.10を用 いて，グリッドはGeohash [1]を用いる．

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

PC（Nexus 7 ver.2012）のGPS及びWi-Fiにより，３秒ごと に測位し，３週間程度収集したものであり，滞留点により分割 して軌跡とする．そのため，各軌跡の出発地と目的地はユーザ が滞留を行った地点となる．１ユーザ当たりの軌跡の数は平均 60個で，軌跡の平均の長さは4.7kmである．なお，滞留点は ユーザ自身によるラベリングにより決定した． 各ユーザの軌跡のうち，７割を学習データとして用いて，残 りの３割をテストデータとして用いる．問合せ観測軌跡Tp o は テストデータの各軌跡の先頭からセル５つ分とする．ただし， 元の軌跡の長さがセル５つ分以下の場合，最終セルは除く．正 解データは各問合せ軌跡の元の軌跡の最終セルndである． 6. 2 評 価 指 標 本研究では，目的地予測の精度を評価するためP dest@k， SD dest@kの２つの評価指標を提案する．これらの評価指標の 詳細は以下の通りである． P dest@k 予測モデルによって予測したk個の目的地セル中に，正解デー

0 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 10 SubSyn (式5) SubSyn (式7) SubSynEA S D _ d e st @ (km) (a) SD dest@k 0 0.1 0.2 0.3 0.4 0.5 0.6 1 2 3 4 5 6 7 8 9 10 SubSyn (式5) SubSyn (式7) SubSynEA P _ d e st @ (b) P dest@k 図3: 実験1結果 31.0 2.9 17.4 0 5 10 15 20 25 30 35

SubSyn SubSynE SubSynEA

学習時間 (S ) (a) 学習時間 2.7 2.4 2.2 0 0.5 1 1.5 2 2.5 3

SubSyn SubSynE SubSynEA

予測 時間 (mS ) (b) 予測時間 図4: 実験2結果 0 2 4 6 8 10 12 1 2 3 4 5 6 7 8 9 1 0 平滑化なし 均一追加法 単方向軌跡拡張法 双方向軌跡拡張法 S D _ d e st @ (km) (a) SD dest@k 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 1 2 3 4 5 6 7 8 9 1 0 平滑化なし 均一追加法 単方向軌跡拡張法 双方向軌跡拡張法 P _ d e st @ (b) P dest@k 図5:実験3結果 タが含まれている確率を表す．式で表すと以下の式になる． P dest@k = 正解数 |Tp o| (14) SD dest@k 予測モデルによって予測したk個の目的地セルのうち，正解 データに最も近いセルと正解セルとの距離を表す．距離はセル の中心間の距離をpyprojライブラリにより求めた．式で表す と以下の式になる． SD dest@k = min 1<_=i<_=k(dist(nd, ni)) (15) なお，niは予測モデルによって予測した目的地セルを表し，nd は実際の目的地セルを表す． 6. 3 SubSynアルゴリズムの比較 SubSynアルゴリズムには，4.で述べたとおり，目的地予測 確率が異なる２種類(i.e.,式5，式7)，アルゴリズムが異なる ３種類がある(i.e., SubSyn，SubSynE，SubSynEA)．そのた

め，SubSynアルゴリズムには全部で５種類存在する(i.e., Sub-Syn(式5)，SubSyn(式7)，SubSynE(式5)，SubSynE(式7)，

SubSynEA)．これらのSubSynアルゴリズムのうち，どのア ルゴリズムがパーソナライズに適しているか比較を行う．

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

初めに，SubSynアルゴリズムによるパーソナライズ目的地 の精度の比較を行う．比較を行うのは目的地予測確率が異なる

SubSyn(式5)，SubSyn(式7)，SubSynEAの３種類である． 実験結果(図 3a，図 3b)からSubSynEAの精度が最も低 いことがわかる．これは，単一のユーザの軌跡のみではデー タ量が大きく不足しているためである．また，SubSyn(式5)， SubSyn(式7)では，SubSyn(式5)の方が性能が良いことがわ かる．これは，式6より式 8の方が，出発地を考慮している 分，データ量の減少の影響を受けやすいためである． ［実験2］ SubSynアルゴリズムの実行速度の比較 本実験ではSubSynアルゴリズムの実行速度の比較を行う．

比較を行うのは，SubSyn(式5)，SubSynE(式5)，SubSynEA

である． 図 4aから，学習時間ではSubSynEの効率が最も良いこと がわかる．一方で，図4bから，予測時間ではどのアルゴリズ ムも3ms以内と実用的な時間内に予測できることがわかる． SubSyn(式5)とSubSynE(式5)の目的地予測確率は等しい ので，実験1，2からSubSynE(式5)が最も精度が良く，効率 が良いためパーソナライズに最も適していることがいえる． 6. 4 仮想軌跡追加手法の比較 5. 2節で導入した３種類（i.e.,均一追加法，単方向軌跡拡張 法，双方向軌跡拡張法）の仮想軌跡追加手法によるパーソナラ イズ目的地予測の精度向上の効果を確認する． ［実験3］ 仮想軌跡追加手法の比較 本実験では，上記のように最もパーソナライズに適していた SubSynE(式5)をベースとし，３種類の仮想軌跡追加手法によ る平滑化を行い，精度の変化を観察する． 図5a，図5bからk > 1で単方向軌跡拡張法がベースライン の精度を上回っており，平滑化により精度が向上していること が確認できる．しかし，k = 1のときはベースラインが最も精 度が良く平滑化により精度が悪くなっている．これは，平滑化 により予測可能な目的地が増えるため，出力数が少ない場合に は，正解セル以外を出力する可能性が高くなるためと考えれら れる．

均一追加法は他の２つの仮想軌跡追加手法と比較し，その精 度が劣っており，ベースラインと比較してもkが小さい場合に 精度が劣っている．これは，仮想軌跡を過去の軌跡とは無関係 に追加するため，一部の仮想軌跡がノイズになってしまったと 考えられる． 単 方 向 軌 跡 拡 張 法 と 双 方 向 軌 跡 拡 張 法 を 比 較 す る と ， P dest@k で は 単 方 向 軌 跡 拡 張 法 の 方 が 高 精 度 で あ る が ， SD dest@k ではk によって異なる．このことから，単方向 軌跡拡張法は正解セルを出力しやすいが，正解セル以外を出力 するとき，双方向軌跡拡張法の方が正解セルに近いセルを出力 できることがわかる． 6. 5 時間モデル導入の効果 5. 3節で導入した時間モデルの併用によるパーソナライズ目 的地予測の精度向上の効果を確認する． ［実験4］ 時間モデルの併用 本実験では，SubSynE(式5)に単方向軌跡拡張法を行った もの（以降，SubSynE’と呼ぶ）と時間モデルを併用し，重み を変化させたときの精度の変化を観察する．本実験で併用す るモデルは２つであるため，目的地予測確率は式 12を用い る．なお，式 12のP1(nd|Top)がSubSynE’の目的地予測確 率，P2(nd|Top)が時間モデルの目的地予測確率を表すとする． 本実験ではw = 0, 0.25, 0.5, 0.75, 1と，wを0.25刻みに変化 させて精度の比較を行う．そのため，w = 0のときSubSynE’ の重みが0となり，時間モデル単独での目的地予測となる．同 様に，w = 1のとき時間モデルの重みが0となり，SubSynE’ 単独での目的地予測となる． 図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レコメンドサービスにおいて，複数 個の推薦を行う際の精度向上に繋がるため有効な特徴といえる． 今後の課題として，具体的なアプリケーションを考慮した評 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 列5 列4 列3 列2 列1 S D _ d e st @ (km) （時間モデル） （SubSynE’） (a) SD dest@k 0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 1 2 3 4 5 6 7 8 9 10 列1 列2 列3 列4 列5 P _ d e st @ （時間モデル） （SubSynE’） (b) P dest@ k 図6: 実験４ 結果 価指標の考慮や，モデル間の重みのパーソナライズ，併用モデ ルを用いた柔軟な外部情報の利用などが挙げられる． 文 献 [1] http://geohash.org/site/tips.html.

[2] J. Alvarez-Lozano, J. A. Garc´ıa-Mac´ıas, and E. Ch´avez. Learning and user adaptation in location forecasting. In

Proceedings of the 2013 ACM conference on Pervasive and ubiquitous computing adjunct publication, pages 461–470.

ACM, 2013.

[3] D. Ashbrook and T. Starner. Using gps to learn signifi-cant 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 and future route prediction based on trajectory mining.

Perva-sive 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:

Op-portunistic routing under uncertainty. In Proceedings of

the 2012 ACM conference on Ubiquitous Computing, pages

371–380. ACM, 2012.

[7] J. Krumm and E. Horvitz. Predestination: Inferring desti-nations from partial trajectories. In UbiComp 2006:

Ubiq-uitous 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. Learning

and inferring transportation routines. Artificial Intelligence, 171(5):311–331, 2007.

model. Personal and ubiquitous computing, 6(5-6):318–321, 2002.

[11] D. J. Patterson, L. Liao, D. Fox, and H. Kautz. Infer-ring high-level behavior from low-level sensors. In UbiComp

2003: Ubiquitous Computing, pages 73–89. Springer, 2003.

[12] D. Qiu, P. Papotti, and L. Blanco. Future locations predic-tion with uncertain data. In Machine Learning and

Knowl-edge Discovery in Databases, pages 417–432. Springer, 2013.

[13] 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.

[14] D. Tiesyte and C. S. Jensen. Similarity-based prediction of 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.

[15] 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.

[16] A. Y. Xue, R. Zhang, Y. Zheng, X. Xie, J. Huang, and Z. Xu. Destination prediction by sub-trajectory synthesis and privacy protection against such prediction. In Data

Engineering (ICDE), 2013 IEEE 29th International Con-ference on, pages 254–265. IEEE, 2013.

[17] B. D. Ziebart, A. L. Maas, A. K. Dey, and J. A. Bagnell. Navigate like a cabbie: Probabilistic reasoning from ob-served context-aware behavior. In Proceedings of the 10th

international conference on Ubiquitous computing, pages