(57)【要約】【課題】時空間のクラスタリング処理を高精度にかつ高速度に行えるようにする。【解決手段】Mean-Shiftクラスタリングを用いて位置情報系列から滞在地点を抽出する際に、位置情報系列中からエラーと見なせるデータポイントを削除した後、滞在地点抽出部１２において、当該位置情報系列の各データポイントをそれぞれクラスタとして、当該クラスタごとにその空間的カーネル幅内に含まれるクラスタの発見処理をクラスタ間の時間差によらず時系列に従い順次行い、カーネル幅内に含まれないクラスタが発見された時点で以降の発見処理を打ち切るようにしたものである。【選択図】図３
2015158799.tif 000002
【特許請求の範囲】
【請求項１】
複数のクラスタが時系列に配置された情報系列を記憶する手段と、
前記記憶された情報系列の各クラスタについて、当該注目クラスタの予め設定した空間的カーネル幅内に含まれる他のクラスタを発見する処理を、当該カーネル幅内に含まれない他のクラスタが発見されるまで前記時系列に従い順次行うことにより、クラスタ間の空間的な距離が予め設定した距離以内でかつ時間的に連続するクラスタ群を発見するクラスタ発見処理手段と、
前記発見されたクラスタ群に対しMean-Shiftクラスタリングを用いて中心位置及び時間をミーンシフトする手段と、
前記ミーンシフト処理後のクラスタ群のうち同一の中心位置を持つ複数のクラスタを結合する手段と
を具備することを特徴とする時空間クラスタリング処理装置。
【請求項２】
前記クラスタ発見処理手段は、
空間的な距離の許容量を表す第１のパラメータを設定し、前記注目クラスタのカーネル幅内に含まれない他のクラスタが発見され、かつ当該クラスタより時間上の配列位置が前記注目クラスタから遠い他のクラスタが再発見された場合に、当該再発見されたクラスタの時間上の配列位置が前記第１のパラメータの範囲内であるか否かを判定し、第１のパラメータの範囲内である場合に前記再発見されたクラスタを前記注目クラスタのカーネル幅内に含める手段を、さらに備えることを特徴とする請求項１記載の時空間クラスタリング処理装置。
【請求項３】
前記クラスタ発見処理手段は、
時間的な長さの許容量を表す第２のパラメータを設定し、前記注目クラスタのカーネル幅内に含まれない他のクラスタが発見され、かつ当該クラスタより時間上の配列位置が前記注目クラスタから遠い他のクラスタが再発見された場合に、当該再発見されたクラスタの前記注目クラスタからの時間長が前記第２のパラメータの範囲内であるか否かを判定し、第２のパラメータの範囲内である場合に、前記再発見されたクラスタを前記注目クラスタのカーネル幅内に含める手段を、さらに備えることを特徴とする請求項１又は２記載の時空間クラスタリング処理装置。
【請求項４】
コンピュータ及び記憶部を備える時空間クラスタリング装置が実行する時空間クラスタリング方法であって、
複数のクラスタが時系列に配置された情報系列を記憶部に記憶する過程と、
前記記憶された情報系列の各クラスタについて、当該注目クラスタの予め設定した空間的カーネル幅内に含まれる他のクラスタを発見する処理を、当該カーネル幅内に含まれない他のクラスタが発見されるまで前記時系列に従い順次行うことにより、クラスタ間の空間的な距離が予め設定した距離以内でかつ時間的に連続するクラスタ群を発見するクラスタ発見処理過程と、
前記発見されたクラスタ群に対しMean-Shiftクラスタリングを用いて中心位置及び時間をミーンシフトする過程と、
前記ミーンシフト処理後のクラスタ群のうち同一の中心位置を持つ複数のクラスタを結合する過程と
を具備することを特徴とする時空間クラスタリング処理方法。
【請求項５】
前記クラスタ発見処理過程は、
空間的な距離の許容量を表す第１のパラメータを設定し、前記注目クラスタのカーネル幅内に含まれない他のクラスタが発見され、かつ当該クラスタより時間上の配列位置が前記注目クラスタから遠い他のクラスタが再発見された場合に、当該再発見されたクラスタの時間上の配列位置が前記第１のパラメータの範囲内であるか否かを判定し、第１のパラメータの範囲内である場合に前記再発見されたクラスタを前記注目クラスタのカーネル幅内に含める過程を、さらに備えることを特徴とする請求項４記載の時空間クラスタリング処理方法。
【請求項６】
前記クラスタ発見処理過程は、
時間的な長さの許容量を表す第２のパラメータを設定し、前記注目クラスタのカーネル幅内に含まれない他のクラスタが発見され、かつ当該クラスタより時間上の配列位置が前記注目クラスタから遠い他のクラスタが再発見された場合に、当該再発見されたクラスタの前記注目クラスタからの時間長が前記第２のパラメータの範囲内であるか否かを判定し、第２のパラメータの範囲内である場合に、前記再発見されたクラスタを前記注目クラスタのカーネル幅内に含める過程を、さらに備えることを特徴とする請求項４又は５記載の時空間クラスタリング処理方法。
【請求項７】
請求項１乃至３の何れかに記載の時空間クラスタリング処理装置が備える各手段における処理を、前記時空間クラスタリング処理装置が備えるコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば位置情報系列から滞在地点を抽出するために、時空間Mean-shiftクラスタリングを用いてクラスタを抽出し結合する時空間クラスタリング処理装置、方法及びプログラムに関する。
【背景技術】
【０００２】
近年注目されている、よりユーザに合わせたレコメンドや行動支援技術を実現するためには、ユーザの興味・嗜好や行動履歴等の分析が重要であり、この行動履歴及び興味・嗜好を分析するにはユーザの滞在地を取得することが重要であると考えられている。
【０００３】
滞在地を抽出する方法として、ＧＰＳや移動通信システムを利用してユーザの位置情報系列を取得し、この取得した位置情報系列からユーザが滞在した地点を抽出する方法が提案されている。位置情報系列から滞在地点を抽出するには、位置情報系列に含まれる緯度経度だけでなく時間軸についてもマッピングし、時空間上でMean-shiftクラスタリングを行なう手法がある（例えば非特許文献１を参照）。
【０００４】
また、時間的な連続性のみを考慮して逐次的に処理を行う方法も提案されている（例えば非特許文献２を参照）。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】西田京介、戸田浩之、倉島健、内山匡、“確率的訪問ＰＯＩ分析：時空間行動軌跡からのユーザモデリング”、マルチメディア、分散、協調とモバイルシンポジウム(DICOMO2013)、 2013年7月。
【非特許文献２】Kang, Jong Hee, et al. "Extracting places from traces of locations." Proceedings of the 2nd ACM international workshop on Wireless mobile applications and services on WLAN hotspots. ACM, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ところが、非特許文献１に記載された方法では、測位点の数が増えるにつれて処理時間が増えてしまう。また、クラスタ間の時空間的な距離を用いてクラスタに所属するかどうかを判定しているために、室内に入るなど位置情報データが長時間欠落しているときの滞在地抽出精度が非常に低いという問題がある。
【０００７】
また、非特許文献２に記載された方法では、時系列のみを考慮して時間的に前のクラスタから滞在地判定が行われる。このため、高速度に逐次的に滞在地判定を行うことができるが、抽出した滞在地の位置の誤差が非常に大きくなるという問題がある。
【０００８】
この発明は上記事情に着目してなされたもので、その目的とするところは、時空間のクラスタリング処理を高精度にかつ高速度に行えるようにした時空間クラスタリング処理装置、方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００９】
上記目的を達成するためにこの発明の第１の観点は、複数のクラスタが時系列に配置された情報系列を記憶する手段と、クラスタ発見処理手段と、ミーンシフト手段と、クラスタ結合手段とを備える。そして、クラスタ発見処理手段により、上記記憶された情報系列の各クラスタについて、当該注目クラスタの予め設定した空間的カーネル幅内に含まれる他のクラスタを発見する処理を、当該カーネル幅内に含まれない他のクラスタが発見されるまで上記時系列に従い順次行うことにより、クラスタ間の空間的な距離が予め設定した距離以内でかつ時間的に連続するクラスタ群を発見する。そして、上記発見されたクラスタ群に対しMean-Shiftクラスタリングを用いて中心位置及び時間をミーンシフトし、このミーンシフト処理後のクラスタ群のうち同一の中心位置を持つ複数のクラスタを結合するようにしたものである。
【００１０】
この発明の第２の観点は、上記クラスタ発見処理手段において、空間的な距離の許容量を表す第１のパラメータを設定し、上記注目クラスタのカーネル幅内に含まれない他のクラスタが発見され、かつ当該クラスタより時間上の配列位置が上記注目クラスタから遠い他のクラスタが再発見された場合に、当該再発見されたクラスタの時間上の配列位置が上記第１のパラメータの範囲内であるか否かを判定し、第１のパラメータの範囲内である場合に上記再発見されたクラスタを上記注目クラスタのカーネル幅内に含める処理を、さらに行うようにしたものである。
【００１１】
この発明の第３の観点は、上記クラスタ発見処理手段において、時間的な長さの許容量を表す第２のパラメータを設定し、上記注目クラスタのカーネル幅内に含まれない他のクラスタが発見され、かつ当該クラスタより時間上の配列位置が上記注目クラスタから遠い他のクラスタが再発見された場合に、当該再発見されたクラスタの上記注目クラスタからの時間長が上記第２のパラメータの範囲内であるか否かを判定し、第２のパラメータの範囲内である場合に、上記再発見されたクラスタを上記注目クラスタのカーネル幅内に含めるようにしたものである。
【発明の効果】
【００１２】
この発明の第１の観点によれば、カーネル幅内に含まれないクラスタの発見に応じて以降の発見処理が打ち切られることになるため、カーネル幅内に含まれるクラスタの発見処理に要する計算量を低減することができ、これにより滞在地の抽出処理に要する時間を短縮することが可能となる。また、各クラスタが空間的カーネル幅内に含まれるか否かの判定処理が、クラスタ間の時間差によらず時系列に従い順次行われるので、一定の時間間隔で情報を取得できなかった場合でも、クラスタの抽出を精度良く行うことができる。
【００１３】
この発明の第２の観点によれば、クラスタの時間的な不連続性が空間的な第１のパラメータの範囲内で許容されることになる。このため、例えば各クラスタの位置情報の誤差の影響を軽減して、安定性の高い滞在地点の抽出処理を行うことが可能となる。
【００１４】
この発明の第３の観点によれば、クラスタ間の時間的な不連続性が、時間内な第２のパラメータを考慮した許容条件の範囲内であれば許容される。このため、例えば各クラスタの位置情報の誤差と計測時刻の誤差の影響を軽減して、より一層安定性の高い滞在地点の抽出処理を行うことが可能となる。
【００１５】
すなわちこの発明の各観点によれば、時空間のクラスタリング処理を高精度にかつ高速度に行えるようにした時空間クラスタリング処理装置、方法及びプログラムを提供することができる。
【図面の簡単な説明】
【００１６】
【図１】この発明の一実施形態に係る時空間クラスタリング処理装置を備えた滞在地点抽出装置の機能構成を示すブロック図。
【図２】この発明の一実施形態に係る時空間クラスタリング処理装置を備えた滞在地点抽出装置による滞在地点抽出処理の手順と処理内容を示すフローチャート。
【図３】図２に示した滞在地点抽出処理におけるカーネル内クラスタ発見処理の第１の実施例を示すフローチャート。
【図４】図３に示した滞在地点抽出処理におけるカーネル内クラスタ発見処理の第２の実施例を示すフローチャート。
【図５】図３に示した滞在地点抽出処理におけるカーネル内クラスタ発見処理の第３の実施例を示すフローチャート。
【図６】この発明の一実施形態における滞在地点抽出方法と既存方法との相違を説明するための図。
【図７】この発明の一実施形態における滞在地点抽出方法と既存方法との効果の違いを説明するための図。
【発明を実施するための形態】
【００１７】
以下、図面を参照してこの発明に係わる実施形態を説明する。  
［一実施形態］
（構成）
図１は、この発明の一実施形態に係る時空間クラスタリング処理装置を備えた滞在地点抽出装置の機能構成を示すブロック図である。この滞在地点抽出装置は例えばサーバコンピュータ又はパーソナルコンピュータからなり、ＣＰＵ（Central Processing Unit）を備えた制御ユニットと、記憶ユニットを少なくとも備えている。
【００１８】
記憶ユニットは、ＧＰＳ系列記憶部２１と、地点名データベース（地点名ＤＢ）２２と、滞在地点名系列記憶部２３を備えている。ＧＰＳ系列記憶部２１は、例えばユーザの携帯端末（図示せず）においてＧＰＳ測位部により計測された位置情報系列が当該携帯端末から送られたとき、当該位置情報系列を格納するために用いられる。地点名データベース（地点名ＤＢ）２２には、サービス対象エリアの緯度経度情報に関連付けてその地点名を表す情報が予め記憶されている。なお、地点名を表す情報には、建物名や施設名、店舗名等も含まれる。滞在地点名系列記憶部２３は、後述する制御ユニット１により抽出された滞在地点名を表す情報を保存するために用いられる。
【００１９】
制御ユニット１は、精度向上部１１と、滞在地点抽出部１２と、地点名参照部１３を有する。なお、これらの処理部は何れも記憶ユニット内のプログラムメモリに格納されたプログラムを上記ＣＰＵに実行させることにより実現される。
【００２０】
精度向上部１１は、位置情報系列中の各データポイントのうち明らかにエラーと見なすことができるデータポイントを削除する処理を行う。エラーと見なすことができるデータポイントとしては、例えば移動速度を計算すると2000 km/h以上となってしまうようなデータポイント、つまり実際にその速度で移動していることが現実的でないようなデータポイントが挙げられる。
【００２１】
滞在地点抽出部１２は、以下の処理を実行する。
(1) 上記精度向上部１１からエラーを削除した後の位置情報系列を受け取り、当該位置情報系列の各データポイントをそれぞれクラスタとする。そして、当該各クラスタについてその空間的カーネル幅内に含まれかつ時間的に連続するクラスタを抽出する処理。  
(2) 上記抽出された各クラスタに対しMean-Shiftクラスタリングを用いて中心位置及び時間をミーンシフトする処理。  
(3) 上記ミーンシフト処理後のクラスタのうち同一の中心位置を持つクラスタを結合する処理。  
(4) 上記結合処理後のクラスタのうち最低滞在時間以下のクラスタを削除する処理。
【００２２】
地点名参照部１３は、上記滞在地点抽出部１２により得られたクラスタの緯度経度情報をもとに地点名ＤＢ２２をアクセスし、当該地点名ＤＢ２２から対応する地点名を表す情報を読み出す。そして、この読み出された地点名を表す情報を滞在地点名系列記憶部２３に格納する処理を実行する。
【００２３】
（動作）
次に、以上のように構成された装置の滞在地点抽出処理動作を説明する。なお、ＧＰＳ系列記憶部２１には、図示しないユーザの携帯端末等から取得された位置情報系列が既に記憶されているものとして説明を行う。図１にその一例をＧＰＳ系列として例示している。
【００２４】
制御ユニット１は、先ず上記ＧＰＳ系列記憶部２１から読み出した位置情報系列を精度向上部１１に入力し、当該位置情報系列の各データポイントについて、明らかにエラーと見なせるデータポイントを抽出して削除する。この処理は、例えば１つ前のデータポイントとの間で計測位置とその時刻をもとに移動速度を算出し、この算出した移動速度をしきい値と比較することにより行う。この結果、例えば図１に示したＧＰＳ系列の中で、「2013-12-03 00:00:34,11.76,149.52」がエラーデータとして削除される。
【００２５】
次に制御ユニット１は、滞在地点抽出部１２により以下のように滞在地点の抽出処理を実行する。図２はその処理手順と処理内容を示すフローチャートである。  
すなわち、先ずステップＳ１１において、上記精度向上部１１によりエラーが削除された位置情報系列の各データポイントをそれぞれクラスタとして初期化し、ステップＳ１２でMean Shiftクラスタリングによるミーンシフトが収束したと判定されるまで、ステップＳ１３〜Ｓ１５による処理を繰り返し実行する。
【００２６】
このうち先ずステップＳ１３では、上記各クラスタについて時空間カーネル内のクラスタを発見する処理が行われる。この時空間カーネル内クラスタの発見処理手法には以下の３つの実施例が考えられる。
【００２７】
（１）第１の実施例
第１の実施例は、Mean-shiftクラスタリングを行なう際に、空間的なカーネルを利用し、時間的に連続しているクラスタのみを同一のカーネル内にあると判断して、滞在地点を抽出する手法である。例えば、クラスタcls_iのカーネル幅内に含まれるクラスタを抽出する際に、クラスタcls_iに続くクラスタi+1，i+2，…について順次クラスタcls_iのカーネル幅内に含まれるか否かの判定を行い、この判定の結果クラスタcls_i+2がカーネル幅内に含まれていたとしてもその１つ前のクラスタcls_i+1がカーネル幅内に含まれていない場合は、上記クラスタcls_i+2もカーネル幅内に含まれないとする。また同様に、クラスタcls_iに続くクラスタi-1，i-2，…について順次クラスタcls_iのカーネル幅内に含まれるか否かの判定を行い、クラスタcls_i-2がカーネル幅内に含まれていても、その１つ後のcls_i-1がカーネル幅内に含まれない場合は、上記クラスタcls_i-2もカーネル幅内に含まれないとする。
【００２８】
図３はこの第１の実施例に係るカーネル内クラスタ発見手法の処理手順と処理内容を示すフローチャートである。  
クラスタは時系列に従い計測時刻が早い順に並んでおり、i番目のクラスタをcls_iとし、クラスタの配列を{cls}とする。先ずステップＳ２１ではクラスタcls_iが１つ選択され、この状態でステップＳ２２において上記クラスタcls_iより計測時刻の順番が遅い各クラスタcls_j:｛cls｜i＜j｝が順次i+1，i+2，…のように選択される。そして、ステップＳ２３において、上記選択されたクラスタcls_j（j=i+1，i+2，…）ごとに上記クラスタcls_iとの空間距離が求められ、この空間距離が上記クラスタcls_iのカーネル幅内にあるか否かが判定される。この判定の結果、空間距離が上記クラスタcls_iのカーネル幅内にあると判定されたクラスタcls_j（j=i+1，i+2，…）は、ステップＳ２４において制御ユニット１内のメモリに保存される。
【００２９】
そして、上記判定の過程で、クラスタcls_j（j=i+k1）がクラスタcls_iのカーネル幅内に入っていないと判定されたとする。この場合、順番が上記i+k1以降のクラスタはすべてクラスタcls_iのカーネル幅内に入っていないと見なされ、この時点で上記時間軸における順番の進み方向のカーネル内クラスタの発見処理は終了し、ステップＳ２６に移行する。
【００３０】
ステップＳ２６では、上記クラスタcls_iより計測時刻の順番が早い各クラスタcls_j:｛cls｜i>j｝が順次i-1，i-2，…のように選択される。そして、ステップＳ２７において、上記選択されたクラスタcls_j（j= i-1，i-2，…）ごとに上記クラスタcls_iとの空間距離が求められ、この空間距離が上記クラスタcls_iのカーネル幅内にあるか否かが判定される。この判定の結果、空間距離が上記クラスタcls_iのカーネル幅内にあると判定されたクラスタcls_j（j= i-1，i-2，…）は、ステップＳ２８において制御ユニット１内のメモリに保存される。
【００３１】
そして、上記判定の過程で、クラスタcls_j（j=i-k2）がクラスタcls_iのカーネル幅内に入っていないと判定されたとする。この場合、順番が上記i-k2以降のクラスタはすべてクラスタcls_iのカーネル幅内に入っていないと見なされ、この時点で上記時間軸における順番の戻り方向のカーネル内クラスタの発見処理は終了する。
【００３２】
上記クラスタcls_iについてのカーネル内クラスタの発見処理が終了すると、ステップＳ３０からステップＳ２１に戻って次のクラスタcls_i+1が選択され、今度はこのクラスタcls_i+1と他のクラスタcls_jとの間の空間距離に基づくカーネル内クラスタの発見処理が上記ステップＳ２２〜Ｓ２９において行われる。以後同様に、順次次のクラスタcls_iが選択されるごとに、当該選択されたクラスタcls_iと他のクラスタcls_jとの間の空間距離に基づくカーネル内クラスタの発見処理が繰り返し行われ、すべてのクラスタcls_iについてのカーネル内クラスタの発見処理が終了すると、制御ユニット１はステップＳ１４に移行する。
【００３３】
（２）第２の実施例
第２の実施例は、上記第１の実施例を拡張したもので、時間的な不連続性を、予め設定した空間的なパラメータの範囲内であれば許容する手法である。すなわち、パラメータをnとしたとき、クラスタcls_iの空間的カーネル幅内に他の各クラスタcls_jが含まれるか否かを順次判定していった場合に、あるクラスタ以降でカーネル幅内に含まれなくなっても、当該クラスタより順位がさらにn1個後のクラスタで再びカーネル幅内に入った場合には、n1がパラメータnの範囲内（n1≦n）である場合に限り、n1個後ろクラスタはクラスタcls_iのカーネル幅内に含まれると判定するものである。
【００３４】
図４は、この第２の実施例に係るカーネル内クラスタ発見手法の処理手順と処理内容を示すフローチャートである。なお、同図において図３と同一部分には同一符号を付して説明を行う。
【００３５】
クラスタは時系列に従い計測時刻が早い順に並んでおり、i番目のクラスタをcls_iとし、クラスタの配列を{cls}とする。先ずステップＳ２１ではクラスタcls_iが１つ選択され、この状態でステップＳ２２において上記クラスタcls_iより計測時刻の順番が遅い各クラスタcls_j:｛cls｜i＜j｝が順次i+1，i+2，…のように選択される。そして、ステップＳ２３において、上記選択されたクラスタcls_j（j=i+1，i+2，…）ごとに上記クラスタcls_iとの空間距離が求められ、この空間距離が上記クラスタcls_iのカーネル幅内にあるか否かが判定される。この判定の結果、空間距離が上記クラスタcls_iのカーネル幅内にあると判定されたクラスタcls_j（j=i+1，i+2，…）は、ステップＳ２４において制御ユニット１内のメモリに保存される。
【００３６】
一方、上記判定の過程で、クラスタcls_j（j=i+k1）がクラスタcls_iのカーネル幅内に入っていないと判定されたとする。この場合、k1+1番目以降の各クラスタについてさらに判定を続ける。そして、i+k1+n1番目のクラスタで再びクラスタcls_iのカーネル幅内に入った場合には、当該クラスタの順位i+k1+n1が予め設定したパラメータnの範囲内（n1≦n）であるか否かがステップＳ３１で判定され、パラメータnの範囲内であれば、上記i+k1+n1番目のクラスタはクラスタcls_iのカーネル幅内に含まれると判定され、ステップＳ２４において制御ユニット１内のメモリに保存される。
【００３７】
これに対し、上記クラスタの順位i+k1+n1がパラメータnの範囲内（n1≦n）に入っていなければ、順番が上記i+k1より後のクラスタはすべてクラスタcls_iのカーネル幅内に入っていないと見なされ、この時点で上記時間軸における順番の進み方向のカーネル内クラスタの発見処理は終了し、ステップＳ２６に移行する。
【００３８】
ステップＳ２６では、上記クラスタcls_iより計測時刻の順番が早い各クラスタcls_j:｛cls｜i>j｝が順次i-1，i-2，…のように選択される。そして、ステップＳ２７において、上記選択されたクラスタcls_j（j= i-1，i-2，…）ごとに上記クラスタcls_iとの空間距離が求められ、この空間距離が上記クラスタcls_iのカーネル幅内にあるか否かが判定される。この判定の結果、空間距離が上記クラスタcls_iのカーネル幅内にあると判定されたクラスタcls_j（j= i-1，i-2，…）は、ステップＳ２８において制御ユニット１内のメモリに保存される。
【００３９】
一方、上記判定の過程で、クラスタcls_j（j=i-k2）がクラスタcls_iのカーネル幅内に入っていないと判定されたとする。この場合、k2-1番目以降の各クラスタについてさらに判定を続ける。そして、i-k2-n2番目のクラスタで再びクラスタcls_iのカーネル幅内に入った場合には、当該クラスタの順位i-k2-n2がパラメータnの範囲内（n2≦n）であるか否かがステップＳ３２で判定され、パラメータnの範囲内であれば、上記i-k2-n2番目のクラスタはクラスタcls_iのカーネル幅内に含まれると判定され、ステップＳ２９において制御ユニット１内のメモリに保存される。
【００４０】
これに対し、上記クラスタの順位i-k2-n2がパラメータnの範囲内（n1≦n）に入っていなければ、順番が上記i-k2より前のクラスタはすべてクラスタcls_iのカーネル幅内に入っていないと見なされ、この時点で上記時間軸における順番の戻り方向のカーネル内クラスタの発見処理は終了する。
【００４１】
上記クラスタcls_iについてのカーネル内クラスタの発見処理が終了すると、ステップＳ３０からステップＳ２１に戻って次のクラスタcls_i+1が選択され、今度はこのクラスタcls_i+1と他のクラスタcls_jとの間の空間距離に基づくカーネル内クラスタの発見処理が上記ステップＳ２２〜Ｓ２９（ステップＳ３１、Ｓ３２を含む）において行われる。以後同様に、順次次のクラスタcls_iが選択されるごとに、当該選択されたクラスタcls_iと他のクラスタcls_jとの間の空間距離に基づくカーネル内クラスタの発見処理が繰り返し行われ、すべてのクラスタcls_iについてのカーネル内クラスタの発見処理が終了すると、制御ユニット１は先に述べたステップＳ１４に移行する。
【００４２】
（３）第３の実施例
第３の実施例は、上記第２の実施例をさらに拡張したもので、時間的な不連続性を、第２の実施例で述べた空間的なパラメータの範囲内で、かつ予め設定した時間内なパラメータの範囲内であれば、許容する手法である。すなわち、空間的パラメータn に加え、時間的なパラメータを考慮した許容条件をさらに定義する。そして、クラスタcls_iの空間的カーネル幅内に他の各クラスタcls_jが含まれるか否かを順次判定していった場合に、あるクラスタ以降でカーネル幅内に含まれなくなっても、当該クラスタより順位がさらに後のn1番目のクラスタで再びカーネル幅内に入った場合に、当該クラスタの順位n1がパラメータnの範囲内（n1≦n）であり、かつ上記許容条件を満たす場合に、上記n1番目のクラスタはクラスタcls_iのカーネル幅内に含まれると判定するものである。
【００４３】
図５は、この第３の実施例に係るカーネル内クラスタ発見手法の処理手順と処理内容を示すフローチャートである。なお、同図において図３と同一部分には同一符号を付して説明を行う。
【００４４】
クラスタは時系列に従い計測時刻が早い順に並んでおり、i番目のクラスタをcls_iとし、クラスタの配列を{cls}とする。先ずステップＳ２１ではクラスタcls_iが１つ選択され、この状態でステップＳ２２において上記クラスタcls_iより計測時刻の順番が遅い各クラスタcls_j:｛cls｜i＜j｝が順次i+1，i+2，…のように選択される。そして、ステップＳ２３において、上記選択されたクラスタcls_j（j=i+1，i+2，…）ごとに上記クラスタcls_iとの空間距離が求められ、この空間距離が上記クラスタcls_iのカーネル幅内にあるか否かが判定される。この判定の結果、空間距離が上記クラスタcls_iのカーネル幅内にあると判定されたクラスタcls_j（j=i+1，i+2，…）は、ステップＳ２４において制御ユニット１内のメモリに保存される。
【００４５】
一方、上記判定の過程で、クラスタcls_j（j=i+k1）がクラスタcls_iのカーネル幅内に入っていないと判定されたとする。この場合、k1+1番目以降の各クラスタについてさらに判定を続ける。そして、i+k1+n1番目のクラスタで再びクラスタcls_iのカーネル幅内に入った場合には、ステップＳ４１において、先ず当該クラスタの順位i+k1+n1が予め設定した空間的パラメータn の範囲内（n1≦n）であるか否かが判定される。続いて、予め設定した時間的パラメータt を考慮した下記の許容条件
n1
Σ ｜cls_i+k1+x｜＜t
x=0
を満たしているか否かが判定され、当該許容条件を満たしていれば、上記i+k1+n1番目のクラスタはクラスタcls_iのカーネル幅内に含まれると判定され、ステップＳ２４において制御ユニット１内のメモリに保存される。
【００４６】
これに対し、上記クラスタの順位i+k1+n1がパラメータnの範囲内（n1≦n）に含まれていないか、或いはたとえ含まれていても上記許容条件を満たしていなければ、順番が上記i+k1より後のクラスタはすべてクラスタcls_iのカーネル幅内に入っていないと見なされ、この時点で上記時間軸における順番の進み方向のカーネル内クラスタの発見処理は終了し、ステップＳ２６に移行する。
【００４７】
次にステップＳ２６では、上記クラスタcls_iより計測時刻の順番が早い各クラスタcls_j:｛cls｜i>j｝が順次i-1，i-2，…のように選択される。そして、ステップＳ２７において、上記選択されたクラスタcls_j（j= i-1，i-2，…）ごとに上記クラスタcls_iとの空間距離が求められ、この空間距離が上記クラスタcls_iのカーネル幅内にあるか否かが判定される。この判定の結果、空間距離が上記クラスタcls_iのカーネル幅内にあると判定されたクラスタcls_j（j= i-1，i-2，…）は、ステップＳ２８において制御ユニット１内のメモリに保存される。
【００４８】
一方、上記判定の過程で、クラスタcls_j（j=i-k2）がクラスタcls_iのカーネル幅内に入っていないと判定されたとする。この場合、k2-1番目以降の各クラスタについてさらに判定を続ける。そして、i-k2-n2番目のクラスタで再びクラスタcls_iのカーネル幅内に入った場合には、ステップＳ４１において、先ず当該クラスタの順位i-k2-n2が予め設定した空間的パラメータn の範囲内（n1≦n）であるか否かが判定される。続いて、予め設定した時間的パラメータt を考慮した下記の許容条件
n2
Σ ｜cls_i-k2-x｜＜t
x=0
を満たしているか否かが判定され、当該許容条件を満たしていれば、上記i-k2-n2番目のクラスタはクラスタcls_iのカーネル幅内に含まれると判定され、ステップＳ２４において制御ユニット１内のメモリに保存される。
【００４９】
これに対し、上記クラスタの順位i-k2-n2がパラメータnの範囲内（n2≦n）に含まれていないか、或いはたとえ含まれていても上記許容条件を満たしていなければ、順番が上記i-k2より前のクラスタはすべてクラスタcls_iのカーネル幅内に入っていないと見なされ、この時点で上記時間軸における順番の戻り方向のカーネル内クラスタの発見処理は終了する。
【００５０】
上記クラスタcls_iについてのカーネル内クラスタの発見処理が終了すると、ステップＳ３０からステップＳ２１に戻って次のクラスタcls_i+1が選択され、今度はこのクラスタcls_i+1と他のクラスタcls_jとの間の空間距離に基づくカーネル内クラスタの発見処理が上記ステップＳ２２〜Ｓ２９（ステップＳ３１、Ｓ３２を含む）において行われる。
【００５１】
以後同様に、順次次のクラスタcls_iが選択されるごとに、当該選択されたクラスタcls_iと他のクラスタcls_jとの間の空間距離に基づくカーネル内クラスタの発見処理が繰り返し行われ、すべてのクラスタcls_iについてのカーネル内クラスタの発見処理が終了すると、制御ユニット１は先に述べたステップＳ１４に移行する。
【００５２】
ステップＳ１４に移行すると制御ユニット１の滞在地点抽出部１２では、上記各クラスタについて中心位置及び時間をミーンシフト（加重平均に移動）する処理が行われる。このミーンシフトについては、先に述べた非特許文献１に詳しく記載されている。次にステップＳ１５では、上記ミーンシフト後の各クラスタについて、同一の中心位置を持つクラスタを結合する処理が行われる。
【００５３】
上記ステップＳ１２において、各クラスタに対するミーンシフトが収束したと判定された場合には、ステップＳ１６において、上記結合処理後のクラスタから最低滞在時間を満たさないクラスタを削除する処理が行われる。そして、この削除処理後に残ったクラスタ群が滞在地点系列として地点名参照部１３へ出力される。
【００５４】
地点名参照部１３では、上記滞在地点抽出部１２により得られたクラスタの緯度経度情報をもとに地点名ＤＢ２２がアクセスされる。そして、当該地点名ＤＢ２２から対応する地点名を表す情報が検索される。そして、この検索された地点名を表す情報が滞在地点名系列記憶部２３に格納される。
【００５５】
なお、上記滞在地点名系列記憶部２３に格納された滞在地点名系列情報は、例えばネットワークサービスプロバイダや情報配信事業者等の事業者が使用する事業者端末からの要求に応じて読み出され、要求元の事業者端末へ送信される。この滞在地点名系列情報は、例えばユーザに対するレコメンドサービスや行動支援のために用いられる。
【００５６】
（第１の実施例の効果）
以上詳述したようにこの発明の一実施形態に係る時空間クラスタリング方法の第１の実施例では、Mean-Shiftクラスタリングを用いて位置情報系列から滞在地点を抽出する際に、位置情報系列中からエラーと見なせるデータポイントを削除した後、滞在地点抽出部１２において、当該位置情報系列の各データポイントをそれぞれクラスタとして、当該クラスタごとにその空間的カーネル幅内に含まれるクラスタの発見処理をクラスタ間の時間差によらず時系列に従い順次行い、カーネル幅内に含まれないクラスタが発見された時点で以降の発見処理を打ち切るようにしている。
【００５７】
図６は、第１の実施例によるクラスタ発見処理の結果を既存方法による処理結果と対比した示したもので、（ａ）は既存方法による結果を、（ｂ）は第１の実施例による結果をそれぞれ示している。同図に示したように、既存方法では常にすべてのクラスタについてカーネル幅内に含まれるか否かを判定するようにしているため、（ａ）に示すように一度クラスタ半径外に出ても、一定時間内に半径内に戻ると同一クラスタとして結合されてしまう。
【００５８】
これに対し第１の実施例では、先に述べたようにクラスタの発見処理がクラスタ間の時間差によらず時系列に従い順次行われ、カーネル幅内に含まれないクラスタが発見された時点で以降の発見処理が打ち切られる。このため、（ｂ）に示すようにあるクラスタが一度クラスタ半径外に出ると、それ以後クラスタが上記半径内に入っても当該クラスタは同一の地点を表すものとは見なされない。
【００５９】
したがって第１の実施例によれば、上記カーネル幅内に含まれるクラスタの発見処理に要する計算量を低減することができ、これにより滞在地の抽出処理に要する時間を短縮することが可能となる。
【００６０】
また、各クラスタが空間的カーネル幅内に含まれるか否かの判定処理が、クラスタ間の時間差によらず時系列に従い順次行われるので、一定の時間間隔で位置情報を取得できない屋内等の環境においても、滞在地の抽出を精度良く行うことができる。すなわち、位置情報iと位置情報i+1との間の時間的な距離は非常に大きいが距離的には非常に近いという場合にも、位置情報iと位置情報i+1を同一クラスタに含めることが可能となる。
【００６１】
図７はこの効果を説明するための図で、（ａ）は既存方式によるクラスタの発見結果を、（ｂ）は第１の実施例による発見結果をそれぞれ示している。同図（ａ）に示すように、既存方式ではクラスタ間の時間差が一定値を超えると、これらのクラスタは同一の滞在地を表す情報として抽出されない。これに対し第１の実施例では、（ｂ）に示すようにクラスタ間の時間差が大きくても、これらのクラスタが連続していればこれらのクラスタは同一の滞在地を表す情報として抽出される。したがって、例えばユーザが地下街やオフィスビル内に長時間滞在した場合でも、上記２つのクラスタを同一の滞在地を示すものとして結合して、当該滞在地を確実に抽出することが可能となる。
【００６２】
また、第２の実施例では、クラスタの発見処理の過程において、クラスタcls_iの空間的カーネル幅内に他の各クラスタcls_jが含まれるか否かを順次判定していった場合に、あるクラスタ以降でカーネル幅内に含まれなくなっても、当該クラスタより順位がさらに後のn1番目のクラスタで再びカーネル幅内に入った場合には、当該クラスタの順位n1が予め設定したパラメータnの範囲内（n1≦n）であれば、上記n1番目のクラスタはクラスタcls_iのカーネル幅内に含まれると判定するようにしている。
【００６３】
したがって、クラスタの時間的な不連続性を空間的なパラメータnの範囲内で許容することができる。このため、例えば各クラスタの位置情報の誤差の影響を軽減して、安定性の高い滞在地点の抽出処理を行うことが可能となる。
【００６４】
さらに、第３の実施例では、空間的パラメータn に加え、時間的なパラメータを考慮した許容条件をさらに定義する。そして、クラスタcls_iの空間的カーネル幅内に他の各クラスタcls_jが含まれるか否かを順次判定していった場合に、あるクラスタ以降でカーネル幅内に含まれなくなっても、当該クラスタより順位がさらに後のn1番目のクラスタで再びカーネル幅内に入った場合に、当該クラスタの順位n1がパラメータnの範囲内（n1≦n）であり、かつ時間的なパラメータt を考慮して予め設定した許容条件を満たす場合に、上記n1番目のクラスタはクラスタcls_iのカーネル幅内に含まれると判定するようにしている。
【００６５】
したがって、クラスタ間の時間的な不連続性を、第２の実施例で述べた空間的なパラメータn の範囲内で、かつ時間内なパラメータを考慮した許容条件の範囲内であれば、許容することができる。このため、例えば各クラスタの位置情報の誤差と計測時刻の誤差の影響を軽減して、より一層安定性の高い滞在地点の抽出処理を行うことが可能となる。
【００６６】
［他の実施形態］
前記一実施形態の第３の実施例では、クラスタがカーネル幅内から外れても、当該クラスタが空間的なパラメータn の範囲内で、かつ時間内なパラメータを考慮した許容条件の範囲内であれば、クラスタ間の時間的な不連続を許容するようにした。しかし、空間的なパラメータn を考慮せず、時間的なパラメータのみを許容条件としてクラスタ間の時間的な不連続を許容するようにしてもよい。
【００６７】
また、前記一実施形態では、位置計測手段としてＧＰＳを利用する場合を例示したが、それ以外にセルラ携帯通信システムや無線ＬＡＮ等の移動通信ネットワークシステムの基地局が提供する位置情報や、三軸加速度センサを用いた位置計測手段等を使用してもよい。
【００６８】
さらに、前記一実施形態では、ユーザの携帯端末等で計測した位置情報系列をサーバコンピュータで収集し、このサーバコンピュータにおいて上記位置情報系列から滞在地点を抽出するための時空間クラスタリング処理を実行する場合を例にとって説明した。しかし、それに限らず、ユーザの携帯端末において当該携帯端末により得られた位置情報系列に対しそのまま時空間クラスタリング処理を実行してもよく、またユーザの携帯端末により得られた位置情報系列をユーザの固定端末に転送し、この固定端末において上記転送された位置情報系列に対し時空間クラスタリング処理を実行するようにしてもよい。
【００６９】
さらに、前記一実施形態では位置情報系列から滞在地点を抽出する場合を例に説明した。しかし、それに限らず例えば加速度センサにより検出された監視対象物の動作履歴を表す情報から動作の停滞を抽出したり、カメラにより得られた対象物の監視映像等から無変化の状態を抽出する場合にも、この発明を適用可能である。
【００７０】
また、本発明の装置はコンピュータとプログラムによっても実現でき、プログラムを記録媒体に記録することも、ネットワークを通して提供することも可能である。その他、カーネル内に含まれるクラスタを抽出するための処理手順や処理内容等についても、この発明の要旨を逸脱しない範囲で種々変形して実施可能である。
【００７１】
要するにこの発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態に亘る構成要素を適宜組み合せてもよい。
【符号の説明】
【００７２】
１…制御ユニット、１１…精度向上部、１２…滞在地点抽出部、１３…地点名参照部、２１…ＧＰＳ系列記憶部、２２…地点名ＤＢ、２３…滞在地点名系列記憶部。
【図１】
2015158799.tif 000003
【図２】
2015158799.tif 000004
【図３】
2015158799.tif 000005
【図４】
2015158799.tif 000006
【図５】
2015158799.tif 000007
【図６】
2015158799.tif 000008
【図７】
2015158799.tif 000009