Over the last decade, process mining emerged as a new research field that focuses on the analysis of processes using event data. p. 1

Process mining focuses on end-to-end processes and is possible because of the growing availability of event data and new process discovery and conformance checking techniques. p. 1

Process mining aims to discover, monitor and improve real processes by extracting knowledge from event logs readily available in today’s information systems [Aalst 2011]. p. 1

Starting point for process mining is an event log. Each event in such a log refers to an activity (i.e., a well-defined step in some process) and is related to a particular case (i.e., a process instance). The events belonging to a case are ordered and can be seen as one “run” of the process. Event logs may store additional information about events. p. 1

Event logs can be used to conduct three types of process mining as shown in Fig. 1 [Aalst 2011]. The first type of process mining is discovery. A discovery technique takes an event log and produces a model without using any a-priori information. Process discovery is the most prominent process mining technique. p. 2

The second type of process mining is conformance. Here, an existing process model is compared with an event log of the same process. Conformance checking can be used to check if reality, as recorded in the log, conforms to the model and vice versa. The third type of process mining is enhancement. Here, the idea is to extend or improve an existing process model thereby using information about the actual process recorded in some event log. Whereas conformance checking measures the alignment between model and reality, this third type of process mining aims at changing or extending the a-priori model. For instance, by using timestamps in the event log one can extend the model to show bottlenecks, service levels, and throughput times. p. 2

Business Process Management (BPM) p. 2

Unlike existing analysis approaches, process mining is process-centric (and not data-centric), truly intelligent (learning from historic data), and fact-based (based on event data rather than opinions). p. 2

the backbone of process mining is the control-flow perspective. p. 3

A Petri net consists of places (start, p1, p2, p3, p4, p5, and end) and transitions (a, b, c, d, e, f, g, and h). Transitions may be connected to places and places may be connected to transitions. It is not allowed to connect a place to a place or a transition to a transition. p. 4

The state of a Petri net, also referred to as marking, is defined by the distribution of tokens over places. A transition is enabled if each of its input places contains a token. For example, in M1, transition a is enabled in the initial marking of M1, because the only input place of a contains a token (black dot). p. 5

An enabled transition may fire thereby consuming a token from each of its input places and producing a token for each of its output places. Firing a in the initial marking corresponds to removing one token from start and producing two tokens (one for p1 and one for p2). After firing a, three transitions are enabled: b, c, and d. There is a non-deterministic choice between b and d. Firing b will disable c because the token is removed from the shared input place (and vice versa). Transition d is concurrent with b and c, i.e., it can fire without disabling another transition. Transition e becomes enabled after d and b or c have occurred. Note that transition e in M1 is only enabled if both input places (p3 and p4) contain a token. After executing e, three transitions become enabled: f, g, and h. These transitions are competing for the same token thus modeling a choice. When g or h is fired, the process ends with a token in place end. If f is fired, the process returns to the state just after executing a. p. 5

ProM’s heuristic miner uses the algorithm described in [Weijters and Aalst 2003] (see also Section 6.2 in [Aalst 2011]). The algorithm first builds a dependency graph based on the frequencies of activities and the number of times one activity is followed by another activity. Based on predefined thresholds, dependencies are added to the dependency graph graph (or not). The dependency graph reveals the “backbone” of the process model. This backbone is used to discover the detailed split and join behavior of nodes. If an activity has multiple input arcs, then the heuristic miner analyzes the log to see whether the join is an AND-join, an XOR-join or an OR-join. In case of an OR-join, the detailed synchronization behavior is learned. If an activity has multiple output arcs, then the “split behavior” is learned in a similar fashion. p. 6

Typically, four quality dimensions for comparing model and log are considered: (a) fitness, (b) simplicity, © precision, and (d) generalization p. 7

A model with good fitness allows for most of the behavior seen in the event log. A model has perfect fitness if all traces in the log can be replayed by the model from beginning to end. Often fitness is described by a number between 0 (very poor fitness) and 1 (perfect fitness). Obviously, the simplest model that can explain the behavior seen in the log is the best model. This principle is known as Occam’s Razor. p. 7

A model is precise if it does not allow for “too much” behavior. Clearly, the “flower model” lacks precision. A model that is not precise is “underfitting”. Underfitting is the problem that the model over-generalizes the example behavior in the log (i.e., the model allows for behaviors very different from what was seen in the log). p. 7

A model should also generalize and not restrict behavior to just the examples seen in the log. A model that does not generalize sufficiently is “overfitting”. Overfitting is the problem that a very specific model is generated whereas it is obvious that the log only holds example behavior (i.e., the model explains the particular sample log, but a next sample log of the same process may produce a completely different process model). p. 7

Basically, there are three approaches to conformance checking. The first approach is to create an abstraction of the behavior in the log and an abstraction of the behavior allowed by the model. An example is the notion of a footprint described in Section 7.3 of [Aalst 2011]. A footprint is a matrix showing causal dependencies between activities. For example, the footprint of an event log may show that x is sometimes followed by y but never the other way around. If the footprint of the corresponding model shows that x is never followed by y or that y is sometimes followed p. 7

by x, then the footprints of event log and model disagree on the ordering relation of x and y. p. 8

The second approach replays the event log on the model. A naive approach towards conformance checking would be to simply count the fraction of cases that can be “parsed completely” (i.e., the proportion of cases corresponding to firing sequences leading from the initial state to the final state). p. 8

The third, and most advanced, approach is to compute an optimal alignment between each trace in the log and the most similar behavior in the model. p. 8

The open-source tool ProM has been the de-facto standard for process mining during the last decade. Process discovery, conformance checking, social network analysis, organizational mining, decision mining, history-based prediction and recommendation, p. 11

etc. are all supported by ProM [Aalst 2011; Verbeek et al. 2010]. p. 12

REFERENCES p. 15