Clustering location and time for location prediction

• US 8,412,234 B1
• Filed: 12/07/2011
• Issued: 04/02/2013
• Est. Priority Date: 12/07/2011
• Status: Active Grant

• Current Assignee: T-Mobile Innovations LLC (Deutsche Telekom AG)
• Original Assignee: Sprint Communications Company LP (Deutsche Telekom AG)
• Inventors: Reuther, Phyllis, Gatmir-Motahari, Sara
• Primary Examiner(s): PATEL, MAHENDRA R
• Application Number:
  US13/313,741
• Time in Patent Office: 482 Days
• Field of Search: 455/273, 455/139, 455/276.1, 705/7.17, 714/54, 342/125, 342/450, 340/538.16, 340/870.28, 370/395.4, 370/428, 370/537
• US Class Current: 455/456.1
• CPC Class Codes: G01S 5/02525 Gathering the radio frequency fingerprints
• CPC Class Codes: G01S 5/0278 involving statistical or probabilistic considerations G01S5/0252, G01S5/0294 take precedence
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management

Abstract

The invention is directed to methods for predicting future locations based on time clustering. Historical location data from a particular period of time is used to identify locations or places. The period of time is divided into even time slots. For each time slot, a probability distribution is computed by calculating a probability that the mobile device is located at each identified location during that time slot. The time slots are clustered into time slot groups based on similar probability distributions. For each time slot group, a probability distribution is calculated representing a probability that the mobile device is present at each location during the period of time defined by the time slot group.

Claims

1. One or more non-transitory computer-readable media having computer-executable instructions embodied thereon that, when executed, enable a computing device to perform a method of predicting a future location based on time clustering, the method comprising:

providing location data for a particular mobile device over a predetermined period of time;

identifying one or more locations from the location data;

dividing the predetermined period of time into a plurality of time slots;

for each of the plurality of time slots, automatically calculating a probability distribution representing a probability that the mobile device is located at each of the one or more locations;

determining from the plurality of time slots that one or more first time slots and one or more second time slots have similar probability distributions;

based on the similar probability distributions, clustering the plurality of time slots into one or more time-slot groups, wherein clustering includes associating the one or more first time slots with the one or more second time slots to form the one or more time-slot groups; and

for each of the one or more time-slot groups, automatically calculating the probability distribution representing the probability that the mobile device is located at each of the one or more locations, wherein at least one of the one or more locations is a future location.

2. The media of claim 1, wherein each of the plurality of time slots are one hour in duration.

3. The media of claim 1, wherein the location data is provided by one or more of a global positioning system (GPS), an assisted GPS (AGPS), or network measurements.

4. The media of claim 1, wherein the predetermined period of time is five days, six days, or seven days.

5. The media of claim 1, wherein the probability distribution calculated for each of the one or more time-slot groups is used to predict future locations of the mobile device.

6. The media of claim 5, wherein a maximum likelihood estimation is used to predict the future locations of the mobile device.

7. The media of claim 1, wherein the one or more time-slot groups include work hours of weekdays, non work hours of weekdays, and weekends.

8. The media of claim 1, wherein identifying one or more locations from the location data further comprises:

grouping one or more geographical points of the location data together based on their respective location; and

determining a geographical place that represents each group of the one or more geographical points such that the geographical place corresponds to one of the one or more locations.

9. The media of claim 1, further comprising associating a first time slot and a second time slot of the plurality of time slots to form a first of the one or more time-slot groups.

10. One or more non-transitory computer-readable media having computer-executable instructions embodied thereon that, when executed, enable a computing device to perform a method of predicting a future location based on time clustering, the method comprising:

receiving location data for a particular mobile device, the location data corresponding to a predetermined period of time;

dividing the location data into one or more location groups, wherein each of the one or more location groups represents a unique location where the mobile device was located during the predetermined period of time;

dividing the predetermined period of time into two or more time slots;

determining from the two or more time slots that one or more first time slots and one or more second time slots have similar probability distributions;

based on the similar probability distributions, clustering the two or more time slots into one or more time-slot groups,

wherein the clustering includes associating the one or more first time slots with the one or more second time slots to form the one or more time-slot groups,

wherein the one or more time-slot groups include typical work hours of weekdays, non work hours of weekdays, and weekends; and

for each of the one or more time-slot groups, automatically calculating the probability distribution representing the probability that the mobile device will be in each of the unique locations during the times in each of the one or more time-slot groups, wherein at least one of the unique locations is a future location.

11. The media of claim 10, wherein the location data is received from a service provider associated with the mobile device, and wherein the location data is collected from one or more of GPS, AGPS, or network measurements.

12. The media of claim 10, wherein dividing the location data into one or more location groups further comprises spatially clustering data points from the location data to identify the one or more location groups.

13. The media of claim 10, wherein each of the time-slot groups comprises at least one time slot.

14. The media of claim 13, wherein the at least one time slot comprising each of the time-slot groups has a similar probability distribution to other time slots in the time slot group.

15. A method for predicting a future location based on time clustering, the method comprising:

utilizing historical location data associated with a particular mobile device to identify a plurality of locations where the mobile device has been located within a predetermined period of time;

dividing the predetermined period of time into a plurality of time slots;

for each time slot, automatically computing a probability distribution representing a probability that the mobile device is located at each of the plurality of locations throughout a duration of the time slot;

determining that a first time slot and a second time slot have a similar probability distribution;

associating the first time slot with the second time slot based on the similar probability distribution to create a first time cluster; and

for the first time cluster, automatically computing the probability distribution representing the probability that the mobile device is located at each of the plurality of locations throughout the duration of the time slots that comprise the first time cluster, wherein the probability distribution of the first time cluster is used to predict future locations of a user by way of the mobile device, wherein at least one of the plurality of locations is a future location.

16. The media of claim 15, further comprising receiving the historical location data corresponding to the mobile device, wherein the historical location data is provided by one or more of a GPS, an AGPS, or network measurements.

17. The media of claim 15, wherein the probability distribution calculated for the first time cluster is used to predict future locations of the mobile device.

18. The media of claim 17, wherein a maximum likelihood estimation is used to predict the future locations of the mobile device.

19. The media of claim 15, wherein the probability distributions are computed by an algorithm.