Clickstream Purchase Prediction Using Hidden Markov Models

• US 20150269609A1
• Filed: 12/23/2014
• Published: 09/24/2015
• Est. Priority Date: 03/18/2014
• Status: Active Grant

• Current Assignee: Staples, Inc.
• Original Assignee: Staples, Inc.
• Inventors: Mehanian, Courosh, Dangaltchev, Tchavdar, Kumara, Karthik, Pan, Jing, Wee, Timothy
• Granted Patent: US 11,042,898 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06Q 30/0246 Traffic
• CPC Class Codes: G06Q 30/0254 based on statistics

Abstract

Technology for predicting online user shopping behavior, such as whether a user will purchase a product, is described. An example method includes receiving current session data describing a current session for a current user, extracting a current clickstream from the current session data classifying the current clickstream as a purchase clickstream or a non-purchase clickstream by processing the current clickstream using one or more sets of Hidden Markov Model parameters produced by one or more Hidden Markov Models, and computing, using the one or more computing devices, a purchase probability that the current user will purchase a product during the current session based on the classifying.

Claims

1. A computer-implemented method comprising:

receiving, using one or more computing devices, clickstreams for past users reflecting past online sessions of the past users, the clickstreams including purchase clickstreams and non-purchase clickstreams;

encoding, using the one or more computing devices, the clickstreams into encoded clickstreams;

training, using the one or more computing devices, a purchase Hidden Markov Model (HMM) and a non-purchase HMM based on the encoded clickstreams, the purchase HMM producing a set of purchase HMM parameters and the non-purchase HMM producing a set of non-purchase HMM parameters;

receiving, using the one or more computing devices, current session data describing a current session for a current user, the current session including a current clickstream of the current user;

encoding, using the one or more computing devices, the current clickstream into an encoded current clickstream;

classifying, using the one or more computing devices, the encoded current clickstream by processing the encoded current clickstream using the set of purchase HMM parameters and the set of non-purchase HMM parameters to determine a purchase likelihood and a non-purchase likelihood, respectively;

computing, using the one or more computing devices, a purchase probability that the current user will purchase a product during the current session based on the purchase likelihood and the non-purchase likelihood; and

determining, using the one or more computing devices, an offer to present to the current user based on the probability, the offer being selected from a set of offers to sell a product using an incentive.

2. The computer-implemented method of claim 1, wherein encoding the clickstreams into the encoded clickstreams includes:

encoding the clickstreams into sequences of webpage types, the webpage types including a product-type webpage; and

parsing subsequences from the encoded clickstreams, the subsequences ending in the product-type webpage.

3. The computer-implemented method of claim 1, wherein:

classifying, using the one or more computing devices, the encoded current clickstream includes calculating, using the one or more computing devices, forward variables based on the set of purchase HMM parameters and the set of non-purchase HMM parameters using a Forward Recursion Algorithm and feeding the forward variables into a classifier.

4. A computer-implemented method comprising:

receiving, using one or more computing devices, current session data describing a current session for a current user;

extracting, using the one or more computing devices, a current clickstream from the current session data;

classifying, using the one or more computing devices, the current clickstream as a purchase clickstream or a non-purchase clickstream by processing the current clickstream using one or more sets of Hidden Markov Model (HMM) parameters produced by one or more HMMs; and

computing, using the one or more computing devices, a purchase probability that the current user will purchase a product during the current session based on the classifying.

5. The computer-implemented method of claim 4, wherein the HMMs include a purchase HMM and a non-purchase HMM, and the method further comprises:

receiving, using one or more computing devices, clickstreams for past users reflecting past online sessions of the past users, the clickstreams including purchase clickstreams and non-purchase clickstreams;

encoding, using the one or more computing devices, the clickstreams into encoded clickstreams; and

training, using the one or more computing devices, the purchase HMM and the non-purchase HMM based on the encoded clickstreams, the purchase HMM producing a set of purchase HMM parameters and the non-purchase HMM producing a set of non-purchase HMM parameters, the one or more sets of HMM parameters including the set of purchase HMM parameters and the set of non-purchase HMM parameters.

6. The computer-implemented method of claim 5, wherein encoding the clickstreams into the encoded clickstreams includes:

encoding the clickstreams into sequences of webpage types, the webpage types including a product-type webpage; and

parsing subsequences from the encoded clickstreams, the subsequences ending in the product-type webpage.

7. The computer-implemented method of claim 5, wherein training, using the one or more computing devices, the purchase HMM and the non-purchase HMM further includes training the purchase HMM and the non-purchase HMM using a Baum-Welch Algorithm.

8. The computer-implemented method of claim 4, wherein classifying, using the one or more computing devices, the current clickstream includes scoring, using the one or more computing devices, the current clickstream to determine a likelihood that the current clickstream corresponds to an output of the one or more HMMs using a Forward Recursion Algorithm.

9. The computer-implemented method of claim 8, wherein classifying, using the one or more computing devices, the current clickstream further comprises feeding, using the one or more computing devices, an output of the Forward Recursion Algorithm into a Neural Network Classifier.

10. The computer-implemented method of claim 4, further comprising:

determining, using the one or more computing devices, a customized offer to present to the current user based on the purchase probability; and

presenting, using the one or more computing devices, the customized offer to the current user on a user device, the customized offer including an offer to sell the product using an incentive to the current user.

11. The computer-implemented method of claim 4, wherein the customized offer is selected from a set of possible offers based on the purchase probability and one or more of a maximum expected revenue, a maximum expected profit, and a maximum number of expected sales that would result from a sale of the product at the discounted price.

12. The computer-implemented method of claim 4, further comprising:

computing, using the one or more computing devices, an average precision score as a function of a number of hidden states used by the one or more HMMs;

determining, using the one or more computing devices, the number of hidden states corresponding to a highest value of the average precision score; and

tuning, using the one or more computing devices, a hyperparameter used by the one or more Hidden Markov Models corresponding to the highest value of the average precision score.

13. A computing system comprising:

one or more processors;

one or more memories;

a production encoder module stored by the one or more memories and executable by the one or more processors to receive current session data describing a current session for a current user and extract a current clickstream from the current session data; and

a classifier stored by the one or more memories and executable by the one or more processors to classify current session data describing a current session for a current user, extract a current clickstream from the current session data, classify the current clickstream as a purchase clickstream or a non-purchase clickstream by processing the current clickstream using one or more sets of Hidden Markov Model (HMM) parameters produced by one or more HMMs, and compute a purchase probability that the current user will purchase a product during the current session based on the classifying.

14. The computing system of claim 13, wherein the HMMs include a purchase HMM and a non-purchase HMM, and the system further comprises:

a training encoder module stored by the one or more memories and executable by the one or more processors to receive clickstreams for past users reflecting past online sessions of the past users, the clickstreams including purchase clickstreams and non-purchase clickstreams and encode the clickstreams into encoded clickstreams; and

a Hidden Markov Model training module stored by the one or more memories and executable by the one or more processors to train the purchase HMM and the non-purchase HMM based on the encoded clickstreams, the purchase HMM producing a set of purchase HMM parameters and the non-purchase HMM producing a set of non-purchase HMM parameters, the one or more sets of HMM parameters including the set of purchase HMM parameters and the set of non-purchase HMM parameters.

15. The computing system of claim 14, wherein the training encoder module is further configured to encode the clickstreams into sequences of webpage types, the webpage types including a product-type webpage, and to parse subsequences from the encoded clickstreams, the subsequences ending in the product-type webpage.

16. The computing system of claim 14, wherein the Hidden Markov Model training module is further configured to train the purchase HMM and the non-purchase HMM using a Baum-Welch Algorithm.

17. The computing system of claim 13, wherein the classifier is further configured to classify the current clickstream by scoring the current clickstream to determine a likelihood that the current clickstream corresponds to an output of the one or more HMMs using a Forward Recursion Algorithm.

18. The computing system of claim 17, wherein the classifier is further configured to classify the current clickstream by feeding an output of the Forward Recursion Algorithm into a classifier.

19. The computing system of claim 13, further comprising an offer module stored by the one or more memories and executable by the one or more processors to determine a customized offer to present to the current user based on the purchase probability and present the customized offer to the current user on a user device, the customized offer including an offer to sell the product using an incentive to the current user.

20. The computing system of claim 19, wherein the customized offer is selected from a set of possible offers based on the purchase probability and one or more of a maximum expected revenue, a maximum expected profit, and a maximum number of expected sales that would result from a sale of the product at the discounted price.

21. The computing system of claim 13, further comprising an analysis module stored by the one or more memories and executable by the one or more processors to:

compute an average precision score as a function of a number of hidden states used by the one or more HMMs;

determine the number of hidden states corresponding to a highest value of the average precision score; and

tune a hyperparameter used by the one or more Hidden Markov Models corresponding to the highest value of the average precision score.