Collaborative location and activity recommendations

• US 8,719,198 B2
• Filed: 05/04/2010
• Issued: 05/06/2014
• Est. Priority Date: 05/04/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zheng, Yu, Zheng, Wencheng, Xie, Xing
• Primary Examiner(s): NGUYEN, KIM T
• Application Number:
  US12/773,771
• Publication Number:
  US 20110276565A1
• Time in Patent Office: 1,463 Days
• Field of Search: 706/21, 706/46
• US Class Current: 706/21
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: H04W 4/029 Location-based management or tracking services
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

Techniques describe constructing a location and activity recommendation model to identify relationships between locations and activities. To construct the model, the process obtains global positioning system (GPS) logs of geographical locations collected over time and identifies stay points representing locations visited by an individual user. The process also identifies points of interest in a region using a database and correlates a relationship between activity to activity by submitting queries to a search engine. The information gathered is used to fill locations and activities in a location-activity matrix. Recommendations may be made for a location and/or activity when given a user query, based on a user'"'"'s present geographical location, or a prediction of a user'"'"'s interest.

Claims

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

creating a location-activity matrix by detecting stay points to represent a set of stay regions representing stay points where a device associated with an individual has stayed over a time threshold within a distance threshold, and by extracting user comments from global positioning system (GPS) logs of the device corresponding to the set of stay regions;

creating a location-feature matrix by identifying points of interest (POI) in a region and determining a number of different POI in an enclosing polygon of stay points;

creating an activity-activity matrix by identifying a correlation between a pair of activities; and

associating information from the location-feature matrix and the activity-activity matrix with the location-activity matrix.

2. The method of claim 1, wherein the creating the location-activity matrix further comprises:

parsing the user comments from the GPS logs to identify activities for each stay region; and

determining a frequency for the activities at each stay region.

3. The method of claim 1, wherein the creating the location-feature matrix further comprises:

normalizing the number of the different POI by a term frequency-inverse document frequency; and

assigning less weight for the POI that occur more frequently in the enclosing polygon of stay points.

4. The method of claim 1, wherein the activity-activity matrix further comprises:

sending a query for the pair of activities to a search engine;

retrieving a number of search results for the pair of activities queried on the search engine; and

determining the number of search results returned and comparing this number to a threshold number to determine whether the correlation exists between the pair of activities.

5. The method of claim 1, further comprising:

parsing trajectories from the GPS logs, the trajectories based at least in part on a sequence of stay points;

dividing a map of the stay points into a set of grids based on at least a parameter;

identifying a grid that has not been assigned to a stay region, the grid having a predetermined number of stay points;

extracting neighboring grids that surround the grid, the neighboring grids including grids that have been assigned to stay regions and grids that have not been assigned to the stay regions; and

clustering the grid and the neighboring grids that have not been assigned to the stay regions to form a new stay region.

6. The method of claim 1, further comprising applying a gradient descent to iteratively minimize associating the information to the location-activity matrix.

7. The method of claim 1, further comprising:

receiving a query for a location;

identifying and ranking activities that correspond to the location queried; and

providing a recommendation of a list of candidate activities based at least in part on the ranking.

8. The method of claim 1, further comprising:

receiving a query for an activity;

identifying and ranking locations of interest in the location-activity matrix that correspond to the activity queried; and

presenting a list of candidate locations of interest in the location-activity matrix based at least in part on the ranking.

9. The method of claim 1, further comprising presenting a user with a recommendation for an activity of interest, the recommendation being based at least in part on a present geographical location of the user, a geographical location accessed on a map, and/or a prediction of the user'"'"'s interest in the activity of interest based on a query history of the location.

10. The method of claim 1, further comprising presenting a user with a recommendation for a location of interest, the recommendation being based at least in part on a prediction of the user'"'"'s interest in the location based on a query history for activities that occur in the location of interest.

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

creating a location and activity recommendation model that models a relationship between locations and activities;

applying a collective matrix factorization to identify locations of interest and corresponding activities of interest from the location and activity recommendation model by;

decomposing a location-activity matrix by a low rank approximation as a product of sharing matrices;

sharing location information through a first sharing matrix from a location-feature matrix;

sharing activity information through a second sharing matrix from an activity-activity matrix;

propagating location and activity information among the location-activity matrix, the location-feature matrix, and the activity-activity matrix; and

filling locations of interest information and activities of interest information in the location-activity matrix by applying a gradient descent to achieve a filled location-activity matrix; and

providing to a user a recommendation for a location of interest and/or a recommendation for an activity of interest with reference to the filled location-activity matrix.

12. The computer-readable storage media of claim 11, further comprising creating the location and activity recommendation model by:

obtaining stay points from global positioning system (GPS) logs to represent locations, representing locations where a device associated with an individual has stayed over a time threshold within a distance threshold and evaluating user comments from the GPS logs to correspond to the locations to create the location-activity matrix;

parsing the user comments from GPS logs to identify activities for each stay region; and

determining a frequency for the activities that occur at each stay region.

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

identifying points of interest (POI) in the locations; and

mining features of the locations by determining a number of different POI in the locations to create the location-feature matrix.

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

identifying a correlation for a pair of activities to create the activity-activity matrix by;

submitting a pair of activities to a search engine;

retrieving a number of search results for the pair of activities queried on the search engine; and

determining that the number of search results for the pair of activities is greater than a threshold number.

15. The computer-readable storage media of claim 11, wherein the recommendation for the activity of interest is based at least in part on a present geographical location of the user, a geographical location accessed on a map, and/or a prediction of the user'"'"'s interest in the activity of interest based at least in part on a query history of the location.

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

ranking the locations of interest and the activities of interest in a descending order in the filled location-activity matrix;

presenting the recommendation for locations of interest based at least in part on a query of an activity, the recommendation including a list of candidate locations;

or

presenting the recommendation for activities of interest based at least in part on a query of a location, the recommendation including a list of candidate activities.

17. A system comprising:

a processor;

a memory coupled to the processor;

a plurality of modules stored in the memory and executable on the processor, the plurality of modules comprising;

a location and activity recommendation model module to compute relationships between locations and activities based at least in part on information from global positioning system (GPS) logs, a points of interest (POI) database, and information accessible via a search engine;

a location-activity recommendation service module to receive user input from a user and present a recommendation for a location and/or an activity to the user at least partly in response to receiving the user input, the recommendation based at least in part on the relationships computed by the location and activity recommendation model module;

a location-activity module to extract stay points from the GPS logs, each stay point representing a geographical region where an individual has stayed over a time threshold within a distance threshold;

the location-activity module to divide a map of the geographical region into grids by employing a greedy clustering algorithm;

the location-activity module to identify a grid that has not been assigned to a stay region;

the location-activity module to extract neighboring grids that surround the grid, the neighboring grids include grids that have been assigned to stay regions and grids that have not been assigned to the stay regions; and

the location-activity module to cluster the grid and the neighboring grids that have not been assigned to the stay regions to form a new stay region.

18. The system of claim 17, the location and activity recommendation service module being further to rank the locations and activities;

and

the location and activity recommendation model module being further to provide a list of at least a portion of the locations and/or a list of activities in a descending order to a user.

19. The system of claim 17, the location and activity recommendation model module being further to provide a display of a map based at least in part on receiving a query from the user;

and

in an event that query from the user comprises a location query, display on the map and at the queried location a list of recommended activities for the queried location; and

in an event that the query from the user comprises an activity query, display on the map locations that are recommended for the queried activity.