(57)【特許請求の範囲】
【請求項１】
ユーザ群のユーザの各々の移動経路を蓄積して、特定ユーザに適した経路を探索する経路探索装置であって、
前記ユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データを記憶するユーザ移動履歴データ記憶部と、
前記ユーザ群のユーザの各々についてのユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記ユーザ群のユーザの各々についての特徴を表すユーザ特徴データ、又は前記リンクの各々についての特徴を表すリンク特徴データを求める移動履歴処理部と、
前記移動履歴処理部によって求められた前記ユーザ特徴データ、又は前記リンク特徴データに基づいて、前記特定ユーザに適したリンクからなる経路を探索する経路探索部と、
を含む経路探索装置。
【請求項２】
ユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データを記憶するユーザ移動履歴データ記憶部と、
前記ユーザ群のユーザの各々についてのユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記ユーザ群のユーザの各々についての特徴を表すユーザ特徴データを求める移動履歴処理部と、
を含むユーザ特徴データ作成装置。
【請求項３】
ユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データを記憶するユーザ移動履歴データ記憶部と、
前記ユーザ群のユーザの各々についてのユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記リンクの各々についての特徴を表すリンク特徴データを求める移動履歴処理部と、
を含むリンク特徴データ作成装置。
【請求項４】
ユーザ群のユーザの各々の移動経路を蓄積して、特定ユーザに適した経路を探索する経路探索装置における経路探索方法であって、
移動履歴処理部が、ユーザ移動履歴データ記憶部に記憶されている、前記ユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記ユーザ群のユーザの各々についての特徴を表すユーザ特徴データ、又は前記リンクの各々についての特徴を表すリンク特徴データを求めるステップと、
経路探索部が、前記移動履歴処理部によって求められた前記ユーザ特徴データ、又は前記リンク特徴データに基づいて、前記特定ユーザに適したリンクからなる経路を探索するステップと、
を含む経路探索方法。
【請求項５】
移動履歴処理部が、ユーザ移動履歴データ記憶部に記憶されている、ユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記ユーザ群のユーザの各々についての特徴を表すユーザ特徴データを求めるステップ、
を含むユーザ特徴データ作成方法。
【請求項６】
移動履歴処理部が、ユーザ移動履歴データ記憶部に記憶されている、ユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記リンクの各々についての特徴を表すリンク特徴データを求めるステップ、
を含むリンク特徴データ作成方法。
【請求項７】
コンピュータを、請求項１に記載の経路探索装置の各部として機能させるためのプログラム。
【請求項８】
コンピュータを、請求項２に記載のユーザ特徴データ作成装置の各部として機能させるためのプログラム。
【請求項９】
コンピュータを、請求項３に記載のリンク特徴データ作成装置の各部として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、経路探索装置、ユーザ特徴データ作成装置、リンク特徴データ作成装置、方法、及びプログラムに係り、特に、ユーザに適した経路を探索するための経路探索装置、ユーザ特徴データ作成装置、リンク特徴データ作成装置、方法、及びプログラムに関する。
【背景技術】
【０００２】
従来より、歩行者向けのナビゲーションシステムにおいて、ルート検索を行うに当たって、ユーザの移動能力の差異を考慮したルート検索が行われている。このようなルート検索においては、ユーザ自身に「健常者」、「車イス」、「ベビーカー」等のカテゴリ（属性）を入力させて、あらかじめ調査したルートの属性と、入力されたユーザのカテゴリが合致するようにルート検索を行っている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】松田 三恵子，杉山 博史，土井 美和子，「歩行者の経路への嗜好を反映した経路生成」，電子情報通信学会論文誌. A,基礎・境界 J87-A(1),132-139,2004-01-01
【発明の概要】
【発明が解決しようとする課題】
【０００４】
もっとも、「車イス」ユーザであっても、電動車イスか手動車イスかで走破能力は異なる。また手動車イスであってもユーザの運動能力に差がある。また、「健常者」であっても体力・脚力に差があって多少遠回りでも、階段よりエレベータやエスカレータを好むユーザもいる。
【０００５】
このようなユーザの多様性に従来の技術で対応すると、ユーザに入力させるカテゴリの分類が多岐にわたってしまい、ユーザによる適切な選択は困難であるといった課題が存在する。
【０００６】
また、上記多様なカテゴリの分類によって、特定の経路断片（以降リンク）を経路探索結果に含めるのか含めないのかを決定づけるための経路属性情報を、経路探索対象のリンクについて調査し、保持することが必要である。しかし、この場合には、あらかじめ調査したカテゴリに基づく経路探索しかできない、という課題が存在する。例えば、歩道の幅、路面状況、傾斜を調査していたとすると、十分な幅があって傾斜の緩やかで凹凸の少ない経路をユーザが好むといった要望には対処可能だが、ビル風の少ない経路、街灯の整備されている経路、雰囲気のいい経路といった好みには対応できない、という課題が生じる。
【０００７】
本発明は、上記事情を鑑みて成されたものであり、ユーザが移動しない経路を考慮して、ユーザに適した経路を探索することができる経路探索装置、方法、及びプログラムを提供することを目的とする。
【０００８】
また、ユーザが移動しない経路を考慮して、ユーザ特徴データを作成することができるユーザ特徴データ作成装置、方法、及びプログラムを提供することを目的とする。
【０００９】
また、ユーザが移動しない経路を考慮して、リンク特徴データを作成することができるリンク特徴データ作成装置、方法、及びプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記目的を達成するために、第１の発明に係る経路探索装置は、ユーザ群のユーザの各々の移動経路を蓄積して、特定ユーザに適した経路を探索する経路探索装置であって、前記ユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データを記憶するユーザ移動履歴データ記憶部と、前記ユーザ群のユーザの各々についてのユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記ユーザ群のユーザの各々についての特徴を表すユーザ特徴データ、又は前記リンクの各々についての特徴を表すリンク特徴データを求める移動履歴処理部と、前記移動履歴処理部によって求められた前記ユーザ特徴データ、又は前記リンク特徴データに基づいて、前記特定ユーザに適したリンクからなる経路を探索する経路探索部と、を含んで構成されている。
【００１１】
また、第２の発明に係るユーザ特徴データ作成装置は、複数のカテゴリに分類されたユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データを記憶するユーザ移動履歴データ記憶部と、前記ユーザ群のユーザの各々についてのユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記ユーザ群のユーザの各々についての特徴を表すユーザ特徴データを求める移動履歴処理部と、を含んで構成されている。
【００１２】
また、第３の発明に係るリンク特徴データ作成装置は、複数のカテゴリに分類されたユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データを記憶するユーザ移動履歴データ記憶部と、
【００１３】
前記ユーザ群のユーザの各々についてのユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記リンクの各々についての特徴を表すリンク特徴データを求める移動履歴処理部と、を含んで構成されている。
【００１４】
第４の発明に係る経路探索方法は、ユーザ群のユーザの各々の移動経路を蓄積して、特定ユーザに適した経路を探索する経路探索装置における経路探索方法であって、移動履歴処理部が、ユーザ移動履歴データ記憶部に記憶されている、前記ユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記ユーザ群のユーザの各々についての特徴を表すユーザ特徴データ、又は前記リンクの各々についての特徴を表すリンク特徴データを求めるステップと、経路探索部が、前記移動履歴処理部によって求められた前記ユーザ特徴データ、又は前記リンク特徴データに基づいて、前記特定ユーザに適したリンクからなる経路を探索するステップと、を含んで実行することを特徴とする。
【００１５】
また、第５の発明に係るユーザ特徴データ作成方法は、移動履歴処理部が、ユーザ移動履歴データ記憶部に記憶されている、ユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記ユーザ群のユーザの各々についての特徴を表すユーザ特徴データを求めるステップ、を含んで実行することを特徴とする。
【００１６】
また、第６の発明に係るリンク特徴データ作成方法は、移動履歴処理部が、ユーザ移動履歴データ記憶部に記憶されている、ユーザ群のユーザの各々について、前記ユーザの移動経路から得られる、ネットワークデータ上の前記ユーザが移動したリンクを表すユーザ移動履歴データに基づいて、前記ユーザ群を複数のカテゴリに分類し、前記ユーザ群のユーザの各々について、前記ユーザが移動したリンクと、前記ユーザが移動しなかったリンクであって、前記ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、前記マトリクスの因子分析を行って、前記リンクの各々についての特徴を表すリンク特徴データを求めるステップ、を含んで実行することを特徴とする。
【００１７】
また、第７の発明に係るプログラムは、コンピュータを、第１の発明に係る経路探索装置、第２の発明に係るユーザ特徴データ作成装置、又は第３の発明に係るリンク特徴データ作成装置の各部として機能させるためのプログラムである。
【発明の効果】
【００１８】
本発明の経路探索装置、方法、及びプログラムによれば、ユーザ群のユーザの各々についてのユーザ移動履歴データに基づいて、ユーザ群を複数のカテゴリに分類し、ユーザ群のユーザの各々について、ユーザが移動したリンクと、ユーザが移動しなかったリンクであって、ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、マトリクスの因子分析を行って、ユーザ群のユーザの各々についての特徴を表すユーザ特徴データ、又はリンクの各々についての特徴を表すリンク特徴データを求め、ユーザ特徴データ、又はリンク特徴データに基づいて、特定ユーザに適したリンクからなる経路を探索することにより、ユーザが移動しない経路を考慮して、ユーザに適した経路を探索することができる、という効果が得られる。
【００１９】
また、本発明のユーザ特徴作成装置、方法、及びプログラムによれば、ユーザ群のユーザの各々についてのユーザ移動履歴データに基づいて、ユーザ群を複数のカテゴリに分類し、ユーザ群のユーザの各々について、ユーザが移動したリンクと、ユーザが移動しなかったリンクであって、ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、マトリクスの因子分析を行って、ユーザ群のユーザの各々についての特徴を表すユーザ特徴データを求めることにより、ユーザが移動しない経路を考慮して、ユーザ特徴データを作成することができる、という効果が得られる。
【００２０】
また、本発明のリンク特徴作成装置、方法、及びプログラムによれば、ユーザ群のユーザの各々についてのユーザ移動履歴データに基づいて、ユーザ群を複数のカテゴリに分類し、ユーザ群のユーザの各々について、ユーザが移動したリンクと、ユーザが移動しなかったリンクであって、ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、マトリクスの因子分析を行って、リンクの各々についての特徴を表すリンク特徴データを求めることにより、ユーザが移動しない経路を考慮して、リンク特徴データを作成することができる、という効果が得られる。
【図面の簡単な説明】
【００２１】
【図１】本発明の実施の形態に係る経路探索装置の構成を示すブロック図である。
【図２】ネットワークデータのノード及びリンクの一例を示す図である。
【図３】ユーザ移動履歴データの一例を示す図である。
【図４】リンク特徴データの一例を示す図である。
【図５】ユーザ特徴データの一例を示す図である。
【図６】ユーザ・（移動リンク＋忌避リンク）のマトリクスの一例を示す図である。
【図７】本発明の実施の形態に係る経路探索装置における特徴抽出処理ルーチンを示すフローチャートである。
【図８】本発明の実施の形態に係る経路探索装置における経路探索処理ルーチンを示すフローチャートである。
【発明を実施するための形態】
【００２２】
以下、図面を参照して本発明の実施の形態を詳細に説明する。
【００２３】
＜本発明の実施の形態に係る概要＞
【００２４】
まず、本発明の実施の形態における概要を説明する。
【００２５】
例えば特定ユーザをユーザＡとすると、ユーザＡの移動履歴から、ユーザＡが多くのリンクを走破した地理範囲において、他のユーザの移動履歴を参照し、ユーザＡの走破したリンクを多く共通に持つ他のユーザからなるユーザ群を特定する。
【００２６】
当該ユーザ群において多数のユーザに共通に走破されているが、ユーザＡが通らないリンクをユーザＡが意図的に忌避したリンクと推定する。
【００２７】
その上で以下の（ａ）、（ｂ）、及び（ｃ）の手法を利用する。
【００２８】
（ａ）：ユーザ・（走破済（移動）リンク＋忌避リンク）の行列をユーザ・アイテム行列としたユーザベースの協調フィルタを利用する。
【００２９】
（ｂ）：ユーザが走破したリンクとユーザが忌避したリンクの属性の特徴によりアイテムベースの協調フィルタを利用する。
【００３０】
（ｃ）：（ｂ）のフィルタによってユーザＡと類似のユーザを抽出し、経路探索におけるリンクのコスト計算に類似ユーザによる走破履歴を反映させる。
【００３１】
協調フィルタリングの類似度計算には、一般的に利用されるユークリッド距離やピアソン相関係数を用いてもよいし、その他どのような方法を用いても本発明の実施の形態の本質に関係しない。
【００３２】
＜本発明の実施の形態に係る経路探索システムの構成＞
【００３３】
次に、本発明の実施の形態に係る経路探索システムの構成について説明する。図１に示すように、経路探索システム１は、ネットワーク１５０と、経路探索装置２００と、クライアント端末３００１〜Ｎとから構成されている。経路探索装置２００と、クライアント端末３００１〜Ｎとは、ネットワーク１５０を介して相互に通信可能に接続されている。
【００３４】
まず、クライアント端末３００１〜Ｎの各部について説明する。
【００３５】
クライアント端末３００１〜Ｎ（以下、一つのクライアント端末に着目した場合をクライアント端末３００と記載する）はそれぞれ、通信部１３と、ユーザ位置収集部３１と、経路探索ＵＩ３２とを備えている。ユーザ位置収集部３１は、ＧＰＳや無線ＬＡＮロケーションに代表される位置測定技術によって、クライアント端末３００を操作するユーザの現時点の位置を測定し、測定した位置からなる移動経路を、ユーザの識別情報（例えば、「健常者」、「車イス」、「ベビーカー」等のカテゴリ情報）と共に、通信部１３を介して経路探索装置２００に送信する機能を備えている。位置測定は一定時間毎に測定するのでもよいし加速度センサを合わせて備えてユーザの進行方向の変化を検出した時点での位置測定を行うのも好ましい。経路探索装置２００への移動経路の送信についてはユーザ位置収集部３１から送信手続きを開始するのでもよいし、経路探索装置２００からの要求に従って通信を行うようにしてもかまわない。なお、クライアント端末３００を操作するユーザの何れかが、特定ユーザの一例である。
【００３６】
経路探索ＵＩ３２は、クライアント端末３００を操作するユーザの現時点の位置及び目的地を、ユーザの識別情報と共に、通信部１３を介して経路探索装置２００に送信する。そして、経路探索装置２００で探索されたユーザに適したリンクからなる目的地までの経路を受け付け、ディスプレイ上に表示する等してユーザに提示する。
【００３７】
経路探索装置２００は、ＣＰＵと、ＲＡＭと、後述する特徴抽出処理ルーチン及び経路探索処理ルーチンを実行するためのプログラムや各種データを記憶したＲＯＭと、を含むコンピュータで構成することが出来る。この経路探索装置２００は、機能的には図１に示すように通信部１２と、演算部２０とを備えている。
【００３８】
演算部２０は、移動リンク特定部２１と、移動履歴処理部２２と、経路探索部２３と、ＮＷデータ記憶部４０と、ユーザ移動履歴データ記憶部４１と、リンク特徴データ記憶部４２と、ユーザ特徴データ記憶部４３とを含んで構成されている。
【００３９】
ＮＷデータ記憶部４０には、図２に示すような、ユーザ（歩行者）の移動可能なリンク及びリンクの端点を示すノードからなるネットワークデータを蓄積したＤＢが記憶されている。一般的なトポロジカルなネットワークデータを蓄積したＤＢであり、その実現方式は本発明の実施の形態の本質に関連しない。
【００４０】
移動リンク特定部２１は、通信部１２を介して、クライアント端末３００１〜Ｎのそれぞれからユーザ群のユーザの各々の移動経路を受け付け、ユーザ群のユーザの各々について、ユーザ位置座標群をＮＷデータ記憶部４０に保存されたネットワークデータと照合して、ネットワークデータ上の当該ユーザが移動したリンクを表すユーザ移動履歴データを特定し、ユーザ移動履歴データ記憶部４１に記憶する。実現方法は一般的なマップマッチング手法を用いて実現可能である。また、実現方法は本発明の本質に関連しない。また、ユーザ移動履歴データにノードを含めるようにしてもよい。
【００４１】
ユーザ移動履歴データ記憶部４１には、移動リンク特定部２１により特定されたユーザ群のユーザの各々について、ユーザの移動経路から得られる、ネットワークデータ上のユーザが移動したリンクを表すユーザ移動履歴データが記憶されている。ユーザ移動履歴データの一例を図３に示す。図３に示すように、ユーザ移動履歴データは、リンク毎に、ユーザが当該リンクを移動した頻度を表している。
【００４２】
移動履歴処理部２２は、以下に説明するように、ユーザ移動履歴データ記憶部４１に記憶されている、ユーザ群のユーザの各々についてのユーザ移動履歴データに基づいて、ユーザ群を複数のカテゴリに分類する。次に、ユーザ群のユーザの各々について、当該ユーザが移動したリンクと、当該ユーザが移動しなかったリンクであって、当該ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成する。そして、マトリクスの因子分析をユーザ、及びリンクのそれぞれについて行って、ユーザ群のユーザの各々についての特徴を表すユーザ特徴データ、及びリンクの各々についての特徴を表すリンク特徴データを求め、それぞれ、ユーザ特徴データ記憶部４３及びリンク特徴データ記憶部４２に記憶する。なお、ユーザ特徴データ及びリンク特徴データのいずれか一方だけを求めるようにしてもよい。
【００４３】
移動履歴処理部２２は、まず、ユーザ移動履歴データのテーブルから特定の地理範囲に含まれるリンクのカラムのみを抽出し、さらに抽出したリンクに一定以上の移動履歴のあるユーザ群を抽出してユーザ・移動リンクのマトリクスを作成する。なお、一定以上の移動履歴があるか否かは、特定の地理範囲における移動したリンクののべ数か、又は特定の地理範囲における移動したリンクの種類が閾値以上であるか否かにより定めればよい。次に、作成したマトリクスに対するＮＭＦ（Non-negative Matrix Factorization）等の因子分析やＫ近傍法等のカテゴリ分類アルゴリズムによって、抽出されたユーザ群を複数のカテゴリに分類する。カテゴリの分類により、特定の地理範囲でさらに特定のリンク群を利用するカテゴリにユーザを分類できる。
【００４４】
そして、ユーザ毎に、当該ユーザについて同一カテゴリに含まれる他のユーザ群の既定の割合以上が移動履歴を持つにもかかわらず、当該ユーザが移動履歴を持たないリンクを当該ユーザの忌避リンクとして決定する。
【００４５】
またはあるユーザをキーとして当該ユーザが移動履歴を持つリンクをマトリクスの左に集める列並び替えを行い、当該ユーザが一定以上の移動履歴を持つリンク群の移動履歴の多い順に他のユーザのソートを行い、当該ユーザが一定以上の移動履歴をもつリンク群に対して、一定以上の移動履歴を持つ他のユーザ群を抽出する。そして、抽出した他のユーザ群において、一定以上の割合ないし人数が移動履歴を持つにもかかわらず、当該ユーザが移動履歴を持たないリンクを当該ユーザの忌避リンクとして決定するようにしても構わない。
【００４６】
忌避リンクの決定手法は、上記二つの手法に限定されずに、ユーザが移動履歴を持つ特定の地理範囲において当該ユーザと多く共通するリンクを持つ他のユーザからなるユーザ群において、他のユーザでは移動履歴を持つにもかかわらず、当該ユーザが移動履歴を持たないリンクを抽出できるものであれば、手法の詳細は本発明の実施の形態の本質に関連しない。
【００４７】
上記の手法によって作成した、ユーザ・（忌避リンク）マトリクスをユーザ・移動リンクのマトリクスと結合し、ユーザ・（移動リンク+忌避リンク）のマトリクスを作成する。そして、作成したユーザ・（移動リンク+忌避リンク）をＮＭＦ（Non-negative Matrix Factorization）等の因子分析をユーザ及びリンクのそれぞれについて行うことでリンク特徴データ及びユーザ特徴データを算出する。因子分析に用いる手法は本発明の実施の形態の本質に関連しない。
【００４８】
上記の因子分析を行うにあたって、例えば、東京のユーザ群と大阪のユーザ群とを含んだマトリクスを対象に因子分析を行うと、ユーザやリンクの特徴が地理的特徴に偏ってしまう恐れが大きい。そのため、地理的な偏りが予想される場合においては忌避リンクの抽出における処理と同様に、特定の地理範囲に含まれるリンクのカラムのみを抽出し、さらにそれらのリンクに一定以上の移動履歴のあるユーザからなるユーザ群を抽出し、当該ユーザ群とリンク群からなるユーザ・（移動リンク+忌避リンク）を対象とした因子分析を行うのも好ましい。
【００４９】
また、ユーザが実際に移動履歴を持つ個別のリンクを移動リンクとするのではなく、あらかじめ収集された各リンクの経路属性情報によって、各リンクをカテゴリに分類し、各カテゴリについての、ユーザが当該カテゴリに属するリンクを移動した履歴を用いることも好ましい。
【００５０】
これによりユーザ・移動リンク マトリクスの列がリンクのカテゴリ数にまで集約されるため、上記の地理的な偏りに対処するための処理が省略できることと、データのスパースネスに起因する因子分析のあいまいさを回避できるという利点を有する。
【００５１】
リンク特徴データ記憶部４２には、図４に示すように、リンクの各々についての特徴をリンク属性で表したリンク特徴データが記憶されている。
【００５２】
ユーザ特徴データ記憶部４３には、図５に示すように、同一カテゴリに分類されたユーザ群のユーザの各々についての特徴を表すユーザ特徴データが記憶されている。
【００５３】
経路探索部２３は、通信部１２を介して、クライアント端末３００を操作する特定ユーザから現時点の位置、目的地、及びユーザの識別情報を受け付ける。まず、現時点の位置から目的地までの経路の候補を複数求め、経路の候補に含まれるリンクの各々についてコストを計算する。次に、ユーザ特徴データ記憶部４３に記憶されているユーザ特徴データに基づいて、特定ユーザの識別情報におけるユーザ特徴データについて協調フィルタリングの類似度計算を行い、当該特定ユーザと類似するユーザを求める。求められた類似するユーザの移動履歴を取得し、類似するユーザの移動履歴に含まれるリンクのコストを下げるように、各リンクのコストを補正する。
【００５４】
また、特定ユーザの識別情報における移動履歴を取得し、当該特定ユーザの移動履歴に含まれるリンクのリンク特徴データについて協調フィルタリングの類似度計算を行い、当該特定ユーザの移動履歴に含まれるリンクと類似するリンクを求める。求められたリンクのコストを下げるように、各リンクのコストを補正する。また、特定ユーザの識別情報における忌避リンクを取得し、当該特定ユーザの忌避リンクのリンク特徴データについて協調フィルタリングの類似度計算を行い、当該特定ユーザの忌避リンクと類似するリンクを求める。求められたリンクのコストを上げるように、各リンクのコストを補正する。
【００５５】
そして、各リンクのコストを用いて経路の候補から、コストが最小となる経路を、特定ユーザに適したリンクからなる経路として探索し、通信部１２を介してクライアント端末３００に送信する。なお、ユーザ特徴データ、又はリンク特徴データのいずれか一方だけを用いるようにしてもよい。また、経路探索手法の詳細は、本発明の実施の形態の本質に関連しない。
【００５６】
上述したように、ユーザ特徴データを用いる場合には、経路探索におけるリンクのコスト計算において、クライアント端末３００を操作するユーザと移動経路が類似するユーザを協調フィルタリングにより求める。そして、類似するユーザが移動したリンクについてはコストを下げる。また、類似するユーザが忌避リンクとしているリンクについてはコストを上げるようにしてもよい。このようにして、類似するユーザの移動履歴を経路探索に反映させる。同手法によればユーザと類似のリンクを通り類似のリンクを忌避する他のユーザの選択に基づく経路探索を実現でき、あらかじめ調査したリンクの属性以外のリンクの特徴も取り込んだ経路探索も期待できる。
【００５７】
また、上述したように、リンク特徴データを用いる場合には、協調フィルタリングにより、推奨されるリンクと推奨されないリンクを求める。そして、推奨されるリンクのコストを下げ、推奨されないリンクのコストを上げて、リンクを経路探索に反映する。
【００５８】
＜本発明の実施の形態に係る経路探索装置の作用＞
【００５９】
次に、本発明の実施の形態に係る経路探索装置２００の作用について説明する。経路探索装置２００は、図７に示す特徴抽出処理ルーチン、及び図８に示す経路探索処理ルーチンを実行する。
【００６０】
まず、特徴抽出処理ルーチンについて説明する。経路探索装置２００は、クライアント端末３００１〜Ｎのそれぞれからユーザ群のユーザの各々の移動経路を受け付け、一定時間ごとに特徴抽出処理ルーチンを実行する。なお、予め定めた以上の移動経路の蓄積が累積した場合に特徴抽出処理ルーチンを実行するようにしてもよい。
【００６１】
ステップＳ１００では、ユーザ群のユーザの各々について、ユーザ位置座標群をＮＷデータ記憶部４０に保存されたネットワークデータと照合して、ネットワークデータ上の当該ユーザが移動したノード及びリンクを表すユーザ移動履歴データを特定し、ユーザ移動履歴データ記憶部４１に記憶する。
【００６２】
ステップＳ１０２では、ユーザ移動履歴データ記憶部４１に記憶されているユーザ移動履歴データのテーブルから特定の地理範囲に含まれるリンクのカラムのみを抽出し、さらに抽出したリンクに一定以上の移動履歴のあるユーザ群を抽出してユーザ・移動リンクのマトリクスを作成する。そして、当該ユーザ群のユーザの各々についてのユーザ・移動リンクのマトリクスに基づいて、ユーザ群を複数のカテゴリに分類する。
【００６３】
ステップＳ１０４では、当該ユーザ群のユーザの各々について、当該ユーザが移動したリンクと、当該ユーザが移動しなかったリンクであって、当該ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成する。
【００６４】
ステップＳ１０６では、ステップＳ１０４で作成したマトリクスのユーザについて因子分析を行って、ユーザ群のユーザの各々についての特徴を表すユーザ特徴データを求める。
【００６５】
ステップＳ１０８では、ステップＳ１０４で作成したマトリクスのリンクについて因子分析を行って、リンクの各々についての特徴を表すリンク特徴データを求める。
【００６６】
ステップＳ１１０では、ステップＳ１０６で求めたユーザ特徴データ、及びステップＳ１０８で求めたリンク特徴データをそれぞれユーザ特徴データ記憶部４３及びリンク特徴データ記憶部４２に記憶し、特徴抽出処理ルーチンを終了する。
【００６７】
次に、経路探索処理ルーチンについて説明する。経路探索装置２００は、通信部１２を介して、クライアント端末３００を操作する特定ユーザから現時点の位置、目的地、及び特定ユーザの識別情報を受け付けると、経路探索処理ルーチンを実行する。
【００６８】
ステップＳ２００では、現時点の位置から目的地までの経路の候補を複数求め、経路の候補に含まれるリンクの各々についてコストを計算する。
【００６９】
ステップＳ２０２では、ユーザ特徴データ及びリンク特徴データについて協調フィルタリングの類似度計算を行い、当該特定ユーザと類似するユーザの移動履歴に含まれるリンク、及び当該特定ユーザの移動履歴に含まれるリンクと類似するリンクを求め、求められたリンクのコストを下げるように、各リンクのコストを補正する。
【００７０】
ステップＳ２０４では、ステップＳ２０４で補正された各リンクのコストを用いて経路の候補から、コストが最小となる経路を、特定ユーザに適したリンクからなる経路として探索し、通信部１２を介してクライアント端末３００に送信して処理を終了する。
【００７１】
以上説明したように、本発明の実施の形態に係る経路探索装置によれば、ユーザ群のユーザの各々についてのユーザ移動履歴データに基づいて、ユーザ群を複数のカテゴリに分類し、ユーザ群のユーザの各々について、ユーザが移動したリンクと、ユーザが移動しなかったリンクであって、ユーザと同一カテゴリに分類された他のユーザが移動したリンクである忌避リンクとを表すマトリクスを作成し、マトリクスの因子分析を行って、ユーザ群のユーザの各々についての特徴を表すユーザ特徴データ、及びリンクの各々についての特徴を表すリンク特徴データを求め、ユーザ特徴データ、及びリンク特徴データに基づいて、特定ユーザに適したリンクからなる経路を探索することにより、ユーザが移動しない経路を考慮して、ユーザに適した経路を探索することができる。
【００７２】
なお、本発明は、上述した実施の形態に限定されるものではなく、この発明の要旨を逸脱しない範囲内で様々な変形や応用が可能である。
【００７３】
例えば、上述した実施の形態では、経路探索装置として構成する場合を例に説明したが、これに限定されるものではない。例えば、移動リンク特定部と、移動履歴処理部と、ＮＷデータ記憶部と、ユーザ移動履歴データ記憶部と、ユーザ特徴データ記憶部とからなり、移動履歴処理部においてユーザ特徴データを作成するユーザ特徴データ作成装置として構成するようにしてもよい。また、移動リンク特定部と、移動履歴処理部と、ＮＷデータ記憶部と、ユーザ移動履歴データ記憶部と、リンク特徴データ記憶部とからなり、移動履歴処理部においてリンク特徴データを作成するリンク特徴データ作成装置として構成するようにしてもよい。
【符号の説明】
【００７４】
１     経路探索システム
１２、１３    通信部
２０   演算部
２１   移動リンク特定部
２２   移動履歴処理部
２３   経路探索部
３１   ユーザ位置収集部
３２   経路探索ＵＩ
４０   データ記憶部
４１   ユーザ移動履歴データ記憶部
４２   リンク特徴データ記憶部
４３   ユーザ特徴データ記憶部
１５０ ネットワーク
２００ 経路探索装置
３００ クライアント端末
【図１】
0006600602.tif 000002
【図２】
0006600602.tif 000003
【図３】
0006600602.tif 000004
【図４】
0006600602.tif 000005
【図５】
0006600602.tif 000006
【図６】
0006600602.tif 000007
【図７】
0006600602.tif 000008
【図８】
0006600602.tif 000009