Abstract. We consider the problem of discovering accurate, yet easily understandable models from complex event sequence data. Real world event data, such as production logs, exhibit complex behaviours, such as sequences, choices, loops, optionals, and combinations thereof, that make it hard to gain insight in what is going on and how we can improve the process. Current approaches do not solve this problem in a satisfying way as they either just tend to specific behaviours, or return models that are still too difficult to understand.
We formalize the problem in terms of the Minimum Description Length (MDL) principle, by which we say that the best model provides the shortest lossless description of the data. The resulting problem is NP-hard, and hence we propose the greedy Proseqo algorithm to discover good models from data. Proseqo iteratively simplifies the current description by removing nodes, edges, and applying patterns, until MDL tells us to stop. For whenever this result is still too complex, we propose ProSimple, which iteratively removes further edges until we satisfy a user-specified threshold.
Through an extensive set of experiments we show both methods perform very well in practice. They return simple models that reconstruct the ground truth well, need only little data to do so, are robust against noise, and scale well. A case study shows that, unlike the state of the art, we discover easily understandable models that capture the key aspects of the data generation process.