Predicting geographic location associated with network address

• US 7,937,336 B1
• Filed: 06/29/2007
• Issued: 05/03/2011
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Maynard-Zhang, Pedrito U., Minter, Samuel A., Mason, Llewellyn J., Lloyd, Daniel
• Primary Examiner(s): Sparks; Donald
• Assistant Examiner(s): CHANG, LI WU
• Application Number:
  US11/771,679
• Time in Patent Office: 1,404 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: H04L 2101/695 using masks or ranges of addresses
• CPC Class Codes: H04L 67/52 specially adapted for the location of the user terminal

Abstract

A decision tree is provided as a machine learning classifier to predict a user attribute, such as a geographical location of a user, based on a network address. More specifically, the decision tree is constructed via machine learning on a set of sample data that reflects a relationship between a network address and a user attribute of a “known user” whose profile information is recognizable. For a given network address, the decision tree can be used as a machine learning classifier to predict the most likely user attribute of a potential user. With the predicted attribute, a network service can target a group of potential users for various campaigns without recognizing the identities of the potential users.

Claims

1. A computer system for generating a decision tree for predicting a geographic location based on an internet protocol (IP) address associated with a user, the computer system comprising:

a data store containing a decision tree that is constructed to produce a predicted geographic location for an IP address associated with the user; and

a computing device in communication with the data store, wherein the computing device is configured to;

obtain a first set of sample data which includes IP addresses and user profile information, wherein the user profile information includes geographic location information correlated with an IP address;

train the decision tree with the first set of sample data, wherein the decision tree includes a number of leaf nodes and each leaf node of the decision tree associates at least one IP address and a predicted geographic location;

obtain a second set of sample data which includes an IP address and user profile information including geographic location information correlated with an IP address;

prune the trained decision tree with the second set of sample data;

obtain a third set of sample data which includes IP addresses and user profile information including geographic location information correlated with an IP address; and

qualify the decision tree with the third set of sample data, wherein after qualification, each leaf node is assigned a confidence number, wherein the confidence number indicates a degree of accuracy of the predicted geographic location associated with at least one IP address corresponding to the leaf node.

2. The computer system of claim 1, wherein the first set of sample data, the second set of sample data, and the third set of sample data are collected from recognized users whose profile information is readily available.

3. The computer system of claim 1, wherein the trained decision tree is pruned in order to produce an optimal decision tree which has a small number of nodes.

4. The computer system of claim 1, wherein the computing device is further configured to feed an IP address of a user into the qualified decision tree to produce the predicted geographic location of the user.

5. The computer system of claim 4, wherein the computing device is configured to ignore the predicted geographic location if the confidence number for the predicted geographic location of the user does not meet a threshold confidence level.

6. The computer system of claim 1, wherein the computing device is further configured to convert each IP address in the sample data into a bit representation.

7. The computer system of claim 6, wherein a path in the trained decision tree corresponds to the bit representation of at least one IP address.

8. A computer-implemented method for predicting a geographic location of a user who accesses a network-based service and whose identity is not recognized, the computer-implemented method comprising:

obtaining, with a computer, an internet protocol (IP) address of a user device with which the user interacts with the network-based service; and

providing, with the computer, the IP address of the user device to a classifier, and receiving from the classifier a predicted geographic location for the IP address provided;

wherein the classifier is a decision tree having a number of leaf nodes, wherein each leaf node associates at least one IP address with a predicted geographic location.

9. The computer-implemented method of claim 8, further comprising:

obtaining, with the computer, information about a campaign targeting a user group in a geographic location; and

transmitting the obtained information about the campaign to the user device.

10. The computer-implemented method of claim 8, further comprising converting the IP address into a finite number representation.

11. The computer-implemented method of claim 10, wherein the finite number representation is a 32-bit representation.

12. The computer-implemented method of claim 8, further comprising generating, with the computer, the decision tree through a machine learning based on a set of sample user data.

13. The computer-implemented method of claim 12, wherein the predicted geographic location is a most likely geographic location of the user based on the set of sample user data.

14. The computer-implemented method of claim 12, wherein the set of sample user data reflects a relationship between an IP address and a geographic location associated with a user.

15. The computer-implemented method of claim 8, wherein each leaf node of the decision tree records an accuracy number for the at least one IP address with respect to the associated predicted geographic location.

16. The computer-implemented method of claim 8, wherein the predicted geographic location of the user device is a country where the user device is located.

17. The computer-implemented method of claim 8, wherein the predicted geographic location of the user device is a state where the user device is located.

18. The computer-implemented method of claim 8, wherein the predicted geographic location reflects a preferred language in a locality of the user device.

19. The computer-implemented method of claim 8, wherein the classifier is constructed to return an accuracy number for the predicted geographic location associated with the identified IP address of the user device.

20. A computer system for determining a user group for a user whose identity is not recognized, the computer system comprising:

a data store containing a classifier which is constructed to produce a predicted geographic location for a given internet protocol (IP) address; and

a computing device in communication with the data store, wherein the computing device is configured to;

obtain an IP address which is generated from an interaction of a user device with a network-based service;

provide the IP address of the user device to the classifier;

receive, from the classifier, a predicted geographic location associated with the IP address of the user device; and

determine a user group that corresponds to the predicted geographic location;

wherein the classifier is a decision tree having a number of paths, wherein the decision tree includes a number of leaf nodes and each leaf node of the decision tree associates at least one IP address with a predicted geographic location.

21. The computer system of claim 20, wherein the computing device is configured to obtain campaign information targeted to the user group and to transmit the obtained campaign information to the user device.

22. The computer system of claim 20, wherein the decision tree is generated through machine learning on a set of sample user data.

23. The computer system of claim 22, wherein the set of sample user data reflects a relationship between an IP address and a geographic location associated with a user whose identity is recognized.

24. The computer system of claim 20, wherein each path in the decision tree corresponds to an IP address in a finite number representation.

25. A method of operating a computer to generate a decision tree for predicting a geographic location based on an internet protocol (IP) address associated with a user, the method comprising:

obtaining, with the computer, a first set of sample data which includes IP addresses and user profile information, wherein the user profile information includes geographic location information correlated with an IP address;

training, with the computer, a decision tree with the first set of sample data, wherein each leaf node of the decision tree associates at least one IP address and a predicted geographic location;

obtaining, with the computer, a second set of sample data which includes an IP address and user profile information including geographic location information correlated with an IP address;

pruning, with the computer, the trained decision tree with the second set of sample data;

obtaining, with the computer, a third set of sample data which includes IP addresses and user profile information including geographic location information correlated with an IP address; and

qualifying the decision tree with the third set of sample data, wherein after qualification, each leaf node is assigned a confidence number, wherein the confidence number indicates a degree of accuracy of the predicted geographic location associated with at least one IP address corresponding to the leaf node.

26. The method of claim 25, wherein the first set of sample data, the second set of sample data, and the third set of sample data are collected from recognized users whose profile information is readily available.

27. The method of claim 25, wherein the trained decision tree is pruned in order to produce an optimal decision tree which has a small number of nodes.

28. The method of claim 25, wherein the trained decision tree is pruned in order to cure an overfitting problem of the trained decision tree.

29. The method of claim 25, further comprising feeding, with the computer, an IP address of a user into the qualified decision tree to obtain a predicted geographic location of the user.

30. The method of claim 29, further comprising ignoring, with the computer, the predicted geographic location if the confidence number for the predicted geographic location does not meet a threshold confidence level.

31. The method of claim 25, further comprising converting each IP address in the sample data into a finite number representation.

32. The method of claim 25, wherein a path in the trained decision tree corresponds to at least one IP address in a bit representation.

33. A non-transitory, computer-readable medium having computer-executable components encoded thereon that, in response to execution by a computer, cause the computer to map a predicted geographic location of a user to an internet protocol (IP) address, the computer-executable components comprising:

a request process component for receiving information which is generated from a user'"'"'s activities over a network, wherein the information includes an IP address associated with the user; and

a classifier component for predicting a geographic location associated with the identified the IP address that is associated with the user;

wherein the predicted geographic location of the user is obtained from the classifier component; and

wherein the classifier component is a decision tree in which the decision tree includes a number of leaf nodes and each leaf node of the decision tree associates at least one IP address with a predicted geographic location.

34. The non-transitory computer-readable medium of claim 33, further comprising a machine learning component to build the classifier component.

35. The non-transitory computer-readable medium of claim 33, wherein the classifier component is a machine learning decision tree.

36. The non-transitory computer-readable medium of claim 33, wherein each path in the decision tree corresponds to an IP address in a finite number representation.

37. A method of operating a computer to provide information targeted to a user when the user clicks on a webpage, the method comprising:

receiving, with the computer, clickstream information which is generated as the user clicks on the webpage, wherein the clickstream information includes an internet protocol address of a user device;

identifying, with the computer, the internet protocol address from the clickstream information;

providing, with the computer, the identified internet protocol address to a classifier;

receiving, with the computer, a predicted geographic location from the classifier, wherein the classifier is a decision tree trained to predict a geographic location for a given internet protocol address, and wherein the decision tree includes a number of leaf nodes and each leaf node of the decision tree associates at least one IP address with a predicted geographic location;

obtaining, with the computer, information targeted to a group of users in the predicted geographic location; and

transmitting, with the computer, the obtained information to the user device.