Nowadays, many business processes maintain a significant amount of data regarding their executions in the form of events logs. The predictive process monitoring field is concerned with the exploitation of such event logs to predict how such executions will unfold up until their completion. Predictive process monitoring includes various tasks: one of them is the next activity prediction, that is concerned with the prediction of what will next happen in an execution.

In the last years predictive process monitoring, and particularly next activity prediction, is receiving an ever-increasing attention, and researchers are tackling the problem using various deep learning approaches [3,4,13–15,19,21]. It is also known that using graphs is an extremely convenient way of representing process executions [6,20]. Recently, a new type of neural network architecture is gaining ground in the deep learning community: the graph neural network [16,24]. Still, there is almost no work in the literature that evaluates the possibility of exploiting such family of networks for the predictive process monitoring tasks. Driven by this lack of studies, we introduce a methodology to properly exploit the graph representation of processes executions [6] for the next activity prediction task.

In particular, our proposal requires a business process event log and a model of such process, which are used to build for each trace a proper corresponding instance graph. From this graph representation, the dataset is then created and the Deep Convolutional Graph Neural Network [25] is trained to perform the prediction for next activity. Experimental results show that information contained in instance graphs, in particular concerning the parallelism among activities, can improve the prediction accuracy.

The rest of the paper is organized as follows: in Sect. 2 a review of the taskrelevant literature is performed. Section 3 describes the proposed methodology. In Sect. 4 a comparison with the results from the relevant literature is performed and commented. Finally, in Sect. 5 we draw some conclusions and list further directions of research.

# **2 Related Work**

In the scientific community there is an ever-increasing interest in the application of deep learning techniques to predictive process monitoring tasks. In [18] the authors proposed to adopt an LSTM architecture for the one step ahead event prediction and the suffix prediction, using the one-hot encoding of the associated activity and three temporal features related to the event's timestamp. The LSTM architecture has also been used by [3,8,13]. The approach in [8] predicts only the next activity type, while [13] predicts the next activity and all the associated categorical attribute. The authors of [3] combine both [8] and [18] approaches to extend [8] to the next completion time prediction, using an abstract notion of class resource, i.e. group of resources that usually perform similar activities. Recently, in [14] a CNN architecture has been proposed: the authors convert the sequential temporal data in the log into a spatial representation to then treat data as images. In [15] the approach has been further extended by the authors.

The of use Generative Adversarial Nets (GANs) is proposed in [19] to address the next event prediction task, tackling in this way the lack of sufficient training data that often impact performances. In the GAN approach the authors used LSTM networks for both the generator and discriminator. For this reason they trained various networks, each one over sub-sequences of processes of specific length, thus producing more than one prediction model for each process, the same limit of the other LSTM based approaches.

In 2008 Scarselli et al. introduced "The Graph Neural Network Model" (GNN) [16], a neural network model capable of processing data in graph domains. Since their definition, graph neural networks have been increasingly used in several fields. In a recent survey [24] it has been proposed *a new taxonomy to divide the state-of-the-art GNNs into four categories, namely, recurrent GNNs, convolutional GNNs, graph autoencoders, and spatial-temporal GNNs*. In the same work the authors also outline the various application fields.

It is relevant to note that very recently a proposal of usage of Graph Convolutional Neural Network in the next activity and timestamp predictions has

**Fig. 1.** The BIG-DGCNN methodology pipeline

been formulated by [21]. Their approach differs from the one proposed in the present paper as they propose to use a Directly Follows Graph representation to model the traces while our approach adopts an Instance Graph representation. Furthermore, the network architecture used in this work and in [21] are different. In [21] a single graph convolutional layer followed by two fully connected layers are used, while in the present paper a more elaborated architecture is adopted as described in Sect. 3. Also lately, in [23] the author explored the opportunity of exploiting gated graph neural network for the next activity prediction. In the work different graph representations are tested but are only compared with self implemented baselines, focusing the work exclusively on network architecture.

#### **3 Methodology**

In this Section we discuss the proposed methodology, first explaining the rationale of the whole pipeline shown in Fig. 1, then delving into its relevant aspects.

The goal of the present work is to define a robust approach that makes use of information about the parallelism among activities in the next activity prediction task. To this end, we propose to represent each trace with its corresponding Instance Graph (IG), and to process IGs by graph neural networks, that are designed to natively manage graph structures.

It is known that replaying a trace on a Petri net it is possible to produce an instance graph representing the process execution [6]. The starting point of our methodology is thus an event log and a model of the process expressed as Petri net. The model can be given by a domain expert, opening to the possibility to provide the desired perspective over the process, or a Petri net can be derived by some process discovery algorithm. In both cases, a problem arises with highly variable processes whose event log includes many non-conforming traces. This situation often occurs when an a-priori model has been defined for a process that rapidly evolves thus making the model obsolete; or in decision-intensive processes where only a high-level model can be defined and executions vary from case to case (e.g. care process in a hospital). When process discovery is exploited to synthesize a process, lossy algorithms may be adopted (e.g. Heuristic Miner, infrequent Inductive Miner) that discard uncommon behaviours to ensure simpler and more meaningful models. In the presence of non-conforming traces a simple replay will lead to not valid IGs, e.g. disconnected graphs, or graphs with more than one terminal node. To deal with this issue, our approach also provides a repairing of non-conforming traces by the adoption of the BIG algorithm [5]. This prevents the loss of data and grants to our system the possibility to predict also uncommon events. From BIG-generated IGs the dataset is then created and the graph neural network trained to perform the prediction of the next activity. Among the different architectures existing in the literature, the Deep Graph Convolutional Neural Network (DGNN) [25] has been chosen. In the following we will refer to our methodology as BIG-DGCNN.

#### **3.1 Building Instance Graphs**

An Instance Graph (IG) is a graph that describes a specific execution of some process model. In an IG each node represents an activity, and an edge between activity A and activity B denotes the existence of a *causal relation* between A and B, namely the fact that B cannot be executed until A is terminated; in other words, the execution of B depends on the execution of A. For a more formal definition of instance graphs and causal relations see [6]. In an instance graph parallelisms are shown besides causal relations, while choices are not represented. This is obvious, since in each single execution choices have already been made. Activities that can be done in parallel within one instance can appear in any order in the trace without changing the resulting instance graph. Hence, an execution is represented by an unique IG, which in turn represent different traces.

Instance graphs can be built from a set of traces in an event log and the corresponding process model. In this paper we refer to the Building Instance Graph (BIG) algorithm proposed in [5]. Unlike other approaches in the literature, BIG enables the representation of parallel behaviors and is able to handle traces that do not conform to the model. BIG is a two-steps algorithm: first an IG is extracted for each trace, then IGs from non-conforming traces are repaired. In the first step, a node is created in the IG for each event of the trace and the node is labeled with both the activity associated with the given event and the position of the event in the trace. For each pair of events (e*i*, e*j* ) with i<j such that causal relation exists between the corresponding activities in the model, an edge is inserted between the corresponding nodes in the IG if and only if between the pair of events there is neither another causal successor of e*i*, nor a causal predecessor of e*j* .

It is worth noting that, if the trace does not fit the model, the corresponding IG is affected by several issues, e.g. being a disconnected graph and having multiple terminal nodes. From a semantic point-of-view these IGs represent many more behaviours than the model actually allows for, namely they over-generalize. Hence, the representation of the process behavior provided by these IGs is very poor. In order to mitigate these issues, in [5] a procedure for the repair of IGs is proposed.

First, non-synchronous movements in the trace, which lead to issues in the IG, are identified by using aligned-based conformance checking technique [2], which returns the kind of non-synchronous movements and their position in the trace. This information is used to repair each move-in-the-model and each move-in-thelog occurring in the alignment. The former leads to disconnected graphs, which are repaired by identifying nodes corresponding to activities that are in a causal relation with the move-in-the-model and properly connecting them. For each move-in-the-log, the repair procedure changes the edges connecting the nodes corresponding to the events before and the events after the non-synchronous event; the causal relations among the activity corresponding to move-in-the-log and activities related to its predecessors and successors in the trace are used to build new edges.

#### **3.2 Data Preprocessing**

This Section describes the processing of the log to obtain the dataset for training and testing. First of all, since a log not necessarily has single specific ending and starting activities, we introduce such artificial events in the logs. This is done to guarantee that a trace always has a termination activity and to ensure that parallelism at the beginning and end of a process execution are properly represented in the IG. Second, BIG is applied to obtain an IG for each trace.

The approach of this paper learns a function that, given a *graph prefix* τ*g* of dimension g, returns a label a that can be interpreted as the next performed activity in the process execution. Hence, the third step of the proposed methodology is to build the pairs (τ*g*, a) from an IG for any g ∈ {2,...,N − 1} where N is the number of nodes in the IG (i.e. the trace length). Therefore from one IG, we produce N − 2 pairs. The procedure is repeated for every IGs in the dataset.

Each node in an IG has a progressive index associated with it that represents its position in the trace. This index determines an order of the nodes, which we use to progressively build the graph prefixes from the full IG. We denote by a*i*, i = 1,...,N the activity associated with the node of index i.

Given an IG, the graph prefix τ2 is obtained by selecting the first two nodes and the edges between them. This prefix is labelled with the activity a3 of the next node (Fig. 2). The next prefix is simply derived by τ2, extending it with the node of index 3 and the edges connecting it to τ2. The associated label is a4 (Fig. 3). Iteratively, the procedure re-build the whole instance graph until the last node is selected as label.

We adopt the one-hot encoding representation for the set of activities in the log.

#### **3.3 Deep Graph Convolutional Neural Network**

In this paper, we use a variant of the Deep Graph Convolutional Neural Network (DGCNN) proposed in [25]. The DGCNN is composed of three sequential stages. In Fig. 4, we show a representation of the overall neural network architecture. First it has several graph convolution layers which extract the features from the nodes local substructure and define a consistent vertex ordering. Second it has a SortPoolingLayer which sorts the vertex features according to the order defined in the previous stage, selecting the top nodes. In this way the dimension of the input is unified. At last, a 1-D convolution layer and a dense layer take the obtained representation to perform predictions.

**Fig. 2.** First labelling step

**Fig. 3.** Second labelling step

The graph convolution layer adopted by DGCNN is represented by the following formula:

$$Z = f(\tilde{D}^{-1}\tilde{A}XW) \tag{1}$$

where A˜ = A + I is the adjacency matrix (A) of the graph with added self-loops(I), D˜ is its diagonal degree matrix with D˜*ii* = - *j* A˜*ij* , X ∈ R*n*×*c* is the graph nodes information matrix (in our case the one-hot encoding of the activity labels associated to the nodes), W ∈ R*c*×*c*- is the matrix of trainable weight parameters, f is a nonlinear activation function, and Z ∈ R*n*×*c*- is the output activation matrix. In the formulas, n is the number of nodes of the input graph (in our case the graph prefix), c is the number of features associated to a node, and c is the number of features in the next layer tensor representation of the node.

In a graph, the convolution operation aggregates node information in local neighborhoods so to extract local structural information. In order to extract multi-scale structural features, multiple graph convolution layers (Eq. 1) are stacked as follows:

$$Z^{k+1} = f(\tilde{D}^{-1}\tilde{A}Z^kW^k) \tag{2}$$

where Z0 = X, Z*k* ∈ R*n*×*ck* is the output of the k*th* convolution layer, c*k* is the number of features of layer k, and W*k* ∈ R*ck*×*ck*+1 maps c*k* features to c*k*+1 features.

The graph convolution outputs Z*k*, k = 1, ..., h are then concatenated in a tensor Z1:*h* := [Z1, ..., Z*h*] ∈ R*n*×*h* 1 *ck* which is then passed to the Sort-PoolingLayer. It first sorts the input Z1:*h* row-wise according to Z*h*, and then returns as output the top m nodes representations, where m is a user-defined parameter. This way, it is possible to train the next layers on the resulting fixedin-size graph representation.

In the original proposal the DGCNN includes a 1-D convolution layer, followed by several MaxPooling layers, one further 1-D convolution layer followed by a dense layer and a softmax layer.

In the present paper we simplify the architecture leaving only one 1-D convolution layer with dropout [17] followed by a dense and a softmax layer. This is because the process mining domain tend to present smaller graphs in comparison with those of typical application domains of graph neural networks [24].

For further information on the architecture we refer the interested reader to [25].

**Fig. 4.** DGCNN architecture. Taken from [25].

#### **4 Experiments**

#### **4.1 Experimental Setup**

In this Section, we characterize the benchmark datasets used, then we discuss the setting of parameters for the algorithms used in the experiments.

**Datasets.** In order to be comparable with the literature [3,14,18,21], we tested our approach on 2 commonly used benchmark datasets, namely *Helpdesk* and *BPI12W*.

The *Helpdesk* dataset [22] contains traces from a ticketing management process of the help desk of an Italian software company. In this process all execution instances start with the insertion of a new ticket into the ticketing management system.

**Table 1.** Overview of benchmark dataset. *|*σ*|* is used to represent the trace length.

The *BPI12* dataset [7] is taken from a Dutch Financial Institute. The process represents a personal loan or overdraft applications within a global financing organization. The event log is a merge of three intertwined sub processes, related to the evolution of the status of the loan/draft application (*BPI12A*), of the work items belonging to the application (*BPI12W* ), and of the offer belonging to the application (*BPI12O*) respectively. We considered the *BPI12W* sub-process. Furthermore, as usually done, we retained only the completed events in the log. Table 1, shows the characteristics of both datasets.

We hasten to note that *BPI12W* execution instances show no parallel activities, while some level of parallelism exists in *Helpdesk* Thus the selection of these datasets allows us to better appreciate the impact of parallelisms on performance.

Finally, in order to be as much comparable as possible with the literature, we split each log keeping the first (chronologically ordered) 67% of the traces for training and the remaining part for testing.

**Parameter Settings.** In the BIG-DGCNN methodology there are two main algorithms that require the setting of parameters: the infrequent Inductive Miner (iIM) [12] used to derive the Petri net representing the process models requested for the execution of the BIG algorithm, and the DGCNN. Regarding iIM, the noise threshold must be set. This threshold is used to determine how much infrequent behaviour will be filtered out when building the model. In choosing such parameter we tested the fitness of the resulting model (i.e. the extent to which the discovered model can accurately reproduce the cases recorded in the log). We changed the noise threshold with 10% step from 0% to 100% and selected the smallest noise threshold that granted at least a 90% fitness. In this way, we obtain processes that are capable of modeling a vast majority of traces while still maintaining a good degree of generalization, thus emulating a model provided by an expert, and putting us in a close-to-real setting.

Regarding the parameters of the DGCNN, as stated before we set the number of 1-D convolution layers to one, followed by a dense layer, both with 32 neurons. We used ADAM [10] as optimization algorithm and trained the network for 100 epochs with an early stopping. We used as loss function the categorical cross entropy. For both datasets we varied the following parameters:

The configurations that provide the best accuracy are shown in Table 2.

**Table 2.** Best network parameters for the dataset.

**Tools and Hardware.** All the experiments have been performed using pytorch geometric [9] with torch version 1.8.1, on a Tesla T4 GPU, a Intel(R) Xeon(R<EMAIL_ADDRESS>GHz, and a 12 GB RAM.

#### **4.2 Results**

Table 3 shows the accuracy achieved on the selected datasets, by our approach and other approaches exploiting different neural network architectures.

We can see that on Helpdesk BIG-DGCNN achieves the best performance. It is worth noting that in all the competitor approaches instances are described by a richer set of features, like time information, while our input graphs encode only activity labels and flow information.

On the other hand, on the BPI12W dataset there is a relevant performance degradation w.r.t. the other methods. As noted before, BPI12W shows no parallel activities. This seems to confirm our hypothesis that properly taking into account information on parallelisms can be beneficial to the next activity prediction, whilst graph neural networks do not develop their full potential on sequential processes. The hypothesis also gains confidence when the BIG-DGCNN performances are compared against the results presented in [19] on the whole BPI12

**Table 3.** Literature comparison, measured accuracy

dataset. There, plain CNN [14], and LSTM [3,18] approaches has been compared to a LSTM trained in a GAN framework. BIG-DGCNN is able to achieve an accuracy of 76.45% which is higher than the accuracy presented for all the plain methods, although it is lower than that achieved by LSTM+GAN. We remark that GAN is a novel learning framework, where any neural network architecture can be adopted. It is possible that the adoption of graph neural networks like those presented in this work could further improve performance, solving also a limit of the LSTM network used in [19] which is constrained to fixed size prefixes, hence forcing the training of a specialized network for every desired prefix length. We plan to experiment the GAN framework with graph neural networks in future work.

Since [21] also adopts a graph neural network architecture, one may want to analyse the reasons under the different accuracy. Various factors can be responsible for this: first, [21] adopts directly follows graphs, which are derived at a process level, while we build and properly repair the instance graph for each trace. Second, the representation of the graph is performed in a different way. The approach described in [21] only takes into account the last occurred event of a sequence of events with the same activity label when building the input graph. On the contrary, our approach considers all passed events of the trace, including the events relative to repeated actions. Third, the network used in this work is endowed with several graph convolution layers, while that used in [21] is a single layer graph convolutional neural network [11] variant.

#### **5 Conclusions and Future Works**

The main contribution of this work is the definition of BIG-DGCNN, a methodology to address the task of next activity prediction exploiting information about parallelism among activities in a process. The methodology adopts BIG [5] to repair non-conforming traces in order to always build a fully representative instance graph. Then it uses a rather new kind of neural network architecture, the Deep Graph Convolutional Neural Network [25], that is capable of effectively using the structural information of a graph in its functioning. The comparison with the literature highlights that BIG-DGCNN show promising performance in datasets relative to process with a consistent presence of parallelism, while performing less effectively in sequential datasets like BPI12W. Although it is well known that parallelism is a characterizing feature of business processes [1], variants of the approach that can better deal with sequential dataset can be worth of investigation. Other interesting future research directions include:

# **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Can Deep Neural Networks Learn Process Model Structure? An Assessment Framework and Analysis**

Jari Peeperkorn1(B), Seppe vanden Broucke1,2, and Jochen De Weerdt1

1 Research Center for Information Systems Engineering (LIRIS), KU Leuven, Leuven, Belgium

<EMAIL_ADDRESS>2 Department of Business Informatics and Operations Management,

Ghent University, Ghent, Belgium

**Abstract.** Predictive process monitoring concerns itself with the prediction of ongoing cases in (business) processes. Prediction tasks typically focus on remaining time, outcome, next event or full case suffix prediction. Various methods using machine and deep learning have been proposed for these tasks in recent years. Especially recurrent neural networks (RNNs) such as long short-term memory nets (LSTMs) have gained in popularity. However, no research focuses on whether such neural network-based models can truly learn the structure of underlying process models. For instance, can such neural networks effectively learn parallel behaviour or loops? Therefore, in this work, we propose an evaluation scheme complemented with new fitness, precision, and generalisation metrics, specifically tailored towards measuring the capacity of deep learning models to learn process model structure. We apply this framework to several process models with simple control-flow behaviour, on the task of next-event prediction. Our results show that, even for such simplistic models, careful tuning of overfitting countermeasures is required to allow these models to learn process model structure.

**Keywords:** Predictive Process Monitoring · Next Event Prediction · Recurrent Neural Network · Generalisation

# **1 Introduction**

In the field of process mining, a clear trend can be discerned in terms of a shift from post factum analysis to predictive and even prescriptive modelling. This is for instance clearly reflected in the surge in papers presenting deep learningbased modelling techniques to address analysis tasks including remaining time, outcome, and next event prediction. One potentially problematic issue regarding the application of such deep learning models is the fact that, to the best of our knowledge, no research has focused on investigating whether popular modelling architectures such as LSTM neural networks, can actually "learn" process behaviour from a possibly incomplete set of example traces in an event log.

Accordingly, the main contribution of this work is to propose a framework to assess the capability of deep learning-based next event prediction techniques to truly learn process model structure. The framework consists of a variant-based resampling procedure combined with novel metrics to assess fitness, precision and generalisation of the learned neural network models. In our experimental evaluation, we rely on six relatively (and purposefully) trivial process models that reflect essential control-flow constructs in business processes. By doing so, we can investigate the relation between types of control-flow behaviour (e.g. AND, XOR, and OR split/join, loops, long distance dependencies etc.) and the capacity of deep learning models to truly learn these structural patterns. Our findings indicate that even for such trivial models, and in particular for models with parallel behaviour, rigorous application of overfitting countermeasures is required to have any chance of steering the neural network model towards the goal of truly learning process model structure, more so when compared with other domains in which such networks have been applied. These findings have important consequences, given that real-life models and event logs are usually orders of magnitude more complex than the models used here. As such, we believe that this paper opens up an important agenda for further investigation.

Our paper is organised as follows. First, Sect. 2 discusses some relevant related work. Next, our proposed framework is explained in Sect. 3. In Sect. 4, the carefully selected artificial process models are proposed, before discussing the hyperparameter grid search and presenting the experimental results. What follows is a brief discussion of the results and their implication (Sect. 5). The paper is concluded in Sect. 6, which also provides an outlook towards future research. The synthetic data, results and trained models used and presented in this paper are available online1.

### **2 Related Work**

In recent years, within the field of Predictive Process Monitoring (PPM), a lot of attention has been attracted by deep learning-based solutions, most frequently Recurrent Neural Networks (RNN) [3,4,6,9,15,16]. Given the scope of this paper, we limit this section to a selection of PPM works addressing the next event prediction problem, i.e. given a prefix of activities, produce a probability vector corresponding with the likelihood of each respective activity occurring as the next one. In their pioneering work, Tax et al. [15] propose to use a Long Short-Term Memory network (LSTM) to predict next events and corresponding timestamps, thereby relying on one-hot encoding of the activity labels as input for the LSTM, together with their timestamps. Moreover, Evermann et al. [6] also propose the use of LSTM networks, specifically to predict full case suffixes rather than the next event only. However, they reduce the input dimension of the event labels by using vector embeddings, and include attributes such

1 https://github.com/jaripeeperkorn/GeneralizationPPM.

as resources. Camargo et al. [4] use separately trained embeddings of categorical variables and timestamps in order to predict both next events as well as future timestamps. Moreover, Lin et al. [9] use an LSTM encoder-decoder and a modulator structure to predict next events and suffixes, using both controlflow information as well as other event attributes. Recently Taymouri et al. [16] proposed a Generative Adversarial Networks approach to the problem of next event, suffix and timestamp prediction showing promising results. In Bukhsh [3] a transformer network approach is proposed to the problem of next event prediction. Transformer networks have recently been used to beat several benchmarks in other fields like Natural Language Processing [18].

Despite the drastic increase in research attention, no studies have investigated whether RNN-based architectures can actually learn process model structure. As such, it is unclear whether the generalisation that is expected from plain process discovery techniques is realised by neural network models. It has been shown that RNNs are universal approximators [12]. And while Siegelmann and Sontag [13] showed in 1995 already that RNNs are Turing complete, i.e. for any given computable function there exists a finite RNN to compute it, there is still much work on understanding what makes functions difficult to learn, let alone under the constraint of data incompleteness as is the case with business process data sets [11]. That is, whilst it might be clear that RNNs are capable to fit the given training data in the form of process cases, the central question we investigate here is whether such models can be constructed so that they are also able to generalise towards making good predictions for new unseen control-flow behaviour, which is highly likely to occur once a process starts to exhibit even a limited amount of complexity. In other words: do these models memorise the training data or truly learn the process structure?

### **3 A Framework for Assessing the Generalisation Capacity of RNNs**

With the goal of this paper in mind, we set out on developing a framework that is capable to assess to what extent RNN-based architectures are capable to learn process model structure. For an introduction on how RNNs work and how they can be used in predictive process monitoring, the interested reader is referred to [6]. This framework relies on a specific resampling procedure combined with a set of new metrics to quantify recall, precision and generalisation. Recall that we restrict ourselves to next event prediction models, however, an extension to suffix prediction is trivial. Moreover, given that many remaining time or outcome prediction models also rely on incorporating control-flow information, it can be expected that these models too would benefit from proper generalisation, if at all possible.

#### **3.1 The Resampling Procedure**

A schematic overview of the assessment framework is shown in Fig. 1. We start from a (simple) process model and play-out the model to obtain a corresponding event log. We assume that we work in a setting where the number of variants (i.e. distinct traces in terms of the events and their order), is bounded. Therefore, in case of loops, we assume a maximum number of times a certain marking can be visited. Once the event log is obtained, we determine all of its unique control-flow variants. Next, a resampling procedure at the level of variants is performed to construct training and test sets. For instance, one can decide to simply retain all cases pertaining to one single variant in the test log, resulting in a "leave-one-variant-out cross-validation" (LOVOCV).

**Fig. 1.** Overview of the setup.

Thus, starting from the complete event log, which is referred to as the *Train+Test log (Tr+Te)*, we single out all cases pertaining to one or more variants to form the *Test log (Te)*. The remaining variants form the *Training log (Tr)*, which is split into all possible prefixes to train the model. From this set of prefixes, a *Validation log (Val)* is created, mainly to allow the training procedure of the LSTMs to use early stopping. For now, we simply perform a random selection of 20% of the *Training log*'s prefixes. The *Training* and *Validation log*'s prefixes are then used to train a model for next event prediction using the observed next events of every prefix as the target. Accordingly, the model is trained to predict for every prefix what the subsequent event's activity label will be. As such, the model outputs a probability for each of the different activities in the activity vocabulary. Once trained, we use the RNN model to simulate a *Simulated log (Sim)* as follows. We start by presenting the RNN with a prefix only containing the beginning of sequence token (BOS). As output, the model returns a probability for each of the possible activity labels to be the next event. Using these probabilities, we sample a possible next event, to be appended to the existing prefix. Subsequently the prefix is used to sample a next event in the same way. We do this until we reach the end of sequence token (EOS) or a certain predetermined maximum size is reached. LSTMs have been used as generative models similarly in [4]. The idea is that, by simulating an event log from the RNN, we should ideally obtain an event log that is behaviourally highly similar to the event log that we started from. That is, we expect that, even when leaving out one single variant, the RNN should be able to (1) generalise this variant from the observed variants in the Training log, (2) avoid creating variants that were not observed in the original event log (Train+Test), and (3) contain all the variants present in the Training log.

#### **3.2 Metrics**

Accordingly, we define novel recall, precision and generalisation metrics that can quantify these three criteria. Based on the *Training* (including *Validation*), *Test* and *Simulated* logs, we define the following metrics:

$$Fitness = \sum\_{v \in Var(Tr)} \frac{Min\left(Occ(v, Sim), Occ(v, Tr)\right)}{|Tr|} \tag{1}$$

$$Precision = \sum\_{v \in Var(Sim)} \frac{Min\left(Occ(v, Sim), Occ(v, Tr + Te)\right)}{|Sim|} \tag{2}$$

$$Generalisation = \sum\_{v \in Var(Te)} \frac{Min\left(\text{Occ}(v, Sim), Occ(v, Te)\right)}{|Te|} \tag{3}$$

with |*L*| denoting the number of traces in an event log *L*, *Var(L)* denoting the set of variants of an event log *L* and *Occ(v,L)* a function denoting the frequency or multiplicity of a variant *v* in an event log *L*.

Each of these metrics outputs a value between 0 and 1. Beware that these metrics make use of nominal counts, so they only make sense when the original *Train+Test log* and the *Simulated log* contain the same amount of traces. If not, the metrics will have to be corrected. First of all, the fitness metric measures to what extent all of the variants present in the *Training log* are also present in the *Simulated log*. This is because we want the RNN to learn and replicate all of the behaviour found in the *Training log*. Moreover, we expect that the frequency of each variant in *Simulated log* is, more or less, equal to the frequency of observation of that variant in the *Training log*. Therefore, the fitness measure will punish if a certain variant is under-represented in the *Simulated log*. Secondly, the precision metric measures whether the RNN allows for too much behaviour, i.e. traces that have not been seen in *Train+Test log*. Moreover if certain correct variants are over-represented in the *Simulated log* the precision will also decrease. Finally, the generalisation metric quantifies to which extent the RNN is able to generalise, i.e. whether it is able to learn and reproduce correct but unseen behaviour. Therefore, the metric measures whether the frequency of occurrence of the unseen variant(s) in the *Test log* is actually reproduced to the same level in the *Simulated log*.

#### **4 Experimental Evaluation**

With the introduction of our assessment framework, consisting of a variant-level resampling procedure combined with these three metrics, we can now devise an experimental setup to evaluate the generalisation capacity of RNNs. While it is theoretically possible to perform such a assessment using complex artificial and even real-life logs and models, we opt to focus on simple models, as these provide a *sine qua non* condition in terms of investigating whether such models can deal with the aforementioned control-flow patterns at all.

#### **4.1 Process Models**

Hence, we generated artificial process models that represent main modelling constructs. In order to obtain the full event log (i.e. the *Train+Test log*), we use the play-out functionality of the Python Process Mining library PM4PY [2]. The models are depicted as Petri nets in Fig. 2. Model 1 is a simple linear model with a parallel gateway consisting of five parallel branches containing each one single activity. This process has 120 (equally likely) control-flow variants. In Model 2, a process model with 128 (equally likely) control-flow variants is created by sequencing seven exclusive OR (XOR) splits. Similarly, Model 3 consists out of eight XOR splits, but with a long-term dependency added in. Model 4 consists of three inclusive OR (IOR) splits, where at least one, but possibly both of the two activities have to occur. This leads to in total 64 control-flow variants. Model 5 shows a process which has two parallel paths, consisting of five activities each, leading to 125 control-flow variants with varying likelihood. Finally, Model 6 shows a process with three different possible loops (containing two activities each). The amount of possible control-flow variants is technically unlimited, so that we restrict each marking to be visited a maximum of three times, we keep 27 different variants.

Model 1: Parallel Model with 120 variants.

Model 3: Model with multiple XOR splits and a long term dependency, 128 variants.

Model 2: Model with multiple XOR splits, 128 variants.

Model 4: Model with multiple IOR splits, 64 variants.

Model 5: Model with one big parallel split, 126 variants. Model 6: Model with 3 different size 2 loops.

#### **4.2 Hyperparameter Search**

The generalisation capacity of RNNs strongly depends on tuning its hyperparameters. This is an essential part of the training procedure. An overview of the investigated hyperparameters can be found in Table 1. A maximum prefix length of size 10 was used (with longer prefixes left-truncated), unless explicitly mentioned otherwise. The model's weights are optimised using the Adam [8] optimiser with a mini-batch size of 128 prefixes, using a starting learning rate of 0*.*005. The learning rate is decreased when the accuracy on the validation set has not decreased for over 10 epochs and the training is stopped (early stopping) when the accuracy has not increased for over 30 epochs (or when a maximum of 600 epochs is reached). The loss function used is categorical crossentropy. For clarity, the RNN is trained optimising accuracy in a "classical" sense, i.e. whether the activity predicted by the model to be the most probable activity is actually correct. As mentioned earlier, the usage of an embedding layer is the first binary hyperparameter. Where applicable, the dimension of the embedding was set to - √4 Act. Voc. Size, as was done in [4] (note that the embeddings were pretrained independently from the RNN in that work, though we used this value as a starting point in this investigation). The number of stacked LSTM layers is varied between one and two, with the layers' hidden dimension size set to 16, 32 or 64 units. Furthermore, we experiment with different values for overfitting countermeasures like regularisation and dropout. We try five different values for *L1* (*Lasso*) and *L2* (*Ridge*) regularisation [20], which adds a small penalty to the model based on the absolute or squared value of the weights respectively. In order to limit the scope of our grid we change *L*1 and *L*2 together. Lastly we also added the dropout hyperparameter [14], in which, per epoch, a fraction of the nodes is selected to be ignored during training, reducing the likelihood of overfitting to the training data. In this paper we experiment with multiple dropout values (including no dropout). There are multiple ways to introduce dropout when using RNNs related to the internal structure of such units; in this work we chose to add dropout to the output of the LSTM layer (note that dropout on the inputs would lead to removing certain steps of a prefix which is undesirable in our setting). We omitted the use of batch normalisation due to its limited effectiveness when applied to RNNs [5]. In future work, however, we could explore the effectiveness of *Recurrent Batch Normalisation* [5] and *Layer Normalisation* [1]. The neural network implementation was created using the Python library Keras2.

**Table 1.** The hyperparameter values used in the grid search.

2 https://keras.io.

This led to 180 different hyperparameter configurations to iterate over. Based on some preliminary exploration, it was noticed that an RNN, without explicit overfitting countermeasures like regularisation and dropout, struggled to generalise for the process in Model 1. In order to contain computational time, and because the goal is to obtain a RNN that is able to generalise different types of behaviour at the same time, we opted to only perform one grid search on the event log obtained from this process model. The best hyperparameter settings for Model 1 were subsequently used and applied to all other models. For obtaining optimal hyperparamaters using Model 1, we conducted a tailored leave-onevariant-out cross-validation (LOVOCV) procedure as introduced above. More specifically, we generated a *Train+Test log* consisting of 12.000 traces for each model. In each LOVOCV iteration, we singled out all cases pertaining to one single variant into the *Test log*. For every hyperparameter combination, we performed the tailored LOVOCV eight times, each time with a different variant in the test set. In each iteration, we obtained a *Simulated log* of equal size of the original *Train+Test log*. Based on these eight LOVOCV iterations, we calculated the three different metrics defined above, and, for each setting, took the average over the eight iterations. Note that we use the *Test log* for this hyperparameter tuning, rather than the *(cross) validation log* as is usual. Since we are not trying to compare the predictive quality of different approaches as such, this is justified. We choose to continue working with the setting showing the highest average score over all three metrics, i.e., no embedding layer, one LSTM layer of hidden size 32, an *L1* and *L2* of 0*.*001 and a *dropout* of 0*.*4. Because this model was only trained on the data of one simple process model, and the differences between certain settings were slim, we however do not want to claim this setting is ideal for each predictive process monitoring problem. However in the context of this investigation rather than optimisation experiment, we continue with this setting in the rest of the paper. Not shown here, but apparent from the hyperparameter search was: (i) for all three metrics a regularisation value of 0*.*01 resulted in low scores, (ii) no or limited application of overfitting countermeasures leads to high fitness and precision (as expected) but weak generalisation scores. We like to stress that it is therefore of the utmost importance to tune the hyperparameters correctly when training RNNs.

#### **4.3 Results**

Subsequently, we then repeat the experiment using the settled hyperparameter configuration for all models. For each of these, we applied a LOVOCV setup again, working with *Test logs* containing a single variant. As for some models the frequency of the variants is not evenly distributed and to obtain more robust results, we now conducted an exhaustive LOVOCV, i.e. the procedure is repeated as many times as the number of variants in the event log, so that every variant is used once to form the *Test log*. In the case of Model 6 (loops), we restricted the analysis to variants for which the loop is taken a maximum of three times (27 variants). This was however not restricted neither in the play-out itself, nor in the simulation with the trained LSTM, leading to more different variants in these logs. In the experiment for Model 3 (including the long-term dependency) the prefix length of the input of the RNN was set to the maximum trace length minus one instead of the default of 10 because it needed to be long enough in order to have a chance of dealing with the long-term dependency. The average values over all variants for each of the three metrics can be found on the left side of Table 2. The error intervals are calculated by taking the standard deviation over all the metric values. Various interesting observations can be made from the results. First, it can be noticed that models with parallel behaviour (Model 1, 4 and 5) are problematic for the LSTMs. One can observe some level of generalisation, but given the extremely lenient LOVOCV-setup, it is remarkable that the generalisation scores go well below 0.80. On the other hand, the LSTMs show to be much more robust when dealing with XOR-splits (Model 2 and 3) and loops (Model 6). Also the long-term dependency in Model 3 seems to be handled well by the LSTM models. The standard deviations are significantly higher for the generalisation scores as this metric seems to be more prone to fluctuations. This is most likely due to the changing *Test log*, though should be further investigated.

Up until this point we have used the most trivial setting, i.e. the leave-onevariant-out *Test log*. However, one might expect that LSMTs should be able to cope with larger fractions of unseen behaviour. Therefore, this final evaluation part addresses the use of larger test sets, in particular, leaving out 20% of the control-flow variants from the *Training log*. We repeated this three times, with each time 20% randomly selected variants. The average of the metric values for each of these experiments can be found on the right side of Table 2. The error intervals are calculated by taking the standard deviation over the metric values for the three different experiments. When comparing this with the results from the LOVOCV experiment we can see that for some models, precision seems the decrease a bit. This might suggest that because the model has less behaviour to learn the correct process model structure from, it fares worse, allowing for some extra incorrect behaviour. Fitness seems not to be affected. Generalisation also results in lower values when having a more diverse *Test log*. This is especially apparent in the process models which already yielded low generalisation scores above, like Model 4 and 5. Again the standard deviation is higher when calculating the generalisation, because it is highly dependent on which variants exactly were in the *Test log*, and of the apparently more fluctuation-prone behaviour of this metric.

#### **5 Discussion**

From the hyperparameter tuning, it appears that overfitting countermeasures like regularisation and dropout are important parameters for constructing predictive RNNs. However, precise tuning is crucial, and we therefore urge other researchers to perform a good hyperparameter experiment when training RNNs on predictive process monitoring tasks. This may require the inclusion of resampling methods as introduced here, as opposed to only holding out randomly

**Table 2.** The results on the different process models, averaged over all leave-onevariant-out experiments with every different control flow variant. And the results on the different process models when taking a *Test log* consisting of 20% of the control flow variants. Average over three different randomly selected *Test logs*.

selected prefixes. Please observe that the "best" hyperparameters were selected on the test observations for Model 1. It can be expected that standard tuning on a random validation set and thereby only optimising accuracy of next events (and not the metrics presented here), is unlikely to result in the same outcome.

LSTMs seem to be less suited for generalising process models with parallel behaviour. When the degree of incompleteness is increased, i.e. the amount of variants not seen by the RNN during training is expanded, LSTMs seem to struggle more. The generalisation, as well as the precision, decreased when increasing the amount of variants in the test set, when compared with the LOVOCV experiments.

It could be interesting to investigate to what extent the generalisation and overfitting problems could affect predictions of real-life processes, considerably more complex than the artificially created data discussed in this work. Extra overfitting measures may need to be included as well in the future. One option could be found in using a similar resampling method as used here in order to construct the *Test log*, or a hybrid approach, to create the *Validation log*. Another course of action would be to alter the loss function used to train the RNN. Important to check further is whether low generalisation scores of merely memorising and overfitting models also lead to less accurate next event predictions. We still assume proper generalisation would be beneficial in predictive task, especially with increasing complexity, and theoretically the power of deep learning models, actually lies in their generalisation capability [7]. Moreover if overfitting would not be an issue, more explainable statistical models could easily be found as well, as opposed to the black-box LSTMS, with comparable accuracy, and preference should be given to these more explainable models.

#### **6 Conclusion and Future Work**

This paper addressed the so far largely uninvestigated problem of neural networks' capability to learn the behaviour of the underlying process behind an event log. By introducing a new framework that combines a variant-level resampling scheme with three novel metrics, we were able to investigate to what extent LSTMs trained to predict the next event of a process execution are general, fit and precise. By applying this framework on several simple process models, it was shown that LSTMs can only generalise parallel behaviour to a certain extent. Even in the most lenient setting, the LOVOCV, the generalisation metric does not return values close to optimal. When increasing the amount of variants in the *Test log*, unseen by the LSTM during training, generalisation decreases further, as well as precision. This paper opens up the door for future work in predictive process monitoring to include explicit generalisation checks as well, in model selection, hyperparameter tuning and testing.

The experiments in this work were limited to only use control-flow behavior. However, since the generalization behavior investigated in this paper is only control-flow like, this choice is justified. Nevertheless, it might be interesting to investigate the effects of adding more dimensions (like timestamps and resource) to the predictive models. In future work, more synthetic logs could be investigated deepening the relation between process model behaviour and RNN generalisation. A more rigorous theoretical elaboration, similar to [17], might provide some interesting insights as well. Furthermore, it should be investigated whether new recommendations can be proposed regarding how to optimally sample training and validation sets. Also, it would be interesting to apply these metrics on models trained on real-life event logs, as opposed to only synthetic data. In this paper it was opted to first work with synthetic data since it would allow us to test different types of behaviour independently. However real-life logs are in general more complex, and in this way might present other difficulties. When doing this, it might be useful to expand the hyperparameter grid and include extra parameters such as Layer Normalization [1] and Recurrent Batch Normalization [5], and to ameliorate the overfitting measures applied in this work. Other future work can address a comparison of results presented here with the findings in recently proposed work by [19], and similarly test multiple encoding techniques like hash encoding. Moreover, an additional investigation of the attention mechanism seems worthwhile [3]. In addition, a similar experiment could be applied to alternative architectures including Convolutional Neural Networks, Transformer Networks, and GAN-style approaches. This work was also limited to only include next-event prediction models, thus it might be useful to expand the metric definitions to also be able to evaluate full suffix prediction (or even remaining time prediction). Finally, the application of neural networks to formal languages has been investigated in other domains, e.g. in [10], which could lead to more fundamental research on grammar learning capabilities of RNNs.

#### **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Remaining Time Prediction for Processes with Inter-case Dynamics**

Mahsa Pourbafrani1(B) , Shreya Kar1, Sebastian Kaiser2, and Wil M. P. van der Aalst1

1 Chair of Process and Data Science, RWTH Aachen University, Aachen, Germany<EMAIL_ADDRESS><EMAIL_ADDRESS>2 LMU Munich, Munich, Germany<EMAIL_ADDRESS>
**Abstract.** Process mining techniques use event data to describe business processes, where the provided insights are used for predicting processes' future states (*Predictive Process Monitoring*). *Remaining Time Prediction* of process instances is an important task in the field of Predictive Process Monitoring (PPM). Existing approaches have two key limitations in developing *Remaining Time Prediction Models* (RTM): (1) The features used for predictions lack process context, and the created models are black-boxes. (2) The process instances are considered to be in isolation, despite the fact that process states, e.g., the number of running instances, influence the remaining time of a single process instance. Recent approaches improve the quality of RTMs by utilizing process context related to *batching-at-end* inter-case dynamics in the process, e.g., using the time to batching as a feature. We propose an approach that decreases the previous approaches' reliance on user knowledge for discovering fine-grained process behavior. Furthermore, we enrich our RTMs with the extracted features for multiple performance patterns (caused by inter-case dynamics), which increases the interpretability of models. We assess our proposed remaining time prediction method using two real-world event logs. Incorporating the created inter-case features into RTMs results in more accurate and interpretable predictions.

**Keywords:** process mining · predictive process monitoring · remaining time prediction · inter-case dynamics behavior

### **1 Introduction**

Remaining time prediction approaches learn from historical process executions and build prediction models for running process instances, i.e., cases, based on

Funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany's Excellence Strategy – EXC 2023 Internet of Production- Project ID: 390621612. We also thank the Alexander von Humboldt (AvH) Stiftung for supporting our research.

**Fig. 1.** Our proposed framework for inter-case-aware RTMs. Patterns are discovered after detecting uncertain segments, i.e., segments causing high prediction errors due to inter-case dynamics. RTMs are trained using the extracted features from the patterns within uncertain segments.

the extracted features from the event data. Many approaches have been suggested to solve the remaining time prediction problem [17]. However, most proposed approaches have considerably high prediction errors. Based on [17], the best performing model using an LSTM neural network [10] showed a prediction error of 178.4 days on average for the Road Traffic Management (RF) event log [9]. These approaches also only consider control-flow-related aspects of processes and individual case properties, i.e., intra-case properties, while making predictions [12]. A process also has other dimensions associated with it [13]. For instance, specific rules determining scheduling and assignment of limited resources, queuing mechanism, and decision logic in the process create inter-case dependencies within the performance of process instances. Moreover, most of the effort put into this research area has focused on applying new predictive modeling techniques, which create blackbox prediction models. Considering inter-case along with intra-case process features in RTMs increases the explainability, interpretability, and accuracy of the prediction [8]. Therefore, we aim to improve the quality of RTMs and introduce more interpretability in the predictions. The accuracy of a RTM which is unaware of inter-case behavior is substantially impacted if cases in a process segment, i.e., a pair of related activities, are processed in a batch, First-In-First-Out (FIFO), or other patterns. The prediction accuracy decreases as a case passes through such segments indicating that RTM is uncertain about the underlying process behavior in such segments. We call these process segments uncertain segments. Therefore, recognizing all uncertain segments and translating their various inter-case patterns of process execution into features for training RTMs increases prediction quality.

In this paper, we present a three-step approach for developing inter-case dynamics aware RTMs: (1) Identifying process segments that cause high prediction errors due to inter-case dynamics, i.e., uncertain segments. (2) Discovering insights about the underlying patterns, e.g., *batching*, that leads to inter-case dependencies within the detected segments. (3) Transforming derived insights into features and incorporating them in RTMs to improve the quality of predictions. For instance, the waiting time for the batching in a segment is transformed into a feature and introduced into the RTM. We evaluate the prediction errors of RTMs without incorporating inter-case dependencies, such as batching behavior in a process segment, as shown in Fig. 1, and identify uncertain segments that involve inter-case dynamics. We continue by extracting the features associated with the observed patterns in the uncertain segments.

We introduce preliminaries and the related work in Sect. 2. In Sect. 3, we present our main approach. We evaluate the approach in Sect. 4 using real event logs, and Sect. 5 concludes this work.

# **2 Preliminaries and Related Work**

In this section, we introduce the necessary concepts and related work required to understand the approach presented in this paper.

#### **2.1 Related Work**

RTM approaches can be classified into three broad categories [17]. *Process aware approaches* make predictions using explicit process model representations such as transition system [1]. *Process agnostic approaches* typically use machine learning (ML) methods [14] to make predictions. Recent process agnostic approaches predominantly make use of sophisticated neura!l network architectures like LSTM [16] and explainable AI methods [5] to develop RTMs. *Hybrid approaches* like [11] combine capabilities of both categories by exploiting transition systems that are annotated using a machine learning algorithm. However, most approaches across all three categories only consider the intra-case perspective for predictions.

RTM approaches based on queuing models [15] and supervised learning [14] utilized the inter-case dimension in predictions. They create features on the basis of queuing theory like case priority and open cases of similar type. However, these approaches assume FIFO queuing behavior throughout the entire process. Two recent PPM approaches [3,8] use performance spectra [2] to learn inter-case dynamics present in the process without any prior assumption. Denisov et al. [3] presented a novel approach to predict the aggregated performance of nonisolated cases that utilize performance-related features. Klijn et al. [8] presented a novel RTM approach that is aware of *batching-at-end* dynamics. In this paper, we extend the process agnostic RTM approach presented in [8] by considering inter-case dynamics caused by *non-batching*, *batching-at-start* patterns too. We use and improve the fine-grained error analysis technique proposed in [8] to identify inter-case dynamics by limiting manual intervention.

#### **2.2 RTM Background**

RTM approaches predict the remaining time to completion of an ongoing process instance, i.e., *case*, based on process execution data of completed cases. Process execution of a completed case is recorded as a non-empty sequence of events (e), i.e., σ = e1, .., e*n* or *trace*. An event log L is a set of completed traces. Let A, T , E be the universe of activities (event classifiers), timestamps and events. Each event e∈ E consists of mandatory and additional attributes. Let AN be the set of attribute names. For an∈AN, we define #*an*(e) as the value of attribute an for event e. An event e has mandatory attributes timestamp #*t*(e)∈T at which e occurs and activity #*act*(e)∈A that occurs during e.

We first need to understand the general steps to develop a RTM described in [17]. In the *offline* or training phase, the first step is to prepare the input data, i.e., event log. Since a RTM makes prediction for incomplete traces, it trains on *prefixes* extracted from traces in L. A prefix is extracted by taking the first k∈N events from a completed trace (σ = e1, .., e*n*) using function hd*k*(σ) = e1, .., e*k*, k ≤ n. The resulting prefixes are collectively known as a *prefix log* L∗ of L. Therefore, data preparation includes cleaning the data, creating a prefix log and feature engineering. Features like *weekday* or *sojourn time* are extracted from event data and categorical features are encoded.

A RTM can be instantiated based on three main parameters, methods for grouping similar prefixes into buckets, prefix encoding methods, and used prediction techniques. For instance, RTM = (p, a, x) represents that the model's prefix bucketing method is based on similar prefix lengths (p), the encoding method is aggregating data of all prefix events (a), and ML algorithm is XGBoost (x). After training, the models are tuned using techniques like hyperparameter optimization. Finally, the optimal model's prediction accuracy is evaluated using aggregated metrics, e.g., Mean Absolute Error (MAE).

#### **2.3 Performance Spectrum with Error Progression**

To identify process segments subject to high prediction errors due to intercase dynamics, Klijn et al. [8] introduced a visual analysis technique, *Performance Spectrum with Error Progression (PSwEP)*. It uses the performance spectrum (PS) [2], which maps the performance of each case passing through a segment over time. A process segment (a, b)∈A × A can be defined as any two successive steps in the process, e.g., a step from activity a to activity b. For traces of form -..., e*i*, e*i*+1, ..., where #*act*(e*i*) = a, #*t*(e*i*) = t*a*, #*act*(e*i*+1) = b, and #*t*(e*i*+1) = t*b*, we observe an occurrence of a segment (a, b) from time t*a* to t*b*. Each occurrence of segment (a, b) representing a case is plotted in a PS as a line from (t*a*, a) to (t*b*, b). In PSwEP, segment occurrences within a PS are classified based on the error progression of the case while passing through the segment. Let P be the set of predictions made on test data using RTM. Each prediction pr*k*∈P corresponds to a prediction made for prefix hd*k*(σ) = e1, .., e*k* at point of prediction #*act*(e*k*) = a*k* and t*prk* = #*t*(e*k*), i.e., the time moment of prediction.

y*prk* and y*prk* denote the actual and predicted outcomes of pr*k*. To measure the error progression of segment occurrence (a*k*, a*k*+1) linked to σ, the prediction errors at a*k* and a*k*+1 are compared. The difference in relative absolute errors DRAE(rae*k*, rae*k*+1) = rae*k* − rae*k*+1 with rae*k*=|y*prk* − y*prk* |/y*prk* is measured. If the prediction error

**Fig. 2.** PswEP for *(Add Penalty (AP), Send for Credit Collection (SC))* in RF: error decrease (red), error increase (blue).(Color figure online)

decreases for a segment occurrence, i.e., DRAE > 0 this plotted line is colored

red in the PSwEP. If the prediction error increases, i.e., DRAE < 0 the line is colored blue. Figure 2 shows PSwEP of segment *(Apply Penalty (AP), Send for Credit Collection (SC))* in the RF event log.

### **3 Approach**

In this section, we will discuss the main approach proposed to develop an intercase-dynamics-aware RTM. In Sect. 3.1, we discuss the proposed techniques to automatically identify uncertain segments. In Sect. 3.2, we discuss the process of identifying and deriving insights about inter-case dynamics. Finally, in Sect. 3.3, we propose ways to create inter-case features by utilizing derived insights.

#### **3.1 Detecting Uncertain Segments**

**Measuring Uncertainty of a Process Segment.** To identify uncertain segments, we need to measure the uncertainty of each process segment. To do so, we first measure the DRAE (Sect. 2.3) of individual segment occurrences linked to predictions made using RTM on test data. Table 1 shows an example of how individual predictions are aligned with segment occurrences and the error progression of each occurrence is classified. A *decrease* in error, i.e., DRAE > 0 for a case passing through segment (a, b) implies that after the occurrence of activity b the remaining time prediction improves. This decrease could indicate some uncertainty between activity a and b, which gets resolved after activity b completes. An *increase* in error implies that after the occurrence of activity b, the prediction model becomes more unsure about how the partial trace will proceed. If prediction error remains the same, i.e., DRAE = 0, there is no clear indication of uncertainty within the process segment. We can either ignore such rare cases or include them as error *decrease*, where we consider the latter.

Based on above insights, we use three aggregated metrics to quantify uncertainty of segments. For each segment (S) linked to P, we measure (1) *observations* or total occurrences linked to S in P, (2) *decrease cases* or total occurrences linked to S with DRAE ≥ 0, and (3) *increase cases* or total occurrences linked to S with DRAE < 0. Table 2 is the result of applying the above aggregations to occurrences of segments found in Table 1.

**Table 1.** Error progression for the occurrence of segments linked to predictions.

**Table 2.** Measuring uncertainty of each segment by aggregating its occurrences to calculate *observations*, *decrease cases*, and *increase cases*.

**Selecting the Most Uncertain Segments.** We define a mapping function u*S* : N × R −→ [0, 1] to select a subset of process segments for which inter-case features could be created (Eq. 1). The inputs are the number of observations (o) and the ratio r = d/max(1, i) of decrease cases (d) to increase cases (i) for segment S (as shown in Table 2). Output 1 indicates the segment is highly uncertain. Note that ideal candidates for uncertain segments are those where decrease cases are almost the same or more than increase cases, i.e., their ratio should be greater than some threshold t*r*. The threshold for the number of observations (t*obs*) indicates the occurrences of the segments. These thresholds can be set for each process individually.

$$u\_S(o, r) = \begin{cases} 1 & \text{if } o \ge t\_{obs} \text{ and } round(r) \ge t\_r\\ 0 & \text{otherwise} \end{cases} \tag{1}$$

Let SG be the set of all segments in a process and SG*start* be the set of starting segments. Therefore, we apply u*S* to S∈SG \ SG*start* based on some t*r* and t*obs* and select set of segments U for which u*S*(o, r) = 1. Removing starting activities in traces is due to the fact that the RTM has too little information, and the prediction error is likely to decrease when the second activity occurs. We use the RF event log [9] as the running example. First, predictions are made on the last 20% (temporally split) of the event log using a RTM, here RTM = (p, a, x). Then, these predictions are used to measure the uncertainty of each process segment and u*S* is applied to all non-starting segments. We set t*r* = 1 and t*obs* > μ, e.g., t*obs* = 2 ∗ std where μ, std are the mean and standard deviation of segment occurrences. The selected uncertain segments are *(Send Fine (SF), Insert Fine Notification (IF)), (Insert Fine Notification (IF), Add Penalty (AP))* and *(Add Penalty (AP), Send for Credit Collection (SC))*. The details of selecting the most uncertain segments presented here1.

#### **3.2 Identifying Inter-case Dynamics in Uncertain Segments**

In order to diagnose causes for uncertainty within segments, first, we visualize the performance of cases within the process segment using PSwEP (Sect. 2.3). After that, the observed patterns in the performance spectrum are compared to a taxonomy [2] to identify underlying process behavior that causes inter-case patterns within the process segment. We explain the process of deriving insights for the uncertain segments identified in the running example.

In the shown PSwEP of (SF, IF) in Fig. 3 (left), two patterns, *batchingat-start* and *non-batching* FIFO behavior are identified. These are elementary patterns related to the order of case arrival. We notice uncertainty (as shown by the red lines) for non-batched cases. Therefore, RTM is currently not aware that non-batched cases are processed much faster than batch ones. Batched cases within the segment (Fig. 3) are also classified using red. The uncertainty concerning these cases is caused by the prediction model's lack of awareness

1 https://www.pads.rwth-aachen.de/go/id/qcekn/lidx/1.

about *batching-at-start* dynamics. The order of lines in PSwEP of (AP, SC) presented before in Fig. 2 clearly shows that the inter-case pattern is caused by *batching-at-end*. The prediction model is currently unaware of this inter-case dynamic within the process segment. In PSwEP of (IF, AP) in Fig. 3 (right), we observe a FIFO with a constant time pattern in the order of case arrival. The performance of a case is strongly correlated to the previous case that passed through the segment. We also know that there are two possible activities, *Add Penalty (AP)* or *Insert Date Appeal to Prefecture (ID)*, that can occur after *Insert Fine Notification (IF)* and the time that cases wait within the segments is significantly different. Therefore, incorrectly assuming the path of a case arrives at IF impacts the remaining time prediction. We are able to predict the path by observing the recent performance of cases in (IF, AP) and (IF, ID) w.r.t. inter-case dependencies. Lastly, across three segments, we observe changing the density of lines indicating varying workloads.

Based on the above derived insights, we define the abbreviated inter-case pattern(s) identified for segments (SF, IF),(IF, AP) and (AP, SC) as R1 = non − batching, batch(s), R2 = non − batching and R3 = batch(e) respectively.

**Fig. 3.** PSwEP for segments *(Send Fine (SF), Insert Fine Notification (IF))* (left), and *(Insert Fine Notification (IF), Add Penalty (AP))* (right) in the RF event log.

**Table 3.** The created inter-case features for segment predictions (C = {*CS, CS*1 *, CS*2 *, CS*3 }) and waiting time (*w*) within uncertain segments for the RF event log.

#### **3.3 Inter-case Feature Creation**

As the running example shows, ignoring inter-case dynamics results in high prediction errors for prefixes expected to pass through segment S∈U. Therefore, we need to provide the RTM information about a prefix being subject to intercase pattern R detected in uncertain segment S prior to the occurrence of the segment. We use these insights to develop inter-case features.

Consider the running example with three uncertain segments S1, S2, and S3 with inter-case pattern(s) R1, R2 and R3, respectively, we define the following inter-case features: (1) C*S*∈{0, 1}, to indicate if a prefix passes through an uncertain segment S∈U, (2) C*S*1 ∈{0, 1}, to indicate that the prefix passes through S1 with inter-case pattern(s) R1, (3) C*S*2 ∈{0, 1}, to indicate that prefix passes through S2 with inter-case pattern(s) R2, (4) C*S*3 ∈{0, 1}, to indicate that prefix passes through S3 with

**Fig. 4.** The overview of feature creation process for RF event log with uncertain segments *S*1, *S*2 and *S*3.

inter-case pattern(s) R3, and (5) w, to indicate the waiting time of the prefix in S∈U, as a result of inter-case pattern(s) R. As a result of the feature creation step for the running example, Table 3 is generated showing inter-case features. These features are used to train an inter-case-dynamics-aware RTM. Feature y is the target feature, i.e., remaining time to completion.

Creating inter-case features for an ongoing case at run-time requires its own prediction models. We need a model (NS) to predict inter-case features related to segment prediction and waiting time prediction model (TM*S,R*) for each uncertain segment S∈U with inter-case pattern(s) R. Figure 4 gives an overview of the steps involved in creating the models (offline) and utilization of these models to create inter-case features (at run-time). This process is the extended version of the presented feature-creation in [8].

#### **3.4 Predicting the Next Segment**

Classifier NS should determine if a prefix passes through segment S∈U at the point of prediction. To build NS, we build a classifier for the next activity prediction using [18] and modify the outcome to predict the value of segment prediction inter-case features. Let hd*k*(σ) be the input prefix with last activity a for NS. If the next activity predicted is b, we say that the prefix passes through segment (a, b) at the point of prediction. If (a, b)∈U, then C*S* = 1, else we set it to 0. If C*S* = 1, we set the value of the boolean variable representing the prefix passing through segment (a, b) as 1. Therefore, if predicted (a, b) = S1, then C*S*1 = 1, C*S*2 = 0, and C*S*3 = 0. The collective set of predicted features using NS is called C.

#### **3.5 Predicting Waiting Time**

In this section, we present general steps to create a waiting time prediction model (TM*S,R*) that predicts how long a case stays in a segment S with inter-case patterns R. Consider a case c1 arriving at segment S = (a, b) at time t*a* (Fig. 5). Because of intercase dynamics, the waiting time w of c1 will depend on the performance of other cases in relevant segments in some recent time interval, i.e., historic spectrum (S*h*) [3] and relevant individual properties (intra-case features). The intra-case feature of c1 and performance seen within S*h* can be encoded

**Fig. 5.** Illustration of a single instance for *TMS,R* to learn waiting time for case *c*1 using performance-related features extracted from *Sh* and relevant individual properties of *c*1.

as feature vector X1..X*n* using insights gained about R within S. This allows us to formulate the waiting time prediction problem as a supervised learning problem: w = f(X1..X*n*) +ε, where function f predicts w from X1..X*n*. To learn f, we create training samples using the sliding window method and apply a ML method like LightGBM [6] that tries to minimize prediction error ε. Table 4 shows sample data used to train a TM*S,R* for *(IF, AP)*.

**Waiting Time Prediction for Non-batching Dynamics.** In Sect. 3.1, we learned that w of a case in (IF, AP) is influenced by R = non − batching and varying workload in segments (IF, AP) and (IF, AD). To derive workload related context, we define h in S*h* as the period between arrival of c1

**Table 4.** Sample data for training waiting time prediction model (*TMS,R*) for uncertain segment (*IF, AP*) with pattern *R* = *non*−*batching*.

and the last case before it and derive: (1) *starting cases* or the number of cases that started (arrived at the segment) in period h, (2) *ending cases* or the number of cases that completed (exited the segment) in period h and (3) *pending cases* or the number of cases that have started within period h and will complete in the future. Since, performance of a case in (IF, AP) strongly depends on the previous case, we also extract last waiting time (w*l*), e.g., Table 4.

**Waiting Time Prediction for Batching-at-Start Dynamics.** w of a case c1 arriving at *(SF, IF)* will depend on R = batch(s), non−batching and varying workload within the segment. Therefore, S*h* contains only segment *(SF, IF)*. To learn performance related to R = non − batching and the workload, we include features presented in Sect. 3.5. To include features related to R = batch(s), we extract features related to the previous batch [7] with batching moment BM*l*: (1) least (w*min*) and longest waiting time (w*max*) in previous batch, (2) previous *batch size* and *batch size percentile*, (3) mean and standard deviation of IBCT or *inter batch case completion time*, which is the time difference between the completion times of two successive cases in the batch and (4) *batch type*, which distinguishes batches with less than 2 observations that behave like simultaneous batches, and (5) CIA or *case inter-arrival time* which the time between arrival of c1 and the case before it. We also include relevant intra-case features *resource, expense, points* and *weekday, month, hour* of previous batch. *Duration* or the waiting time of the case in the previous segment is also included to distinguish batched and non-batched cases. However, learning case-specific w is difficult because *batching-at-start* cases proceed randomly, i.e., not in the order they arrived at the batch. To avoid learning this random behavior, we propose building a TM*S,R* that predicts the average of expected waiting times for all cases that arrive along with c1. Hence, the training data will be prepared by extracting the above-mentioned features and then aggregating (calculating mean) feature values for instances that correspond to cases arriving simultaneously in the segment.

**Waiting Time Prediction for Batching-at-End Dynamics.** *(AP,SC)* contains inter-case dynamics caused by R = batch(e) and varying workload. To consider the varying workload across the segment, we include the features presented in Sect. 3.5. To learn batching related performance, we extract features w*min*, w*max* and CIA described in previous section. Additionally, we include: (1) t*lb*: or the time elapsed since the occurrence of the last batch, (2): the mean and standard deviation of IBIA *(inter-case arrival rate)* which is the difference between the arrival times of two successive cases in the batch. We also include intra-case features *month* and *weekday*.

### **4 Evaluation**

#### **4.1 Experimental Setup**

We evaluate the proposed approach on two real-life event logs: the RF event log [9] and BPIC'20 event log [4]. We implemented inter-case feature creation and PSwEP in Python, which is publicly available2. To train and test RTMs, we use the benchmark implementation for RTM approaches3 [17]. First, we make predictions with RTM = (p, a, x) for both event logs to identify uncertain segments and their patterns. The uncertain segments identified from RF event log are *(SF, IF)*, *(IF, AP)* and *(AP, SC)* with inter-case pattern(s) R1 = non−batching, batch(s), R2 = non−batching and R3 = batch(e), respectively. The two identified uncertain segments from BPIC'20 event log are *(Declaration Final Approved by Administration (DF), Request Payment (RP))* and *(Request Payment (RP), Payment*

2 https://github.com/karshreya98/Inter case aware RTM.

3 https://github.com/verenich/time-prediction-benchmark.

*Handled (PH))*. The inter-case pattern(s) identified for segments *(DF, RP)* and *(RP, PH)* are R1 = non−batching, batch(s), and R2 = batch(e) respectively. To create inter-case features, we implement NS using [18] and follow steps described in Sect. 3.5 to create TM*S,R* models using LightGBM [6]. Predictions are made with different bucketing prefixes, encoding prefix events, and ML methods. We consider *prefix bucketing methods* to be grouping by prefix lengths (p), using a clustering algorithm (c) or grouping all prefixes in a single bucket (s). Common *prefix encoding methods* include data of only last prefix event (l) or aggregating data of all prefix events (a), and apply ML models, XGBoost (x) or random forest (r) to the input encoded feature vectors. The following input configurations are used: (1) I(∅): event log with no inter-case features, (2) I(C, w): event log with inter-case features created using actual segment prediction C, and (3) I(C, w): event log with inter-case features created using segment prediction made using NS. We use 80% and 20% (by temporally splitting) of the event logs for training and testing the RTMs. To measure overall prediction accuracy, we measure the weighted average MAE [17] of all predictions P made on test data.

#### **4.2 Results**

Table 5 shows that using inter-case features leads to an increase in performance for all 8 combinations of bucketing prefixes, encoding prefix events, and ML methods in RTMs against baseline I(∅). For the RF event log, we see that prediction error decreases by a maxi**Table 6.** MAE (in days) for different configurations (*I*) with the similar lengths bucketing (*p*), aggregating events data for encoding prefix events (*a*), and XGBoost (*x*) as the ML method, *RTM* = (*p, a, x*). P*k* is the set of all predictions for prefixes of length *k*.

mum of 14.26% and a minimum of 4.27% for methods (p, l, x) and (c, a, x), respectively, with I(C, w). For the BPIC'20 event log, we observe a maximum decrease of 5.12% and a minimum decrease of 1.55% in weighted average MAE for methods (c, a, r) and (c, a, x), respectively. Since BPIC'20 is a smaller event log with fewer cases subject to the identified inter-case patterns, the overall reduction in prediction error is smaller. The most accurate predictions for the RF event log obtained using I(C, w) with (c, l, x), has a MAE 0.6 days less than the benchmark result [17]. However, our approach's privilege is that these predictions can be interpreted more easily because of the inter-case features.

In our approach, inter-case features are primarily included for prefixes passing through uncertain segments which occur at some step k of the process. Therefore, we look at MAE of predictions made for all prefixes of relevant length k, i.e., P*k* ⊆ P. Segments (SF, IF), (IF, AP) and (AP, SC) of the RF event log occur predominantly at step k = 2, k = 3 and k = 4 of the process respectively. Segments (DF, RP) and (RP, PH) of the BPIC'20 log occur predominantly at steps k = 3 and k = 4, 5 respectively. Table 6 shows us the results for predictions made using RTM = (p, a, x). For the RF event log, the prediction error decreases by 39%, 12% and 15% for P2, P3 and P4,

**Fig. 6.** Comparing prediction results for RF

**Fig. 7.** Comparing prediction results for BPIC'20

respectively using I(C, w) over baseline. For BPIC'20, error decreases up to 15% and 9% for P4 and P5, respectively, when using I(C, w). However, the MAE of P3 is slightly higher for configuration I(C, w) compared to I(∅) . This is because of incorrect segment predictions for *(DF, RP)* made by NS which is proven by the results of I(C, w). Figures 6 and 7 compare the *batching-at-end* aware predictions made using inter-case features created in our approach that uses LightGBM [6]) and previous approach [8] that uses exponential smoothing (ES). We measure the increase/decrease in performance of P4 made using different combination of RTMs over their respective baselines. We compare only predictions at k = 4 for both logs where uncertain segments with *batching-at-end* dynamics occur. Figure 6 shows that, our approach performs better than previous approach in 5 of the 8 input configuration (I) for batched cases in RF event log. Figure 7 shows that for the batched cases in BPIC'20 log, our method performs better for all the configurations.

#### **5 Conclusion**

We presented an approach to systematically discover a subset of uncertain process segments with inter-case dynamics that cause high prediction errors. Contrary to previous approaches, our designed function for detecting the subset of uncertain segments, limited the manual intervention to the identification of inter-case patterns within these segments. Using visual analysis, we identified and gained insights about inter-case pattern(s) within uncertain segments. In particular, we gained insights into non-batching (FIFO and unordered), *batching-atstart*, and *batching-at-end* inter-case patterns. Subsequently, we included these insights in remaining time predictions by transforming them into the inter-case features. For instance, there is a maximum increase in overall prediction performance by 14.2% for RF event-log. Since there is no standardized process to create a ML model for inter-case feature creation, our proposed approach is also sensitive to user interpretation. Yet, it provides more interpretability to RTMs. Note that despite an overall decrease in prediction error, some prefixes were heavily over-predicted or under-predicted. Therefore, the next step is to improve the prediction models and leverage routing probability derived from stochastic process models. It improves the inter-case feature creation for segment prediction. Another possible path is to make RTM aware of non-case-related aspects, e.g., resources dependencies.

# **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Event Log Sampling for Predictive Monitoring**

Mohammadreza Fani Sani1(B) , Mozhgan Vazifehdoostirani2, Gyunam Park1, Marco Pegoraro1, Sebastiaan J. van Zelst1,3, and Wil M. P. van der Aalst1,3

1 Process and Data Science Chair, RWTH Aachen University, Aachen, Germany *{*fanisani,gnpark,pegoraro,s.j.v.zelst<EMAIL_ADDRESS>2 Industrial Engineering and Innovation Science, Eindhoven University of Technology,

Eindhoven, The Netherlands

<EMAIL_ADDRESS>
3 Fraunhofer FIT, Birlinghoven Castle, Sankt Augustin, Germany

**Abstract.** Predictive process monitoring is a subfield of process mining that aims to estimate case or event features for running process instances. Such predictions are of significant interest to the process stakeholders. However, state-of-the-art methods for predictive monitoring require the training of complex machine learning models, which is often inefficient. This paper proposes an instance selection procedure that allows sampling training process instances for prediction models. We show that our sampling method allows for a significant increase of training speed for next activity prediction methods while maintaining reliable levels of prediction accuracy.

**Keywords:** Process Mining · Predictive Monitoring · Sampling · Machine Learning · Deep Learning · Instance Selection

#### **1 Introduction**

As the environment surrounding business processes becomes more dynamic and competitive, it becomes imperative to predict process behaviors and take proactive actions [1]. Predictive business process monitoring aims at predicting the behavior of business processes, to mitigate the risk resulting from undesired behaviors in the process. For instance, by predicting the next activities in the process, one can foresee the undesired execution of activities, thus preventing possible risks resulting from it [12]. Moreover, by predicting an expected high service time for an activity, one may bypass or add more resources for the activity [15]. Recent breakthroughs in machine learning have enabled the development of effective techniques for predictive business process monitoring. Specifically, techniques based on deep neural networks, e.g., Long-Short Term Memory (LSTM) networks, have shown high performance in different tasks [8]. Additionally, the emergence of ensemble learning methods leads to improvement in accuracy in different areas [4]. Particularly, for predictive process monitoring, eXtreme Gradient Boosting (XGBoost) [6] has shown promising results, often outperforming other ensemble methods such as Random Forest or using a single regression tree [25,28].

Indeed, machine learning algorithms suffer from the expensive computational costs in their training process [34]. In particular, machine learning algorithms based on neural networks and ensemble learning might require tuning their hyperparameters to be able to provide acceptable accuracy. Such long training time limits the application of the techniques considering the limitations in time and hardware [21]. This is particularly relevant for predictive business process monitoring techniques. Business analysts need to test the efficiency and reliability of their conclusions via repeated training of different prediction models with different parameters [15]. Moreover, the dynamic nature of business processes requires new models adapting to new situations in short intervals.

Instance selection aims at reducing original datasets to a manageable volume to perform machine learning tasks, while the quality of the results (e.g., accuracy) is maintained as if the original dataset was used [11]. Instance selection techniques are categorized into two classes based on the way they select instances. First, some techniques select the instances at the boundaries of classes. For instance, Decremental Reduction Optimization Procedure (DROP) [32] selects instances using *k*-Nearest Neighbors by incrementally discarding an instance if its neighbors are correctly classified without the instance. The other techniques preserve the instances residing inside classes, e.g., Edited Nearest Neighbor (ENN) [33] preserves instances by repeatedly discarding an instance if it does not belong to the class of the majority of its neighbors.

Such techniques assume independence among instances [32]. However, in predictive business process monitoring training, instances may be highly correlated [2], impeding the application of techniques for instance selection. Such instances are computed from event data that are recorded by the information system supporting business processes [14]. The event data are correlated by the notion of *case*, e.g., patients in a hospital or products in a factory. In this regard, we need new techniques for instance selection applicable to event data.

In this work, we suggest an instance selection approach for predicting the next activity, one of the main applications of predictive business process monitoring. By considering the characteristics of the event data, the proposed approach samples event data such that the training speed is improved while the accuracy of the resulting prediction model is maintained. We have evaluated the proposed methods using two real-life datasets and state-of-the-art techniques for predictive business process monitoring, including LSTM [13] and XGBoost [6].

The remainder is organized as follows. We discuss the related work in Sect. 2. Next, we present the preliminaries in Sect. 3 and proposed methods in Sect. 4. Afterward, Sect. 5 evaluates the proposed methods using real-life event data and Sect. 6 provides discussions. Finally, Sect. 7 concludes the paper.

#### **2 Related Work**

Predictive process monitoring is an exceedingly active field of research. At its core, the fundamental component of predictive monitoring is the abstraction technique it uses to obtain a fixed-length representation of the process component subject to the prediction (often, but not always, process traces). In the earlier approaches, the need for such abstraction was overcome through model-aware techniques, employing process models and replay techniques on partial traces to abstract a flat representation of event sequences. Such process models are mostly automatically discovered from a set of available complete traces, and require perfect fitness on training instances (and, seldomly, also on unseen test instances). For instance, van der Aalst et al. [1] proposed a time prediction framework based on replaying partial traces on a transition system, effectively clustering training instances by control-flow information. This framework has later been the basis for a prediction method by Polato et al. [20], where the transition system is annotated with an ensemble of SVR and Na¨ıve Bayes classifiers, to perform a more accurate time estimation. A related approach, albeit more linked to the simulation domain and based on a Monte Carlo method, is the one proposed by Rogge-Solti and Weske [24], which maps partial process instances in an enriched Petri net.

Recently, predictive process monitoring started to use a plethora of machine learning approaches, achieving varying degrees of success. For instance, Teinemaa et al. [27] provided a framework to combine text mining methods with Random Forest and Logistic Regression. Senderovich et al. [25] studied the effect of using intra-case and intercase features in predictive process monitoring and showed a promising result for XGBoost compared to other ensemble and linear methods. A comprehensive benchmark on using classical machine learning approaches for outcome-oriented predictive process monitoring tasks [28] has shown that the XGBoost is the best-performing classifier among different machine learning approaches such as SVM, Decision Tree, Random Forest, and logistic regression.

More recent methods are model-unaware and perform based on a single and more complex machine learning model instead of an ensemble. The LSTM network model has proven to be particularly effective for predictive monitoring [8,26], since the recurrent architecture can natively support sequences of data of arbitrary length. It allows performing trace prediction while employing a fixed-length event abstraction, which can be based on control-flow alone [8,26], data-aware [16], time-aware [17], text-aware [19], or model-aware [18].

A concept similar to the idea proposed in this paper, and of current interest in the field of machine learning, is *dataset distillation*: utilizing a dataset to obtain a smaller set of training instances that contain the same information (with respect to training a machine learning model) [31]. While this is not considered sampling, since some instances of the distilled dataset are created ex-novo, it is an approach very similar to the one we illustrate in our paper. Moreover, recently some instance selection algorithms have been proposed to help process mining algorithms. For example, [9,10] proposed to use instance selection techniques to improve the performance of process discovery and conformance checking procedures.

In this paper, we examine the underexplored topic of event data sampling and selection for predictive process monitoring, with the objective of assessing if and to which extent prediction quality can be retained when we utilize subsets of the training data.

#### **3 Preliminaries**

In this section, some process mining concepts such as event log and sampling are discussed. In process mining, we use events to provide insights into the execution of business processes. Each *event* is related to specific activities of the underlying process. Furthermore, we refer to a collection of events related to a specific process instance as a *case*. Both cases and events may have different attributes. An event log that is a collection of events and cases is defined as follows.

**Definition 1 (Event Log).** *Let* E *be the universe of events,* C *be the universe of cases,* AT *be the universe of attributes, and* U *be the universe of attribute values. Moreover, let* C⊆C *be a non-empty set of cases, let* E⊆E *be a non-empty set of events, and let* AT⊆AT *be a set of attributes. We define* (C, E, πC , πE) *as an event log, where* πC :C×AT →U *and* πE:E×AT →U *. Any event in the event log has a case, therefore,* e∈E(πE(e, case) ∈ C) *and* - (πE(e, case)) = C*.*

e∈E *Furthermore, let* A⊆U *be the universe of activities and let* V⊆A∗ *be the universe of sequences of activities. For any* e∈E*, function* πE(e, activity)∈A*, which means that any event in the event log has an activity. Moreover, for any* c∈C *function* πC (c, variant)∈A∗\{} *that means any case in the event log has a variant.*

Therefore, there are some mandatory attributes that are *case* and *activity* for events and *variants* for cases. In some process mining applications, e.g., process discovery and conformance checking, just variant information is considered. Therefore, event logs are considered as a multiset of sequences of activities. In the following, a simple event log is defined.

**Definition 2 (Simple event log).** *Let* A *be the universe of activities and let the universe of multisets over a set* X *be denoted by* B(X)*. A simple event log is* L∈B(A∗)*. Moreover, let* EL *be the universe of event logs and* EL = (C, E, πC , πE)∈EL *be an event log. We define function* sl:EL→B({πE(e, activity)|e∈E}∗) *returns the simple event log of an event log. The set of unique variants in the event log is denoted by* sl(EL)*.*

Therefore, sl returns the multiset of variants in the event logs. Note that the size of a simple event log equals the number of cases in the event logs, i.e., sl(EL) = |C|

In this paper, we use sampling techniques to reduce the size of event logs. An event log sampling method is defined as follows.

**Definition 3 (Event log sampling).** *Let* EL *be the universe of event logs and* A *be the universe of activities. Moreover, let* EL = (C, E, πC , πE)∈EL *be an event log, we define function* δ:EL→EL *that returns the sampled event log where if* (C , E , π C , π E) = δ(EL)*, then* C ⊆C*,* E ⊆E*,* π e⊆πE*,* π C ⊆πC *, and consequently,* sl(δ(EL))⊆sl(EL)*. We define that* δ *is a variant-preserving sampling if* sl(δ(EL)) = sl(EL)*.*

In other words, a sampling method is variant-preserving if and only if all the variants of the original event log are presented in the sampled event log.

To use machine learning methods for prediction, we usually need to transfer each case to one or more features. The feature is defined as follows.

**Definition 4 (Feature).** *Let* AT *be the universe of attributes,* U *be the universe of attribute values, and* C *be the universe of cases. Moreover, let* AT⊆AT *be a set of attributes. A feature is a relation between a sequence of attributes' values for* AT *and the target attribute value, i.e.,* f∈(U|AT| ×U)*. We define fe*:C×EL→B(U|AT| ×U) *is a function that receives a case and an event log, and returns a multiset of features.*

**Fig. 1.** A schematic view of the proposed sampling procedure

For the next activity prediction, i.e., our prediction goal, the target attribute value should be an activity. Moreover, a case in the event log may have different features. For example, suppose that we only consider the activities. For the case a, b, c, d, we may have (a, b), (a, b, c), and (a, b, c, d) as features. Furthermore, c∈C fe(c, EL) are the corresponding features of event log EL = (C, E, πC , πE) that could be given to different machine learning algorithms. For more details on how to extract features from event logs please refer to [23].

# **4 Proposed Sampling Methods**

In this section, we propose an event log preprocessing procedure that helps prediction algorithms to perform faster while maintaining reasonable accuracy. The schematic view of the proposed sampling approach is presented in Fig. 1. We first need to traverse the event log and find the variants and corresponding traces of each variant in the event log. Moreover, different distributions of data attributes in each variant will be computed. Afterward, using different sorting and instance selection strategies, we are able to select some of the cases and return the sample event log. In the following, each of these steps is explained in more detail.

	- *Unique selection*: In this approach, we select only one trace with the highest priority. In other words, suppose that L = sl(δ(EL)), ∀σ∈L-L (σ)=1. Therefore, using this approach we will have |sl(δ(EL))| = |sl(EL)|. It is expected that using this approach, the distribution of frequency of variants will be changed and consequently the resulted prediction model will be less accurate.
	- *Logarithmic distribution*: In this approach, we reduce the number of traces in each variant in a logarithmic way. If L = sl(EL) and L = sl(δ(EL)), ∀σ∈L-L (σ)=[Logk(L(σ))]. Using this approach, the infrequent variants will not have any trace in the sampled event log. By using a higher k, the size of the sampled event log is reduced more.
	- *Division*: This approach performs similar to the previous one, however, instead of using logarithmic scale, we apply the division operator. In this approach, ∀σ∈L-L (σ) = (σ) k . A higher k results in fewer cases in the sample event log. Note that using this approach all the variants have at least one trace in the sampled event log.

There is also a possibility to consider other selection methods. For example, we can select the traces completely randomly from the original event log.

By choosing different data attributes in Step 2 and different sorting algorithms in Step 3, we are able to lead the sampling of the method on *which* cases should be chosen. Moreover, by choosing the type of distribution in Step 4, we determine *how many* cases should be chosen. To compute how sampling method δ reduces the size of the given event log EL, we use the following equation:

$$R\_S = \frac{|sl(EL)|}{|sl(\delta(EL))|}\tag{1}$$

The higher RS value means, the sampling method reduces more the size of the training log. By choosing different distribution methods and different *k-values*, we are able to control the size of the sampled event log. It should be noted that the proposed method will apply just to the training event log. In other words, we do not sample event logs for development and test datasets.

#### **5 Evaluation**

In this section, we aim at designing some experiments to answer our research question, i.e., "Can we improve the computational performance of prediction methods by using the sampled event logs, while maintaining a similar accuracy?". It should be noted that the focus of the experiments is not on prediction model tuning to have higher accuracy. Conversely, we aim to analyze the effect of using sampled event logs (instead of the whole datasets) on the required time and the accuracy of prediction models. In the following, we first explain the event logs that are used in the experiments. Afterward, we provide some information about the implementation of sampling methods. Moreover, the experimental setting is discussed and, finally, we show the experimental results.

**Table 1.** Overview of the event logs that are used in the experiments. The accuracy and the required times (in seconds) of different prediction methods for these event logs are also presented.

#### **5.1 Event Logs**

To evaluate the proposed sampling procedure for prediction, we have used two event logs widely used in the literature. Some information about these event logs is presented in Table 1. In the *RTFM* event log, which corresponds to a road traffic management system, we have some high frequent variants and several infrequent variants. Moreover, the number of activities in this event log is high. Some of these activities are infrequent, which makes this event log imbalanced. In the *BPIC-2012-W* event log, relating to a process of an insurance company, the average of variant frequencies is lower.

#### **5.2 Implementation**

We have developed the sampling methods as a plug-in in the ProM framework [30], accessible via https://svn.win.tue.nl/repos/prom/Packages/LogFiltering. This plug-in takes an event log and returns k different train and test event logs in the CSV format. Moreover, to train the prediction method, we have used XGBoost [6] and LSTM [13] methods as they are widely used in the literature and outperformed their counterparts. Our LSTM network consisted of an input layer, two LSTM layers with *dropout* rates of 10%, and a dense output layer with the *SoftMax* activation function. We used "categorical cross-entropy" to calculate the loss and adopted *ADAM* as an optimizer. We used *gbtree* with a max depth of 6 as a booster in our XGBoost model. Uniform distribution is used as the sampling method inside our XGBoost model. To avoid overfitting in both models, the training set is further divided into 90% training set and 10% validation set to stop training once the model performance on the validation set stops improving. We used the same setting of both models for original event logs and sampled event logs. To access our implementations of these methods and the feature generation please refer to https://github.com/gyunamister/pm-prediction/. For details of the feature generation and feature encoding steps, please refer to [18].

#### **5.3 Evaluation Setting**

To sample the event logs, we use three distributions that are log *distribution*, *division*, and *unique variants*. For the log distribution method, we have used 2, 3, and 10 (i.e., log2, log3, and log10). For the division method, we have used 2, 5, and 10 (i.e., d2, d5, and d10). For each event log and for each sampling method, we have used a 5-fold cross-validation. Moreover, as the results of the experiments are non-deterministic, all the experiments have been repeated 5 times and the average values are represented.

Note that, for both training and evaluation phases, we have used the same settings for extracting features and training prediction models. We used one-hot encoding to encode the sequence of activities for both LSTM and XGBoost models. We ran the experiment on a server with Intel Xeon CPU E7-4850 2.30 GHz, and 512 GB of RAM. In all the steps, one CPU thread has been used. We employed the *Weighted Accuracy* metric [22] to compute how a prediction method performs for test data. To compare the accuracy of the prediction methods, we use the *relative accuracy* that is defined as follows.

$$R\_{Acc} = \frac{\text{Accuracy using the sampled training log}}{\text{Accuracy using the whole training log}} \tag{2}$$

If RAcc is close to 1, it means that using the sampling event logs, the prediction methods behave almost similar to the case that the whole data is used for the training. Moreover, values higher than 1 indicate the accuracy of prediction methods has improved.

To compute the improvement in the performance of training time, we will use the following equations.

$$R\_t = \frac{\text{Training time using whole data}}{\text{Training time using the sampled data}}\tag{3}$$

$$R\_{FE} = \frac{\text{Feature extraction time using whole data}}{\text{Feature extraction time using the sampled data}} \tag{4}$$

For both equations, the resulting values indicate how many times the sampled log is faster than using all data.

#### **5.4 Experimental Results**

Table 2 presents the reduction rate and the improvement in the feature extraction phase using different sampling methods. As it is expected, the highest reduction rate is for log10 (as it removes infrequent variants and keeps few traces of frequent variants), and respectively it has the biggest improvement in RF E. Moreover, the lowest reduction is for *d2*, especially if there are lots of unique variants in the event log (i.e., for the *RTFM* event log). We expected smaller event logs to require less feature extraction time. However, results indicate that the relationship is not linear, and by having more reduction in the size of the sampled event log there will be a much higher reduction in the feature extraction time.

In Table 3 and Table 4, the results of improvement in Rt and RAcc are shown for LSTM and XG prediction methods. As expected, by using fewer cases in the training, the performance of training time improvement will be higher. Comparing the results in these two tables and the results in Table 2, it is interesting to see that in some cases, even by having a high reduction rate, the accuracy of the trained prediction model is close to the case in which whole training log is used. For example, using d10 for the *RTFM* event log, we will have high accuracy for both prediction methods. In other words, we are able to improve the performance of the prediction procedure while the accuracy is still reasonable.

When using the LSTM prediction method for the RTFM event log, there are some cases where we have accuracy improvement. For example, using d3, there is a 0.4% improvement in the accuracy of the trained model. It is mainly because of the existence of high frequent variants. These variants lead to having unbiased training logs and consequently, the accuracy of the trained model will be lower for infrequent behaviors.

**Table 2.** The reduction in the size of training logs (i.e., *RS*) and the improvement in the performance of feature extraction part (i.e., *RF E*) using different sampling methods.

**Table 3.** The accuracy and the improvement in the performance of prediction using different sampling methods for LSTM.

**Table 4.** The accuracy and the improvement in the performance of prediction using different sampling methods for XGBoost.

# **6 Discussion**

The results indicate that we do not always have a typical trade-off between the accuracy of the trained model and the performance of the prediction procedure. In other words, there are some cases where the training process is much faster than the normal procedure, even though the trained model provides an almost similar accuracy. We did not provide the results for other metrics; however, there are similar patterns for weighted recall, precision, and f1-score. Thus, the proposed sampling methods can be used when we aim to apply hyperparameter optimization [3]. In this way, more settings can be analyzed in a limited time. Moreover, it is reasonable to use the proposed method when we aim to train an online prediction method or on naive hardware such as cell phones.

Another important outcome of the results is that for different event logs, we should use different sampling methods to achieve the highest performance. For example, for the *RTFM* event log—as there are some highly frequent variants—the division distribution may be more useful. In other words, independently of the used prediction method, if we change the distribution of variants (e.g., using unique distribution), it is expected that the accuracy will sharply decrease. However, for event logs with a more uniform distribution, we can use logarithmic and unique distributions to sample event logs. The results indicate that the effect of the chosen distribution (i.e., unique, division, and logarithmic) is more important than the used *k-value*. Therefore, it would be valuable to investigate more on the characteristics of the given event log and suitable sampling parameters for such distribution. For example, if most variants of a given event log are unique, the division and unique methods are not able to have remarkable RS and consequently, RF E and Rt will be close to 1.

Moreover, results have shown that by oversampling the event logs, although we will have a very big improvement in the performance of the prediction procedure, the accuracy of the trained model is significantly lower than the accuracy of the model that is trained by the whole event log. Therefore, we suggest gradually increasing (or decreasing) the size of the sampled event log in the hyper-parameter optimization scenarios.

By analysis of the results using common prediction methods, we have found that the infrequent activities can be ignored using some hyper-parameter settings. This is mainly because the event logs are unbalanced for these infrequent activities. Using the sampling methods that modify the distribution of the event logs such as the unique method can help the prediction methods to also consider these activities.

Finally, in real scenarios, the process can change because of different reasons [5]. This phenomenon is usually called *concept drift*. By considering the whole event log for training the prediction model, it is most probable that these changes are not considered in the prediction. Using the proposed sampling procedure, and giving higher priorities to newer traces, we are able to adapt to the changes faster, which may be critical for specific applications.

#### **7 Conclusion**

In this paper, we proposed to use the subset of event logs to train prediction models. We proposed different sampling methods for next activity prediction. These methods are implemented in the ProM framework. To evaluate the proposed methods, we have applied them on two real event logs and have used two state-of-the-art prediction methods: LSTM and XGBoost. The experimental results have shown that, using the proposed method, we are able to improve the performance of the next activity prediction procedure while retaining an acceptable accuracy (in some experiments, the accuracy increased). However, there is a relation between event logs characteristics and suitable parameters that can be used to sample these event logs. The proposed methods can be helpful in situations where we aim to train the model fastly or in hyper-parameter optimization scenarios. Moreover, in cases where the process can change over time, we are able to adapt to the modified process more quickly using sampling methods.

To continue this research, we aim to extend the experiments to study the relationship between the event log characteristics and the sampling parameters. Additionally, we plan to provide some sampling methods that help prediction methods to predict infrequent activities, which could be more critical in the process. Finally, it is interesting to investigate more on using sampling methods for other prediction method applications such as last activity and remaining time prediction.

**Acknowledgment.** The authors would like to thank the Alexander von Humboldt (AvH) Stiftung for funding this research.

# **References**

**Open Access** This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.

The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.

# **Active Anomaly Detection for Key Item Selection in Process Auditing**

Ruben Post1(B) , Iris Beerepoot1, Xixi Lu1, Stijn Kas1, Sebastiaan Wiewel1, Angelique Koopman2, and Hajo Reijers1

1 Information and Computer Sciences, Utrecht University, Utrecht, The Netherlands<EMAIL_ADDRESS>
2 Department of Accountancy, Tilburg University, Tilburg, The Netherlands

**Abstract.** Process mining allows auditors to retrieve crucial information about transactions by analysing the process data of a client. We propose an approach that supports the identification of unusual or unexpected transactions, also referred to as exceptions. These exceptions can be selected by auditors as "key items", meaning the auditors wants to look further into the underlying documentation of the transaction. The approach encodes the traces, assigns an anomaly score to each trace, and uses the domain knowledge of auditors to update the assigned anomaly scores through active anomaly detection. The approach is evaluated with three groups of auditors over three cycles. The results of the evaluation indicate that the approach has the potential to support the decisionmaking process of auditors. Although auditors still need to make a manual selection of key items, they are able to better substantiate this selection. As such, our research can be seen as a step forward with respect to the usage of anomaly detection and data analysis in process auditing.

**Keywords:** Process Mining *·* Domain Knowledge *·* Anomaly Detection *·* Auditing

# **1 Introduction**

In the past years, it has become clear that data captured by information systems are relevant for auditors [1,2]. Process mining allows auditors to elicit behaviour from process data in the form of event logs derived from information systems of their clients [1, p. 32]. An event log is a collection of cases, where a case is a sequence of events performed in the context of a single process [1, p. 128]. As an event log collects behaviour captured by the information systems involved, it can be considered as an unbiased perspective on the client's processes [3]. Take, for example, an event log that contains loan offers made by a bank. The bank receives a customer request for a loan, asks for additional information until it has sufficient information, and finally decides to grant the loan or not. Without process data, the auditor does not know the steps taken before the loan was granted (i.e. the behaviour), while this behaviour could be instrumental in the auditor's decision to further investigate a particular loan offer.

Choosing which loan offer, or any other transaction of the client, to investigate further is also referred to as key item selection. Key items are specific transactions that auditors want to look further into by, for example, requesting additional documentation on the transactions because they might have a higher likelihood of containing a material misstatement (i.e. transactions that violate accounting and auditing standards [4, p. 374]). Currently, key items are selected based on the size of the transactions (i.e. the transactions with the highest monetary value), professional judgement, or by drawing a sample [5, Ch. 6]. Without detailed information about transactions, unusual or unexpected aspects such as the number of times a transaction has been declined and resubmitted, the total number of activities performed in the transaction, or the throughput time of the transaction, are largely ignored while selecting key items.

Anomaly detection algorithms can be used to detect exceptions, which can then be selected as key items. However, both supervised and unsupervised approaches may be unsuitable for practice because they either require a large amount of labeled training data or lack explainability [6–11]. More specifically, selecting the key items based on the underlying process data still requires domain knowledge [11]. Hence, active engagement of domain experts (i.e. auditors) is needed to detect exceptions. This leads to the following research question: *How can key item selection be supported using active anomaly detection on process data?* The research question is answered by structuring the identification of exceptions in process data in a three-step approach. In doing so, we contribute to the research field of process mining and auditing. By embedding domain knowledge in the identification of exceptions, the approach shows that the involvement of domain experts can be beneficial for both the domain experts' insight into the process of the client and the results of the approach itself. Additionally, because the approach provides a more detailed account of the transactions, the selection is better substantiated.

### **2 Related Work**

#### **2.1 Anomaly Detection**

Anomaly detection approaches can be used to identify unusual or unexpected transactions in process data, also referred to as *exceptions*. Several anomaly detection approaches suitable for process data have been proposed [6–11]. Current approaches mostly use trained models to detect anomalies, like Ko et al. [10] and Pauwels et al. [9]. Using these approaches in practice is difficult because there is no labeled data available during audits, meaning these models cannot be trained. An alternative to training data could be a temporal holdout set where the data of the prior audit is used to train the model (i.e. the prior-year data is used to train the model to identify anomalies in the current-year data). However, if a temporal holdout set is used, concepts such as concept drift should be taken into account because the model might not know the difference between an anomaly and the introduction of a new process. An example of this is the recent COVID-19 pandemic, which coerced the digitisation of processes, introducing concept drift to the process data.

Other approaches such as those of Nolle et al. [8] and B¨ohmer et al. [7] use neural network-based autoencoders and Basic Likelihood Graphs to identify anomalies. This introduces complexity through the techniques they use, leading to both an increase in required processing power and unexplainability or incomprehensibility of the approach. This is problematic because it prohibits the domain expert to adequately substantiate their selection of key items.

In contrast to the other approaches, Schumann et al. [11] use low-complexity models that do not require training data to identify anomalies. Because they determine certain non-compliant patterns in the data beforehand and inject the data with these patterns, no training data is required. While the other approaches are evaluated through various performance metrics, only Schumann et al. [11] evaluate their technique with domain experts. The benefit of this type of evaluation is that is allows for domain experts to differentiate between real anomalies and cases that are considered compliant in practice. However, the rationale used by the domain experts is not explained, which brings the applicability and replicability of the approach in practice in question.

#### **2.2 Active Anomaly Detection**