Clustering method for a point of interest and related apparatus

• US 10,423,728 B2
• Filed: 05/06/2016
• Issued: 09/24/2019
• Est. Priority Date: 11/07/2013
• Status: Active Grant

• Current Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Original Assignee: Huawei Technologies Co., Ltd. (Huawei Investment & Holding Co., Ltd.)
• Inventors: Ding, Qiang, Song, Shaoxu, Ou, Yangzhen
• Primary Examiner(s): Ruiz, Angelica
• Application Number:
  US15/148,365
• Publication Number:
  US 20160253407A1
• Time in Patent Office: Days
• CPC Class Codes: G01C 21/3679 Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities G01C21/3611 takes precedence
• CPC Class Codes: G06F 16/287 Visualization; Browsing
• CPC Class Codes: G06F 16/29 Geographical information databases
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: H04W 4/023 using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds
• CPC Class Codes: H04W 4/025 using location based information parameters
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

A clustering method for a point of interest and a related apparatus are provided. The clustering method for a point of interest includes: acquiring a locating point set of a user within a preset period; generating a stay point set according to the locating point set, where each stay point in the stay point set represents one hot area; calculating a confidence level of each stay point in the stay point set; obtaining a trusted stay point from the stay point set by means of screening according to the confidence level of each stay point in the stay point set; and clustering density-connected trusted stay points to form a point of interest. By using technical solutions provided in the present disclosure, reliability and reference value of a POI can be effectively improved.

Claims

1. A clustering method, comprising:

acquiring, from a location tracking device, a locating point set of a user within a preset period, wherein each locating point in the locating point set indicates a particular location of the user at a particular time;

generating a stay point set according to the locating point set, wherein each stay point in the stay point set represents a hot area, and the hot area meets a set of conditions, the set of conditions comprising;

a distance between geographic locations of any two locating points in the hot area is less than a higher locating precision in locating precisions of the two locating points, and a maximum value of a time interval between locating points in the hot area is greater than a preset time threshold;

acquiring movement states of locating points comprised in a hot area represented by each stay point;

calculating a confidence level of each stay point in the stay point set according to the movement states of the locating points comprised in the hot area represented by each stay point and according to a relation between confidence level weights of movement states of each stay point in the stay point set and a quantity of locating points that are located in the hot area represented by a corresponding stay point and whose movement state correspond to a corresponding movement state, wherein each movement state corresponds to a confidence level weight, wherein a lower average speed corresponding to the movement states of the locating points in a hot area represented by a stay point indicates a higher confidence level of the stay point, and wherein a lower movement speed corresponding to a movement state indicates a larger confidence level weight of the movement state;

obtaining a trusted stay point from the stay point set by screening according to the confidence level of each stay point in the stay point set, wherein a confidence level of the trusted stay point is greater than a preset confidence level threshold; and

clustering density-connected trusted stay points to form a point of interest, wherein the density-connected trusted stay points are trusted stay points that represent hot areas whose ranges are connected to each other.

2. The method according to claim 1, wherein generating the stay point set according to the locating point set comprises:

determining a hot area that meets the set of conditions; and

determining a geometric center point of the hot area as a stay point that represents the hot area.

3. The method according to claim 1, wherein calculating the confidence level of each stay point in the stay point set comprises:

calculating the confidence level of each stay point in the stay point set according to a relation

4. The method according to claim 3, wherein acquiring the movement states of the locating points comprised in the hot area represented by each stay point comprises:

acquiring the movement states of the locating points comprised in the hot area represented by each stay point according to sensor data on a terminal of the user.

5. The method according to claim 3, wherein acquiring the movement states of the locating points comprised in the hot area represented by each stay point comprises acquiring the movement states of the locating points comprised in the hot area represented by each stay point according to a change of signal strength and a change of a signal quantity of a Wi-Fi network.

6. The method according to claim 1, wherein clustering the density-connected trusted stay points to form the point of interest comprises:

determining a closed area that is formed by connecting all leaf stay points among all density-connected trusted stay points as an area of a point of interest, wherein a sum of confidence levels of all stay points within a preset radius coverage range whose center is a leaf stay point is not greater than a preset threshold.

7. The method according to claim 1, wherein the density-connected trusted stay points are trusted stay points that represent hot areas whose ranges are directly connected to each other.

8. The method according to claim 1, wherein the density-connected trusted stay points are trusted stay points that represent hot areas whose ranges are indirectly connected to each other.

9. A clustering apparatus, comprising:

a memory configured to store instructions; and

a processor coupled to the memory and configured to execute the instructions to;

acquire, from a location tracking device, a locating point set of a user within a preset period, wherein each locating point in the locating point set indicates a particular location of the user at a particular time;

generate a stay point set according to the locating point set, wherein each stay point in the stay point set represents a hot area, and the hot area meets a set of conditions, the set of conditions comprising;

a distance between geographic locations of any two locating points in the hot area is less than a higher locating precision in locating precisions of the two locating points, and a maximum value of a time interval between locating points in the hot area is greater than a preset time threshold;

acquire movement states of locating points comprised in a hot area represented by each stay point;

calculate a confidence level of each stay point in the stay point set according to the movement states that are of the locating points comprised in the hot area represented by each stay point and according to a relation between confidence level weights of movement states of each stay point in the stay point set and a quantity of locating points that are located in the hot area represented by a corresponding stay point and whose movement state correspond to a corresponding movement state, wherein each movement state corresponds to a confidence level weight, wherein a lower average speed corresponding to the movement states of the locating points in a hot area represented by a stay point indicates a higher confidence level of the stay point, and wherein a lower movement speed corresponding to a movement state indicates a larger confidence level weight of the movement state;

obtain a trusted stay point from the stay point set by means of screening according to the confidence level that is of each stay point in the stay point set, wherein a confidence level of the trusted stay point is greater than a preset confidence level threshold; and

cluster density-connected trusted stay points to form a point of interest, wherein the density-connected trusted stay points are trusted stay points that represent hot areas whose ranges are connected to each other.

10. The clustering apparatus according to claim 9, wherein the processor is further configured to execute the instructions to:

determine a hot area that meets the set of conditions; and

determine a geometric center point of the hot area as a stay point that represents the hot area.

11. The clustering apparatus according to claim 9, wherein the processor is further configured to execute the instructions to:

calculate the confidence level of each stay point in the stay point set according to a relation

12. The clustering apparatus according to claim 11, wherein the processor is further configured to execute the instructions to acquire the movement states of the locating points comprised in the hot area represented by each residence point according to sensor data on a terminal of the user.

13. The clustering apparatus according to claim 11, wherein the processor is further configured to execute the instructions to acquire the movement states of the locating points comprised in the hot area represented by each residence point according to a change of signal strength and a change of a signal quantity of a Wi-Fi network.

14. The clustering apparatus according to claim 9, wherein the processor is further configured to execute the instructions to cluster all density-connected trusted stay points to form a point of interest, and determine a closed area that is formed by connecting all leaf stay points among all density-connected trusted stay points as an area of a point of interest, wherein a sum of confidence levels of all stay points within a preset radius coverage range whose center is a leaf stay point is not greater than a preset threshold.

15. The clustering apparatus according to claim 9, wherein the density-connected trusted stay points are trusted stay points that represent hot areas whose ranges are directly connected to each other.

16. The clustering apparatus according to claim 9, wherein the density-connected trusted stay points are trusted stay points that represent hot areas whose ranges are indirectly connected to each other.

17. A clustering apparatus, comprising:

means for acquiring, from a location tracking device, a locating point set of a user within a preset period, wherein each locating point in the locating point set indicates a particular location of the user at a particular time;

means for generating a stay point set according to the locating point set, wherein each stay point in the stay point set represents a hot area, and the hot area meets a set of conditions, the set of conditions comprising;

a distance between geographic locations of any two locating points in the hot area is less than a higher locating precision in locating precisions of the two locating points, and a maximum value of a time interval between locating points in the hot area is greater than a preset time threshold;

means for acquiring movement states of locating points comprised in a hot area represented by each stay point;

means for calculating a confidence level of each stay point in the stay point set according to the movement states of the locating points comprised in the hot area represented by each stay point and according to a relation between confidence level weights of movement states of each stay point in the stay point set and a quantity of locating points that are located in the hot area represented by a corresponding stay point and whose movement state correspond to a corresponding movement state, wherein each movement state corresponds to a confidence level weight, wherein a lower average speed corresponding to the movement states of the locating points in a hot area represented by a stay point indicates a higher confidence level of the stay point, and wherein a lower movement speed corresponding to a movement state indicates a larger confidence level weight of the movement state;

means for obtaining a trusted stay point from the stay point set by means of screening according to the confidence level of each stay point in the stay point set, wherein a confidence level of the trusted stay point is greater than a preset confidence level threshold; and

means for clustering density-connected trusted stay points to form a point of interest, wherein the density-connected trusted stay points are trusted stay points that represent hot areas whose ranges are connected to each other.

18. The apparatus according to claim 17, wherein the means for generating the stay point set is configured to determine a hot area that meets the set of conditions and to determine a geometric center point of the hot area as a stay point that represents the hot area.

19. The apparatus according to claim 17, wherein the means for calculating is configured to:

calculate the confidence level of each stay point in the stay point set according to a relation

20. The apparatus according to claim 17, wherein the means for clustering is configured to:

determine a closed area that is formed by connecting all leaf stay points among all density-connected trusted stay points as an area of a point of interest, wherein a sum of confidence levels of all stay points within a preset radius coverage range whose center is a leaf stay point is not greater than a preset threshold.