MINING LIFE PATTERN BASED ON LOCATION HISTORY

• US 20110071881A1
• Filed: 09/18/2009
• Published: 03/24/2011
• 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
• Granted Patent: US 8,275,649 B2
• Time in Patent Office: Days
• US Class Current: 705/10
• 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 implemented at least partially by a processor, the method comprising:

collecting location data for an individual;

extracting a place visited from the location data and transforming the place visited in the location data to a stay point, the stay point is a geographical region where the individual has stayed over a time period and is a distance amount from another geographical region;

building a location history tree using a hierarchical clustering algorithm to cluster a sequence of stay points that include similar places visited;

creating a location history of the individual with a sequence of stay point clusters with a transition time between two clusters on different geospatial scales;

predicting a life pattern of the individual based on a routine schedule of the individual and the place visited in the individual'"'"'s daily life based at least in part on the location history; and

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

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

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

4. The method of claim 1, further comprising the stay point is the geographical region with a time threshold of approximately ten minutes and a distance threshold of a distance of approximately 200 meters from another geographical region.

5. The method of claim 1, wherein the location history tree comprises a node representing a cluster of stay points and different levels in the tree represent a different geospatial granularity.

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

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

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

receiving location data for an individual, the data includes a longitude, a latitude, and a timestamp for each geographical region visited;

representing a location history of the individual with geographical regions visited with corresponding arrival and departure times;

estimating behaviors and preferences of the individual based at least in part on the location history; and

providing recommendations to the individual based on the behaviors and preferences of the individual.

9. The computer-readable media of claim 8, further comprising extracting the geographical region based on spatial and temporal values of global positioning system points and transforming the geographical region visited to a stay point, each stay point is the geographical region where the individual has stayed over a time period and is a distance amount away from another geographical region.

10. The computer-readable media of claim 8, further comprising clustering the geographical regions visited into groups that are similar, based on the geographical regions visited are of a same type.

11. The computer-readable media of claim 10, further comprising:

clustering the sequence of stay points places visited using a hierarchical clustering algorithm to build a location history tree; and

clustering a sequence of stay point clusters with a transition time between two clusters on different geospatial scales to represent the location history of the individual.

12. The computer-readable media of claim 8, further comprising constructing a life sequence dataset, a data in the life sequence dataset corresponds to a day or a week.

13. The computer-readable media of claim 8, further comprising the stay point is the geographical region with a time threshold of approximately ten minutes and a distance threshold of a distance of approximately 200 meters from another geographical region.

14. The computer-readable media of claim 8, wherein the recommendations comprise at least one of advertisements, sales promotions, road condition notifications, weather condition notifications, traffic condition notifications, schedule times for public transportation, a route arrangement for travel, or an alternative route to avoid traffic, accidents, or hazardous road conditions.

15. A system comprising:

a memory;

a processor coupled to the memory to perform acts comprising;

gathering location data for an individual, the data includes a longitude, a latitude, and a timestamp for each geographical region;

modeling a location history of the individual by using the geographical regions visited with corresponding arrival and departure times;

predicting a life pattern of the individual based at least in part on the location history; and

presenting information to the individual based at least in part on the life pattern.

16. The system of claim 15, wherein the gathering location data comprises collecting from at least one of logs from a global positioning system (GPS) network or localization data from a global system for mobile communications (GSM) network.

17. The system of claim 15, further comprising identifying a place visited from the location data and transforming the place visited in the location data to a sequence of stay points, each stay point is a geographical region where the individual has stayed over a time period within a specific distance.

18. The system of claim 17, further comprising:

clustering the sequence of stay points that include similar places visited by using a hierarchical clustering algorithm to build a location history tree; and

clustering a sequence of stay point clusters with a transition time between two clusters on different geospatial scales to represent the location history.

19. The system of claim 15, wherein the life pattern comprises clustering a number of stay points into groups based on a number of stay points within a threshold and within a distance threshold.

20. The system of claim 15, wherein the life pattern comprises mining life patterns based at least in part life pattern, A is of the form:

A;

=visit(X)(?arv([t1, t2])(?stay([T1, T2])

where visit is a place visited or stayed for a time period and a distance apart from another geographical region, the symbol ? mean A is a timestamp or timespan annotated;

ary is an arrival time;

t1, t2 are two timestamps;

stay is time stayed; and

T1, T2 are lengths of two timespans.