関心エリア設定装置、関心エリア設定方法、及び推薦経路決定装置ならびに推薦経路決定方法

【課題】各地点について記述された情報を用いることなく、同一事物に関連する地点を含むエリアを設定可能な関心エリア設定装置及び関心エリア設定方法を提供する。
【解決手段】関心エリア設定装置１は、指定された地図範囲に含まれる複数の地点のうちの２以上の地点の位置情報と各地点に対応する時間情報とを含む行動データごとに、複数の地点を時間順に並べた配列表を作成する位置順序決定部２１と、配列表において、所定の二つの地点が時間順に隣接した回数を、その二つの地点間の関連度として算出し、関連度が正の所定値以上となる地点間にリンクを設定する位置関連度算出部２２と、そのリンクを、対応する二つの地点間の関連度が低い方から順に切断し、リンクによって接続された地点の集合ごとに別個のクラスタに分類するクラスタリング部２３と、クラスタごとに、そのクラスタ内に含まれる地点の集合を関心エリアとする関心エリア決定部２４とを有する。

【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地図上の複数の地点を複数のエリアに分類する関心エリア設定装置及び関心エリア設定方法に関する。また本発明は、地図上の複数の地点を経由する移動経路を推薦する推薦経路決定装置及び推薦経路決定方法に関する。
【背景技術】
【０００２】
近年、電子データとしてサーバに記憶されている地図を閲覧しようとするユーザに対して、ユーザが関心を持ちそうな地点を特定の情報によって分類し、その分類結果に応じて決定された関心エリアを地図とともに表示する方法及びシステムが提案されている（例えば、特許文献１〜３を参照）。
特許文献１に開示された方法は、検出対象のロケーションに対してタグ付けされた、ユーザによる記述タグの情報に基づいてクラスタリングを実行することにより、関心エリアを決定する。しかし、それぞれのロケーションに対して記述タグを作成することは、ユーザにとって手間の掛かることである。そのため、そのような記述タグ自体が作成されず、記述タグの情報に基づいてクラスタリングする方法は、適切な関心エリアを設定できないことがあった。
【０００３】
また、特許文献２に開示されたシステムは、ユーザが設定した地図上の範囲内の各地点についての情報を記述した記述情報を取得する。そしてそのシステムは、取得した記述情報を形態素解析によって品詞に分解することで、各地点の特徴を表す特徴語及びその特徴の強さを求める。そのシステムは、得られた特徴語及び特徴の強さに基づいてクラスタリングを実行することにより、共通の特徴を持つ地点を包含する共通特徴エリアを決定する。そのため、このシステムは、特許文献１に開示された方法と同様に、適切な共通特徴エリアを設定するには、各地点について記述された情報を必要とする。
【０００４】
一方、特許文献３に開示された装置は、撮影画像が取得された複数の撮影場所を、撮影場所間の距離または撮影日時によって分類する。そのため、この装置は、各地点ごとの記述情報を使用することなく、複数の地点を分類することができる。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００８−１５８５３１号公報
【特許文献２】特開２００７−２９３８２３号公報
【特許文献３】特開２００６−１８５２４２号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、特許文献３に開示された装置は、ユーザが関心を持つ事物とは無関係に複数の地点を分類する。例えば、互いに異なる関心対象に関連する二つの地点が近接していたり、その二つの地点での撮影日時が同じであれば、この装置は、それら二つの地点を同じグループに分類してしまう。そのため、この装置は、ユーザにとって意味があるように、対象となる地点を分類できないおそれがあった。
【０００７】
そこで、本発明は、地図上の各地点について記述された情報を用いることなく、同一事物に関連する地点を含むエリアを設定可能な関心エリア設定装置及び関心エリア設定方法を提供することを目的とする。
【０００８】
また本発明は、各地点について記述された情報を用いることなく、ユーザに対して適切な移動経路を推薦可能な移動経路決定装置及び移動経路決定方法を提供することを他の目的とする。
【課題を解決するための手段】
【０００９】
請求項１の記載によれば、本発明の一つの形態として、指定された地図範囲に含まれる複数の地点を、少なくとも一つの関心エリアに分類する関心エリア設定装置が提供される。この関心エリア設定装置は、指定された地図範囲に含まれる複数の地点のうちの２以上の地点の位置情報と、それら２以上の地点のそれぞれに対応する時間情報とを含む行動データを少なくとも一つ記憶する記憶部（１２）と、行動データごとに、指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成する位置順序決定部（２１）と、配列表において、複数の地点のうちの二つの地点が時間順に隣接した回数を、その二つの地点間の関連度として算出し、関連度が正の所定値以上となる地点間にリンクを設定する位置関連度算出部（２２）と、上記の複数の地点に含まれる二つの地点間のリンクを、その二つの地点間の関連度が低い方から順に切断し、リンクによって接続された地点の集合ごとに別個のクラスタに分類することにより、１以上の所定数のクラスタを作成するクラスタリング部（２３）と、所定数のクラスタのそれぞれについて、クラスタ内に含まれる地点の集合を関心エリアとして決定する関心エリア決定部（２４）とを有する。
係る構成を有することにより、本発明に係る関心エリア設定装置は、各地点について記述された情報を用いることなく、同一事物に関連する地点を含むエリアを設定できる。なお、本明細書において、所定の地点について記述された情報とは、言葉によってその地点の何らかの特性を表す情報をいう。例えば、所定の地点について記述された情報には、その地点の名称、その地点を表す種別（例えば、道路、交差点、公園、レストラン等）、その地点に存在する店又は建物の名称、その地点において提供されるサービスの種類、あるいはユーザにより自由記述されたコメントが含まれる。
【００１０】
また請求項２の記載によれば、クラスタリング部（２３）は、指定された地図範囲に含まれる複数の地点のうち、他の何れの地点に対してもリンクが設定されていない地点を、何れかのクラスタに含まれる地点のうちの最も近い地点が属するクラスタに含めることが好ましい。
【００１１】
また、請求項３の記載によれば、本発明の他の形態として、指定された地図範囲に含まれる複数の地点を経由する推薦経路を決定する推薦経路決定装置が提供される。この推薦経路決定装置は、指定された地図範囲に含まれる複数の地点のうちの２以上の地点の位置情報と、それら２以上の地点のそれぞれに対応する時間情報とを含む行動データを少なくとも一つ記憶する記憶部（１２）と、行動データごとに、指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成する位置順序決定部（２１）と、配列表において、複数の地点のうちの二つの地点が特定の順序で並んだ回数を、それら二つの地点間のその特定順序に沿った移動頻度として算出する移動頻度算出部（２６）と、複数の地点のそれぞれを一度経由する移動経路のうち、その移動経路に沿った移動頻度の合計が最大となる移動経路を推薦経路とする推薦移動経路決定部（２７）とを有する。
係る構成を有することにより、本発明に係る移動経路決定装置は、各地点について記述された情報を用いることなく、ユーザに対して、指定された地図範囲に含まれる複数の地点を通る適切な移動経路を推薦することができる。
【００１２】
また請求項４の記載によれば、推薦移動経路決定部（２７）は、指定された地図範囲に含まれる複数の地点のうち、ユーザの現在位置に最も近い地点を始点とする、複数の地点のそれぞれを一度経由する移動経路のうち、その移動経路に沿った移動頻度の合計が最大となる移動経路を推薦経路とすることが好ましい。
かかる構成を有することにより、本発明に係る移動経路決定装置は、ユーザの現在位置に最も適した移動経路を推薦することができる。
【００１３】
あるいは請求項５の記載によれば、推薦移動経路決定部（２７）は、指定された地図範囲に含まれる複数の地点のうちのユーザの現在位置に最も近い地点を始点とし、その始点から複数の地点のそれぞれへの移動頻度のうちの最大値を求め、その最大値に対応する地点を次の移動先とすることが好ましい。
かかる構成を有することにより、本発明に係る移動経路決定装置は、ユーザの現在位置に応じて、最も適した次の訪問先を推薦することができる。
【００１４】
さらに請求項６の記載によれば、本発明の他の形態として、指定された地図範囲に含まれる複数のエリアを経由する推薦経路を決定する推薦経路決定装置が提供される。この推薦経路決定装置は、複数のエリアの何れかに含まれる２以上の地点の位置情報と、それら２以上の地点のそれぞれに対応する時間情報とを含む行動データを少なくとも一つ記憶する記憶部（１２）と、行動データごとに、指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成する位置順序決定部（２１）と、配列表において、複数の地点のうちの二つの地点が特定の順序で並んだ回数を、それら二つの地点間のその特定順序に沿った移動頻度として算出する移動頻度算出部（２６）と、複数のエリアのうちの二つのエリアの一方に含まれる全ての地点から、その二つのエリアのうちの他方のエリアに含まれる全ての地点への移動頻度の合計値を、その一方のエリアから他方のエリアへのエリア間移動頻度として算出するエリア間移動頻度算出部（２７）と、複数のエリアのそれぞれを一度経由する移動経路のうち、その移動経路に沿ったエリア間移動頻度の合計が最大となる移動経路を推薦経路とする推薦移動経路決定部（２７）とを有する。
係る構成を有することにより、本発明に係る移動経路決定装置は、各地点について記述された情報を用いることなく、ユーザに対して、指定された地図範囲に含まれる複数のエリアを通る適切な移動経路を推薦することができる。
【００１５】
また請求項７の記載によれば、推薦移動経路決定部（２７）は、複数のエリアのうち、ユーザの現在位置に最も近いエリアを始点とする、複数のエリアのそれぞれを一度経由する移動経路のうち、その移動経路に沿ったエリア間移動頻度の合計が最大となる移動経路を推薦経路とすることが好ましい。
かかる構成を有することにより、本発明に係る移動経路決定装置は、ユーザの現在位置に最も適した移動経路を推薦することができる。
【００１６】
あるいは請求項８の記載によれば、推薦移動経路決定部（２７）は、複数のエリアのうちのユーザの現在位置に最も近いエリアを始点とし、その始点から複数のエリアのそれぞれへのエリア間移動頻度のうちの最大値を求め、その最大値に対応するエリアを次の移動先とすることが好ましい。
かかる構成を有することにより、本発明に係る移動経路決定装置は、ユーザの現在位置に応じて、最も適した次の訪問先を推薦することができる。
【００１７】
さらに請求項９の記載によれば、本発明の他の形態として、指定された地図範囲に含まれる複数の地点を、少なくとも一つの関心エリアに分類する関心エリア設定方法が提供される。この関心エリア設定方法は、指定された地図範囲に含まれる複数の地点のうちの２以上の地点の位置情報と、それら２以上の地点のそれぞれに対応する時間情報とを含む行動データごとに、指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成するステップと、配列表において、指定された地図範囲に含まれる複数の地点のうちの二つの地点が時間順に隣接した回数を、その二つの地点間の関連度として算出し、関連度が正の所定値以上となる地点間にリンクを設定するステップと、指定された地図範囲に含まれる複数の地点に含まれる二つの地点間のリンクを、二つの地点間の関連度が低い方から順に切断し、リンクによって接続された地点の集合ごとに別個のクラスタに分類することにより、１以上の所定数のクラスタを作成するステップと、所定数のクラスタのそれぞれについて、クラスタ内に含まれる地点の集合を関心エリアとして決定するステップとを有する。
上記の各ステップを有することにより、本発明に係る関心エリア設定方法は、各地点について記述された情報を用いることなく、同一事物に関連する地点を含むエリアを設定できる。
【００１８】
さらに請求項１０の記載によれば、本発明の他の形態として、指定された地図範囲に含まれる複数の地点を経由する推薦経路を決定する推薦経路決定方法が提供される。この推薦経路決定方法は、指定された地図範囲に含まれる複数の地点のうちの２以上の地点の位置情報と、それら２以上の地点のそれぞれに対応する時間情報とを含む行動データごとに、指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成するステップと、配列表において、複数の地点のうちの二つの地点が特定の順序で並んだ回数を、それら二つの地点間のその特定順序に沿った移動頻度として算出するステップと、指定された地図範囲に含まれる複数の地点のそれぞれを一度経由する移動経路のうち、その移動経路に沿った移動頻度の合計が最大となる移動経路を推薦経路とするステップとを有する。
上記の各ステップを有することにより、本発明に係る移動経路決定方法は、各地点について記述された情報を用いることなく、ユーザに対して、指定された地図範囲に含まれる複数の地点を通る適切な移動経路を推薦することができる。
【００１９】
さらに請求項１１の記載によれば、本発明の他の形態として、指定された地図範囲に含まれる複数のエリアを経由する推薦経路を決定する推薦経路決定方法が提供される。この推薦経路決定方法は、複数のエリアの何れかに含まれる２以上の地点の位置情報と、それら２以上の地点のそれぞれに対応する時間情報とを含む行動データごとに、指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成するステップと、配列表において、指定された地図範囲に含まれる複数の地点のうちの二つの地点が特定の順序で並んだ回数を、それら二つの地点間のその特定順序に沿った移動頻度として算出するステップと、複数のエリアのうちの二つのエリアの一方に含まれる全ての地点から、その二つのエリアのうちの他方のエリアに含まれる全ての地点への移動頻度の合計値を、その一方のエリアから他方のエリアへのエリア間移動頻度として算出するステップと、複数のエリアのそれぞれを一度経由する移動経路のうち、その移動経路に沿ったエリア間移動頻度の合計が最大となる移動経路を推薦経路とするステップとを有する。
上記の各ステップを有することにより、本発明に係る移動経路決定方法は、各地点について記述された情報を用いることなく、ユーザに対して、指定された地図範囲に含まれる複数のエリアを通る適切な移動経路を推薦することができる。
【００２０】
なお、上記各手段に付した括弧内の符号は、後述する実施形態に記載の具体的手段との対応関係を示す一例である。
【図面の簡単な説明】
【００２１】
【図１】本発明の第１の実施形態に係る地図データ生成装置の概略構成図である。
【図２】地図データ生成装置により分類しようとする複数の地点を含む地図の一例を示す。
【図３】第１の実施形態に係る地図データ生成装置の制御部の機能ブロック図である。
【図４】図２に示された地図に対応する、行動データの一覧表の例を示す図である。
【図５】図４に示された表に含まれる行動データから作成された配列表を示す図である。
【図６】図５に示された配列表に基づいて算出された各地点間の関連度を、図２に示した地図上に表示した図である。
【図７】本発明の第１の実施形態に係る地図データ生成装置の制御部上で実行されるコンピュータプログラムにより制御される、関心エリア決定処理の動作を示すフローチャートである。
【図８】第２の実施形態に係る地図データ生成装置の制御部の機能ブロック図である。
【図９】図２に示された地図上の各地点を行動データごとに時間順に並べて作成された配列表の他の一例を示す図である。
【図１０】図９に示された配列表に基づく、各地点間の移動頻度を示す移動頻度表を示す図である。
【図１１】本発明の第２の実施形態に係る地図データ生成装置の制御部上で実行されるコンピュータプログラムにより制御される、推薦経路決定処理の動作を示すフローチャートである。
【図１２】第３の実施形態に係る地図データ生成装置の制御部の機能ブロック図である。
【図１３】地図設定範囲情報により示された地図の範囲内に含まれる関心エリアを記録した、関心エリアテーブルの一例を示す図である。
【図１４】図１３に示された３個の関心エリアに含まれる各地点間の移動頻度表の一例を示す図である。
【図１５】図１４に示された移動頻度表に基づいて算出された各関心エリア間の移動頻度を示すエリア移動頻度表を示す図である。
【図１６】本発明の第３の実施形態に係る地図データ生成装置の制御部上で実行されるコンピュータプログラムにより制御される、エリア間推薦経路決定処理の動作を示すフローチャートである。
【発明を実施するための形態】
【００２２】
以下、図を参照しつつ、本発明に係る関心エリア設定装置を地図データ生成装置に適用した第１の実施形態について説明する。
この地図データ生成装置は、地図上の複数の地点のそれぞれについて、時間情報を有するデータから、時間的な順序にしたがって各地点間の関連度を求め、その関連度が高い地点同士を同じ関心エリアに分類するものである。
【００２３】
図１は、第１の実施形態による、地図データ生成装置の概略構成図である。地図データ生成装置１は、通信ネットワーク２を介して、少なくとも１台のユーザ端末３と接続される。
【００２４】
ユーザ端末３は、例えば、携帯電話機、車載用ナビゲーションシステムあるいはコンピュータであり、ユーザが所定の操作を行うための操作部（図示せず）と、各種の情報を表示するための表示部（図示せず）を有する。そしてユーザ端末３を所持するユーザが、操作部を介して、所定の範囲を含む地図を指定し、かつその地図を取得することを要求する地図要求コマンドを入力することにより、ユーザ端末３は、通信ネットワーク２を介して、地図データ生成装置１に対してその地図要求コマンド及びユーザにより設定された地図の範囲を表す地図設定範囲情報を送信する。またユーザ端末３は、例えば、ＧＰＳ（Global Positioning System）システムを利用して現在位置を取得できる場合、そのＧＰＳ情報から算出される緯度及び経度であるユーザの現在位置情報を、通信ネットワーク２を介して、地図データ生成装置１に送信してもよい。
また、ユーザ端末３は、地図データ生成装置１から、通信ネットワーク２を介して受信した地図データに表された指定範囲の地図を表示部に表示する。またユーザ端末３は、地図データ生成装置１から、通信ネットワーク２を介して受信した、その指定範囲の地図に含まれる複数の地点を同一事物に関連するものごとに分類した関心エリア情報をその地図に重畳して、あるいはその地図とは別個に、表示部に表示する。
【００２５】
一方、地図データ生成装置１は、ユーザにより指定された範囲の地図を表す地図データを、その地図データの取得を要求したユーザ端末３へ送信する。また地図データ生成装置１は、ユーザにより指定された範囲の地図に含まれる、複数の地点を、同一事物に関連するものごとに分類した複数の関心エリアを設定し、それら関心エリアを表す情報を地図データの取得を要求したユーザ端末３へ送信する。そのために、地図データ生成装置１は、通信部１１と、記憶部１２と、制御部１３とを有する。
通信部１１は、例えば、地図データ生成装置１を通信ネットワーク２に接続するための通信インターフェース及びその制御回路を有する。例えば、通信部１１は、イーサネット（登録商標）などの通信規格に従った通信ネットワークまたは公衆通信回線に接続するための通信インターフェース及びその制御回路を有する。通信部１１は、ユーザ端末３から、地図要求コマンド、地図設定範囲情報、現在位置情報などを通信ネットワーク２を介して受信する。そして通信部１１は、受信したそれらのコマンド及び情報を制御部１３へ渡す。また通信部１１は、制御部１３からユーザ端末３へ送信される地図データ及び関心エリア情報などのデータを受け取ると、その受け取ったデータを通信ネットワーク２へ送出する。
【００２６】
記憶部１２は、半導体メモリ、磁気ディスク（HDD）あるいは光ディスク及びその読み取り装置などといった記憶装置の少なくとも何れか一つを有する。そして記憶部１２は、地図データ生成装置１で使用される各種のプログラム及びデータを記憶する。記憶部１２は、例えば、そのようなデータとして、地図データ及び行動データなどを記憶する。
【００２７】
ここで、一つの行動データは、ユーザ、車など、地図上の複数の地点間を、実際に、あるいは擬似的に移動可能な主体を識別する情報であるカテゴリＩＤと、地図上の複数の地点の位置情報（緯度、経度）と、地点ごとの時間情報を有する。なお、複数の地点間を擬似的に移動するとは、地図データ上の複数の地点にチェックマークを付することをいう。この場合、所定の地点にチェックマークを付した時刻が、その地点の時間情報となる。
行動データは、例えば、特定の人物あるいは車両などの移動物体が、ある地域を訪れたときに通った複数の地点を、その地点の位置情報とともに、その地点を通ったときの時刻を、携帯電話機、ナビゲーションシステムなどによって取得し、その人物、車、あるいは携帯電話機などを識別する識別情報と関連付けて電子データとして記録することにより作成される。あるいは、行動データは、ウェブサーバなどで公開されているブログなどに添付されている、写真データのヘッダ、文章などから、複数の地点の位置情報及びその地点に関連付けられている時刻を取得することにより作成される。
なお、行動データに含まれる各地点の位置情報は、一定の広がりを持つ範囲を代表する地点の位置情報であってもよい。例えば、南北方向及び東西方向にそれぞれ50ｍの幅を持つ領域を同一の地点とみなし、その領域内に含まれる地点は、行動データ上でその領域内の中心点により代表される。あるいは、同一の番地で表される地図上の範囲を同一の地点とみなし、その同一の番地で表される範囲内に含まれる地点は、行動データ上で、その範囲の中心点により代表されてもよい。
これら行動データは、予め収集された上、記憶部１２に記憶される。あるいは、地図データ生成装置１は、通信ネットワーク２を介して他の装置から適宜それら行動データを収集してもよい。
【００２８】
さらに記憶部１２は、制御部１３により決定された関心エリアを示す情報が記録された関心エリアデータベースを格納する。
そして記憶部１２は、制御部１３と接続され、制御部１３からの要求に応じて、所定のプログラム及びデータを出力し、あるいは所定のデータを記憶する。
【００２９】
制御部１３は、プロセッサユニット、RAM及びROMなどの半導体メモリ、及び周辺回路を有する。そして制御部１３は、地図データ生成装置１全体を制御する。また制御部１３は、ユーザ端末３からの要求に応じて、ユーザにより指定された地図の範囲内に存在する複数の地点を同一の事物に関連するものごとに分類した関心エリアを決定する。
【００３０】
図２に、地図データ生成装置１により分類しようとする地図上の複数の地点の一例を示す。なお、図２では、簡単化のために、地図２００は格子状に区切られた複数のエリアの集合として表されるものとし、黒点で表される各地点は、それぞれ、対応するエリアを代表するものとする。また各エリアは、同じ面積を持つものとする。図２において、エリア２０１〜２０５には、それぞれ、記憶部１２に記憶された複数の行動データの何れかに含まれる地点Ａ〜Ｅが存在する。このうち、地点Ａ〜Ｃが、特定の事物α（例えば、観光スポット）に関連するエリアであり、他方、地点Ｄ及び地点Ｅが、別の特定の事物β（例えば、オフィス街）に関連するエリアであるとする。この場合、地図データ生成装置１は、ユーザにとって意味のある関心エリアを設定するために、特定の事物αに関連する地点Ａ〜Ｃを一つの関心エリアに含め、また他の特定の事物βに関連する地点Ｄ及び地点Ｅを、他の関心エリアに含めることが望ましい。
【００３１】
しかし、図２に示される例では、地点Ｃは、地点Ａ及び地点Ｂと離れている一方、地点Ｄ及び地点Ｅと隣接している。そのため、単純に各地点Ａ〜Ｅ間の距離に基づいて地点Ａ〜Ｅを分類しようとすれば、地点Ａ及び地点Ｂを含む関心エリアと、地点Ｃ〜地点Ｅを含む関心エリアに分けられてしまう可能性が高く、ユーザにとって意味のない関心エリアが設定されてしまう。
そこで、制御部１３は、行動データ単位での複数の地点間の関連性に着目して、それらの地点を分類することにより、関心エリアを設定する。
【００３２】
図３に、制御部１３の機能ブロック図を示す。図３に示されるように、制御部１３は、位置順序決定部２１と、位置関連度算出部２２と、クラスタリング部２３と、関心エリア決定部２４と、地図データ生成部２５とを有する。制御部１３が有するこれらの各部は、例えば、プロセッサユニット上で実行されるコンピュータプログラムによって実装される機能モジュールである。
【００３３】
位置順序決定部２１は、行動データごとに、時間順に各地点を並べた配列表を作成する。そのために、位置順序決定部２１は、記憶部１２に記憶されている行動データのうち、ユーザ端末３から受け取った地図設定範囲情報に示された範囲内に含まれる地点を含む行動データを抽出する。地図設定範囲情報は、例えば、関心エリアを決定しようとする範囲の北東端及び南西端の緯度及び経度を有する。あるいは、地図範囲設定情報は、関心エリアを決定しようとする範囲の中心地点の緯度及び経度とその中心地点からの半径を有してもよい。あるいはまた、地図範囲設定情報は、関心エリアを決定しようとする特定の地域を表す住所を有してもよい。
位置順序決定部２１は、記憶部１２に記憶されている行動データに含まれる何れかの地点の緯度及び経度が、地図設定範囲情報に示された範囲内に含まれていれば、その行動データを抽出する。
【００３４】
次に、位置順序決定部２１は、抽出された行動データに含まれる各地点データのうち、所定の時間範囲内に含まれる地点データを抽出し、抽出された地点データを一つの組にまとめる。これは、時間的に隔たりの大きい地点は、互いの関連性が少ないと考えられるためである。例えば、ある行動データが、特定のユーザが地図設定範囲情報に示された地域を観光または仕事で訪問した地点の情報を地点データとして持っているとする。このような場合、そのユーザは、日ごとに異なる目的を持って複数の地点を訪れていることも多い。そのため、互いに関連性がある地点同士を一つの組として抽出するためには、行動データに含まれている地点データは、日にちごとに別個に集約されることが好ましい。
なお、所定の時間範囲は、例えば、１日単位、半日（例えば、１日の午前と午後）単位、あるいは１ヶ月単位のように予め設定される。また所定の時間範囲は、カテゴリＩＤに示された、行動データの主体に応じて異なる値となっていてもよい。さらに、所定の時間範囲は、地図データ生成装置１が有するキーボード及びディスプレイなどのユーザインターフェース（図示せず）を介して、あるいはユーザ端末３を介して設定されてもよい。
位置順序決定部２１は、抽出された行動データごとに、その行動データに含まれ、かつ所定の時間範囲に含まれる各地点を、その各地点に関連付けられた時間順に並べた配列表を作成する。
【００３５】
図４は、図２に示された地図２００に対応する、行動データの一覧表の例を示す。図４に示す表４００において、各行は一つの行動データを示す。左端の列は、カテゴリＩＤを示す。そして表４００の各欄は、それぞれ、地点データを示し、その地点データには、地点名（Ａ〜Ｅの何れか）と、その地点に関連する時間が含まれている。なお、実際には、各地点データは、地点名の代わりに、あるいは地点名とともに、その地点の位置情報（緯度及び経度）を有する。
【００３６】
表４００において、カテゴリＩＤ００１により特定される行動データは、３個の地点データ４１１〜４１３を含んでおり、それぞれ、地点Ａ、Ｂ、Ｃに対応する。そして各地点に関連する時間は何れも2008年12月3日となっている。同様に、カテゴリＩＤ００２により特定される行動データは、地点Ａ、Ｂに対応する地点データを含んでいる。この行動データに含まれる二つの地点データは、同一の日付と関連付けられている。さらに、カテゴリＩＤ００３により特定される行動データは、地点Ｂ、Ｃに対応する地点データを含んでいる。この行動データに含まれる二つの地点データも、同一の日付と関連付けられている。
一方、カテゴリＩＤ００４により特定される行動データは、地点Ｃ、Ｄ、Ｅに対応する地点データ４２１〜４２３を含んでいる。このうち、地点データ４２１、４２２は、同一の日付と関連付けられているが、地点データ４２３は、別の日付と関連付けられている。
【００３７】
図５は、図４に示された表４００に含まれる行動データから、位置順序決定部２１により作成された配列表５００を示す。なお、この例では、上記の所定の時間範囲は、１日に設定されている。
図５に示された配列表５００において、各行は、抽出された地点データの一つの組を示す。そして配列表５００の左端は、各組の識別番号を示し、配列表５００の上端は、各地点の順序を示している。配列表５００のその他の欄は、地点データの組に含まれる地点名を示している。地点データの組１〜組４は、それぞれ、表４００における、カテゴリＩＤ００１〜００４に対応する行動データから抽出されている。そして、地点データの各組１〜組４に含まれる地点データは、その地点データに関連付けられた時間の早い順に左側から並べられている。図５に示されるように、地点データの組１〜組３は、それぞれ、対応する行動データに含まれる全ての地点データを時間順に有しているが、地点データの組４は、カテゴリＩＤ００４により特定される行動データに含まれる３個の地点データのうち、同一の日付を持つ２個の地点データのみを時間順に有している。なお、カテゴリＩＤ００４により特定される行動データに含まれる３個の地点データのうちの残りの一つの地点データに関しては、同じ時間範囲内に含まれる他の地点データが存在しないため、配列表５００には含まれない。
位置順序決定部２１は、作成した配列表を位置関連度算出部２２に渡す。
【００３８】
位置関連度算出部２２は、位置順序決定部２１から受け取った配列表に基づいて、地図設定範囲情報に示された範囲内の複数の地点間の関連度を算出する。ここで、配列表上で横方向に隣接する地点データに表される地点同士は、時間的に限られた期間内に、同一人物、同じ車などが通った地点、あるいは、同一人物が地図上で連続してチェックマークを付けた地点であり、何れの地点も、特定の事物との関連性が高いと考えられる。
そこで、位置関連度算出部２２は、配列表上で横方向に隣接する任意の二つの地点データの組み合わせの数、すなわち、その二つの地点が時間順に並んだ数を計数する。そして位置関連度算出部２２は、その合計値を、それら二つの地点データに表される二つの地点間の関連度とする。そして位置関連度算出部２３は、関連度が正の所定値以上となる地点間に、それら地点間に何らかの関係があることを示すリンクを設定する。
なお、その正の所定値は、地図設定範囲情報に示された範囲の広さ、その範囲内に含まれる地点数、あるいは配列表作成に使用される行動データの数に応じて決定される。例えば、地図設定範囲情報に示された範囲の広さが広くなるほど、関連度を調べる地点間の数が増えるので、相対的に関連度の値は低くなる可能性が高い。そこで、地図設定範囲情報に示された範囲の広さが広くなるほど、その正の所定値を小さくする。同様に、地図設定範囲情報に示された範囲に含まれる地点数が増えるほど、その正の所定値を小さくする。逆に、配列表作成に使用される行動データの数が増えるほど、関連度の値は全体的に高くなる。そこで、その行動データの数が増えるほど、その正の所定値を大きくする。なお、本実施形態では、その正の所定値を１とした。
【００３９】
例えば、位置関連度算出部２２は、図５に示した配列表５００に基づいて、地点Ａ〜Ｅ間の関連度を算出する場合、まず、全ての地点間の関連度を０にリセットする。そして位置関連度算出部２２は、地点データの組１から、地点ＡＢ間の関連度及び地点ＢＣ間の関連度をそれぞれ１インクリメントする。同様に、位置関連度算出部２２は、地点データの組２〜組４から、地点ＡＢ間、地点ＢＣ間、地点ＣＤ間の関連度をそれぞれ１インクリメントする。この結果、地点ＡＢ間、地点ＢＣ間の関連度はそれぞれ２となり、地点ＣＤ間の関連度は１となる。そしてその他の地点間（例えば、地点ＡＣ間、地点ＤＥ間など）の関連度は０となる。したがって、位置関連度算出部２２は、地点ＡＢ間、地点ＢＣ間、地点ＣＤ間にそれぞれリンクを設定する。
【００４０】
図６は、配列表５００に基づいて算出された各地点間の関連度を、図２に示した地図２００上に表示した図である。図６において、矢印６０１〜６０３が示された地点間は１以上の関連度を有し、リンクが設定されている。一方、矢印のない地点間の関連度は０である。また、各矢印に近接して示された数値は、その矢印の両端に位置する二つの地点間の関連度を表す。
図６に示されるように、この例では、地点間の距離とは無関係に、行動データの主体が各地点間を移動した頻度に基づいて、各地点間の関連度が求められていることが分かる。
【００４１】
なお、位置関連度算出部２２は、配列表上で二つの地点データが横方向に隣接していることのみに着目するので、その二つの地点データの順序が入れ替わっていても、関連度としては同等に扱う。例えば、配列表５００の組２において、地点Ｂが地点Ａよりも時間的に早い場合でも、位置関連度算出部２２は、その組２から、地点ＡＢ間の関連度を１インクリメントする。
位置関連度算出部２２は、各地点間の関連度及びリンクを表す情報をクラスタリング部２３に渡す。
【００４２】
クラスタリング部２３は、位置関連度算出部２２から受け取った各地点間の関連度及びリンクを表す情報に基づいて、地図設定範囲情報に示された範囲内に含まれる複数の地点を分類する。
クラスタリング部２３は、いわゆるグラフカット手法のように、リンクを持つ二つの地点のうち、最も関連度が低い二つの地点から順に、そのリンクを切断する。そしてクラスタリング部２３は、リンクによって接続された地点の集合ごとに別個のクラスタに分類する。そしてクラスタリング部２３は、作成されたクラスタの数が予め設定された所定数に達した時点で、その分類処理を停止する。あるいは、クラスタリング部２３は、予め設定された閾値以下の関連度を持つ全てのリンクを切断してもよい。
その後、クラスタリング部２３は、他の地点とのリンクが設定されていない地点を、その地点と最も近い地点が含まれるクラスタにマージしてもよい。あるいは、クラスタリング部２３は、他の地点とのリンクが設定されていない地点を、別個のクラスタとしてもよい。作成された各クラスタは、それぞれ、そのクラスタに含まれる全ての地点の位置情報を少なくとも含む。
【００４３】
図５及び図６に示される、各地点間の関連度の例において、クラスタリング部２３は、２個のクラスタを作成するものとする。この場合、クラスタリング部２３は、リンクが設定されている地点間のうち、最も関連度の低い、地点Ｃと地点Ｄ間のリンクを切断する。これにより、クラスタリング部２３は、地点ＡＢ間、地点ＢＣ間は切断されていないリンクで連結されているため、地点Ａ、Ｂ、Ｃを１個のクラスタに分類する。一方、地点Ｄ、地点Ｅは、ともに他の地点との関連度が０か、既に他の地点とのリンクが切断されているので、クラスタリング部２３は、地点Ｄ、Ｅを地点Ａ、Ｂ、Ｃとは別個のクラスタに分類する。そのため、３個のクラスタが作成されるので、クラスタリング部２３は、地点間のリンクを切断する処理を停止する。そしてクラスタリング部２３は、他の何れの地点に対するリンクも設定されていない地点Ｅを、地点Ｅから最も近い地点Ｄと同じクラスタにマージする。この結果、地点Ａ、Ｂ、Ｃを含むクラスタと、地点Ｄ、Ｅが含まれる二つのクラスタが作成される。
クラスタリング部２３は、作成したクラスタを関心エリア決定部２４に渡す。
【００４４】
関心エリア決定部２４は、クラスタリング部２３から受け取ったクラスタに基づいて、関心エリアを決定する。例えば、関心エリア決定部２４は、受け取ったクラスタに、他のクラスタと識別するための識別情報を付す。そして関心エリア決定部２４は、その識別情報と、クラスタに含まれるそれぞれの地点の位置情報とを関連付けて、記憶部１２に記憶された関心エリアデータベースに記録する。
【００４５】
地図データ生成部２５は、地図設定範囲情報に示された範囲に対応する地図を表す地図データを記憶部１２から読み出す。そして地図データ生成部２５は、関心エリアデータベースを参照して、その地図上で、同一の関心エリアに属するそれぞれの地点を、同一の手法で強調表示することにより、関心エリアが表示された地図データを生成する。例えば、地図データ生成部２５は、地図上で、一つの関心エリアに含まれる各地点に赤い星印を重畳する。一方、地図データ生成部２５は、別の関心エリアに含まれる各地点に、青色の円印を重畳する。
地図データ生成部２５は、生成された地図データを、通信ネットワーク２を介して、地図データの取得を要求したユーザ端末３へ送信する。
【００４６】
図７に示したフローチャートを参照しつつ、制御部１３による関心エリア決定処理の動作手順を説明する。なお、この動作手順は、制御部１３において実行されるコンピュータプログラムによって制御される。
【００４７】
まず、制御部１３の位置順序決定部２１は、ユーザ端末３から受け取った地図設定範囲情報に示された範囲内に含まれる地点に対応する地図データを含む行動データを抽出する（ステップＳ１０１）。次に、位置順序決定部２１は、抽出された行動データごとに、予め設定された所定の時間範囲内に含まれる地点データを時間順に並べた配列表を作成する（ステップＳ１０２）。そして位置順序決定部２１は、作成した配列表を制御部１３の位置関連度算出部２２に渡す。
位置関連度算出部２２は、任意の二つの地点データについて、配列表において時間順に並んだ数を計数する。そして位置関連度算出部２２は、その合計値を、それら二つの地点データに表される二つ地点間の関連度として算出する（ステップＳ１０３）。そして位置関連度算出部２３は、関連度が１以上となる地点間にリンクを設定する。位置関連度算出部２３は、各地点間の関連度及び設定したリンクを表す情報を制御部１３のクラスタリング部２３に渡す。
【００４８】
クラスタリング部２３は、切断されていないリンクが設定された地点間のうち、最も関連度の低い地点間のリンクを切断する（ステップＳ１０４）。そしてクラスタリング部２３は、切断されていないリンクにより接続された地点の集合ごとに、クラスタを作成する（ステップＳ１０５）。その後クラスタリング部２３は、クラスタ数が所定数に到達したか否か判定する（ステップＳ１０６）。ステップＳ１０６において、クラスタ数が所定数に達していない場合、制御部１３は、制御をステップＳ１０４に戻す。一方、ステップＳ１０６において、クラスタ数が所定数に達している場合、クラスタリング部２３は、作成したクラスタを制御部１３の関心エリア決定部２４に渡す。
【００４９】
関心エリア決定部２４は、クラスタリング部２３から受け取ったクラスタに含まれる地点データが表す地点の組を、関心エリアとして決定する（ステップＳ１０７）。そして関心エリア決定部２４は、関心エリアに含まれるそれぞれの地点の位置情報を、関心エリアを他の関心エリアと識別するための識別情報である関心エリアＩＤに関連付けて、記憶部１２に記憶された関心エリアデータベースに記憶する。
最後に、制御部１３の地図データ生成部２５は、地図設定範囲情報に示された範囲に対応する地図上に、同一の関心エリアに属するそれぞれの地点を同一の手法で強調表示することにより、関心エリアが表示された地図データを生成する（ステップＳ１０８）。制御部１３は、生成された地図データを、通信ネットワーク２を介して、地図データを要求したユーザ端末３へ送信する。そして制御部１３は、関心エリア決定処理を終了する。
【００５０】
以上説明してきたように、本発明の第１の実施形態である地図データ生成装置１は、行動データの主体が地図上の各地点を訪問した時間順を調べ、その時間的な並びに基づいてその地点間の関連度を求める。そしてこの地図データ生成装置１は、その関連度が高い地点同士が同一の関心エリアに含まれるように、関心エリアを設定する。行動データの主体が各地点を訪問した時刻が近ければ、それらの地点は特定の事物に関連している可能性が高いと想定される。従って、地図データ生成装置１は、地図上の各地点について記述された情報を用いることなく、同一の事物に関連する地点を含む関心エリアを設定することができる。
【００５１】
次に、本発明に係る推薦経路決定装置を地図データ生成装置に適用した第２の実施形態について説明する。この第２の実施形態に係る地図データ生成装置は、行動データごとに時間順に並べられた地点の順序頻度から、各地点を訪問する移動経路を推薦するものである。
【００５２】
この第２の実施形態に係る地図データ生成装置も、図１に示される構成を有する。そして、第２の実施形態に係る地図データ生成装置の制御部により実現される機能のみが、第１の実施形態に係る地図データ生成装置と異なる。そのため、以下では、第２の実施形態に係る地図データ生成装置の各構成要素のうち、第１の実施形態に係る地図データ生成装置の何れかの構成要素と同一の機能及び構成を有する構成要素については、第１の実施形態に係る地図データ生成装置の対応する構成要素と同一の参照番号を付するとともに、その詳細な説明を省略する。
【００５３】
図８は、第２の実施形態に係る地図データ生成装置１の制御部１３により実現される機能を示す機能ブロック図である。図８に示すように、制御部１３は、位置順序決定部２１と、移動頻度算出部２６と、推薦移動経路決定部２７とを有する。
【００５４】
位置順序決定部２１は、第１の実施形態に係る地図データ生成装置１の位置順序決定部２１と同様に、行動データごとに地点データを時間順に並べた配列表を作成する。そして位置順序決定部２１は、作成した配列表を移動頻度算出部２６に渡す。
【００５５】
移動頻度算出部２６は、位置順序決定部２１から受け取った配列表に基づいて、地図設定範囲情報に示された範囲内の各地点間の移動頻度を算出する。
そのために、移動頻度算出部２６は、特定の二つの地点に着目する。そして移動頻度算出部２６は、配列表上で、特定の順序でそれら二つの着目地点に対応する地点データが並ぶ数を計数し、その合計値を、その二つの着目地点間の特定順序に沿った移動頻度とする。
移動頻度算出部２６は、全ての地点データの組み合わせ及び全ての順序について、移動頻度を算出する。そして移動頻度算出部２６は、求めた移動頻度を推薦移動経路決定部２７に渡す。
【００５６】
推薦移動経路決定部２７は、地図設定範囲情報に示された範囲内の各地点間の移動順序を規定した推薦移動経路を決定する。本実施携帯では、推薦移動経路決定部２７は、推薦移動経路として、各地点を１回通る経路を推薦する。
そのために、推薦移動経路決定部２７は、地図設定範囲情報に示された範囲内の各地点間の移動経路を任意に設定する。そして推薦移動経路決定部２７は、その移動経路に沿って、移動頻度算出部２６により求められた上記の移動頻度を合計する。そして推薦移動経路決定部２７は、移動頻度の合計値が最大となる移動経路を推薦移動経路とする。これにより、推薦移動経路決定部２７は、記憶部１２に記憶された行動データの主体のうちの多くが通る順序に沿った移動経路を推薦できる。
【００５７】
ここで、推薦移動経路決定部２７は、地図設定範囲情報に示された範囲内の地点の全ての移動経路について、移動頻度の合計値を求めてもよい。しかし、地点の数が多くなると、全ての移動経路について移動頻度の合計値を求めるために必要な演算量は膨大なものとなる。そこで、推薦移動経路決定部２７は、何れかの地点間で移動頻度が０となる移動経路については、推薦移動経路としないことにして、移動頻度の合計値の算出を行わないようにしてもよい。
なお、本実施形態において、各地点間の推薦移動経路を決定する問題は、いわゆる巡回セールスマン問題である。したがって、推薦移動経路決定部２７は、巡回セールスマン問題を解くために利用される、例えば、ボルツマンマシンのような相互結合型のニューラルネットワーク、あるいは各地点を移動順序に沿って並べた複数の遺伝子を用いる遺伝的アルゴリズムを利用して、各地点間の推薦移動経路を決定してもよい。
【００５８】
図９は、図２に示された地図２００上の各地点Ａ〜Ｅを、記憶部１２に記憶された行動データごとに時間順に並べて作成された配列表の一例を示す。図９に示された配列表９００は、図５に示された配列表５００と同様に、各行は、抽出された地点データの一つの組を示す。そして配列表９００の左端は、各組の識別番号を示し、配列表９００の上端は、各地点の順序を示している。配列表９００のその他の欄は、地点データの組に含まれる地点名を示している。
図１０は、図９に示された配列表９００に基づいて、移動頻度算出部２６が算出した各地点間の移動頻度を表す移動頻度表を示す。図１０に示される移動頻度表１０００において、各欄は、その欄が属する行の左側に示された地点から、その欄が属する列の上側に示された地点への移動頻度を表す。
【００５９】
例えば、図９の配列表９００を参照すると、時間順で地点Ａの次に地点Ｂが並んでいる回数は２回である。そのため、図１０の移動頻度表１０００では、地点Ａから地点Ｂへの移動頻度を示す欄１００１の値は「２」となる。また、配列表９００を参照すると、時間順で地点Ａの次に地点Ｃが並んでいる回数は１回だけである。そのため、図１０の移動頻度表１０００では、地点Ａから地点Ｃへの移動頻度を示す欄１００２の値は「１」となる。逆に、配列表９００を参照すると、時間順で地点Ｃの次に地点Ａが並んでいる回数は０回である。そのため、図１０の移動頻度表１０００では、地点Ｃから地点Ａへの移動頻度を示す欄１００３の値は「０」となる。
【００６０】
移動頻度表１０００から、移動頻度の合計が最大となる経路は地点Ａ→地点Ｂ→地点Ｃであり、移動頻度の合計値は４である。そこで、推薦移動経路決定部２７は、地点Ａ→地点Ｂ→地点Ｃの経路を推薦移動経路とする。
【００６１】
推薦移動経路決定部２７は、決定した推薦移動経路を、地図設定範囲情報に示された範囲の地図データに関連付けて、記憶部１２に記憶する。あるいは、推薦移動経路決定部２７は、決定した推薦移動経路を地図設定範囲情報に示された範囲の地図データとともに、通信ネットワーク２を介して地図データを要求したユーザ端末３に送信する。あるいはまた、推薦移動経路決定部２７は、地図設定範囲情報に示された範囲の地図上に、決定した推薦移動経路に沿って、各地点間に矢印を重畳した地図データを生成してもよい。そして推薦移動経路決定部２７は、推薦移動経路を表す矢印が重畳された地図データを、通信ネットワーク２を介して地図データを要求したユーザ端末３に送信してもよい。
【００６２】
図１１に示したフローチャートを参照しつつ、制御部１３による推薦移動経路決定処理の動作手順を説明する。なお、この動作手順は、制御部１３において実行されるコンピュータプログラムによって制御される。
【００６３】
まず、制御部１３の位置順序決定部２１は、ユーザ端末３から受け取った地図設定範囲情報に示された範囲内に含まれる地点に対応する地図データを含む行動データを抽出する（ステップＳ２０１）。次に、位置順序決定部２１は、抽出された行動データごとに、予め設定された所定の時間範囲内に含まれる地点データを時間順に並べた配列表を作成する（ステップＳ２０２）。そして位置順序決定部２１は、作成した配列表を制御部１３の移動頻度算出部２６に渡す。
移動頻度算出部２６は、配列表において、二つの地点データが特定の順序で並ぶ数の合計を、それら二つの地点データに表される二つ地点間のその特定の順序に対する移動頻度として算出する（ステップＳ２０３）。移動頻度算出部２６は、各地点間の移動頻度を制御部１３の推薦移動経路決定部２７に渡す。
【００６４】
推薦移動経路決定部２７は、地図設定範囲情報に示された範囲内の各地点間の任意の移動経路に沿って各地点間の移動頻度を合計し、その移動頻度の合計値が最大となる移動経路を推薦移動経路として決定する（ステップＳ２０４）。そして推薦移動経路決定部２７は、上記のように、決定した推薦移動経路を、地図設定範囲情報に示された範囲の地図データに関連付けて、記憶部１２に記憶する。あるいは、推薦移動経路決定部２７は、決定した推薦移動経路を通信ネットワーク２を介して地図データを要求したユーザ端末３に送信する。そして制御部１３は、推薦移動経路決定処理を終了する。
【００６５】
以上説明してきたように、本発明の第２の実施形態である地図データ生成装置は、行動データに含まれる地図上の各地点の時間順に基づいて、その地点間の移動頻度を求め、その移動頻度の合計が最大となるように推薦する移動経路を決定する。そのため、この地図データ生成装置は、地図上の各地点について記述された情報を用いることなく、それら複数の地点を訪問するのに適した移動経路を提案することができる。
【００６６】
なお、この第２の実施形態に係る地図データ生成装置は、ユーザ端末３から、ユーザの現在位置情報を取得できる場合、地図設定範囲情報に示された範囲内に含まれる、何れかの行動データに示された地点のうち、その現在位置に最も近い地点を始点とする推薦移動経路を決定してもよい。
この場合、推薦移動経路決定部２７は、移動頻度算出部２６により求められた各地点間の移動頻度から、始点に対して最も移動頻度の高い地点を、次の推薦訪問地点とする。そして推薦移動経路決定部２７は、その推薦訪問地点を表す情報（例えば、位置情報あるいは、ユーザの現在地点からその推薦訪問地点までの経路情報を含む）を、通信ネットワーク２を介してユーザ端末３に送信する。
あるいは、推薦移動経路決定部２７は、ユーザの現在位置に最も近い、何れかの行動データに示された地点を始点とする全ての経路について移動頻度の合計値を求め、その合計値が最大となる経路を推薦移動経路としてもよい。例えば、図１０に示された移動頻度表１０００が得られている場合において、地図データ生成装置がユーザ端末３からユーザの現在位置が地点Ｂであることを知らされた場合、地点Ｂを始点とする移動経路のうち、各地点間の移動頻度の合計値が最大となる経路は、地点Ｂ→地点Ｃ→地点Ａである。そこで推薦移動経路決定部２７は、ユーザ端末３に対して、地点Ｃを経由して地点Ａへ向かう経路を推薦移動経路として通知する。
【００６７】
次に、本発明に係る推薦経路決定装置を地図データ生成装置に適用した第３の実施形態について説明する。この第３の実施形態に係る地図データ生成装置は、選択された複数の関心エリアについて、行動データごとに時間順に並べられた地点の順序頻度から、各関心エリアを訪問する移動経路を推薦するものである。
【００６８】
この第３の実施形態に係る地図データ生成装置も、図１に示される構成を有する。そして、第３の実施形態に係る地図データ生成装置の制御部により実現される機能のみが、第１の実施形態に係る地図データ生成装置と異なる。そのため、以下では、第３の実施形態に係る地図データ生成装置の各構成要素のうち、第１の実施形態に係る地図データ生成装置の何れかの構成要素と同一の機能及び構成を有する構成要素については、第１の実施形態に係る地図データ生成装置の対応する構成要素と同一の参照番号を付するとともに、その詳細な説明を省略する。
【００６９】
この第３の実施形態に係る地図データ生成装置では、第１の実施形態に係る地図データ生成装置あるいはユーザにより、予め第１の実施形態に係る地図データ生成装置に関して説明した関心エリアデータベースが作成される。そしてこの第３の実施形態に係る地図データ生成装置の記憶部１２は、作成された関心エリアデータベースを記憶する。
【００７０】
図１２は、第３の実施形態に係る地図データ生成装置１の制御部１３により実現される機能を示す機能ブロック図である。図１２に示すように、制御部１３は、位置順序決定部２１と、移動頻度算出部２６と、エリア間移動頻度算出部２８と、エリア間推薦移動経路決定部２９とを有する。
【００７１】
位置順序決定部２１は、第１の実施形態に係る地図データ生成装置１の位置順序決定部２１と同様に、ユーザにより指定され、かつ通信ネットワーク２を介してユーザ端末３から受信した地図設定範囲情報に示された範囲内の地点を含む行動データごとに、地点データを時間順に並べた配列表を作成する。あるいは、位置順序決定部２１は、ユーザ端末３により指定された複数の関心エリアの何れかに含まれる地点を少なくとも一つ含む行動データごとに、地点データを時間順に並べた配列表を作成する。そして位置順序決定部２１は、作成した配列表を移動頻度算出部２６に渡す。
移動頻度算出部２６は、第２の実施形態に係る地図データ生成装置１の移動頻度算出部２６と同様に、位置順序決定部２１から受け取った配列表に基づいて、地図設定範囲情報に示された範囲内の各地点間の移動頻度を算出する。そして移動頻度算出部２６は、各地点間の移動頻度をエリア間移動頻度算出部２８に通知する。
【００７２】
エリア間移動頻度算出部２８は、移動頻度算出部２６により算出された各地点間の移動頻度に基づいて、地図設定範囲情報により示された地図の範囲内に含まれる関心エリア間、あるいはユーザ端末３を介して指定された関心エリア間の移動頻度であるエリア間移動頻度を算出する。
具体的には、エリア間移動頻度算出部２８は、関心エリア間に跨る各地点間の移動頻度を、関心エリア単位で合計することにより、エリア間移動頻度を算出する。
【００７３】
以下、関心エリア間の移動頻度の算出例を、図１３〜図１５を参照しつつ説明する。この例では、エリア間移動頻度算出部２８は３個の関心エリアα、β、γ間の移動頻度を算出するものとする。
図１３は、地図設定範囲情報により示された地図の範囲内に含まれる関心エリアを記録した、関心エリアテーブルの一例を示す。図１３に示された関心エリアテーブル１３００では、各行が一つの関心エリアを表す。そして関心エリアテーブル１３００の左端は関心エリアＩＤを示し、その他の欄は、各関心エリアに含まれる地点名を示す。図１３に示されるように、この関心エリアテーブル１３００は、３個の関心エリアα、β、γを記録する。そして関心エリアαは、地点１〜３を含む。また関心エリアβは、地点４、５を含む。さらに関心エリアγは、地点６、７を含む。
図１４は、移動頻度算出部２６により算出された図１３に示された３個の関心エリアに含まれる各地点間の移動頻度表の一例を示す。図１４に示される移動頻度表１４００において、各欄は、その欄が属する行の左側に示された地点から、その欄が属する列の上側に示された地点への移動頻度を表す。
【００７４】
エリア間移動頻度算出部２８は、図１４に示される移動頻度表１４００において、始点が関心エリアαに含まれる地点（地点１〜３）から、終点が関心エリアβに含まれる地点（地点４、５）への移動頻度を合計する。例えば、地点１から地点４及び地点５への移動頻度は、それぞれ１、０であり、地点２から地点４及び地点５への移動頻度は、それぞれ１であり、地点３から地点４及び地点５への移動頻度は、それぞれ０である。従って、関心エリアαから関心エリアβへの移動頻度は３となる。逆に、地点４から地点１〜３への移動頻度は、それぞれ３、１、０であり、地点５から地点１〜３への移動頻度は、それぞれ２、２、１である。従って、関心エリアβから関心エリアαへの移動頻度は９となる。
図１５は、図１４に示された移動頻度表１４００に基づいて、エリア間移動頻度算出部２８が算出した各関心エリア間の移動頻度を示すエリア移動頻度表を示す。図１５に示されたエリア移動頻度表１５００において、各欄は、その欄が属する行の左側に示された関心エリアから、その欄が属する列の上側に示された関心エリアへの移動頻度を表す。
エリア間移動頻度算出部２８は、全ての関心エリアの組み合わせについて、上記の計数を実行する。そしてエリア間移動頻度算出部２８は、求めたエリア間移動頻度をエリア間推薦移動経路決定部２９に通知する。
【００７５】
エリア間推薦移動経路決定部２９は、地図設定範囲情報に示された範囲内の各関心エリア間の移動経路を推薦する、推薦移動経路を決定する。本実施携帯では、エリア間推薦移動経路決定部２９は、推薦移動経路として、各関心エリアを１回通る経路を推薦する。
そのために、エリア間推薦移動経路決定部２９は、地図設定範囲情報に示された範囲内の各関心エリア間の移動経路を任意に設定する。そしてエリア間推薦移動経路決定部２９は、その移動経路に沿って、エリア間移動頻度算出部２８により求められた上記のエリア間移動頻度を合計する。そしてエリア間推薦移動経路決定部２９は、移動頻度の合計値が最大となる移動経路を推薦移動経路とする。
なお、エリア間推薦移動経路決定部２９は、演算量を抑制するために、第２の実施形態の地図データ生成装置の制御部が有する推薦移動経路決定部２７と同様に、何れかの地点間で移動頻度が０となる移動経路については、推薦移動経路としないことにして、移動頻度の合計値の算出を行わないようにしてもよい。またエリア間推薦移動経路決定部２９は、推薦移動経路決定部２７と同様に、ボルツマンマシンのような相互結合型のニューラルネットワーク、あるいは各地点を移動順序に沿って並べた複数の遺伝子を用いる遺伝的アルゴリズムを利用して、各関心エリア間の推薦移動経路を決定してもよい。
【００７６】
例えば、図１５に示されたエリア移動頻度表１５００に基づいて、エリア間推薦移動経路決定部２９が推薦移動経路を決定する場合、移動頻度の合計が最大となる経路は関心エリアα→関心エリアγ→関心エリアβであり、移動頻度の合計値は１８である。そこで、エリア間推薦移動経路決定部２９は、関心エリアα→関心エリアγ→関心エリアβの経路を推薦移動経路とする。
【００７７】
エリア間推薦移動経路決定部２９は、決定した推薦移動経路を、地図設定範囲情報に示された範囲の地図データに関連付けて、記憶部１２に記憶する。あるいは、エリア間推薦移動経路決定部２９は、決定した推薦移動経路を地図設定範囲情報に示された範囲の地図データとともに、通信ネットワーク２を介して地図データを要求したユーザ端末３に送信する。あるいはまた、エリア間推薦移動経路決定部２９は、地図設定範囲情報に示された範囲の地図上に、決定した推薦移動経路に沿って、各関心エリアに含まれる複数の地点の重心間に矢印を重畳した地図データを生成してもよい。そしてエリア間推薦移動経路決定部２９は、推薦移動経路を表す矢印が重畳された地図データを、通信ネットワーク２を介して地図データを要求したユーザ端末３に送信してもよい。
【００７８】
図１６に示したフローチャートを参照しつつ、制御部１３による、エリア間の推薦移動経路決定処理の動作手順を説明する。なお、この動作手順は、制御部１３において実行されるコンピュータプログラムによって制御される。
【００７９】
まず、制御部１３の位置順序決定部２１は、ユーザ端末３から受け取った地図設定範囲情報に示された範囲内に含まれる関心エリア、及びその範囲内含まれる地点に対応する地点データを含む行動データを抽出する（ステップＳ３０１）。次に、位置順序決定部２１は、抽出された行動データごとに、予め設定された所定の時間範囲内に含まれる地点データを時間順に並べた配列表を作成する（ステップＳ３０２）。そして位置順序決定部２１は、作成した配列表を制御部１３の移動頻度算出部２６に渡す。
移動頻度算出部２６は、配列表において、二つの地点データが特定の順序で並ぶ数の合計を、それら二つの地点データに表される二つ地点間のその特定の順序に対する移動頻度として算出する（ステップＳ３０３）。移動頻度算出部２６は、各地点間の移動頻度を制御部１３のエリア間移動頻度算出部２８に通知する。
エリア間移動頻度算出部２８は、関心エリア間に跨る各地点間の移動頻度を、関心エリア単位で合計することにより、エリア間移動頻度を算出する（ステップＳ３０４）。そしてエリア間移動頻度算出部２８は、各関心エリア間の移動頻度を制御部１３のエリア間推薦移動経路決定部２９に通知する。
【００８０】
エリア間推薦移動経路決定部２９は、地図設定範囲情報に示された範囲内の各関心エリア間の任意の移動経路に沿って各関心エリア間の移動頻度を合計し、その移動頻度の合計値が最大となる移動経路を推薦移動経路として決定する（ステップＳ３０５）。そしてエリア間推薦移動経路決定部２９は、上記のように、決定した推薦移動経路を、地図設定範囲情報に示された範囲の地図データに関連付けて、記憶部１２に記憶する。あるいは、エリア間推薦移動経路決定部２９は、決定した推薦移動経路を通信ネットワーク２を介して地図データを要求したユーザ端末３に送信する。そして制御部１３は、エリア間の推薦移動経路決定処理を終了する。
【００８１】
以上説明してきたように、本発明の第３の実施形態である地図データ生成装置は、行動データに含まれる地図上の各地点の時間順に基づいて、その地点間の移動頻度を求め、その地点間の移動頻度を、予め設定された関心エリア間で集計することにより、関心エリア間の移動頻度を求める。そしてこの地図データ生成装置は、エリア間の移動頻度の合計が最大となるように推薦する移動順序を決定する。そのため、この地図データ生成装置は、地図上の各地点について記述された情報を用いることなく、ユーザが複数のエリアを訪問するのに適した移動経路を提案することができる。
【００８２】
なお、この第３の実施形態に係る地図データ生成装置も、第２の実施形態に係る地図データ生成装置と同様に、ユーザ端末３からユーザの現在位置情報を取得できる場合、その現在位置に最も近い関心エリアを始点とするエリア間の推薦移動経路を決定してもよい。この場合、エリア間推薦移動経路決定部２９は、エリア間移動頻度算出部２８により求められた各関心エリア間の移動頻度から、ユーザの現在位置に最も近い関心エリアに対して最も移動頻度の高い関心エリアを、次の推薦訪問エリアとする。そしてエリア間推薦移動経路決定部２９は、その推薦訪問エリアを表す情報（例えば、位置情報あるいは、ユーザの現在地点からその推薦訪問エリアまでの経路情報を含む）を、通信ネットワーク２を介してユーザ端末３に送信する。
あるいは、エリア間推薦移動経路決定部２９は、ユーザの現在位置に最も近い関心エリアを始点とする全ての経路について、移動頻度の合計値を求め、その合計値が最大となる経路を推薦移動経路としてもよい。なお、エリア間推薦移動経路決定部２９は、ユーザの現在位置と最も近い地点が属する関心エリアを、ユーザの現在位置に最も近い関心エリアとすることができる。
【００８３】
本発明は、上記の実施形態に限定されない。例えば、他の実施形態に係る地図データ生成装置は、図１に示した構成を有するとともに、その制御部は、上記の各実施形態の地図データ生成装置の制御部が有する各機能を全て有してもよい。そしてこの地図データ生成装置は、関心エリアの設定、地点間の推薦移動経路の決定及び関心エリア間の推薦移動経路の決定を一つの装置で実行できるようにしてもよい。
【００８４】
また、上記の各実施形態における、制御部の位置関連度算出部及び移動頻度算出部は、各地点間の距離あるいは道のりを考慮して、２地点間の関連度及び移動頻度を算出してもよい。例えば、位置関連度算出部及び移動頻度算出部は、２地点間の距離あるいは道のりが近いほど大きくなる重みを設定し、それら２地点が配列表上で時間順に並んだとき、その重みを合計することにより、関連度及び移動頻度を算出してもよい。あるいは、各地点について記述された情報があれば、位置関連度算出部及び移動頻度算出部はその記述情報を考慮して、２地点間の関連度及び移動頻度を算出してもよい。例えば、位置関連度算出部及び移動頻度算出部は、配列表上で時間順に並んだ２地点の両方に同じ特性を表す記述情報が付されていれば、その２地点間の関連度及び移動頻度がそのような記述情報が付されていない場合よりも大きくなるように、関連度及び移動頻度を算出してもよい。
【００８５】
また、本発明の他の実施形態に係る地図データ生成装置は、上記の各実施形態の地図データ生成装置の構成要素に加え、ユーザからの入力操作を受け付けるためのキーボード、マウスなどの操作部と、地図を表示するための液晶ディスプレイなどの表示部を有していてもよい。そしてこの地図データ生成装置は、操作部を介して設定された地図設定範囲情報に基づいて、関心エリアを設定し、地点間の推薦移動経路を決定し、または関心エリア間の推薦移動経路を決定してもよい。
以上のように、当業者は、本発明の範囲内で、実施される形態に合わせて様々な変更を行うことができる。
【符号の説明】
【００８６】
１地図データ生成装置
２通信ネットワーク
３ユーザ端末
１１通信部
１２記憶部
１３制御部
２１位置順序決定部
２２位置関連度算出部
２３クラスタリング部
２４関心エリア決定部
２５地図データ生成部
２６移動頻度算出部
２７推薦移動経路決定部
２８エリア間移動頻度算出部
２９エリア間推薦移動経路決定部

【特許請求の範囲】
【請求項１】
指定された地図範囲に含まれる複数の地点を、少なくとも一つの関心エリアに分類する関心エリア設定装置であって、
前記複数の地点のうちの２以上の地点の位置情報と、当該２以上の地点のそれぞれに対応する時間情報とを含む行動データを少なくとも一つ記憶する記憶部（１２）と、
前記行動データごとに、前記指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成する位置順序決定部（２１）と、
前記配列表において、前記複数の地点のうちの二つの地点が時間順に隣接した回数を、当該二つの地点間の関連度として算出し、当該関連度が正の所定値以上となる地点間にリンクを設定する位置関連度算出部（２２）と、
前記複数の地点に含まれる二つの地点間のリンクを、当該二つの地点間の前記関連度が低い方から順に切断し、前記リンクによって接続された地点の集合ごとに別個のクラスタに分類することにより、１以上の所定数のクラスタを作成するクラスタリング部（２３）と、
前記所定数のクラスタのそれぞれについて、クラスタ内に含まれる地点の集合を関心エリアとして決定する関心エリア決定部（２４）と、
を有することを特徴とする関心エリア設定装置。
【請求項２】
前記クラスタリング部（２３）は、前記複数の地点のうち、他の何れの地点に対してもリンクが設定されていない地点を、何れかのクラスタに含まれる地点のうちの最も近い地点が属するクラスタに含める、請求項１に記載の関心エリア設定装置。
【請求項３】
指定された地図範囲に含まれる複数の地点を経由する推薦経路を決定する推薦経路決定装置であって、
前記複数の地点のうちの２以上の地点の位置情報と、当該２以上の地点のそれぞれに対応する時間情報とを含む行動データを少なくとも一つ記憶する記憶部（１２）と、
前記行動データごとに、前記指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成する位置順序決定部（２１）と、
前記配列表において、前記複数の地点のうちの二つの地点が特定の順序で並んだ回数を、当該二つの地点間の当該特定順序に沿った移動頻度として算出する移動頻度算出部（２６）と、
前記複数の地点のそれぞれを一度経由する移動経路のうち、当該移動経路に沿った前記移動頻度の合計が最大となる移動経路を推薦経路とする推薦移動経路決定部（２７）と、
を有することを特徴とする推薦経路決定装置。
【請求項４】
前記推薦移動経路決定部（２７）は、前記複数の地点のうち、ユーザの現在位置に最も近い地点を始点とする、前記複数の地点のそれぞれを一度経由する移動経路のうち、当該移動経路に沿った前記移動頻度の合計が最大となる移動経路を前記推薦経路とする、請求項３に記載の推薦経路決定装置。
【請求項５】
前記推薦移動経路決定部（２７）は、前記複数の地点のうちのユーザの現在位置に最も近い地点を始点とし、当該始点から前記複数の地点のそれぞれへの前記移動頻度のうちの最大値を求め、当該最大値に対応する地点を次の移動先とする、請求項３に記載の推薦経路決定装置。
【請求項６】
指定された地図範囲に含まれる複数のエリアを経由する推薦経路を決定する推薦経路決定装置であって、
前記複数のエリアの何れかに含まれる２以上の地点の位置情報と、当該２以上の地点のそれぞれに対応する時間情報とを含む行動データを少なくとも一つ記憶する記憶部（１２）と、
前記行動データごとに、前記指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成する位置順序決定部（２１）と、
前記配列表において、前記複数の地点のうちの二つの地点が特定の順序で並んだ回数を、当該二つの地点間の当該特定順序に沿った移動頻度として算出する移動頻度算出部（２６）と、
前記複数のエリアのうちの二つのエリアの一方に含まれる全ての地点から、当該二つのエリアのうちの他方のエリアに含まれる全ての地点への前記移動頻度の合計値を、当該一方のエリアから他方のエリアへのエリア間移動頻度として算出するエリア間移動頻度算出部（２７）と、
前記複数のエリアのそれぞれを一度経由する移動経路のうち、当該移動経路に沿った前記エリア間移動頻度の合計が最大となる移動経路を推薦経路とする推薦移動経路決定部（２７）と、
を有することを特徴とする推薦経路決定装置。
【請求項７】
前記推薦移動経路決定部（２７）は、前記複数のエリアのうち、ユーザの現在位置に最も近いエリアを始点とする、前記複数のエリアのそれぞれを一度経由する移動経路のうち、当該移動経路に沿った前記エリア間移動頻度の合計が最大となる移動経路を前記推薦経路とする、請求項６に記載の推薦経路決定装置。
【請求項８】
前記推薦移動経路決定部（２７）は、前記複数のエリアのうちのユーザの現在位置に最も近いエリアを始点とし、当該始点から前記複数のエリアのそれぞれへの前記エリア間移動頻度のうちの最大値を求め、当該最大値に対応するエリアを次の移動先とする、請求項６に記載の推薦経路決定装置。
【請求項９】
指定された地図範囲に含まれる複数の地点を、少なくとも一つの関心エリアに分類する関心エリア設定方法であって、
前記指定された地図範囲に含まれる複数の地点のうちの２以上の地点の位置情報と、当該２以上の地点のそれぞれに対応する時間情報とを含む行動データごとに、前記指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成するステップと、
前記配列表において、前記複数の地点のうちの二つの地点が時間順に隣接した回数を、当該二つの地点間の関連度として算出し、当該関連度が正の所定値以上となる地点間にリンクを設定するステップと、
前記複数の地点に含まれる二つの地点間のリンクを、当該二つの地点間の前記関連度が低い方から順に切断し、前記リンクによって接続された地点の集合ごとに別個のクラスタに分類することにより、１以上の所定数のクラスタを作成するステップと、
前記所定数のクラスタのそれぞれについて、クラスタ内に含まれる地点の集合を関心エリアとして決定するステップと、
を有することを特徴とする関心エリア設定方法。
【請求項１０】
指定された地図範囲に含まれる複数の地点を経由する推薦経路を決定する推薦経路決定方法であって、
指定された地図範囲に含まれる複数の地点のうちの２以上の地点の位置情報と、当該２以上の地点のそれぞれに対応する時間情報とを含む行動データごとに、前記指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成するステップと、
前記配列表において、前記複数の地点のうちの二つの地点が特定の順序で並んだ回数を、当該二つの地点間の当該特定順序に沿った移動頻度として算出するステップと、
前記複数の地点のそれぞれを一度経由する移動経路のうち、当該移動経路に沿った前記移動頻度の合計が最大となる移動経路を推薦経路とするステップと、
を有することを特徴とする推薦経路決定方法。
【請求項１１】
指定された地図範囲に含まれる複数のエリアを経由する推薦経路を決定する推薦経路決定方法であって、
前記複数のエリアの何れかに含まれる２以上の地点の位置情報と、当該２以上の地点のそれぞれに対応する時間情報とを含む行動データごとに、前記指定された地図範囲に含まれる複数の地点を時間順に並べた配列表を作成するステップと、
前記配列表において、前記複数の地点のうちの二つの地点が特定の順序で並んだ回数を、当該二つの地点間の当該特定順序に沿った移動頻度として算出するステップと、
前記複数のエリアのうちの二つのエリアの一方に含まれる全ての地点から、当該二つのエリアのうちの他方のエリアに含まれる全ての地点への前記移動頻度の合計値を、当該一方のエリアから他方のエリアへのエリア間移動頻度として算出するステップと、
前記複数のエリアのそれぞれを一度経由する移動経路のうち、当該移動経路に沿った前記エリア間移動頻度の合計が最大となる移動経路を推薦経路とするステップと、
を有することを特徴とする推薦経路決定方法。

【図１】