1 Introduction

In the last two decades, process mining has developed as a research area focusing on the analysis of data to create insights into processes. These processes may be administrative processes such as the handling of insurance claims or production processes where parts are combined to create end products. In all processes, the day to day operations of processes differ from the designed process, i.e. the actual operational data does not conform to the designed process. That is why conformance checking has become a significant field in process mining [5]. In conformance checking, the goal is to relate reality captured in event logs with designed (or discovered) process models.

Various types of conformance checking techniques exist. Rule checking techniques [9, 13], for example, are used to check if specific business rules are respected while case-replay techniques [1, 3, 6, 12] try to identify specific deviations between modelled and observed behavior on the control flow level. More advanced techniques consider resources and data on top of the control flow [2, 10]. Here, authorization (which resource can perform which activity) and data dependencies (higher-value cases take a different route) play a role. More recently, a technique was proposed to consider all perspectives at once [11].

The state-of-the-art of conformance checking uses alignments to relate the recorded execution of a process with a model of this process. An alignment (first introduced in [1], in detail explained in [5]) is a sequence of so-called moves where each move either represents a synchronous move, a log move or a model move. A synchronous move indicates that observed and modeled behaviour agree, i.e. the execution of an activity observed in the data matches the activity being performed according to the design of the process. A log move represents the fact that some observed behaviour cannot be explained by the designed process and a model move represents the fact that an observation of something that should have happened appears to be missing from the data. The latter typically indicates that the observed behaviour can be better explained if it is assumed that some data is missing.

Such alignments can be computed for individual cases in an event log using an A\(^\star \) based search strategy [1, 6], or by means of logic programming [4]. Furthermore, techniques exist to compute representations of classes of alignments [7] while other techniques focus on approximations of alignments [14] to increase the speed of computation or provide divide-and-conquer strategies [8]. However, all these techniques have one fundamental property in common, namely that in the end, they all reason over the so-called synchronous product (although not always instantiating this model).

The synchronous product of a process model and an observed trace is a Petri net where each of the moves explained above is represented by a transition in that Petri net. An alignment is a firing sequence of that Petri net which starts in the initial marking and reaches the final marking. By giving each type of move a weight (typically 0 for synchronous moves and 1 for non-synchronous moves) one can define an optimal alignment as a firing sequence in the synchronous product that minimizes the sum of the weights.

Common to all approaches is that they consider each case in isolation. Conformance checking for an entire event log is reduced to a case-by-case assessment of that log. In this keynote, we use a simple example to show why a systemic approach can lead to the identification of deviating behaviour that cannot be detected on a case-by-case basis.

2 Running Example

As an example, we consider a fictive production process. In this production process, a company paints red and blue products. A product comes into the paint booth and then the operator paints the product in either red or blue. After painting, another operator may check if the product was correctly painted. This check is performed at random, zero or more times. An annotated Petri net model of this very simple process is shown in Fig. 1. Please note that this is, purposely, not a typical process model in the sense that it does not have a clearly identifiable end place.

The model shows the relation between the requested color and the required path, as well as the relation between the resources used in the painting process (x) and the quality check (\(\text {anybody but }x\)).

Fig. 1.
figure 1

Process model for our example with three resources and four cases waiting to be processed. (Color figure online)

Full size image

In Table 1, we show a simple event log for this process. As common practice in event logs, they are grouped by case and contain information about the time an event was logged and the requested color which is a case attribute.

Table 1. Example of a log of the production process.
Full size table
Fig. 2.
figure 2

A typical control-flow focused process-model version of Fig. 1

Full size image

A close inspection of the event log already shows that there are some conformance issues. The first case, i.e. product P5634 appears to have gone through the process correctly. A request was entered to paint the product red, it was painted red by Bill and a check was performed once by Sue. In contrast, products P5635 and P5636 show deviations. In the former, the ‘Request paint’ activity appears to be missing and in the latter the ‘Paint blue complete’ activity appears to be missing. However, one could also argue that the activity ‘Paint Red start’ and ‘Pains Red complete’ are missing and ‘Paint Blue start’ was wrongly logged, since the data suggests a red product was requested, note a blue one. The last case in the log, product P5637 contains two request paint events and two start events for painting. The case is most likely not finished.

A traditional conformance checking technique, which focuses only on the control flow, would ignore the resource and data parts of the model and use the model shown in Fig. 2 instead. This is a classical workflow model with a clear begin and end. A so-called \(\tau \) transition is included to reach the end signalling the termination of a case. This transition is not expected to be observable in an event log. Using this model results in five deviations for this log, since it produces the following alignments:

figure a

Product P5634 shows a model move on the \(\tau \) transition. The symbol \(\gg \) is used as a ‘skip’ symbol indicating that at this position, something was expected but is not present. This is to be expected as this is an unobservable transition. Product P5635 also shows a model move on the ‘Request paint’ transition to start the process off. For product P5637, we see two log moves, i.e. the second ‘Request paint’ and the second ‘Paint Blue start’ are identified as log moves. In total, this log shows five deviations (and four model moves on \(\tau \) which are not called deviations).

Rather than looking only at control flow, more advanced techniques exist for conformance checking. In particular, the data-aware techniques available today are able to detect that product P5636 was painted blue, while it was requested to be painted red. Such techniques explain this deviation in one of two ways depending on the parameter settings: either the product was painted in the wrong color, or the product was painted in the right color, but the log was wrong, i.e. it would produce one of the following two alignments:

figure b

Furthermore, techniques exist to identify deviations on the resource level. Suppose, for example, that a four-eyes principle applies here, i.e. the Quality Check should not be performed by the same person who painted the product. In that case, product P5636 shows a deviation as Mary appears have done both the painting and the Quality Check. A typical rule-checking technique would flag this as a deviation, or, again depending on the parameter settings, would label the first quality check as a log move.

figure c

With all these examples, we have shown that conformance checking techniques can be helpful in identifying deviations. However, there are some deviations in this example which cannot be caught easily with existing techniques which consider cases in isolation. Therefore, in the next section, we show that there is a more subtle problem in this example event log that calls for a systemic view on the data.

3 Alignments: A Systemic View

In the running example, the first case did not show any deviations and, when considering the control flow only, the second case shows only one deviation. However, when considering these two cases together one may see a problem. The activity ‘Quality check’, performed by Sue for product P5634 was executed at time 12:47. However, for product P5636, painting, by Sue, started at 12:45 and lasted until 12:53. In other words, the resource who supposedly executed the quality check for product P5634 was otherwise occupied at 12:47. In order to detect this, we should no longer consider the process model of Fig. 2, but we should consider the model in Fig. 1 and both cases at once.

Doing so with a focus purely on the control-flow perspective, leads to the following systemic alignments. To distinguish the case-level alignments from the systemic ones, we combine the log traces of the latter with the execution of the model in a single table (note that in all cases the trailing \(\tau \) disappeared as this is not part of the model in Fig. 1).

figure d

Or, alternatively:

figure e

In both cases, one of the alignments would be considered sub-optimal from a control-flow perspective when looking at each case in isolation. However, the combination of alignments is the only way to explain the deviation seen in the event log under the assumption that Sue indeed performed all these activities. Taking the resource perspective into account as well would result in another possibility, namely:

figure f

A similar conflict exists between product P5637 and P5634. According to the event log, Bill started painting product P5637 blue at 12:59, but then at 14:01, Bill is seen to perform the quality check on product P5635 and subsequently at 14:15, product P5637 is requested to be painted again, a request Bill honors instantly. A logical explanation for this deviation would be that Bill realized it was break-time at 12:59 when he just started painting product P5637. He then decides to abort that activity and go for lunch until 14:00. In order to avoid an exceptionally long painting time to be logged, he re-requested the paint job. While the latter would be visible from a regular alignment the former requires reasoning over two cases in relation to avoid the conclusion that Bill went for lunch for too long.

When considering all events of the log in Table 1 and the model of Fig. 1 with data and resources, the following systemic alignment can be found:

figure g

The systemic alignment shows a total of seven deviations. Three classical model moves (in purple) and two classical log moves (in yellow). One partial synchronous move, where the event log agrees with the model on the control flow, but the indicated resource cannot be correct (in orange) and one partially synchronous move where the data perspective is wrong (in blue).

The examples above show that already for a small example, looking at the system as a whole is important and the larger the system, the more important this becomes. Examples of deviations that can only be found when looking at the system as a whole are things like:

  • Privacy violations, i.e. resources who are accessing data which they are in general authorized to access, but only in the context of working on a specific case, while they are not working on that specific case.

  • Time-travel violations, i.e. resources that appear to be in two places at once, or in two places after each other which would have required the resource to travel at more than it’s maximum speed (think of robots with cloned ID’s traveling on a grid).

  • Overtaking on a conveyor, i.e. items that move over a conveyor, but suddenly depart in a different order than the order in which they entered.

  • Batching violations, i.e. tasks which are executed in batches for many cases at once and which are suddenly executed only for a limited set of cases.

These, and many other types of deviations can only be identified when looking at combinations of cases and, sometimes, even combinations of process models all together in one systemic view. Unfortunately, if systems grow larger, then the computational challenges become larger too.

4 The Computational Challenge

Computing control-flow alignments for a single case is already a complex task [5]. Computing alignments for multiple cases at once is even worse in terms of complexity. While the work of [7] provides a way to compute symbolic representations of many alignments at once, these representations still focus on the individual cases, i.e. relations between cases are ignored.

An initial step in this direction is the computation of alignments for multiple, related cases by considering joint synchronous products. A joint synchronous product is a combination of a classical Petri net representation of the original process model and the event log as a whole. Figure 3 shows the classical Petri net representation used to get the alignments of Sect. 3. Here, two cases are represented by copies of the original model and each resource is individually represented. Note that this model becomes significantly larger if the data perspective is included or if the other two cases in the event log are included.

Fig. 3.
figure 3

A classical Petri net representation of the Fig. 1, for products P5634 and P5635, including the resource perspective, but not including the data perspective. (Color figure online)

Full size image
Fig. 4.
figure 4

Part of the joint synchronous product relating to the first two events of product P5634. (Color figure online)

Full size image
Fig. 5.
figure 5

Part of the joint synchronous product relating to the last two events of product P5635. (Color figure online)

Full size image
Fig. 6.
figure 6

First part of the optimal alignment for the event log of Table 1. This part of the joint synchronous product explains the first eight events of that log. (Color figure online)

Full size image

In a joint synchronous product the classical Petri net representation is then combined with the event log and all possible moves are encoded as transitions. Where in traditional synchronous products, the move is a pair of an event in the log and a transition that fires in the model (one of which can be \(\gg \)), in a joint synchronous product, a move is a vector of all data that should be considered. In our example, this implies a vector of the product number, the event label, one of the transitions in the model, the resource involved in the transition and the requested color. However, the process of obtaining a joint synchronous product is not different from the traditional procedure for control flow [1] or the procedure for including other perspectives [11].

In Fig. 4 the start of the joint synchronous product is shown for the event log of Table 1. This snippet shows the initial ‘Request paint’ event from case P5634 and the corresponding transition with the possible synchronous move on the left. Then, on the right, for the same case, the ‘Paint Red start’ event is depicted, with all possible variants, i.e. on the top, three model moves for Sue, Bill and Mary. Below that the synchronous move for Bill and below that two partial synchronous moves where event and model agree, but the resource is not Bill. Finally the log move \((\gg ,\text {Prs})\) is shown on the bottom right. A similar snippet is shown for the last two events on product P5635 in Fig. 5. Note that the data perspective (i.e. the color) is not directly included here.

From these fragments it’s easy to see that the joint synchronous product, in the general case, is huge and cannot be depicted here. Figure 6 shows the first part of the systemic alignment shown earlier as a run of the joint synchronous product where the different borders indicate the specific products of the log. It includes the first two products and the first event of the third product. As can be seen, there is a ‘wrong resource’ move for product P5634 which is otherwise handled fully synchronously (in orange again), while for product P5635 there is a model move because of the missing ‘Request product’. This corresponds to the first part of the systemic alignment at the end of Sect. 3.

5 Conclusion and Future Work

In this keynote, we introduced systemic views on conformance checking. Rather than relating observed and modelled behaviour on a case-by-case basis, we showed through an example, that looking at the entire system is sometimes necessary to identify deviations. We then showed an initial approach, using a joint synchronous product to actually compute global alignments for an entire log including resource and data perspectives. This preliminary idea requires considerable work to operationalize as the search space for the entire system is very large. We therefore plan to look for structural reductions on this model.