Mining life pattern based on location history

• US 8,275,649 B2
• Filed: 09/18/2009
• Issued: 09/25/2012
• Est. Priority Date: 09/18/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zheng, Yu, Ye, Yang, Xie, Xing
• Primary Examiner(s): PATS, JUSTIN
• Application Number:
  US12/562,588
• Publication Number:
  US 20110071881A1
• Time in Patent Office: 1,103 Days
• Field of Search: 705/7.29, 705/7.31, 705/7.34
• US Class Current: 705/7.34
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration
• CPC Class Codes: G06Q 30/0261 based on user location

Abstract

Techniques for providing mining life pattern are described. This disclosure describes mining a life pattern of an individual, for example, by identifying places visited during the individual'"'"'s daily activities. Mining the individual life pattern includes collecting location data for the individual and predicting behaviors and preferences of the individual based at least in part on a location history. The location history of the individual is represented with a sequence of geographical regions that have been visited by the individual with corresponding arrival and departure times for each region. Once the life pattern is predicted from the location history, information is recommended to the individual based at least in part on the life pattern.

Claims

1. A method comprising:

under control of one or more processors configured with executable instructions;

collecting location data associated with an individual;

extracting a plurality of locations from the location data and transforming the plurality of locations in the location data to a plurality of stay points, each stay point comprising one or more locations of the plurality of locations that define a geographical region in which the individual has stayed within a predetermined distance over a predetermined time period;

clustering the plurality of stay points into a sequence of stay point clusters, each stay point cluster comprising stay points corresponding to a same place or sharing a same semantic meaning within a specific distance threshold;

creating a location history of the individual with the sequence of stay point clusters;

predicting a life pattern of the individual based at least in part on the location history, the life pattern emphasizing places significant to the individual and ignoring transitions between the significant places;

generating a life associate rule based on the life pattern, the life associate rule comprising a rule describing a relationship between two non-conditional life patterns and a support value representing a probability of co-occurrence of the two non-conditional life patterns; and

providing information to the individual based at least in part on the life pattern or the life associate rule.

2. The method of claim 1, wherein collecting the location data comprises collecting global positioning system (GPS) logs and converting the GPS logs according to a time series into a GPS trajectory for the individual.

3. The method of claim 1, wherein collecting the location data comprise collecting global position system (GPS) logs of a sequence of GPS points, each GPS point contains a longitude, a latitude, and a timestamp.

4. The method of claim 1, wherein the clustering further comprises building a location history tree, the location history tree comprising a plurality of nodes in a plurality of levels, each node representing a cluster of a subset of the plurality of stay points and each level in the tree representing a geospatial granularity which is different from the rest of the plurality of levels.

5. The method of claim 1, wherein the location history comprises a place visited or stayed for a period of time, a timestamp for arrival at the place visited, and a timestamp for departure from the place visited.

6. The method of claim 1, wherein the providing the information comprises recommending at least one of advertisements, sales promotions, schedule times for public transportation, a route arrangement for travel, an alternative route to avoid traffic, accidents, or hazardous road conditions, movie trailer, or a book promotion.

7. A storage device encoded with instructions that, when executed by one or more processors, configure the one or more processors to perform acts comprising:

collecting location data associated with an individual;

extracting a plurality of locations from the location data and transforming the plurality of locations in the location data to a plurality of stay points, each stay point comprising one or more locations of the plurality of locations that define a geographical region in which the individual has stayed within a predetermined distance over a predetermined time period;

clustering the plurality of stay points into a sequence of stay point clusters, each stay point cluster comprising stay points corresponding to a same place or sharing a same semantic meaning within a specific distance threshold;

creating a location history of the individual with the sequence of stay point clusters;

predicting a life pattern of the individual based at least in part on the location history, the life pattern emphasizing places significant to the individual and ignoring transitions between the significant places;

generating a life associate rule based on the life pattern, the life associate rule comprising a rule describing a relationship between two non-conditional life patterns and a support value representing a probability of co-occurrence of the two non-conditional life patterns; and

providing information to the individual based at least in part on the life pattern or the life associate rule.

8. The storage device of claim 7, wherein collecting the location data comprises collecting global positioning system (GPS) logs and converting the GPS logs according to a time series into a GPS trajectory for the individual.

9. The storage device of claim 7, wherein collecting the location data comprise collecting global position system (GPS) logs of a sequence of GPS points, each GPS point contains a longitude, a latitude, and a timestamp.

10. The storage device of claim 7, wherein the clustering further comprises building a location history tree, the location history tree comprising a plurality of nodes in a plurality of levels, each node representing a cluster of a subset of the plurality of stay points and each level in the tree representing a geospatial granularity which is different from the rest of the plurality of levels.

11. The storage device of claim 7, wherein the location history comprises a place visited or stayed for a period of time, a timestamp for arrival at the place visited, and a timestamp for departure from the place visited.

12. The storage device of claim 7, wherein the providing the information comprises recommending at least one of advertisements, sales promotions, schedule times for public transportation, a route arrangement for travel, an alternative route to avoid traffic, accidents, or hazardous road conditions, movie trailer, or a book promotion.

13. A system comprising:

memory;

one or more processors coupled to the memory to perform acts comprising;

collecting location data associated with an individual;

extracting a plurality of locations from the location data and transforming the plurality of locations in the location data to a plurality of stay points, each stay point comprising one or more locations of the plurality of locations that define a geographical region in which the individual has stayed within a predetermined distance over a predetermined time period;

clustering the plurality of stay points into a sequence of stay point clusters, each stay point cluster comprising stay points corresponding to a same place or sharing a same semantic meaning within a specific distance threshold;

creating a location history of the individual with the sequence of stay point clusters;

predicting a life pattern of the individual based at least in part on the location history, the life pattern emphasizing places significant to the individual and ignoring transitions between the significant places;

generating a life associate rule based on the life pattern, the life associate rule comprising a rule describing a relationship between two non-conditional life patterns and a support value representing a probability of co-occurrence of the two non-conditional life patterns; and

providing information to the individual based at least in part on the life pattern or the life associate rule.

14. The system of claim 13, wherein collecting the location data comprises collecting global positioning system (GPS) logs and converting the GPS logs according to a time series into a GPS trajectory for the individual.

15. The system of claim 13, wherein collecting the location data comprise collecting global position system (GPS) logs of a sequence of GPS points, each GPS point contains a longitude, a latitude, and a timestamp.

16. The system of claim 13, wherein the clustering further comprises building a location history tree, the location history tree comprising a plurality of nodes in a plurality of levels, each node representing a cluster of a subset of the plurality of stay points and each level in the tree representing a geospatial granularity which is different from the rest of the plurality of levels.

17. The system of claim 13, wherein the location history comprises a place visited or stayed for a period of time, a timestamp for arrival at the place visited, and a timestamp for departure from the place visited.

18. The system of claim 13, wherein the providing the information comprises recommending at least one of advertisements, sales promotions, schedule times for public transportation, a route arrangement for travel, an alternative route to avoid traffic, accidents, or hazardous road conditions, movie trailer, or a book promotion.