Location-based analytic platform and methods

• US 10,262,330 B2
• Filed: 03/24/2015
• Issued: 04/16/2019
• Est. Priority Date: 01/04/2013
• Status: Active Grant

• Current Assignee: PlaceIQ, Inc.
• Original Assignee: PlaceIQ, Inc.
• Inventors: Milton, Stephen, McCall, Duncan
• Primary Examiner(s): Burke, Jeff A
• Assistant Examiner(s): Vu, Thong
• Application Number:
  US14/667,371
• Publication Number:
  US 20150199699A1
• Time in Patent Office: 1,484 Days
• Field of Search: 707735, 707754, 709203, 709217
• CPC Class Codes: G06F 16/9537 Spatial or temporal dependent retrieval, e.g. spatiotemporal queries
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 30/0205 Location or geographical consideration
• CPC Class Codes: H04W 4/029 Location-based management or tracking services

Abstract

Provided is a process of learning an audience member function, the process including: obtaining a training set of geographic data describing geolocation histories of a plurality of mobile devices, wherein members of the training set are classified according to whether the respective member of the training set is a member of an audience; retrieving attributes of geolocations in the geolocation histories from a geographic information system; learning feature functions of an audience member function based on the training set, wherein at least some of the feature functions are a function of the retrieved attributes of geolocation, wherein the feature functions are learned, at least in part, by calculating a plurality of impurity measures for candidate feature functions and selecting one of the candidate feature functions based on the relative values of the impurity measures; and storing the feature functions of the audience member function in an audience repository.

Claims

1. A method of learning an audience member function, the method comprising:

obtaining, with one or more processors, a training set of geographic data describing geolocation histories of a plurality of mobile devices, wherein members of the training set are classified according to whether the respective member of the training set is a member of an audience, and wherein

each geolocation history corresponds to a different user or computing device selected from among a set of more than 100,000 geolocation histories; and

at least some geolocation histories each comprise a respective plurality of timestamped geolocations collected over more than a week;

retrieving, with one or more processors, attributes of geolocations in the geolocation histories from a geographic information system, wherein, for at least some geolocations in the geolocation histories, a plurality of attributes are retrieved for respective geolocations, the attributes each indicating a propensity of users to exhibit a different respective behavior described by the respective attribute in a respective geolocation;

learning, with one or more processors, feature functions of an audience member function based on the training set, wherein at least some of the feature functions are a function of the retrieved attributes of geolocation, wherein the feature functions are learned, at least in part, by calculating a plurality of impurity measures for candidate feature functions and selecting one of the candidate feature functions based on the relative values of the impurity measures, and wherein;

the audience member function is configured to output a score indicative of a probability that a given user is in, or classification of the given user in, the audience;

the audience member function is configured to output the score based on a given input vector, corresponding to the given user;

the given input vector is based on a given geolocation history of the user and has a plurality of dimensions, at least some of the plurality of dimensions being based on at least some of the plurality of attributes; and

the feature functions are learned, at least in part, by performing steps comprising;

selecting a subset of the training set that has a selected dimension larger than a threshold value;

for each of a plurality of other dimensions, and for each of a plurality of values of each of the plurality of other dimensions, calculating an impurity measure corresponding to respective value in the respective other dimension; and

selecting another dimension and a value based on the smallest impurity measure among the calculated impurity measures; and

storing, with one or more processors, the feature functions of the audience member function in an audience repository.

2. The method of claim 1, comprising:

after storing the feature functions of the audience member function in the audience repository, performing steps comprising;

receiving data describing a content request from a given mobile device at a given time at a given geographic location;

retrieving the audience member function from the audience repository;

determining audience membership, at least in part, by inputting the given device, the given time, and the given geographic location into the audience membership function;

in response to the determination, selecting content corresponding to the audience;

causing the selected content to be sent to the given mobile device.

3. The method of claim 1, wherein:

the audience member function is a weighted combination of the feature functions.

4. The method of claim 1, wherein feature functions include an adaptive basis function learned according to the training set.

5. The method of claim 1, wherein the impurity measure is based on an entropy of the subset greater than the respective value in the respective other dimension.

6. The method of claim 1, comprising:

determining that more than a threshold amount of training set is greater than the respective value in the respective dimension.

7. The method of claim 1, comprising:

before calculating impurity measures, determining both that at least some of the subset is part of the audience and that at least some of the subset is not part of the audience.

8. The method of claim 1, comprising:

sampling the training set a plurality of times to form a plurality of subsets;

learning intermediate feature functions on each of the plurality of subsets; and

determining aggregate feature functions from the intermediate feature functions.

9. The method of claim 1, wherein:

geolocations in the training set are designated with geographic tiles corresponding to different geographic areas;

or

geolocations in the training set are designated with polygons with latitude and longitude vertices corresponding to places of interest.

10. The method of claim 1, wherein:

the training set of geographic data comprises geolocations associated with more than 100 billion content requests from user computing devices; and

learning the audience member function comprises;

mapping candidate splits to one set of computing nodes; and

reducing impurity measures from resulting regions with a different set of computing nodes.

11. The method of claim 4, wherein:

learning the adaptive basis function comprises steps for determining probabilities with an adaptive basis function.

12. The method of claim 1, wherein:

the given input vector has more than 100 dimensions.

13. A tangible, non-transitory, machine-readable medium storing instructions that when executed by one or more processors effectuate operations comprising:

obtaining, with one or more processors, a training set of geographic data describing geolocation histories of a plurality of mobile devices, wherein members of the training set are classified according to whether the respective member of the training set is a member of an audience, and wherein

each geolocation history corresponds to a different user or computing device selected from among a set of more than 100,000 geolocation histories; and

at least some geolocation histories each comprise a respective plurality of timestamped geolocations collected over more than a week;

retrieving, with one or more processors, attributes of geolocations in the geolocation histories from a geographic information system, wherein, for at least some geolocations in the geolocation histories, a plurality of attributes are retrieved for respective geolocations, the attributes each indicating a propensity of users to exhibit a different respective behavior described by the respective attribute in a respective geolocation;

learning, with one or more processors, feature functions of an audience member function based on the training set, wherein at least some of the feature functions are a function of the retrieved attributes of geolocation, wherein the feature functions are learned, at least in part, by calculating a plurality of impurity measures for candidate feature functions and selecting one of the candidate feature functions based on the relative values of the impurity measures, and wherein;

the audience member function is configured to output a score indicative of a probability that a given user is in, or classification of the given user in, the audience;

the audience member function is configured to output the score based on a given input vector, corresponding to the given user;

the given input vector is based on a given geolocation history of the user and has a plurality of dimensions, at least some of the plurality of dimensions being based on at least some of the plurality of attributes; and

the feature functions are learned, at least in part, by performing steps comprising;

selecting a subset of the training set that has a selected dimension larger than a threshold value;

for each of a plurality of other dimensions, and for each of a plurality of values of each of the plurality of other dimensions, calculating an impurity measure corresponding to respective value in the respective other dimension; and

selecting another dimension and a value based on the smallest impurity measure among the calculated impurity measures; and

storing, with one or more processors, the feature functions of the audience member function in an audience repository.

14. The medium of claim 13, the operations comprising:

after storing the feature functions of the audience member function in the audience repository, performing steps comprising;

receiving data describing a content request from a given mobile device at a given time at a given geographic location;

retrieving the audience member function from the audience repository;

determining audience membership, at least in part, by inputting the given device, the given time, and the given geographic location into the audience membership function;

in response to the determination, selecting content corresponding to the audience;

causing the selected content to be sent to the given mobile device.

15. The medium of claim 13, wherein:

the audience member function is a weighted combination of the feature functions.

16. The medium of claim 13, wherein feature functions include an adaptive basis function learned according to the training set.

17. The medium of claim 16, wherein:

learning the adaptive basis function comprises steps for determining probabilities with an adaptive basis function.

18. The medium of claim 13, wherein the impurity measure is based on an entropy of the subset greater than the respective value in the respective other dimension.

19. The medium of claim 13, the operations comprising:

determining that more than a threshold amount of training set is greater than the respective value in the respective dimension.

20. The medium of claim 13, the operations comprising:

before calculating impurity measures, determining both that at least some of the subset is part of the audience and that at least some of the subset is not part of the audience.

21. The medium of claim 13, the operations comprising:

sampling the training set a plurality of times to form a plurality of subsets;

learning intermediate feature functions on each of the plurality of subsets; and

determining aggregate feature functions from the intermediate feature functions.

22. The medium of claim 13, wherein:

geolocations in the training set are designated with geographic tiles corresponding to different geographic areas;

or

geolocations in the training set are designated with polygons with latitude and longitude vertices corresponding to places of interest.

23. The medium of claim 13, wherein:

the training set of geographic data comprises geolocations associated with more than 100 billion content requests from user computing devices; and

learning the audience member function comprises;

mapping candidate splits to one set of computing nodes; and

reducing impurity measures from resulting regions with a different set of computing nodes.

24. The medium of claim 13, wherein:

the given input vector has more than 100 dimensions.