The holy grail in process mining is a process model that scores perfectly in fitness, precision, generalization and simplicity. This is why there are not only many process discovery algorithms, but also many ways to calculate a numerical representation for these four quality dimensions. The thesis described in this extended abstract aims to answer the following question: Can we automate finding a process model that is optimal with respect to selectable but fixed measures of fitness, precision, generalization and simplicity? Process mining is about finding and analyzing a descriptive model for an existing and running business process. Most process mining techniques assume the existence of a so-called event log: A collection of recorded behavior of the business process in question. Process discovery algorithms take such an event log as input and return a formal model for the analysis and enhancement of the business process [1]. Naturally, each process discovery algorithm makes decisions during its execution that influence the model it returns. In turn, diferent process discovery algorithms may return diferent process models for the same event log as input. This poses the question of which process model is the best for the business process. To answer this question, four quality dimensions proved themselves useful for the process mining community: Fitness, precision, generalization and simplicity [2]. Fitness (or recall) evaluates how much of the behavior in the event log is featured in the process model, while precision measures how much of the behavior of the model is featured in the event log. Generalization reviews how well the process model is able to replay behavior of the business process that is not part of the event log. Simplicity (or complexity) judges how easy the process model is to understand. For each of these dimensions, there are several techniques that compute a value between 0 and 1 which indicates how good a process model performs for the specific quality dimension. A value close to 1 means that the process model performs (almost) perfectly. While there are many quality metrics for fitness [ 3, 4, 5, 6, 7, 8, 9] and precision [5, 6, 7, 8, 9, 10, 11, 12, 13], there are much fewer metrics defined for generalization [ 8, 9, 10, 11] and simplicity or complexity [14], as they are harder to formalize. Each of the aforementioned quality metrics perform their calculations diferently, and thus sometimes return diferent values for the same pair of model and event log.
Research regarding these quality metrics is still active, because already existing metrics
tend to lack desired features [15] or don’t correctly measure what they were created for [16].
Janssenswillen et al. [17] found a high correlation between fitness and precision, which raises
the desire for more independent metrics. The generalization metric, on the other hand, is
severely under-developed [18], since generalization is hard to define formally with having just
the event log as the representation for the system behavior. Simplicity has a similar problem, as
it aims to “prefer an easier model over a more complex one” [
With this process discovery algorithm, a user can specify any computable and deterministic quality metric to get a “perfect” process model with respect to their choices. The results of this process discovery technique become predictable and depend only on the chosen quality metrics. However, the aim of this process discovery algorithm is not to create actually perfect process models, since this is not possible with imperfect metrics. Instead, when optimizing over a quality metric, we can get a better understanding of which structures are rewarded or punished by the metric. This makes it easier to further investigate existing quality metrics and tailor them towards metrics that satisfactorily fulfill their purposes. For example, this can be achieved by creating an artificial system-model, as well as an event log for it, and checking to which extent the optimizing strategy is able to rediscover the original model (i.e. the rediscovery problem).
There are already some algorithms discovering process models that are optimal for some quality dimensions. The inductive miner [19] by design creates a process model with perfect iftness and keeps this process model simple by not allowing duplicate transition labels. The ILP miner [20] optimizes over fitness and precision and keeps the process model simple by not allowing duplicate or silent transitions. Because of the optimal results, these two discovery algorithms are widely used and researchers still try to improve them. However, they don’t ofer to consider metrics for generalization and don’t allow choosing the quality metrics whose scores should be optimized.
At first sight, the Evolutionary Tree Miner [ 21] seems strongly related to our ideas. It as
well optimizes over all four quality dimensions. However, it does not give a user the freedom
to choose any quality metric, but fixes the alignment-based fitness [
Our goal is to create a process discovery algorithm that is deterministic and able to optimize
over a set of quality measures defined by the user. To do so, our initial idea is to investigate
common optimization techniques and to formulate optimization problems for existing quality
metrics. We plan to start with the fitness metric using alignments [
We have already identified some challenges for our approach: First, most simplicity measures
are defined for BPMN or EPC, but we aim to produce free-choice workflow nets. However,
translating existing simplicity- or complexity measures [
Technol. 51 (2009) 610–626. doi:10.1016/j.infsof.2008.08.005.