(57)【特許請求の範囲】
【請求項１】
携帯端末から当該携帯端末の位置データを複数の期間グループに渡り間欠的に取得し、この取得された位置データを当該位置データの計測時刻が含まれる期間グループに関連付けて記憶する手段と、
前記記憶された位置データを前記期間グループごとに読み出し、当該期間グループごとに当該期間グループに計測時刻が含まれる位置データに対しクラスタリング処理を行って、複数の位置データが含まれる滞在エリアの和集合を抽出する手段と、
前記期間グループごとに抽出されたすべての滞在エリアの集合を対象として、これらの滞在エリアの集合に含まれる各滞在エリア間の距離をそれぞれ計算し、この計算された距離が予め設定した第１のしきい値以下の滞在エリア同士を同じ滞在場所を表していると判断して統合し共通滞在エリアとして出力する手段と、
前記統合処理により得られた共通滞在エリアに含まれる位置データの各々について、当該位置データが出現する期間グループの数をカウントし、このカウント値が予め設定した第２のしきい値以上となる位置データを含む共通滞在エリアの集合を抽出する手段と、
前記記憶された位置データのうち推定対象の期間グループに計時時刻が含まれる位置データを読み出し、この読み出された位置データと前記抽出された共通滞在エリアの集合に含まれる滞在エリアとの間の距離を計算する手段と、
前記距離の計算結果に基づいて、当該計算された距離が予め設定した第３のしきい値以下となる滞在エリアを抽出すると共に、この抽出された滞在エリアに含まれる位置データの系列を選択する手段と、
前記抽出された滞在エリアと当該滞在エリアに含まれる前記選択された位置データの系列を表す情報を、前記推定対象の期間グループにおける滞在系列を表す情報として出力する手段と
を具備することを特徴とする滞在場所推定装置。
【請求項２】
前記共通滞在エリアを出力する手段は、滞在エリア間の距離を計算する手段として、滞在エリアの重心の座標間の距離を計算する手段と、滞在エリアに含まれる複数の位置データのうち位置の座標が最も近いもの同士の距離を計算する手段と、滞在エリアに含まれるすべての位置データを含む最小の矩形領域間の距離を計算する手段のいずれかを使用することを特徴とする請求項１記載の滞在場所推定装置。
【請求項３】
携帯端末から当該携帯端末の位置データを複数の期間グループに渡り間欠的に取得し、この取得された位置データを当該位置データの計測時刻が含まれる期間グループに関連付けて記憶する過程と、
前記記憶された位置データを前記期間グループごとに読み出し、当該期間グループごとに当該期間グループに計測時刻が含まれる位置データに対しクラスタリング処理を行って、複数の位置データが含まれる滞在エリアの集合を抽出する過程と、
前記期間グループごとに抽出されたすべての滞在エリア集合を対象として、これらの滞在エリア集合に含まれる各滞在エリア間の距離をそれぞれ計算し、この計算された距離が予め設定した第１のしきい値以下の滞在エリア同士を同じ滞在場所を表していると判断して統合し、この統合された滞在エリアを共通滞在エリアとして出力する過程と、
前記出力された共通滞在エリアに計測時刻が含まれる位置データの各々について、当該位置データが出現する期間グループの数をカウントし、このカウント値が予め設定した第２のしきい値以上となる位置データを含む共通滞在エリアの集合を抽出する過程と、
前記記憶された位置データのうち推定対象の期間グループに計時時刻が含まれる位置データを読み出し、この読み出された位置データと前記抽出された共通滞在エリアの集合に含まれる滞在エリアとの間の距離を計算する過程と、
前記距離の計算結果に基づいて、当該計算された距離が予め設定した第３のしきい値以下となる滞在エリアを抽出すると共に、この抽出された滞在エリアに含まれる位置データの系列を選択する過程と、
前記抽出された滞在エリアと当該滞在エリアに含まれる前記選択された位置データの系列を表す情報を、前記推定対象の期間グループにおける滞在系列を表す情報として出力する過程と
を具備することを特徴とする滞在場所推定方法。
【請求項４】
前記共通滞在エリアを出力する過程は、滞在エリア間の距離を計算する方法として、滞在エリアの重心の座標間の距離を計算する方法と、滞在エリアに含まれる複数の位置データのうち位置の座標が最も近いもの同士の距離を計算する方法と、滞在エリアに含まれるすべての位置データを含む最小の矩形領域間の距離を計算する方法のいずれかを使用することを特徴とする請求項３記載の滞在場所推定方法。
【請求項５】
請求項１又は２記載の滞在場所推定装置が備える各手段に対応する処理を、前記滞在場所推定装置が備えるプロセッサに実行させる滞在場所推定プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、ＧＰＳ（Global Positioning System）に代表される位置計測デバイスによって取得されたユーザの位置情報からユーザが滞留した地点を推定し、その推定結果をユーザの行動予測に提供する滞在場所推定装置、方法及びプログラムに関する。
【背景技術】
【０００２】
ＧＰＳに代表される位置計測デバイスを搭載した携帯端末をユーザが携行することで、取得・蓄積された位置データをもとに予測モデルを構成し、ユーザの移動を予測する手法が提案されている。例えば、非特許文献１には、取得されたＧＰＳデータからユーザが滞在した場所をクラスタリングによって抽出し、蓄積されたデータをもとに滞在場所間の移動を表すマルコフモデルを構築し、行動を予測する手法が記載されている。
【０００３】
また、非特許文献２には、同様にＧＰＳデータをクラスタリングすることによってユーザが滞在した場所を抽出したのち、ユーザの一日の行動を滞在場所を並べた系列で表現し、その後この系列に対し系列パターンマイニング処理を適用して系列パターンを抽出し、この抽出されたパターンを用いることでユーザの行動を予測する手法が記載されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Daniel Ashbrook and Thad Starner, “Using GPS to Learn Significant Locations and Predict Movement across Multiple Users”, Personal and Ubiquitous Computing 7(5), pp. 275-286 (2003)
【非特許文献２】M. Nishino, T. Yamada, S. Seko, M. Motegi, S. Muto and M. Abe, A place prediction algorithm based on frequent time-sensitive patterns, In Pervasive 2009 adjunctive proceedings, 2009
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところが、実環境で携帯端末を用いて位置を計測しようとすると、例えばＧＰＳ信号を受信し難い場所の存在や携帯端末の性能的な限界の影響により、ユーザの位置計測に失敗したり計測を行う時間間隔が長くなり、その結果位置の計測結果が疎になる場合がある。このような場合、ユーザの滞在場所の系列を把握に取得できなくなり、結果として系列パターンの抽出や行動予測といった処理を失敗するという課題があった。
【０００６】
この発明は上記事情に着目してなされたもので、その目的とするところは、ユーザの位置を密に計測することが困難な場合でも、ユーザの滞在場所の系列を正確に検出できるようにし、これにより高精度の行動予測を可能にする滞在場所推定装置、方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００７】
一般に、ユーザの日常の行動には、通勤や通学、商店街で夕飯の買い物をするといった、日々繰り返される行動が存在する。この種の行動については、ある日の行動の位置データが疎な場合でも、同じ行動をとっている別の日に取得された位置データを用いることで、ユーザがどこに滞在したかを推定することが可能である。
【０００８】
この発明の１つの観点は、以上の点に着目してなされたもので、携帯端末から当該携帯端末の位置データを複数の期間グループに渡り間欠的に取得して、この取得された位置データを当該位置データの計測時刻が含まれる期間グループに関連付けて記憶する。この状態で、上記期間グループごとに当該期間グループに計測時刻が含まれる位置データに対しクラスタリング処理を行って、複数の位置データが含まれる滞在エリアの集合を抽出し、この抽出されたすべての滞在エリア集合を対象としてこれらの滞在エリア集合に含まれる各滞在エリア間の距離をそれぞれ計算して、この距離が予め設定した第１のしきい値以下の滞在エリア同士を同じ滞在場所を表していると判断して統合し、この滞在エリアを共通滞在エリアとして出力する。次に、上記統合処理により得られた共通滞在エリアに含まれる位置データの各々について、当該位置データが出現する期間グループの数をカウントし、このカウント値が予め設定した第２のしきい値以上となる位置データを含む共通滞在エリアの集合を抽出する。そして、上記記憶された位置データのうち推定対象の期間グループに計時時刻が含まれる位置データを読み出し、この読み出された位置データと上記抽出された共通滞在エリアの集合に含まれる滞在エリアとの間の距離を計算し、この距離の計算結果に基づいて、当該計算された距離が予め設定した第３のしきい値以下となる滞在エリアを抽出すると共にこの抽出された滞在エリアに含まれる位置データの系列を選択し、上記抽出された滞在エリアと当該滞在エリアに含まれる上記選択された位置データの系列を表す情報を、上記推定対象の期間グループにおける滞在系列を表す情報として出力するようにしたものである。
【０００９】
したがって、過去の複数の期間グループにおいて計測された位置データからユーザが毎日定常的に滞在する共通滞在エリアが抽出され、この抽出された共通滞在エリアの情報に基づいて、推定対象とする期間グループにおけるユーザの滞在場所を推定することが可能となる。このため、例えば携帯端末の性能的な限界等の影響により、ユーザの位置計測に失敗したりまた計測を行う時間間隔が長くなり、その結果位置データの計測密度が疎になったとしても、推定対象とする期間にユーザがどの場所に滞在したかを高い確率で推定することが可能となる。
【００１０】
上記共通滞在エリアを出力する際に使用される滞在エリア間の距離計算手段又は過程としては、滞在エリアの重心の座標間の距離を計算する手段又は過程と、滞在エリアに含まれる複数の位置データのうち位置の座標が最も近いもの同士の距離を計算する手段又は過程と、滞在エリアに含まれるすべての位置データを含む最小の矩形領域間の距離を計算する手段又は過程のいずれかを使用する。  
このようにすると、比較的容易に滞在エリア間の距離を計算することができる。
【発明の効果】
【００１１】
すなわちこの発明の１つの観点によれば、ユーザの位置を密に計測することが困難な場合でも、ユーザの行動を正確に予測可能にする滞在場所推定装置、方法及びプログラムを提供することができる。
【図面の簡単な説明】
【００１２】
【図１】この発明の一実施形態に係わる滞在場所推定方法を実施するシステムの構成を示す図。
【図２】図１に示したシステムにおける携帯端末の機能構成を示すブロック図。
【図３】図１に示したシステムにおけるサービスサーバの機能構成を示すブロック図。
【図４】図３に示したサービスサーバに設けられる位置データ記憶部に記憶される位置データの例を示す図。
【図５】図３に示したサービスサーバに設けられる滞在場所データ記憶部に記憶されるデータの例を示す図。
【図６】図３に示したサービスサーバに設けられる滞在場所抽出処理部による滞在場所抽出処理の手順と内容を示すフローチャート。
【図７】図６に示した滞在場所抽出処理の手順中における共通滞在場所抽出処理の手順と内容を示すフローチャート。
【図８】図７に示した共通滞在場所抽出処理の手順中における日数カウント処理の手順と内容を示すフローチャート。
【図９】図６に示した滞在場所抽出処理の動作説明に使用するための図。
【図１０】図７に示した共通滞在場所抽出処理の動作説明に使用するための図。
【図１１】図３に示したサービスサーバに設けられる滞在系列抽出処理部による滞在系列抽出処理の手順と内容を示すフローチャート。
【図１２】図１１に示した滞在系列抽出処理の動作説明に使用するための図。
【発明を実施するための形態】
【００１３】
以下、図面を参照してこの発明に係わる実施形態を説明する。  
図１は、この発明の一実施形態に係わる滞在場所推定装置を備えたシステムを示す図である。このシステムは、それぞれユーザが所持する複数の携帯端末ＭＳ１〜ＭＳｎを、通信ネットワークＮＷを介して、滞在場所推定装置としてのサービスサーバＳＶに接続可能としたものである。
【００１４】
通信ネットワークＮＷは、ＩＰ（Internet Protocol）網と、このＩＰ網にアクセスするためのアクセス網とから構成される。アクセス網としては、公衆通信網、携帯電話網、ＬＡＮ（Local Area Network）、無線ＬＡＮ、ＣＡＴＶ（Cable Television）網等が用いられる。
【００１５】
携帯端末ＭＳ０〜ＭＳｎは、携帯電話機やＰＤＡ（Personal Digital Assistant）、ネットブック等と呼ばれる携帯型のパーソナル・コンピュータからなり、次のように構成される。図２はその機能構成を示すブロック図である。  
すなわち、携帯端末ＭＳ１〜ＭＳｎは、制御部１１と、無線送受信部１２と、符号化処理部１３と、音声インタフェースとしてのスピーカ１４及びマイクロホン１５と、ＧＰＳ（Global Positioning System）受信機１６と、記憶部１７と、入力部１８及び表示部１９とを備えている。
【００１６】
無線送受信部１２は、アンテナ１２ａを介して通信ネットワークＮＷとの間で無線信号を送受信する。符号化処理部１３は、音声やテキスト等の情報データ及び制御データを送受信するために必要な符号化処理及び復号処理を行う。ＧＰＳ受信機１６は、図示しない複数のＧＰＳ衛星から送信されるＧＰＳ信号をアンテナ１６ａを介して受信する。記憶部１７は、上記情報データを記憶すると共に、後述するＧＰＳ計測部１１１により得られたＧＰＳデータを記憶する。入力部１８はダイヤルキーパッド及び複数の機能キーからなり、ユーザが通信に係わる種々情報を入力するために用いる。表示部１９は例えば液晶表示器からなり、通信に係わる種々の情報を表示する。
【００１７】
制御部１１は、この発明に係わる機能として、ＧＰＳ計測部１１１と、ＧＰＳデータ送信制御部１１２を備えている。ＧＰＳ計測部１１１は、例えば５分以上の予め定められた計測周期で上記ＧＰＳ受信機１６を起動し、当該ＧＰＳ受信機１６により受信されたＧＰＳ信号を取り込んで自端末の位置データを生成する。位置データｌi は、計測ＩＤをi とするとき、経度ｘi 、緯度ｙi 、計測時刻ｔi からなる３つの要素で表される。この生成された位置データｌi は記憶部１７に記憶される。
【００１８】
ＧＰＳデータ送信制御部１１２は、サービスサーバＳＶから位置データの送信要求が到来した場合に、上記記憶部１７に記憶された位置データｌi を読み出して要求元のサービスサーバＳＶに向け送信する。なお、位置データｌi は、定期的又は自端末の緯度経度が一定量以上変化したときに、記憶部１７から読み出してサービスサーバＳＶへ送信するようにしてもよい。
【００１９】
サービスサーバＳＶは、例えば通信事業者又はサービス事業者が運用するもので、次のように構成される。図３はその機能構成を示すブロック図である。  
すなわち、サービスサーバＳＶは、送受信ユニット２と、処理ユニット３と、記憶ユニット４とを備えている。送受信ユニット２は、処理ユニット３の制御の下で通信ネットワークＮＷとの間で情報の送受信を行う。
【００２０】
記憶ユニット４は、ＨＤＤ（Hard Disc Drive）又はＳＳＤ（Solid State Drive）を使用したランダムアクセス可能な不揮発性メモリを使用したもので、この発明を実現するために必要な記憶部として、位置データ記憶部４１と、滞在場所データ記憶部４２と、滞在系列データ記憶部４３とを備えている。
【００２１】
位置データ記憶部４１は、後述する位置データ収集処理部３１の制御の下で、上記携帯端末ＭＳ１〜ＭＳｎから収集された位置データ、つまり経度、緯度、計測時刻を、計測ＩＤと関連付けて記憶するために使用される。  
滞在場所データ記憶部４２は、後述する滞在場所抽出処理部３２により位置データから抽出された滞在場所データを記憶するために使用される。  
滞在系列データ記憶部４３は、後述する滞在系列抽出処理部３３により抽出された滞在系列データを記憶するために使用される。
【００２２】
処理ユニット３は、中央処理ユニット（ＣＰＵ；Central Processing Unit）を中核とするもので、この発明を実施するために必要な処理機能として、位置データ収集処理部３１と、滞在場所抽出処理部３２と、滞在系列抽出処理部３３と、滞在系列出力処理部３４とを備えている。これらの処理機能はいずれもアプリケーション・プログラムを上記ＣＰＵに実行させることにより実現される。
【００２３】
位置データ収集処理部３１は、各携帯端末ＭＳ１〜ＭＳｎに対しそれぞれ異なるタイミングで定期的にＧＰＳデータの送信要求を送信し、この要求に対し各携帯端末ＭＳ１〜ＭＳｎが送信するＧＰＳデータを送受信ユニット２により受信して位置データ記憶部４１に記憶させる処理を実行する。
【００２４】
滞在場所抽出処理部３２は、次の処理を実行する。  
(1) 位置データ記憶部４１から、期間グループごとにその位置データを読み込み、この読み込んだ位置データに対しクラスタリング処理を行って、滞在エリアの集合を抽出する処理。  
(2) 上記抽出された滞在エリア集合を対象としてこれらの滞在エリア集合に含まれる各滞在エリア間の距離をそれぞれ計算し、この距離が予め設定した第１のしきい値以下の滞在エリア同士を統合して共通滞在エリアとする処理。  
(3) 上記統合処理により得られた共通滞在エリアに含まれる位置データの各々について、当該位置データが出現する期間グループの数をカウントして、このカウント値が予め設定した第２のしきい値以上となる位置データを含む共通滞在エリアの集合を抽出して、この共通滞在エリアの集合を(1) で抽出された期間グループごとの滞在エリアの集合と共に滞在場所データ記憶部４２に記憶させる処理。
【００２５】
滞在系列抽出処理部３３は、上記位置データ記憶部４１から推定対象の期間グループで計測された位置データを読み込むと共に、上記滞在場所データ記憶部４２から上記共通滞在エリアの集合及び期間グループごとの滞在エリアの集合を読み込む。そして、上記推定対象の期間グループで計測された位置データと、上記共通滞在エリアの集合に含まれる滞在エリアとの間の距離を計算する。続いて、この距離の計算結果に基づいて、当該計算された距離が予め設定した第３のしきい値以下となる滞在エリアを抽出すると共に、この抽出された滞在エリアに含まれる位置データの系列を選択し、これらの情報を上記推定対象の期間グループにおける滞在系列データとして、滞在系列データ記憶部４３に記憶させる処理を実行する。
【００２６】
滞在系列出力処理部３４は、例えば図示しない他のサーバから滞在系列データの取得要求が送られた場合に、上記滞在系列データ記憶部４３から滞在系列データを読み出して送受信ユニット２から要求元のサーバへ送信する処理を実行する。なお、滞在系列出力処理部３４が定期的に、又は滞在系列データが更新されるごとに、当該滞在系列データを自律的に読み出して送信するようにしてもよい。
【００２７】
次に、以上のように構成されたシステムによるユーザの滞在場所推定動作を、サービスサーバＳＶの動作を主体として説明する。  
（１）位置データ計測処理
各ユーザが所持する携帯端末ＭＳ１〜ＭＳｎでは、定常状態において以下のように位置情報の検出及び送信処理が行われる。すなわち、制御部１１は定常状態においてＧＰＳ計測タイミングになったか否かを監視している。この状態で、前回の計測タイミングから例えば５分が経過すると、ＧＰＳ計測部１１１がＧＰＳ受信機１６を起動し、このＧＰＳ受信機１６により受信されたＧＰＳ信号を取り込んで「緯度」及び「経度」を算出する。そして、この算出された「緯度」及び「経度」に「計測時刻」を付与し、この「計測時刻」が付与された「緯度」及び「経度」を位置データとして記憶部１７に格納する。
【００２８】
また制御部１１１は、上記位置データの計測処理を定期的に実行しながら、位置データ送信要求の受信を監視する。この状態で、サービスサーバＳＶから送信要求を受信すると、位置データ送信制御部１１２を起動する。そして、位置データ送信制御部１１２により、上記記憶部１７から前回の送信より後に記憶された位置データを読み出し、この読み出された各位置情報を符号化処理部１３及び無線送受信部１２からサービスサーバＳＶに向け送信させる。以後、送信要求が受信されるごとに、上記記憶部１７に記憶された位置データをサービスサーバＳＶへ送信させる。
【００２９】
（２）位置データの収集処理
サービスサーバＳＶは、位置データ収集処理部３１の制御の下で、各携帯端末ＭＳ１〜ＭＳｎに対しそれぞれ異なるタイミングで定期的に位置データの送信要求を送信する。そして、この要求に対し各携帯端末ＭＳ１〜ＭＳｎから送信される位置データを送受信ユニット２により受信し、位置データ記憶部４１に記憶させる。図４は、位置データ記憶部４１に記憶された位置データの一例を示すものである。
【００３０】
なお、この位置データを記憶させる際に、その後の滞在場所抽出処理のために、記憶された位置データをその計測時刻に基づいて幾つかの期間グループに分割する。例えば、ある時刻Ｔ0 に対して、Ｔ0 ≦ｔi ≦Ｔ0 ＋τであるようなｌi の集合をひとつの期間グループ、Ｔ0 ＋τ≦ｔi ≦Ｔ0 ＋２τであるようなｌi の集合を別の期間グループとして期間グループ分けを行う。τは定数値であり、例えばτ＝２４時間とすれば、ひとつの期間グループに含まれる位置データの集合がユーザの１日の行動に対応する。作成された期間グループを、それぞれＬ1 ，Ｌ2， …，ＬN とする。Nは期間グループの総数である。
【００３１】
（３）滞在場所の抽出処理
（３−１）クラスタリング処理
滞在場所抽出処理部３２は、位置データ記憶部４１に複数日数分の位置データが記憶されると、当該位置データ記憶部４１から位置データを上記期間グループＬ1 ，Ｌ2， …，ＬN ごとに読み込む。そして、この読み込んだ各期間グループＬ1 ，Ｌ2， …，ＬNの位置データに対しクラスタリング処理を実行してユーザが滞在した場所を抽出する。
【００３２】
図６は、この滞在場所抽出処理の手順と処理内容を示すフローチャートである。  
滞在場所抽出処理部３２は、先ずステップＳ１１によりカウンタｉに“１”をセットし、ステップＳ１２により期間グループＬi つまり期間グループＬ1 を選択する。そして、この期間グループＬ1 に含まれる位置データを位置データ記憶部４１から読み込み、クラスタリング処理を実行する。
【００３３】
クラスタリング処理には、例えば位置データの密度に基づいてクラスタリングを行うＤＢＳＣＡＮアルゴリズムを適用する。このＤＢＳＣＡＮアルゴリズムを適用したクラスタリング処理の手順と内容については、J.S. M. Ester, H.P. Kriegel and X. Xu, A density-based algorithm for discovering clusters in large spatial databases with noise, In Proc. of KDD, pp. 226 - 231, 1996.に詳しく記載されている。
【００３４】
上記クラスタリング処理によって得られたクラスタの集合をＣi ＝｛ｃ1 ，ｃ2 ，…，ｃ|Ｃi|｝とする。ここでｃi はひとつのクラスタに対応し、|Ｃi|は期間グループＬi から抽出されたクラスタの総数である。得られた各クラスタｃi が、ユーザがＬi の期間中に滞在した場所を表す。図９にクラスタリングによる滞在場所抽出処理の概念図を示す。位置データに対してクラスタリング処理を実行することで、クラスタｃ1 ，ｃ2 ，ｃ3 ，ｃ4が抽出された様子を示している。
【００３５】
上記クラスタリング処理により得られたデータは、例えば以下のように滞在場所データ記憶部４２に記憶される。図５はその記憶結果の一例を示すものである。すなわち、位置データを表す計測ＩＤと、期間グループＩＤ及び滞在場所ＩＤとが相互に関連付けられて記憶される。期間グループＩＤはどのＬi に位置データが含まれているかを表し、滞在場所ＩＤは位置データがどのクラスタに含まれているかを表す。なお、どのクラスタにも含まれない位置データも存在し、そのような位置データは滞在場所ＩＤを持たない。
【００３６】
滞在場所抽出処理部３２は、上記期間グループＬ1 のクラスタ集合Ｃ1 の抽出処理が終了すると、続いてステップＳ１４でカウンタｉをインクリメントし、ステップＳ１５ですべてのＬi に対する処理が終了したか否かを判定する。この判定の結果、まだ処理していないＬi があればステップＳ１２に戻って次の期間グループＬi を選択し、この選択された期間グループＬi に含まれる位置データに対しステップＳ１３においてクラスタリング処理を実行する。以後、同様に未選択のすべての期間グループＬi に対し、順次クラスタリング処理を実行する。  
かくして、各期間グループＬi に対応するクラスタ集合Ｃ1 ，Ｃ2 ，…，ＣNが滞在場所データ記憶部４２に記憶される。
【００３７】
（３−２）共通滞在場所の抽出処理
各期間グループＬi に対応するクラスタ集合Ｃ1 ，Ｃ2 ，…，ＣNが得られると、滞在場所抽出処理部３２は次にステップＳ１６に移行する。そして、上記クラスタ集合Ｃ1 ，Ｃ2 ，…，ＣN に共通で含まれている滞在場所を抽出する処理を、以下のように実行する。図７はその処理手順と処理内容を示すフローチャートである。
【００３８】
すなわち、滞在場所抽出処理部３２は先ずステップＳ２１において、上記滞在場所データ記憶部４２からクラスタ集合Ｃ1 ，Ｃ2 ，…，ＣN を読み込み、ステップＳ２２においてこれらのクラスタ集合Ｃ1 ，Ｃ2 ，…，ＣN の和集合としてのすべてのクラスタを含む集合Ｃを得る。次にステップＳ２３において上記和集合Ｃからｃ≠ｃ’である２つのクラスタｃ，ｃ’∈Ｃを取り出し、ステップＳ２４においてこの取り出したクラスタ間の緯度及び経度の距離を算出する。クラスタｃ，ｃ’間の距離の定義方法としては、例えばクラスタｃ，ｃ’の重心間の距離を利用する方法や、クラスタｃ，ｃ’内の位置データのうち最も近いものどうしの距離を利用する方法などが考えられる。
【００３９】
次に滞在場所抽出処理部３２は、ステップＳ２４において、上記算出されたクラスタｃ，ｃ’間の距離を予め設定したしきい値と比較する。この比較の結果、クラスタｃ，ｃ’間の距離がしきい値以下の場合は、クラスタｃとｃ’とは同じ滞在場所を表していると判断してステップＳ２５に移行し、このクラスタｃとｃ’とを統合する。そして、この統合処理後のクラスタを滞在場所データ記憶部４２に一時保存する。これに対しクラスタｃ，ｃ’間の距離がしきい値を超えている場合には、クラスタｃ，ｃ’の統合を行わずにステップＳ２６に移行する。
【００４０】
滞在場所抽出処理部３２は、ステップＳ２６において、上記クラスタの和集合Ｃの中に存在するすべてのクラスタについて、まだ上記ステップＳ２４，Ｓ２５の処理が行われていない組み合わせが存在するか否かを判定する。そして、未処理の組み合わせが存在する場合には、ステップＳ２３に戻って当該未選択のクラスタの組み合わせを１つ選択し、この選択したクラスタの組み合わせについて上記ステップＳ２４，Ｓ２５によるクラスタの統合処理を行う。以後同様に、和集合Ｃの中に存在するすべてのクラスタの組み合わせについて上記ステップＳ２４，Ｓ２５によるクラスタの統合処理を繰り返し実行し、すべての組み合わせに対する統合処理が終了すると、ステップＳ２７に移行する。
【００４１】
滞在場所抽出処理部３２は、ステップＳ２７において、上記クラスタの統合処理の結果を用いて日数のカウント処理を以下のように行う。図８はその処理手順と処理内容を示すフローチャートである。
【００４２】
滞在場所抽出処理部３２は、先ずステップＳ３１において、上記クラスタ間の統合処理が終了したクラスタ集合Ｃを滞在場所データ記憶部４２から読み込む。次に、ステップＳ３２で、出力対象のクラスタ集合Ｃ’を初期化（＝空集合）したのち、ステップＳ３３においてｃ∈Ｃをひとつ取り出す。そして、ステップＳ３４において、上記取り出されたクラスタｃに含まれる各位置データについてどの期間グループＬi に含まれるかを調べ、ｃに含まれる位置データが何種類の期間グループに含まれるかをカウントする。例えば、ｎ種類の期間グループに含まれるならば、その滞在場所はｎ種類の時間区間で出現したことを意味する。例えば、いまτ＝２４時間であるならば、その滞在場所はｎ日分の位置データにおいて出現したことに相当する。
【００４３】
滞在場所抽出処理部３２は、続いてステップＳ３５において、上記ステップＳ３４において得られた期間グループ数のカウント値、つまり日数をしきい値と比較する。この比較の結果、期間グループ数のカウント値（日数）がしきい値以上であれば、ステップＳ３６に移行して、上記ステップＳ３４で取り出されたクラスタｃを出力対象のクラスタ集合Ｃ’に追加する。これに対し、上記期間グループ数のカウント値（日数）がしきい値以下であれば、ステップＳ３６の処理を行わずにステップＳ３７に移行する。
【００４４】
滞在場所抽出処理部３２は、ステップＳ３７において、ｃ∈Ｃであるすべてのクラスタｃに対し上記ステップＳ３３〜Ｓ３６による処理が終了したか否かを判定する。この判定の結果、まだ処理していないクラスタｃが残っていれば、ステップＳ３３に戻って未選択のクラスタｃをひとつ選択し、この選択したクラスタｃに対し上記ステップＳ３４〜Ｓ３６による処理を実行する。以後、未処理のクラスタをひとつ選択するごとに、上記ステップＳ３４〜Ｓ３６による処理を実行する。
【００４５】
そうして、すべてのクラスタｃに対する処理が終了すると、滞在場所抽出処理部３２はステップＳ３８（図７のステップＳ２８）において、出力対象のクラスタ集合Ｃ’を滞在場所データ記憶部４２に記憶させる。滞在場所抽出処理部３２は、最後にステップＳ１７に移行して、上記すべての出力対象のクラスタ集合Ｃ’に加えて滞在場所集合Ｃ1 ，Ｃ2 ，…，ＣN を滞在場所データ記憶部４２に記憶させ、処理を終了する。
【００４６】
図１０は、以上述べた共通滞在場所抽出処理を概念的に示したものである。同図（ａ）〜（ｃ）はそれぞれ異なる期間グループＬ1 ，Ｌ2 ，Ｌ3 のクラスタ集合を表し、点線はユーザが移動した軌跡を表している。  
ユーザが移動しているときに、ユーザが携行している端末に搭載されたＧＰＳ計測部１１１を用いてユーザの位置が計測され、この計測された位置データをもとにサービスサーバＳＶの滞在場所抽出処理部３２において滞在場所抽出処理が行われ、これによりユーザの滞在場所としてＰ０１〜Ｐ０８が抽出されたとする。この場合、図７に示すクラスタの統合処理により、Ｐ０１、Ｐ０４及びＰ０７が同一のクラスタとして統合され、かつＰ０２、Ｐ０５、Ｐ０３及びＰ０６も同様に同一のクラスタとして統合される。そして、図８に示す日数カウント処理により、Ｐ０１とＰ０４とＰ０７とを統合したクラスタの期間グループ数が“３”、かつＰ０２とＰ０５とを統合したクラスタ及びＰ０３とＰ０６とを統合したクラスタの期間グループ数が“２”とそれぞれカウントされる。また、ステップＳ８のステップＳ３５において用いられるしきい値を“２”に設定すると、上記統合されたクラスタがＣ’に含まれ、最終的に図１０（ｄ）に示すようにＰ０９、Ｐ１０、Ｐ１１が得られる。
【００４７】
（４）滞在系列の抽出処理
上記滞在場所抽出処理部３２による滞在場所の抽出処理が終了すると、続いて滞在系列抽出処理部３３が以下のように滞在系列データの抽出処理を実行する。図１１はその処理手順と処理内容を示すフローチャートである。
【００４８】
滞在系列抽出処理部３３は、先ずステップＳ４１において位置データ記憶部４１からある期間グループＬi に含まれる位置データを読み込む。読み込む位置データは、計測された順にｌi1，ｌi2，…，ｌi|Li|とする。ここで|Li|はＬi に含まれる位置データの総数である。次に、ステップＳ４２においてカウンタｊの値を１にセットしたのち、ステップＳ４３において位置データｌijの座標とクラスタ集合Ｃi ∪Ｃ’に含まれる各クラスタとの間の距離を計算する。距離の定義は幾種類か考えられ、例えば各クラスタの重心の座標間の距離としてもよいし、各クラスタに含まれるすべての計測点を含む最小の矩形領域間の距離としてもよい。
【００４９】
滞在系列抽出処理部３３は、続いてステップＳ４４において、上記計算された距離が予め設定したしきい値以下となるようなクラスタｃが存在するか否かを判定する。この判定の結果、しきい値以下のクラスタｃが存在する場合には、当該ユーザは期間グループＬiにおいてクラスタｃに対応する滞在場所で滞在を開始したと判断し、ステップＳ４５に移行する。
【００５０】
ステップＳ４５において滞在系列抽出処理部３３は、ｊ≦ｋ≦ａを満たすすべてのｋについて、ｌikとクラスタｃとの間の距離がしきい値以下になるような、最大のａを選択する。ｌiaはクラスタｃに対応する滞在場所での滞在が続く期間の終端に相当する。つまり、ユーザがクラスタｃに滞在していたときの最後の位置データである。そして滞在系列抽出処理部３３は、ステップＳ４６により、ｌijからｌiaまでの期間にクラスタｃに相当する滞在場所にユーザが滞在した旨の情報を、滞在系列データとして滞在系列記憶部４３に記憶する。
【００５１】
また滞在系列抽出処理部３３は、上記滞在系列データが終了すると、ステップＳ４７でカウンタｊをａ＋１に更新すると共にステップＳ４８でｊをｊ＋１に更新し、しかるのちステップＳ４９でｊが|Li|を超えていないかどうかを判定する。この判定の結果、ｊが|Li|を超えていなければ、ステップＳ４３に戻って先に述べたステップＳ４３〜ステップＳ４８の処理を実行する。以後、ｊが|Li|を超えるまで、各ｊについて上記ステップＳ４３〜ステップＳ４８の処理を繰り返し実行する。そして、ｊが|Li|を超えると、滞在系列抽出処理を終了する。
【００５２】
図１２は、以上述べた滞在系列の抽出処理を概念的に示した図である。例えば、いま期間グループＬi において、「開始」と書かれた矢印から「終了」と書かれた矢印に向けてユーザが移動したとする。この移動中に計測された位置データを図１１に示した滞在系列抽出処理のフローチャートに沿って処理すると、順にｃ1 、ｃ2 、ｃ4 の近傍を通過しているため、同図の下部に示すような滞在系列（Ｅ０１、Ｅ０２、Ｅ０３）が得られる。この滞在系列（Ｅ０１、Ｅ０２、Ｅ０３）は滞在系列記憶部４３に記憶される。
【００５３】
この状態で、例えば他の行動予測機能を持ったサーバから滞在系列データの取得要求が到来すると、滞在系列出力処理部３４が上記滞在系列記憶部４３からすべての滞在系列データを読み出し、この読み出された滞在系列データを送受信ユニット２から要求元のサーバに向け送信する。  
上記滞在系列データを受信したサーバは、この受信した滞在系列データを利用することによって、例えば非特許文献１又は２に記載されたマルコフモデルや系列パターンを用いた行動予測処理が可能になる。
【００５４】
以上詳述したようにこの実施形態では、滞在場所抽出処理部３２により先ず期間グループＬi ごとにその位置データに対しクラスタリングを行って滞在エリアの集合Ｃ1 ，Ｃ2 ，…，ＣN を抽出し、この抽出された滞在エリア集合Ｃ1 ，Ｃ2 ，…，ＣNを対象としてこれらの滞在エリア集合Ｃ1 ，Ｃ2 ，…，ＣNに含まれる各滞在エリア間の距離をそれぞれ計算し、この距離が予め設定した第１のしきい値以下の滞在エリア同士を統合して共通滞在エリアとする。次に、上記統合処理により得られた共通滞在エリアに含まれる位置データの各々について、当該位置データが出現する期間グループの数をカウントして、このカウント値が予め設定した第２のしきい値以上となる位置データを含む共通滞在エリアの集合を抽出する。そして、滞在系列抽出処理部３３により、推定対象の期間グループで計測された位置データと、上記抽出された共通滞在エリアの集合に含まれる滞在エリアとの間の距離を計算し、この距離の計算結果に基づいて当該計算された距離が予め設定した第３のしきい値以下となる滞在エリアを抽出すると共にこの抽出された滞在エリアに含まれる位置データの系列を選択し、これらの情報を上記推定対象の期間グループにおける滞在系列を表す情報として出力するようにしている。
【００５５】
したがって、過去の複数の期間グループにおいて計測された位置データからユーザが毎日定常的に滞在する共通滞在エリアが抽出され、この抽出された共通滞在エリアの情報に基づいて、推定対象とする期間グループにおけるユーザの滞在場所を推定することが可能となる。このため、例えば携帯端末の性能的な限界等の影響により、ユーザの位置計測に失敗したりまた計測を行う時間間隔が長くなり、その結果位置データの計測密度が疎になったとしても、推定対象とする期間にユーザがどの場所に滞在したかを高い確率で推定することが可能となる。
【００５６】
なお、この発明は上記実施形態に限定されるものではない。例えば、前記実施形態ではサービスサーバが滞在系列を生成する処理を行い、この処理により得られた滞在系列データを他のサーバ装置に送信し、このサーバ装置で上記滞在系列データをもとにユーザの行動予測を行うようにした。しかし、サービスサーバにおいて上記滞在系列データの生成処理から行動予測処理までを一括して行うようにしてもよい。  
その他、滞在場所推定装置の構成、その処理手順と処理内容等についても、この発明の要旨を逸脱しない範囲で種々変形して実施可能である。
【００５７】
要するにこの発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【符号の説明】
【００５８】
ＭＳ１〜ＭＳｎ…携帯端末、ＳＶ…サービスサーバ、ＮＷ…通信ネットワーク、２…サービスサーバの送受信ユニット、３…処理ユニット、４…記憶ユニット、１１…携帯端末の制御部、１２…無線送受信部、１３…符号化処理部、１４…スピーカ、１５…マイクロホン、１６…ＧＰＳ受信機、１７…携帯端末の記憶部、１８…入力部、１９…表示部、３１…位置データ収集処理部、３２…滞在場所抽出処理部、３３…滞在系列抽出処理部、３４…滞在系列出力処理部、４１…位置データ記憶部、４２…滞在場所データ記憶部、４３…滞在系列記憶部、１１１…ＧＰＳ計測部、１１２…ＧＰＳデータ送信制御部。
【図１】
0005422436.tif 000002
【図２】
0005422436.tif 000003
【図３】
0005422436.tif 000004
【図４】
0005422436.tif 000005
【図５】
0005422436.tif 000006
【図６】
0005422436.tif 000007
【図７】
0005422436.tif 000008
【図８】
0005422436.tif 000009
【図９】
0005422436.tif 000010
【図１０】
0005422436.tif 000011
【図１１】
0005422436.tif 000012
【図１２】
0005422436.tif 000013