(57)【要約】  本発明の実施例は、関心ポイントのクラスタリング方法及び関連する装置を開示する。関心ポイントのクラスタリング方法は、所定の期間内にユーザの位置決めポイントセットを取得するステップと、前記位置決めポイントセットに従って滞在ポイントセットを生成するステップであって、前記滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、前記ホットエリアは以下の条件、前記ホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が前記２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、前記ホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する、生成するステップと、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップと、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルに従ってスクリーニング手段によって前記滞在ポイントセットから信頼される滞在ポイントを取得するステップと、関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするステップとを有する。本発明において提供される技術的解決策を利用することによって、ＰＯＩの信頼性及び参照値が効果的に向上可能である。
2016537718.tif 000002
【特許請求の範囲】
【請求項１】
関心ポイントのクラスタリング方法であって、
所定の期間内にユーザの位置決めポイントセットを取得するステップと、
前記位置決めポイントセットに従って滞在ポイントセットを生成するステップであって、前記滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、前記ホットエリアは以下の条件、前記ホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が前記２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、前記ホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する、生成するステップと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップであって、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が前記滞在ポイントのより高い信頼レベルを示す、計算するステップと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルに従ってスクリーニング手段によって前記滞在ポイントセットから信頼される滞在ポイントを取得するステップであって、前記信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい、取得するステップと、
関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするステップであって、前記密度接続とは、２つの信頼される常駐ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す、クラスタリングするステップと、
を有する方法。
【請求項２】
前記位置決めポイントセットに従って滞在ポイントセットを生成するステップは、
前記条件を充足するホットエリアを決定するステップと、
前記ホットエリアを表す滞在ポイントとして前記ホットエリアの幾何学的中心ポイントを決定するステップと、
を有する、請求項１記載の方法。
【請求項３】
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップは、
各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するステップと、
式
【数６】
2016537718.tif 000008
を用いることによって、且つ、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態に従って、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップであって、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは前記滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は前記移動状態のより大きな信頼レベルウェイトを示す、計算するステップと、
を有する、請求項１又は２記載の方法。
【請求項４】
前記位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得するステップは、具体的には、
前記ユーザの端末におけるセンサデータ、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、前記位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得することである、請求項３記載の方法。
【請求項５】
前記関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするステップは、
関心ポイントのエリアとして、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアを決定するステップであって、中心がリーフ滞在ポイントである所定の半径カバレッジ範囲内の全ての滞在ポイントの信頼レベルの和は所定の閾値より大きくない、決定するステップを有する、請求項１乃至４何れか一項記載の方法。
【請求項６】
関心ポイントのクラスタリング装置であって、
所定の期間内にユーザの位置決めポイントセットを取得するよう構成される取得ユニットと、
前記取得ユニットにより取得された前記位置決めポイントセットに従って滞在ポイントセットを生成するよう構成される滞在ポイント生成ユニットであって、前記滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、前記ホットエリアは以下の条件、前記ホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が前記２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、前記ホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する、滞在ポイント生成ユニットと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成される計算ユニットであって、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が前記滞在ポイントのより高い信頼レベルを示す、計算ユニットと、
前記滞在ポイントセットにおける各滞在ポイントのものであって、前記計算ユニットにより計算される信頼レベルに従ってスクリーニング手段によって前記滞在ポイントセットから信頼される滞在ポイントを取得するよう構成されるフィルタリングユニットであって、前記信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい、フィルタリングユニットと、
関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするよう構成されるクラスタリングユニットであって、前記密度接続とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す、クラスタリングユニットと、
を有するクラスタリング装置。
【請求項７】
前記滞在ポイント生成ユニットは、
前記条件を充足するホットエリアを決定するよう構成される第１の決定ユニットと、
前記ホットエリアを表す滞在ポイントとして前記ホットエリアの幾何学的中心ポイントを決定するよう構成される第２の決定ユニットと、
を有する、請求項６記載の関心ポイントのクラスタリング装置。
【請求項８】
前記計算ユニットは、
各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するよう構成される取得サブユニットと、
式
【数７】
2016537718.tif 000009
を用いることによって、且つ、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントのものであって、前記取得サブユニットにより取得される移動状態に従って、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成される計算サブユニットであって、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは前記滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は前記移動状態のより大きな信頼レベルウェイトを示す、計算サブユニットと、
を有する、請求項６又は７記載の関心ポイントのクラスタリング装置。
【請求項９】
前記取得サブユニットは、具体的には、
前記ユーザの端末におけるセンサデータ、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、前記位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得するよう構成される、請求項８記載の関心ポイントのクラスタリング装置。
【請求項１０】
前記クラスタリングユニットは、具体的には、
関心ポイントを形成するため全ての密度接続される信頼される滞在ポイントをクラスタリングし、関心ポイントのエリアとして、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアを決定するよう構成され、中心がリーフ滞在ポイントである所定の半径カバレッジ範囲内の全ての滞在ポイントの信頼レベルの和は所定の閾値より大きくない、請求項６乃至９何れか一項記載の関心ポイントのクラスタリング装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地理情報処理技術の分野に関し、特に関心ポイントのクラスタリング方法及び関連する装置に関する。
【背景技術】
【０００２】
関心ポイント（ＰＯＩ，Ｐｏｉｎｔ  Ｏｆ  Ｉｎｔｅｒｅｓｔ）は、例えば、自宅、オフィス又は頻繁に訪れるスーパーマーケットなど、ユーザにとって非常に重要なエリアなど、ユーザが長時間頻繁に滞在する位置エリアを表す。
【０００３】
ユーザの日常行動の追跡情報は、携帯電話などの端末のＷｉ−Ｆｉネットワーク、グローバル・ポジショニング・システム（ＧＰＳ，Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）及び基地局識別子（ＩＤ，Ｉｄｅｎｔｉｔｙ）などの位置決め機能を利用することによって取得されてもよい。追跡情報は、位置決めのずれを有する多数の位置決め座標点から構成される。追跡情報からユーザのＰＯＩをどのように抽出するかの研究は、状況認識及び位置ベースサービス（ＬＢＳ，Ｌｏｃａｔｉｏｎ−ｂａｓｅｄ  Ｓｅｒｖｉｃｅ）アプリケーション及びサービスにとって非常に価値があり、また学術における研究の焦点である。
【０００４】
現在、ユーザの複数のＧＰＳ追跡情報に基づきＰＯＩを探索するための方法があり、当該方法の主要なアイデアは、まずツリー状の階層パターンを用いることによってユーザの複数の履歴位置データをモデル化し、それから、ツリー状の階層パターンに基づき、ハイパーテキストの主題に基づき検索を実行するインタフェースモデルを提案し、ユーザから個別の単一の訪問の位置へのリンクを確立することである。
【０００５】
しかしながら、上記の方法では、ユーザの滞在ポイントは、空間及び時間の次元を利用することによって抽出される。滞在ポイントは、ユーザの単一の訪問のみを表すことができるが、ユーザにとって非常に重要なＰＯＩの場所を表すことはできない。さらに、ＰＯＩが探索されているとき、ユーザの履歴位置データしか参照されず、従って、探索されたＰＯＩの信頼性及び参照値は低い。
【発明の概要】
【０００６】
本発明の実施例は、ＰＯＩの信頼性及び参照値を改善するため利用される関心ポイントのクラスタリング方法及び関連する装置を提供する。
【０００７】
本発明の第１の態様は、関心ポイントのクラスタリング方法を提供し、ここで、当該方法は、
所定の期間内にユーザの位置決めポイントセットを取得するステップと、
前記位置決めポイントセットに従って滞在ポイントセットを生成するステップであって、前記滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、前記ホットエリアは以下の条件、前記ホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が前記２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、前記ホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する、生成するステップと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップであって、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が前記滞在ポイントのより高い信頼レベルを示す、計算するステップと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルに従ってスクリーニング手段によって前記滞在ポイントセットから信頼される滞在ポイントを取得するステップであって、前記信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい、取得するステップと、
関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするステップであって、前記密度接続とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す、クラスタリングするステップと、
を有する。
【０００８】
本発明の第１の態様に基づき、第１の可能な実現方式では、
前記位置決めポイントセットに従って滞在ポイントセットを生成するステップは、
前記条件を充足するホットエリアを決定するステップと、
前記ホットエリアを表す滞在ポイントとして前記ホットエリアの幾何学的中心ポイントを決定するステップと、
を有する。
【０００９】
本発明の第１の態様又は本発明の第１の態様の第１の可能な実現方式に基づき、第２の可能な実現方式では、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップは、
各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するステップと、
式
【数１】
2016537718.tif 000003
を用いることによって、且つ、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態に従って、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップであって、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは前記滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は前記移動状態のより大きな信頼レベルウェイトを示す、計算するステップと、
を有する。
【００１０】
本発明の第１の態様の第２の可能な実現方式に基づき、第３の可能な実現方式では、前記位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得するステップは、具体的には、
前記ユーザの端末におけるセンサデータ、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、前記位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得することである。
【００１１】
第１の態様、又は本発明の第１の態様の第１の可能な実現方式、又は本発明の第１の態様の第２の可能な実現方式、又は本発明の第１の態様の第３の可能な実現方式に基づき、第４の可能な実現方式では、前記関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするステップは、
関心ポイントのエリアとして、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアを決定するステップであって、中心がリーフ滞在ポイントである所定の半径カバレッジ範囲内の全ての滞在ポイントの信頼レベルの和は所定の閾値より大きくない、決定するステップを有する。
【００１２】
本発明の第２の態様は、関心ポイントのクラスタリング装置を提供し、ここで、当該装置は、
所定の期間内にユーザの位置決めポイントセットを取得するよう構成される取得ユニットと、
前記取得ユニットにより取得された前記位置決めポイントセットに従って滞在ポイントセットを生成するよう構成される滞在ポイント生成ユニットであって、前記滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、前記ホットエリアは以下の条件、前記ホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が前記２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、前記ホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する、滞在ポイント生成ユニットと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成される計算ユニットであって、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が前記滞在ポイントのより高い信頼レベルを示す、計算ユニットと、
前記滞在ポイントセットにおける各滞在ポイントのものであって、前記計算ユニットにより計算される信頼レベルに従ってスクリーニング手段によって前記滞在ポイントセットから信頼される滞在ポイントを取得するよう構成されるフィルタリングユニットであって、前記信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい、フィルタリングユニットと、
関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするよう構成されるクラスタリングユニットであって、前記“密度接続”とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が直接的に接続されるか、又は間接的に接続されることを示す、クラスタリングユニットと、
を有する。
【００１３】
本発明の第２の態様に基づき、第１の可能な実現方式では、
前記滞在ポイント生成ユニットは、
前記条件を充足するホットエリアを決定するよう構成される第１の決定ユニットと、
前記ホットエリアを表す滞在ポイントとして前記ホットエリアの幾何学的中心ポイントを決定するよう構成される第２の決定ユニットと、
を有する。
【００１４】
本発明の第２の態様又は本発明の第２の態様の第１の可能な実現方式に基づき、第２の可能な実現方式では、
前記計算ユニットは、
各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するよう構成される取得サブユニットと、
式
【数２】
2016537718.tif 000004
を用いることによって、且つ、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントのものであって、前記取得サブユニットにより取得される移動状態に従って、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成される計算サブユニットであって、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは前記滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は前記移動状態のより大きな信頼レベルウェイトを示す、計算サブユニットと、
を有する。
【００１５】
本発明の第２の態様の第２の可能な実現方式に基づき、第３の可能な実現方式では、前記取得サブユニットは、具体的には、前記ユーザの端末におけるセンサデータ、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、前記位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得するよう構成される。
【００１６】
本発明の第２の態様、又は本発明の第２の態様の第１の可能な実現方式、又は本発明の第２の態様の第２の可能な実現方式、又は本発明の第２の態様の第３の可能な実現方式に基づき、第４の可能な実現方式では、前記クラスタリングユニットは、具体的には、関心ポイントを形成するため全ての密度接続される信頼される滞在ポイントをクラスタリングし、関心ポイントのエリアとして、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアを決定するよう構成され、中心がリーフ滞在ポイントである所定の半径カバレッジ範囲内の全ての滞在ポイントの信頼レベルの和は所定の閾値より大きくない。
【００１７】
本発明の実施例が以下の効果を有することは、上記の技術的解決策から知ることができる。
【００１８】
本発明の実施例では、１つの滞在ポイントが位置決め精度及び時間閾値に従って複数の位置決めポイントによって形成され、大部分の待ち合わせポイント、位置決めジャンプポイント及び通過ポイントが、位置決め精度及び時間閾値の制約の下でフィルタリング可能であることが知ることができる。さらに、滞在ポイントの信頼レベルは、滞在ポイントの位置決めポイントの移動状態を参照して計算され、信頼レベルが相対的に低い滞在ポイントが滞在ポイントの信頼レベルに従って選抜され、いくつかの途中のノイズ滞在ポイント（交通渋滞部分における滞在時、信号機の待ち時間及びゆっくり歩行している時間に生成された擬似滞在ポイントなど）が更にフィルタリングできる。従って、密度接続される信頼される滞在ポイントをクラスタリングすることによって最終的に形成される関心ポイントは、より高い信頼性及びより高い参照値を有する。
【図面の簡単な説明】
【００１９】
本発明の実施例又は従来技術における技術的解決策をより明確に説明するため、以下は、実施例又は従来技術を説明するのに必要な添付図面を簡単に紹介する。明らかに、以下の説明における添付図面は本発明のいくつかの実施例を単に示し、当業者は、創作的な努力なく、これらの添付図面から他の図面を依然として導出してもよい。
【図１】図１は、本発明による関心ポイントのクラスタリング方法の実施例の概略的なフローチャートである。
【図２ａ】図２ａは、本発明による適用シナリオにおける位置決めポイントセットの追跡の概略図である。
【図２ｂ】図２ｂは、本発明による適用シナリオにおいて形成される滞在ポイントセットの概略図である。
【図２ｃ】図２ｃは、本発明による適用シナリオにおいてスクリーニング手段によって取得される信頼される滞在ポイントセットの概略図である。
【図２ｄ】図２ｄは、本発明による適用シナリオにおいてクラスタリング手段により取得されるＰＯＩの概略図である。
【図３】図３は、本発明による関心ポイントのクラスタリング装置の実施例の概略的な構成図である。
【図４】図４は、本発明による関心ポイントのクラスタリング装置の他の実施例の概略的な構成図である。
【図５】図５は、本発明による関心ポイントのクラスタリング装置の更なる他の実施例の概略的な構成図である。
【発明を実施するための形態】
【００２０】
本発明の実施例は、関心ポイントのクラスタリング方法及び関連する装置を提供する。
【００２１】
本発明の課題、特徴及び効果をより明確且つより理解可能にするため、以下は、本発明の実施例における添付図面を参照して、本発明の実施例における技術的解決策を明確且つ完全に説明する。明らかに、説明される実施例は、本発明の実施例の全てでなく単なる一部である。創作的な努力なく本発明の実施例に基づき当業者により取得される他の全ての実施例は、本発明の保護範囲内に属する。
【００２２】
以下は、本発明の実施例において提供される関心ポイントのクラスタリング方法を説明する。図１を参照して、本発明の本実施例における関心ポイントのクラスタリング方法は、以下を含む。
【００２３】
１０１．所定の期間内にユーザの位置決めポイントセットを取得する。
【００２４】
本発明の本実施例における位置決めポイントセットは１つ以上の位置決めポイントを有し、位置決めポイントはユーザの位置情報を示すのに利用される。
【００２５】
任意的には、位置決めポイントは、経度値及び緯度値によって表されるＧＰＳ位置ポイントであり、関心ポイントのクラスタリング装置は、ユーザのＧＰＳ位置データから所定の期間内にユーザの位置決めポイントセットを取得する。
【００２６】
１０２．上記の位置決めポイントセットに従って滞在ポイントセットを生成する。
【００２７】
上記の滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、ここで、上記のホットエリアは、以下の条件、上記のホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が上記の２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、上記のホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する。
【００２８】
例えば、位置決めポイントセット｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝は、滞在ポイントが形成されうるホットエリアを構成し、位置決めポイントセット｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝は、以下の２つの条件を充足する必要がある。
【００２９】
１．｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝における何れか２つの位置決めポイントの地理的位置の間の距離は空間閾値Ｄｔｈ未満であり、ここで、Ｄｔｈは固定値でなく、それは関連する位置決めポイントが変わるに従って変化し、具体的には、２つの位置決めポイントの位置決め精度における最大値、すなわち、Ｄｔｈ（Ｐｎ，Ｐｍ）＝ｍａｘ（Ｒａｄｉｕｓ（Ｐｎ），Ｒａｄｉｕｓ（Ｐｍ））である。例えば、位置決めポイントＰ１の位置決め精度は５メータであり、位置決めポイントＰ２の位置決め精度は１０メータであり、このとき、位置決めポイントＰ１及び位置決めポイントＰ２について、Ｄｔｈ（Ｐ１，Ｐ２）は位置決めポイントＰ１及び位置決めポイントＰ２においてより高い位置決め精度に等しく、すなわち、Ｄｔｈ（Ｐ１，Ｐ２）は１０メータに等しいと仮定される。位置決めポイントＰ３の位置決め精度が１５メータである場合、位置決めポイントＰ１及び位置決めポイントＰ３について、Ｄｔｈ（Ｐ１，Ｐ３）は位置決めポイントＰ１及び位置決めポイントＰ３との間のより高い位置決め精度に等しく、すなわち、Ｄｔｈ（Ｐ１，Ｐ２）は１５メータに等しい。
【００３０】
２．異なる位置決めポイントが異なる時点で測定手段により取得されるため、全ての２つの位置決めポイントの間に時間間隔が存在する。例えば、位置決めポイントＰ１は１０：００に測定手段により取得され、位置決めポイントＰ２は１０：０３に測定手段により取得され、このとき、位置決めポイントＰ１と位置決めポイントＰ３との間の時間間隔は３分であると仮定される。本発明の本実施例では、｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝は更に、以下の条件、｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝における位置決めポイントの間の時間間隔の最大値が所定の時間閾値Ｔｔｈ（例えば、Ｔｔｈの値は５分、７分又は１０分であってもよい）より大きく、すなわち、｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝において、測定手段により最初に取得された位置決めポイントと、測定手段により最後に取得された位置決めポイントとの間の時間間隔はＴｔｈより大きく、ここで、Ｔｔｈは、ここで限定されない、実際の要求に従って具体的に設定されてもよい、を充足する必要がある。
【００３１】
任意的には、上記の条件を充足するホットエリアが決定された後、上記のホットエリアの幾何学的中心ポイントは、上記のホットエリアを表す滞在ポイントとして決定され、ここで、滞在ポイントは、ホットエリアにおける全ての位置決めポイントを表すものであってもよい。おそらく、他の方式がまたホットエリアに対応する滞在ポイントを決定するのに利用されてもよい。例えば、ホットエリアの重心が、ホットエリアを表す滞在ポイントとして利用され、ここで、ホットエリアの重心は、ホットエリア内の位置決めポイントの分布に関連する。
【００３２】
１０３．上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算する。
【００３３】
滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が滞在ポイントのより高い信頼レベルを示す。
【００３４】
実現方式では、関心ポイントのクラスタリング装置は、上記の滞在ポイントセットにおける各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得し、上記の滞在ポイントセットにおける各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態に従って、式
【数３】
2016537718.tif 000005
を用いることによって、上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算し、ここで、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、ここで、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は移動状態のより大きな信頼レベルウェイトを示す。例えば、ユーザの可能な移動状態は、静止、歩行又は走行であり、このとき、３つの移動状態について、移動状態に対応し、昇順である移動速度は順に以下のように、静止、歩行又は走行であり、移動状態のものであって、降順である信頼レベルウェイトは順に以下のように、静止、歩行又は走行であると仮定される。
【００３５】
任意的には、関心ポイントのクラスタリング装置は、上記のユーザの端末（携帯電話、タブレット及び車両搭載端末など）におけるセンサデータ（加速度及びジャイロスコープなど）、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、上記の位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得するか、又は、関心ポイントのクラスタリング装置は、ここに限定されず、他の位置決め装置（サーバなど）から上記の位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得してもよい。
【００３６】
１０４．上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルに従ってスクリーニング手段によって上記の滞在ポイントセットから信頼される滞在ポイントを取得する。
【００３７】
上記の信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい。
【００３８】
本発明の本実施例では、関心ポイントのクラスタリング装置は、スクリーニング手段により上記の滞在ポイントセットから信頼される滞在ポイント（すなわち、信頼レベルが所定の信頼レベル閾値より大きい滞在ポイント）を取得し、信頼レベルが所定の信頼レベル閾値より大きくない滞在ポイントを削除する。
【００３９】
１０５．ＰＯＩを形成するため、密度接続される信頼される滞在ポイントをクラスタリングする。
【００４０】
上記の“密度接続”とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す。例えば、信頼される滞在ポイントＰ１のカバレッジ範囲は信頼される滞在ポイントＰ２のカバレッジ範囲と交わり、それから、信頼される滞在ポイントＰ１及び信頼される滞在ポイントＰ２により表されるホットエリアの範囲は、互いに直接的に接続されると仮定される。この場合、信頼される滞在ポイントＰ１及び信頼される滞在ポイントＰ２は密度接続される。あるいは、信頼される滞在ポイントＰ１のカバレッジ範囲が信頼される滞在ポイントＰ３のカバレッジ範囲と交わり、信頼される滞在ポイントＰ２のカバレッジ範囲が信頼される滞在ポイントＰ４のカバレッジ範囲と交わり、信頼される滞在ポイントＰ３のカバレッジ範囲が信頼される滞在ポイントＰ４のカバレッジ範囲と交わり、このとき、信頼される滞在ポイントＰ１及び信頼される滞在ポイントＰ２により表されるホットエリアの範囲は、互いに間接的に接続されると仮定される。この場合、信頼される滞在ポイントＰ１及び信頼される滞在ポイントＰ２はまた密度接続される。
【００４１】
任意的には、信頼される滞在ポイントＰ１（リーフ滞在ポイントであってもよいし、又は内部滞在ポイントであってもよい）が内部滞在ポイントｏから密度到達可能であり、信頼される滞在ポイントＰ２（リーフ滞在ポイントであってもよいし、又は内部滞在ポイントであってもよい）が内部滞在ポイントｏから密度到達可能である場合、信頼される滞在ポイントＰ１及び信頼される滞在ポイントＰ２は密度接続される。以下は、“内部滞在ポイント”、“リーフ滞在ポイント”及び“密度到達可能”を説明する。
【００４２】
内部滞在ポイント：中心が滞在ポイントである所定の半径カバレッジ内の全ての滞在ポイントの信頼されるレベルの和が、所定の閾値より大きい。
【００４３】
リーフ滞在ポイント：中心が滞在ポイントである所定の半径カバレッジ内の全ての滞在ポイントの信頼されるレベルの和が、所定の閾値より大きくない。
【００４４】
密度到達可能：ｐｉ（０＜ｉ＜ｎ）が内部滞在ポイントである必要がある信頼される滞在ポイントｐ１，ｐ２，．．．，ｐｎの所与の系列において、ｐｎはリーフ滞在ポイント又は内部滞在ポイントであってもよく、Ｐ＝ｐ１及びＱ＝ｐｎであり、ｐｉはｐｉ−１（１＜ｉ＜（ｎ＋１））から直接的に密度到達可能であり、このとき、滞在ポイントＱは内部滞在ポイントＰから密度到達可能であると仮定される。
【００４５】
直接的に密度到達可能：信頼される滞在ポイントＰ（リーフ滞在ポイントであってもよいし、又は内部滞在ポイントであってもよい）が信頼される滞在ポイントＱの半径カバレッジ内に配置され、信頼される滞在ポイントＱが内部滞在ポイントである場合、信頼される滞在ポイントＰは、信頼される滞在ポイントＱから直接的に密度到達可能である。
【００４６】
任意的には、全ての密度接続される信頼される滞在ポイントは、ＰＯＩを形成するためクラスタリングされる。さらに、ＰＯＩのエリアとして全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリア、又はＰＯＩのエリアは、ここに限定されない、全ての密度接続される信頼される滞在ポイントを含む最小の円形エリア又は正方形エリアであってもよい。
【００４７】
本発明の本実施例では、１つの滞在ポイントが位置決め精度及び時間閾値により複数の位置決めポイントによって形成され、大部分の待ち合わせポイント、位置決めジャンプポイント及び通過ポイントが、位置決め精度及び時間閾値の制約の下でフィルタリング可能であることが、上記から知ることができる。さらに、滞在ポイントの信頼レベルは、滞在ポイントの位置決めポイントの移動状態を参照して計算され、信頼レベルが相対的に低い滞在ポイントが滞在ポイントの信頼レベルに従って選抜され、いくつかの途中のノイズ滞在ポイント（交通渋滞部分における滞在時、信号機の待ち時間及びゆっくり歩行している時間に生成された擬似滞在ポイントなど）が更にフィルタリングできる。従って、密度接続される信頼される滞在ポイントをクラスタリングすることによって最終的に形成される関心ポイントは、より高い信頼性及びより高い参照値を有する。
【００４８】
本発明の技術的解決策のより良好な理解のため、以下は、特定の適用シナリオを利用することによって、本発明の本実施例における関心ポイントのクラスタリング方法を説明する。
【００４９】
図２ａにおいて、所定の期間内のユーザの位置決めポイントセットの追跡が示されることが仮定される。
【００５０】
ステップ１：関心ポイントのクラスタリング装置は、図２ａに示される位置決めポイントセットから、動的な空間閾値及び時間閾値を用いることによって、以下の２つ条件を充足するホットエリアを決定し、１．ホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が上記の２つの位置決めポイントのより高い位置決め精度未満であり、且つ、２．ホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きく、これらの条件を充足するホットエリアを決定した後、ホットエリアを表す滞在ポイントしてホットエリアの幾何学的中心ポイントを決定し、図２ｂに示される滞在ポイントの追跡の図を取得するため、複数の滞在ポイントを形成し、ここで、図２ｂにおける各黒いポイントは形成された滞在ポイントを表し、各滞在ポイントは、ユーザが同じ場所に滞在するときに生成される多数の位置決めポイントを表しうる。図２ｂが図２ａと比較された後、大部分の待ち合わせポイント、位置決めジャンプポイント及び通過ポイントが図２ｂにおいてフィルタリングされることが知ることができる。
【００５１】
ステップ２：関心ポイントのクラスタリング装置は、１つの滞在ポイントを形成する全ての位置決めポイントにおけるユーザの移動状態（静止、歩行及び走行など）に従って、各滞在ポイントの信頼レベルを計算し、ここで、１つの滞在ポイントの全ての位置決めポイントにおけるユーザの移動状態に対応する平均速度がより低い場合、滞在ポイントの信頼レベルはより高くなり、例えば、滞在ポイントを形成する全ての位置決めポイントにおける移動状態が静止（すなわち、移動速度が０）である滞在ポイントの位置決めポイントのパーセンテージがより高い場合、滞在ポイントの信頼レベルはより高く、そうでなく、滞在ポイントを形成する全ての位置決めポイントにおける移動状態が走行（すなわち、移動速度が０よりはるかに大きい）である滞在ポイントの位置決めポイントのパーセンテージがより高い場合、滞在ポイントの信頼レベルはより低く、各滞在ポイントの信頼レベルを計算した後、図２ｂに示される滞在ポイントセットから、信頼レベルが所定の信頼レベル閾値より大きくない滞在ポイントを削除し、すなわち、図２ｂに示される滞在ポイントセットから、スクリーニング手段によって、信頼レベルが所定の信頼レベル閾値より大きい滞在ポイントを取得し、図２ｃに示される信頼される滞在ポイントセットを取得する。図２ｃが図２ｂと比較された後、いくつかの途中のノイズ滞在ポイント（交通渋滞部分における滞在時、信号機の待ち時間及びゆっくり歩行している時間に生成された擬似滞在ポイント）が図２ｃにおいてフィルタリングされることが知ることができる。
【００５２】
ステップ３：信頼レベルに基づき上記の滞在ポイントをクラスタリングし、全ての滞在ポイントが密度接続される最大滞在ポイントセットを特定し（すなわち、当該セットにおける何れか２つの滞在ポイントが密度接続される）、ＰＯＩを形成するため最大滞在ポイントセットをクラスタリングし、ここで、ＰＯＩのエリアは、クラスタリング手段によって取得され、図２ｄに示されるＰＯＩの概略図など、最大滞在ポイントセットにおける全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドポリゴンを用いることによって表されてもよい。各滞在ポイントの信頼レベルは、ステップ３におけるクラスタリング処理において考慮され、ＰＯＩのクラスタリング信頼性が向上し、ＰＯＩのエリア範囲は実際のケースにおけるエリア範囲により近い。
【００５３】
本発明の実施例は更に、関心ポイントのクラスタリング装置を提供する。図３に示されるように、本発明の本実施例における関心ポイントのクラスタリング装置３００は、取得ユニット３０１、滞在ポイント生成ユニット３０２、計算ユニット３０３、フィルタリングユニット３０４及びクラスタリングユニット３０５を有し、ここで、
【００５４】
取得ユニット３０１は、所定の期間内にユーザの位置決めポイントセットを取得するよう構成される。
【００５５】
本発明の本実施例における位置決めポイントセットは１つ以上の位置決めポイントを有し、位置決めポイントはユーザの位置情報を示すのに利用される。
【００５６】
任意的には、位置決めポイントは経度値及び緯度値により表されるＧＰＳ位置ポイントであり、関心ポイントのクラスタリング装置は、ユーザのＧＰＳ位置データから所定の期間内のユーザの位置決めポイントセットを取得する。
【００５７】
滞在ポイント生成ユニット３０２は、取得ユニット３０１により取得された位置決めポイントセットに従って滞在ポイントセットを生成するよう構成され、ここで、上記の滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、上記のホットエリアは以下の条件、上記のホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が上記の２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、上記のホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する。
【００５８】
任意的には、図３に示される実施例に基づき、図４に示される関心ポイントのクラスタリング装置４００によると、滞在ポイント生成ユニット３０２は、上記の条件を充足するホットエリアを決定するよう構成される第１の決定ユニット３０２１と、上記のホットエリアを表す滞在ポイントとして上記のホットエリアの幾何学的中心ポイントを決定するよう構成される第２の決定ユニット３０２２とを有する。
【００５９】
計算ユニット３０３は、上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成され、ここで、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が滞在ポイントのより高い信頼レベルを示す。
【００６０】
任意的には、図３又は図４に示される実施例に基づき、計算ユニット３０３は、
各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するよう構成される取得サブユニットと、
式
【数４】
2016537718.tif 000006
を用いることによって、且つ、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントのものであって、上記の取得サブユニットにより取得される移動状態に従って、上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成される計算サブユニットとを有し、ここで、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、ここで、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は移動状態のより大きな信頼レベルウェイトを示す。
【００６１】
任意的には、上記の取得サブユニットは、具体的には、上記のユーザの端末におけるセンサデータ（加速度及びジャイロスコープなど）、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、上記の位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得するよう構成される。
【００６２】
フィルタリングユニット３０４は、上記の滞在ポイントセットにおける各滞在ポイントのものであって、計算ユニット３０３により計算される信頼レベルに従ってスクリーニング手段によって上記の滞在ポイントセットから信頼される滞在ポイントを取得するよう構成され、ここで、上記の信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい。
【００６３】
クラスタリングユニット３０５は、関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするよう構成され、ここで、“密度接続”とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す。
【００６４】
任意的には、クラスタリングユニット３０５は更に、関心ポイントを形成するため全ての密度接続される信頼される滞在ポイントをクラスタリングし、関心ポイントのエリアとして、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアを決定するよう構成され、中心がリーフ滞在ポイントである所定の半径カバレッジ範囲内の全ての滞在ポイントの信頼レベルの和は所定の閾値より大きくない。
【００６５】
本発明の本実施例における関心ポイントのクラスタリング装置は、端末（携帯電話、タブレット、ノートブックコンピュータ、デスクトップコンピュータ、又は位置決め機能を有する他の端末など）であってもよいし、又は、関心ポイントのクラスタリング装置は、端末から独立し、ここに限定されない有線又は無線方式で端末と通信可能である装置であってもよい。
【００６６】
本発明の本実施例における関心ポイントのクラスタリング装置は、上記の方法の実施例における関心ポイントのクラスタリング装置であってもよく、上記の方法の実施例における全ての技術的解決策を実現するよう構成可能であることが留意されるべきである。関心ポイントのクラスタリング装置の各機能モジュールの機能は、具体的には、上記の方法の実施例において説明される方法に従って実現されてもよい。特定の実現処理について、上記の実施例における関連する説明が参照されてもよく、詳細はここでは再説明されない。
【００６７】
本発明の本実施例では、１つの滞在ポイントが位置決め精度及び時間閾値により複数の位置決めポイントによって形成され、大部分の待ち合わせポイント、位置決めジャンプポイント及び通過ポイントが、位置決め精度及び時間閾値の制約の下でフィルタリング可能であることが、上記から知ることができる。さらに、滞在ポイントの信頼レベルは、滞在ポイントの位置決めポイントの移動状態を参照して計算され、信頼レベルが相対的に低い滞在ポイントが滞在ポイントの信頼レベルに従って選抜され、いくつかの途中のノイズ滞在ポイント（交通渋滞部分における滞在時、信号機の待ち時間及びゆっくり歩行している時間に生成された擬似滞在ポイントなど）が更にフィルタリングできる。従って、密度接続される信頼される滞在ポイントをクラスタリングすることによって最終的に形成される関心ポイントは、より高い信頼性及びより高い参照値を有する。
【００６８】
本発明の実施例は更にコンピュータ記憶媒体を提供し、ここで、コンピュータ記憶媒体はプログラムを記憶し、当該プログラムは上記の方法の実施例に記録されるステップの一部又は全てを実行する。
【００６９】
以下は、本発明の本実施例において提供され、ピア・ツー・ピアネットワークに適用される他の装置を説明する。図５を参照して、本発明の本実施例における関心ポイントのクラスタリング装置５００は、入力装置５０１、出力装置５０２、メモリ５０３及びプロセッサ５０４（関心ポイントのクラスタリング装置５００には１つ以上のプロセッサ５０４があってもよく、１つのプロセッサは図５における具体例として使用される）を有する。本発明のいくつかの実施例では、入力装置５０１、出力装置５０２、メモリ５０３及びプロセッサ５０４は、バスを使用することによって、又は他の方式で接続されてもよい。図５において、バス接続が具体例として利用される。メモリ５０３は、入力装置５０１により入力されるデータを記憶するよう構成され、プロセッサ５０４によるデータ処理のため必要なファイルなどの情報を更に記憶してもよい。入力装置５０１と出力装置５０２との双方は、他の装置と通信するため関心ポイントのクラスタリング装置５００により用いられるポートを有してもよく、ディスプレイ、キーボード、マウス及びプリンタなど、関心ポイントのクラスタリング装置５００に接続される外部の出力装置を更に有してもよい。具体的には、入力装置５０１は、マウス、キーボードなどを有してもよく、出力装置５０２は、ディスプレイなどを有してもよい。本発明の本実施例では、入力装置５０１と出力装置５０２との双方にあって、他の装置と通信するためのポートは、アンテナ及び／又は通信ケーブルである。
【００７０】
プロセッサ５０４は、以下のステップ、
所定の期間内にユーザの位置決めポイントセットを取得するステップと、
上記の位置決めポイントセットに従って滞在ポイントセットを生成するステップであって、ここで、上記の滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、上記のホットエリアは以下の条件、上記のホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が上記の２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、上記のホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する、生成するステップと、
上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップであって、ここで、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が滞在ポイントのより高い信頼レベルを示す、計算するステップと、
上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルに従ってスクリーニング手段によって上記の滞在ポイントセットから信頼される滞在ポイントを取得するステップであって、ここで、上記の信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい、取得するステップと、
関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするステップであって、ここで、上記の“密度接続”とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す、クラスタリングするステップと、
を実行する。
【００７１】
任意的には、位置決めポイントは経度値及び緯度値により表されるＧＰＳ位置ポイントであり、プロセッサ５０４は、ユーザのＧＰＳ位置データから所定の期間内のユーザの位置決めポイントセットを取得するよう構成される。
【００７２】
任意的には、上記の条件を充足するホットエリアを決定した後、プロセッサ５０４は、上記のホットエリアを表す滞在ポイントとして上記のホットエリアの幾何学的中心ポイントを決定し、ここで、滞在ポイントは、ホットエリアにおける全ての位置決めポイントを表してもよい。おそらく、他の方式がまたホットエリアに対応する滞在ポイントを決定するのに利用されてもよい。例えば、ホットエリアの重心がホットエリアを表す滞在ポイントして使用され、ここで、ホットエリアの重心は、ホットエリア内の位置決めポイントの分布に関連する。
【００７３】
任意的には、プロセッサ５０４は、上記の滞在ポイントセットにおける各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得し、上記の滞在ポイントセットにおける各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態に従って、式
【数５】
2016537718.tif 000007
を用いることによって、上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算し、ここで、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、ここで、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は移動状態のより大きな信頼レベルウェイトを示す。例えば、ユーザの可能な移動状態は静止、歩行又は走行であり、このとき、３つの移動状態について、移動状態に対応し、昇順である移動速度は、順に以下のように静止、歩行又は走行であるため、移動状態のものであって、降順である信頼レベルウェイトは、順に以下のように静止、歩行又は走行であると仮定される。
【００７４】
任意的には、プロセッサ５０４は、上記のユーザの端末におけるセンサデータ（加速度及びジャイロスコープなど）、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、上記の位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得するか、又は、関心ポイントのクラスタリング装置は、ここに限定されない、他の位置決め装置（サーバなど）から上記の滞在ポイントセットにおける全ての位置決めポイントの移動状態を取得してもよい。
【００７５】
任意的には、プロセッサ５０４は、ＰＯＩを形成するため全ての密度接続される信頼される滞在ポイントをクラスタリングし、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアがＰＯＩのエリアであると判断するか、又は、ここに限定されず、ＰＯＩのエリアは、全ての密度接続される信頼される滞在ポイントを含む最小の円形エリア又は正方形エリアであってもよい。
【００７６】
本発明の本実施例における関心ポイントのクラスタリング装置は、端末（携帯電話、タブレット、ノートブックコンピュータ、デスクトップコンピュータ、又は位置決め機能を有する他の端末など）であってもよいし、又は、関心ポイントのクラスタリング装置は、端末から独立し、ここに限定されない有線又は無線方式で端末と通信可能である装置であってもよい。
【００７７】
本発明の本実施例における関心ポイントのクラスタリング装置は、上記の方法の実施例における関心ポイントのクラスタリング装置であってもよく、上記の方法の実施例における全ての技術的解決策を実現するよう構成可能であることが留意されるべきである。関心ポイントのクラスタリング装置の各機能モジュールの機能は、具体的には、上記の方法の実施例において説明される方法に従って実現されてもよい。特定の実現処理について、上記の実施例における関連する説明が参照されてもよく、詳細はここでは再説明されない。
【００７８】
本発明の本実施例では、１つの滞在ポイントが位置決め精度及び時間閾値により複数の位置決めポイントによって形成され、大部分の待ち合わせポイント、位置決めジャンプポイント及び通過ポイントが、位置決め精度及び時間閾値の制約の下でフィルタリング可能であることが、上記から知ることができる。さらに、滞在ポイントの信頼レベルは、滞在ポイントの位置決めポイントの移動状態を参照して計算され、信頼レベルが相対的に低い滞在ポイントが滞在ポイントの信頼レベルに従って選抜され、いくつかの途中のノイズ滞在ポイント（交通渋滞部分における滞在時、信号機の待ち時間及びゆっくり歩行している時間に生成された擬似滞在ポイントなど）が更にフィルタリングできる。従って、密度接続される信頼される滞在ポイントをクラスタリングすることによって最終的に形成される関心ポイントは、より高い信頼性及びより高い参照値を有する。
【００７９】
簡潔な説明のため、上記の方法の実施例はアクションの系列として表されていることが留意されるべきである。しかしながら、本発明によると、いくつかのステップは他の順序で又は同時に実行されてもよいため、当業者は、本発明が説明されたアクションの順序に限定されないことを理解すべきである。上記の実施例では、各実施例の説明は各自の焦点を有する。実施例において詳細に説明されていない部分について、他の実施例における関連する説明が参照されてもよい。
【００８０】
本出願において提供される複数の実施例では、開示された装置及び方法は他の方式で実現されてもよいことが理解されるべきである。例えば、説明される装置の実施例は単なる一例である。例えば、ユニットの分割は単なる論理機能の分割であり、実施例の実現形態では他の分割であってもよい。例えば、複数のユニット又はコンポーネントが他のシステムに合成又は統合されてもよいし、又は、一部の特徴は無視されてもよいし、あるいは実行されなくてもよい。さらに、表示又は説明される相互結合又は直接的な結合若しくは通信接続は、いくつかのインタフェースを用いることによって実現されてもよい。装置又はユニットの間の間接的な結合又は通信接続は、電子、機械又は他の形態により実現されてもよい。
【００８１】
個別のパーツとして説明されるユニットは物理的に別のものであっても又はなくてもよく、ユニットとして表示されるパーツは物理的なユニットであっても又はなくてもよく、１つの位置に配置されてもよく、又は複数のネットワークユニット上で分散されてもよい。ユニットの一部又は全ては、実施例の解決策の課題を実現するため実際のニーズに従って選択されてもよい。
【００８２】
さらに、本発明の実施例における機能ユニットは１つの処理ユニットに一体化されてもよいし、又は、各ユニットは物理的に単独で存在してもよく、又は２つ以上のユニットが１つのユニットに統合される。統合されたユニットは、ハードウェアの形式で実現されてもよいし、又はソフトウェア機能ユニットの形式で実現されてもよい。
【００８３】
統合されたユニットがソフトウェア機能ユニットの形式で実現され、独立した製品として販売又は使用されるとき、統合されたユニットは、コンピュータ可読記憶媒体に記憶されてもよい。このような理解に基づき、実質的に本発明の技術的解決策又は従来技術に貢献する部分、又は技術的解決策の全て若しくは一部は、ソフトウェアプロダクトの形式で実現されてもよい。ソフトウェアプロダクトは、記憶媒体に記憶され、本発明の実施例において説明される方法のステップの全て又は一部を実行するようコンピュータ装置（パーソナルコンピュータ、サーバ又はネットワーク装置であってもよい）に命令するための複数の命令を有する。上記の記憶媒体は、ＵＳＢフラッシュドライブ、着脱可能なハードディスク、読み出し専用メモリ（ＲＯＭ，Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ランダム・アクセス・メモリ（ＲＡＭ，Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、磁気ディスク又は光ディスクなどのプログラムコードを記憶可能な何れかの媒体を含む。
【００８４】
上記は、本発明において提供される関心ポイントのクラスタリング方法及び関連する装置を詳細に説明した。当業者は、本発明のアイデアに基づき、特定の実現方式及び適用範囲に関して修正を行ってもよい。従って、本明細書のコンテンツは本発明に対する限定として解釈されるものでない。
【図１】
2016537718.tif 000010
【図２ａ】
2016537718.tif 000011
【図２ｂ】
2016537718.tif 000012
【図２ｃ】
2016537718.tif 000013
【図２ｄ】
2016537718.tif 000014
【図３】
2016537718.tif 000015
【図４】
2016537718.tif 000016
【図５】
2016537718.tif 000017
【手続補正書】
【提出日】平成28年6月28日(2016.6.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
関心ポイントのクラスタリング方法であって、
所定の期間内にユーザの位置決めポイントセットを取得するステップと、
前記位置決めポイントセットに従って滞在ポイントセットを生成するステップであって、前記滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、前記ホットエリアは以下の条件、前記ホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が前記２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、前記ホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する、生成するステップと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップであって、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が前記滞在ポイントのより高い信頼レベルを示す、計算するステップと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルに従ってスクリーニング手段によって前記滞在ポイントセットから信頼される滞在ポイントを取得するステップであって、前記信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい、取得するステップと、
関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするステップであって、前記密度接続とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す、クラスタリングするステップと、
を有する方法。
【請求項２】
前記位置決めポイントセットに従って滞在ポイントセットを生成するステップは、
前記条件を充足するホットエリアを決定するステップと、
前記ホットエリアを表す滞在ポイントとして前記ホットエリアの幾何学的中心ポイントを決定するステップと、
を有する、請求項１記載の方法。
【請求項３】
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップは、
各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するステップと、
式
【数６】
2016537718.tif 000018
を用いることによって、且つ、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態に従って、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップであって、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは前記滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は前記移動状態のより大きな信頼レベルウェイトを示す、計算するステップと、
を有する、請求項１又は２記載の方法。
【請求項４】
前記各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するステップは、
前記ユーザの端末におけるセンサデータ、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、前記各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得することである、請求項３記載の方法。
【請求項５】
前記関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするステップは、
関心ポイントのエリアとして、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアを決定するステップであって、中心がリーフ滞在ポイントである所定の半径カバレッジ範囲内の全ての滞在ポイントの信頼レベルの和は所定の閾値より大きくない、決定するステップを有する、請求項１乃至４何れか一項記載の方法。
【請求項６】
関心ポイントのクラスタリング装置であって、
所定の期間内にユーザの位置決めポイントセットを取得するよう構成される取得ユニットと、
前記取得ユニットにより取得された前記位置決めポイントセットに従って滞在ポイントセットを生成するよう構成される滞在ポイント生成ユニットであって、前記滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、前記ホットエリアは以下の条件、前記ホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が前記２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、前記ホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する、滞在ポイント生成ユニットと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成される計算ユニットであって、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が前記滞在ポイントのより高い信頼レベルを示す、計算ユニットと、
前記滞在ポイントセットにおける各滞在ポイントのものであって、前記計算ユニットにより計算される信頼レベルに従ってスクリーニング手段によって前記滞在ポイントセットから信頼される滞在ポイントを取得するよう構成されるフィルタリングユニットであって、前記信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい、フィルタリングユニットと、
関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするよう構成されるクラスタリングユニットであって、前記密度接続とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す、クラスタリングユニットと、
を有するクラスタリング装置。
【請求項７】
前記滞在ポイント生成ユニットは、
前記条件を充足するホットエリアを決定するよう構成される第１の決定ユニットと、
前記ホットエリアを表す滞在ポイントとして前記ホットエリアの幾何学的中心ポイントを決定するよう構成される第２の決定ユニットと、
を有する、請求項６記載の関心ポイントのクラスタリング装置。
【請求項８】
前記計算ユニットは、
各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するよう構成される取得サブユニットと、
式
【数７】
2016537718.tif 000019
を用いることによって、且つ、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントのものであって、前記取得サブユニットにより取得される移動状態に従って、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成される計算サブユニットであって、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは前記滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は前記移動状態のより大きな信頼レベルウェイトを示す、計算サブユニットと、
を有する、請求項６又は７記載の関心ポイントのクラスタリング装置。
【請求項９】
前記取得サブユニットは、
前記ユーザの端末におけるセンサデータ、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するよう構成される、請求項８記載の関心ポイントのクラスタリング装置。
【請求項１０】
前記クラスタリングユニットは、
関心ポイントを形成するため全ての密度接続される信頼される滞在ポイントをクラスタリングし、関心ポイントのエリアとして、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアを決定するよう構成され、中心がリーフ滞在ポイントである所定の半径カバレッジ範囲内の全ての滞在ポイントの信頼レベルの和は所定の閾値より大きくない、請求項６乃至９何れか一項記載の関心ポイントのクラスタリング装置。
【請求項１１】
請求項１乃至５何れか一項記載の方法をコンピュータに実行させるためのプログラム。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、地理情報処理技術の分野に関し、特に関心ポイントのクラスタリング方法及び関連する装置に関する。
【背景技術】
【０００２】
関心ポイント（ＰＯＩ，Ｐｏｉｎｔ  Ｏｆ  Ｉｎｔｅｒｅｓｔ）は、例えば、自宅、オフィス又は頻繁に訪れるスーパーマーケットなど、ユーザにとって非常に重要なエリアなど、ユーザが長時間頻繁に滞在する位置エリアを表す。
【０００３】
ユーザの日常行動の追跡情報は、携帯電話などの端末のＷｉ−Ｆｉネットワーク、グローバル・ポジショニング・システム（ＧＰＳ，Ｇｌｏｂａｌ  Ｐｏｓｉｔｉｏｎｉｎｇ  Ｓｙｓｔｅｍ）及び基地局識別子（ＩＤ，Ｉｄｅｎｔｉｔｙ）などの位置決め機能を利用することによって取得されてもよい。追跡情報は、位置決めのずれを有する多数の位置決め座標点から構成される。追跡情報からユーザのＰＯＩをどのように抽出するかの研究は、状況認識及び位置ベースサービス（ＬＢＳ，Ｌｏｃａｔｉｏｎ−ｂａｓｅｄ  Ｓｅｒｖｉｃｅ）にとって非常に価値があり、また学術における研究の焦点である。
【０００４】
現在、ユーザの複数のＧＰＳ追跡情報に基づきＰＯＩを探索するための方法があり、当該方法の主要なアイデアは、まずツリー状の階層パターンを用いることによってユーザの複数の履歴位置データをモデル化し、それから、ツリー状の階層パターンに基づき、ハイパーテキストの主題に基づき検索を実行するインタフェースモデルを提案し、ユーザから個別の単一の訪問の位置へのリンクを確立することである。
【０００５】
しかしながら、上記の方法では、ユーザの滞在ポイントは、空間及び時間の次元を利用することによって抽出される。滞在ポイントは、ユーザの単一の訪問のみを表すことができるが、ユーザにとって非常に重要なＰＯＩの場所を表すことはできない。さらに、ＰＯＩが探索されているとき、ユーザの履歴位置データしか参照されず、従って、探索されたＰＯＩの信頼性及び参照値は低い。
【発明の概要】
【０００６】
本発明の実施例は、ＰＯＩの信頼性及び参照値を改善するため利用される関心ポイントのクラスタリング方法及び関連する装置を提供する。
【０００７】
本発明の第１の態様は、関心ポイントのクラスタリング方法を提供し、ここで、当該方法は、
所定の期間内にユーザの位置決めポイントセットを取得するステップと、
前記位置決めポイントセットに従って滞在ポイントセットを生成するステップであって、前記滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、前記ホットエリアは以下の条件、前記ホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が前記２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、前記ホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する、生成するステップと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップであって、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が前記滞在ポイントのより高い信頼レベルを示す、計算するステップと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルに従ってスクリーニング手段によって前記滞在ポイントセットから信頼される滞在ポイントを取得するステップであって、前記信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい、取得するステップと、
関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするステップであって、前記密度接続とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す、クラスタリングするステップと、
を有する。
【０００８】
本発明の第１の態様に基づき、第１の可能な実現方式では、
前記位置決めポイントセットに従って滞在ポイントセットを生成するステップは、
前記条件を充足するホットエリアを決定するステップと、
前記ホットエリアを表す滞在ポイントとして前記ホットエリアの幾何学的中心ポイントを決定するステップと、
を有する。
【０００９】
本発明の第１の態様又は本発明の第１の態様の第１の可能な実現方式に基づき、第２の可能な実現方式では、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップは、
各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するステップと、
式
【数１】
2016537718.tif 000020
を用いることによって、且つ、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態に従って、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップであって、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは前記滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は前記移動状態のより大きな信頼レベルウェイトを示す、計算するステップと、
を有する。
【００１０】
本発明の第１の態様の第２の可能な実現方式に基づき、第３の可能な実現方式では、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するステップは、具体的には、
前記ユーザの端末におけるセンサデータ、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、前記位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得することである。
【００１１】
第１の態様、又は本発明の第１の態様の第１の可能な実現方式、又は本発明の第１の態様の第２の可能な実現方式、又は本発明の第１の態様の第３の可能な実現方式に基づき、第４の可能な実現方式では、前記関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするステップは、
関心ポイントのエリアとして、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアを決定するステップであって、中心がリーフ滞在ポイントである所定の半径カバレッジ範囲内の全ての滞在ポイントの信頼レベルの和は所定の閾値より大きくない、決定するステップを有する。
【００１２】
本発明の第２の態様は、関心ポイントのクラスタリング装置を提供し、ここで、当該装置は、
所定の期間内にユーザの位置決めポイントセットを取得するよう構成される取得ユニットと、
前記取得ユニットにより取得された前記位置決めポイントセットに従って滞在ポイントセットを生成するよう構成される滞在ポイント生成ユニットであって、前記滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、前記ホットエリアは以下の条件、前記ホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が前記２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、前記ホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する、滞在ポイント生成ユニットと、
前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成される計算ユニットであって、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が前記滞在ポイントのより高い信頼レベルを示す、計算ユニットと、
前記滞在ポイントセットにおける各滞在ポイントのものであって、前記計算ユニットにより計算される信頼レベルに従ってスクリーニング手段によって前記滞在ポイントセットから信頼される滞在ポイントを取得するよう構成されるフィルタリングユニットであって、前記信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい、フィルタリングユニットと、
関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするよう構成されるクラスタリングユニットであって、前記“密度接続”とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が直接的に接続されるか、又は間接的に接続されることを示す、クラスタリングユニットと、
を有する。
【００１３】
本発明の第２の態様に基づき、第１の可能な実現方式では、
前記滞在ポイント生成ユニットは、
前記条件を充足するホットエリアを決定するよう構成される第１の決定ユニットと、
前記ホットエリアを表す滞在ポイントとして前記ホットエリアの幾何学的中心ポイントを決定するよう構成される第２の決定ユニットと、
を有する。
【００１４】
本発明の第２の態様又は本発明の第２の態様の第１の可能な実現方式に基づき、第２の可能な実現方式では、
前記計算ユニットは、
各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するよう構成される取得サブユニットと、
式
【数２】
2016537718.tif 000021
を用いることによって、且つ、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントのものであって、前記取得サブユニットにより取得される移動状態に従って、前記滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成される計算サブユニットであって、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは前記滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は前記移動状態のより大きな信頼レベルウェイトを示す、計算サブユニットと、
を有する。
【００１５】
本発明の第２の態様の第２の可能な実現方式に基づき、第３の可能な実現方式では、前記取得サブユニットは、具体的には、前記ユーザの端末におけるセンサデータ、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するよう構成される。
【００１６】
本発明の第２の態様、又は本発明の第２の態様の第１の可能な実現方式、又は本発明の第２の態様の第２の可能な実現方式、又は本発明の第２の態様の第３の可能な実現方式に基づき、第４の可能な実現方式では、前記クラスタリングユニットは、具体的には、関心ポイントを形成するため全ての密度接続される信頼される滞在ポイントをクラスタリングし、関心ポイントのエリアとして、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアを決定するよう構成され、中心がリーフ滞在ポイントである所定の半径カバレッジ範囲内の全ての滞在ポイントの信頼レベルの和は所定の閾値より大きくない。
【００１７】
本発明の実施例が以下の効果を有することは、上記の技術的解決策から知ることができる。
【００１８】
本発明の実施例では、１つの滞在ポイントが位置決め精度及び時間閾値に従って複数の位置決めポイントによって形成され、大部分の待ち合わせポイント、位置決めジャンプポイント及び通過ポイントが、位置決め精度及び時間閾値の制約の下でフィルタリング可能であることが知ることができる。さらに、滞在ポイントの信頼レベルは、滞在ポイントの位置決めポイントの移動状態を参照して計算され、信頼レベルが相対的に低い滞在ポイントが滞在ポイントの信頼レベルに従って選抜され、いくつかの途中のノイズ滞在ポイント（交通渋滞部分における滞在時、信号機の待ち時間及びゆっくり歩行している時間に生成された擬似滞在ポイントなど）が更にフィルタリングできる。従って、密度接続される信頼される滞在ポイントをクラスタリングすることによって最終的に形成される関心ポイントは、より高い信頼性及びより高い参照値を有する。
【図面の簡単な説明】
【００１９】
本発明の実施例又は従来技術における技術的解決策をより明確に説明するため、以下は、実施例又は従来技術を説明するのに必要な添付図面を簡単に紹介する。明らかに、以下の説明における添付図面は本発明のいくつかの実施例を単に示し、当業者は、創作的な努力なく、これらの添付図面から他の図面を依然として導出してもよい。
【図１】図１は、本発明による関心ポイントのクラスタリング方法の実施例の概略的なフローチャートである。
【図２ａ】図２ａは、本発明による適用シナリオにおける位置決めポイントセットの追跡の概略図である。
【図２ｂ】図２ｂは、本発明による適用シナリオにおいて形成される滞在ポイントセットの概略図である。
【図２ｃ】図２ｃは、本発明による適用シナリオにおいてスクリーニング手段によって取得される信頼される滞在ポイントセットの概略図である。
【図２ｄ】図２ｄは、本発明による適用シナリオにおいてクラスタリング手段により取得されるＰＯＩの概略図である。
【図３】図３は、本発明による関心ポイントのクラスタリング装置の実施例の概略的な構成図である。
【図４】図４は、本発明による関心ポイントのクラスタリング装置の他の実施例の概略的な構成図である。
【図５】図５は、本発明による関心ポイントのクラスタリング装置の更なる他の実施例の概略的な構成図である。
【発明を実施するための形態】
【００２０】
本発明の実施例は、関心ポイントのクラスタリング方法及び関連する装置を提供する。
【００２１】
本発明の課題、特徴及び効果をより明確且つより理解可能にするため、以下は、本発明の実施例における添付図面を参照して、本発明の実施例における技術的解決策を明確且つ完全に説明する。明らかに、説明される実施例は、本発明の実施例の全てでなく単なる一部である。創作的な努力なく本発明の実施例に基づき当業者により取得される他の全ての実施例は、本発明の保護範囲内に属する。
【００２２】
以下は、本発明の実施例において提供される関心ポイントのクラスタリング方法を説明する。図１を参照して、本発明の本実施例における関心ポイントのクラスタリング方法は、以下を含む。
【００２３】
１０１．所定の期間内にユーザの位置決めポイントセットを取得する。
【００２４】
本発明の本実施例における位置決めポイントセットは１つ以上の位置決めポイントを有し、位置決めポイントはユーザの位置情報を示すのに利用される。
【００２５】
任意的には、位置決めポイントは、経度値及び緯度値によって表されるＧＰＳ位置ポイントであり、関心ポイントのクラスタリング装置は、ユーザのＧＰＳ位置データから所定の期間内にユーザの位置決めポイントセットを取得する。
【００２６】
１０２．上記の位置決めポイントセットに従って滞在ポイントセットを生成する。
【００２７】
上記の滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、ここで、上記のホットエリアは、以下の条件、上記のホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が上記の２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、上記のホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する。
【００２８】
例えば、位置決めポイントセット｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝は、滞在ポイントが形成されうるホットエリアを構成し、位置決めポイントセット｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝は、以下の２つの条件を充足する必要がある。
【００２９】
１．｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝における何れか２つの位置決めポイントの地理的位置の間の距離は空間閾値Ｄｔｈ未満であり、ここで、Ｄｔｈは固定値でなく、それは関連する位置決めポイントが変わるに従って変化し、具体的には、２つの位置決めポイントの位置決め精度における最大値、すなわち、Ｄｔｈ（Ｐｎ，Ｐｍ）＝ｍａｘ（Ｒａｄｉｕｓ（Ｐｎ），Ｒａｄｉｕｓ（Ｐｍ））である。例えば、位置決めポイントＰ１の位置決め精度は５メータであり、位置決めポイントＰ２の位置決め精度は１０メータであり、このとき、位置決めポイントＰ１及び位置決めポイントＰ２について、Ｄｔｈ（Ｐ１，Ｐ２）は位置決めポイントＰ１及び位置決めポイントＰ２の位置決め精度においてより高い位置決め精度に等しく、すなわち、Ｄｔｈ（Ｐ１，Ｐ２）は１０メータに等しいと仮定される。位置決めポイントＰ３の位置決め精度が１５メータである場合、位置決めポイントＰ１及び位置決めポイントＰ３について、Ｄｔｈ（Ｐ１，Ｐ３）は位置決めポイントＰ１及び位置決めポイントＰ３の位置決め精度におけるより高い位置決め精度に等しく、すなわち、Ｄｔｈ（Ｐ１，Ｐ２）は１５メータに等しい。
【００３０】
２．異なる位置決めポイントが異なる時点で測定手段により取得されるため、全ての２つの位置決めポイントの間に時間間隔が存在する。例えば、位置決めポイントＰ１は１０：００に測定手段により取得され、位置決めポイントＰ２は１０：０３に測定手段により取得され、このとき、位置決めポイントＰ１と位置決めポイントＰ２との間の時間間隔は３分であると仮定される。本発明の本実施例では、｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝は更に、以下の条件、｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝における位置決めポイントの間の時間間隔の最大値が所定の時間閾値Ｔｔｈ（例えば、Ｔｔｈの値は５分、７分又は１０分であってもよい）より大きく、すなわち、｛Ｐｊ，Ｐｊ＋１，．．．，Ｐｊ＋Ｌ｝において、測定手段により最初に取得された位置決めポイントと、測定手段により最後に取得された位置決めポイントとの間の時間間隔はＴｔｈより大きく、ここで、Ｔｔｈは、ここで限定されない、実際の要求に従って具体的に設定されてもよい、を充足する必要がある。
【００３１】
任意的には、上記の条件を充足するホットエリアが決定された後、上記のホットエリアの幾何学的中心ポイントは、上記のホットエリアを表す滞在ポイントとして決定され、ここで、滞在ポイントは、ホットエリアにおける全ての位置決めポイントを表すものであってもよい。おそらく、他の方式がまたホットエリアに対応する滞在ポイントを決定するのに利用されてもよい。例えば、ホットエリアの重心が、ホットエリアを表す滞在ポイントとして利用され、ここで、ホットエリアの重心は、ホットエリア内の位置決めポイントの分布に関連する。
【００３２】
１０３．上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算する。
【００３３】
滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が滞在ポイントのより高い信頼レベルを示す。
【００３４】
実現方式では、関心ポイントのクラスタリング装置は、上記の滞在ポイントセットにおける各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得し、上記の滞在ポイントセットにおける各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態に従って、式
【数３】
2016537718.tif 000022
を用いることによって、上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算し、ここで、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、ここで、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は移動状態のより大きな信頼レベルウェイトを示す。例えば、ユーザの可能な移動状態は、静止、歩行及び走行であり、このとき、３つの移動状態について、移動状態に対応し、昇順である移動速度は順に以下のように、静止、歩行及び走行であり、移動状態のものであって、降順である信頼レベルウェイトは順に以下のように、静止、歩行又は走行であると仮定される。
【００３５】
任意的には、関心ポイントのクラスタリング装置は、上記のユーザの端末（携帯電話、タブレット及び車両搭載端末など）におけるセンサデータ（加速度及びジャイロスコープから取得されるデータなど）、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、上記の位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得するか、又は、関心ポイントのクラスタリング装置は、ここに限定されず、他の位置決め装置（サーバなど）から各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得してもよい。
【００３６】
１０４．上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルに従ってスクリーニング手段によって上記の滞在ポイントセットから信頼される滞在ポイントを取得する。
【００３７】
上記の信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい。
【００３８】
本発明の本実施例では、関心ポイントのクラスタリング装置は、スクリーニング手段により上記の滞在ポイントセットから信頼される滞在ポイント（すなわち、信頼レベルが所定の信頼レベル閾値より大きい滞在ポイント）を取得し、信頼レベルが所定の信頼レベル閾値より大きくない滞在ポイントを削除する。
【００３９】
１０５．ＰＯＩを形成するため、密度接続される信頼される滞在ポイントをクラスタリングする。
【００４０】
上記の“密度接続”とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す。例えば、信頼される滞在ポイントＰ１のカバレッジ範囲は信頼される滞在ポイントＰ２のカバレッジ範囲と交わり、それから、信頼される滞在ポイントＰ１及び信頼される滞在ポイントＰ２により表されるホットエリアの範囲は、互いに直接的に接続されると仮定される。この場合、信頼される滞在ポイントＰ１及び信頼される滞在ポイントＰ２は密度接続される。あるいは、信頼される滞在ポイントＰ１のカバレッジ範囲が信頼される滞在ポイントＰ３のカバレッジ範囲と交わり、信頼される滞在ポイントＰ２のカバレッジ範囲が信頼される滞在ポイントＰ４のカバレッジ範囲と交わり、信頼される滞在ポイントＰ３のカバレッジ範囲が信頼される滞在ポイントＰ４のカバレッジ範囲と交わり、このとき、信頼される滞在ポイントＰ１及び信頼される滞在ポイントＰ２により表されるホットエリアの範囲は、互いに間接的に接続されると仮定される。この場合、信頼される滞在ポイントＰ１及び信頼される滞在ポイントＰ２はまた密度接続される。
【００４１】
任意的には、信頼される滞在ポイントＰ１（リーフ滞在ポイントであってもよいし、又は内部滞在ポイントであってもよい）が内部滞在ポイントｏから密度到達可能であり、信頼される滞在ポイントＰ２（リーフ滞在ポイントであってもよいし、又は内部滞在ポイントであってもよい）が内部滞在ポイントｏから密度到達可能である場合、信頼される滞在ポイントＰ１及び信頼される滞在ポイントＰ２は密度接続される。以下は、“内部滞在ポイント”、“リーフ滞在ポイント”及び“密度到達可能”を説明する。
【００４２】
内部滞在ポイント：中心が滞在ポイントである所定の半径カバレッジ内の全ての滞在ポイントの信頼されるレベルの和が、所定の閾値より大きい。
【００４３】
リーフ滞在ポイント：中心が滞在ポイントである所定の半径カバレッジ内の全ての滞在ポイントの信頼されるレベルの和が、所定の閾値より大きくない。
【００４４】
密度到達可能：ｐｉ（０＜ｉ＜ｎ）が内部滞在ポイントである必要がある信頼される滞在ポイントｐ１，ｐ２，．．．，ｐｎの所与の系列において、ｐｎはリーフ滞在ポイント又は内部滞在ポイントであってもよく、Ｐ＝ｐｉ及びＱ＝ｐｎであり、ｐｉはｐｉ−１（１＜ｉ＜（ｎ＋１））から直接的に密度到達可能であり、このとき、滞在ポイントＱは内部滞在ポイントＰから密度到達可能であると仮定される。
【００４５】
直接的に密度到達可能：信頼される滞在ポイントＰ（リーフ滞在ポイントであってもよいし、又は内部滞在ポイントであってもよい）が信頼される滞在ポイントＱの半径カバレッジ内に配置され、信頼される滞在ポイントＱが内部滞在ポイントである場合、信頼される滞在ポイントＰは、信頼される滞在ポイントＱから直接的に密度到達可能である。
【００４６】
任意的には、全ての密度接続される信頼される滞在ポイントは、ＰＯＩを形成するためクラスタリングされる。さらに、ＰＯＩのエリアとして全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリア、又はＰＯＩのエリアは、ここに限定されない、全ての密度接続される信頼される滞在ポイントを含む最小の円形エリア又は正方形エリアであってもよい。
【００４７】
本発明の本実施例では、１つの滞在ポイントが位置決め精度及び時間閾値により複数の位置決めポイントによって形成され、大部分の待ち合わせポイント、位置決めジャンプポイント及び通過ポイントが、位置決め精度及び時間閾値の制約の下でフィルタリング可能であることが、上記から知ることができる。さらに、滞在ポイントの信頼レベルは、滞在ポイントの位置決めポイントの移動状態を参照して計算され、信頼レベルが相対的に低い滞在ポイントが滞在ポイントの信頼レベルに従って選抜され、いくつかの途中のノイズ滞在ポイント（交通渋滞部分における滞在時、信号機の待ち時間及びゆっくり歩行している時間に生成された擬似滞在ポイントなど）が更にフィルタリングできる。従って、密度接続される信頼される滞在ポイントをクラスタリングすることによって最終的に形成される関心ポイントは、より高い信頼性及びより高い参照値を有する。
【００４８】
本発明の技術的解決策のより良好な理解のため、以下は、特定の適用シナリオを利用することによって、本発明の本実施例における関心ポイントのクラスタリング方法を説明する。
【００４９】
図２ａにおいて、所定の期間内のユーザの位置決めポイントセットの追跡が示されることが仮定される。
【００５０】
ステップ１：関心ポイントのクラスタリング装置は、図２ａに示される位置決めポイントセットから、動的な空間閾値及び時間閾値を用いることによって、以下の２つ条件を充足するホットエリアを決定し、１．ホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が上記の２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、２．ホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きく、これらの条件を充足するホットエリアを決定した後、ホットエリアを表す滞在ポイントしてホットエリアの幾何学的中心ポイントを決定し、図２ｂに示される滞在ポイントの追跡の図を取得するため、複数の滞在ポイントを形成し、ここで、図２ｂにおける各黒いポイントは形成された滞在ポイントを表し、各滞在ポイントは、ユーザが同じ場所に滞在するときに生成される多数の位置決めポイントを表しうる。図２ｂが図２ａと比較された後、大部分の待ち合わせポイント、位置決めジャンプポイント及び通過ポイントが図２ｂにおいてフィルタリングされることが知ることができる。
【００５１】
ステップ２：関心ポイントのクラスタリング装置は、１つの滞在ポイントを形成する全ての位置決めポイントにおけるユーザの移動状態（静止、歩行及び走行など）に従って、各滞在ポイントの信頼レベルを計算し、ここで、１つの滞在ポイントの全ての位置決めポイントにおけるユーザの移動状態に対応する平均速度がより低い場合、滞在ポイントの信頼レベルはより高くなり、例えば、滞在ポイントを形成する全ての位置決めポイントにおける移動状態が静止（すなわち、移動速度が０）である滞在ポイントの位置決めポイントのパーセンテージがより高い場合、滞在ポイントの信頼レベルはより高く、そうでなく、滞在ポイントを形成する全ての位置決めポイントにおける移動状態が走行（すなわち、移動速度が０よりはるかに大きい）である滞在ポイントの位置決めポイントのパーセンテージがより高い場合、滞在ポイントの信頼レベルはより低く、各滞在ポイントの信頼レベルを計算した後、図２ｂに示される滞在ポイントセットから、信頼レベルが所定の信頼レベル閾値より大きくない滞在ポイントを削除し、すなわち、図２ｂに示される滞在ポイントセットから、スクリーニング手段によって、信頼レベルが所定の信頼レベル閾値より大きい滞在ポイントを取得し、図２ｃに示される信頼される滞在ポイントセットを取得する。図２ｃが図２ｂと比較された後、いくつかの途中のノイズ滞在ポイント（交通渋滞部分における滞在時、信号機の待ち時間及びゆっくり歩行している時間に生成された擬似滞在ポイント）が図２ｃにおいてフィルタリングされることが知ることができる。
【００５２】
ステップ３：信頼レベルに基づき上記の滞在ポイントをクラスタリングし、全ての滞在ポイントが密度接続される最大滞在ポイントセットを特定し（すなわち、当該セットにおける何れか２つの滞在ポイントが密度接続される）、ＰＯＩを形成するため最大滞在ポイントセットにおける滞在ポイントをクラスタリングし、ここで、ＰＯＩのエリアは、クラスタリング手段によって取得され、図２ｄに示されるＰＯＩの概略図など、最大滞在ポイントセットにおける全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドポリゴンを用いることによって表されてもよい。各滞在ポイントの信頼レベルは、ステップ３におけるクラスタリング処理において考慮され、ＰＯＩのクラスタリング信頼性が向上し、ＰＯＩのエリア範囲は実際のケースにおけるエリア範囲により近い。
【００５３】
本発明の実施例は更に、関心ポイントのクラスタリング装置を提供する。図３に示されるように、本発明の本実施例における関心ポイントのクラスタリング装置３００は、取得ユニット３０１、滞在ポイント生成ユニット３０２、計算ユニット３０３、フィルタリングユニット３０４及びクラスタリングユニット３０５を有し、ここで、
【００５４】
取得ユニット３０１は、所定の期間内にユーザの位置決めポイントセットを取得するよう構成される。
【００５５】
本発明の本実施例における位置決めポイントセットは１つ以上の位置決めポイントを有し、位置決めポイントはユーザの位置情報を示すのに利用される。
【００５６】
任意的には、位置決めポイントは経度値及び緯度値により表されるＧＰＳ位置ポイントであり、関心ポイントのクラスタリング装置は、ユーザのＧＰＳ位置データから所定の期間内のユーザの位置決めポイントセットを取得する。
【００５７】
滞在ポイント生成ユニット３０２は、取得ユニット３０１により取得された位置決めポイントセットに従って滞在ポイントセットを生成するよう構成され、ここで、上記の滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、上記のホットエリアは以下の条件、上記のホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が上記の２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、上記のホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する。
【００５８】
任意的には、図３に示される実施例に基づき、図４に示される関心ポイントのクラスタリング装置４００によると、滞在ポイント生成ユニット３０２は、上記の条件を充足するホットエリアを決定するよう構成される第１の決定ユニット３０２１と、上記のホットエリアを表す滞在ポイントとして上記のホットエリアの幾何学的中心ポイントを決定するよう構成される第２の決定ユニット３０２２とを有する。
【００５９】
計算ユニット３０３は、上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成され、ここで、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が滞在ポイントのより高い信頼レベルを示す。
【００６０】
任意的には、図３又は図４に示される実施例に基づき、計算ユニット３０３は、
各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するよう構成される取得サブユニットと、
式
【数４】
2016537718.tif 000023
を用いることによって、且つ、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントのものであって、上記の取得サブユニットにより取得される移動状態に従って、上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するよう構成される計算サブユニットとを有し、ここで、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、ここで、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は移動状態のより大きな信頼レベルウェイトを示す。
【００６１】
任意的には、上記の取得サブユニットは、具体的には、上記のユーザの端末におけるセンサデータ（加速度及びジャイロスコープから取得されたデータなど）、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得するよう構成される。
【００６２】
フィルタリングユニット３０４は、上記の滞在ポイントセットにおける各滞在ポイントのものであって、計算ユニット３０３により計算される信頼レベルに従ってスクリーニング手段によって上記の滞在ポイントセットから信頼される滞在ポイントを取得するよう構成され、ここで、上記の信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい。
【００６３】
クラスタリングユニット３０５は、関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするよう構成され、ここで、“密度接続”とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す。
【００６４】
任意的には、クラスタリングユニット３０５は更に、関心ポイントを形成するため全ての密度接続される信頼される滞在ポイントをクラスタリングし、関心ポイントのエリアとして、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアを決定するよう構成され、中心がリーフ滞在ポイントである所定の半径カバレッジ範囲内の全ての滞在ポイントの信頼レベルの和は所定の閾値より大きくない。
【００６５】
本発明の本実施例における関心ポイントのクラスタリング装置は、端末（携帯電話、タブレット、ノートブックコンピュータ、デスクトップコンピュータ、又は位置決め機能を有する他の端末など）であってもよいし、又は、関心ポイントのクラスタリング装置は、端末から独立し、ここに限定されない有線又は無線方式で端末と通信可能である装置であってもよい。
【００６６】
本発明の本実施例における関心ポイントのクラスタリング装置は、上記の方法の実施例における関心ポイントのクラスタリング装置であってもよく、上記の方法の実施例における全ての技術的解決策を実現するよう構成可能であることが留意されるべきである。関心ポイントのクラスタリング装置の各機能モジュールの機能は、具体的には、上記の方法の実施例において説明される方法に従って実現されてもよい。特定の実現処理について、上記の実施例における関連する説明が参照されてもよく、詳細はここでは再説明されない。
【００６７】
本発明の本実施例では、１つの滞在ポイントが位置決め精度及び時間閾値により複数の位置決めポイントによって形成され、大部分の待ち合わせポイント、位置決めジャンプポイント及び通過ポイントが、位置決め精度及び時間閾値の制約の下でフィルタリング可能であることが、上記から知ることができる。さらに、滞在ポイントの信頼レベルは、滞在ポイントの位置決めポイントの移動状態を参照して計算され、信頼レベルが相対的に低い滞在ポイントが滞在ポイントの信頼レベルに従って選抜され、いくつかの途中のノイズ滞在ポイント（交通渋滞部分における滞在時、信号機の待ち時間及びゆっくり歩行している時間に生成された擬似滞在ポイントなど）が更にフィルタリングできる。従って、密度接続される信頼される滞在ポイントをクラスタリングすることによって最終的に形成される関心ポイントは、より高い信頼性及びより高い参照値を有する。
【００６８】
本発明の実施例は更にコンピュータ記憶媒体を提供し、ここで、コンピュータ記憶媒体はプログラムを記憶し、当該プログラムは上記の方法の実施例に記録されるステップの一部又は全てを実行する。
【００６９】
以下は、本発明の本実施例において提供される他の装置を説明する。図５を参照して、本発明の本実施例における関心ポイントのクラスタリング装置５００は、入力装置５０１、出力装置５０２、メモリ５０３及びプロセッサ５０４（関心ポイントのクラスタリング装置５００には１つ以上のプロセッサ５０４があってもよく、１つのプロセッサは図５における具体例として使用される）を有する。本発明のいくつかの実施例では、入力装置５０１、出力装置５０２、メモリ５０３及びプロセッサ５０４は、バスを使用することによって、又は他の方式で接続されてもよい。図５において、バス接続が具体例として利用される。メモリ５０３は、入力装置５０１により入力されるデータを記憶するよう構成され、プロセッサ５０４によるデータ処理のため必要なファイルなどの情報を更に記憶してもよい。入力装置５０１と出力装置５０２との双方は、他の装置と通信するため関心ポイントのクラスタリング装置５００により用いられるポートを有してもよく、ディスプレイ、キーボード、マウス及びプリンタなど、関心ポイントのクラスタリング装置５００に接続される外部の出力装置を更に有してもよい。具体的には、入力装置５０１は、マウス、キーボードなどを有してもよく、出力装置５０２は、ディスプレイなどを有してもよい。本発明の本実施例では、入力装置５０１と出力装置５０２との双方にあって、他の装置と通信するためのポートは、アンテナ及び／又は通信ケーブルである。
【００７０】
プロセッサ５０４は、以下のステップ、
所定の期間内にユーザの位置決めポイントセットを取得するステップと、
上記の位置決めポイントセットに従って滞在ポイントセットを生成するステップであって、ここで、上記の滞在ポイントセットにおける各滞在ポイントは１つのホットエリアを表し、上記のホットエリアは以下の条件、上記のホットエリアにおける何れか２つの位置決めポイントの地理的位置の間の距離が上記の２つの位置決めポイントの位置決め精度におけるより高い位置決め精度未満であり、且つ、上記のホットエリアにおける位置決めポイントの間の時間間隔の最大値が所定の時間閾値より大きい、を充足する、生成するステップと、
上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算するステップであって、ここで、滞在ポイントにより表されるホットエリアにおける全ての位置決めポイントの移動状態に対応するより低い平均速度が滞在ポイントのより高い信頼レベルを示す、計算するステップと、
上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルに従ってスクリーニング手段によって上記の滞在ポイントセットから信頼される滞在ポイントを取得するステップであって、ここで、上記の信頼される滞在ポイントの信頼レベルは所定の信頼レベル閾値より大きい、取得するステップと、
関心ポイントを形成するため、密度接続される信頼される滞在ポイントをクラスタリングするステップであって、ここで、上記の“密度接続”とは、２つの信頼される滞在ポイントにより表されるホットエリアの範囲が互いに直接的に接続されるか、又は間接的に接続されることを示す、クラスタリングするステップと、
を実行する。
【００７１】
任意的には、位置決めポイントは経度値及び緯度値により表されるＧＰＳ位置ポイントであり、プロセッサ５０４は、ユーザのＧＰＳ位置データから所定の期間内のユーザの位置決めポイントセットを取得するよう構成される。
【００７２】
任意的には、上記の条件を充足するホットエリアを決定した後、プロセッサ５０４は、上記のホットエリアを表す滞在ポイントとして上記のホットエリアの幾何学的中心ポイントを決定し、ここで、滞在ポイントは、ホットエリアにおける全ての位置決めポイントを表してもよい。おそらく、他の方式がまたホットエリアに対応する滞在ポイントを決定するのに利用されてもよい。例えば、ホットエリアの重心がホットエリアを表す滞在ポイントして使用され、ここで、ホットエリアの重心は、ホットエリア内の位置決めポイントの分布に関連する。
【００７３】
任意的には、プロセッサ５０４は、上記の滞在ポイントセットにおける各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得し、上記の滞在ポイントセットにおける各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態に従って、式
【数５】
2016537718.tif 000024
を用いることによって、上記の滞在ポイントセットにおける各滞在ポイントの信頼レベルを計算し、ここで、Ｃｏｎｆｉは滞在ポイントｉの信頼レベルを表し、ｎはｎ個の可能な移動状態を表し、Ｗｋはｋ番目の移動状態の信頼レベルウェイトを表し、ｎｋは滞在ポイントｉにより表されるホットエリアにあって、移動状態がｋ番目の移動状態である位置決めポイントの数を表し、ここで、各移動状態は信頼レベルウェイトに対応し、移動状態に対応するより低い移動速度は移動状態のより大きな信頼レベルウェイトを示す。例えば、ユーザの可能な移動状態は静止、歩行及び走行であり、このとき、３つの移動状態について、移動状態に対応し、昇順である移動速度は、順に以下のように静止、歩行及び走行であるため、移動状態のものであって、降順である信頼レベルウェイトは、順に以下のように静止、歩行又は走行であると仮定される。
【００７４】
任意的には、プロセッサ５０４は、上記のユーザの端末におけるセンサデータ（加速度及びジャイロスコープから取得されるデータなど）、又はＷｉ−Ｆｉネットワークの信号強度の変化又は信号量の変化に従って、上記の位置決めポイントセットにおける全ての位置決めポイントの移動状態を取得するか、又は、プロセッサ５０４は、ここに限定されない、他の位置決め装置（サーバなど）から各滞在ポイントにより表されるホットエリアに含まれる全ての位置決めポイントの移動状態を取得してもよい。
【００７５】
任意的には、プロセッサ５０４は、ＰＯＩを形成するため全ての密度接続される信頼される滞在ポイントをクラスタリングし、全ての密度接続される信頼される滞在ポイントの間の全てのリーフ滞在ポイントを順次接続することによって形成されるクローズドエリアがＰＯＩのエリアであると判断するか、又は、ここに限定されず、ＰＯＩのエリアは、全ての密度接続される信頼される滞在ポイントを含む最小の円形エリア又は正方形エリアであってもよい。
【００７６】
本発明の本実施例における関心ポイントのクラスタリング装置は、端末（携帯電話、タブレット、ノートブックコンピュータ、デスクトップコンピュータ、又は位置決め機能を有する他の端末など）であってもよいし、又は、関心ポイントのクラスタリング装置は、端末から独立し、ここに限定されない有線又は無線方式で端末と通信可能である装置であってもよい。
【００７７】
本発明の本実施例における関心ポイントのクラスタリング装置は、上記の方法の実施例における関心ポイントのクラスタリング装置であってもよく、上記の方法の実施例における全ての技術的解決策を実現するよう構成可能であることが留意されるべきである。関心ポイントのクラスタリング装置の各機能モジュールの機能は、具体的には、上記の方法の実施例において説明される方法に従って実現されてもよい。特定の実現処理について、上記の実施例における関連する説明が参照されてもよく、詳細はここでは再説明されない。
【００７８】
本発明の本実施例では、１つの滞在ポイントが位置決め精度及び時間閾値により複数の位置決めポイントによって形成され、大部分の待ち合わせポイント、位置決めジャンプポイント及び通過ポイントが、位置決め精度及び時間閾値の制約の下でフィルタリング可能であることが、上記から知ることができる。さらに、滞在ポイントの信頼レベルは、滞在ポイントの位置決めポイントの移動状態を参照して計算され、信頼レベルが相対的に低い滞在ポイントが滞在ポイントの信頼レベルに従って選抜され、いくつかの途中のノイズ滞在ポイント（交通渋滞部分における滞在時、信号機の待ち時間及びゆっくり歩行している時間に生成された擬似滞在ポイントなど）が更にフィルタリングできる。従って、密度接続される信頼される滞在ポイントをクラスタリングすることによって最終的に形成される関心ポイントは、より高い信頼性及びより高い参照値を有する。
【００７９】
簡潔な説明のため、上記の方法の実施例はアクションの系列として表されていることが留意されるべきである。しかしながら、本発明によると、いくつかのステップは他の順序で又は同時に実行されてもよいため、当業者は、本発明が説明されたアクションの順序に限定されないことを理解すべきである。上記の実施例では、各実施例の説明は各自の焦点を有する。実施例において詳細に説明されていない部分について、他の実施例における関連する説明が参照されてもよい。
【００８０】
本出願において提供される複数の実施例では、開示された装置及び方法は他の方式で実現されてもよいことが理解されるべきである。例えば、説明される装置の実施例は単なる一例である。例えば、ユニットの分割は単なる論理機能の分割であり、実施例の実現形態では他の分割であってもよい。例えば、複数のユニット又はコンポーネントが他のシステムに合成又は統合されてもよいし、又は、一部の特徴は無視されてもよいし、あるいは実行されなくてもよい。さらに、表示又は説明される相互結合又は直接的な結合若しくは通信接続は、いくつかのインタフェースを用いることによって実現されてもよい。装置又はユニットの間の間接的な結合又は通信接続は、電子、機械又は他の形態により実現されてもよい。
【００８１】
個別のパーツとして説明されるユニットは物理的に別のものであっても又はなくてもよく、ユニットとして表示されるパーツは物理的なユニットであっても又はなくてもよく、１つの位置に配置されてもよく、又は複数のネットワークユニット上で分散されてもよい。ユニットの一部又は全ては、実施例の解決策の課題を実現するため実際のニーズに従って選択されてもよい。
【００８２】
さらに、本発明の実施例における機能ユニットは１つの処理ユニットに一体化されてもよいし、又は、各ユニットは物理的に単独で存在してもよく、又は２つ以上のユニットが１つのユニットに統合される。統合されたユニットは、ハードウェアの形式で実現されてもよいし、又はソフトウェア機能ユニットの形式で実現されてもよい。
【００８３】
統合されたユニットがソフトウェア機能ユニットの形式で実現され、独立した製品として販売又は使用されるとき、統合されたユニットは、コンピュータ可読記憶媒体に記憶されてもよい。このような理解に基づき、実質的に本発明の技術的解決策又は従来技術に貢献する部分、又は技術的解決策の全て若しくは一部は、ソフトウェアプロダクトの形式で実現されてもよい。ソフトウェアプロダクトは、記憶媒体に記憶され、本発明の実施例において説明される方法のステップの全て又は一部を実行するようコンピュータ装置（パーソナルコンピュータ、サーバ又はネットワーク装置であってもよい）に命令するための複数の命令を有する。上記の記憶媒体は、ＵＳＢフラッシュドライブ、着脱可能なハードディスク、読み出し専用メモリ（ＲＯＭ，Ｒｅａｄ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ランダム・アクセス・メモリ（ＲＡＭ，Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、磁気ディスク又は光ディスクなどのプログラムコードを記憶可能な何れかの媒体を含む。
【００８４】
上記は、本発明において提供される関心ポイントのクラスタリング方法及び関連する装置を詳細に説明した。当業者は、本発明のアイデアに基づき、特定の実現方式及び適用範囲に関して修正を行ってもよい。従って、本明細書のコンテンツは本発明に対する限定として解釈されるものでない。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図３
【補正方法】変更
【補正の内容】
【図３】
2016537718.tif 000025
【国際調査報告】
2016537718.tif 000026
2016537718.tif 000027
2016537718.tif 000028
2016537718.tif 000029