(57)【特許請求の範囲】
【請求項１】
コンピュータにより、
ユーザ端末から収集した位置情報を測位データとして記憶手段に記憶する第１のステップと、
前記記憶手段から各測位データを読み出して、前記各測位データにそれぞれ含まれる測位誤差データを用いて各測位データの測位精度をそれぞれ算出する第２のステップと、
前記各測位データにおける各測位点をそれぞれクラスタとし、それぞれのクラスタから一定領域内かつ測位時刻の間隔が一定時間内に含まれる複数の測位点をそれぞれ取得する第３のステップと、
前記複数の測位点の測位精度および測位データを用いて測位精度を重みとする重み付き重心を算出し、前記それぞれのクラスタの中心点とする第４のステップと、
各クラスタの中心点間の距離が一定距離以下であるクラスタを併合する第５のステップと、
併合されたクラスタに含まれる各クラスタの測位点を測位時刻の順番に並べ、隣り合う２つの測位点の測位時刻の時間間隔が一定時間以上の場合、前記併合されたクラスタを分離する第６のステップと、
併合されたクラスタ及び併合後に分離されたクラスタの中心点をユーザの滞留点として抽出する第７のステップと、
を有することを特徴とする滞留点抽出方法。
【請求項２】
前記第２のステップと前記第３のステップとの間に、測位時刻の間隔が一定時間より大きく、かつ、測位点間が一定距離より小さい測位データ間に新たな測位データを追加するステップを更に有することを特徴とする請求項１に記載の滞留点抽出方法。
【請求項３】
ユーザ端末から収集した位置情報を測位データとして記憶する記憶手段と、
前記記憶手段から各測位データを読み出して、前記各測位データにそれぞれ含まれる測位誤差データを用いて各測位データの測位精度をそれぞれ算出する算出手段と、
前記各測位データにおける各測位点をそれぞれクラスタとし、それぞれのクラスタから一定領域内かつ測位時刻の間隔が一定時間内に含まれる複数の測位点をそれぞれ取得する取得手段と、
前記複数の測位点の測位精度および測位データを用いて測位精度を重みとする重み付き重心を算出し、前記それぞれのクラスタの中心点とする算出手段と、
各クラスタの中心点間の距離が一定距離以下であるクラスタを併合する併合手段と、
併合されたクラスタに含まれる各クラスタの測位点を測位時刻の順番に並べ、隣り合う２つの測位点の測位時刻の時間間隔が一定時間以上の場合、前記併合されたクラスタを分離する分離手段と、
併合されたクラスタ及び併合後に分離されたクラスタの中心点をユーザの滞留点として抽出する抽出手段と、
を有することを特徴とする滞留点抽出装置。
【請求項４】
測位時刻の間隔が一定時間より大きく、かつ、測位点間が一定距離より小さい測位データ間に新たな測位データを追加する補間手段を更に有することを特徴とする請求項３に記載の滞留点抽出装置。
【請求項５】
請求項１又は２に記載の滞留点抽出方法をコンピュータに実行させることを特徴とする滞留点抽出プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ユーザ端末の位置情報を用いてユーザの滞留点を求める技術に関する。
【背景技術】
【０００２】
フィーチャーフォンやスマートフォンなどから、ＧＰＳや無線基地局、Ｗｉ−Ｆｉなどを用いて取得された位置情報を測位データとして収集し、ユーザの地理的行動を分析することが行われている。そして、収集した測位データからユーザがどこへ訪問したかを理解するために、その測位データを用いてユーザが長時間留まった地点を滞留点として抽出する技術が存在する。具体的には、測位データに含まれる測位点、すなわち、測位された時刻における経度・緯度が示す地点が密である場所を滞留点として抽出する、カーネル密度ベースのクラスタリング手法であるＭｅａｎ−Ｓｈｉｆｔ技術（非特許文献１）が用いられている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】Dorin Comaniciu、外１名、“Mean Shift: A Robust Approach Toward Feature Space Analysis”、IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE、Vol.24、No.5、2002年5月、p.603-619
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、滞留点に測位点が集中していることを前提としているため、フィーチャーフォンなどの電池消費削減の観点から移動のない時に測位回数を抑制するなどして測位取得間隔が変化する場合、滞留点付近の測位点の数が減少してしまうという課題がある。また、ＧＰＳなどによる測位は、屋内や屋外、電波状況などの環境要因によって変化する。そのため、全ての測位点を等しく扱う従来技術では、測定誤差の大きい測位点に引き寄せられることにより滞留点がずれてしまうという課題もある。これら２つの課題より、滞留点の抽出精度が低下するおそれがあった。
【０００５】
本発明は、上記事情を鑑みてなされたものであり、ユーザが留まった滞留点の抽出精度を改善することを目的とする。
【課題を解決するための手段】
【０００６】
上記課題を解決するため、請求項１の滞留点抽出方法は、コンピュータにより、ユーザ端末から収集した位置情報を測位データとして記憶手段に記憶する第１のステップと、前記記憶手段から各測位データを読み出して、前記各測位データにそれぞれ含まれる測位誤差データを用いて各測位データの測位精度をそれぞれ算出する第２のステップと、前記各測位データにおける各測位点をそれぞれクラスタとし、それぞれのクラスタから一定領域内かつ測位時刻の間隔が一定時間内に含まれる複数の測位点をそれぞれ取得する第３のステップと、前記複数の測位点の測位精度および測位データを用いて測位精度を重みとする重み付き重心を算出し、前記それぞれのクラスタの中心点とする第４のステップと、各クラスタの中心点間の距離が一定距離以下であるクラスタを併合する第５のステップと、併合されたクラスタに含まれる各クラスタの測位点を測位時刻の順番に並べ、隣り合う２つの測位点の測位時刻の時間間隔が一定時間以上の場合、前記併合されたクラスタを分離する第６のステップと、併合されたクラスタ及び併合後に分離されたクラスタの中心点をユーザの滞留点として抽出する第５のステップと、を有することを要旨とする。
【０００７】
本発明によれば、各測位データにそれぞれ含まれる測位誤差データを用いて各測位データの測位精度をそれぞれ算出し、各測位データにおける各測位点をそれぞれクラスタとし、任意のクラスタから一定領域内かつ測位時刻の間隔が一定時間内に含まれる複数の測位点を取得し、それら複数の測位点の測位精度および測位データを用いて測位精度を重みとする重み付き重心を算出し、その重み付き重心を任意のクラスタの中心点とし、その中心点をユーザの滞留点として抽出するため、環境要因によって測位精度が変化する場合でも、精度の悪い測位点による影響で滞留点の場所がずれてしまうことを抑制できることから、ユーザが留まった滞留点を精度よく抽出することができる。
【０００８】
請求項２の滞留点抽出方法は、請求項１に記載の滞留点抽出方法において、前記第２のステップと前記第３のステップとの間に、測位時刻の間隔が一定時間より大きく、かつ、測位点間が一定距離より小さい測位データ間に新たな測位データを追加するステップを更に有することを要旨とする。
【０００９】
本発明によれば、測位時刻の間隔が一定時間より大きく、かつ、測位点間が一定距離より小さい測位データ間に新たな測位データを追加するため、測位データの測位取得間隔が変化する場合でも、滞留の可能性が高い地点に多くの測位データを補間できることから、ユーザが留まった滞留点を更に精度よく抽出することができる。
【００１０】
請求項３の滞留点抽出装置は、ユーザ端末から収集した位置情報を測位データとして記憶する記憶手段と、前記記憶手段から各測位データを読み出して、前記各測位データにそれぞれ含まれる測位誤差データを用いて各測位データの測位精度をそれぞれ算出する算出手段と、前記各測位データにおける各測位点をそれぞれクラスタとし、それぞれのクラスタから一定領域内かつ測位時刻の間隔が一定時間内に含まれる複数の測位点をそれぞれ取得する取得手段と、前記複数の測位点の測位精度および測位データを用いて測位精度を重みとする重み付き重心を算出し、前記それぞれのクラスタの中心点とする算出手段と、各クラスタの中心点間の距離が一定距離以下であるクラスタを併合する併合手段と、併合されたクラスタに含まれる各クラスタの測位点を測位時刻の順番に並べ、隣り合う２つの測位点の測位時刻の時間間隔が一定時間以上の場合、前記併合されたクラスタを分離する分離手段と、併合されたクラスタ及び併合後に分離されたクラスタの中心点をユーザの滞留点として抽出する抽出手段と、を有することを要旨とする。
【００１１】
請求項４の滞留点抽出装置は、請求項３に記載の滞留点抽出装置において、測位時刻の間隔が一定時間より大きく、かつ、測位点間が一定距離より小さい測位データ間に新たな測位データを追加する補間手段を更に有することを要旨とする。
【００１２】
請求項５の滞留点抽出プログラムは、請求項１又は２に記載の滞留点抽出方法をコンピュータに実行させることを要旨とする。
【発明の効果】
【００１３】
本発明によれば、ユーザが留まった滞留点の抽出精度を高めることができる。
【図面の簡単な説明】
【００１４】
【図１】滞留点抽出装置の機能ブロック構成を示す図である。
【図２】測位データＤＢの構成例を示す図である。
【図３】測位データ抽出部の処理フローを示す図である。
【図４】測位データ補間部の処理フローを示す図である。
【図５】測位データの線形補間例を示す図である。
【図６】滞留点抽出部の処理フローを示す図である。
【図７】滞留点ＤＢの構成例を示す図である。
【図８】滞留点の抽出例を示す図である。
【発明を実施するための形態】
【００１５】
以下、本発明を実施する一実施の形態について図面を用いて説明する。
【００１６】
図１は、本実施の形態に係る滞留点抽出装置１の機能ブロック構成を示す図である。この滞留点抽出装置１は、測位データＤＢ１１と、測位データ抽出部１２と、測位データ補間部１３と、滞留点抽出部１４と、滞留点ＤＢ１５と、を備えて構成される。以下、それら各部の機能について詳述する。
【００１７】
測位データＤＢ１１は、フィーチャーフォンやスマートフォンなどのユーザ端末から、ＧＰＳや携帯の無線基地局、Ｗｉ−Ｆｉなどを利用して取得できる位置情報を測位データとして収集し、保存する機能部である。
【００１８】
測位データＤＢ１１の構成例を図２に示す。測位データは、ユーザＩＤ（ｕｉｄ）、測位時間（ｔｉｍｅ）、経度（ｌｏｎｇｉｔｕｄｅ）、緯度（ｌａｔｉｔｕｄｅ）、測位方法（ｍｅｔｈｏｄ）、測位誤差（ａｃｃｕｒａｃｙ）などにより構成される。測位誤差とは、ＧＰＳなどで計測された測位の不正確度であり、収集した位置情報に既に含まれているパラメータ値である。図２の構成例では、メートルを単位としている。なお、高度や加速度など、その他の情報が測位データに含まれていても構わない。
【００１９】
測位データ抽出部１２は、入力された対象ユーザＩＤリストに記載されたユーザＩＤに該当する測位データを測位データＤＢ１１から抽出する。このとき、後述する図３の手続きにしたがって、測位誤差から測位精度を算出し、抽出した測位データに付与した上で出力する。
【００２０】
測位データ補間部１３は、測位データ抽出部１２から出力された測位データを入力とし、後述する図４の手続きにしたがって、測位時間の間隔が一定時間より大きく、かつ、測位点間が一定距離より小さい測位データ間に新たな測位データを線形補間し、もとの測位データに加えた上で出力する。なお、測位点とは、測位された時間における経度・緯度が示す地点という。
【００２１】
滞留点抽出部１４は、測位データ補間部１３から出力された測位データを入力とし、後述する図６の手続きにしたがって、測位精度に応じて測位点に重みをつけたカーネル密度ベースのクラスタリング手法を用いて滞留点を抽出する。抽出した滞留点は、滞留点ＤＢ１５に出力し、保存する。
【００２２】
次に、測位データ抽出部１２、測位データ補間部１３、滞留点抽出部１４の各動作を詳述する。最初に、測位データ抽出部１２について説明する。図３は、測位データ抽出部１２の処理フローを示す図である。
【００２３】
まず、ステップＳ１０１において、事前に与えられた対象ユーザＩＤリストに含まれるユーザＩＤを入力とし、未処理のユーザＩＤに該当する全ての測位データを測位データＤＢ１１から取得する。以降のステップＳ１０２は、ユーザＩＤごとに実行される。
【００２４】
次に、ステップＳ１０２において、ステップＳ１０１で取得した各測位データにそれぞれ含まれる各測位誤差ａを用いて、各測位データの測位精度Ａ（ａ）を式（１）よりそれぞれ算出する。
【００２５】
【数１】
0005930551.tif 000002
ここで、Ａは測位精度を求める関数、ａは測位誤差の値、Ａ０は測位誤差がゼロの場合の測位精度、λは減衰定数である。式（１）を用いることにより、測位精度Ａは、Ａ０をピークとして測位誤差が大きくなるごとに指数関数的に減衰することになる。減衰の強さは減衰定数λの大きさによって調節できる。測位精度Ａ０と減衰定数λは事前に人手によって任意に定めることができるが、共に正の値でなければならない。例えば、Ａ０＝１、λ＝０．０１などを用いる。
【００２６】
なお、測位誤差が大きるなるほど測位精度が小さくなるような関数であり、負の値をとることがなければ、式（１）以外の関数を用いても構わない。また、ＧＰＳ、無線基地局、Ｗｉ−Ｆｉなどの測位方法に応じて測位精度Ａ０や減衰定数λの値を変えるなど、測位誤差ａ以外の情報を考慮した関数を用いても構わない。
【００２７】
そして、このようにして算出した測位精度を、ステップＳ１０１で取得した測位データに付与し、新たな測位データとして測位データ補間部１３に出力する。
【００２８】
その後、ステップＳ１０３において、未処理のユーザＩＤがあるか否かを判定し、未処理のユーザＩＤがある場合は、ステップＳ１０１に戻り、全てのユーザＩＤについてステップＳ１０１，Ｓ１０２を行う。一方、未処理のユーザＩＤがない場合は、処理を終了する。
【００２９】
続いて、測位データ補間部１３の動作について説明する。図４は、測位データ補間部１３の処理フローを示す図である。
【００３０】
まず、ステップＳ２０１において、測位データ抽出部１２から出力された測位データを入力とし、未処理のユーザＩＤに該当する全ての測位データを取得する。以降のステップＳ２０２〜Ｓ２０５は、ユーザＩＤごとに実行される。
【００３１】
次に、ステップＳ２０２において、未処理の隣接測位データを取得する。具体的には、ステップＳ２０１で取得した各測位データから、測位点と当該測位点に時間的に隣接している測位点とを隣接測位データとして取得する。ここでは、測位データｄの集合Ｄが｛ｄ０，ｄ１，…，ｄnー１｜ｎ＞２，ｎ∈Ｎ｝のように測位時間昇順に構成されているものとし、隣接測位データを含む集合Ｄ’を｛（ｄ０，ｄ１），（ｄ１，ｄ２），…，（ｄnー２，ｄnー１）｜ｎ＞２，ｎ∈Ｎ｝と表現する。なお、ｎは、現在処理中のユーザＩＤに該当する測位データの総数である。以降、この隣接測位データを用いて測位時間昇順で順に処理する。
【００３２】
次に、ステップＳ２０３において、事前に人手によって定められた測位時間間隔閾値Ｔｌｅｒｐおよび測位距離間隔閾値Ｌｌｅｒｐを用いて、隣接測位データｄｉ，ｄｉ＋１（０≦ｉ＜ｎ−１；ｉ∈Ｚ）にそれぞれ含まれる測位時間ｔｉ，ｔｉ＋１と測位点ｌｉ，ｌｉ＋１が式（２）の条件を満たしているか否かを判定する。
【００３３】
【数２】
0005930551.tif 000003
なお、ｄｉｓｔとは、与えられた２つの測位点ｌｉ，ｌｉ＋１間における、回転楕円体上の最小距離をメートル単位で出力する関数である。例えば、ヒュベニの距離計算式などを用いる。
【００３４】
そして、式（２）の条件を満たす場合、前述したように測定回数の抑制処理が働いていることが考えられるため、ステップＳ２０４へ進み、隣接測位データｄｉ，ｄｉ＋１における２つの測位データ間に対して新たな測位データを追加する。一方、式（２）の条件を満たさない場合は、ステップＳ２０４を行うことなくステップＳ２０５へ進む。
【００３５】
次に、ステップＳ２０４において、新たな測位データを補間間隔閾値Ｓｌｅｒｐの間隔で線形補間する。具体的には、隣接測位データｄｉ，ｄｉ＋１間を線形補間する場合、式（３）より算出した補間測位データＤｉ，ｉ＋１を新たな測位データとして追加する。
【００３６】
【数３】
0005930551.tif 000004
すなわち、隣接する２つの測位点間の線分を補間間隔閾値Ｓｌｅｒｐで分割し、分割された各点に補間測位点を新たに追加する。これにより、（Ｓｌｅｒｐ−１）個の補間測位点が増加することになる。なお、ｌｏｎｉは測位点ｌｉにおける経度を表し、ｌａｔｉは測位点ｌｉにおける緯度を表している。図５は、測位データの線形補間例を示す図である。測位時間間隔閾値Ｔｌｅｒｐ＝１５、測位距離間隔閾値Ｌｌｅｒｐ＝２００、補間間隔閾値Ｓｌｅｒｐ＝４の場合を例示している。
【００３７】
次に、ステップＳ２０５において、未処理の隣接測位データがあるか否かを判定し、未処理の隣接測位データがある場合は、ステップＳ２０２へ戻り、全ての未処理の隣接測位データについてステップＳ２０２〜Ｓ２０４を行う。一方、未処理の隣接測位データがない場合は、ステップＳ２０６へ進む。
【００３８】
次に、ステップＳ２０６において、未処理のユーザＩＤがあるか否かを判定し、未処理のユーザＩＤがある場合は、ステップＳ２０１へ戻り、全てのユーザＩＤについてステップＳ２０１〜Ｓ２０５を行う。一方、未処理のユーザＩＤがない場合、ステップＳ２０７へ進む。
【００３９】
最後に、ステップＳ２０７において、これまでの処理によって線形補間が行われた測位データ、又は線形補間を行う必要がなかったそのままの測位データを滞留点抽出部１４に出力する。
【００４０】
続いて、滞留点抽出部１４の動作について説明する。図６は、滞留点抽出部１４の処理フローを示す図である。
【００４１】
まず、ステップＳ３０１において、測位データ補間部１３から出力された測位データを入力とし、未処理のユーザＩＤに該当する全ての測位データを処理する。以降のステップＳ３０２〜Ｓ３１１は、ユーザＩＤごとに実行される。
【００４２】
次に、ステップＳ３０２において、ステップＳ３０１で取得した測位データｄに含まれる全ての各測位点ｌをそれぞれクラスタとして初期化し、ループ回数をゼロに設定する。なお、ここでいう初期化とは、各クラスタの中心点ｄｉｃを測位点ｌｉそのものの値にそれぞれ設定することをいう。すなわち、ｉ番目のクラスタの中心点ｄｉｃの初期値は測位データｄｉとなる。
【００４３】
なお、クラスタとは、ユーザが所定の位置に留まっていたと考えられる範囲の最小単位である。ステップＳ３０２〜Ｓ３０８では、各測位点をそれぞれクラスタとし、その後、ステップＳ３０９，Ｓ３１０において、クラスタを併合又は併合後のクラスタを分割することにより、一定時間ごとに留まったユーザの滞留点を抽出する。
【００４４】
次に、ステップＳ３０３において、未処理のクラスタ（以降、対象クラスタ）の中心から、事前に人手によって定められた半径Ｒ（単位はメートル）以内かつ時間Ｔ以内（単位は秒）に含まれる複数の測位点を取得する。具体的には、半径Ｒかつ時間Ｔ以内に含まれる測位点のインデックスの集合Ｋを式（４）より算出する。
【００４５】
【数４】
0005930551.tif 000005
ここで、ｎは、現在処理中のユーザＩＤに該当する測位データの総数である。
【００４６】
次に、ステップＳ３０４において、ステップＳ３０３で取得した複数の測位点ｌｋの測位精度Ａ（ａｋ）および測位データｄｋを用いて、測位精度を重みとする重み付き重心ｄ’ｉｃを式（５）より算出する。
【００４７】
【数５】
0005930551.tif 000006
ここで、重み付き重心ｄ’ｉｃの算出方法を具体的に説明する。例えば、ステップＳ３０３で３つの測位データｄｋが取得され、取得された各測位データｄ１〜ｄ３の実データが以下であるとする。右辺に示すデータ構造は、左から順に、測位時間，経度，緯度，測位精度である。
【００４８】
ｄ１＝｛２０１４／１／１  ００：００，［１４０，４０］，０．５｝
ｄ２＝｛２０１４／１／１  ００：１０，［１４１，４１］，０．３｝
ｄ３＝｛２０１４／１／１  ００：２０，［１４２，４２］，０．２｝
これらの測位データｄ１〜ｄ３を用いて、測位時間，経度，緯度，測位精度の各重み付き重心をそれぞれ算出し、算出し終えた全てを対象クラスタの重み付き重心とする。例えば、測位時間ｔであれば、ｔ＝（０．５×［２０１４／１／１  ００：００］＋０．３×［２０１４／１／１  ００：１０］＋０．２×［２０１４／１／１  ００：２０］）÷（０．５＋０．３＋０．２）＝［２０１４／１／１  ００：０７］が重み付き測位時間となる。
【００４９】
同様に、経度ｌｏｎ，緯度ｌａｔであれば、［ｌｏｎ，ｌａｔ］＝（０．５×［１４０，４０］＋０．３×［１４１，４１］＋０．２×［１４２，４２］）÷（０．５＋０．３＋０．２）＝［１４０．７，４０．７］が重み付き経度，緯度となる。
【００５０】
このように、測位精度および測位データを式（５）に代入して計算することにより、測位データに含まれる経度・緯度や時間など、多次元情報の重み付き重心が算出される。なお、高度など、経度・緯度や時間以外の情報が測位データに含まれていてもよく、その場合にはその重心を更に追加してもよい。
【００５１】
次に、ステップＳ３０５において、対象クラスタの中心点ｄｉｃを、ステップＳ３０４で算出した重み付き重心ｄ’ｉｃに移動する。ここでいう移動とは、対象クラスタの中心点ｄｉｃを重み付き重心ｄ’ｉｃに変更することをいう。これにより、対象クラスタの中心が測位精度に応じた位置に移動することになる。
【００５２】
次に、ステップＳ３０６において、未処理のクラスタがあるか否かを判定し、未処理のクラスタがある場合は、ステップＳ３０３へ戻り、全てのクラスタについてステップＳ３０３〜Ｓ３０５を行う。一方、未処理のクラスタがない場合は、ステップＳ３０７へ進む。
【００５３】
次に、ステップＳ３０７において、全てのクラスタについて、各クラスタの中心ｄｉｃを重み付き重心ｄ’ｉｃに変更する処理を１回行ったので、ループ回数をインクリメントし、再度、全てのクラスタを未処理とする。
【００５４】
次に、ステップＳ３０８において、現時点のループ回数が、事前に人手によって設定されたループ限界数閾値Ｉの回数に到達しているか否かを判定し、ループ限界数閾値Ｉに到達していない場合は、ステップＳ３０３へ戻り、今度は、ステップＳ３０５で移動した移動後の中心点を基準にしてステップＳ３０３〜Ｓ３０５を行う。
【００５５】
ここまでの処理において、例えば１００個の測位データがある場合、ステップＳ３０２により、１００個のクラスタが初期に生成され、ステップＳ３０３〜Ｓ３０５により、各クラスタの中心点が測位精度に応じた位置に移動するので、１００個のクラスタが測位データの密な場所に集合することになる。一方、ループ限界数閾値Ｉに到達した場合は、ステップＳ３０９へ進む。
【００５６】
次に、ステップＳ３０９において、集合したクラスタを併合することにより、測位データが密になっている場所の数だけクラスタを残す。具体的には、クラスタの中心点間の距離が、事前に人手によって設定されたクラスタ中心点間距離閾値Ｃ以下であるクラスタを併合する。なお、クラスタの中心点間距離は関数ｄｉｓｔを用いて計算する。また、併合した新しいクラスタの中心点は、式（５）に基づき重み付き重心により算出する。その際、インデックスの集合Ｋの要素は、併合対象となるクラスタに含まれる測位点の和集合を用いる。
【００５７】
次に、ステップＳ３１０において、クラスタ内の測位データ集合が、事前に人手によって設定された時間間隔閾値Ｓより大きい場合は、該当するクラスタを分割する。つまり、クラスタ内の測位点を時間昇順で順番に確認したとき、時間ｈと時間ｈ＋１とにおける時間間隔が時間間隔閾値Ｓより大きい場合には、時間ｈまでの測位データで構成されるクラスタと、時間ｈ＋１以降の測位データで構成されるクラスタとに分離する。その際、分離した２つの各クラスタの中心点の位置は、いずれも元のクラスタの中心点の位置を設定する。この処理により、ステップＳ３０９で距離的観点から併合されてしまった、行きと帰りで同じ場所となるようなクラスタを、時間的観点から区別することができる。
【００５８】
次に、ステップＳ３１１において、残存する各クラスタの中心点をユーザの滞留点としてそれぞれ出力し、滞留点ＤＢ１５に保存する。滞留点ＤＢ１５の構成例を図７に示す。図７の構成例では、あるユーザが１つの地点に滞留した場合を例示している。滞留点における滞留開始時間（ｂｅｇｉｎ＿ｔｉｍｅ）および滞留終了時間（ｅｎｄ＿ｔｉｍｅ）は、それぞれ、クラスタに含まれる測位点の最小時間および最大時間で定義される。また、滞留時間（ｓｔａｙ＿ｔｉｍｅ）は、滞留終了時間（ｅｎｄ＿ｔｉｍｅ）から滞留開始時間（ｂｅｇｉｎ＿ｔｉｍｅ）を引くことで求められる。経度（ｌｏｎｇｉｔｕｄｅ）および緯度（ｌａｔｉｔｕｄｅ）は、クラスタの中心点、すなわちユーザの滞留点である。
【００５９】
そして、ステップＳ３１２において、未処理のユーザＩＤがあるか否かを判定し、未処理のユーザＩＤがある場合は、ステップＳ３０１へ戻り、全てのユーザＩＤについてステップＳ３０１〜Ｓ３１１を行う。一方、未処理のユーザＩＤがない場合は、処理を終了する。
【００６０】
以上より、本実施の形態によれば、測位データ抽出部１２により、各測位データにそれぞれ含まれる測位誤差を用いて各測位データの測位精度をそれぞれ算出し、滞留点抽出部１４により、各測位データにおける各測位点をそれぞれクラスタとし、対象クラスタから半径Ｒ以内かつ時間Ｔ以内に含まれる複数の測位点を取得し、それら複数の測位点の測位精度および測位データを用いて測位精度を重みとする重み付き重心を算出し、その重み付き重心を対象クラスタの中心点とし、その中心点をユーザの滞留点として抽出するので、環境要因によって測位精度が変化する場合でも、精度の悪い測位点による影響で滞留点の場所がずれてしまうことを抑制できる。
【００６１】
また、本実施の形態によれば、測位データ補間部１３により、測位時間間隔が測位時間間隔閾値より大きく、かつ、測位点間が測位距離間隔閾値より小さい測位データ間に新たな測位データを追加するので、測位データの測位取得間隔が変化する場合でも、滞留の可能性が高い地点に多くの測位データを補間できる。
【００６２】
以上説明した大きく２つの処理を行うことにより、図８に示すように、ユーザが留まった滞留点を精度よく抽出することができる。
【００６３】
最後に、本実施の形態で説明した滞留点抽出装置１は、メモリやＣＰＵを備えたコンピュータにより実現できる。また、滞留点抽出装置１の各動作をプログラムとして構築し、コンピュータにインストールして実行させることや、通信ネットワークを介して流通させることも可能である。
【符号の説明】
【００６４】
１…滞留点抽出装置
１１…測位データＤＢ
１２…測位データ抽出部
１３…測位データ補間部
１４…滞留点抽出部
１５…滞留点ＤＢ
Ｓ１０１〜Ｓ１０３、Ｓ２０１〜Ｓ２０７、Ｓ３０１〜Ｓ３１２…ステップ
【図１】
0005930551.tif 000007
【図２】
0005930551.tif 000008
【図３】
0005930551.tif 000009
【図４】
0005930551.tif 000010
【図５】
0005930551.tif 000011
【図６】
0005930551.tif 000012
【図７】
0005930551.tif 000013
【図８】
0005930551.tif 000014