TAXONOMY-DRIVEN LUMPING FOR SEQUENCE MINING

• US 20110029475A1
• Filed: 08/03/2009
• Published: 02/03/2011
• Est. Priority Date: 08/03/2009
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Bonchi, Francesco, Donato, Debora, Gionis, Aristides
• Granted Patent: US 8,346,686 B2
• Time in Patent Office: Days
• US Class Current: 706/52
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/02 Knowledge representation; Symbolic representation

Abstract

Methods and apparatus are described for modeling sequences of events with Markov models whose states correspond to nodes in a provided taxonomy. Each state represents the events in the subtree under the corresponding node. By lumping observed events into states that correspond to internal nodes in the taxonomy, more compact models are achieved that are easier to understand and visualize, at the expense of a decrease in the data likelihood. The decision for selecting the best model is taken on the basis of two competing goals: maximizing the data likelihood, while minimizing the model complexity (i.e., the number of states).

Claims

1. A computer implemented method for modeling event data using a pre-existing taxonomy of events, the event data representing a plurality of sequences of events, each sequence comprising an order of events initiated by a corresponding user, each event mapping to a leaf node of the taxonomy, the method comprising:

identifying a plurality of candidate Markov models, each Markov model representing probabilities of a user transitioning from any first node in the Markov model to any second node in the Markov model according to the sequences of events, each Markov model formed from a subset of nodes in the taxonomy by merging selected nodes of the taxonomy into corresponding ancestor nodes of the taxonomy, wherein each event is represented by a node in each Markov model, and further wherein no Markov model contains both a particular node and an ancestor of that particular node;

measuring the fitness of the candidate Markov models with a fitness policy;

selecting at least some of the plurality of candidate Markov models with reference to the fitness measure and one or more resource constraints; and

choosing a preferred Markov model from the selected candidate Markov models with reference to an objective function.

2. The method of claim 1, wherein the objective function balances a likelihood score of each selected candidate Markov model with a number of states corresponding to the model.

3. The method of claim 2, wherein the objective function comprises the relation

4. The method of claim 1, further comprising partitioning the event data into multiple clusters, each cluster yielding a preferred Markov Model, and iteratively adjusting the clusters by reassigning each event sequence to the cluster whose preferred Markov Model maximizes the objective function for that sequence.

5. The method of claim 1 wherein selecting at least some of the candidate Markov models with reference to the fitness measure comprises selecting each selected candidate Markov model according to one of (i) a likelihood score of the selected candidate Markov model, (ii) a minimal number of nodes in the selected candidate Markov model, or (iii) an objective function score on the selected candidate Markov model.

6. The method of claim 1, further comprising displaying advertisements for a user based on a probability represented by the preferred Markov model.

7. The method of claim 1 wherein the event data comprises one of (i) search queries submitted to a search engine, (ii) purchases on an online commerce site, (iii) locations on a map, (iv) pages visited on one or more websites, or (v) user interactions with a software system.

8. A system for modeling event data using a pre-existing taxonomy of events, the event data representing a plurality of sequences of events, each sequence comprising an order of events initiated by a corresponding user, each event mapping to a leaf node of the taxonomy, the system comprising one or more computing devices configured to:

identify a plurality of candidate Markov models representing the probabilities of a user transitioning from any first node in the model to any second node in the model according to the sequences of events, each Markov model formed from a subset of nodes in the taxonomy by merging selected nodes of the taxonomy into corresponding ancestor nodes of the taxonomy, wherein each event is represented by a node in each Markov model, further wherein no Markov model contains both a particular node and an ancestor of that particular node;

measure the fitness of the candidate Markov models with a fitness policy;

select at least some of the plurality of candidate Markov models with reference to the fitness measure and one or more resource constraints; and

choose a preferred Markov model from the selected candidate Markov models with reference to an objective function.

9. The system of claim 8, wherein the objective function balances a likelihood score of each selected candidate Markov model with a number of states corresponding to the model.

10. The system of claim 9, wherein the objective function comprises the relation

11. The system of claim 8, wherein the one or more computing devices are further configured to partition the event data into multiple clusters, each cluster yielding a preferred Markov Model, and iteratively adjust the clusters by reassigning each event sequence to the cluster whose preferred Markov Model maximizes the objective function for that sequence.

12. The system of claim 8 wherein the one or more computing devices are configured to select at least some of the candidate Markov models with reference to the fitness measure by selecting each selected candidate Markov model according to one of (i) a likelihood score of the selected candidate Markov model, (ii) a minimal number of nodes in the selected candidate Markov model, or (iii) an objective function score on the selected candidate Markov model.

13. The system of claim 8, wherein the one or more computing devices are further configured to display advertisements for a user based on a probability represented by the preferred Markov model.

14. The system of claim 8 wherein the event data comprises one of (i) search queries submitted to a search engine, (ii) purchases on an online commerce site, (iii) locations on a map, (iv) pages visited on one or more websites, or (v) user interactions with a software system.

15. A computer program product for modeling event data using a pre-existing taxonomy of events, the event data representing a plurality of sequences of events, each sequence comprising an order of events initiated by a corresponding user, each event mapping to a leaf node of the taxonomy, comprising at least one computer-readable medium having computer instructions stored therein which are configured to cause one or more computing devices to:

identify a plurality of candidate Markov models representing the probabilities of a user transitioning from any first node in the model to any second node in the model according to the sequences of events, each Markov model formed from a subset of nodes in the taxonomy by merging selected nodes of the taxonomy into corresponding ancestor nodes of the taxonomy, wherein each event is represented by a node in each Markov model, further wherein no Markov model contains both a particular node and an ancestor of that particular node;

measure the fitness of the candidate Markov models with a fitness policy;

select at least some of the plurality of candidate Markov models with reference to the fitness measure and one or more resource constraints; and

choose a preferred Markov model from the selected candidate Markov models with reference to an objective function.

16. The computer program product of claim 15, wherein the objective function balances a likelihood score of each selected candidate Markov model with a number of states corresponding to the model.

17. The system of claim 16, wherein the objective function comprises the relation

18. The computer program product of claim 15, wherein the computer instructions are further configured to cause the one or more computing devices to partition the event data into multiple clusters, each cluster yielding a preferred Markov Model, and iteratively adjust the clusters by reassigning each event sequence to the cluster whose preferred Markov Model maximizes the objective function for that sequence.

19. The computer program product of claim 15 wherein the computer instructions are further configured to cause the one or more computing devices to select at least some of the candidate Markov models with reference to the fitness measure by selecting each selected candidate Markov model according to one of (i) a likelihood score of the selected candidate Markov model, (ii) a minimal number of nodes in the selected candidate Markov model, or (iii) an objective function score on the selected candidate Markov model.

20. The computer program product of claim 15 wherein the event data comprises one of (i) search queries submitted to a search engine (ii) purchases on an online commerce site (iii) locations or visited or trajectories taken on a map (iv) pages visited on a website (v) user interactions with a software system or user interface.