(57)【要約】【課題】エリアのサイズに依存することなく、整数値によって移動人数を精度よく推定できる。【解決手段】エリアの各々の各時刻の人口に基づいて、エリアの各々の各時刻の人口、各時刻におけるエリア間の移動人数、及びエリア間の移動確率を用いて表される尤度関数を最大化するように、エリアの各々の各時刻の人口と、各時刻におけるエリア間の移動人数とが予め定められた関係であること、及び各時刻におけるエリア間の移動人数が整数値であることを制約として、各時刻におけるエリア間の移動人数を推定し、推定された各時刻におけるエリア間の移動人数に基づいて、尤度関数を最大化するように、エリア間の移動確率を推定することを予め定められた条件を満たすまで繰り返す。【選択図】図１
2019211918.tif 000002
【特許請求の範囲】
【請求項１】
エリアの各々の各時刻の人口に基づいて、前記エリアの各々の各時刻の人口、前記各時刻におけるエリア間の移動人数、及びエリア間の移動確率を用いて表される尤度関数を最大化するように、前記エリアの各々の各時刻の人口と、前記各時刻におけるエリア間の移動人数とが予め定められた関係であること、及び前記各時刻におけるエリア間の移動人数が整数値であることを制約として、前記各時刻におけるエリア間の移動人数を推定する整数移動人数推定部と、
前記推定された前記各時刻におけるエリア間の移動人数に基づいて、前記尤度関数を最大化するように、前記エリア間の移動確率を推定する移動確率推定部と、
前記整数移動人数推定部、及び移動確率推定部との処理を予め定められた条件を満たすまで繰り返す推定制御部と、
を含む整数移動人数推定装置。
【請求項２】
前記整数移動人数推定部が、前記移動確率推定部によって推定された前記エリア間の移動確率、及び前記尤度関数に基づいて、前記制約を満たす、各時刻におけるエリア間の移動人数をサンプリングする請求項１に記載の整数移動人数推定装置。
【請求項３】
前記整数移動人数推定部が、前記移動確率推定部によって推定された前記エリア間の移動確率を用いたときの前記尤度関数を最大化し、かつ、前記制約を満たす、各時刻におけるエリア間の移動人数を推定する請求項１に記載の整数移動人数推定装置。
【請求項４】
整数移動人数推定部が、エリアの各々の各時刻の人口に基づいて、前記エリアの各々の各時刻の人口、前記各時刻におけるエリア間の移動人数、及びエリア間の移動確率を用いて表される尤度関数を最大化するように、前記エリアの各々の各時刻の人口と、前記各時刻におけるエリア間の移動人数とが予め定められた関係であること、及び前記各時刻におけるエリア間の移動人数が整数値であることを制約として、前記各時刻におけるエリア間の移動人数を推定するステップと、
移動確率推定部が、前記推定された前記各時刻におけるエリア間の移動人数に基づいて、前記尤度関数を最大化するように、前記エリア間の移動確率を推定するステップと、
推定制御部が、前記整数移動人数推定部、及び移動確率推定部との処理を予め定められた条件を満たすまで繰り返すステップと、
を含む整数移動人数推定方法。
【請求項５】
前記整数移動人数推定部が、前記移動確率推定部によって推定された前記エリア間の移動確率、及び前記尤度関数に基づいて、前記制約を満たす、各時刻におけるエリア間の移動人数をサンプリングする請求項４に記載の整数移動人数推定方法。
【請求項６】
前記整数移動人数推定部が、前記移動確率推定部によって推定された前記エリア間の移動確率を用いたときの前記尤度関数を最大化し、かつ、前記制約を満たす、各時刻におけるエリア間の移動人数を推定する請求項４に記載の整数移動人数推定方法。
【請求項７】
コンピュータを、請求項１〜請求項３のいずれか１項に記載の整数移動人数推定装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、整数移動人数推定装置、方法、及びプログラムに係り、特に、各時刻におけるエリア間の移動人数を推定するための整数移動人数推定装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
ＧＰＳなどから得られる人間の位置情報は、プライバシーへの配慮から個人を追跡できないような人口統計情報として提供されることがある。ここで、人口統計情報とは、各タイムステップ（時刻）における、各エリアにいる人数の情報である。エリアとは、例えば地理空間をグリッド状に区切ったものを想定している。このような人口統計情報から、各タイムステップ間の各エリア間の移動確率及び移動人数を推定するニーズが存在する。
【０００３】
従来技術では、集計されたデータから個別の確率モデルを推定する枠組み（Collective Graphical Model）を用いて、各エリア間の移動確率及び移動人数を推定している（非特許文献１、非特許文献２参照）。
【０００４】
この技術においては、時刻ｔから時刻ｔ＋１にかけてエリアｉからエリアｊに移動する人数Ｍｔｉｊと、エリアｉからエリアｊへの移動確率θｉｊから計算される尤度関数Ｌ（Ｍ，θ）を最大化するＭ，θを求めることで推定を行う。尤度関数Ｌ（Ｍ，θ）の最大化は、Ｍ，θに関する交互最適化によって行う。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】D. R. Sheldon and T. G. Dietterich. Collective Graphical Models. In Proceedings of the 24th International Conference on Neural Information Processing Systems, pp. 1161-1169, 2011
【非特許文献２】T. Iwata, H. Shimizu, F. Naya, and N. Ueda. Estimating People Flow from Spatiotemporal Population Data via Collective Graphical Mixture Models. ACM Transactions on Spatial Algorithms and Systems, Vol.3, No.1, pp.1-18,may 2017
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来技術では、交互最適化の１ステップであるＭｔｉｊに関する最大化は、整数変数を連続変数に緩和し、人数保存制約のもとで連続変数に関する最適化方法を用いることによって行われていた。
【０００７】
しかし、このような推定の方法は、推定精度を低下させてしまう可能性がある。その理由は以下の三つの現象によるものである。
【０００８】
第一に、もとの確率モデルは多項分布で定義されているため、移動人数Ｍが整数の場合にしか尤度は意味を持たず、連続緩和した場合の尤度には確率的な意味付けをすることができない。そのため、近似的にしか最尤推定法が行えなくなってしまう、というものである。
【０００９】
第二に、尤度計算の中でスターリングの近似
【００１０】
2019211918.tif 000003
【００１１】
を用いているが、この近似はＭｔｉｊが小さい場合には正確ではない。特に、エリアサイズが小さい場合など移動先候補が多い場合、Ｍｔｉｊの値が小さくなりやすいため近似の精度が悪くなってしまう、というものである。
【００１２】
第三に、移動人数は整数値しかとらない値のはずだが、出力が小数値というありえない値になってしまう。四捨五入を行うなどの方法によって整数値に加工することは可能だが、この場合人数保存制約が大きく崩れてしまう、というものである。
【００１３】
特に、これらの現象はエリアサイズが小さく移動先候補となるエリアが多くなる場合に、より顕著になる。
【００１４】
本発明は、上記問題点を解決するために成されたものであり、エリアのサイズに依存することなく、整数値によって移動人数を精度よく推定できる整数移動人数推定装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１５】
上記目的を達成するために、第１の発明に係る整数移動人数推定装置は、エリアの各々の各時刻の人口に基づいて、前記エリアの各々の各時刻の人口、前記各時刻におけるエリア間の移動人数、及びエリア間の移動確率を用いて表される尤度関数を最大化するように、前記エリアの各々の各時刻の人口と、前記各時刻におけるエリア間の移動人数とが予め定められた関係であること、及び前記各時刻におけるエリア間の移動人数が整数値であることを制約として、前記各時刻におけるエリア間の移動人数を推定する整数移動人数推定部と、前記推定された前記各時刻におけるエリア間の移動人数に基づいて、前記尤度関数を最大化するように、前記エリア間の移動確率を推定する移動確率推定部と、前記整数移動人数推定部、及び移動確率推定部との処理を予め定められた条件を満たすまで繰り返す推定制御部と、を含んで構成されている。
【００１６】
第２の発明に係る整数移動人数推定方法は、整数移動人数推定部が、エリアの各々の各時刻の人口に基づいて、前記エリアの各々の各時刻の人口、前記各時刻におけるエリア間の移動人数、及びエリア間の移動確率を用いて表される尤度関数を最大化するように、前記エリアの各々の各時刻の人口と、前記各時刻におけるエリア間の移動人数とが予め定められた関係であること、及び前記各時刻におけるエリア間の移動人数が整数値であることを制約として、前記各時刻におけるエリア間の移動人数を推定するステップと、移動確率推定部が、前記推定された前記各時刻におけるエリア間の移動人数に基づいて、前記尤度関数を最大化するように、前記エリア間の移動確率を推定するステップと、推定制御部が、前記整数移動人数推定部、及び移動確率推定部との処理を予め定められた条件を満たすまで繰り返すステップと、を含んで実行することを特徴とする。
【００１７】
第３の発明に係るプログラムは、コンピュータを、第１の発明に係る整数移動人数推定装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１８】
本発明の整数移動人数推定装置、方法、及びプログラムによれば、エリアの各々の各時刻の人口に基づいて、エリアの各々の各時刻の人口、各時刻におけるエリア間の移動人数、及びエリア間の移動確率を用いて表される尤度関数を最大化するように、エリアの各々の各時刻の人口と、各時刻におけるエリア間の移動人数とが予め定められた関係であること、及び各時刻におけるエリア間の移動人数が整数値であることを制約として、各時刻におけるエリア間の移動人数を推定し、推定された各時刻におけるエリア間の移動人数に基づいて、尤度関数を最大化するように、エリア間の移動確率を推定することを予め定められた条件を満たすまで繰り返すことにより、エリアのサイズに依存することなく、整数値によって移動人数を精度よく推定できる、という効果が得られる。
【図面の簡単な説明】
【００１９】
【図１】本発明の実施の形態に係る整数移動人数推定装置の構成を示すブロック図である。
【図２】人口統計情報蓄積部の一例を示す図である。
【図３】整数移動人数蓄積部の一例を示す図である。
【図４】移動確率蓄積部の一例を示す図である。
【図５】本発明の実施の形態に係る整数移動人数推定装置における整数移動人数推定処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２１】
＜本発明の実施の形態に係る整数移動人数推定装置の構成＞
【００２２】
次に、本発明の実施の形態に係る整数移動人数推定装置の構成について説明する。図１に示すように、本発明の実施の形態に係る整数移動人数推定装置１００は、ＣＰＵと、ＲＡＭと、後述する推定処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この整数移動人数推定装置１００は、機能的には図１に示すように操作部７と、演算部２０と、出力部８とを備えている。
【００２３】
操作部７は、人口統計情報蓄積部１のデータに対する各種操作を受け付ける。各種操作とは、人口統計情報を登録、修正、又は削除する操作である。
【００２４】
演算部２０は、人口統計情報蓄積部１と、推定制御部２と、整数移動人数推定部３と、移動確率推定部４と、整数移動人数蓄積部５と、移動確率蓄積部６とを含んで構成されている。
【００２５】
人口統計情報蓄積部１は、人口統計情報を格納しており、操作部７からの要求に従って、人口統計情報を読み出し、推定制御部２に送信する。人口統計情報は、各タイムステップにおける各エリアの人口情報である。タイムステップは例えば午前７時、午前８時、午前９時…といった１時間おきの時刻であり、エリアは例えば地理空間を５ｋｍ四方の正方形グリッドに区切ったものである。時刻ｔにおけるエリアｉの人口はＮｔｉで表される。蓄積する人口統計情報のデータの例を図２に示す。
【００２６】
各処理部について説明する前に、推定プロセスの概観を説明する。
【００２７】
まず、推定に用いる記号を以下のように定義する。
【００２８】
2019211918.tif 000004
【００２９】
エリアｉからエリアｊへの移動確率をθｉｊとすると、時刻ｔにおけるエリアｉからの移動人数Ｍｔｉ＝｛Ｍｔｉｊ｜ｊ∈Ｖ｝は、ｉからの移動確率
【００３０】
2019211918.tif 000005
【００３１】
を用いて以下（１）式に示す確率で生成されると仮定する。
【００３２】
【数１】
2019211918.tif 000006
【００３３】
したがって、Ｎ＝｛Ｎｔｉ｜ｔ＝０，．．．，Ｔ−１，ｉ∈Ｖ｝、θ＝｛θｉ｜ｉ∈Ｖ｝が与えられたとき、Ｍ＝｛Ｍｔｉ｜ｔ＝０，．．．，Ｔ−２，ｉ∈Ｖ｝の尤度関数は以下（２）式となる。
【００３４】
【数２】
2019211918.tif 000007
【００３５】
また、人数の保存則を表す制約が以下（３）式、及び（４）式により成立する。
【００３６】
【数３】
2019211918.tif 000008
【００３７】
推定は、尤度関数Ｐ（Ｍ｜Ｎ，θ）を制約である（３）式、及び（４）式のもとで最大化することによって行う。すなわち、解く最適化問題は以下（５ａ）〜（５ｆ）式となる。
【００３８】
【数４】
2019211918.tif 000009
【００３９】
ただし、
【００４０】
2019211918.tif 000010
【００４１】
は正の整数全体の集合である。
【００４２】
上記の最適化問題を解く方法はいくつか考えられるが、本実施の形態においてはMetropolis-Hastings法（非特許文献３参照）を利用したstochastic EM法（非特許文献４参照）によって解く。この方法によって、Ｍを整数値として保持及び推定することができる。
【００４３】
[非特許文献３] W. K. Hastings. Monte Carlo Sampling Methods Using Markov Chains and Their Applications. Biometrika, Volume57, Number 1(1970), 97-109
【００４４】
[非特許文献４] S. F. Nielsen. The Stochastic EM Algorithm: Estimation and Asymptotic Results. Bernoulli, Volume 6, Number3(2000), 457-489
【００４５】
具体的には、以下に示すＥステップとＭステップを繰り返すことによってＭ，θを更新していく。
【００４６】
まずＥステップ（Ｍの更新）について説明する。
【００４７】
Ｅステップでは、一般的なstochastic EMアルゴリズムのように、ＭをサンプリングすることによってＭを更新する。更新は、各Ｍｔごとに別々に行う。ただし、Ｍｔは時刻ｔからｔ＋１の間における推定移動人数を表す。サンプリングの方法としては、Metropolis-Hastings法を用いる。ここで、以下の制約を満たすようなＭｔ全体の集合をＦｔで表す。
【００４８】
2019211918.tif 000011
【００４９】
Ｍｔを更新する具体的なアルゴリズムは以下１〜５の処理を行う。当該アルゴリズムがMetropolis-Hastings法を利用した方法である。
【００５０】
１．適当なＭｉｎｉｔｔ∈ＦｔによってＭｔを初期化する（Ｍｉｎｉｔｔは例えば線形計画法などによって見つけることができる）。
２．ｉ１，ｉ２をＶから抽出する際に、それぞれが重複しないように非復元抽出する。また、ｉ３，ｉ４をＶから抽出する際に非復元抽出する。
３．
2019211918.tif 000012
に１を足し、
2019211918.tif 000013
に−１を足したものをＭ′ｔとする。
４．
2019211918.tif 000014
ならば何もしないで５に移行する。
2019211918.tif 000015
の場合、確率
2019211918.tif 000016
で、
2019211918.tif 000017
と更新し、確率
2019211918.tif 000018
で何もしない。
５．上記２〜４を繰り返す。適当な回数繰り返した後、Ｍｔを出力する。
【００５１】
十分な回数繰り返しを行えば、上記のアルゴリズムによって生成されたＭはＰ（Ｍ｜Ｎ，θ）からの近似的なサンプリングになることを示すことができる。
【００５２】
次にＭステップ（θの更新）について説明する。
【００５３】
尤度関数Ｐ（Ｍ｜Ｎ，θ）の対数を取ると以下（６）式となる。
【００５４】
【数５】
2019211918.tif 000019
【００５５】
ただし、最終行においてはθに依存する部分以外に関しては定数として省略している。ｌｏｇＰ（Ｍ｜Ｎ，θ）を制約
【００５６】
2019211918.tif 000020
【００５７】
のもとで最大化すればよい。このようなθ＊は、ラグランジュの未定乗数法を用いることにより以下（７）式のように閉形式で記述することができる。
【００５８】
【数６】
2019211918.tif 000021
【００５９】
以上が推定プロセスの概観である。
【００６０】
以上の推定プロセスを踏まえて各処理部の処理について説明する。
【００６１】
推定制御部２は人口統計情報蓄積部１から人口統計情報を読み出し、整数移動人数推定部３に渡すことで推定プロセスをスタートさせる。また、移動確率推定部４の実行が完了する度に条件を満たすかを判定し、推定を終えるか否かのチェックを行うことで、整数移動人数推定部３及び移動確率推定部４の処理を繰り返す。条件を満たすかの判断の方法として、尤度が収束したかどうかを確認する方法や、指定された回数の反復が終わった場合に終了させる方法などが考えられる。推定を終える場合、推定された整数移動人数と移動確率を、それぞれ整数移動人数蓄積部５と移動確率蓄積部６に送信する。
【００６２】
整数移動人数推定部３は、人口統計情報のエリアの各々の各時刻の人口に基づいて、エリアの各々の各時刻の人口Ｎｔｉ、各時刻におけるエリア間の移動人数Ｍｔｉ、及びエリア間の移動確率θｉｊを用いて表される上記（２）式の尤度関数を最大化するように、上記（５ｂ）〜（５ｆ）式に示す、エリアの各々の各時刻の人口と、各時刻におけるエリア間の移動人数とが予め定められた関係であること、及び各時刻におけるエリア間の移動人数が整数値であることを制約として、各時刻におけるエリア間の移動人数Ｍを推定する。具体的な推定は、上記Ｅステップで説明したMetropolis-Hastings法を利用したアルゴリズムに従って、移動確率推定部４によって推定されたエリア間の移動確率、及び上記（２）式の尤度関数に基づいて、（５ｂ）〜（５ｆ）式の制約を満たす、各時刻におけるエリア間の移動人数をサンプリングすることにより行う。
【００６３】
移動確率推定部４は、推定された各時刻におけるエリア間の移動人数Ｍに基づいて、上記（２）式の尤度関数を最大化するように、エリア間の移動確率を推定する。具体的には上記Ｍステップで説明したように、上記（７）式に従って移動確率θを推定する。
【００６４】
整数移動人数蓄積部５は、推定された移動人数Ｍを記憶する。整数移動人数蓄積部５には、例えば図３に示すように、出発タイムスタンプ、出発エリア、到着エリア、及び移動人数のレコードが格納される。
【００６５】
移動確率蓄積部６は、推定された移動確率θを記憶する。移動確率蓄積部６には、例えば図４に示すように、出発エリア、到着エリア、及び移動確率のレコードが格納される。
【００６６】
出力部８は、整数移動人数蓄積部５に格納された各タイムステップ間の各エリア間の移動人数Ｍと、移動確率蓄積部６に格納された各エリア間の移動確率θを読み込み、それらを出力する。
【００６７】
＜本発明の実施の形態に係る整数移動人数推定装置の作用＞
【００６８】
次に、本発明の実施の形態に係る整数移動人数推定装置１００の作用について説明する。整数移動人数推定装置１００は、推定制御部２が人口統計情報蓄積部１から人口統計情報を読み出し、整数移動人数推定部３に渡すことで推定プロセスをスタートさせることにより、図５に示す整数移動人数推定処理ルーチンを実行する。
【００６９】
まず、ステップＳ１００では、整数移動人数推定部３が、人口統計情報のエリアの各々の各時刻の人口に基づいて、エリアの各々の各時刻の人口Ｎｔｉ、各時刻におけるエリア間の移動人数Ｍｔｉ、及びエリア間の移動確率θｉｊを用いて表される上記（２）式の尤度関数を最大化するように、上記（５ｂ）〜（５ｆ）式に示す、エリアの各々の各時刻の人口と、各時刻におけるエリア間の移動人数とが予め定められた関係であること、及び各時刻におけるエリア間の移動人数が整数値であることを制約として、各時刻におけるエリア間の移動人数Ｍを推定する。詳細には、（５ｂ）〜（５ｆ）式の制約を満たす、各時刻におけるエリア間の移動人数をサンプリングすることにより行う。
【００７０】
次に、ステップＳ１０２では、移動確率推定部４が、ステップＳ１００で推定された各時刻におけるエリア間の移動人数Ｍに基づいて、上記（２）式の尤度関数を最大化するように、上記（７）式に従ってエリア間の移動確率を推定する。具体的には上記Ｍステップで説明した方法により移動確率θを推定する。
【００７１】
ステップＳ１０４では、推定制御部２が、条件を満たすかを判定し、条件を満たしていれば処理を終了し、条件を満たしていなければステップＳ１００、Ｓ１０２の処理を繰り返す。
【００７２】
以上説明したように、本発明の実施の形態に係る整数移動人数推定装置によれば、エリアの各々の各時刻の人口に基づいて、エリアの各々の各時刻の人口、各時刻におけるエリア間の移動人数、及びエリア間の移動確率を用いて表される尤度関数を最大化するように、エリアの各々の各時刻の人口と、各時刻におけるエリア間の移動人数とが予め定められた関係であること、及び各時刻におけるエリア間の移動人数が整数値であることを制約として、各時刻におけるエリア間の移動人数を推定し、推定された各時刻におけるエリア間の移動人数に基づいて、尤度関数を最大化するように、エリア間の移動確率を推定することを予め定められた条件を満たすまで繰り返すことにより、エリアのサイズに依存することなく、整数値によって移動人数を精度よく推定できる。
【００７３】
＜変形例＞
【００７４】
上述した実施の形態の変形例について説明する。
【００７５】
変形例では、上述した実施の形態における整数移動人数推定部３の処理を、サンプリングを利用した方法ではなく、制約が付いた輸送問題として定式化を行い輸送問題のアルゴリズムを適用した推定に変更した場合について説明する。
【００７６】
整数移動人数推定装置１００の整数移動人数推定部３の処理部分だけが変更され、他の構成及び作用については同様であるため、整数移動人数推定部３の変更部分についてのみ説明を行う。
【００７７】
整数移動人数推定部３における尤度関数を以下（８）式のように定式化する。
【００７８】
【数７】
2019211918.tif 000022
【００７９】
ただしＭに関係ない部分は定数として省略する。（８）式の尤度関数を最大化し、かつ、以下（９ｂ）〜（９ｄ）式の制約を満たす、各時刻におけるエリア間の移動人数を推定する。
【００８０】
【数８】
2019211918.tif 000023
【００８１】
上記の最適化問題は、一般的に輸送問題（非特許文献５参照）と言われている最適化問題の一例になっているため、輸送問題のアルゴリズムを適用することができる。目的関数がＭｔに関して線形ではないため大域的最適解が得られるとは限らないが、十分な品質の解を得られると考えられる。
【００８２】
[非特許文献５] G.B. Danzig. Application of the simplex method to a transportation problem. In T. C. Koopmans,editor, Activity Analysis of Production and Allocation, volume 13 of Cowles Commission for Research in Economics, pages 359-373.Wiley, 1951.
【００８３】
整数移動人数推定部３のＥステップにおいて輸送問題のアルゴリズムを適用して処理し、上述した実施の形態のＭステップを繰り返すことで、各時刻におけるエリア間の移動人数を推定することができる。
【００８４】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【符号の説明】
【００８５】
１     人口統計情報蓄積部
２     推定制御部
３     整数移動人数推定部
４     移動確率推定部
５     整数移動人数蓄積部
６     移動確率蓄積部
７     操作部
２０   演算部
１００ 整数移動人数推定装置
【図１】
2019211918.tif 000024
【図２】
2019211918.tif 000025
【図３】
2019211918.tif 000026
【図４】
2019211918.tif 000027
【図５】
2019211918.tif 000028