Analyzing mobile-device location histories to characterize consumer behavior

• US 10,235,683 B2
• Filed: 07/17/2015
• Issued: 03/19/2019
• Est. Priority Date: 07/18/2014
• Status: Active Grant

• Current Assignee: PlaceIQ, Inc.
• Original Assignee: PlaceIQ, Inc.
• Inventors: Milton, Stephen, McCall, Duncan
• Primary Examiner(s): Chace, Christian
• Assistant Examiner(s): Buss, Benjamin J
• Application Number:
  US14/802,020
• Publication Number:
  US 20160019465A1
• Time in Patent Office: 1,341 Days
• Field of Search: None
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: G06Q 30/0201 Market modelling; Market analysis; Collecting market data
• CPC Class Codes: H04W 4/021 Services related to particular areas, e.g. point of interest [POI] services, venue services or geofences
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

Provided is a process of inferring a user'"'"'s reason for movement between geolocations sensed by a mobile device of the user, the process including: obtaining a history of time-stamped geolocations of a user; selecting a plurality of geographic areas based on each of the selected geographic areas including at least one of the time-stamped geolocations; obtaining a probabilistic model specifying parameters comprising: a plurality of candidate user events, each candidate user event being an underlying potential reason why the user moved between geographic locations; probabilities of the user transitioning between each pair of the candidate user events; and probabilities of obtaining a geolocation reported by the computing devices associated with the user in each of the plurality of geographic areas following occurrence of each of the candidate user events; inferring, with one or more processors, one of the candidate user events.

Claims

1. A method of inferring a user'"'"'s reason for movement between geolocations sensed by a mobile device of the user, the method comprising:

obtaining, with one or more processors, a history of time-stamped geolocations of a user, the time-stamped geolocations being obtained based on data from one or more computing devices associated with the user and reported to one or more remote server systems;

selecting, with one or more processors, a plurality of geographic areas based on each of the selected geographic areas including at least one of the time-stamped geolocations;

associating, with one or more processors, the selected geographic areas with the time-stamp of the included geolocation to establish a time series sequence of the geographic areas;

training, with one or more processors, a probabilistic model, wherein training the probabilistic model comprises;

obtaining an initial set of probabilities for the model;

selecting a training set of time series sequences of geographic areas for the user, wherein the training set comprises at least a portion of the established time series sequence of the geographic areas;

selecting a plurality of user events, each user event being an underlying potential reason why users move between geographic locations;

calculating a plurality of probabilities of the model by iterating steps comprising;

estimating, for each pairwise combination of user events in the plurality of user events, a probability of the user transitioning between the pairwise combination of the user events based on the training set and, in a first iteration, the initial set of probabilities and, in a subsequent iteration, a revised set of probabilities;

normalizing the estimated probabilities of the user transitioning between the pairwise combinations of user events to form revised probabilities of the user transitioning between the pairwise combinations of user events;

estimating the probabilities of obtaining a geolocation reported by the computing devices associated with the user based on the training set and the revised probabilities of the user transitioning between the pairwise combinations of the user events; and

normalizing the estimated probabilities of obtaining a geolocation reported by the computing devices associated with the user to form revised probabilities of obtaining a geolocation reported by the computing devices associated with the user,

wherein the revised set of probabilities includes both the revised probabilities of the user transitioning between the pairwise combinations of the user events and the revised probabilities of obtaining a geolocation reported by the computing devices associated with the user;

determining, with the trained probabilistic model, parameters for an input time series sequence of geographic areas based on a recent subset of time-stamped geolocations of the user in the history, the parameters comprising;

a plurality of candidate user events from the plurality of user events, each candidate user event being an underlying potential reason why the user moved between geographic locations;

probabilities of the user transitioning between each pair of the candidate user events; and

probabilities of obtaining a geolocation reported by the computing devices associated with the user in each of the geographic areas in the input time series sequence of the geographic areas following occurrence of each of the candidate user events;

inferring, with one or more processors, a reason why the user transitioned between a given sequential pair of the geographic areas in the input time series sequence of geographic areas responsive to the parameters determined by the trained probabilistic model, wherein the reason comprises one of the candidate user events; and

storing, with one or more processors, the inferred reason in memory.

2. The method of claim 1, wherein:

the training set of time series sequences of geographic areas include at least three geographic areas;

the geographic areas are obtained by clustering geolocations in the history of time-stamped geolocations of the user;

the history of time-stamped geolocations of the user comprise 20 or more geolocations having time-stamps spanning a duration of more than one hour;

the trained probabilistic model includes a two dimensional probability matrix with at least N(N−

1) of the probabilities of the user transitioning between each pair of the candidate user events, where N is a number of the candidate user events within the plurality of user events;

the trained probabilistic model includes at least N(M−

1) of the probabilities of obtaining the geolocation reported by the computing devices associated with the user, where M is a number of geographic areas in the input time series sequence of geographic areas;

inferring the reason why the user transitioned between the given sequential pair of the geographic areas in the input time series sequence of geographic areas comprises, inferring a sequence of two or more of the candidate user events that account for why the user transitioned between three consecutive geographic areas in the input time series sequence of geographic areas by performing operations comprising;

for a given one of inferred events;

calculating most probable candidate sequences of the events that lead to a respective sequentially previous candidate event in the inferred sequence for each of the candidate events; and

selecting the given one of the inferred events based on the calculated probabilities of the most probable candidate sequences for the previous candidate events, respective probabilities of transitioning to each candidate event for the given one of the inferred events, and respective probabilities of obtaining a geolocation in the recent subset of time-stamped geolocations of the user in the history in a geographic area in the input time series sequence of geographic areas corresponding temporally to the given one of the inferred events.

3. The method of claim 1, wherein:

the obtained geolocations are tiles in which the user was determined to be located.

4. The method of claim 1, wherein:

the obtained geolocations are businesses in which the user was determined to be located.

5. The method of claim 1, wherein:

the obtained geolocations are polygons in which the user was determined to be located.

6. The method of claim 1, wherein:

selecting a plurality of geographic areas based on each of the selected geographic areas including at least one of the time-stamped geolocations comprises geographically clustering at least some geolocations in the history of time-stamped geolocations of the user.

7. The method of claim 6, wherein:

geographically clustering at least some geolocations in the history comprises;

determining that a subset of the at least some geolocations have at least a threshold number of other geolocations in the subset within a threshold geographic distance to define core geolocations.

8. The method of claim 7, comprising:

determining that another subset of the at least some geolocations are within the threshold distance from a core geolocation to define reachable geolocations.

9. The method of claim 8, comprising:

grouping subsets of the core geolocations by determining that respective core geolocations in respective subsets form a connected graph in which each core geolocation in the connected graph is within the threshold distance of another core geolocation in the connected graph; and

for each subset, adding reachable geolocations within the threshold distance to a core geolocation in the respective subset to the respective subset to define a respective cluster, wherein at least some of the selected geographic areas correspond to a convex hull of a respective cluster.

10. The method of claim 1, comprising:

obtaining survey results of users in which survey participants identify sequences of the candidate events and geolocations the survey participants visited following the candidate events; and

wherein training the probabilistic model comprises calculating, based in part on the survey results;

the probabilities of the user transitioning between pairwise combinations of the user events based in part on the identified sequences of the candidate events; and

the probabilities of obtaining a geolocation reported by the computing devices associated with the user based in part on the identified sequences of geolocations.

11. The method of claim 1, comprising:

determining that an amount of change between consecutive sets of revised probabilities is less than a threshold amount; and

in response to determining that the amount of change between consecutive sets of revised probabilities is less than the threshold amount, ceasing to repeatedly perform the steps.

12. The method of claim 1, wherein estimating the probabilities of the user transitioning between the pairwise combinations of user events based on the initial set of probabilities or the revised set of probabilities comprises:

for each of the probabilities of the user transitioning between the pairwise combinations of user events, performing steps comprising;

for each of a plurality of pairs of sequential geographic areas in the training set, calculating a component probability of the user transitioning between the respective pair of user events and a highest probability of the respective pair of sequential geographic areas based on the initial set of probabilities or the revised set of probabilities if the revised set of probabilities is available; and

dividing a sum of the component probabilities by a sum of the highest probabilities to form an estimated probability of the user transitioning between the respective pair of the user events.

13. The method of claim 1, wherein estimating the probabilities of obtaining a geolocation reported by the computing devices associated with the user comprises:

for each given geographic area in the training set, for each given user event, and for each of a plurality of pairs of sequential geographic areas in the training set, calculating a component probability of the respective pair of sequential geographic areas assuming the respective given geographic area followed the respective given user event and a highest probability of the respective pair of sequential geographic areas occurring in the set based on the initial set of probabilities or the revised set of probabilities if the revised set of probabilities is available; and

dividing a sum of the component probabilities by a sum of the highest probabilities to form an estimated probability of obtaining a geolocation reported by the computing devices associated with the user in the respective given geographic area assuming the respective given user event occurred.

14. The method of claim 1, wherein the training the probabilistic model comprises:

estimating probabilities of the user transitioning to each user event following each pairwise combination of user events, wherein

the parameters determined with the trained probabilistic model comprise probabilities of the user transitioning to each candidate user event after each pair of the candidate user events.

15. The method of claim 1, wherein the trained probabilistic model comprises:

a two dimensional probability matrix with at least N(N−

1) of the probabilities of the user transitioning between each pair of the candidate user events.

16. The method of claim 1, comprising:

receiving, via a network, a request for content, the request including an identifier of the user; and

selecting the content based on the inferred reason.

17. The method of claim 1, comprising:

bidding in an auction for an opportunity to present an advertisement to the user based on the inferred reason.

18. The method of claim 1, comprising:

inferring respective reasons why a plurality of users each transitioned between geographic areas, wherein the reasons for each respective users are inferred concurrently on different processors, wherein each of the processors is coupled to system memory storing parameters for different geographic areas.

19. The method of claim 1, wherein inferring the reason why the user transitioned between the given sequential pair of the geographic areas comprises, inferring a sequence of two or more of the candidate user events that account for why the user transitioned between three consecutive geographic areas in the input time series sequence of geographic areas.

20. The method of claim 19, comprising for a given one of inferred events:

calculating most probable candidate sequences of the events that lead to a respective sequentially previous candidate event in the inferred sequence for each of the candidate events; and

selecting the given one of the inferred events based on the calculated probabilities of the most probable candidate sequences for the previous candidate events, respective probabilities of transitioning to each candidate event for the given one of the inferred events, and respective probabilities of obtaining a geolocation in the history in the geographic area corresponding temporally to the given one of the inferred events.

21. The method of claim 1, further comprising:

concurrently training a plurality of probabilistic models for a plurality of different users with a plurality of different processors, each concurrently trained probabilistic model associated with respective ones of the plurality of users and operable to infer a reason why the respective user transitioned between a sequential pair of geographic areas;

receiving a plurality of sets of time-stamped geolocations corresponding to responsive ones of at least some of the different users;

determining, for each of the at least some of the different users, an input time series sequences of geographic areas from at least one corresponding set of time-stamped geolocations in the plurality of sets of time-stamped geolocations;

selecting, for each of the at least some of the different users, the respective one of the trained probabilistic models;

currently determining with a plurality of different processors, parameters for the input time series sequences of geographic areas corresponding to the at least some of the different users with the respective ones of the selected trained probabilistic models; and

inferring respective reasons why the different users each transitioned between geographic areas based on the parameters for the input time series sequences of geographic areas corresponding to the at least some of the different users with the respective ones of the selected trained probabilistic models, wherein the reasons for each of the different users are inferred concurrently on different processors.

22. The method of claim 1, wherein:

at least part of the method is executed concurrently for more than 100,000 users;

associating the selected geographic areas with the time-stamp of the included geolocation to establish a time series sequence of the geographic areas comprises establishing augmented time series sequences by;

precomputing one or more records including contextual information of at least some of the one or more computing devices associated with the user or the geographic areas;

storing, before establishing the time series sequence, the precomputing records in a distributed cache of a computing cluster configured to execute a distributed analysis among a plurality of computing devices of the computing cluster; and

establishing the time series sequence by refencing the precomputed records stored in the distributed cache.

23. The method of claim 1, further comprising:

steps for passing contextual information needed for each tile or device implicated by a portion of an analysis.

24. The method of claim 1, wherein training the probabilistic model comprises:

steps for expediting training.

25. A system, comprising:

one or more processors; and

memory storing instructions that when executed by at least some of the processors effectuate operations comprising;

obtaining a history of time-stamped geolocations of a user, the time-stamped geolocations being obtained based on data from one or more computing devices associated with the user and reported to one or more remote server systems;

selecting a plurality of geographic areas based on each of the selected geographic areas including at least one of the time-stamped geolocations;

associating the selected geographic areas with the time-stamp of the included geolocation to establish a time series sequence of the geographic areas;

training a probabilistic model, wherein training the probabilistic model comprises;

obtaining an initial set of probabilities for the model;

selecting a training set of time series sequences of geographic areas for the user, wherein the training set comprises at least a portion of the established time series sequence of the geographic areas;

selecting a plurality of user events, each user event being an underlying potential reason why users move between geographic locations;

calculating a plurality of probabilities of the model by iterating steps comprising;

estimating, for each pairwise combination of user events in the plurality of user events, a probability of the user transitioning between the pairwise combination of the user events based on the training set and, in a first iteration, the initial set of probabilities and, in a subsequent iteration, a revised set of probabilities;

normalizing the estimated probabilities of the user transitioning between the pairwise combinations of user events to form revised probabilities of the user transitioning between the pairwise combinations of user events;

estimating the probabilities of obtaining a geolocation reported by the computing devices associated with the user based on the training set and the revised probabilities of the user transitioning between the pairwise combinations of the user events; and

normalizing the estimated probabilities of obtaining a geolocation reported by the computing devices associated with the user to form revised probabilities of obtaining a geolocation reported by the computing devices associated with the user, wherein the revised set of probabilities includes both the revised probabilities of the user transitioning between the pairwise combinations of the user events and the revised probabilities of obtaining a geolocation reported by the computing devices associated with the user;

determining, with the trained probabilistic model, parameters for an input time series sequence of geographic areas based on a recent subset of time-stamped geolocations of the user in the history, the parameters comprising;

a plurality of candidate user events from the plurality of user events, each candidate user event being an underlying potential reason why the user moved between geographic locations;

probabilities of the user transitioning between each pair of the candidate user events; and

probabilities of obtaining a geolocation reported by the computing devices associated with the user in each of the geographic areas in the input time series sequence of the geographic areas following occurrence of each of the candidate user events;

inferring, with one or more processors, a reason why the user transitioned between a given sequential pair of the geographic areas in the input time series sequence of geographic areas responsive to the parameters determined by the trained probabilistic model, wherein the reason comprises one of the candidate user events; and

storing the inferred reason in memory.