(57)【要約】【課題】ＯＤトラヒックデータと相関を持つ外部情報を与えたときのＯＤトラヒックデータを精度よく予測することができる。【解決手段】操作部１０が、各時期のＯＤトラヒックデータと、外部情報とを受け付ける。パラメータ推定部１６が、各時期に対し、ＯＤトラヒックデータを表すデータテンソルを、時期のコアテンソルと、複数の因子行列との積に分解し、時期における各時間帯の外部情報を表す行列を、スケールパラメータと、複数の因子行列との積に分解し、場所に関する外部情報を表す行列を、スケールパラメータと、複数の因子行列との積に分解する。予測部２２が、パラメータ推定部１６によって得られた、各時期のコアテンソルと、複数の因子行列とに基づいて、予測対象の時期及び時間帯のＯＤトラヒックデータを予測する。【選択図】図３
2018195244.tif 000002
【特許請求の範囲】
【請求項１】
各時期における各時間帯のＯＤ（Origin-Destination）トラヒックデータと、前記ＯＤトラヒックデータと相関がある、各時期における各時間帯の外部情報、及び場所に関する外部情報とを受け付ける操作部と、
各時期に対し、前記操作部により受け付けた前記時期における各時間帯の前記ＯＤトラヒックデータを表すデータテンソルを、前記時期のコアテンソルと、時間帯に関する因子行列、及び場所に関する因子行列を含む複数の因子行列との積に分解し、
前記時期における各時間帯の外部情報を表すテンソル又は行列を、前記時間帯の外部情報に対するスケールパラメータと、前記複数の因子行列のうちの、時間帯に関する因子行列を含む複数の因子行列との積に分解し、
前記場所に関する外部情報を表すテンソル又は行列を、前記場所に関する外部情報に対するスケールパラメータと、前記複数の因子行列のうちの、場所に関する因子行列を含む複数の因子行列との積に分解するパラメータ推定部と、
前記パラメータ推定部によって得られた、各時期のコアテンソルと、前記時間帯に関する因子行列、及び前記場所に関する因子行列を含む前記複数の因子行列とに基づいて、予測対象の時期及び時間帯のＯＤトラヒックデータを予測する予測部と、
を含むＯＤトラヒック予測装置。
【請求項２】
前記パラメータ推定部は、各時期のコアテンソルから得られる、時間発展に関するパラメータを更に推定し、
前記予測部は、前記時間発展に関するパラメータを用いて、予測対象の時期及び時間帯のＯＤトラヒックデータを予測する請求項１記載のＯＤトラヒック予測装置。
【請求項３】
前記パラメータ推定部は、前記データテンソルを分解した結果及び前記外部情報を表すテンソル又は行列を分解した結果から計算される、各時期における各時間帯の前記ＯＤトラヒックデータ、各時期における各時間帯の外部情報、及び場所に関する外部情報のモデル値の尤度を最適化するように、各時期のコアテンソルと、前記時間帯に関する因子行列、及び前記場所に関する因子行列を含む前記複数の因子行列と、前記時間帯の外部情報に対するスケールパラメータと、前記場所に関する外部情報に対するスケールパラメータとを更新することを繰り返す請求項１又は２記載のＯＤトラヒック予測装置。
【請求項４】
操作部が、各時期における各時間帯のＯＤ（Origin-Destination）トラヒックデータと、前記ＯＤトラヒックデータと相関がある、各時期における各時間帯の外部情報、及び場所に関する外部情報とを受け付け、
パラメータ推定部が、各時期に対し、前記操作部により受け付けた前記時期における各時間帯の前記ＯＤトラヒックデータを表すデータテンソルを、前記時期のコアテンソルと、時間帯に関する因子行列、及び場所に関する因子行列を含む複数の因子行列との積に分解し、
前記時期における各時間帯の外部情報を表すテンソル又は行列を、前記時間帯の外部情報に対するスケールパラメータと、前記複数の因子行列のうちの、時間帯に関する因子行列を含む複数の因子行列との積に分解し、
前記場所に関する外部情報を表すテンソル又は行列を、前記場所に関する外部情報に対するスケールパラメータと、前記複数の因子行列のうちの、場所に関する因子行列を含む複数の因子行列との積に分解し、
予測部が、前記パラメータ推定部によって得られた、各時期のコアテンソルと、前記時間帯に関する因子行列、及び前記場所に関する因子行列を含む前記複数の因子行列とに基づいて、予測対象の時期及び時間帯のＯＤトラヒックデータを予測する
ＯＤトラヒック予測方法。
【請求項５】
前記パラメータ推定部が推定することでは、各時期のコアテンソルから得られる、時間発展に関するパラメータを更に推定し、
前記予測部が予測することでは、前記時間発展に関するパラメータを用いて、予測対象の時期及び時間帯のＯＤトラヒックデータを予測する請求項４記載のＯＤトラヒック予測方法。
【請求項６】
前記パラメータ推定部が推定することでは、前記データテンソルを分解した結果及び前記外部情報を表すテンソル又は行列を分解した結果から計算される、各時期における各時間帯の前記ＯＤトラヒックデータ、各時期における各時間帯の外部情報、及び場所に関する外部情報のモデル値の尤度を最適化するように、各時期のコアテンソルと、前記時間帯に関する因子行列、及び前記場所に関する因子行列を含む前記複数の因子行列と、前記時間帯の外部情報に対するスケールパラメータと、前記場所に関する外部情報に対するスケールパラメータとを更新することを繰り返す請求項４又は５記載のＯＤトラヒック予測方法。
【請求項７】
コンピュータを、請求項１〜請求項３の何れか１項記載のＯＤトラヒック予測装置を構成する各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ＯＤトラヒックデータを予測するためのＯＤトラヒック予測装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
ODトラヒックはOrigin(起点)からDestination(終点)に向けたヒト・モノ・情報などの流量であり、例えば地域(都市、駅等)間の交通量や交易量にあたる。
【０００３】
ODトラヒックは機械学習の文脈において「関係データ」として扱われる。関係データは複数のオブジェクトあるいは複数種類のデータの間に定義される「関係」を表すデータであり、「グラフ」を用いて表すことができる（図９（Ａ）参照）。グラフG={V,E}は頂点の集合
2018195244.tif 000003
と2つの頂点の組に対応する辺の集合
2018195244.tif 000004
で定義される。ODトラヒックデータの場合、頂点が各地域、辺が2つの地域間の交通量に対応する。機械学習の文献においては、通常このようなグラフ構造を持つデータを、多次元配列を用いて記述する。まずノードを表すインデックスとしてi, jを導入する。i番目のノードとj番目のノードの関係をxijと書く。iを行インデックス、jを列インデックスと見なせばxijの集合を1つの行列Xで表すことができる（図９（Ｂ）参照）。例えばN個の地域間の交通量データはN×Nの行列で表現できる。観測された他のデータから未観測のxijを推定する問題は「リンク予測」と呼ばれる。
【０００４】
ODトラヒックは時間帯によって変化する。例えば朝夕のラッシュ時には移動が多く、真夜中は少ないということが考えられる。時間とともに変化するグラフを記述する際には、テンソルが用いられる。時間帯の個数をTとすると、時間情報を付加したデータはN×N×Tの3階のテンソル
2018195244.tif 000005
で表される（図１０参照）。
2018195244.tif 000006
の各要素xijt=は、「地域iからjに時間帯tに移動した人の数」である。また、時間帯に加え曜日も考慮する場合には、N×N×T×7の4階のテンソル
2018195244.tif 000007
でデータを表現する（図１１（Ａ）参照）。この場合
2018195244.tif 000008
の各要素x′ijdt=は、「地域iからjに曜日d、時間帯tに移動した人の数」である。このようにテンソルの次元を増やしていくことで3次以上の多項関係を表すことができる（図１１（Ｂ）参照）。テンソルで表されるデータの解析には、CP分解やTucker分解等のテンソル分解が用いられる。テンソル分解はデータテンソルを行列の積の形に分解するもので、データの低次元表現を与える（図１２参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】DUNLAVY, Daniel M.; KOLDA, Tamara G.; ACAR, Evrim. Temporal link  prediction using matrix and tensor factorizations. ACM Transactions on Knowledge Discovery from Data (TKDD), 2011, 5.2: 10.
【非特許文献２】ERMI, Beyza; ACAR, Evrim; CEMGIL, A. Taylan.  Link prediction via generalized cou-pled tensor factorisation. arXiv preprint arXiv:1208.6231, 2012.
【非特許文献３】NOMIKOS, Paul; MACGREGOR, John F. Multi-way partial least squares in monitoring  batch processes. Chemometrics and intelligent laboratory systems, 1995, 30.1: 97-108.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来のテンソル分解では、自己回帰性(前の時刻の値と今の時刻の値の関係)を考慮しないため、時間とともに発展するグラフのモデル化には適さない。例えば、バイクシェアシステムにおけるODトラヒック(始点バイクステーションと終点バイクステーション間のトリップ数)は、バイクシェアシステムの広がりに伴って時間とともに増加している。このようなODトラヒックデータに対しては、時間発展を考慮したモデル化が必要である。 また、基本的なテンソル分解手法はそのままでは外的要因に関する情報(外部情報)を扱うことができない。バイクシェアシステムのトリップ数、地域間の移動人数等のODトラヒックは天候や周囲のイベント等の外的要因によって変動すると考えられる。グラフの時間発展を記述するモデルは複数存在するが（非特許文献１参照）、これらのモデルはこのままでは外部情報を取り入れることができない。外部情報を考慮するための手法として、補助情報付きテンソル分解（非特許文献2）や外部情報を回帰変数として用いる手法（非特許文献3）が提案されている。しかしこれらのモデルは時間発展を考慮することができない。
【０００７】
このように、従来手法では、時間発展と外部情報を同時に考慮することができない。そのため外的要因の影響が大きく、かつ時間とともに発展するグラフを適切にモデル化することができず、リンク予測の精度が下がるという問題が存在した。
【０００８】
本発明は、上記の事情を鑑みてなされたものであり、ＯＤトラヒックデータと相関を持つ外部情報を与えたときのＯＤトラヒックデータを精度よく予測することができるＯＤトラヒック予測装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成するために、本発明に係るＯＤトラヒック予測装置は、各時期における各時間帯のＯＤ（Origin-Destination）トラヒックデータと、前記ＯＤトラヒックデータと相関がある、各時期における各時間帯の外部情報、及び場所に関する外部情報とを受け付ける操作部と、各時期に対し、前記操作部により受け付けた前記時期における各時間帯の前記ＯＤトラヒックデータを表すデータテンソルを、前記時期のコアテンソルと、時間帯に関する因子行列、及び場所に関する因子行列を含む複数の因子行列との積に分解し、前記時期における各時間帯の外部情報を表すテンソル又は行列を、前記時間帯の外部情報に対するスケールパラメータと、前記複数の因子行列のうちの、時間帯に関する因子行列を含む複数の因子行列との積に分解し、前記場所に関する外部情報を表すテンソル又は行列を、前記場所に関する外部情報に対するスケールパラメータと、前記複数の因子行列のうちの、場所に関する因子行列を含む複数の因子行列との積に分解するパラメータ推定部と、前記パラメータ推定部によって得られた、各時期のコアテンソルと、前記時間帯に関する因子行列、及び前記場所に関する因子行列を含む前記複数の因子行列とに基づいて、予測対象の時期及び時間帯のＯＤトラヒックデータを予測する予測部と、を含んで構成されている。
【００１０】
また、本発明に係るＯＤトラヒック予測方法は、操作部が、各時期における各時間帯のＯＤ（Origin-Destination）トラヒックデータと、前記ＯＤトラヒックデータと相関がある、各時期における各時間帯の外部情報、及び場所に関する外部情報とを受け付け、パラメータ推定部が、各時期に対し、前記操作部により受け付けた前記時期における各時間帯の前記ＯＤトラヒックデータを表すデータテンソルを、前記時期のコアテンソルと、時間帯に関する因子行列、及び場所に関する因子行列を含む複数の因子行列との積に分解し、前記時期における各時間帯の外部情報を表すテンソル又は行列を、前記時間帯の外部情報に対するスケールパラメータと、前記複数の因子行列のうちの、時間帯に関する因子行列を含む複数の因子行列との積に分解し、前記場所に関する外部情報を表すテンソル又は行列を、前記場所に関する外部情報に対するスケールパラメータと、前記複数の因子行列のうちの、場所に関する因子行列を含む複数の因子行列との積に分解し、予測部が、前記パラメータ推定部によって得られた、各時期のコアテンソルと、前記時間帯に関する因子行列、及び前記場所に関する因子行列を含む前記複数の因子行列とに基づいて、予測対象の時期及び時間帯のＯＤトラヒックデータを予測する。
【００１１】
また、本発明のプログラムは、コンピュータを、上記のＯＤトラヒック予測装置を構成する各部として機能させるためのプログラムである。
【発明の効果】
【００１２】
以上説明したように、本発明のＯＤトラヒック予測装置、方法、及びプログラムによれば、各時期に対し、前記時期における各時間帯の前記ＯＤトラヒックデータを表すデータテンソルを、前記時期のコアテンソルと、複数の因子行列との積に分解し、前記時期における各時間帯の外部情報を表すテンソル又は行列を、前記時間帯の外部情報に対するスケールパラメータと、時間帯に関する因子行列を含む複数の因子行列との積に分解し、前記場所に関する外部情報を表すテンソル又は行列を、前記場所に関する外部情報に対するスケールパラメータと、場所に関する因子行列を含む複数の因子行列との積に分解し、各時期のコアテンソルと、前記時間帯に関する因子行列、及び前記場所に関する因子行列を含む前記複数の因子行列とに基づいて、予測対象の時期及び時間帯のＯＤトラヒックデータを予測することにより、ＯＤトラヒックデータと相関を持つ外部情報を与えたときのＯＤトラヒックデータを精度よく予測することができる、という効果が得られる。
【図面の簡単な説明】
【００１３】
【図１】時間発展を導入して拡張したテンソル同時分解を説明するための図である。
【図２】コアテンソルの時間発展を説明するための図である。
【図３】本発明の実施の形態におけるＯＤトラヒック予測装置のブロック図である。
【図４】ＯＤトラヒック履歴の一例を示す図である。
【図５】外部情報の一例を示す図である。
【図６】パラメータ学習のアルゴリズムを示す図である。
【図７】本発明の実施の形態におけるＯＤトラヒック予測装置の学習処理ルーチンを示すフローチャートである。
【図８】本発明の実施の形態におけるＯＤトラヒック予測装置のＯＤトラヒック予測処理ルーチンを示すフローチャートである。
【図９】（Ａ）ＯＤフローのグラフ表現を示す図、及び（Ｂ）ＯＤフロー行列を示す図である。
【図１０】ＯＤフローのテンソル表現を示す図である。
【図１１】ＯＤフローのテンソル表現のバリエーションを示す図である。
【図１２】テンソル分解を説明するための図である。
【発明を実施するための形態】
【００１４】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００１５】
＜概要＞
本発明の実施の形態では、テンソルの同時分解手法に自己回帰を導入することで外的要因の影響と時間発展を同時に扱う技術を用いる。テンソル同時分解手法は、データを表すテンソル(データテンソル)と外部情報を表すテンソル(あるいは行列)を、因子行列を共有させつつ同時に分解するもので、データと外部情報の間接的な関係を捉えることができる（図１参照）。その際、データテンソルはコアテンソルと呼ばれる小さなテンソルと複数の因子行列の積で近似される。
【００１６】
本発明の実施の形態では、コアテンソルの自己回帰性を仮定する。具体的には、ある時刻におけるコアテンソルが次の時間ステップで別のコアテンソルに遷移する確率をモデル化しデータから学習する（図２参照）。
【００１７】
そのため外的要因の影響が大きく、かつ時間とともに発展するODトラヒックデータに対し、高精度な予測が可能になる。また、周期性の時間発展をモデル化することで、比較的長期の予測ができる。
【００１８】
以下では、OD(Origin-Destination)トラヒックの履歴であるＯＤトラヒックデータと、ＯＤトラヒックデータと相関を持つ外部情報とに基づき近未来のODトラヒックを予測する場合について説明する。
【００１９】
＜本発明の実施の形態に係るＯＤトラヒック予測装置の構成＞
次に、本発明の実施の形態に係るＯＤトラヒック予測装置の構成について説明する。図３に示すように、本発明の実施の形態に係るＯＤトラヒック予測装置１００は、ＣＰＵと、ＲＡＭと、後述する各処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。ＯＤトラヒック予測装置１００は、各時期における各時間帯のＯＤ（Origin-Destination）トラヒックデータと、ＯＤトラヒックデータと相関がある、各時期における各時間帯の外部情報、及び場所に関する外部情報とに基づいて、予測対象の時期、時間帯、及び場所のＯＤトラヒックを予測する。このＯＤトラヒック予測装置１００は、機能的には図３に示すように、操作部１０と、ＯＤ履歴格納部１２と、外部情報格納部１４と、パラメータ推定部１６と、パラメータ格納部１８と、検索部２０と、予測部２２と、出力部２４とを備えている。
【００２０】
操作部１０は、後述するＯＤ履歴格納部１２及び外部情報格納部１４に格納されているデータに対するユーザからの各種操作を受け付ける。各種操作とは、ＯＤ履歴格納部１２及び外部情報格納部１４に格納された情報を登録、修正、削除する操作等である。
【００２１】
操作部１０の入力手段は、キーボードやマウス、メニュー画面、タッチパネルによるもの等、何でもよい。操作部１０は、マウス等の入力手段のデバイスドライバーや、メニュー画面の制御ソフトウェアで実現され得る。
【００２２】
検索部２０は、予測対象となる時期（週）と曜日と時間帯と場所と時間差の情報を受け付ける。検索部２０の入力手段は、キーボードやマウスやメニュー画面やタッチパネルによるもの等、何でも良い。検索部２０は、マウス等の入力手段のデバイスドライバーや、メニュー画面の制御ソフトウェアで実現され得る。
【００２３】
ＯＤ履歴格納部１２は、装置により解析され得るODトラヒックの履歴情報を格納しており、パラメータ推定部１６からの要求に従って、ODトラヒック履歴情報を読み出し、当該情報をパラメータ推定部１６に送信する。 ODトラヒック履歴情報は、例えば、地域間の人の遷移数であり、「人が(1)何日(2)何曜日の(3)何時に(4)どこから(5)どこへ(6)どれぐらいの時間差をもって(7)どれだけ移動したか」という情報からなるデータである（図４参照）。 このようなデータは、(2)曜日d、(3)時間帯t、 (4)始点場所ID i、(5)終点場所ID j、(6)時間差lに対応する5つの軸からなるテンソルで表現できる。テンソルの各成分をyi,j,l,d,tとおく。複数週間分のデータが存在する場合、第w週目のデータ集合をYwと定義する。Ywはywi,j,l,d,tの集合
2018195244.tif 000009
である。ここでywi,j,l,d,tは第w週目、d番目の曜日、時間帯tに場所iからjに時間差lをもって移動した人の数である。Dは曜日の数、Tは時間帯の数、Nは場所の数、Lは考慮する時間差の数を表す。週の数をWとするとデータ全体の集合は
2018195244.tif 000010
である。なお、OD履歴格納部１２をＯＤトラヒック予測装置１００の外部に設け、Webページを保持するWeb サーバや、データベースを具備するデータベースサーバ等で構成してもよい。
【００２４】
外部情報格納部１４には、装置により解析され得る外部情報を格納しており、パラメータ推定部１６からの要求に従って、外部情報を読み出し、当該情報をパラメータ推定部１６に送信する。外部情報はODトラヒックに影響を与える外的要因に関するデータであり、例えば天気(気温、 降水量)や地理情報(地域ペア間の地理的な距離)等が考えられる。 例として、各週・曜日・時間帯ごとの気温（図５参照）と各週・曜日・時間帯ごとの降水量、地域間の地理的距離の情報を持っている状況を考える。第w週目の曜日d、時間帯tの気温をpwdt、第w週目の曜日d、時間帯tの降水量をqwdt、場所iとjの地理的距離をzwi,jとおく。要素pwdtの集合
2018195244.tif 000011
からなる行列をPw、要素qwdtの集合
2018195244.tif 000012
からなる行列をQw, 要素zwijの集合
2018195244.tif 000013
からなる行列をZwとおく。各行列の集合をそれぞれ
2018195244.tif 000014
と書く。ここで、場所iとjの地理的距離zwi,jが、各週において変化しない場合には、各週ｗにおいて、場所iとjの地理的距離zwi,jが共通した値となる。なお、外部情報格納部１４をＯＤトラヒック予測装置１００の外部に設け、 Web ページを保持するWebサーバや、データベースを具備するデータベースサーバ等で構成してもよい。
【００２５】
パラメータ推定部１６は、OD履歴格納部１２と外部情報格納部１４に格納されている情報に基づき、これらの情報の低次元表現を抽出し、時間発展を推定する。前述の例を使って手順を説明する。ODトラヒック履歴を表すテンソルにCP分解をかけることを考える。CP分解は、テンソルをコアテンソルと呼ばれる小さなテンソルと因子行列の積で近似する手法である。本実施の形態のゴールは、テンソルを再現するコアテンソルと因子行列の組を見つけることである。ODトラヒックのデータテンソルywi,j,l,d,tは以下のように分解される。
【００２６】
【数１】
2018195244.tif 000015
【００２７】
ここで
2018195244.tif 000016
は因子行列、λwkはコアテンソルの対角成分である。CP分解の場合、コアテンソルは対角成分のみを持つ。KはCP分解のランク数であり、事前の知見に基づいて主導で与えるかクロスバリデーション等で決める。因子行列の要素の集合をそれぞれ
【００２８】
【数２】
2018195244.tif 000017
【００２９】
と書き、コアテンソルの対角成分の集合を
【００３０】
【数３】
2018195244.tif 000018
【００３１】
と書く。同様に、外部情報を表す行列Z、 P、 QをΘ(1), Θ(2), Θ(4), Θ(5)を使って以下のように分解する。
【００３２】
【数４】
2018195244.tif 000019
【００３３】
ここでγzk,γpk,γqkはスケールパラメータである。スケールパラメータの集合をそれぞれ
2018195244.tif 000020
とおく。外部情報とODトラヒックデータのスケールの違いはこのパラメータに吸収される。データテンソルYwの因子行列と外部情報行列Pw,Qw,Zwの因子行列を共有させることにより、外部情報を考慮したテンソル分解が可能になる。自己回帰性を考慮するため、コアテンソルが時間と共に発展すると仮定する。本実施の形態では、一例として、今週のコアテンソルの値が先週のコアテンソルの値の線形変換で決まると仮定する。
【００３４】
【数５】
2018195244.tif 000021
【００３５】
また、本モデルの尤度は以下のように書き下せる。
【００３６】
【数６】
2018195244.tif 000022
【００３７】
ここで! は階乗を表す。本実施の形態のゴールは、尤度Lを最小化するようなパラメータの組{Θ(1), Θ(2), Θ(3), Θ(4), Θ(5),Γz,Γp,Γq,Λ}を推定することである。パラメータの最適化にはどんな方法を用いても良いが、更新対象のパラメータ以外を固定して尤度Lを最小化するように更新対象のパラメータを更新することにより各パラメータを交互に更新する方法（例えば、非特許文献4）が広く用いられている。パラメータ学習の手順を図６に示す。
【００３８】
［非特許文献4］：M. Welling and M. Weber. Positive tensor factorization. Pattern Recognition Letters,  22(12):1255-1261, 2001.
【００３９】
推定されたパラメータの組はパラメータ格納部２０に格納される。パラメータ格納部２０は、これらの情報が保存され、復元可能なものであればなんでもよい。例えば、データベースや、予め備えられた汎用的な記憶装置(メモリやハードディスク装置)の特定領域に記憶される。
【００４０】
従って、パラメータ推定部１６は、ＯＤ履歴格納部１２に格納されたＯＤトラヒックデータ、及び外部情報格納部１４に格納された外部情報に基づいて、各週ｗに対し、当該週ｗにおける各時間帯ｔのＯＤトラヒックデータを表すデータテンソルＹwtを、当該週ｗのコアテンソルλwkと、場所に関する因子行列θ(1)ik、θ(2)jk、θ(3)lkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkとの積に分解し、当該週ｗにおける各時間帯の外部情報を表す行列Ｐを、外部情報に対するスケールパラメータγpkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkとの積に分解し、当該週ｗにおける各時間帯の外部情報を表す行列Ｑを、外部情報に対するスケールパラメータγqkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkとの積に分解し、場所に関する外部情報Ｚを、場所に関する外部情報に対するスケールパラメータγzkと、場所に関する因子行列θ(1)ik、θ(2)jkとの積に分解する。
【００４１】
具体的には、データテンソルを分解した結果及び外部情報を表す行列を分解した結果から計算される、各週ｗにおける各時間帯のＯＤトラヒックデータ、各週ｗにおける各時間帯の外部情報、及び場所に関する外部情報の各々のモデル値
2018195244.tif 000023
の尤度を最適化するように、各週ｗのコアテンソルλwkと、場所に関する因子行列θ(1)ik、θ(2)jk、θ(3)lkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkと、外部情報に対するスケールパラメータγpk、γqkと、場所に関する外部情報に対するスケールパラメータγzkとを更新することを繰り返す。
【００４２】
また、パラメータ推定部１６は、各週ｗのコアテンソルλwkから得られる、時間発展に関するパラメータαkを更に推定する。
【００４３】
予測部２２は、操作部１０によって受け付けた予測対象の週、曜日、時間帯、場所、及び時間差に関する情報と、パラメータ格納部１８に格納された、各週ｗのコアテンソルλwkと、場所に関する因子行列θ(1)ik、θ(2)jk、θ(3)lkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkと、に基づいて、予測対象の週、曜日、時間帯、場所、及び時間差に関するＯＤトラヒックデータを予測する。このとき、時間発展に関するパラメータαkを用いて、予測対象の時期、時間帯、場所、及び時間差に関するＯＤトラヒックデータを予測する。
【００４４】
例えば前述の例の場合、次の週(第w +1週)の曜日d、時間帯tに場所iからjへ時間差lで移動する人の数は次式で予測できる。
【００４５】
【数７】
2018195244.tif 000024
【００４６】
出力部２４は、予測部２２によって予測されたＯＤトラヒックデータを、結果として出力する。ここで、出力とは、ディスプレイへの表示、プリンタへの印字、音出力、外部装置への送信等を含む概念である。出力部２４は、ディスプレイやスピーカー等の出力デバイスを含むと考えても含まないと考えても良い。出力部２４は、出力デバイスのドライバーソフトまたは、出力デバイスのドライバーソフトと出力デバイス等で実現され得る。
【００４７】
＜本発明の実施の形態に係るＯＤトラヒック予測装置の作用＞
次に、本発明の実施の形態に係るＯＤトラヒック予測装置１００の作用について説明する。
【００４８】
＜学習処理ルーチン＞
まず、ＯＤトラヒック予測装置１００は、操作部１０よりODトラヒック履歴情報が入力されると、ODトラヒック履歴情報をＯＤ履歴格納部１２に格納し、操作部１０により外部情報が入力されると、外部情報を外部情報格納部１４に格納する。そして、ＯＤトラヒック予測装置１００は、図７に示す学習処理ルーチンを実行する。
【００４９】
まず、ステップＳ１００では、各週ｗのコアテンソルλwkと、場所に関する因子行列θ(1)ik、θ(2)jk、θ(3)lkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkと、外部情報に対するスケールパラメータγpk、γqkと、場所に関する外部情報に対するスケールパラメータγzkとを初期化する。
【００５０】
ステップＳ１０２では、場所に関する因子行列θ(1)ik、θ(2)jk、θ(3)lkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkと、外部情報に対するスケールパラメータγpk、γqkと、場所に関する外部情報に対するスケールパラメータγzkとに基づいて、上記（９）式に示す尤度を最小化するように、各週ｗのコアテンソルλwkを更新する。
【００５１】
ステップＳ１０４では、各週ｗのコアテンソルλwkと、外部情報に対するスケールパラメータγpk、γqkと、場所に関する外部情報に対するスケールパラメータγzkとに基づいて、上記（９）式に示す尤度を最小化するように、場所に関する因子行列θ(1)ik、θ(2)jk、θ(3)lkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkとを更新する。
【００５２】
ステップＳ１０５では、各週ｗのコアテンソルλwkと、場所に関する因子行列θ(1)ik、θ(2)jk、θ(3)lkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkと、に基づいて、上記（９）式に示す尤度を最小化するように、外部情報に対するスケールパラメータγpk、γqkと、場所に関する外部情報に対するスケールパラメータγzkとを更新する。
【００５３】
ステップＳ１０６では、予め定められた収束判定条件を満たしたか否かを判定し、収束判定条件を満たしていない場合には、上記ステップＳ１０２へ戻り、一方、収束判定条件を満たした場合には、ステップＳ１０８へ進む。
【００５４】
なお、収束判定条件としては、推定された各パラメータの変化量が閾値以下となることや、予め定めた繰り返し回数に到達したことを用いればよい。
【００５５】
ステップＳ１０８では、上記ステップＳ１０２〜ステップＳ１０５で最終的に更新された各週ｗのコアテンソルλwkと、場所に関する因子行列θ(1)ik、θ(2)jk、θ(3)lkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkと、外部情報に対するスケールパラメータγpk、γqkと、場所に関する外部情報に対するスケールパラメータγzkと、各週ｗのコアテンソルλwkから推定される時間発展に関するパラメータαkとをパラメータ格納部１８に格納して、学習処理ルーチンを終了する。
【００５６】
＜ＯＤトラヒック予測処理ルーチン＞
次に、図８に示すＯＤトラヒック予測処理ルーチンについて説明する。
【００５７】
上記学習処理ルーチンが実行され、パラメータ格納部２０に各週ｗのコアテンソルλwkと、場所に関する因子行列θ(1)ik、θ(2)jk、θ(3)lkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkと、外部情報に対するスケールパラメータγpk、γqkと、場所に関する外部情報に対するスケールパラメータγzkと、時間発展に関するパラメータαkとが格納され、予測対象の週、曜日、時間帯、場所、及び時間差に関する情報が入力されると、ＯＤトラヒック予測装置１００は、図８に示すＯＤトラヒック予測処理ルーチンを実行する。
【００５８】
ステップＳ１１０において、操作部１０は、予測対象の週、曜日、時間帯、場所、及び時間差に関する情報を受け付ける。
【００５９】
ステップＳ１１２において、パラメータ格納部１８に格納された、各週ｗのコアテンソルλwkと、場所に関する因子行列θ(1)ik、θ(2)jk、θ(3)lkと、日に関する因子行列θ(4)dkと、時間帯に関する因子行列θ(5)tkと、時間発展に関するパラメータαkとを読み出す。
【００６０】
ステップＳ１１４において、予測対象の週、曜日、時間帯、場所、及び時間差に関する情報と、上記ステップＳ１１２で読み込まれた各パラメータとに基づいて、上記（１０）式に従って、予測対象の週、時間帯、場所、及び時間差に関するＯＤトラヒックデータを予測する。
【００６１】
ステップＳ１１６において、出力部２４は、上記ステップＳ１１４で予測された予測対象の週、時間帯、場所、及び時間差に関するＯＤトラヒックデータを結果として出力して、ＯＤトラヒック予測処理ルーチンを終了する。
【００６２】
以上説明したように、本発明の実施の形態に係るＯＤトラヒック予測装置によれば、各週ｗに対し、当該週ｗにおける各時間帯のＯＤトラヒックデータを表すデータテンソルを、当該週ｗのコアテンソルと、複数の因子行列との積に分解し、当該週ｗにおける各時間帯の外部情報を表す行列を、時間帯の外部情報に対するスケールパラメータと、時間帯に関する因子行列を含む複数の因子行列との積に分解し、場所に関する外部情報を表す行列を、場所に関する外部情報に対するスケールパラメータと、場所に関する因子行列を含む複数の因子行列との積に分解し、各週ｗのコアテンソルと、時間帯に関する因子行列、及び場所に関する因子行列を含む前記複数の因子行列とに基づいて、予測対象の週、時間帯、及び場所のＯＤトラヒックデータを予測することにより、ＯＤトラヒックデータと相関を持つ外部情報を与えたときのＯＤトラヒックデータを精度よく予測することができる。
【００６３】
なお、本発明は、上述した実施形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００６４】
例えば、上記の実施の形態では、外部情報を表す行列を用いる場合を例に説明したが、これに限定されるものではなく、外部情報を表すテンソルを用いてもよい。
【００６５】
また、上述のＯＤトラヒック予測装置１００は、内部にコンピュータシステムを有しているが、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
【００６６】
また、本願明細書中において、プログラムが予めインストールされている実施形態として説明したが、当該プログラムを、コンピュータ読み取り可能な記録媒体に格納して提供することも可能であるし、ネットワークを介して提供することも可能である。
【符号の説明】
【００６７】
１０   操作部
１２   ＯＤ履歴格納部
１４   外部情報格納部
１６   パラメータ推定部
１８   パラメータ格納部
１８   履歴格納部
２０   検索部
２２   予測部
２４   出力部
１００ ＯＤトラヒック予測装置
【図１】
2018195244.tif 000025
【図２】
2018195244.tif 000026
【図３】
2018195244.tif 000027
【図４】
2018195244.tif 000028
【図５】
2018195244.tif 000029
【図６】
2018195244.tif 000030
【図７】
2018195244.tif 000031
【図８】
2018195244.tif 000032
【図９】
2018195244.tif 000033
【図１０】
2018195244.tif 000034
【図１１】
2018195244.tif 000035
【図１２】
2018195244.tif 000036