Scalable process discovery and conformance checking

The aim of conformance checking is to verify a process model against reality. As shown in Fig. 1, two types of conformance checking exist: log–model conformance checking and model–model conformance checking. In log–model conformance checking, reality is assumed to be represented by an event log, while in model–model conformance checking, a representation of the system is assumed to be present and to represent reality. Such a system is usually given as another process model, to which we refer to as system model.

Process discovery aims at discovering a process model from an event log (see Fig. 1). We first sketch some challenges that discovery algorithms face, after which we discuss existing discovery approaches.

Challenges Several factors challenge process discovery algorithms. One such challenge is that the resulting process model should have well-defined behavioural semantics and be sound [50]. Even though an unsound process model or a model without a language, i.e. without a definition of traces the model expresses, might be useful for manual analysis, conformance checking and other automated techniques can obviously not provide accurate measures on such models [28, 59]. The IMd framework uses its representational bias to provide a language and to guarantee soundness: it discovers an abstract hierarchical view on workflow nets [50], process trees, that is guaranteed to be sound [11].

Another challenge of process discovery is that for many event logs the different measures, e.g. fitness, log-precision, generalisation and simplicity, are competing, i.e. there might not exist a model that scores well on all criteria [12]. Thus, discovery algorithms have to balance these measures, and this balance might depend on the use case at hand, e.g. auditing questions are best answered using a model with high fitness, optimisations are best performed on a model with high log-precision, implementations might require a model with high generalisation, and human interpretation is eased by a simple model [12].

A desirable property of discovery algorithms is having the ability to rediscover the language of the system (rediscoverability); we assume the system and the system model to have the same behaviour for rediscoverability. Rediscoverability is usually proven using assumptions on both system and event log: the system typically must be of a certain class, and the event log must contain enough correct information to describe the system well [29]. Therefore, three more challenges of process discovery algorithms are to handle (1) noise in the event log, i.e. random absence or presence of events [13], (2) infrequent behaviour, i.e. behaviour that occurs less frequent than ‘normal’ behaviour, i.e. the exceptional cases. For instance, most complaints sent to an airline are handled according to a model, but a few complaints are so complicated that they require ad hoc solutions. This behaviour could be of interest or not, which depends on the goal of the analysis [50]. (3) incompleteness, i.e. the event log does not contain ‘enough’ information. The notion of what ‘enough’ means depends on the discovery algorithm [6, 29]. Even though rediscoverability is desirable, it is a formal property, and it is not easy to compare algorithms using it. However, the pcc framework allows to perform experiments to quantify how rediscoverability is influenced by noise, infrequent behaviour, and incompleteness.

A last challenge arises from the main focus of this paper, i.e. highly scalable environments. Ideally, a discovery technique should linearly pass over the event log once, which removes the need to keep the event log in memory. In the remainder of this section, we discuss related process discovery techniques and their application in scalable environments.

Sound process discovery algorithms Process discovery techniques such as the Evolutionary Tree Miner (ETM) [11], the Constructs Competition Miner (CCM) [41], Maximal Pattern Mining (MPM) [34], and Inductive Miner (IM) [29] provide several quality guarantees, in particular soundness and some offer rediscoverability, but do not manage to discover a model in a single pass. ETM applies a genetic strategy, i.e. generates an initial population, and then applies random crossover steps, selects the ‘best’ individuals from the population and repeats. While ETM is very flexible towards the desired log measures to which respect the model should be ‘best’ and guarantees soundness, it requires multiple passes over the event log and does not provide rediscoverability.

CCM and IM use a divide-and-conquer strategy on event logs. In the Inductive Miner framework (IM framework), first an appropriate cut of the process activities is selected; second, that cut is used to split the event log into sublogs; third, these sublogs are recursed on, until a base case is encountered. If no appropriate cut can be found, a fall-through (‘anything can happen’) is returned. CCM works similarly by having several process constructs compete with one another. While both CCM and the IM framework guarantee soundness and IM guarantees rediscoverability (for the class of models described in Appendix 1), both require multiple passes through the event log (the event log is being split and recursed on).

MPM first constructs a prefix tree of the event log. Second, it folds leaves to obtain a process model, thereby applying local generalisations to detect concurrency. The MPM technique guarantees soundness and fitness, allows for noise filtering and can reach high precision, but it does so at the cost of simplicity: typically, lots of activities are duplicated. Inherently, the MPM technique requires random access to the event log and a single pass does not suffice.

Other process discovery algorithms Other process discovery techniques are, for instance, the \(\alpha \) -algorithm (\(\alpha \)) and its derivatives [49, 65, 66], the Heuristics Miner [64] (HM), the Integer Linear Programming miner [54] (ILP) and several commercial tools, such as Fluxicon Disco (FD) [23] and Perceptive Process Mining (two versions: PM1 and PM2).

Some of these guarantee soundness, but do not support explicit concurrency (FD, PM1) [31]. The ILP miner guarantees fitness and can guarantee that the model is empty after completion, but only for the traces seen in the event log, i.e. the models produced by ILP are usually not sound. However, most of these algorithms (\(\alpha \), HM, ILP, PM2) neither guarantee soundness nor even provide a final marking, which makes it difficult to determine their language (see Appendix 5), and thus, their models are difficult to analyse automatically (though, such unsound models can still be useful for manual analysis).

Several techniques (e.g. \(\alpha \), HM) satisfy the single-pass requirement. These algorithms first obtain an abstraction from the log, which denotes what activities directly follow one another; in HM, this abstraction is filtered. Second, from this abstraction a process model is constructed. Both \(\alpha \) and HM have been demonstrated to be applicable in highly scalable environments: event logs of 5 million traces have been processed using map-reduce techniques [21]. Moreover, \(\alpha \) guarantees rediscoverability, but neither \(\alpha \) nor HM guarantees soundness. We show that our approach offers the same scalability as HM and \(\alpha \), but provides both soundness and rediscoverability.

Some commercial tools such as FD and PM1 offer high scalability, but do not support explicit concurrency [31]. Other discovery techniques such as the language-based region miner [9, 10] or the state-based region miner [17] guarantee fitness but neither soundness nor rediscoverability nor work in single pass.

Software mining In the field of software mining, similar techniques have been used to discover formal specifications of software. For instance, in [40] and [4], execution sequences of software runs (i.e. traces) are recorded in an event log, from which techniques extract, e.g., valid execution sequences on the methods of an API. Such valid execution sequences can then be used to generate documentation. Process discovery differs from software mining in focus and challenges: process discovery aims to find process models with soundness and concurrency and is challenged, e.g., by deviations from the model (noise, infrequent behaviour) and readability requirements of the discovered models, while for software mining techniques, the system is fixed and challenges arise from, e.g., nesting levels [40], programmed exceptions [67], and collaborating components [22].

Streams Another set of approaches that aims to handle even bigger logs assumes that the event log is an unbounded stream of events. Some approaches such as [18, 24] work on click-stream data, i.e. the sequence of web pages users visit, to extract, for instance, clusters of similar users or web pages. However, we aim to extract end-to-end process models, in particular containing parallelism. HM, \(\alpha \), and CCM have been shown to be applicable in streaming environments [14, 42], and any single-pass discovery algorithm (thus the IMd framework as well) can be converted into a streaming algorithm, but will have to deal with the same discovery challenges as described before.

Event logs An event log is a multiset of traces that denote process executions. For instance, the event log \([\langle a, b, c \rangle , \langle b, d \rangle ^2]\) denotes the event log in which the trace consisting of the activity a followed by the activity b followed by the activity c was executed once, and the trace consisting of b followed by d was executed twice.

Process trees A process tree is an abstract representation of a block-structured hierarchical process model, in which the leaves represent the activities, i.e. the basic process steps, and the operators describe how their children are to be combined [11]. \(\tau \) denotes the activity whose execution is not visible in the event log. We consider four operators: \(\times \), \(\rightarrow \), \(\wedge \), and \(\circlearrowleft \). \(\times \) describes the exclusive choice between its children, \(\rightarrow \) the sequential composition, and \(\wedge \) the parallel composition. The first child of a loop \(\circlearrowleft \) is the body of the loop, and all other children are redo children. First, the body must be executed, followed by zero or more iterations of a redo child and the body. A formal definition is given in Appendix 1; we give an example here: Fig. 3 shows the Petri net corresponding to the process tree \(\rightarrow (\times (\wedge (a, b), c), \times (\circlearrowleft (\rightarrow (d, e), f), g))\). Process trees are inherently sound.

Directly-follows graphs A directly-follows graph can be derived from a log and describes what activities follow one another directly, and with which activities a trace starts or ends. In a directly-follows graph, there is an edge from an activity a to an activity b if a is followed directly by b. The weight of an edge denotes how often that happened. For instance, the directly-follows graph of our example log \([\langle a, b, c \rangle , \langle b, d \rangle ^2]\) is shown in Fig. 4. Note that the multiset of start activities is \([a, b^2]\) and the multiset of end activities is \([c, d^2]\). A directly-follows graph can be obtained in a single pass over the event log with minimal memory requirements [21].

Cuts, characteristics, and the Inductive Miner framework. A partition is a non-overlapping division of the activities of a directly-follows graph. For instance, \((\{a, b\}, \{c, d\})\) is a binary partition of the directly-follows graph in Fig. 4. A cut is a partition combined with a process tree operator, for instance \((\rightarrow , \{a, b\}, \{c, d\})\). In the IM framework, finding a cut is an essential step: its operator becomes the root of the process tree, and its partition determines how the log is split.

The IM framework [29] discovers the main cut and projects the given log onto the activity partition. In case of loops, each iteration becomes a new trace in the projected sublog. Subsequently, for each sublog its main cut is detected and recursion continues until reaching partitions with singleton elements; these become the leaves of the process tree. If no cut can be found, a generalising fall-through is returned that allows for any behaviour (a ‘flower model’). By the use of process trees, the IM framework guarantees sound models and makes it easy to guarantee fitness. The IM framework is formalised in Appendix 1.

Suppose that the log is produced by a process which can be represented by a process tree T. Then, the root of T leaves certain characteristics in the log and in the directly-follows graph. The most basic algorithm that uses the IM framework, i.e. IM [29], searches for a cut that matches these characteristics perfectly. Other algorithms using the IM framework are the infrequent behaviour-filtering Inductive Miner—infrequent (IMf) [28] and the incompleteness-handling Inductive Miner—incompleteness (IMc) [30].

Cut definitions are given Appendix 1. Here we describe how the cut detection works. Each of the four process tree operators \(\times \), \(\rightarrow \), \(\wedge \), and \(\circlearrowleft \) leaves a different characteristic footprint in the directly-follows graph. Figure 5 visualises these characteristics: for exclusive choice, the activities of one subtree will never occur in the same trace as activities of another subtree. Hence, activities of the different subtrees form clusters that are not connected by edges in the directly-follows graph. Thus, the \(\times \) cut is computed by taking the connected components of the directly-follows graph.

If two subtrees are sequentially ordered, all activities of the first subtree strictly precede all activists of the second subtree; in the directly-follows graph we expect to see a chain of clusters without edges going back. The procedure to discover a sequence cut is as follows: each activity starts as a singleton set. First, the strongly connected components of the directly-follows graph are computed and merged. By definition, two activities are in a strongly connected component if they are pairwise reachable, and therefore they cannot sequential. Second, pairwise unreachable sets are merged, as if there is no way to reach two nodes in the same trace, they cannot be sequential. Finally, the remaining sets are sorted based on reachability.

The activities of two parallel subtrees can occur in any intertwined order; we expect all possible connections to be present between the child clusters in the directly-follows graph. To detect parallelism, the graph is negated: the negated graph gets no edge between two activities if both directly-follows edges between these activities are present. If either edge is missing, the negated graph will contain an edge between these two activities. In this negated graph, the partition of the parallel cut is the set of connected components.

In a loop, the directly-follows graph must contain a clear set of start and end activities; all connections between clusters must go through these activities. To detect a loop cut, first the connected components of the directly-follows graph are computed, while excluding the start and end activities. Please note that start and end activities by definition belong to the body of the loop. Second, for each component reachability is used to determine whether it is directed from a start activity to an end activity (body part), or directed the other way round (a redo).

As a first algorithm that uses the framework, we introduce Inductive Miner—directly-follows (IMd). We explain the stages of IMd in more detail by means of an example: Let L be \([\langle a, b, c, f, g, h, i \rangle \), \(\langle a, b, c, g, h, f, i \rangle \), \(\langle a, b, c, h, f, g, i \rangle \), \(\langle a, c, b, f, g, h, i \rangle \), \(\langle a, c, b, g, h, f, i \rangle \), \(\langle a, c, b, h, f, g, i \rangle \), \(\langle a, d, f, g, h, i \rangle \), \(\langle a, d, e, d, g, h, f, i \rangle \), \(\langle a, d, e, d, e, d, h, f, g, i \rangle ]\). The directly-follows graph \(D_1\) of L is shown in Fig. 6.

Cut detection IMd searches for a cut that perfectly matches the characteristics mentioned in Sect. 3. As explained, cut detection has been implemented using standard graph algorithms (connected components, strongly connected components), which run in polynomial time, given the number of activities (O(n)) and directly-follows edges (\(O(n^2)\)) in the graph.

In our example, the cut \((\rightarrow , \{a\}, \{b, c, d, e\}, \{f, g, h\}, \{i\})\) is selected: as shown in Fig. 5, every edge crosses the cut lines from left to right. Therefore, it perfectly matches the sequence cut characteristic. Using this cut, the sequence is recorded and the directly-follows graph can be split.

Directly-follows graph splittingGiven a cut, the IMd framework splits the directly-follows graph in disjoint subgraphs. The idea is to keep the internal structure of each of the clusters of the cut by simply projecting a graph on the cluster. Figure 7 shows an example of how \(D_1\) (Fig. 6) is split using the sequence cut that was discovered in our example. If the operator of the cut is \(\rightarrow \) or \(\circlearrowleft \), the start and end activities of a child might be different from the start and end activities of its parent. Therefore, every edge that enters a cluster is counted as a start activity, and an edge leaving a cluster is counted as an end activity. In our example, the start activities of cluster \(\{f, g, h\}\) are those having an incoming edge not starting in \(\{f, g, h\}\), and correspondingly for end activities. The result is shown in Fig. 7a. In case of \(\times \), no edges leave any cluster and hence the start and end activities remain unchanged. In case of \(\wedge \), removed edges express the arbitrary interleaving of activities in parallel clusters; removing this interleaving information does not change with which activities a cluster may start or end; thus, start and end activities remain unchanged.

The choices for a sequence cut and the split directly-follows graphs are recorded in an intermediate tree: \(\rightarrow ((D_2), (D_3), (D_4), (D_5))\), denoting a sequence operator with 4 unknown subtrees that are to be derived from 4 directly-follows graphs.

Recursion Next, IMd recurses on each of the new directly-follows graphs (find cut, split, ...) until a base case (see below) is reached or no perfectly matching cut can be found. Each of these recursions returns a process tree, which in turn can be inserted as a child of an operator identified in an earlier recursion step.

Base case Directly-follows graphs \(D_2\) (Fig. 7a) and \(D_5\) (Fig. 7d) contain base cases: in both graphs, only a single activity is left. The algorithm turns these into leaves of the process tree and inserts them at the respective spot of the parent operator. In our example, detecting the base cases of \(D_2\) and \(D_5\) yields the intermediate tree \(\rightarrow (a, (D_3), (D_4), i)\), in which \(D_3\) and \(D_4\) indicate directly-follows graphs that are not base cases and will be recursed on later.

Fall-through Consider \(D_4\) as shown in Fig. 7c. \(D_4\) does not contain unconnected parts, so does not contain an exclusive choice cut. There is no sequence cut possible, as f, g, and h form a strongly connected component. There is no parallel cut as there are no dually connected parts and no loop cut as all activities are start and end activities. Thus, IMd selects a fall-through, being a process tree that allows for any behaviour consisting of f, g, and h (a flower model \(\circlearrowleft (\tau , f, g, h)\), having the language \((f|g|h)*\)). The intermediate tree of our example up till now becomes \(\rightarrow (a, (D_3), \circlearrowleft (\tau , f, g, h), i)\) (remember that \(\tau \) denotes the activity of which the execution is invisible).

Example continued In \(D_3\), as shown in Fig. 7b, a cut is present: \((\times , \{b, c\}, \{d, e\})\): no edge in \(D_3\) crosses this cut. The directly-follows graphs \(D_6\) and \(D_7\), as shown in Fig. 8a, b, result after splitting \(D_3\). The tree of our example up till now becomes \(\rightarrow (a, \times ((D_6), (D_7)), \circlearrowleft (\tau , f, g, h), i)\).

In \(D_6\), as shown in Fig. 8a, a parallel cut is present, as all possible edges cross the cut, i.e. the dashed line, in both ways. The dashed line in \(D_7\) (Fig. 8b) denotes a loop cut, as all connections between \(\{d\}\) and \(\{e\}\) go via the set of start and end activities \(\{d\}\). Four more base cases give us the complete process tree \(\rightarrow (a, \times (\wedge (b, c), \circlearrowleft (d, e)), \circlearrowleft (\tau , f, g, h), i)\).

To summarise: IMd selects a cut, splits the directly-follows graph, and recurses until a base case is encountered or a fall-through is necessary. As each recursion removes at least one activity from the graph and cut detection is \(O(n^2)\), IMd runs in \(O(n^3)\), in which n is the number of activities in the directly-follows graph.

By the nature of process trees, the returned model is sound. By reasoning similar to IM [29], IMd guarantees rediscoverability on the same class of models (see Appendix 1), i.e. assuming that the model is representable by a process tree without using duplicate activities, and it is not possible to start loops with an activity they can also end with [29]. This makes IMd the first single-pass algorithm to offer these guarantees.

The basic algorithm IMd guarantees rediscoverability, but, as will be shown in this section, is sensitive to both infrequent and incomplete behaviour. To solve this, we introduce two more algorithms using the IMd framework.

Consider again directly-follows graph \(D_3\), as shown in Fig. 7b, and suppose that there is a single directly-follows edge added, from c to d. Then, \((\times , \{b, c\}, \{d, e\})\) is not a perfectly matching cut, as with the addition of this edge the two parts \(\{b, c\}\) and \(\{d, e\}\) became connected. Nevertheless, as 9 traces showed exclusive choice behaviour and only one did not, this single trace is probably an outlier and in most cases, a model ignoring this trace would be preferable.

To handle these infrequent cases, we apply a strategy similar to IMf [28] and use the IMd framework to define another discovery algorithm: Inductive Miner—infrequent—directly-follows (IMfD). Infrequent behaviour introduces edges in the directly-follows graph that violate cut requirements. As a result, a single edge makes it impossible to detect an otherwise very strong cut. To handle this, IMfD first searches for existing cuts as described in Sect. 3.2. If none is found (when IMd would select a fall-through), the graph is filtered by removing edges which are infrequent with respect to their neighbours. Technically, for a parameter \(0 \le h \le 1\), for an activity a we keep the outgoing edges that occur more than h times the most occurring outgoing edge of a (a formal definition is given in Appendix 1). Start and end activities are filtered similarly.

Incompleteness A log in a ‘big-data setting’ can be assumed to contain lots of behaviour. However, we only see example behaviour and we cannot assume to have seen all possible traces, even if we use the rather weak notion of directly-follows completeness [30] as we do here. Moreover, sometimes smaller subsets of the log are considered, for instance when performing slicing and dicing in the context of process cubes [48]. For instance, an airline might be interested in comparing the complaint-handling process for several groups of customers, to gain insight in how the process relates to age, city, and frequent-flyer level of the customer. Then, there might be combinations of age, city, and frequent-flyer level that rarely occur and the log for these customers might contain too little information.

If the log contains little information, edges might be missing from the directly-follows graph and the underlying real process might not be rediscovered. Figure 9 shows an example: the cut \((\{a, b\}, \{c, d\})\) is not a parallel cut as the edge (c, b) is missing. As the event log only provides example behaviour, it could be that this edge is possible in the process, but has not been seen yet. Given this directly-follows graph, IMd can only give up and return a fall-through flower model, which yields a very imprecise model. However, choosing the parallel cut \((\{a, b\}, \{c, d\})\) would obviously be a better choice here, providing a better precision.

To handle incompleteness, we introduce Inductive Miner—incompleteness—directly-follows (IMcD), which adopts ideas of IMc [30] into the IMd framework. IMcD first applies the cut detection of IMd and searches for a cut that perfectly matches a characteristic. If that fails, instead of a perfectly matching cut, IMcD searches for the most probable cut of the directly-follows graph at hand.

IMcD does so by first estimating the most probable behavioural relation between any two activities in the directly-follows graph. In Fig. 9, the activities a and b are most likely in a sequential relation as there is an edge from a to b. a and c are most likely in parallel as there are edges in both directions. Loops and choices have similar local characteristics. For each pair of activities x and y the probability \(P_r(x, y)\) that x and y are in relation R is determined. The best cut is then a partition into sets of activities X and Y such that the average probabilities that \(x \in X\) and \(y \in Y\) are in relation R is maximal. For a formal definition, please refer to [30].

In our example, the probability of cut \((\wedge , \{a, b\}, \{c, d\})\) is the average probability that (a, c), (a, d), (b, c) and (b, d) are parallel. IMcD chooses the cut with highest probability, using optimisation techniques. This approach gives IMcD a run-time exponential in the number of activities, but still requires a single pass over the event log.

The IMd framework imposes some limitations on process discovery. We discuss limiting factors on the challenges identified in Sect. 2: rediscoverability, handling incompleteness, handling noise and handling infrequent behaviour, and balancing fitness, precision, generalisation and simplicity.

Limitations on rediscoverability of the IMd framework are similar to the IM framework: the system must be a process tree and adhere to some restrictions, and the log must be directly-follows complete (as discussed before). If the system does not adhere to the restrictions, then IMd framework will not give up but rather try to discover as much process tree like behaviour as possible. For instance, if a part of the process is sequential, then IMd framework might be able to discover this, even though the other parts of the process are not block structured. Therefore, in practice, such models can be useful [8, 15]. To formally investigate what happens on non-block-structured models would be an interesting subject of further study. For the remaining non-block structured parts, the flexibility of IMd framework easily allows for future customisations, e.g. [36].

If the log is incomplete, in some cases log-based discovery techniques might handle this incompleteness better. For instance, take the process tree \(P_1 = \wedge (a, b, c)\) and an event log \(L = \{\langle a, b, c\rangle , \langle c, b, a \rangle , \langle b, a, c\rangle , \langle a, c, b\rangle \}\). Figure 10a shows the directly-follows graph of L. Log L is not directly-follows complete with respect to \(P_1\), as the edge (c, a) is missing. Both IM and IMd will first detect a concurrent cut \((\wedge , \{a, c\}, \{b\})\). The sublogs after splitting by IM are \(\{\langle a, c\rangle , \langle c, a \rangle \}\) and \(\{\langle b \rangle \}\), in which the missing directly-follows edge a, c pops up and enables the rediscovery of \(P_1\). In IMd, however, the directly-follows graph is split, resulting in the directly-follows graph for a, c shown in Fig. 10b, from which \(P_1\) cannot be rediscovered. In Sect. 6, we will illustrate that the effect of this limitation is limited on larger examples.

If the log contains noise and/or infrequent behaviour, then the IMd framework might choose a wrong cut at some point (as discussed in Sect. 4.2), possibly preventing rediscovery of the system. The noise handling abilities of log-based and directly-follows-based algorithms differ in detail; in both, noise and infrequent behaviour manifest as superfluous edges in a directly-follows graph. On one hand, in IM, such wrong edges might pop up during recursion by reasoning similar to the incompleteness case (which could be harmful), while using the same reasoning, log-based algorithms might have more information available to filter such edges again (which could be beneficial). In the evaluation, we will investigate this difference further.

Given an event log, both types of algorithms have to balance fitness, precision, generalisation and simplicity. For directly-follows-based algorithms, this balance might be different.

For instance, a desirable property of discovery algorithms is the ability to preserve fitness, i.e. to discover a model that is guaranteed to include all behaviour seen in the event log. For directly-follows-based algorithms, this is challenging. For instance, Fig. 10c shows a complete directly-follows graph of the process tree \(P_2 = \wedge (\rightarrow (a, b), c)\). However, it is also the directly-follows graph of the event log \(L_2 = \{\langle a, c, b, c, a, b\rangle , \langle c \rangle \}\). Hence, if a fitness-preserving directly-follows-based discovery algorithm would be applied to the directly-follows graph in Fig. 10c, this algorithm could not return \(P_2\) and has to seriously underfit/generalise to preserve fitness since the behaviour of both needs to be included. Hence, \(P_2\) could never be returned. Therefore, we chose the IMd framework to not guarantee fitness, while the IM framework by its log splitting indirectly takes such concurrency dependencies into account. Please note that this holds for any pure directly-follows-based process discovery algorithm (see the limitations of the \(\alpha \)-algorithm). Generalisation, i.e. the likelihood that future behaviour will be representable by the model, is similarly influenced.

Algorithms of the IM framework can achieve a high log-precision if it can avoid fall-throughs such as the flower model [28]. Thus, IM framework achieves the highest log-precision if it can find a cut. The same holds for IMd framework, and therefore we expect log-precision to largely depend on the cut selection. In the evaluation, we will investigate log-precision further.

The influence of directly-follows-based algorithms on simplicity highly depends on the chosen simplicity measure: both IM framework and IMd framework return models in which each activity appears once.

The recall of a model S and a model M describes the part of the behaviour of S that is captured by M (compare to the conventional fitness notion in process mining), while precision captures the part of the behaviour of M that is also possible in S.

For a complex model S and a complex model M, the direct language-based comparison of the two models by constructing and comparing their state spaces might suffer from the state explosion problem, and hence be prohibitively expensive. Therefore, the framework approximates recall and precision by measuring them on subsets of activities, i.e. we avoid the state explosion problem by considering small submodels, and averaging over all such subsets. The framework is applicable to any process model formalism and process discovery algorithm, as long as the languages of the models used can be described as deterministic finite automata (DFAs). We first introduce the general idea of the framework, after which we describe its steps in more detail.

Framework Figure 11 shows an overview of the model–model evaluation framework; formally, the framework takes as input a model S, a model M, and an integer k. S and M must be process models, but can be represented using any formalism with executable semantics.

To measure recall and precision of S and M, we introduce a parameterised technique in which k defines the size of the subsets of activities for which recall and precision shall be computed. Take a subset of activities \(A = \{a_1\ldots a_k\}\), such that \(A \subseteq \varSigma (M) \cup \varSigma (S)\), and \(|A| = k\). Then, S and M are projected onto A, yielding \(S|_A\) and \(M|_A\) (we will show how the projection is performed below). From these projected \(S|_A\) and \(M|_A\), deterministic finite automata (DFAs) are generated, which are compared to quantify recall and precision. These steps are repeated for all such subsets A, and the average recall and precision over all subsets is reported.

As we aim to apply this method to test rediscoverability, a desirable property is that precision and recall should be 1 if and only if \(\mathcal {L}(S) = \mathcal {L}(M)\). Theorem 1, given later, states that this is the case for the class of process trees used in this paper.

As a running example, we will compare two models, being a process tree and a Petri net. Both are shown in Fig. 12.

In the remainder of this section, we describe the steps of the framework in more detail after which we give an example and prove Theorem 1.

Projection Many process formalisms allow for projection on subsets of activities; we give a definition for process trees here and sketch projection for Petri nets in Appendix 5.

A process tree can be projected on a set of activities \(A = \{a_1 \ldots a_k\}\) by replacing every leaf that is not in A with \(\tau \): (in which \(\oplus \) is any process tree operator)After projection, a major problem reduction (and speedup) can be achieved by applying structural language-preserving reduction rules to the process tree, such as the rules described in Appendix 2.

In principle, any further language-preserving state-space reduction rules can be applied; we will not explore further options in this paper.

If we project our example process tree and Petri net onto activities a and b, we obtain the models as shown in Fig. 13.

Process model to deterministic finite automaton An automaton describes a language based on an alphabet \(\varSigma \). The automaton starts in its initial state; from each state, transitions labelled with activities from \(\varSigma \) denote the possible steps that can be taken from that state. A state can be an accepting state, which denotes that a trace which execution ends in that state is accepted by the automaton. An automaton with a finite set of states is a non-deterministic finite automaton (NFA). In case that the automaton does not contain a state from which two transitions with the same activity leave, the automaton is a deterministic finite automaton (DFA). Each NFA can be translated into a DFA and a language for which a DFA exist is a regular language; for each DFA, there exists a reduced unique minimal version [35].

Process tree is defined using regular expressions in Appendix 1, which can be transformed straightforwardly into an NFA (we used the implementation [37], which provides a shuffle operator). Second, a simple procedure transforms the NFA into a DFA [35].

The translation of our example \(S|_{\{a, b\}}\) and \(M|_{\{a, b\}}\) to DFAs results in the automata shown in Fig. 14a, b.

Comparing deterministic finite automata Precision is defined as the part of behaviour in \(M|_A\) that is also in \(S|_A\). Therefore, first the conjunction \(\text {DFA}(S|_A) \cap \text {DFA}(M|_A)\) (which we abbreviate to \(\text {DFAc}(S, M, A)\)) of these DFAs is constructed, which accepts the traces accepted by both \(S|_A\) and \(M|_A\). Figure 14c shows the conjunctive DFA of our running example. Then, precision is measured similarly to several existing precision metrics, such as [3]: we count the outgoing edges of all states in \(\text {DFA}(M|_A)\) and compare that to the outgoing edges of the corresponding states (s, m) in \(\text {DFAc}(S, M, A)\) (for ease of notation, we consider an automaton as a set of states here):If \(\text {DFA}(M|_A)\) has no edges at all (i.e. describes the empty language), we definePlease note that we count acceptance as an outgoing edge, and that states may be counted multiple times if they are used multiple times in \(\text {DFAc}\). Recall is defined as the part of behaviour in \(S|_A\) that is not in \(M|_A\), i.e. \(recall(S, M, A) = {\textit{precision}}(M, S, A)\). In our example (see Table 1), recall for (a, b) is \(\frac{1+1+1}{3+1+1+1} = 0.5\); precision is \(\frac{1+1+1}{2+1+1} = 0.75\).

In order to evaluate models with respect to event logs, the framework in Sect. 5.1 is adapted as follows: Fig. 15 shows an overview: the framework starts from an event log L and a model M (in a process mining setting, M would have been discovered from L). First, L and M are projected on a set of activities A. A log is projected by removing the non-projected events, e.g. \(\{\langle a, b, c \rangle , \langle c, d \rangle \}|_{\{a, b\}} = \{\langle a, b \rangle , \langle ~\rangle \}\). Second, from both projections a DFA is constructed. Precision is computed as in Sect. 5.2, i.e. by comparing \(\text {DFA}(L|_A)\) and \(\text {DFA}(M|_A)\). For fitness, it is desirable that the frequencies of traces are taken into account, such that a trace that appears 10,000 times in L contributes more to the fitness value than a trace that appears just once. Therefore, we compute fitness as the fraction of traces of \(L|_A\) that can be replayed on \(\text {DFA}(M|_A)\):If the log contains no traces, we define fitness to be 1.

Note that L is a multiset: if a trace appears multiple times in L, it contributes multiple times as well. This is repeated for all subsets of activities A of a certain length k, similarly to the model–model comparison. Note that besides a fitness/precision number, the subsets A also provide clues where deviations in the log and model occur.

For each tree, we first generate a random log of t traces, starting t at 1. Second, we test whether an algorithm returns a model for that log when allocated 2GB of main memory, i.e. the algorithm terminates with a result and does not crash. If successful, we multiply t by 10 and repeat the procedure. The maximum t is recorded for each algorithm and process tree A, B, and C.

Besides the new algorithms introduced in this paper, the following algorithms were included in the experiment:

The soundness-guaranteeing algorithms ETM, CCM, and MPM were not included, as ETM is a non-deterministic algorithm and requires long run times to discover reasonable models, and as for CCM and MPM, there is no implementation publicly available. It would be interesting to test these as well.

Event logs The complexities of the event logs are shown in Table 2; they were generated randomly from trees A, B, or C. From this table, we can deduce that the average trace length in (A) is 37 events, in (B) 109, and in (C) 764; Appendix 6 shows additional statistics. Thus, the average trace length increases with the number of activities.

The largest log we could generate for A was 217 GB (\(10^8\) traces), limited by disk space. For the trees B and C, the largest logs we could generate were \(10^6\) and \(10^5\) traces, but now limited by RAM. For the bigger logs, the traces were directly transformed into a directly-follows graph and the log itself was not stored. In Table 2, these logs are marked with *.

Compared with [32], tree B was added and the logs of trees A and C were regenerated. Therefore, the log generated for these trees are slightly different from [32]. However, the conclusions were not influenced by this.

Results Table 3 shows the results. Results that could not be obtained are marked with * (for instance, IMc and IMcD ran for over a week without returning a result).

This experiment clearly shows the scalability of the IMd framework, which handles larger and more complex logs easily (IMd and IMfD handle \(10^8\) traces, \(7\times 10^{10}\) events, and \(10^4\) activities). Moreover, it shows the inability of existing approaches to handle larger and complex logs: the most scalable other algorithms were IM and IMf, that both handled only 1000 traces. Furthermore, it shows the limited use sampling would have on such logs (logs manageable for other algorithms, i.e. 1000 traces for tree C do not contain all activities yet). We discuss the results in detail in Appendix 7.

TimeTimewise, it took a day to obtain a directly-follows graph from the log of \(10^8\) traces of tree A, (using the preprocessing Python script) after that discovering a process model was a matter of seconds for IMd and IMfD. For the largest logs they could handle, P-IF, \(\alpha \), HM, IM, IMf, and IMc took a few minutes; P-PT took days, ILP a few hours. In comparison, on the logs that ILP could handle, creating a directly-follows graph took a few seconds, just as applying IMd.

To answer RQ2, i.e. whether single-pass algorithms are able to rediscover the system, how large logs need to be in order to enable rediscovery, and how these algorithms compare to classical algorithms, we performed a second experiment. In complex processes, such as B and C, information can be missing from logs if the logs are not large enough: Table 2 shows that in our example, \(10^5\) traces were necessary for B to have all activities appear in the log.

Set-up For each model generated in the scalability experiment, we measure recall and precision with respect to tree A, B, or C using the pcc framework. Given the results of the scalability experiment, we include the algorithms IM, IMf, IMc, HM, IMd, IMfD, IMcD, and a baseline model allowing for any behaviour (a flower model).

As HM does not guarantee to return a sound model, nor provides a final marking, we obtain a final marking using the method described in Appendix 5. However, even with this method we were unable to determine the languages of the models returned by HM, and thus, these were excluded.

Results Figure 17 shows that for model A (40 activities) both IM and IMd rediscover the language of A (a model that has 1.0 model-precision and recall with respect to A) on a log of \(10^4\) traces. As can be seen in Fig. 18, IMd could rediscover the language of B at \(10^8\) traces, IM did not succeed as the largest log it could handle (\(10^5\) traces) did not contain enough information to rediscover the language of B. The largest log we generated for tree C, i.e. containing \(10^8\) traces, did not contain enough information to rediscover the language of C: IMd discovered a model with a recall of 1.0 and a model-precision of 0.97. Corresponding results have been obtained for IMf/IMfD and IMc/IMcD; see Appendix 8 for all details. The flower model provided the baseline for precision: it achieved recall 1.0 at \(10^1\) (A) and \(10^2\) (B) traces and achieves a model-precision of 0.8.

We conclude that algorithms of the IMd framework are capable of rediscovering the original system, even in case of very large systems (trees B and C), and that these algorithms do not require larger logs than other algorithms to do so: IM and IMd rediscovered the models on logs of the same sizes; for smaller logs IMd performed slightly better than IMfD. Overall, IMd and IMfD have a similar robustness to incomplete event logs as their IM counterparts, which makes them more robust than other algorithms as well [30]. We discuss the results in detail in Appendix 7.

To answer RQ3, we tested how noise in the event log influences rediscovery. We took the event log of \(10^4\) traces of tree B, as that log was well handled by several algorithms but did not reach perfect recall and precision in the incompleteness experiment, indicating that discovery is possible but challenging. To this \(10^4\) traces, we add n noisy traces with some noise, for tenfold increasing n from 1 to \(10^5\), i.e. the logs have 10,001–110,000 traces. A noisy trace is obtained from a normal trace by adding or removing a random event (both with 0.5 probability). By the representational bias of the process trees used in the generation, such a trace is guaranteed to not fit the original model. To each of these logs, we applied IM, IMf, IMd, and IMfD and measured recall and precision with respect to the unchanged system B. No artificial RAM limit was enforced.

Notice that when \(10^5\) noisy traces are added, only 9 % of the traces remains noise-free. The directly-follows graph of this noisy log contains 118,262 directly-follows edges, while the graph of the model would just have 32,012. Moreover, almost all activities are observed as start activities (946) and end activities (929) in this log (vs 244/231 in the model). It is clear that without serious noise filtering, no algorithm could make any sense of this log.

Results Figure 19 shows the comparison of the 2 noise filtering algorithms IMf and IMfD on the logs of B with various noise levels. Surprisingly, IMfD performs better than IMf: IMfD achieves consistently higher precision at only slight drop in recall compared to IMf whose precision drops to 0.8, which is close to the flower model (i.e. no actual restriction of behaviour). The perfect recall obtained by IM on large lots can be explained by the fall-throughs of IMd and IM: if no cut can be found, a flower model is selected. For IM and IMd, we consistently observed lower precision scores for all models compared to both IMf and IMfD but a consistent fitness of 1.0 (which is easily explained by their lack of noise handling capabilities); exact numbers and more details are available in Appendix 8.

A manual inspection of the models returned shows that all models still give information on the overall structure of the system, while for larger parts of the model no structure could be discovered and a flower submodel was discovered. In this limited experiment, IMfD is the clear winner: it keeps precision highest in return for a little drop in recall. We suspect that this is due to IMfD using less information than IMf and therefore the introduced noise has a larger impact (see Sect. 4.3). More experiments need to evaluate this hypothesis.

To answer the second part of RQ3 we investigated how infrequent behaviour, i.e. structured deviations from the system, influences rediscovery. The set-up of this experiment is similar to the noise experiment, i.e. t deviating traces are added. Each deviating trace contains one structural deviation from the model, e.g. for an \(\times \), two children are executed. For more details, please refer to Appendix 4.

Similar to the noise experiment, the log with \(10^5\) added infrequent traces has a lot of wrong behaviour: without infrequent behaviour, its directly-follows graph would contain 32,012 edges, 244 start activities, and 231 end activities, but the deviating log contained 118,262 edges, 946 start activities, and 929 end activities. That means that if one would randomly pick an edge from the log, there would be only 27 % chance that the chosen edge would be according to the model. Exact numbers and more details are available in Appendix 8.

Results Figure 20 shows the results of IMf and IMfD on logs of process tree B with various levels of added infrequent behaviour. Similar to the noise experiments, IMfD compared to IMf trades recall (0.95 vs 0.99) for log-precision (0.95 vs 0.90). Of the non-filtering versions IM and IMd, both got a recall of 0.99, IM a model-precision of around 0.90, and IMd 0.92, and thus, IMd performs a bit better in this experiment.

We suspect that two of the inserted types of infrequent behaviour positively influenced the results: skipping a child of a \(\rightarrow \) or \(\wedge \) has no troublesome impact on the directly-follows graph for the IMd framework, but log splitting will introduce a (false) empty trace for the IM framework. The IM framework algorithms must decide to ignore this empty trace in later recursions, while IMd framework algorithms simply don’t see it. Altogether, IMfD performs remarkably well given event logs containing structured deviations from the system.

To test real-life performance of the new algorithms and to answer RQ4, i.e. whether the newly introduced fitness and precision measures can handle larger logs and how they compare to existing measures, we performed a fourth experiment.

Experimental set-up In this experiment, we take four real-life event logs. To these event logs, we apply the algorithms \(\alpha \), HM, IM, IMf, IMd, and IMfD and analyse the resulting models manually. The algorithms CCM and MPM are not publicly available and were excluded.

Second, in order to evaluate the pcc framework, we apply the pcc framework and existing fitness [51] and log-precision [1] measures to the discovered models. The models by HM and \(\alpha \) were unsound and had to be excluded (we introduced some heuristics for unsound models, but they did not help in this case. For more details, see Appendix 5). Furthermore, IM and IMd do not apply noise filtering and therefore their models are often flower models, so these were excluded as well.

To provide a baseline for log-precision, we add a flower model to the comparison: a flower model allows for all behaviour, so intuitively has the worst precision. Therefore, we scale (normalised) the log-precision according to this baseline:Intuitively, scaled precision denotes the linear precision gain with respect to a flower model, i.e. 0 for the flower model itself and 1 for perfect precision. The pcc framework-fitness measure and the existing fitness measure [51] are conceptually similar, so they are not scaled.

Logs We analysed four real-life logs. The first log (BPIC11) originates from the emergency department of a Dutch hospital [56]. BPIC11 describes a fairly unstructured process and contains 624 activities, 1143 traces (patients), and 150,291 events. In our classification, it is a complex and medium log. The second log (BPIC12) originates from a Dutch financial institution and describes a mortgage application process [57]. It contains 23 activities, 13,087 traces (clients), and 164,506 events and is therefore a medium log. BPIC12 was filtered to only contain events having the ‘complete’ life cycle transition, i.e. ‘schedule’ and ‘start’ events were removed. The resulting log was included, as well as the logs for three activity subsets, (BPIC\(|_A\), BPIC\(|_O\), and BPIC\(|_W\)), e.g. BPIC\(|_A\) only contains activities prefixed by A. The third log (SL) originates from the repeated execution of software: SL was obtained by recording method calls executed by RapidMiner, using 5 operators, each corresponding to plug-ins of RapidProM. The recording was performed using the Kieker tool (see http://​kieker-monitoring.​net) and repeated 25 times with different input event logs. In total, the event log (SL) has 25 traces, 5,869,492 events, and 271 activities, which makes it a large. Its traces are particularly long: up to 1,151,788 events per trace. The fourth log (CS) originates from a website of a dot-com start-up and represents click-stream data, i.e. every website visitor is a trace, and each page visited is an events [26]. CS contains 77,513 traces, 358,278 events, and 3300 activities, which makes it more complex and medium. As described in the ‘Introduction’, much bigger event logs exist. We were able to run IMd and IMfD on larger and more complex logs, but we were unable to compute metrics or even visualise the resulting models. Therefore, we do not report on such logs in this evaluation.

On BPIC11, IM, IMf, IMd, and IMfD produced a model.

On BPIC12, all the algorithms produced a model. We illustrate the results of the experiments on BPIC12, filtered for activities starting with A (BPIC\(|_A\)): Fig. 21 shows the model returned by IMf; Fig. 22 the model by IMfD. This illustrates the different trade-offs made between IM and IMd: these models are very similar, except that for IMf, three activities can be skipped. Operating on the directly-follows abstraction of the log, IMfD was unable to decide to make these activities skippable, which lowers fitness a bit (0.816 vs 0.995) but increases precision (1 vs 0.606).

On the SL log, HM, IM, IMf, IMd, and IMfD produced a model, and \(\alpha \) could not proceed beyond passing over the event log. The models discovered by HM, IMf, and IMfD are shown in Fig. 23 (we uploaded these models to http://​www.​processmining.​org/​blogs/​pub2015/​scalable_​process_​discovery_​and_​evaluation). The model discovered by HM has 2 unconnected parts, of which one part cannot be executed. Hence, it is not a workflow model, thus not sound and, as discussed before, difficult to be analysed automatically. In the models discovered IMf and IMfD, the five RapidProM operators are easily recognisable. However, the models are too complex to be analysed in detail by hand.² Therefore, in further analysis steps, problematic parts of the models by IMf and IMfD could be identified, the log filtered for them, and the analysis repeated.

On the CS log, IM, IMf, IMd, and IMfD produced a model. IMd and IMfD returned a model in less than 30 s using less than 1 GB of RAM, while IM and IMf took more than an hour and used 30 GB of RAM. As CS has five times more activities than SL, we could not visualise it. This illustrates that scalable process discovery is a first step in scalable process mining: the models we obtained are suitable for automatic processing, but human analysis without further visualisation techniques is very challenging.

Results for log conformance checking Table 4 shows the results, extended with the approximate running time of the techniques.

Fitness scores according to the pcc framework differ from the fitness scores by van der Aalst [51] by at most 0.05 (except for BPIC12\(|_A\) IMfD). Thus, this experiment suggests that the new fitness measurement could replace the alignment-based fitness [51] metric, while being generally faster on both smaller and larger logs, though additional experiments may be required to verify this hypothesis. More importantly, the pcc framework could handle logs (BPIC11, SL, CS) that the existing measure could not handle.

Comparing the scaled precision measures, the pcc framework and the existing approach agree on the relative order of IMf and IMfD for BPIC12\(|_A\) and BPIC12\(|_O\), disagree on BPIC12, and are incomparable on BPIC11, SL, and CS due to failure of the existing measure. For BPIC12\(|_W\), IMfD performed worse than the flower model according to Adriansyah et al. [1] but better according to our measure. This model, as shown in Fig. 24, is certainly more restrictive than a flower model, which is correctly reflected by our new precision measure. Therefore, likely the approach of Adriansyah et al. [1] encounters an inaccuracy when computing the precision score. For BPIC12, precision [1] ranks IMf higher than IMfD, whereas our precision ranks IMfD higher than IMf. Inspecting the models, we found that IMf misses one activity from the log while IMfD has all activities. Apparently, our new measure penalises more for a missing activity, while the alignment-based existing measure penalises more for a missing structure.

A similar effect is visible for SL: IMf achieves a lower precision than the flower model. Further analysis revealed that several activities were missing from the model by IMf. The following example illustrates the effect: let \(L = \{\langle a, b \rangle \}\) be a projected log and \(M = a\) a projected model. Then, technically, their conjunction is empty and hence both precision and recall are 0. This matches intuition, as they have no trace in common. This sensitivity to missing activities is inherent to language-based measuring techniques. From the model discovered by IMf, 45 activities are missing, which means that of the 36,585 pairs of activities that are considered for precision and recall, in 11,160 pairs a missing activity is involved.

This experiment does not suggest that our new measure can directly replace the existing measures, but precision seems to be able to provide a categorisation, such as good/mediocre/bad precision, compared to the flower model.

Altogether, we showed that our new fitness and precision metrics are useful to quickly assess the quality of a discovered model and decide whether to continue analyses with it or not, in particular on event logs that are too large for current techniques. In addition to simply providing an aggregated fitness and precision value, both existing and our new technique allow for more fine-grained diagnostics of where in the model and event log fitness and precision are lost. For instance, by looking at the subsets \(a_1 \ldots a_k\) of activities with a low fitness or precision score, one can identify the activities that are not accurately represented by the model and then refine the analysis of the event log accordingly.

For most event logs, IMfD seems to perform comparably to IMf. However, please notice that by the nature of fitness and log-precision, for each event log there exists a trivial model that scores perfectly on both, i.e. the model consisting of a choice between all traces. As such a model provides neither any new information nor insight, generalisation and simplicity have to be taken into account as well. As future work, we would like to adapt generalisation metrics to be applicable to large event logs and complex processes as well.