Mining Correlation Between Locations Using Location History

• US 20110208425A1
• Filed: 02/23/2010
• Published: 08/25/2011
• Est. Priority Date: 02/23/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Lizhu, Xie, Xing, Zheng, Yu
• Granted Patent: US 8,612,134 B2
• Time in Patent Office: Days
• US Class Current: 701/208
• 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 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.

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 algorithm based at least in part on a core-distance parameter 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 computing a correlation between locations in location histories of the multiple users by:

identifying a number of individual users visiting the locations;

integrating travel experiences of the individual users who have visited the locations in a weighted manner;

determining a common travel sequence which multiple users followed between two stay points; and

identifying a correlation between the locations based on the travel experiences and the common travel sequence.

9. The method of claim 8, further comprising presenting a user with a recommendation, based at least in part on the correlation between 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, and/or locations within a predetermined distance from the user'"'"'s present geospatial location.

10. 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 geographical 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 number of individual users visiting the identified locations in a trip;

integrating the travel experiences of the number of individual users who have visited the identified locations in a weighted manner;

determining a common travel sequence based on the number of individual users followed between stay points, each stay point representing a geographical region where an individual user stayed over a time threshold within a distance threshold;

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 a threshold travel time and/or locations within a predetermined distance from the geospatial location.

11. The computer-readable media of claim 10, 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.

12. The computer-readable media of claim 10, further comprising building a location model for each individual user of the multiple users to identify locations to determine the correlation, the building by:

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

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.

13. The 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.

14. The computer-readable media of claim 10, 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 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.

15. The computer-readable media of claim 10, 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.

16. The computer-readable media of claim 10, 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.

17. 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, 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 of the multiple users, by integrating travel experiences of individual users and determining a common travel sequence which the individual users followed between locations.

18. The system of claim 17, further comprising:

a location correlation application module stored in the memory and executable on the processor to provide a recommendation, based at least in part on the correlation between the locations of the multiple users, 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, and/or locations within a predetermined distance of the user'"'"'s present geospatial location.

19. The system of claim 17, 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.

20. The system of claim 17, 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.