(57)【要約】【課題】ネットワーク上のノードの状態の変化を精度よく推定することができるようにする。【解決手段】条件付きスコア計算部２６によって、状態テーブルＺ、有向エッジｅの各々についてのパラメータ行列、ノードｖの各々に対する状態遷移行列、及び各有向エッジｅの各時刻ｔのフロー量に基づいて、ノードｖ、状態ｋ、及び時刻ｔの組み合わせの各々について、条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）を算出する。状態更新部３０によって、条件付きスコアに基づいて、複数のノードｖの各々に対する各時刻ｔの状態Ｚv,tを更新する。反復終了条件を満たすまで、条件付きスコア計算部２６及び状態更新部３０の各処理を繰り返す。変化検出部３６によって、ノードｖ、状態ｋ、及び時刻ｔの組み合わせの各々について繰り返し算出された条件付きスコアに基づいて算出されるスコアＳｃｏｒｅ（ｖ，ｔ，ｋ）に基づいて、ノードｖの状態の変化を検出する。【選択図】図１
2015064765.tif 000002
【特許請求の範囲】
【請求項１】
複数のノードｖ間を有向エッジｅで結んだネットワークにおける各有向エッジｅの各時刻ｔのフロー量を入力として、前記ノードｖの状態の変化を推定するネットワーク状態推定装置において、
前記有向エッジｅの各々について、前記有向エッジｅの始点のノード及び終点のノードにおける状態の全ての組み合わせｋ１、ｋ２の各々に対する、前記フロー量の分布を表すパラメータを記憶すると共に、前記複数のノードｖの各々について、前記複数の状態ｋ間の各々の状態遷移確率を記憶したパラメータデータベースと、
前記複数のノードｖの各々に対する各時刻ｔの状態Ｚvt、前記有向エッジｅの各々についての前記パラメータ、前記複数のノードｖの各々に対する前記状態遷移確率、及び前記各有向エッジｅの各時刻ｔのフロー量に基づいて、前記ノードｖ、前記状態ｋ、及び時刻ｔの全ての組み合わせについて、時刻ｔにおける前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表す条件付きスコアを算出する条件付きスコア算出手段と、
前記条件付きスコア算出手段によって前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について算出された前記条件付きスコアに基づいて、前記ノードｖの状態の変化を推定する状態推定手段と、
を含むネットワーク状態推定装置。
【請求項２】
前記条件付きスコア算出手段は、前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について、少なくとも前記状態ｋから時刻ｔ＋１の状態Ｚv,t+1へ遷移する状態遷移確率、時刻ｔ−１の状態Ｚv,t-1から前記状態ｋへ遷移する状態遷移確率、前記ノードｖを始点とする前記有向エッジｅの各々についての、前記ノードｖの時刻ｔにおける前記状態ｋと前記有向エッジｅの終点のノードの時刻ｔにおける状態との組み合わせにおける前記有向エッジｅの前記フロー量の確率、及び前記ノードｖを終点とする前記有向エッジｅの各々についての、前記ノードｖの時刻ｔにおける前記状態ｋと前記有向エッジｅの始点のノードの時刻ｔにおける状態との組み合わせにおける前記有向エッジｅの前記フロー量の確率を乗じた値を、時刻ｔの前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表す前記条件付きスコアとして算出する請求項１記載のネットワーク状態推定装置。
【請求項３】
前記複数のノードｖの各々に対して、各時刻ｔの状態Ｚv,tの初期値として、予め定められた複数の状態ｋの何れか一つを設定する初期設定手段と、
前記条件付きスコア算出手段によって算出された前記条件付きスコアに基づいて、前記複数のノードｖの各々に対する各時刻ｔの状態Ｚv,tを更新する状態更新手段と、
反復終了条件を満たすまで、前記条件付きスコア算出手段による算出、及び前記状態更新手段による更新を繰り返す反復判定手段とを更に含み、
前記条件付きスコア算出手段は、前記複数のノードｖの各々に対する各時刻ｔの状態Ｚvt、前記有向エッジｅの各々についての前記パラメータ、前記複数のノードｖの各々に対する前記状態遷移確率、及び前記各有向エッジｅの各時刻ｔのフロー量に基づいて、前記ノードｖ、前記状態ｋ、及び時刻ｔの全ての組み合わせについて、前記複数のノードｖの各々に対する各時刻ｔの状態Ｚv,tが与えられたときの、時刻ｔにおける前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表す条件付きスコアを算出し、
前記状態推定手段は、前記条件付きスコア算出手段によって前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について繰り返し算出された前記条件付きスコアに基づいて、前記ノードｖの状態の変化を推定する
請求項１又は２記載のネットワーク状態推定装置。
【請求項４】
前記状態推定手段は、前記条件付きスコア算出手段によって前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について繰り返し算出された前記条件付きスコアに基づいて得られる、時刻ｔの前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表すスコアに基づいて、前記ノードｖの状態の変化を推定する請求項３記載のネットワーク状態推定装置。
【請求項５】
前記状態推定手段は、前記ノードｖの状態の変化として、前記ノードｖにおいて異常状態が生じたことを推定する請求項１〜請求項４の何れか１項記載のネットワーク状態推定装置。
【請求項６】
複数の地点を表す前記複数のノードｖ間を有向エッジｅで結んだ道路ネットワークにおける各有向エッジｅの各時刻ｔの交通需要量を表す前記フロー量を入力とした請求項１〜請求項５の何れか１項記載のネットワーク状態推定装置。
【請求項７】
複数のノードｖ間を有向エッジｅで結んだネットワークにおける各有向エッジｅの各時刻ｔのフロー量を入力として、前記ノードｖの状態の変化を推定するためのプログラムにおいて、
前記有向エッジｅの各々について、前記有向エッジｅの始点のノード及び終点のノードにおける状態の全ての組み合わせｋ１、ｋ２の各々に対する、前記フロー量の分布を表すパラメータを記憶すると共に、前記複数のノードｖの各々について、予め定められた複数の状態ｋ間の各々の状態遷移確率を記憶したパラメータデータベースを含むコンピュータを、
前記複数のノードｖの各々に対する各時刻ｔの状態Ｚvt、前記有向エッジｅの各々についての前記パラメータ、前記複数のノードｖの各々に対する前記状態遷移確率、及び前記各有向エッジｅの各時刻ｔのフロー量に基づいて、前記ノードｖ、前記状態ｋ、及び時刻ｔの全ての組み合わせについて、時刻ｔにおける前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表す条件付きスコアを算出する条件付きスコア算出手段、及び
前記条件付きスコア算出手段によって前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について算出された前記条件付きスコアに基づいて、前記ノードｖの状態の変化を推定する状態推定手段
として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワーク状態推定装置及びプログラムに係り、特に、ネットワーク上のノードの状態の変化を推定するネットワーク状態推定装置及びプログラムに関する。
【背景技術】
【０００２】
従来より、ネットワークの障害の有無を判定し、障害中の異常状態遷移を検出するネットワーク異常検出装置が知られている（特許文献１）。このネットワーク異常検出装置は、障害及び異常状態の遷移の有無を判定するために用いる基準となる基準ベクトルＲおよび一時基準ベクトルＴを備えている。現時点で第２のベクトルＢが得られたとき、基準ベクトルＲと第２のベクトルＢとの間の角度差ＲＢを異常スコアとし、その異常スコアが閾値より大きい場合、異常（障害）有りと判定する。なお、一時基準ベクトルＴは、既に異常（障害）ありと判定された第１のベクトルＡと同じものである。そこで、第２のベクトルＢと一時基準ベクトルＴとの間の角度差ＴＢを異常スコアとし、その異常スコアが閾値より大きい場合、第１のベクトルＡと第２のベクトルＢとは異なる異常状態を表している（異常状態が遷移している）と判定することができる。
【０００３】
また、多様な多数のセンサを含むセンサネットワークにおいて、センサ間の依存関係や各センサの観測値の統計的な振舞いから想定外の異常を検出する特異パターン検出システムが知られている（特許文献２）。特異パターン検出システムのモデル学習サーバは、データベースサーバから、センサネットワーク内の各センサから得た観測値を示す観測データを受信し、この観測データから親センサ群を求めるとともに、求められたセンサと親センサ群との依存関係を元に、センサ観測値の統計的なパラメータを求めて、特異パターン検出サーバに送信する。特異パターン検出サーバは、データベースサーバから、特異パターン検出対象となる各観測時刻ごとの観測データである観測パターンを受信し、親センサ群の情報と統計的なパラメータを用いて、受信した観測パターンの特異性を判定し、異常検出時にユーザ端末へ警告を通知する。
【０００４】
また、特徴量ベクトルを意味付けのされていないパターンに分類するパターン分類装置が知られている（特許文献３）。このパターン分類装置は、特徴量を入力する入力ノードと、特徴量と特徴量パターンとの合致度を算出するパターンマッチング部と、特徴量ベクトルと特徴量パターンセットとの合致度を算出し出力する出力ノードと、特徴量ベクトルと既存の特徴量パターンセットの近似度を判定する近似度判定手段と、新しい特徴量ベクトルのパターン種別に対応する新しい出力ノード及び新しい特徴量パターンセットを生成し追加するパターンセット追加手段と、特徴量パターンセットを変形するパターンセット変形手段とからなる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２０１２‐２５６９６１号公報
【特許文献２】特開２００７‐２７９８８７号公報
【特許文献３】特開平７−３３４４７９号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記の特許文献１に記載の技術では、ネットワーク上を流れる行列型のデータから特徴抽出を行い、異常（ある種のイベント）を抽出する方法になっているが、確率的な方法ではなく、固有ベクトルを用いた方法を採用しており、ノイズなどに対しての頑強性が低く、また、得られた固有ベクトルがいかなる意味（状態）を持つかが明確ではない。
【０００７】
上記の特許文献２に記載の技術では、ネットワークの通信パターンの異常検出を統計的なアプローチによって行なっているが、非循環の有向グラフのみに対して有効な方法であり、より現実的な循環有向グラフ上のパターン検出に用いることができない。交通にしても、センサにしても、現実のネットワークは一般に循環的な因果関係を持つと考えるのが自然である。
【０００８】
上記の特許文献３に記載の技術では、時間に関する情報やネットワーク構造の情報が考慮されていないため、ノードごとの状態変化の検出を行うことは難しい。
【０００９】
本発明は、上記の事情に鑑みて成されたものであり、ネットワーク上のノードの状態の変化を精度よく推定することができるネットワーク状態推定装置及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために本発明のネットワーク状態推定装置は、複数のノードｖ間を有向エッジｅで結んだネットワークにおける各有向エッジｅの各時刻ｔのフロー量を入力として、前記ノードｖの状態の変化を推定するネットワーク状態推定装置において、前記有向エッジｅの各々について、前記有向エッジｅの始点のノード及び終点のノードにおける状態の全ての組み合わせｋ１、ｋ２の各々に対する、前記フロー量の分布を表すパラメータを記憶すると共に、前記複数のノードｖの各々について、前記複数の状態ｋ間の各々の状態遷移確率を記憶したパラメータデータベースと、前記複数のノードｖの各々に対する各時刻ｔの状態Ｚvt、前記有向エッジｅの各々についての前記パラメータ、前記複数のノードｖの各々に対する前記状態遷移確率、及び前記各有向エッジｅの各時刻ｔのフロー量に基づいて、前記ノードｖ、前記状態ｋ、及び時刻ｔの全ての組み合わせについて、時刻ｔにおける前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表す条件付きスコアを算出する条件付きスコア算出手段と、前記条件付きスコア算出手段によって前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について算出された前記条件付きスコアに基づいて、前記ノードｖの状態の変化を推定する状態推定手段と、を含んで構成されている。
【００１１】
本発明のプログラムは、複数のノードｖ間を有向エッジｅで結んだネットワークにおける各有向エッジｅの各時刻ｔのフロー量を入力として、前記ノードｖの状態の変化を推定するためのプログラムにおいて、前記有向エッジｅの各々について、前記有向エッジｅの始点のノード及び終点のノードにおける状態の全ての組み合わせｋ１、ｋ２の各々に対する、前記フロー量の分布を表すパラメータを記憶すると共に、前記複数のノードｖの各々について、予め定められた複数の状態ｋ間の各々の状態遷移確率を記憶したパラメータデータベースを含むコンピュータを、複数のノードｖ間を有向エッジｅで結んだネットワークにおける各有向エッジｅの各時刻ｔのフロー量を入力として、前記ノードｖの状態の変化を推定するネットワーク状態推定装置において、前記複数のノードｖの各々に対する各時刻ｔの状態Ｚvt、前記有向エッジｅの各々についての前記パラメータ、前記複数のノードｖの各々に対する前記状態遷移確率、及び前記各有向エッジｅの各時刻ｔのフロー量に基づいて、前記ノードｖ、前記状態ｋ、及び時刻ｔの全ての組み合わせについて、時刻ｔにおける前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表す条件付きスコアを算出する条件付きスコア算出手段、及び前記条件付きスコア算出手段によって前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について算出された前記条件付きスコアに基づいて、前記ノードｖの状態の変化を推定する状態推定手段として機能させるためのプログラムである。
【００１２】
本発明によれば、条件付きスコア算出手段によって、前記複数のノードｖの各々に対する各時刻ｔの状態Ｚvt、前記有向エッジｅの各々についての前記パラメータ、前記複数のノードｖの各々に対する前記状態遷移確率、及び前記各有向エッジｅの各時刻ｔのフロー量に基づいて、前記ノードｖ、前記状態ｋ、及び時刻ｔの全ての組み合わせについて、時刻ｔにおける前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表す条件付きスコアを算出する。
【００１３】
そして、状態推定手段によって、前記条件付きスコア算出手段によって前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について算出された前記条件付きスコアに基づいて、前記ノードｖの状態の変化を推定する。
【００１４】
このように、前記複数のノードｖの各々に対する各時刻ｔの状態Ｚv,t、前記有向エッジｅの各々についての前記パラメータ、前記複数のノードｖの各々に対する前記状態遷移確率、及び前記各有向エッジｅの各時刻ｔのフロー量に基づいて、前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について、時刻ｔの前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表す前記条件付きスコアを算出し、前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について算出された前記条件付きスコアに基づいて、前記ノードｖの状態の変化を推定することにより、ネットワーク上のノードの状態の変化を精度よく推定することができる。
【００１５】
本発明に係る条件付きスコア算出手段は、前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について、少なくとも前記状態ｋから時刻ｔ＋１の状態Ｚv,t+1へ遷移する状態遷移確率、時刻ｔ−１の状態Ｚv,t-1から前記状態ｋへ遷移する状態遷移確率、前記ノードｖを始点とする前記有向エッジｅの各々についての、前記ノードｖの時刻ｔにおける前記状態ｋと前記有向エッジｅの終点のノードの時刻ｔにおける状態との組み合わせにおける前記有向エッジｅの前記フロー量の確率、及び前記ノードｖを終点とする前記有向エッジｅの各々についての、前記ノードｖの時刻ｔにおける前記状態ｋと前記有向エッジｅの始点のノードの時刻ｔにおける状態との組み合わせにおける前記有向エッジｅの前記フロー量の確率を乗じた値を、時刻ｔの前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表す前記条件付きスコアとして算出するようにすることができる。
【００１６】
本発明に係るネットワーク状態推定装置は、前記複数のノードｖの各々に対して、各時刻ｔの状態Ｚv,tの初期値として、予め定められた複数の状態ｋの何れか一つを設定する初期設定手段と、前記条件付きスコア算出手段によって算出された前記条件付きスコアに基づいて、前記複数のノードｖの各々に対する各時刻ｔの状態Ｚv,tを更新する状態更新手段と、反復終了条件を満たすまで、前記条件付きスコア算出手段による算出、及び前記状態更新手段による更新を繰り返す反復判定手段とを更に含み、前記条件付きスコア算出手段は、前記複数のノードｖの各々に対する各時刻ｔの状態Ｚvt、前記有向エッジｅの各々についての前記パラメータ、前記複数のノードｖの各々に対する前記状態遷移確率、及び前記各有向エッジｅの各時刻ｔのフロー量に基づいて、前記ノードｖ、前記状態ｋ、及び時刻ｔの全ての組み合わせについて、前記複数のノードｖの各々に対する各時刻ｔの状態Ｚv,tが与えられたときの、時刻ｔにおける前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表す条件付きスコアを算出し、前記状態推定手段は、前記条件付きスコア算出手段によって前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について繰り返し算出された前記条件付きスコアに基づいて、前記ノードｖの状態の変化を推定するようにすることができる。
【００１７】
本発明に係る状態推定手段は、前記条件付きスコア算出手段によって前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について繰り返し算出された前記条件付きスコアに基づいて得られる、時刻ｔの前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表すスコアに基づいて、前記ノードｖの状態の変化を推定するようにすることができる。
【００１８】
本発明に係る状態推定手段は、前記ノードｖの状態の変化として、前記ノードｖにおいて異常状態が生じたことを推定するようにすることができる。
【００１９】
本発明に係るネットワーク状態推定装置は、複数の地点を表す前記複数のノードｖ間を有向エッジｅで結んだ道路ネットワークにおける各有向エッジｅの各時刻ｔの交通需要量を表す前記フロー量を入力とすることができる。
【００２０】
なお、本発明のプログラムを記憶する記憶媒体は、特に限定されず、ハードディスクであってもよいし、ＲＯＭであってもよい。また、ＣＤ−ＲＯＭやＤＶＤディスク、光磁気ディスクやＩＣカードであってもよい。更にまた、該プログラムを、ネットワークに接続されたサーバ等からダウンロードするようにしてもよい。
【発明の効果】
【００２１】
以上説明したように、本発明によれば、前記複数のノードｖの各々に対する各時刻ｔの状態Ｚv,t、前記有向エッジｅの各々についての前記パラメータ、前記複数のノードｖの各々に対する前記状態遷移確率、及び前記各有向エッジｅの各時刻ｔのフロー量に基づいて、前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について、時刻ｔの前記ノードｖの状態Ｚv,tが前記状態ｋである度合いを表す前記条件付きスコアを算出し、前記ノードｖ、前記状態ｋ、及び時刻ｔの組み合わせの各々について算出された前記条件付きスコアに基づいて、前記ノードｖの状態の変化を推定することにより、ネットワーク上のノードの状態の変化を精度よく推定することができる、という効果が得られる。
【図面の簡単な説明】
【００２２】
【図１】本発明の実施の形態に係る道路ネットワーク状態推定装置の構成を示すブロック図である。
【図２】時間変化する重み付き有向グラフのデータを示す図である。
【図３】状態テーブルを示す図である。
【図４】各ノードのスコアを示す図である。
【図５】本発明の実施の形態に係るパラメータ学習装置の構成を示すブロック図である。
【図６】本発明の実施の形態に係るパラメータ学習装置におけるパラメータ学習処理ルーチンの内容を示すフローチャートである。
【図７】本発明の実施の形態に係る道路ネットワーク状態推定装置における状態変化推定処理ルーチンの内容を示すフローチャートである。
【発明を実施するための形態】
【００２３】
以下、図面を参照して、本発明の好適な実施の形態について説明する。
【００２４】
図１に示すように、本発明の実施の形態に係る交通ネットワーク状態推定装置１０は、ＣＰＵと、ＲＡＭと、後述する状態変化推定処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータから構成されている。交通ネットワーク状態推定装置１０は、複数のプローブカーの各々に搭載された車載器から送信されたプローブデータを収集するプローブデータ収集部１２と、プローブデータ収集部１２によって収集されたプローブデータを、道路ネットワークにおける各時刻の各有向リンクの交通需要量を表す重み付き有向グラフに変換するプローブデータ変換部１４と、道路ネットワークの各ノードの各時刻における状態を格納した状態格納部１６と、状態格納部１６に格納される各状態を初期化する状態初期化部１８と、各有向リンクの交通需要量の分布を表すパラメータ及び各ノードの状態遷移確率を記憶したパラメータデータベース２０と、各時刻における各有向リンクの交通需要量に対する尤度を各々計算する尤度計算部２２と、道路ネットワークの各ノードの各時刻における状態について遷移確率を計算する遷移確率計算部２４と、道路ネットワークの各ノードの各時刻における状態に対する条件付きスコア及びスコアを計算する条件付きスコア計算部２６と、計算されたスコアを格納したスコア格納部２８と、計算された条件付きスコアに基づいて状態格納部１６に格納される各状態を更新する状態更新部３０と、反復条件を満たすか否かを判定する反復判定部３２と、状態変化を検出するためのデータを格納した変化検出用データベース３４と、道路ネットワークの各ノードの各時刻における状態に対するスコアに基づいて、ノードの状態の変化を検出する変化検出部３６と、状態の変化の検出結果に基づいて、ノードの将来の状態の変化を予測する変化予測部３８と、将来の状態の変化の予測結果を、複数の車両に搭載された車載器へ配信する情報配信部４０とを備えている。なお、変化検出部３６が、状態推定手段の一例である。
【００２５】
各プローブカーの車載器は、ネットワーク（図示省略）を介して、ＧＰＳを用いて計測した自車両の位置情報を含むプローブデータを、逐次、交通ネットワーク状態推定装置１０へ送信する。
【００２６】
プローブデータ収集部１２は、通信部（図示省略）によって受信したプローブデータを収集する。
【００２７】
プローブデータ変換部１４は、プローブデータ収集部１２によって収集されたプローブデータと、予め用意された道路ネットワークのデータとに基づき、道路ネットワークにおける各時刻の各有向リンクの交通需要量を表す、時間変化する重み付き有向グラフに変換する。
【００２８】
時間変化する重み付き有向グラフのデータは、図２に示すような形式で表わされる。
【００２９】
時間ｔは離散的なものであるとし、１〜Ｔの値をとるとする。例えば、Ａ→Ｂ、ｔ＝１、重み＝８１というデータの集合であり、このデータは「時刻１にＡ→Ｂの有向リンクで８１という交通需要量を観測した」ということに対応している。この８１という値が重みと呼んでいるものである。なお、有向グラフの構造（頂点数とその繋がり方）は不変であるとする。有向グラフＧに対して、そのノードの集合Ｖ、その有向リンクの集合をＥとする。有向リンクｅの時刻ｔでの重みをＸｅｔと書く。
【００３０】
各有向リンクｅの始点ノードをｂ（ｅ）と書き、終点ノードをｔ（ｅ）と書くことにする。ノード集合Ｖに対して、ｅ∈Ｅのうち、始点ノードｂ（ｅ）＝ｖとなるような有向リンクｅの集合をＥｏｕｔ（ｖ）と書き、終点ノードｔ（ｅ）＝Ｖとなるような有向リンクｅの集合をＥｉｎ（ｖ）と書くことにする。
【００３１】
各ノードｖは各時刻ｔにおいて「状態」と呼ばれる量を持ち、状態を表す変数をＺｖｔと書く。Ｚｖｔはすべて１〜Ｋの範囲の値をとるものであるとする。Ｋを「状態数」と呼ぶ。
【００３２】
このように定義された状態は図３のようなテーブル形式で書くことができる。単にＺと書いたときは各ノードの状態の時系列を表す状態テーブル全体を指すものとする。
【００３３】
状態格納部１６は、上記図３に示す状態テーブルＺを格納する。
【００３４】
状態初期化部１８は、計算開始時点において、状態テーブルＺの各状態に、ランダムに１〜Ｋの値を初期値として設定する（Ｋは予め与えられた正の整数）。
【００３５】
パラメータデータベース２０には、各有向リンクｅ∈Ｅに対して、それぞれＫ×Ｋのパラメータ行列Θｅが記憶されている。パラメータ行列Θｅの要素には、重みを発生させている確率分布のパラメータが格納され、重みがどんなデータであるかに依存する。本実施の形態では、重みが交通需要量を表すため、パラメータ行列Θｅの要素は、ポアソン分布に従う確率変数とみなすことができ、Θｅの各要素には、ポアソン分布のパラメータ（平均）が格納されている。「重みを発生させている確率分布」を「出力分布」と定義する。有向リンクｅの出力分布を、そのパラメータ依存性を明記した形で、ｆｅ（Ｘ｜θ）と書く。ここで、θには、Θｅの要素のうち、どれかーつが代入される。なお、Θｅのｋ＋１行ｋ２列の要素を参照する際には、Θｅ［ｋ１］［ｋ２］という表記を用いる。
【００３６】
また、パラメータデータベース２０には、各ノードｖ∈Ｖに対して、状態遷移行列Ｐｖが記憶されている。状態遷移行列Ｐｖのｋ１行ｋ２列の要素は、時刻ｔにおいて状態ｋ１であるｖの状態が時刻ｔ＋１で状態ｋ２になる状態遷移確率である。
【００３７】
尤度計算部２２は、プローブデータ変換部１４によって得られた時間変化する重み付き有向グラフのデータと、状態格納部１６に格納された状態テーブルＺと、パラメータデータベース２０に記憶された各リンクｅのパラメータ行列Θｅとに基づいて、時刻ｔ毎に、各有向リンクｅの重みＸet（交通需要量）に対する尤度を計算する。
【００３８】
遷移確率計算部２４は、状態格納部１６に格納された状態テーブルＺと、パラメータデータベース２０に記憶された各ノードｖの状態遷移行列Ｐｖとに基づいて、時刻ｔ毎に、各ノードｖが状態ｋとなる遷移確率を計算する。
【００３９】
条件付きスコア計算部２６は、尤度計算部２２の計算結果および遷移確率計算部２４の計算結果に基づき、ノードｖ、時刻ｔ、及び状態ｋの組み合わせ毎に、状態テーブルＺが与えられたときのノードｖが時刻ｔにおいて状態ｋである度合いを示す条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）を計算すると共に、計算された条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）に基づいて、ノードｖが時刻ｔにおいて状態ｋである度合いを示すスコアＳｃｏｒｅ（ｖ，ｔ，ｋ）を計算し、スコア格納部２８に格納されているスコアを、計算されたスコアＳｃｏｒｅ（ｖ，ｔ，ｋ）に更新する。
【００４０】
ノードｖが時刻ｔにおいて状態ｋである度合いを示すスコアＳｃｏｒｅ（ｖ，ｔ，ｋ）は、図４に示すように、ノードｖ、時刻ｔ、及び状態ｋの組み合わせ毎に定められる実数値である。
【００４１】
スコアＳｃｏｒｅ（ｖ，ｔ，ｋ）は以下の擬似コードで示されるような収束計算によって求められる。十分に大きな繰り返し回数の上限Ｒを設定しておく。
【００４２】
［擬似コード］
状態テーブルＺをランダムに初期化する；
Ｓｃｏｒｅ（ｖ，ｔ，ｋ）＜−０；
ｓ＝長さＫの配列：
ｆｏｒ（ｒ＝１：ｒ＜＝Ｒ；＋＋ｒ）
ｆｏｒ（ｔ＝１；ｔ＜＝Ｔ；＋＋ｔ）｛
ｆｏｒ（∀ｖ∈Ｖ）｛
ｆｏｒ（ｋ＝１；ｋ＜＝Ｋ；＋＋ｋ）｛
ｓ［ｋ］＝Ｓｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）；
Ｓｃｏｒｅ（ｖ，ｔ，ｋ）＝（ｒ−１）／Ｒ＊Ｓｃｏｒｅ（ｖ，ｔ，ｋ）＋ｌｏｇ（ｓ［ｋ］）／Ｒ
｝
Ｚv,t＝（ｓ［ｋ］に比例する確率で１〜Ｋを選択）
｝
｝
｝
［擬似コード終わり］
【００４３】
状態テーブルＺが与えられたときの条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）は、スコア計算のために計算される。条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）は、スコアと同様に、ノードｖ、時刻ｔ、及び状態ｋの組み合わせ毎に計算される。
【００４４】
ノードｖ及び時刻ｔについての条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）は、現在の状態テーブルＺに基いて、状態ｋ（ｋ＝１〜Ｋ）毎に計算される。計算式は次のように与えられる。
【００４５】
【数１】
2015064765.tif 000003
【００４６】
ただし、Ｐｖ［ｋ］［Ｚv,t-1］×Ｐｖ［Ｚv,t+1］［ｋ］は、遷移確率計算部２４によって計算される、ノードｖが時刻ｔにおいて状態ｋとなる遷移確率である。また、ｆe（Ｘet｜Θe［ｋ］［Ｚt(e),t］）、ｆe（Ｘet｜Θe［Ｚb(e),t］［ｋ］）は、尤度計算部２２によって計算される、時刻ｔ、リンクｅの重みＸetに対する尤度である。
【００４７】
なお、上式第一項、第二項において、ｔ−１やｔ＋１が１〜Ｔの添宇の範囲を越えた場合は、例えば遷移確率自身を１とするなどの処理を行えばよい。
【００４８】
状態更新部３０は、条件付きスコア計算部２６によって計算された条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）に基づいて、時刻ｔ及びノードｖの組み合わせ毎に、各状態ｋについて計算された条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）に比例する確率で、時刻ｔにおけるノードｖの状態を決定し、状態格納部１６に格納されている状態テーブルを更新する。
【００４９】
反復判定部３２は、尤度計算部２２、遷移確率計算部２４、条件付きスコア計算部２６、及び状態更新部３０の各処理の繰り返し回数ｒが、上限回数Ｒに到達したか否かを判定し、繰り返し回数ｒが上限回数Ｒに到達するまで、尤度計算部２２、遷移確率計算部２４、条件付きスコア計算部２６、及び状態更新部３０の各処理を繰り返す。最終的に収束した時刻ｔ、ノードｖ、及び状態ｋの組み合わせ毎のスコアＳｃｏｒｅ（ｖ，ｔ，ｋ）が、スコア格納部２８に格納される。なお、繰り返し回数ｒが上限回数Ｒに到達することが、反復終了条件の一例である。
【００５０】
変化検出用データベース３４には、時刻ｔにノードｖで状態変化が生じたかどうかを判定するためのルール（変化検出パラメータ）が記憶されている。
【００５１】
例えば、以下の（１）、（２）のルールが記憶されている。
【００５２】
（１）Ｋ個の状態ｋの各々に対するＳｃｏｒｅ（ｖ，ｔ，ｋ）の値すべてが、予め定められた閾値よりも小さい場合、時刻ｔにおけるノードｖに異常な状態が生じていると判定する。
【００５３】
（２）Ｋ個の状態ｋの各々に対するＳｃｏｒｅ（ｖ，ｔ，ｋ）の値の中で最大値となるＳｃｏｒｅ（ｖ，ｔ，ｋ）の状態ｋが、異常状態であると予め定義されている状態ｋ’であって、かつ、当該最大値となるＳｃｏｒｅ（ｖ，ｔ，ｋ）の値が、予め定められた範囲内である場合、時刻ｔにおけるノードｖに異常な状態が生じていると判定する。
【００５４】
また、変化検出用データベース３４には、将来の状態の変化を予測するためのルールが記憶されている。
【００５５】
例えば、午後３時の時点で、ノードＡにおいて状態Ｘが最もスコアが高い場合、午後４〜６時は状態Ｙとなる可能性が非常に高い、というルールが、変化検出用データベース３４に記憶されている。なお、将来の状態の変化を予測するためのルールは、過去の状態の系列に基づき、アソシエーションルールなどの手法によって抽出可能である。また、遷移確率を用いたルールが、変化検出用データベース３４に記憶されていてもよい。例えば、ノードＡにおいて状態Ｘが最もスコアが高い場合、午後４時の状態がＸである確率が１０％、状態がＹである確率が８０％、状態がＺである確率が１０％である、というルールが、変化検出用データベース３４に記憶されている。遷移確率については、パラメータデータベース２０に格納されたものを使うことが可能である。
【００５６】
変化検出部３６は、スコア格納部２８に格納された時刻ｔ、ノードｖ、及び状態ｋの組み合わせ毎のスコアＳｃｏｒｅ（ｖ，ｔ，ｋ）と、変化検出用データベース３４に記憶されている状態変化が生じたかどうかを判定するためのルールとに基づいて、状態の変化として、異常な状態が生じている時刻ｔ及びノードｖを検出する。
【００５７】
変化予測部３８は、変化検出部３６で検出された状態の変化と、変化検出用データベース３４に記憶されている将来の状態の変化を予測するためのルールとに基づいて、将来の状態を予測する。
【００５８】
情報配信部４０は、変化予測部３８によって予測された結果を示す情報を、予測された状態変化が重要だと思われる車両の車載器に対して配信する。例えば、状態の変化として、ノードＡにおいて、午後５時に、スタジアムで試合がある、という状態Ｘが検出され、午後８時の時点で帰宅が始まると予測された場合には、午後８時にスタジアム周辺を通りそうな車両の車載器に対して、渋滞予測情報を配信する。
【００５９】
次に、パラメータデータベース２０に記憶されるパラメータ行列Θｅ及び状態遷移行列Ｐｖを学習する方法について説明する。パラメータデータベース２０に記憶されるパラメータ行列Θｅ及び状態遷移行列Ｐｖは、図５に示すパラメータ学習装置１００によって予め学習される。
【００６０】
パラメータ学習装置１００は、ＣＰＵと、ＲＡＭと、後述するパラメータ学習処理ルーチンを実行するためのプログラムを記憶したＲＯＭとを備えたコンピュータから構成されている。パラメータ学習装置１００は、プローブデータ収集部１１２と、プローブデータ変換部１１４と、状態格納部１１６と、状態初期化部１１８と、パラメータデータベース１２０と、尤度計算部１２２と、遷移確率計算部１２４と、条件付きスコア計算部１２６と、状態更新部１３０と、パラメータ更新部１３１と、反復判定部１３２とを備えている。
【００６１】
プローブデータ収集部１１２は、プローブデータ収集部１２と同様に、通信部（図示省略）によって受信したプローブデータを収集する。
【００６２】
プローブデータ変換部１１４は、プローブデータ変換部１４と同様に、プローブデータ収集部１１２によって収集されたプローブデータと、予め用意された道路ネットワークのデータとに基づき、道路ネットワークにおける各時刻の各有向リンクの交通需要量を表す、時間変化する重み付き有向グラフのデータに変換する。
【００６３】
状態格納部１１６は、上記図３に示す状態の時系列テーブルＺを格納する。
【００６４】
ここで、パラメータの学習は以下の擬似コードで示されるような処理によって行われる。
【００６５】
[擬似コード]
状態テーブルＺをランダムに初期化する：
Ｓｃｏｒｅ（ｖ、ｔ、ｋ）←０；
ｓ←長さＫの配列；
ｆｏｒ（ｒ＝１；ｒ＜Ｒ；＋＋ｒ）
ｆｏｒ（ｔ＝１；ｔ＜Ｔ；＋＋ｔ）{
ｆｏｒ（∀ｖ∈Ｖ）{
ｆｏｒ（ｋ１＝１；ｋ１＜＝Ｋ；＋＋ｋ１）{
ｓ[ｋ１]←Ｓｃｏｒｅ（ｖ、ｔ、ｋ１｜Ｚ）；
}
Ｚv,t←（ｓ[ｋ]に比例する確率で１−Ｋを選択）
Ｐｖ←Ｕｐｄａｔｅ  Ｔｒａｎｓｉｔｉｏｎ  Ｍａｔｒｉｘ（ｖ、Ｚ）；／／パラメータ更新部１３１による状態遷移行列の更新
ｆｏｒ（ｋ１＝１；ｋ１＜＝Ｋ；＋＋ｋ１）{
ｆｏｒ（ｋ２＝１；ｋ２＜＝Ｋ；＋＋ｋ２）{
ｆｏｒ（∀ｅ∈{ｖを始点とするリンク}）{
Θｅ[ｋ１][ｋ２]←ＵｐｄａｔｅＰａｒａｍｅｔｅｒ（ｅ、ｋ１、ｋ２、Ｚ）；／／パラメータ更新部１３１によるパラメータ行列の更新
}
ｆｏｒ（∀ｅ∈{ｖを終点とするリンク}）{
Θｅ[ｋ２][ｋ１]←ＵｐｄａｔｅＰａｒａｍｅｔｅｒ（ｅ、ｋ２、ｋ１、Ｚ）；／／パラメータ更新部１３１によるパラメータ行列の更新
}
}
}
}
}
}
[擬似コード終わり]
【００６６】
上記の擬似コードで示したように、状態初期化部１１８は、計算開始時点において、状態の時系列テーブルＺの各状態に、ランダムに１〜Ｋの値を初期値として設定する。
【００６７】
パラメータデータベース１２０には、パラメータデータベース２０と同様に、各有向リンクｅ∈Ｅに対して、それぞれＫ×Ｋのパラメータ行列Θｅが記憶されている。また、パラメータデータベース１２０には、各ノードｖ∈Ｖに対して、状態遷移行列Ｐｖが記憶されている。
【００６８】
尤度計算部１２２は、尤度計算部２２と同様に、プローブデータ変換部１１４によって得られた時間変化する重み付き有向グラフのデータと、状態格納部１１６に格納された状態テーブルＺと、パラメータデータベース１２０に記憶された各有向リンクｅのパラメータ行列Θｅとに基づいて、時刻ｔ毎に、各有向リンクｅの重みＸet（交通需要量）に対する尤度を計算する。
【００６９】
遷移確率計算部１２４は、遷移確率計算部２４と同様に、状態格納部１１６に格納された状態テーブルＺと、パラメータデータベース１２０に記憶された各ノードｖの状態遷移行列Ｐｖとに基づいて、時刻ｔ毎に、各ノードｖが状態ｋとなる遷移確率を計算する。
【００７０】
条件付きスコア計算部１２６は、条件付きスコア計算部１２６と同様に、尤度計算部１２２の計算結果および遷移確率計算部１２４の計算結果に基づき、ノードｖ、時刻ｔ、及び状態ｋの組み合わせ毎に、状態テーブルＺが与えられたときのノードｖが時刻ｔにおいて状態ｋである度合いを示す条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）を計算する。
【００７１】
状態更新部１３０は、状態更新部３０と同様に、条件付きスコア計算部１２６によって計算された条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）に基づいて、時刻ｔ及びノードｖの組み合わせ毎に、各状態ｋについて計算された条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）に比例する確率で、時刻ｔにおけるノードｖの状態を決定し、状態格納部１１６に格納されている状態テーブルを更新する。
【００７２】
反復判定部１３２は、尤度計算部１２２、遷移確率計算部１２４、条件付きスコア計算部１２６、状態更新部１３０、及びパラメータ更新部１３１の各処理の繰り返し回数ｒが、上限回数Ｒに到達したか否かを判定し、繰り返し回数ｒが上限回数Ｒに到達するまで、尤度計算部１２２、遷移確率計算部１２４、条件付きスコア計算部１２６、状態更新部１３０、及びパラメータ更新部１３１の各処理を繰り返す。
【００７３】
パラメータ更新部１３１は、状態格納部１１６に格納されている状態テーブルＺに基づいて、各ノードｖに対して、状態遷移行列Ｐｖを更新する。具体的には、以下の擬似コードに従って、状態遷移行列Ｐｖが更新される。
【００７４】
Ｐｖ←Ｋ×Ｋ行列
Ｆｏｒ（ｋ＝１；ｋ１＜＝Ｋ；ｋ１＋＋）{
Ｆｏｒ（ｋ２＝１；ｋ２＜＝Ｋ；ｋ２＋＋）{
Ｐｖ［ｋ１］［ｋ２］←ｃ（ｋ１、ｋ２）／（ｋ１）；
｝
｝
Ｒｅｔｕｒｎ  Ｐｖ；
【００７５】
ただし、ｃ（ｋ１、ｋ２）は、状態テーブルＺから得られるノードｖの状態の時系列Ｚｖの中に（ｋ１、ｋ２）が連続して出現した回数であり、ｃ（ｋ１）はＺｖの中にｋ１が出現した回数である。
【００７６】
また、パラメータ更新部１３１は、各有向リンクｅについて、状態ｋ１、ｋ２の組み合わせ毎に、パラメータ行列Θe［ｋ１］［ｋ２］を更新する。具体的には、以下の擬似コードに従って、パラメータ行列Θe［ｋ１］［ｋ２］が更新される。
【００７７】
Ｄｅ[ｋ１][ｋ２]←{}／／空の集合
Ｆｏｒ（ｔ＝１；ｔ＜＝Ｔ；ｔ＋＋）{
ｉｆ（Ｚb(e),t＝＝ｋ１＆＆Ｚt(e),t＝＝ｋ２）{      ／／Ｚb(e),tという記号はノードｂ（ｅ）の時刻ｔの状態を表している
Ｄｅ[ｋ１][ｋ２]←Ｄｅ[ｋ１][ｋ２]∪Ｘet  ／／Ｘetはリンクｅの時刻ｔの重み（交通需要量）
}
}
Θｅ[ｋ１] [ｋ２]←（Ｄｅ[ｋ１][ｋ２]に含まれるデータＸetの平均値）／／Ｄｅ[ｋ１][ｋ２]が空集合のままの時はデフォルト値を使う
Ｒｅｔｕｒｎ  Θｅ[ｋ１][ｋ２]；
【００７８】
次に、本発明の実施の形態に係るパラメータ学習装置１００の動作について説明する。まず、各プローブカーの車載器は、自車両位置の計測結果を含むプローブデータを、パラメータ学習装置１００へ逐次送信する。
【００７９】
パラメータ学習装置１００は、受信したプローブデータを収集する。また、パラメータ学習装置１００は、図６に示すパラメータ学習処理ルーチンを実行する。
【００８０】
まず、ステップＳ１００において、収集したプローブデータに基づいて、時間変化する重み付き有向グラフのデータに変換する。ステップＳ１０２では、状態格納部１１６に格納されている状態テーブルの各状態を初期化する。
【００８１】
そして、ステップＳ１０４において、繰り返し回数を示す変数ｒを１に初期化する。ステップＳ１０６では、対象時刻ｔを設定し、ステップＳ１０８において、対象ノードｖを設定する。
【００８２】
ステップＳ１１０において、全ての状態ｋの各々について、対象ノードｖを始点ノードとする有向リンクｅの各々に対し、有向リンクｅの重みＸetに対する尤度ｆe（Ｘet｜Θe［ｋ］［Ｚt(e),t］）を計算する。また、全ての状態ｋの各々について、対象ノードｖを終点ノードとする有向リンクｅの各々に対し、有向リンクｅの重みＸetに対する尤度ｆe（Ｘet｜Θe［Ｚb(e),t］［ｋ］）を計算する。
【００８３】
次のステップＳ１１２では、全ての状態ｋの各々について、対象ノードｖにおいて対象時刻ｔに状態ｋに遷移する遷移確率Ｐｖ［ｋ］［Ｚv,t-1］×Ｐｖ［Ｚv,t+1］［ｋ］を計算する。
【００８４】
そして、ステップＳ１１４で、全ての状態ｋの各々について、状態テーブルＺが与えられたときの、対象時刻ｔにおいて対象ノードｖが状態ｋである度合いを示す条件付きスコアＳｃｏｒｅ（ｖ、ｔ、ｋ｜Ｚ）を計算する。ステップＳ１１６では、上記ステップＳ１１４で計算された条件付きスコアＳｃｏｒｅ（ｖ、ｔ、ｋ｜Ｚ）に基づいて、対象時刻ｔにおける対象ノードｖの状態Ｚｖｔを決定し、状態格納部１１６に格納されている状態テーブルＺを更新する。
【００８５】
ステップＳ１１８において、状態格納部１１６に格納されている状態テーブルＺに基づいて、パラメータデータベース１２０に格納されている、対象ノードｖの状態遷移行列Ｐｖを更新する。ステップＳ１２０では、対象ノードを始点ノードとする各有向リンクｅについて、当該有向リンクｅのパラメータ行列Θeを更新する。また、対象ノードｖを終点ノードとする各有向リンクｅについて、当該有向リンクｅのパラメータ行列Θeを更新する。
【００８６】
そして、ステップＳ１２２において、全てのノードについて、上記ステップＳ１０８〜Ｓ１２０の処理を実行したか否かを判定する。上記ステップＳ１０８〜Ｓ１２０の処理を実行していないノードが存在する場合には、上記ステップＳ１０８に戻り、当該ノードを対象ノードとして設定する。一方、全てのノードについて、上記ステップＳ１０８〜Ｓ１２０の処理を実行した場合には、ステップＳ１２４へ進む。
【００８７】
ステップＳ１２４において、全ての時刻について、上記ステップＳ１０６〜Ｓ１２２の処理を実行したか否かを判定する。上記ステップＳ１０６〜Ｓ１２２の処理を実行していない時刻が存在する場合には、上記ステップＳ１０６に戻り、当該時刻を対象時刻として設定する。一方、全ての時刻について、上記ステップＳ１０６〜Ｓ１２２の処理を実行した場合には、ステップＳ１２６へ進む。
【００８８】
ステップＳ１２６では、繰り返し回数ｒが、上限回数Ｒに到達したか否かを判定する。繰り返し回数ｒが、上限回数Ｒに到達していない場合には、ステップＳ１２８において、繰り返し回数ｒを１だけインクリメントして、上記ステップＳ１０６へ戻る。一方、繰り返し回数ｒが、上限回数Ｒに到達した場合には、パラメータ学習処理ルーチンを終了する。
【００８９】
そして、パラメータデータベース１２０に最終的に格納されている状態遷移行列及びパラメータ行列が、交通ネットワーク状態推定装置１０に入力され、パラメータデータベース２０に格納される。
【００９０】
また、各プローブカーの車載器は、自車両位置の計測結果を含むプローブデータを、交通ネットワーク状態推定装置１０へ逐次送信する。
【００９１】
交通ネットワーク状態推定装置１０は、受信したプローブデータを収集する。また、交通ネットワーク状態推定装置１０は、図７に示す状態変化推定処理ルーチンを実行する。
【００９２】
まず、ステップＳ２００において、収集したプローブデータに基づいて、時間変化する重み付き有向グラフのデータに変換する。ステップＳ２０２では、状態格納部１６に格納されている状態テーブルの各状態を初期化する。
【００９３】
そして、ステップＳ２０４において、繰り返し回数を示す変数ｒを１に初期化する。ステップＳ２０６では、対象時刻ｔを設定し、ステップＳ２０８において、対象ノードｖを設定する。
【００９４】
ステップＳ２１０において、全ての状態ｋの各々について、対象ノードｖを始点ノードとする有向リンクｅの各々に対し、有向リンクｅの重みＸetに対する尤度ｆe（Ｘet｜Θe［ｋ］［Ｚt(e),t］）を計算する。また、全ての状態ｋの各々について、対象ノードｖを終点ノードとする有向リンクｅの各々に対し、有向リンクｅの重みＸetに対する尤度ｆe（Ｘet｜Θe［Ｚb(e),t］［ｋ］）を計算する。
【００９５】
次のステップＳ２１２では、全ての状態ｋの各々について、対象ノードｖが対象時刻ｔにおいて状態ｋに遷移する遷移確率Ｐｖ［ｋ］［Ｚv,t-1］×Ｐｖ［Ｚv,t+1］［ｋ］を計算する。
【００９６】
そして、ステップＳ２１４で、全ての状態ｋの各々について、状態テーブルＺが与えられたときの、対象時刻ｔにおいて対象ノードｖが状態ｋである度合いを示す条件付きスコアＳｃｏｒｅ（ｖ、ｔ、ｋ｜Ｚ）を計算する。また、全ての状態ｋの各々について、計算された条件付きスコアＳｃｏｒｅ（ｖ、ｔ、ｋ｜Ｚ）に基づいて、スコアＳｃｏｒｅ（ｖ、ｔ、ｋ）を計算する。
【００９７】
そして、ステップＳ２１６では、上記ステップＳ２１４で計算された条件付きスコアＳｃｏｒｅ（ｖ、ｔ、ｋ｜Ｚ）に基づいて、対象時刻ｔにおける対象ノードｖの状態Ｚｖｔを決定し、状態格納部１１６に格納されている状態テーブルＺを更新する。
【００９８】
ステップＳ２１８において、全てのノードについて、上記ステップＳ２０８〜Ｓ２１６の処理を実行したか否かを判定する。上記ステップＳ２０８〜Ｓ２１６の処理を実行していないノードが存在する場合には、上記ステップＳ２０８に戻り、当該ノードを対象ノードとして設定する。一方、全てのノードについて、上記ステップＳ２０８〜Ｓ２１６の処理を実行した場合には、ステップＳ２２０へ進む。
【００９９】
ステップＳ２２０において、全ての時刻について、上記ステップＳ２０６〜Ｓ２１８の処理を実行したか否かを判定する。上記ステップＳ２０６〜Ｓ２１８の処理を実行していない時刻が存在する場合には、上記ステップＳ２０６に戻り、当該時刻を対象時刻として設定する。一方、全ての時刻について、上記ステップＳ２０６〜Ｓ２１８の処理を実行した場合には、ステップＳ２２２へ進む。
【０１００】
ステップＳ２２２では、繰り返し回数ｒが、上限回数Ｒに到達したか否かを判定する。繰り返し回数ｒが、上限回数Ｒに到達していない場合には、ステップＳ２２４において、繰り返し回数ｒを１だけインクリメントして、上記ステップＳ２０６へ戻る。一方、繰り返し回数ｒが、上限回数Ｒに到達した場合には、ステップＳ２２６へ移行する。
【０１０１】
ステップＳ２２６では、スコア格納部２８に最終的に格納されている時刻ｔ、ノードｖ、状態ｋの組み合わせ毎のスコアＳｃｏｒｅ（ｖ、ｔ、ｋ）に基づいて、状態の変化として、異常な状態が生じている時刻ｔ及びノードｖを検出する。
【０１０２】
そして、ステップＳ２２８では、上記ステップＳ２２６で検出された状態の変化に基づいて、将来の状態の変化を予測する。ステップＳ２３０では、上記ステップＳ２２８で予測された結果を、車載器に対して配信し、状態変化推定処理ルーチンを終了する。
【０１０３】
以上説明したように、本発明の実施の形態の交通ネットワーク状態推定装置によれば、状態テーブルＺ、有向エッジｅの各々についてのパラメータ行列、ノードｖの各々に対する状態遷移行列、及び各有向エッジｅの各時刻ｔの交通需要量に基づいて、ノードｖ、状態ｋ、及び時刻ｔの組み合わせの各々について、時刻ｔのノードｖの状態Ｚvtが状態ｋである度合いを表す条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）を算出することと、条件付きスコアＳｃｏｒｅ（ｖ，ｔ，ｋ｜Ｚ）に基づいて、状態テーブルＺを更新することを繰り返し、ノードｖ、状態ｋ、及び時刻ｔの組み合わせの各々について繰り返し算出されたスコアＳｃｏｒｅ（ｖ，ｔ，ｋ）に基づいて、ノードｖの状態の変化を推定することにより、道路ネットワーク上のノードの状態の変化を精度よく推定することができる。
【０１０４】
算出されるスコアＳｃｏｒｅ（ｖ，ｔ，ｋ）は、道路ネットワーク上で交通需要量が観測された瞬間に、それぞれのノードがどの状態に属しているかの確率に比例する量になっている。「状態」と呼んでいるのは、例えば、「通常のフローパターン」や「スタジアムで試合があるときのフローパターン」などの分類に対応する。このスコアは、ノード間で依存関係をもっている（独立ではない）ため、計算することは容易ではないが、上記の擬似コードに示したアルゴリズムにより、このスコアの算出を可能とする。また、一旦、このスコアが求まれば、「スタジアムで試合がありそうだ」などということが推論可能となる。
【０１０５】
また、条件付きスコアの算出式において、前後の時刻からの状態遷移確率を考慮するため、状態（イベント）が時間的に連続しやすいなどの知識を、状態変化の検出時に考慮していることになり、ノイズに対する頑強性が向上する。また、リンク重みに対する尤度は、ノードがその状態に所属するときに、有向リンクの重みが観測される確率になっている。したがって、状態遷移確率と重みに対する尤度の積は「前後の時刻の状態と現在の観測されたリンク重み」が与えられた時の「現在の状態」の確率分布になっている。
【０１０６】
この条件付きスコアに基づくスコアを「ノード（エリア）ごと」に計算するため、局所的な状態の変化を検出することができる。また、状態の時間変化や接続ノードとの関係性を確率値としてスコアに考慮しているため、データの「ゆらぎ」を考慮することが可能であり、上記の特許文献１に記載された固有ベクトルに基づく非確率的な手法と比較して、ノイズに対する頑強性が向上する。
【０１０７】
また、時間変化する重み付きの有向グラフに対して、ノード間のつながり（相互作用）から生じる局所的な状態変化を、ノイズに対して頑強に検出することができる。複数のノードで同時に状態変化が生じた場合でも、どのノードで状態変化が生じたのかを切り分けて検出することができる。有向リンクの重みが、交通需要量である場合には、これはエリアごとの状態（イベント）などが検出されることに対応している。
【０１０８】
なお、上記の実施の形態では、パラメータ学習装置のパラメータ更新部によるパラメータ行列の更新は、確率分布のパラメータを最尤推定することに対応している。パラメータ行列の更新方法は自由度が高いため、ベイズ推定なども利用して、パラメータ行列の更新を行ってもよい。ベイズ推定を利用する場合には、パラメータ更新部によるパラメータ行列の更新おける擬似コードで、「Θｅ[ｋ１][ｋ２]←（Ｄｅ[ｋ１][ｋ２]に含まれるデータＸｅｔの平均値）」の部分について、Ｄｅ[ｋ１][ｋ２]というデータ集合が与えられた時のポアソン分布のベイズ推定を行うように置き換えればよい。
【０１０９】
また、各有向リンクの出力分布がポアソン分布以外の場合であっても、その出力分布に対して、データ集合Ｄｅ[ｋ１][ｋ２]による最尤推定（もしくはベイズ推定）を行えばよい。
【０１１０】
また、複数のノードｖ間を有向エッジｅで結んだネットワークにおける各有向エッジｅの各時刻ｔのフロー量として、ノード＝地点、リンク重み（フロー量）＝交通需要量、出力分布＝ポアソン分布のパラメータとする場合を例に説明したが、これに限定されるものではなく、上記のフロー量、ノード、有向リンクの三要素を変更することで様々なネットワークフローを取り扱うことができる。
【０１１１】
例えば、サーバネットワークにおけるノード（サーバ）間の有向リンクの各時刻ｔのフロー量として、サーバ間のトラフィック（正の実数値）を入力し、サーバのトラフィックを監視し、異常の検出などを行うようにしてもよい。この場合には、出力分布を、対数正規分布（正の実数値を発生させる分布）とし、パラメータ行列の要素を、対数正規分布のパラメータとすればよい。
【０１１２】
また、コミュニケーション（ＳＮＳ）におけるノード（人）間の有向リンクの各時刻ｔのフロー量として、会話の回数（整数値）を入力し、チャットのパターンの分類および抽出を行うようにしてもよい。この場合には、出力分布を、ポアソン分布とし、パラメータ行列の要素を、ポアソン分布のパラメータとすればよい。
【０１１３】
また、サプライチェーンにおけるノード（企業）間の有向リンクの各時刻ｔのフロー量として、取引金額（正の実数値）を入力し、取引関係の変化の検出を行うようにしてもよい。この場合には、出力分布を、対数正規分布（正の実数値を発生させる分布）とし、パラメータ行列の要素を、対数正規分布のパラメータとすればよい。
【０１１４】
また、道路ネットワークにおけるノード（交差点）間の有向リンクの各時刻ｔのフロー量として、交差点間の所要時間（正の実数値）を入力し、渋滞のパターン分類又は異常パターンの発見を行うようにしてもよい。この場合には、出力分布をガンマ分布（正の実数値を発生させる分布）とし、パラメータ行列の要素をガンマ分布のパラメータとすればよい。
【符号の説明】
【０１１５】
１０   交通ネットワーク状態推定装置
１２   プローブデータ収集部
１４   プローブデータ変換部
１６   状態格納部
１８   状態初期化部
２０   パラメータデータベース
２２   尤度計算部
２４   遷移確率計算部
２６   スコア計算部
２８   スコア格納部
３０   状態更新部
３２   反復判定部
３４   変化検出用データベース
３６   変化検出部
３８   変化予測部
４０   情報配信部
１００ パラメータ学習装置
【図１】
2015064765.tif 000004
【図２】
2015064765.tif 000005
【図３】
2015064765.tif 000006
【図４】
2015064765.tif 000007
【図５】
2015064765.tif 000008
【図６】
2015064765.tif 000009
【図７】
2015064765.tif 000010