スケジュールに基づく寄り道ナビゲーションシステムの検討
肥 川充†
河 合 由 起 子†

藤川井崎健児††洋††藤大野澤和久††裕††A Proposal of Navigation System by using Personal Schedule
Mitsuru Hikawa,† Kenji Fujii,†† Kazuhisa Fujino,††Yukiko Kawai,† Hiroshi Kawasaki†† and Yutaka Osawa††

1. は じ め に
今や日本でインターネットにつながる端末を利用するユーザは 75.3 ％ に上り*1 ，Web アプリケーショ
ンでは googleMap や Yahoo!Map に代表される地図サービスの利用が 68.7 ％と最も普及している1) ．近
年では，地図サービスとして目的地への最短経路を探索するだけでなく，経由地を寄り道してナビゲーションする研究も多く行われている．これらの寄り道ナビ
ゲーションでは，通勤通学のための日常的に一定の経路を利用している利用者に，買物など別の目的で寄り道を行う手法2) や，待ち合わせ場所に先に到着すると予想されるユーザに対して時間消化のためのナビゲーションを行うシステム3) があげられる．また，出発地と目的地の間で，それら周辺情報を提示し，ユーザが選択することで寄り道できるサービスの検討も行われている4) ．このような寄り道ナビゲーションの多くは，出発地，経由地 (寄り道)，目的地をユーザが選択ある
いは推定し，ナビゲーションを行う．経由地や目的地の推定に関する研究では，GIS 情報だけでなくハイパーリンク構造やブログ情報，閲覧履歴といった Webを利用して観光名所や任意のカテゴリの店舗などを検索し推薦を行う5)6)7) ．また，最短経路探索に関する研究も，古くから多くの研究が行われており，Dijkstraのアルゴリズム8) や A*アルゴリズム9) が代表的である．最近，大澤らにより複数の候補を用いて経路探索を行う寄り道検索が提案されている10) ．しかしながら，これまでの寄り道ナビゲーションサービスでは，数時間といった任意の時点でのあるイベントに対する寄り道は可能であるが，長期的連続するイベントに対† 京都産業大学
Kyoto Sangyo University†† 埼玉大学
Saitama University

するナビゲーションは困難である．そこで，本研究では，個々のユーザの長期的行動に基づいて複数の目的地と経由地を抽出し，経由地を寄り道として推薦するナビゲーションシステム を提案する．ユーザの長期

図1

システムの概要

的行動を分析することで，個々の習慣を検出し，その習慣が定常的な場合は目的地（例えば毎週月曜 11 時に 101 講義室など）とし，習慣ではあるが不定期な場合は経由地（例えば本屋やスーパーなどのジャンルなど）に分類する．また，経由地はジャンルさえ合致すれば良いため，出発地と目的地間に複数存在する可能性が高く，それらの中から最短経路の探索を行う．これにより，複数の連続するイベントに対しても経由地に寄り道しつつ目的地に最短経路で到達できる効率的なナビゲーションが可能になる．

2. システム概要
提案するナビゲーションシステムは，二つの機能を情報処理学会 インタラクション 2010

有する．一つは，ユーザの長期的行動に基づいて目的地と複数の経由地を推定する機能であり，もう一つは，短い寄り道経路で経由地を通りつつ，目的地までの最短経路を瞬時に決定する機能である．これら二つを同時に満たすため，スケジューラと地図とを連動させ時間と空間の統合を図る．システムの概要を図 1 に示
す．ユーザはスケジューラにイベントを記入する．イベントは時間や場所の入力フォームの制約を持たない．
システムは記入された各イベントのテキストデータから日時と地理情報を検出する．地理情報とは，地名や店名などの「組織名」と，歯医者，本屋，市役所などの「ジャンル」などである．さらに，システムは検出された地理情報から緯度経度情報を自動取得し，経路探索などに利用する．イベント情報は地理情報の組織名，ジャンル名とその周辺のイベント情報に基づき，目的地と経由地に分類される．分類されたイベントは，日時に基づき目的地ごと，経由地ごとにランキングされる．目的地のランキングは，1 日単位で行われ，経由地のランキングは，数日単位とする．例えば，1 日に複数の目的地があった場合は，時間の早い順にランキングされ，経由地は，目的地同様に当日の早い順にランキングした後に，翌日以降のイベントを閾値以上抽出してランキングし，追加する．寄り道検索機能では，目的地（組織名，緯度経度）と経由地（ジャンル，緯度経度）から，短い寄り道経路が複数含まれつつ，目的地までの最短経路を算出する．これは，出発地から，指定されたジャンルに属する複数の経由地を候補地として，どれか一つの候補地を経由して目的地に至る最短の経路を求めるものである．出発地はデフォル
トではユーザが指定した自宅や会社とする．本システ
ムにより，目的地に最短で到達できるだけでなく，経路途中でその他のイベントに立ち寄ることができる効
果的なナビゲーションを達成できる．

3. スケジューラを用いた目的地と経由地の推定
本節では，ユーザの長期的な行動管理とそれに基づいた目的地と経由地の推定法について述べる．
3.1 スケジューラ
ユーザの長期的な行動管理の実現を達成するために，スケジューラを利用する．ユーザはスケジューラの各日にイベントを記入する．イベントの記入では，時間や場所の入力フォームを持たず，「10:00」や「午前」，「京都駅」や「101 講義室」，といった自由記述が可能である．ただし，１つのイベントは 1 行に記述するものとする．また，地図のナビゲーションはデフォルトでは 1 日分の記入されたイベントとするが，ユーザが指定をすることで，複数日のイベントによるナビゲーションを可能とする．
3.2 目的地と経由地の推定
目的地と経由地を推定するために，スケジューラに入力された各イベントから，日時と地理情報を抽出す
る．地理情報は，（a）組織名（主に固有名詞），（b）ジャンル（コンビニエンスストアや本屋）とし，目的地は（a），経由地は（b）とする．抽出法はまず，各イベン
トを形態素解析し，日時とイベント名を抽出する．日時は「名詞―副詞接続」（午前や午後）あるいは「数値」（10:00 など）とするが，記入がない場合は NULLとする．イベント名（目的地名，経由地名）は，事前実験より，「名詞−一般」，「固有名詞―組織」，「固有名詞―地域」ならびに「未知語」とし，それらを抽出する．目的地は「固有名詞−組織」とし，その前後に「名詞−一般」が存在する場合には，連続させて組織名とする．ただし，「株式会社京都」など地名が組織名に含まれる場合の処理として，「固有名詞―地域」の前後に「名詞―一般」が存在する場合も組織名と判断し，目的地とする．経由地は「名詞―一般」とする．
次に，抽出した名詞の緯度経度を取得する．緯度経度の取得は Yahoo!Map を用いる．Web を用いた緯度経度の取得は即時性，網羅性，安価という面から有利であるが，大量の検索結果となる問題がある．提案システムでは，イベントの連続性に注目し，Web 検索の際に，1 つ前のイベントの地名（目的地名あるいは経由地名）の県名と市町村名を補間語として用いることで，検索結果を絞り込む．逆に検索結果がない場合は，補間語の地域を広げる．目的地の緯度経度は，前述の抽出した組織名と補間語を用いて検索する．目的地は１地点であるため，複数の緯度経度を取得した場
合は，1 つ前の目的地の緯度経度に最も近い場所とする．経由地は目的地と異なり，目的地に到達するまでに寄り道として通過する地点となるため，複数地点の緯度経度となる．緯度経度の取得後，（出発地，目的地，経由地）の組を作成し，次章の寄り道経路探索処理を行い，地図に表示する．目的地，経由地は，同日内の時間によりランキングし，同順位の目的地と経由地を同じ組として生成する．ただし，同日内の目的地と経由地のランキング数が同じでない場合は，以下の処理を行う．
• 目的地がない場合は，同日内の経由地の最も時間の早いものを目的地とする．
• 経由地が目的地より少ない場合は，翌日以降の経由地を対象とする．
尚，最初の出発地はユーザが初期設定した自宅あるいは大学とし，以降の出発地は 1 つ前の目的地とする．

4. 寄り道経路探索
寄り道経路検索とは，出発地と目的地，複数の経由地（候補地）が与えられたとき，寄り道経路が最短となる候補地，およびその候補地を経由する最短経路を算出するものである．ここで，出発地と目的地は緯度経度で与えられるものとする．また，候補地は，経由したいジャンル（コンビニエンスストアや本屋など）から，該当する複数の候補地の緯度経度を得るものとする．経由地のジャンルを一つだけ指定する寄り道経路検索は STP（simple trip planning）検索と呼ばれる．これは，指定されたジャンルに属する候補地のうち，一箇所を経由して目的地に至る最短の経路を求める検索である．また，複数のジャンルを指定する検索は TPQ（trip planning query）検索と呼ばれる．
こちらは，指定された複数のジャンルの候補地から，それぞれ一箇所ずつ順不同で経由する最短経路を求める検索である．STP 検索の例を図 2 に示す．
4.1 STP 検索のためのアルゴリズム
STP 検索において，最短の寄り道経路だけが求まスケジュールに基づく寄り道ナビゲーションシステムの検討

図 2 STP 検索の例

るのではなく，短い寄り道経路が複数求まるほうが都合は良い．そのため，短い寄り道経路から順に複数個の経路が求まる手法として，我々は双方向探索法と逐次拡大法を提案している10) ．に k 個，およびそれらを経由する寄り道経路を確定することができる．我々は，双方向探索法と逐次拡大法を提案しており，今回これを用いた．その結果，候補地が多く点在するほど，両方式ともに性能が良くなることが示されている．
4.2 TPQ 検索のためのアルゴリズム
TPQ 検索は，指定された複数のジャンルの候補地から，それぞれ一箇所ずつ順不同で経由する最短経路を求める検索である．本論文でも，システムの利便性を高めるためには，複数のジャンルを寄り道することが望ましく，TPQ 検索は必須と考えられる．しかし，この検索は巡回セールスマン問題のように NP 困難であり，最短の経路を容易に求めることができない．Li らは，最短である保障はないが，最短に近いであろう寄り道経路を求めるいくつかの手法を提示している11) ．
これらのアルゴリズムは主として，ユークリッド距離に基づくものである．またそれらの内，NN アルゴリズム（ Nearest Neighbor Algorithm ） と MD アルゴリズム（Minimum Distance Algorithm）は道路網上での距離に基づく解法であり，実験結果から MD アルゴリズムの優位性を主張している．そこで，MD アルゴリズムで必要となる STP 検索と同様な処理において，我々の提案している双方向探索法や逐次拡大法を用いることにより，より最適な TPQ 検索結果が得られることが期待される．そこで，今後これらを実装する予定である．

5. 実験と考察
図 3 出発地および目的地からの探索

双方向探索法は，出発地から目的地までの最短経路長を DSP とし，f（f >= 1.0）を任意に定めたとき，総経路長が f × DSP 以下になる全ての候補地，およびそれらを経由する寄り道経路を求める検索である．このような候補地は，出発地または目的地からの最短経路長が必ず（f × DSP）/2 以下になる．そのため，図3 のように，出発地と目的地それぞれから，Dijkstra法を用いて（f × DSP）/2 の範囲を探索し，この範囲内に含まれる候補地を取得する．そして，これらの各候補地を経由する寄り道経路を，出発地から候補地までの最短経路と目的地から候補地までの最短経路を組み合わせることによって求める．求まった寄り道経路のうち，寄り道経路が f × DSP 以下になる全ての候補地を取得することによって，目的の候補地，およびそれらを経由する寄り道経路を求めることができる．
これに対し，逐次拡大法は寄り道経路が短くなる順にk（任意の実数）個の候補地，およびそれらを経由する寄り道経路を求める検索である．出発地から，目的地を終点とした A*アルゴリズムによって探索を行うとともに，目的地からも同様に，出発地を終点としたA*アルゴリズムによる探索を行う．双方からの探索範囲に含まれた候補地は，A*アルゴリズムの特性により双方からの最短経路が求まるため，その候補地を経由する寄り道経路が確定する．これら確定した寄り道経路のうち，k 番目に短い寄り道経路の長さまで双方の探索範囲を拡大した時点で，寄り道経路が短い順個人のスケジュールに基づく寄り道ナビゲーションシステムを構築し，実験を行った．形態素解析は Chasenを用い，緯度経度の獲得は Yahoo!MapAPI を用いた．
5.1 スケジューラとナビゲーション図 4 に，実装したスケジューラと寄り道ナビゲーションのインターフェースを示す．左側のスケジューラにユーザは自由にイベントを記入できる．右側の地図は，任意の期間内で，出発地，目的地，経由地を抽出し，その最短経路を推薦提示する．経由地は多数あるためユーザは選択することができ，その都度，最短経路が提示される．
5.2 目的地と経由地の推定と緯度経度抽出

図 4 目的地と経由地の推定と緯度経度抽出

図 4 を用いて，被験者 3 人（20 代の男子学生）に約 1 ヶ月分の予定を自由に記入してもらい，目的地と経由地の分類を行った．イベントはほぼ毎日記入されており，イベントが記入された日を対象とした場合

情報処理学会 インタラクション 2010の 1 日のイベント平均記入数は 1.2 件であった．被験者 A は多くのイベントに訪問先の組織名を記入していたが，被験者 B と C は全く組織名の記入がなかった．また，被験者 C は「大学」や「スーパー」など，類似のイベントが A と C と比較して多い傾向であった．なお，目的地と経由地の分類結果に対する適合率と再現率をそれぞれ，適合率=（推薦された正解数／推薦された数）とし，再現率=（推薦された正解数／正解数）とすると，適合率は，目的地，経由地ともに92 ％となった．再現率は，目的地が 72 ％と低かった．
実験の結果より，被験者 C の再現率が 52 ％など目的地の漏れはあるものの，本システムによる目的地と経由地の抽出は有効であることが示された．また，分類された目的地と経由地の緯度経度抽出を行った．抽出結果の適合率（推薦された正解数／推薦された数）は目的地が 88 ％，経由地が 74 ％となった．尚，本シス
テムでは，目的地は検索結果の上位１位の１箇所とし，経由地は検索結果全てとなる．この実験から，Web 検索を利用した目的地と経由地の緯度経度抽出は有効であることが確認できた．
5.3 寄り道経路探索

変接続の前後に訪問先の組織名あるいはジャンル名まで記入されると目的地と経由地に分類できる．これを実現するためには，ユーザに訪問先記入を促すためのアラート機能を考慮する必要がある．ただし，個人の表記の揺れ全てに対応することはできないため，スケジュールを履歴情報としてとらえ，学習することで，目的地と経由地推定の精度向上を図る予定である．緯度経度抽出に関しては，Web 検索の際に自宅の住所を補間語として用いる手法が有効であることが分かった．今後は初期設定に手間はかかるが，自宅だけでなく，職場先や実家の住所も事前に記入してもらうことで，精度向上につなげたい．

6. お わ り に
本稿では，個々のユーザの長期的行動に基づいて経由地を抽出し，それら複数の経由地を寄り道として推薦するナビゲーションシステムを提案した．提案シス
テムでは，スケジューラと地図とを連動させ時空間の管理・統合を実現した．実験より，提案手法による目的地と経由地の推定ならびに最短寄り道経路探索の有効性を確認した．これにより，複数の時系列のイベントから，寄り道しながら目的を達成できる効率的なナビゲーションの実現性を示すことができた．
謝辞 本研究の一部は，総務省戦略的情報通信研究開発制度 (SCOPE) 若手 ICT(072103013) の一環として実施されたものである．ここに記して謝意を表す．

参 考

図 5 寄り道経路探索結果の一例

出発地と目的地，複数の経由地（候補地）が与えられたとき，寄り道経路が最短となる候補地，およびその候補地を経由する最短経路の算出を行い，地図上にプロットした結果を図 5 に示す．赤色が出発地点で青色が目的地点である．小さい黄色と小さい青色の点が候補地を示しており，黄色は（f × DSP）/2 の範囲内の候補地となる．図より出発地から最短の候補地（×印）を経由して目的地にナビゲーションできていることが確認できる．
5.4 考察と今後の課題
目的地と経由地の推定に対する実験結果より，目的地の再現率は低いものの，目的地と経由地の抽出は 8割以上可能であることが示された．目的地に関しては，被験者 A は組織名まで記入していたため「名詞―固有名詞」として 100 ％抽出できた．一方で，目的地，経由地ともに適合率と比較して再現率が低くなった理由は，「名詞―サ変接続」を対象としていないため，「お出かけ」や「就職活動」などが分類できなかったためと考えられる．しかしながら，被験者 A のようにサ文

献1) インターネット白書 2008．
2) 相尚寿，浅見泰司，貞広幸雄，寄り道支援路線図の自動作成システム，地理情報システム学会講演論文集，Vol．
14， pp．273-276， 2008．
3) 曽我真人，角本一嘉，待ち合わせを支援する協調ナビ
ゲーションの提案，情報処理学会研究報告 (UBI)，Vol．
40， pp．75-82，2008．
4) 吉田由紀，定方徹，奥田英範，奥雅博，寄り道おすすめサービスのためのユーザ行動の考察，Web インテリジェ
ンスとインタラクション研究会 (WI2)，Vol．4，2008．
5) Takeshi Kurashima，Taro Tezuka，and Katsumi
Tanaka，Blog Map of Experiences: Extracting andGeographically Mapping Visitor Experiences fromCity Blogs， LNCS3806，pp．496-503，2005．
6) 手塚太郎，近藤浩之，田中克己，混合ガウス分布を用いたウェブコンテンツの地域性推定とオブジェクトレベ
ルローカルサーチ，情報処理学会論文誌（TOD），Vol．
1， No．1， pp．13-25， 2008．
7) 相良毅，喜連川優， Web からの効率的な新規店舗の発見・登録支援手法，情報処理学会論文誌（TOD），Vol．
48，No．SIG11， pp．49-57， 2008．
8) E．W．Dijkstra，A note on two problems in connection with graphs，Numeriche Mathematik， 1，pp．269-271，1959．
9) P．E．Hart，N．J．Nillson and B．Raphael，Aformal basic for the heuristic determination of minimum cost paths，IEEE Transaction of SystemsScience and Cybernetics，ssc- 4，2，pp．100-107，
1968．
10) 大沢裕，藤野和久，道路網上での最短寄り道経路検索ア
ルゴリズム，信学技報，ITS2008-27，pp．1-6，2008．
11) F，Li，D，Cheng，M，Hadjielefttheriou，G．Kollios and S．H．Teng，On trip planning queriesin spatial databases，SSTD 2005，LNCS 3633，
Spring-Verlag，pp．273-290，2005．