(57)【特許請求の範囲】
【請求項１】
現在の交通状況に基づき、将来の交通状況を予測する交通状況予測方法であって、
節点が交通状況を決定する属性のテストに対応し、葉が予測値である決定木を構築するための交通データを収集し、該交通データから、交通渋滞を説明する要因になると考えられる各属性の観測値である条件部と、該条件部の観測値が得られてからある時間後の交通渋滞レベルである結果部からなるトレーニングデータを予測対象道路全てに対して道路ごとおよび何分先を予測するかという予測時間毎に作成するステップと、
作成されたトレーニングデータを用いて、予測対象道路全てに対して道路ごとおよび何分先を予測するかという予測時間毎に決定木を構築するステップと、
予測に必要な交通データを収集するステップと、
構築された決定木を、前記の収集された、予測に必要な交通データでたどって交通情報の予測値を得るステップと
を有する交通状況予測方法。
【請求項２】
前記決定木を構築するステップは、与えられたトレーニングデータ集合全体における情報エントロピーと、ある属性をテストする仮定とした場合の情報エントロピーとの差分を情報ゲインとする、情報エントロピーに基づく手法を用い、前記情報ゲインが最も大きくなる属性を選択していくことで決定木を構築する、請求項１記載の交通状況予測方法。
【請求項３】
現在の交通状況に基づき、将来の交通状況を予測する交通状況予測装置であって、
節点が交通状況を決定する属性のテストに対応し、葉が予測値である決定木を構築するための交通データを収集し、該交通データから、交通渋滞を説明する要因になると考えられる各属性の観測値である条件部と、該条件部の観測値が得られてからある時間後の交通渋滞レベルである結果部からなるトレーニングデータを予測対象道路全てに対して道路ごとおよび何分先を予測するかという予測時間毎に作成する決定木構築用データ収集手段と、
作成されたトレーニングデータを用いて、予測対象道路全てに対して道路ごとおよび何分先を予測するかという予測時間毎に決定木を構築する決定木構築手段と、
予測に必要な交通データを収集する予測用データ収集手段と、
作成されたトレーニングデータ、構築された決定木、収集された予測用交通データを記憶する記憶手段と、
構築された決定木を、前記の収集された、予測に必要な交通データでたどって交通情報の予測値を得る交通情報予測手段と
を有する交通状況予測装置。
【請求項４】
前記決定木構築手段は、与えられたトレーニングデータ集合全体における情報エントロピーと、ある属性をテストする仮定とした場合の情報エントロピーとの差分を情報ゲインとする、情報エントロピーに基づく手法を用い、前記情報ゲインが最も大きくなる属性を選択していくことで決定木を構築する、請求項３記載の交通状況予測装置。
【請求項５】
請求項１または２に記載の交通状況予測方法をコンピュータに実行させるための交通状況予測プログラム。
【請求項６】
請求項１または２に記載の交通状況予測方法をコンピュータに実行させるための交通状況予測プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、現在の交通状況をもとに将来の交通状況を予測する交通状況予測方法および装置に関するものである。
【０００２】
【従来の技術】
従来の交通状況予測方法では、連続量である交通量、旅行時間（所要時間）等に対し、その時系列データを取得し、その時系列変化を種々の曲線に当てはめて学習させ、学習した曲線に基づき予測していた。
【０００３】
これらの手法は、基本的に入力、出力とも連続量である場合を対象としており、渋滞レベルデータなどの不連続量や、祝祭日、五十日などの非数値要因に対してはそのままでは使用できない、という問題があった。ここで、渋滞レベルデータとは、ある道路に対し、どの部分がどの程度渋滞しているかを表すもので、例えば「渋滞」、「混雑」、「非渋滞」などの渋滞を表すレベルで表現される。
【０００４】
前記問題を解決する一手法として、特願平１１―３７０１８がある。特願平１１―３７０１８の手法は、交通状況を説明する非数値要因を数値化することによって問題を解決するものである。
【０００５】
しかしこの手法は、非数値要因を一度数値化するため、処理の手間がかかってしまい交通状況を予測するまでの時間が遅くなる、数値化の際に本来の意味が失われてしまう、といった問題があった。
【０００６】
【発明が解決しようとする課題】
渋滞状況を決定する要因として、祝祭日、五十日などの非数値的、非周期的要因が問題となることは多い。例えばオフィス街においては平日は非常に渋滞し、祝祭日はあまり渋滞しないことはよく知られている。また、渋滞状況を表す量としても、渋滞レベルなどの非連続量が使われることがある。渋滞レベルとは、どの程度渋滞しているかを表す量で、一般にはその場所を通過する車両の平均速度を２〜３段階に離散化して使用される場合が多い。例えば、ＡＴＩＳ（Ａｄｖａｎｃｅｄ  Ｔｒａｆｆｉｃ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｒｖｉｃｅ）  、ＶＩＣＳ  （Ｖｅｈｉｃｌｅ  Ｉｎｆｏｒｍａｔｉｏｎ  ａｎｄ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ  Ｓｅｒｖｉｃｅ）  などがカーナビ等に提供する情報には、この渋滞レベル情報が含まれている。
【０００７】
このように、交通渋滞状況を予測する際には、その説明変数、非説明変数ともに非連続、あるいは非数値量が問題となる場合が多い。
【０００８】
しかし、上述のように、従来の方法では非連続、非数値量を直接使用できないため、そもそも予測が不可能だったり、予測精度の低下などを招いていた。また、非連続、非数値量を一旦数値化してから予測を行っていたため、処理時間の増大、数値化による情報量の欠落による予測精度の低下などを招いていた。
【０００９】
本発明の目的は、正確で処理時間の短い交通状況予測方法、装置、交通状況予測プログラム、および該プログラムを記録した記録媒体を提供することにある。
【００１０】
【課題を解決するための手段】
上記目的を達成するために、本発明は、節点が交通状況を決定する属性のテストに対応し、葉が予測値である決定木を構築するための交通データを収集し、該交通データから、交通渋滞を説明する要因になると考えられる各属性の観測値である条件部と、該条件部の観測値が得られてからある時間後の交通渋滞レベルである結果部からなるトレーニングデータを予測対象道路全てに対して道路ごとおよび何分先を予測するかという予測時間毎に作成し、作成されたトレーニングデータを用いて、予測対象道路全てに対して道路ごとおよび何分先を予測するかという予測時間毎に決定木を構築し、予測に必要な交通データを収集し、構築された決定木を、前記の収集された、予測に必要な交通データでたどって交通情報の予測値を得るものである。
【００１１】
交通状況を予測する決定木を構築することで非数値、非連続な、交通状況を説明する要因をそのまま高速に扱うことが可能となり、交通状況を高速、かつ正確に予測することができる。
【００１２】
【発明の実施の形態】
次に、本発明の実施の形態について図面を参照して説明する。
【００１３】
図１は本発明の一実施形態の交通状況予測装置のブロック図、図２はその全体の処理を示すフローチャートである。
【００１４】
なお、本発明の前提として、サービス対象道路の交通渋滞レベルデータ等の各種交通情報は、ＡＴＩＳ、ＶＩＣＳ等の交通情報センタ等を通じて収集することが可能であるとする。
【００１５】
また、本実施形態では、交通状況予測方法の一例として、交通渋滞レベルデータを予測する場合について示す。交通渋滞レベルは、ある道路に対し数十〜数百メートルおきに置かれた測定点で測定され、渋滞なし（０）、混雑（１）、渋滞（２）の３つのレベルを持つこととする。すなわち、ある道路の渋滞状況は、０，１，２の羅列で表現でき、例えば、“００１１２２００”のようになる。これは１つの道路の８個所の測定点の渋滞レベルを示している。
【００１６】
まず、交通渋滞レベル予測に用いる決定木について述べる。前記決定木とは、例えば図３のように、１つの節点が１つの属性のテストに対応し、前記節点の子節点が前記属性の取り得る値に対応し、葉が予測値である木構造のことである。決定木は、予測対象道路全てに対し、道路ごとおよび何分先を予測するかという予測時間毎に作成する。予測する際には、このような決定木を根節点から順にたどっていくことで予測値を決定する。図３の例において、例えば、月曜日の１２：００における予測値を算出する場合を以下に示す。まず、根節点３０１において曜日の属性値がテストされ、月曜日であるから、次の節点３０２に進む。節点３０２において時刻の属性値がテストされ、葉３０３に進み、予測値“００１１２２００”が決定される。このように、決定木を用いて交通状況を予測する場合は一度決定木を構築した後ならば、非常に高速な予測が可能となる。
【００１７】
まず、ステップ２０１において、決定木構築用データ収集部１０１はＡＴＩＳ、ＶＩＣＳ等の交通情報センタ（図示せず）を通じて交通状況を決定する要因なると思われるデータを収集し、予測対象道路全てに対して、決定木を構築するためのトレーニングデータ４０１を作成し、記憶部１０５に保存する。
【００１８】
決定木を構築するためのトレーニングデータ４０１は、道路ごと、および何分先を予測するかという予測先時間毎に作成する。トレーニングデータ４０１は、図４のように、条件部４１０と結果部４２０に分けられる。条件部４１０とは、交通渋滞を説明する要因となると考えられる各属性の観測値である。例えば、説明要因として曜日、時刻、過去の渋滞状況という属性を採用する場合は、図４のようになる。また、結果部４２０とは、その結果ｎ分後の交通レベルがどのようになったかを示す値である。図４のようなトレーニングデータ４０１をある学習期間（決定木を構築する期間）分だけ作成する。
【００１９】
次に、ステップ２０２において、決定木構築部１０２により決定木を構築し、記憶部１０５に保存する。決定木を構築する手法はいくつか考えられるが、ここでは例として情報エントロピーに基づく構築手法を用いることとする。この構築手法は、例えば、Ｊ．  Ｒｏｓｓｑｕｉｎｌａｎ，  “Ｃ４．５：Ｐｒｏｇｒａｍｓ  ｆｏｒ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ  （Ｍｏｒｇａｎ  Ｋａｕｆｍａｎｎ  Ｓｅｒｉｅｓ  ｉｎ  Ｍａｃｈｉｎｅ  Ｌｅａｒｎｉｎｇ）”，Ｍｏｒｇａｎｎ  Ｋａｕｆｍａｎｎ  Ｐｕｂｌｉｓｈｅｒｓ．に記載されている。具体的手法を以下に示す。
【００２０】
まず、デフォルトの予測値として、トレーニングデータ４０１の結果部４０２全体における最頻値を予め計算する。次に、決定木を根節点から順に再帰的に作成していく（決定木作成アルゴリズムを再帰呼び出しする）。作成アルゴリズムの一例をに示す。以下、与えられたトレーニングデータ４０１の集合をＴとし、｜Ｔ｜はトレーニングデータ集合Ｔの総数とする。また、根節点においては全てのトレーニングデータ集合Ｔが与えられるものとする。
【００２１】
決定木作成アルゴリズム：
ある節点に注目しているものとして、
１．与えられたトレーニングデータ集合Ｔが空ならば当該節点をデフォルト値を与える葉とする。
２．与えられたトレーニングデータ集合Ｔの結果部４２０が全て同じ値ならば、当該節点をその値を与える葉とする。
３．属性が全てテスト済み、すなわち根から順にテストすべき属性が決まっていき、全ての属性をテストし終わったならば、当該節点を与えられたトレーニングデータ集合のＴの結果部４２０の最頻値を与える葉とする。
４．上記のいずれでもないならば、情報ゲインが最も大きくなるように、当該節点でテストすべき属性を決定する。その後、決定した属性の取り得る値に対応する子節点をそれぞれ作成し、トレーニングデータ集合Ｔを属性Ｘの値にしたがいＴｉ，（ｉ＝１，・・・・，ｋ）に分割して各子節点に与え、各子節点において決定木作成アルゴリズムを実行する。
【００２２】
ここで４．の情報ゲインの算出方法に関して詳細に示す。情報ゲインとは、与えられたトレーニングデータ集合Ｔ全体における情報エントロピーと、ある属性Ｘをテストすると仮定した場合の情報エントロピーとの差分であり、以下のように定義される。
【００２３】
【数１】
0003628616.tif 000002
【００２４】
ここで、ｉｎｆｏ（Ｔ）は与えられたトレーニングデータ集合Ｔにおける情報エントロピーを表し、
【００２５】
【数２】
0003628616.tif 000003
【００２６】
で与えられる。ｎはトレーニングデータ集合Ｔの結果部４２０が取り得る値の種類数、Ｔｃは結果部４２０の値がｃ番目の値となるトレーニングデータ集合Ｔである。また、ｉｎｆｏｘ（Ｔ）は、当該節点においてある属性Ｘをテストしたと仮定した場合の情報エントロピーを表す。
【００２７】
属性Ｘのテスト後は、トレーニングデータ集合Ｔが属性Ｘの値によって分割されるので、エントロピーは
【００２８】
【数３】
0003628616.tif 000004
【００２９】
で与えられる。ここで、ｋは属性Ｘが取り得る値の種類数、Ｔｉは属性Ｘの値がｉ番目の値であるトレーニングデータ集合Ｔである。
【００３０】
上記のようにして情報ゲインが算出される。情報ゲインは属性Ｘのテストによってトレーニングデータ集合Ｔがいかにうまく分割されたかを示すものであり、情報ゲインが最も大きくなる属性Ｘを選択していくことで、予測精度の高い決定木を構築していくことが可能となる。
【００３１】
次に、ステップ２０３において、予測用交通データ収集部１０３により予測に必要な交通データ、つまり決定木構築用データ４０１の条件部４１０に相当する部分の現在の値を収集し、記憶部１０５に保存する。
【００３２】
最後に、ステップ２０４において、交通状況予測部１０４により記憶部１０５に記憶されている決定木を用いて、決定木に関する説明の箇所で述べたようにして交通状況の予測を行う。
【００３３】
ところで、本実施形態では決定木の構築方法として情報ゲインを用いる手法を述べたが、他にも情報ゲインと分割情報量との比を用いる手法、一度構築した決定木を予測誤り率が減少するよう枝刈する手法等も考えられ、決定木を構築する手法は本実施形態に限定されない。
【００３４】
また、本実施形態では、説明要因とし曜日、時刻、過去の渋滞状況を採用した場合について述べたが、他にも月、五十日、天候等も考えられ、説明要因として何を採用するかは本実施形態に限定されない。
【００３５】
さらに、本実施形態では、交通状況として交通渋滞レベルデータを予測したが、この他にも旅行時間、交通量なども考えられ、交通状況として何を予測するかは本実施形態に限定されない。
【００３６】
図５は本発明の他の実施形態の交通情報予測装置の構成図である。
【００３７】
通信装置５０１は、ＡＴＩＳ、ＶＩＣＳ等の交通情報センタから、交通状況を決定する要因になると思われるデータを受信する。記憶装置５０２は、収集したデータ、構築された決定木等の各種データおよびプログラムを記憶する。表示装置５０３は得られた交通情報予測値等を表示する。記録媒体５０４は、フロッピィ・ディスク、ＣＤ―ＲＯＭ、光磁気ディスク、ＤＶＤ等で、図２の各ステップからなる交通状況予測プログラムが格納されている。データ装置５０５はＣＰＵ、各種インタフェースを含み、記録媒体５０４から交通状況予測プログラムを読み込み、これを実行する。
【００３８】
【発明の効果】
以上説明したように、本発明によれば、交通状況を予測する決定木を構築、利用することで、非数値、非連続な、交通状況を説明する要因から、高速かつ正確に交通状況を予測できる。
【図面の簡単な説明】
【図１】本発明の一実施形態の交通状況予測装置の構成図である。
【図２】図１の交通状況予測装置の処理の流れを示すフローチャートである。
【図３】決定木の一例を示す図である。
【図４】トレーニングデータの一例を示す図である。
【図５】本発明の他の実施形態の交通状況予測装置の構成図である。
【符号の説明】
１０１    決定木構築用データ収集部
１０２    決定木構築部
１０３    予測用交通データ収集部
１０４    交通状況予測部
１０５    記憶部
２０１〜２０４    ステップ
３０１    根節点
３０２    節点
３０３，３０４    葉
４０１    トレーニングデータ
４１０    条件部
４２０    結果部
５０１    通信装置
５０２    記憶装置
５０３    表示装置
５０４    記録媒体
５０５    データ処理装置
【図１】
0003628616.tif 000005
【図２】
0003628616.tif 000006
【図３】
0003628616.tif 000007
【図４】
0003628616.tif 000008
【図５】
0003628616.tif 000009