The holy grail in process mining is a process discovery algorithm that, given an event log, produces fitting, precise, properly generalizing and simple process models. Within the field of process mining, conformance checking is considered to be anything where observed behaviour, e.g., in the form of event logs or event streams, needs to be related to already modelled behaviour. In the conformance checking domain, the relation between an event log and a model is typically quantified using fitness, precision and generalization. In this paper, we present metrics for fitness, precision and generalization, based on alignments and the newer concept named anti-alignments. The work summarized here is presented in detail in [vdAAvD12, vDCC16]. The holy grail in process mining is a process discovery algorithm that, given an event log, produces fitting, precise, properly generalizing and simple process models. Event logs are generally considered to be accurate representations of the behaviour of a system in such as way that each event refers to an activity that was executed in the context of a case. By deriving a process model from such an event log, process discovery algorithms give insights into the underlying system. There has been always a discussion on how to interpret process discovery results, i.e. how does the produced model relate to the actual, but unknown, system in four quality dimensions [BvDvdA14]: Fitness quantifies how much of the observed behaviour is captured by the model, Generalization quantifies how well the model explains unobserved system behaviour, Precision quantifies how much behavior exists in the model that was not observed, and Simplicity quantifies the complexity of the model and is not considered in this paper. Consider an example event log in Table 1, together with several process models as depicted in Figure 1 to 4. The model in Figure 1 shows the “ideal” process discovery result, i.e. the model that is fitting, fairly precise and properly generalizing. Models 2 and 3 are chosen such that they score poorly on at least one of the dimensions precision or generalization, while model 4 scores around 0.5 in both dimensions.
Trace hA; B; D; E; Ii hA;C; D; G; H; F; Ii hA;C; G; D; H; F; Ii hA;C; H; D; F; Ii hA;C; D; H; F; Ii Alignment based Fitness. A model fits a log if all traces in the log can be replayed by the model. A fitness metric quantifies the fit of a log in a model. Several different measures exist for this quality dimension [BvDvdA14, Ad14, vdAAvD12, and references therein]. The most recent and robust technique uses a cost-based alignment between the traces in the event log and the most optimal execution of the process model [Ad14]. An alignment is a sequence of pairs that refer to an event from a trace and a transition in the model, or elements indicating deviations. The projection of these pairs onto the first element yields the trace from the log and the projection onto the second elements yields a firing sequence in the model. Each pair in an alignment is called a move. If both parts of the pair are equally labelled, we call such a pair a synchronous move. A model move is a pair t , i.e. a transition is fired, but no corresponding event appeared in the log and a log move is a pair a , i.e. an event appears in the log, but there is no corresponding transition to be fired in the model.
Consider for example the trace hA;C; H; D; F; Ii and model 2. The optimal alignment for this trace in that model is h AA ; B ; C ; H ; DD ; E ; F ; II i with 5 deviations and a fitness of 1 151 = 0:55.
Typically, a cost function is used to compute so-called optimal alignments, such that the number of model moves, i.e. pairs (a; ), and log moves, i.e. pairs ( ; t) in the alignment is minimized. Then, using an optimal alignment, i.e. an alignment with minimal cost, for each trace fitness is calculated by adding all penalties for log and model moves and dividing that by the worst-case costs, i.e. the costs of an alignment with only log and model moves. For more details on fitness, we refer to [BvDvdA14, Ad14, vdAAvD12]. Anti-alignment based Precision. A model is considered precise if the behaviour the model allows for that was not observed in the event log is small. In this section, we present the precision metric proposed in [vDCC16], which uses anti-alignments as introduced in [CC16]. An anti-alignment is a firing sequence of a model which differs (according to some distance metric) sufficiently from all the observed traces in a log4. Consider the log in Table 1 and model 4. A maximal anti-alignment of length 10 is the firing sequence hA;C; G; G; D; G; G; G; F; Ii with minimal edit distance 140 = 0:4. In contrast, model 1 has only one anti-alignment, namely hA;C; G; H; D; F; Ii with length 7 and distance 71 ) and model 2 and 3 do not have anti-alignments.
In [vDCC16], we suggest a fresh view on precision, using anti-alignments5. The intuition behind our metric is as follows. A very precise process model allows for exactly the observed traces to be executed and not more. Hence, if one trace is removed from the log, this trace becomes the anti-alignment for the remaining log as it is the only execution of the model that is not in the log. We use this property to estimate precision. For each trace in the log, we compute a maximal anti-alignment for the model and the log without that trace. This anti-alignment is guaranteed to reach the final marking. Then, we compute the distance between the removed trace and the anti-alignment found which we average over the log, not taking into account the relative frequencies of the traces in the log. If the language of the model equals the log, then the anti-alignments will be equal to each removed trace, hence the precision is 1. If for every trace, an anti-alignment can be produced which has maximal distance from that trace, the precision is 0. Frequencies of traces are not considered as the comparison is between the language of the model and the observed traces. Observing one trace more frequently than another should not influence the precision of the model as the unobserved behaviour does not change. In trace-based precision, the length of the anti-alignment considered is bounded by the length of the removed trace. This guarantees that an anti-alignment exists in the log without that trace, but also limits the possibility to see imprecise executions of the model that are much longer than the lengths of the observed traces. Therefore, we also defined a logbased precision metric, which uses an anti-alignment of the model with respect to the entire log of a much greater length than the longest trace observed in the log. The logbased precision metric uses a single anti-alignment of considerable maximum length to determine the amount of behaviour allowed by the model, but not observed in the event log. Our final precision metric is a weighted sum of log- and trace-based precision. Anti-alignment based Generalization. In contrast to precision, which relates the log and the model, generalization relates some unknown system to the log and the model as it rea4 We refer to http://www.lsv.ens-cachan.fr/~chatain/darksider/ for the anti-alignment tool. 5 This approach is implemented in the ProM package “anti-alignments” http://www.promtools.org/. sons over expected future behaviour. Generalization aims to estimate the extent to which unobserved, but likely possible behaviour, is explained by the model.
In order to quantify generalizations, we consider not only the sequential behaviour that is actually allowed by the model, but we also quantify how different this behaviour is when considering the state space of the model. (Structured) loops and parallel structures, which are most commonly used to achieve generalization when modelling a system, have introduce new traces while introducing fewer new states. Therefore, in our generalization metric, we consider the notion of a recovery distance for an anti-alignment. Like for precision, we first consider trace-based generalization following the same leaveone-out procedure. This way, the model is guaranteed to contain an anti-alignment of some distance (i.e. the removed trace). Not using trace-based generalization would lead us to consider all models non-generalizing if the log equals the language of the model. In contrast to precision, generalization depends on the frequency of the traces and once again, using the average over trace-based and log-based generalization we get one metric. 2
Conclusions and Future Challenges In this paper we presented three metrics for fitness [vdAAvD12], precision [vDCC16] and generalization [vDCC16] based on alignments and anti-alignments. The future challenges in the domain of conformance checking are in scalability, i.e. dealing with volume and velocity and variability of input data; approximation, i.e. balancing computation time with accuracy of alignments; understandability, i.e. providing explanations of the root causes between observed and modelled behaviour; multi-perspective conformance, i.e. considering data, resources and time; measurability, i.e. providing a better understanding of the different conformance dimensions and solid metrics having a formal interpretation. [Ad14]