Mining correlation between locations using location history

• US 8,612,134 B2
• Filed: 02/23/2010
• Issued: 12/17/2013
• Est. Priority Date: 02/23/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zheng, Yu, Zhang, Lizhu, Xie, Xing
• Primary Examiner(s): Champagne, Luna
• Application Number:
  US12/711,130
• Publication Number:
  US 20110208425A1
• Time in Patent Office: 1,393 Days
• Field of Search: 701/400, 701/467, 705/7.34
• US Class Current: 701/400
• CPC Class Codes: G01S 19/14 specially adapted for specific applications

Abstract

Techniques describe determining a correlation between identified locations to recommend a location that may be of interest to an individual user. The process constructs a location model to identify locations. To construct the model, the process uses global positioning system (GPS) logs of geospatial locations collected over time and identifies trajectories representing trips of the individual user and extracts stay points from the trajectories. Each stay point represents a geographical region where the individual user stayed over a time threshold within a distance threshold. A location history is formulated for the individual user based on a sequence of the extracted stay points to identify locations.

The process determines a correlation between identified locations. The process integrates travel experiences of individual users who have visited the locations in a weighted manner and identifies a common travel sequence which the individual users followed between the locations.

Claims

1. A method implemented at least partially by a processor, the method comprising:

collecting global positioning system (GPS) logs of geospatial locations of multiple users captured over time;

constructing, using the processor, a location model for each individual user of the multiple users by;

identifying trajectories representing trips of the individual user based on the GPS logs of geospatial locations captured over time;

extracting stay points from the trajectories, each stay point representing a geographical region where the individual user stayed over a time threshold within a distance threshold; and

formulating a location history for the individual user based on a sequence of the extracted stay points; and

determining a correlation between locations by;

identifying, based on the location histories of the multiple users, a collection of users that have visited the locations; and

integrating travel experiences of the collection of users in a weighted manner, wherein a contribution of each travel experience is weighted based on a sequence in which the locations were visited in a trip and a number of intervening locations in the trip.

2. The method of claim 1, wherein the GPS logs include a sequence of GPS points representing geospatial locations of the individual user captured over a time period, and wherein the GPS points each contain a date, a time, a longitude, and a latitude.

3. The method of claim 1, further comprising:

clustering the stay points of geographical regions for the individual user to form clusters of stay points; and

removing a top two clusters of stay points having a greatest number of stay points to eliminate the geographical regions that are private to the individual user.

4. The method of claim 1, further comprising:

clustering the stay points that are extracted into clusters corresponding to the geographical regions based on a density-based clustering algorithm; and

detecting clusters with irregular structures.

5. The method of claim 1, further comprising clustering the stay points that are extracted to form clusters by using a density-based clustering algorithm, the density-based clustering algorithm based at least in part on a core-distance and a minimum number of stay points falling within the core-distance.

6. The method of claim 1, further comprising:

creating a dataset of location histories of the multiple users;

partitioning the dataset of the multiple users into clusters by employing a density-based clustering algorithm;

assigning the stay points in the dataset into clusters of geographical regions that are similar;

substituting a stay point in the location history of the individual user with an identification of a cluster; and

identifying locations of geographical regions based on the clustering of the stay points.

7. The method of claim 1, further comprising:

identifying that a travel time spent between two consecutive stay points in the location history of the individual user exceeds a predetermined threshold and, in response, partitioning the location history of the individual user into more than one trip;

or

identifying that the travel time spent between the two consecutive stay points does not exceed the predetermined threshold and, in response, leaving the location history of the individual as a trip.

8. The method of claim 1, further comprising presenting a user with a recommendation, the recommendation based at least in part on the correlation between the locations, the recommendation being based on a user'"'"'s present geospatial location, a prediction of the user'"'"'s interest in a location, locations within a threshold travel time, locations within a predetermined distance from the user'"'"'s present geospatial location, or a combination thereof.

20. The method of claim 1, wherein the contribution of a travel experience in which a first location and a second location are consecutively visited is higher than the contribution of a travel experience in which at least one other location is visited after the first location is visited but before the second location is visited.

9. One or more computer-readable media encoded with instructions that, when executed by a processor, perform acts comprising:

accessing a location model constructed from global positioning system (GPS) logs of geospatial locations to identify locations for calculating a correlation between identified locations;

calculating a correlation between the identified locations from the location model based on using an algorithm for;

identifying a collection of individual users visiting the identified locations in a trip; and

integrating the travel experiences of the collection of individual users who have visited the identified locations in a weighted manner, wherein a contribution of each travel experience is weighted based on a sequence in which the identified locations were visited in a trip and a number of intervening locations in the trip;

identifying a recommended location based on the correlation between the identified locations from location histories of the individual users;

detecting a user'"'"'s present geospatial location or accessing a geospatial location on a map; and

recommending the recommended location based on detecting the user'"'"'s present geospatial location or based on the geospatial location accessed on the map, wherein the recommended location is within at least one of;

a threshold travel time, or

a predetermined distance from the geospatial location.

10. The one or more computer-readable media of claim 9, wherein the integrating the travel experiences comprises employing an inference model to infer the travel experiences by:

building a matrix between individual users and locations visited by the individual users;

representing a relationship between the travel experiences of the individual user and location interests of the locations visited; and

calculating the travel experiences and the location interests in an iterative process to determine the travel experiences.

11. The one or more computer-readable media of claim 9, further comprising building a location model for each individual user by:

retrieving global positioning system (GPS) logs of geospatial locations of multiple users captured over time; and

constructing a location model for each individual user of the multiple users by;

identifying trajectories representing trips of the individual user based on the GPS logs of geospatial locations captured over time;

extracting stay points from the trajectories, each stay point representing a geographical region where the individual user stayed over a time threshold within a distance threshold; and

formulating a location history for the individual user based on a sequence of the extracted stay points.

12. The one or more computer-readable media of claim 11, further comprising:

clustering the stay points of geographical regions for the individual user to form clusters of stay points;

removing a top two clusters of stay points having a greatest number of stay points to eliminate the geographical regions that are private to the individual user; and

reclustering the stay points after the top two clusters have been removed.

13. The one or more computer-readable media of claim 9, further comprising:

creating a dataset of location histories of multiple users;

partitioning the dataset of the multiple users into clusters by employing a density-based clustering algorithm;

assigning the stay points in the dataset into clusters of geographical regions that are closely related in distance;

substituting a stay point in the location history of the individual user with an identification of a cluster; and

identifying the identified locations of geographical regions based on the clustering of the stay points.

14. The one or more computer-readable media of claim 9, wherein the GPS logs include a sequence of GPS points representing geospatial locations of the individual user captured over a time period, and wherein the GPS points each contain a date, a time, a longitude, and a latitude.

15. The one or more computer-readable media of claim 9, further comprising:

identifying that a travel time spent between two consecutive stay points in the location history of the individual user exceeds a predetermined threshold and, in response, partitioning the location history of the individual user into more than one trip;

or

identifying that the travel time spent between the two consecutive stay points does not exceed the predetermined threshold and, in response, leaving the location history of the individual as a trip.

16. A system comprising:

a memory;

a processor coupled to the memory;

a location model module stored in the memory and executable on the processor to construct a location model for identifying locations visited by a collection of individual users, the locations based on location histories of multiple users captured over time through global positioning system (GPS) logs; and

a location correlation module stored in the memory and executable on the processor to compute a correlation between the locations visited by the collection of individual users, by integrating travel experiences of the collection of individual users in a weighted manner, wherein a contribution of each travel experience is weighted based on a sequence in which the locations were visited in a trip and a number of intervening locations in the trip.

17. The system of claim 16, further comprising:

a location correlation application module stored in the memory and executable on the processor to provide a recommendation, the recommendation based at least in part on the correlation between the locations visited by the collection of individual users, the recommendation being based, at least in part, on at least one of;

a user'"'"'s present geospatial location,

a prediction of the user'"'"'s interest in a location,

locations within a threshold travel time, or

locations within a predetermined distance of the user'"'"'s present geospatial location.

18. The system of claim 16, further comprising:

an inference model module to infer the travel experiences of the individual user by;

building a matrix between individual users and locations visited by the individual users;

representing a relationship between the travel experiences of the individual user and location interests of the locations visited; and

calculating the travel experiences and the location interests for each location in an iterative process to determine the travel experiences.

19. The system of claim 16, further comprising the location model module stored in the memory and executable on the processor to construct the location model by:

extracting stay points from the GPS logs, each stay point representing a geographical region where the individual user stayed over a time threshold within a distance threshold;

partitioning a dataset of the multiple users into clusters by employing a density-based clustering algorithm;

assigning the stay points in the dataset into clusters of geographical regions;

substituting a stay point in the location history of the individual user with an identification of a cluster; and

identifying locations of geographical regions based on the clustering of the stay points.