(57)【要約】本発明の実施形態は、ナビゲーションシステムにおいて行先の履歴に従って移動先を予測する方法を提供する。予測するために用いられるモデルが行先のデータベースを組み込み、そのデータベースは、ユーザーにとって好みの、すなわち、最も確からしい行先を含むことができる。また、そのモデルは、現在の時刻、曜日、現在地、現在の方向、過去の場所、気象等の特徴を含むことができるコンテキストも使用する。そのモデルは、行先が正確にわからないときでも、行先及び行先カテゴリを推測する。具体的には、方法が、その移動の以前の状態を表す予測モデルを用いて、その移動の現在の状態を表す特徴ベクトル、行先及び行先のカテゴリの確率に基づいて、移動中に行先を予測する。最も高い確率を有する行先及び行先のカテゴリのサブセットがユーザー選択のために出力される。
2016536597.tif 000002
【特許請求の範囲】
【請求項１】
移動中に行先を予測する方法であって、
前記移動の以前の状態に基づいて、これまでに行先及び行先カテゴリに移動した確率を推測するステップと、
前記移動の現在の状態を表す特徴ベクトルに基づいて、前記移動の以前の状態と、前記行先及び行先カテゴリとに基づく予測モデルを用いて、前記行先のカテゴリの確率を予測するステップと、
ユーザー選択のために、最も高い確率を有する前記カテゴリのサブセットを出力するステップと、
を含み、前記ステップはプロセッサにおいて実行される、方法。
【請求項２】
前記特徴ベクトルは、車両ナビゲーションデータと、車両システムバスデータと、気象データと、導出データとを含む、請求項１に記載の方法。
【請求項３】
前記予測モデルはＮグラムに基づく、請求項１に記載の方法。
【請求項４】
前記モデルは、確率＋ユニット（プロビット）回帰モデルであり、従属変数は２つの値のみをとることができる、請求項１に記載の方法。
【請求項５】
前記モデルのパラメーターを正規化することと、
前記特徴ベクトルを低次元部分空間に変換することと、
を更に含む、請求項１に記載の方法。
【請求項６】
前記予測することは、確率的モデルを用いる、請求項１に記載の方法。
【請求項７】
多項分布を用いて前記行先を予測する、請求項１に記載の方法。
【請求項８】
カテゴリがジャンル、名称及び行先の階層を含む、請求項１に記載の方法。
【請求項９】
前記予測することは、行先のデータベースと、場所の履歴との組み合わせを用いる、請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は包括的には移動先を予測することに関し、詳細には、履歴データに基づいて予測することに関する。
【背景技術】
【０００２】
運転者及び船長が不慣れなエリアを通って不慣れな行先まで運転及び操舵するのを助けるために、ナビゲーションシステムが紙の地図及び海図に取って代わりつつある。大部分のナビゲーションシステムは、車両、船舶又は飛行機の厳密な場所を特定するために全地球測位システム（ＧＰＳ：ｇｌｏｂａｌ  ｐｏｓｉｔｉｏｎｉｎｇ  ｓｙｓｔｅｍ）を含む。１つの利点として、ナビゲーションシステム内のデータは絶えず更新することができ、経路途中の付加情報によって増大させることができ、システム間で容易に転送することができる。
【０００３】
通常、行先は操作者又は乗客によって設定される。行先は、地名、住所、電話番号、事前に登録された行先のリストから選択された事前に選択された地理的位置等に基づくことができる。特定の経路の知識を、状況及び環境データ、例えば、交通及び気象のデータとともに用いて、特定の行先まで操作者及びナビゲーターを助けることができる。
【０００４】
特許文献１は、行先を予測し、車両位置データを受信する方法を記載している。車両位置データは現在の行程を含み、その車両のための行先を予測するために、現在の行程が以前の行程と比較される。行先までの経路も提案することができる。
【０００５】
特許文献２は、行程の行先を予測するナビゲーションデバイス及び方法を記載している。その方法は、その行程の出発点、出発時刻及び日付を含む出発パラメーターを決定する。行程履歴の情報を用いることによって、予測アルゴリズムが生成される。
【０００６】
特許文献３は、車両ナビゲーションシステムが車両のための行先を入手するのを助けるための予測行先エントリシステムを記載している。ナビゲーションシステムは、以前の運転履歴又は習慣を用いる。この情報は、車両のユーザーによって望まれる現在の行先に関する予測を行うために用いられる。その情報は、異なるユーザープロファイルに分離することができ、車両の場所、車両の以前の運転履歴、車両のユーザーの以前の検索履歴、又は車両の１つ若しくは複数の特性に関連する感覚入力（ｓｅｎｓｏｒｙ  ｉｎｐｕｔ）を含むことができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第７，２３３，８６１号
【特許文献２】米国特許出願公開第２０１１／０２３８２８９号
【特許文献３】米国特許出願公開第２０１３／０１６６０９６号
【発明の概要】
【０００８】
本発明の実施形態は、ナビゲーションシステムにおいて行先の履歴に従って移動先を予測する方法を提供する。予測のために用いられるモデルが行先のデータベースを組み込み、データベースはユーザーにとって好みの、すなわち、最も確からしい行先を含むことができる。
【０００９】
また、モデルは、現在の時刻、曜日、現在地、現在の方向、過去の場所、気象等の特徴を含むことができるコンテキストを使用する。モデルは、行先が正確にわからないときでも、行先を推測する。
【００１０】
具体的には、方法が、その移動の以前の状態に基づく予測モデルを用いて、その移動の現在の状態を表す特徴ベクトル、行先のカテゴリの確率に基づいて、移動中に行先を予測する。最も高い確率を有するカテゴリのサブセットがユーザー選択のために出力される。
【図面の簡単な説明】
【００１１】
【図１】本発明の実施形態による、履歴データに基づいて移動先を予測する方法の流れ図である。
【図２】本発明の実施形態による、階層型行先カテゴリ予測モデルの図である。
【図３】本発明の実施形態による、行先カテゴリ依存性を用いる行先カテゴリ予測モデルの図である。
【発明を実施するための形態】
【００１２】
序論
本発明の実施形態は、ナビゲーションシステムにおいて移動活動の履歴に従って移動先を予測する方法を提供する。本明細書において説明される例では、その移動は車両によって実行される。しかしながら、本明細書において説明される方法によって、他の移動形態も予測できることは理解されたい。その方法は、バスによって接続されたメモリ、入出力インターフェースに接続されるプロセッサにおいて実行することができる。出力デバイスは、ユーザーに行先を示すディスプレイ又はスピーカーを含むことができる。入力デバイスは、具体的な行先を選択する全地球測位システム（ＧＰＳ）タッチスクリーン、キーボード及び音声認識システムからの場所軌道を含むことができる。
【００１３】
方法概説
本方法は、ナビゲーションデータ１０１と、（車両）システムバスデータ１０２と、気象データ１０３と、導出データとを取り込む。導出データの中には、車両ナビゲーションシステムデータ１０１、車両バスデータ１０２、及び気象データ１０３から入手できるものもある。ナビゲーションシステムは、ＧＰＳと、種々の情報サーバーへのワイヤレスインターネット接続とを含むことができる。車両バスは、車両（例えば、自動車、バス、列車、工業用若しくは農業用車両、船舶又は航空機）内の構成要素を相互接続する任意の特殊内部通信ネットワークと定義される。データを同期させて（１１０）、特徴ベクトル１２１として特徴を抽出する（１２０）。各特徴ベクトルは、或る過去の時間にわたる移動の以前の状態をまとめて表す。
【００１４】
トレーニング
一度、間欠的、定期的、又は連続的とすることができるトレーニング段階１５５中に、トレーニングデータベース１５１に特徴が記憶される。また、トレーニングは、企業、政府機関、住居、ランドマーク及び他の地理的に位置する実在物のような、具体的な行先に関連付けられる場所、住所、名称、識別子、カテゴリを含む行先データベース１５０を維持管理する。そのような行先データベースはサーバー上に位置することもできる。行先カテゴリは、そのタイプ、品質、利用可能性等の、行先選択に関連する任意の意味情報を含むことができる。
【００１５】
トレーニング中に、行先カテゴリの確率が推測される（１５３）。すなわち、その確率は行先のカテゴリに関連付けられる。行先カテゴリの確率は、従来技術のシステムにおいて一般に見られるような、その行先の識別情報と混同すべきでない。また、トレーニングは、移動中に観測された軌道も確定する（１５２）。ナビゲーションユーザーインターフェースを通して、ユーザーの実際の行先が不明である場合、観測された軌道を用いて、各行先に関連付けられる確率と、その関連付けられるカテゴリとを推測する。トレーニング中に推測された、軌道と、確率的に推測された行先及び行先カテゴリとを用いて、予測モデル１６０を構成する。
【００１６】
動作
動作中に、実際の移動の現在の状態に関する類似の特徴がリアルタイムに取り込まれ、予測手順１３０によって処理され、行先の確率１３１、行先カテゴリ、及び行先に電話をかける等の関連する行動が得られる。最も高い確率を有する、例えば、高い方から３つの確率を有する予測された行先、カテゴリ及び行動が表示されるか（１４０）、又は音声出力のような出力ユーザーインターフェース１４１上で他の手段によって選択肢としてユーザーに提示される。表示される最も高い確率を有する選択肢の数は、ユーザーが指定することができる。その後、ユーザーは、入力ユーザーインターフェースを用いて、行先、行先カテゴリ又は行動を選択することができ（１４２）、その後、選択された行先への移動中に、経路指定情報又は軌道１４３を生成することができる。
【００１７】
理論的正当化
本発明は、移動者がその行先順序、例えば、
自宅→飲料／軽食→仕事→商店→自宅
に関して規則性を示すという直観に基づく。
【００１８】
本発明の実施形態は、入力として、以前の行先、行先カテゴリ、及び時刻、曜日、行程の状況、移動の方向等の、現在の軌道及び過去の軌道から導出される特徴を取り込む。予測は、行先及び行先カテゴリ、並びに最終到着地を表す変数を用いる推測作業として処理される。到着地のみが観測されるとき、トレーニングアルゴリズムは、行先及び行先カテゴリを隠れ変数として推測することができる。
【００１９】
簡略化されたモデル
一対の確率変数｛ｘ，ｓ｝において、ｘは特徴ベクトルを表し、ｓは場所、例えば、経路及び緯度、例えば、行程の１つの区間の終点を表す。
【００２０】
特徴ベクトルｘ＝［ｘ１，．．．，ｘＦ］は、軌道識別情報（ＩＤ：ｉｄｅｎｔｉｆｉｃａｔｉｏｎ）、軌道ごとの区間ＩＤ、区間ごとの点ＩＤ、高度、時刻、速度及び方向、そしておそらくそれらの統計データ、例えば、平均値、平均、偏差等、まとめて移動の状態を含む。
【００２１】
本発明者らは、行先ｄの多項カテゴリ（又はジャンル）ｚ∈［１，．．．，Ｃ］を推測する。多項カテゴリは、行先データベースからの取り得る行先、すなわち、ユーザーから得られた「好みの」行先に指標を付ける多項式である。
【００２２】
本発明者らは、これを多項ロジスティック回帰モデルとして定式化する。
【数１】
2016536597.tif 000003
ただし、Λ＝［λ１，．．．，λＣ］Ｔであり、λは重みであり、
【数２】
2016536597.tif 000004
であり、φ（ｘ）は本発明の入力特徴ｘのベクトル値関数である。推測のタイプによるが、多項ロジスティック回帰に類似であるが、サンプリングに基づく方法の場合により好都合な場合がある多項プロビット回帰モデルを用いることもできる。
【００２３】
本発明者らの直観は、ユーザーがより高い確率を有するカテゴリｃを選択した後に、ユーザーは、そのカテゴリからの行先ｄを選択する可能性が最も高いと仮定する。
【数３】
2016536597.tif 000005
ただし、「ｃａｔ」は行先ｄで特定された１組のカテゴリである。これは、カテゴリｃと一致する行先にわたって一様な多項式である。
【００２４】
ユーザーが選択されたｄ付近の場所ｓにおいて車両を駐車すると仮定する。これは以下のようにモデル化することができる。
【数４】
2016536597.tif 000006
ただし、Σ＝σ２Ｉ２であり、σは、人がその行先から離れて駐車する距離の標準偏差であり、ｌｏｃ（ｄ）＝［ｄｌａｔ，ｄｌｏｎ］Ｔは、対象点ｄの場所（緯度及び経度）である。
【００２５】
モデルトレーニング
そのようなモデル１６０をトレーニングするために（１５５）、例えば、対ｘｉ、ｓｉを考える。ただし、ｘｉは区間の中央にある。トレーニングする目的関数は以下の通りである。
【数５】
2016536597.tif 000007
ただし、ｐ（ｚ｜ｄ）及び／又はｐ（ｓ｜ｄ）は１組の行先以外では、０であるか、又は相対的に小さいので、本発明者らは１組の行先のみ総和する。
【数６】
2016536597.tif 000008
【００２６】
正規化手法
ロジスティック回帰は、Ｌ１及び／又はＬ２を何らかの形で正規化することによって利益を得る。それらの特徴を低次元の部分空間に変換することによって、一般化性能を改善することもできる。
【００２７】
変換モデルは以下の通りである。
【数７】
2016536597.tif 000009
ただし、Ａは、全てのクラス及び全てのユーザーの場合に共有される（Ｒ×Ｆ）行列である。一般に、次元削減を実行するために、Ｒ＜Ｆである。
【００２８】
目的関数として、そのモデルは以下の通りである。
【数８】
2016536597.tif 000010
【００２９】
目的関数が以下のようになるように、Ｌ１及びＬ２正規化を追加する。
【数９】
2016536597.tif 000011
ただし、α＝０．５及びβ＝０．５がモデルのパラメーターを正規化するのに最適である。正規化項をＡに追加しない。
【００３０】
カテゴリ予測のためのプロビットモデル
ロジスティック回帰を用いてｐ（ｚ｜ｘ）をモデル化する代わりに、本発明者らは、プロビット回帰を用いることが有用であることがわかっており、プロビット回帰は、発生モデルの視点から、より容易に取り扱うことができる。本発明者らは、データｘとの回帰を計算する補助変数Ｙ∈ＲＣ×Ｎと、パラメーター（回帰変数）ｗ∈ＲＣ×Ｎとを用いる。その後、従来の雑音モデルε：Ｎ（０，１）の結果として、ｙｃｉ＝ｗｃφ（ｘｉ）＋εが生じ、ただし、ｗｃはクラスｃ回帰変数の１×Ｎ行ベクトルであり、φ（ｘｉ）は第ｉの要素の場合の内積のＮ×１列ベクトルであり、その結果、以下のガウス確率分布が生じる。
【数１０】
2016536597.tif 000012
【００３１】
補助変数ｙｃｉから対象とする離散目標カテゴリｚｉ∈１，．．．，Ｃへのつながりは、
【数１１】
2016536597.tif 000013
であり、ｐ（ｚｉ＝ｊ｜ｙｉ）がデルタ関数である場合に、以下の周辺化
【数１２】
2016536597.tif 000014
によって、結果として、多項プロビット尤度が生成される。
【数１３】
2016536597.tif 000015
ただし、Ｅは従来の正規分布
【数１４】
2016536597.tif 000016
に関して得られた期待値であり、Φは正規累積密度関数である。
【００３２】
カテゴリ予測モデル
【数１５】
2016536597.tif 000017
を有することを思い起こされたい。ただし、ｘｉ∈ＲＤはＤ次元特徴ベクトルであり、ｓｉは終点の場所である。本発明者らは、時刻ｉごとにカテゴリを予測したい。カテゴリごとに、線形分類器又は非線形分類器を構成することができる。線形の場合、φ（ｘｉ）＝ｘｉであり、非線形の場合、φ（ｘｉ）＝［Ｋ（ｘｉ，ｘ１），Ｋ（ｘｉ，ｘ２），．．．，Ｋ（ｘｉ，ｘＮ）］であり、ただし、Ｋ（．，．）はカーネル関数である。
【００３３】
回帰変数ｗｉｃは、平均が０で、分散が
【数１６】
2016536597.tif 000018
である従来の正規分布に従う。ただし、αｉｃは、ハイパーパラメーターτ、νを有するガンマ分布に従う。τ、νを十分に小さい値、例えば、（＜１０−５）になるように設定することによって、回帰変数ｗｎｃのごく一部のみが０以外の値になり、結果として疎らになる。
【００３４】
カテゴリｃごとに、行先
【数１７】
2016536597.tif 000019
に関する唯一の分布μｃが存在するものと仮定する。ただし、Ｌｃは推測される行先１５３であり、そのカテゴリはｃを含み、
【数１８】
2016536597.tif 000020
はｎで指標を付された行先を表す。
【００３５】
最終的な行先ｄｉのモデルは、多項ディリクレ（Ｄｉｒ）分布から得られる。人が車両を行先付近に駐車すると仮定して、選択された行先の場所の平均がｄｉ、分散がσ２Ｉ２であるガウス分布を用いてｓｉをモデル化し、σ２は固定することができるか、又はガンマ事前確率を更に課すことができる。
【００３６】
図２は、本明細書において説明され、以下のように要約されるような変数を有する本発明のモデルを図式的に示す。
【数１９】
2016536597.tif 000021
【００３７】
カテゴリ化された行先ごとのパラメーターをユーザープリファレンスとして学習することもできる。しかしながら、これは、学習するために、更に多くのトレーニングデータを取り込む場合がある。この場合、これを更に制約するように、カテゴリ化された行先についての情報の階層を含む必要がある。例えば、「ジャンル」ｇ及び「名称」又は「ブランド」ｂ（例えば、「スターバックス」対「ダンキンドーナツ」）と、実際の行先ｄ、例えば、特定の住所にある特定の「スターバックス」とを有することができる。これらをツリー構造：ｃ→ｇ→ｂ→ｄとして定式化することができ、その関係は決定論的である。ｂ∈ｂｒａｎｄ（ｄ）、ｇ∈ｇｅｎｒｅ（ｂ）、ｃ∈ｃａｔ（ｇ）。
【００３８】
各アイテムに関連付けられる２つ以上のタグが存在する場合に、これらを１組として定式化するが、一般的には、ツリー内の各アイテムは単一の親を有する。このようにして、ジャンル及びブランド名に関するユーザープリファレンスを含むことができ、実際の場所ｄのレベルにおいてパラメーターを学習する必要はない。
【数２０】
2016536597.tif 000022
【００３９】
また、他のユーザーデータを含むこともできるので、これらの確率を制約するために、グローバル事前確率
【数２１】
2016536597.tif 000023
を定式化することができる。
【００４０】
場所予測
ユーザーが以前の場所から移動することになる次の場所を予測したい場合には、推測が複雑になるのを緩和するために、場所をクラスタ化することを考えることができる。本発明者らは、離散的な１組のクラスタ化された領域ｒ∈Ｒを用いる。Ｎグラム（Ｎ−ｇｒａｍ）に基づくマルコフモデルｐ（ｒｉ｜ｒｉ−１，ｒｉ−２，．．．，ｒｉ−ｎ＋１）を用いて所与の以前の領域から現在の領域ｒｔを推測することができる。ただし、ｎはマルコフモデルの次数であり、Ｎグラムは一連の領域ｒｉ、ｒｉ−１、ｒｉ−２、．．．、ｒｉ−ｎ＋１である。Ｎグラムモデルは、見えないＮグラムに関する確率を与えるように平滑化することができる。
【００４１】
また、ユーザーが近くの領域に移動するモデルも考えることができる。
【数２２】
2016536597.tif 000024
【００４２】
また、ユーザーが近くの場所に移動するか否かを示す補助確率変数оｉによって、又は上記のマルコフ動態によって、これらを合成することも考えることができる。
【数２３】
2016536597.tif 000025
【００４３】
事前確率ｐ（оｉ）を用いてこれを合成し、ｒｉが観測されると仮定すると、
【数２４】
2016536597.tif 000026
を学習するために、目的関数を最適化することができる。
【数２５】
2016536597.tif 000027
【００４４】
２つの成分間の冗長性に起因して、ｐ（оｉ）をうまく学習できない場合があり、相互検証を用いてそれを設定した方がよい場合があるか、又はディリクレ事前確率を課して一様分布を容易にした方がよい場合がある。
【００４５】
領域予測のための弁別モデル
領域予測のためのＮグラムモデルにおいて、時刻等の他のコンテキスト特徴を合成することは難しい場合がある。代替形態として、上記のロジスティック回帰又はプロビット回帰モデルのような分類器に基づく手法を用いることができる。この場合、ｐ（ｚｉ｜ｘｉ）と同じようにして、ｐ（ｒｉ｜ｘｉ）を定義することができる。この場合の特徴ｘｉは、カテゴリ予測のために用いられる任意の他の特徴に加えて、以前の行先ｒｉ−１、ｒｉ−２、．．．、ｒｉ−ｎ＋１を表す特徴を含む。
【００４６】
行先カテゴリ選択のための場所依存性
また、予測される領域ｒと、予測されるカテゴリｚと、行先ｄとの間の依存性をモデル化することもできる。領域予測及びカテゴリ予測は、以下のような行先尤度を通して合成することができる。
【数２６】
2016536597.tif 000028
【００４７】
行先データベース依存性
２つ以上の行先データベース１５０を有することができ、データベースはユーザー行先を判断する際に異なる重要度を有することができる。詳細には、ユーザーは、一群の「好みの」行先を有することができる。ここでは、これらを、汎用データベースからの事前確率より高い事前確率を有する行先のデータベースとして扱う。それゆえ、行程区間ｉにわたって行先を予測するためにユーザーによって選択されたデータベースを示す多項確率変数ｆ１：Ｍｕｌｔ（λ）を使用する。行先データベースの選択を実施するために、集合Ｌｃ，ｋを、そのカテゴリがｃを含むデータベースｋからの行先のライブラリと定義する。その際、
【数２７】
2016536597.tif 000029
である。ただし、
【数２８】
2016536597.tif 000030
はｎで指標を付された行先を表す。
【００４８】
データはモデルに従って分布するものと仮定する。
●行先指標確率λ：Ｄｉｒｉｃｈｌｅｔ（η）
●分散パラメーターσ２：ＩｎｖｅｒｓｅＧａｍｍａ（ｃ０，ｄ０）
●行先確率μｃ：Ｄｉｒｉｃｈｌｅｔ（γ）
●回帰変数
【数２９】
2016536597.tif 000031
●点ｉ＝１，．．．，Ｎごとの
−行先データベース指標ｆｉ：Ｍｕｌｔｉｎｏｍｉｎａｌ（λ）
−潜在変数
【数３０】
2016536597.tif 000032
−ｙｉｃ＞ｙｉｊ，∀ｃ≠ｊである場合には、指標ｚｉ＝ｃ
−行先
【数３１】
2016536597.tif 000033
−駐車場所ｓｉ：Ｎ（ｌｏｃ（ｄｉ），σ２Ｉ２）
【００４９】
図３は、本明細書において定義されるような変数を有する行先データベース依存性を用いる行先カテゴリ予測モデルを示す。
【００５０】
教師なし領域モデリング
上記のモデルにおいて、領域が、地理的空間をタイル張りすることによって、又はユーザーが頻繁に移動する行先及び／又は場所をクラスタ化することによって導出された所定の場所として扱われる。行先地にわたる空間分布を領域モデルとして考えることは、妥当な拡張である。この場合、領域の場所は、教師なしのモデルの状況において学習することができる。
【００５１】
軌道モデル化
上記のモデルにおいて、場所予測が領域履歴に基づく。また、予測は、移動方向、道路区間、経路に沿った距離、現在の経路及び地図情報を所与とした際の行先へのナビゲーションの容易さ、交通情報を含む地理的特徴に基づくこともできる。そのようなモデル化は、新たな場所への予測及び一般化を改善する本方法の妥当な拡張である。
【図１】
2016536597.tif 000034
【図２】
2016536597.tif 000035
【図３】
2016536597.tif 000036
【国際調査報告】
2016536597.tif 000037
2016536597.tif 000038