US Patent 8346686 Taxonomy-driven lumping for sequence mining

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).