# US 2016/0253407 A1 · Clustering Method for a Point of Interest and Related Apparatus

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2016/0253407 A1
- Document ID: US20160253407A1
- Status: Published application
- Kind: A1
- Application number: 15/148,365
- Filed: 2016-05-06
- Published: 2016-09-01
- Earliest claimed: 2013-11-07
- Assignees: Huawei Technologies Co., Ltd.
- Applicants: Huawei Technologies Co., Ltd.
- Inventors: Qiang Ding; Shaoxu Song; Yangzhen Ou
- Web page: https://patentgrep.com/patent/US20160253407A1

## CPC

- G06F 16/287: {Visualization; Browsing}
- G01C 21/3679: {Retrieval, searching and output of POI information, e.g. hotels, restaurants, shops, filling stations, parking facilities (G01C21/3611 takes precedence)}
- G06F 16/29: Geographical information databases
- G06F 18/23: Clustering techniques
- H04W 4/023: {using mutual or relative location information between multiple location based services [LBS] targets or of distance thresholds}
- H04W 4/025: {using location based information parameters}
- H04W 4/029: Location-based management or tracking services
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)
- H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72)

## 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

### Claim 1

A clustering method, comprising:
acquiring a locating point set of a user within a preset period;
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;
calculating a confidence level of each stay point in the stay point set, wherein a lower average speed corresponding to movement states of all locating points in a hot area represented by a stay point indicates a higher confidence level of the stay point;
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
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.

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

The method according to claim 1, wherein calculating the confidence level of each stay point in the stay point set comprises:
acquiring movement states of all locating points comprised in a hot area represented by each stay point; and
calculating the confidence level of each stay point in the stay point set according to a relation
Conf
i
=
(
∑
k
=
1
n

W
k
·
n
k
)
/
∑
k
=
1
n

n
k
and according to the movement states of all locating points comprised in the hot area represented by each stay point, wherein Confi represents a confidence level of a stay point i, n represents n possible movement states, Wk represents a confidence level weight of the kth movement state, and nk represents a quantity of locating points that are in a hot area represented by the stay point i and whose movement states are the kth movement state, and wherein each movement state corresponds to a confidence level weight, and a lower movement speed corresponding to a movement state indicates a larger confidence level weight of the movement state.

### Claim 4 (depends on 3)

The method according to claim 3, wherein acquiring the movement states of all locating points comprised in the hot area represented by each stay point comprises:
acquiring the movement states of all locating points comprised in the hot area represented by each stay point according to sensor data on a terminal of the user.

### Claim 5 (depends on 3)

The method according to claim 3, wherein acquiring the movement states of all locating points comprised in the hot area represented by each stay point comprises acquiring the movement states of all 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.

### Claim 6 (depends on 1)

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.

### Claim 7 (depends on 1)

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.

### Claim 8 (depends on 1)

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.

### Claim 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 a locating point set of a user within a preset period;
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;
calculate a confidence level of each stay point in the stay point set, wherein a lower average speed corresponding to movement states of all locating points in a hot area represented by a stay point indicates a higher confidence level of the stay point;
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.

### Claim 10 (depends on 9)

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.

### Claim 11 (depends on 9)

The clustering apparatus according to claim 9, wherein the processor is further configured to execute the instructions to:
acquire movement states of all locating points comprised in a hot area represented by each stay point; and
calculate the confidence level of each stay point in the stay point set according to a relation
Conf
i
=
(
∑
k
=
1
n

W
k
·
n
k
)
/
∑
k
=
1
n

n
k
and according to the movement states that are of all locating points comprised in the hot area represented by each stay point, wherein Confi represents a confidence level of a stay point i, n represents n possible movement states, Wk represents a confidence level weight of the kth movement state, and nk represents a quantity of locating points that are in a hot area represented by the stay point i and whose movement states are the kth movement state, wherein each movement state corresponds to a confidence level weight, and a lower movement speed corresponding to a movement state indicates a larger confidence level weight of the movement state.

### Claim 12 (depends on 11)

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

### Claim 13 (depends on 11)

The clustering apparatus according to claim 11, wherein the processor is further configured to execute the instructions to acquire the movement states of all 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.

### Claim 14 (depends on 9)

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.

### Claim 15 (depends on 9)

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.

### Claim 16 (depends on 9)

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.

### Claim 17

A clustering apparatus, comprising:
means for acquiring a locating point set of a user within a preset period;
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 calculating a confidence level of each stay point in the stay point set, wherein a lower average speed corresponding to movement states of all locating points in a hot area represented by a stay point indicates a higher confidence level of the stay point;
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.

### Claim 18 (depends on 17)

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.

### Claim 19 (depends on 17)

The apparatus according to claim 17, wherein the means for calculating is configured to:
acquire movement states of all locating points comprised in a hot area represented by each stay point; and
calculate the confidence level of each stay point in the stay point set according to a relation
Conf
i
=
(
∑
k
=
1
n

W
k
·
n
k
)
/
∑
k
=
1
n

n
k
and according to the movement states of all locating points comprised in the hot area represented by each stay point, wherein Confi represents a confidence level of a stay point i, n represents n possible movement states, Wk represents a confidence level weight of the kth movement state, and nk represents a quantity of locating points that are in a hot area represented by the stay point i and whose movement states are the kth movement state, and wherein each movement state corresponds to a confidence level weight, and a lower movement speed corresponding to a movement state indicates a larger confidence level weight of the movement state.

### Claim 20 (depends on 17)

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.
