Bottleneck prediction is an important sub-task of process mining that aims at optimizing the discovered process models by avoiding such congestions. This paper discusses an ongoing work on incorporating recurrent concept drift in bottleneck prediction when applied to a real-world scenario. In the field of process mining, we develop a method of predicting whether and which bottlenecks will likely appear based on data known before a case starts. We next introduce GRAEC, a carefully-designed weighting mechanism to deal with concept drifts. The weighting decays over time and is extendable to adapt to seasonality in data. The methods are then applied to a simulation, and an invoicing process in the field of installation services in real-world settings. The results show an improvement to prediction accuracy compared to retraining a model on the most recent data.
Concept drift expresses an occurrence of a shift in relations between input and output data over time. The challenge with concept drift is that it is dificult to asses, detect, and correct such evolutions. One method of solving concept drift is to retrain models periodically. This method poses two major disadvantages. First, this reduces the quantity of available data, which is a big issue when the number of data points per time unit is low, or when dealing with unbalanced datasets. The combination of these two causes over-fitting of the model on larger classes. Second, retraining a model with new data inherently discards former data, which could remove valuable information on seasonality.
This paper discusses a technique to cover both issues and applies it to reduce the duration of a process, by predicting if, and where, bottlenecks take place in the process. A simple example for a paper submission process is shown in Figure 1, where the bottlenecks are indicated for process instances at diferent points in time. Note the bottle activities for papers on Process Mining. The proposed solution uses multiple machine learning models trained over diferent intervals of previous data, and assigns weights to the predictions of each model based on the diference in time between the model First International Workshop on Data Science for Industry 4.0.
Copyright ©2019 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. and the test data, factoring in an exponential decay (giving priority to recent models) and a periodic function (giving priority to seasonally similar points in time). As such we develop a Gradual and Recurrent concept drift Adapting Ensemble Classifer, or GRAEC. The contributions of this paper are: • A mathematical way for assessing bottlenecks in business processes • A novel concept drift adaptation method, GRAEC • An extensive experimental evaluation using a simulation study and a real-world dataset, which proves the superiority of our method compared to existing solutions which also proves the correctness of our concept The rest of the paper is organised as follows. Section 2 discusses some related literature. Section 3 defines the problem that this paper aims to solve. Section 4 proposes a solution to adapting for concept drift with seasonality. Section 5 describes the experimental set-up for the simulation and the real-world dataset. Section 6 presents and discusses the results of the experiment. Section 7 concludes the paper and provides suggestions for future research. 2
Concept drift has been a topic in online data streams in recent
years. Concept drift is the phenomenon where relations between
input (features) and output (labels in the case of the experiments
in this paper) change over time, because the underlying models
and/or distributions change [
The challenges of seasonal concepts, or what is more known in
the literature as recurrent concepts, have been addressed recently in
[
In the field of prediction process bottlenecks, [
The problem discussed in this paper is to adapt to concept drift when applied in the domain of business processes analysis. The focus of the paper is on the efectiveness of the proposed concept drift adaption method, finding the bottlenecks is the use case.
We aim to improve the throughput of the process by indicating bottleneck activities based on information we have before the case starts. In our toy example of paper submissions, such information could be the author(s), the research area, the number of publications each author has, and the number of pages in the paper, all of which are known once a submission is made. Using this information we then predict which of the activity will be the bottleneck activity. This bottleneck is then considered as a label for classifiers, which are trained using the information of the case as input.
We assume that the process is stable, i.e. our research is limited to processes whose structure does not change over time. The time evolution we are looking at is that of the relations between case information and bottleneck labels, i.e. the drift in the underlying statistical models. 4
The problem this paper addresses is predicting bottleneck activities in business processes, and improve these predictions by accounting for concept drifts. The goal is not to indicate or explicitly detect concept drift, but to optimise the use of selected previously trained models to improve prediction quality. This section describes the proposed solution, first introducing the context of business processes (Subsection 4.1), next assessing what activity is a bottleneck activity (Subsection 4.2), and finally improving predictions using GRAEC (Subsection 4.3). We discuss them in general and also in applying them to a simulation and a case study in Section 5. 4.1
Process mining is field of research that bridges the gap between the computational possibilities of data mining with the industrial application of business processes, by learning process behaviour from event logs. Event logs consist of events, each describing what happened (Activity), at what time (Time), by whom (Resource), for which process instance (Case ID). Time can alternatively be represented by considering start and end times of events. The analysis in this paper only considers end times (the time when the activity is logged) but can easily be extended to include both. Resources are not considered in the process analysis part of the solution. To explain the algorithm used to define the bottlenecks, some notation is required.
An event log L is a set of events e, a subset of all possible events E. An event e is a combination of the Case ID, Activity, and Time, represented as the tuple (e .cid, e .act, e .time). A case c is a sequence of events, c ∈ E∗. The first element of a sequence c is represented as c(0). We further define the function act (c) : E∗ → A∗, mapping each element of a case to the activity of the event, A being the set of all activities. act (c) is said to be the trace of c, and two cases c1 and c2 are said to be of the same variant if act (c1) = act (c2). The function is extended to a set C of cases; if all c ∈ C have the same variant, act (C) is the sequence of activities for which act (c) = act (C) for all c ∈ C. The duration of a case c is defined as duration(c) = c(|c | − 1).time − c(0).time, i.e. the time diference between the first and the last event. This implies that the duration of the first event is not considered in the duration. If only the end times of events are logged, there is no way to asses the duration of the first event. In the example sketched above this is no issue: the submission merely marks the start of the case, no work is required by the committee. The same applies to the real-world scenario (assessed in Lines 8 and 7 respectively) in Line 15. If there are no activities that satisfies both requirements, we take the activity with the longest duration that satisfies the Resolvability requirement, in Line 17.
Result: Each case c in C gets a label label (c) 1 for i = 1 . . . N do 2 σ ← act (Hi ) 3 for c ∈ Hi do 4 label (c) ← short 5 presented in Section 5. In other processes some notion of the start of the process (like an automated trigger caused by a client) needs to be identified to analyse the throughput of the first activity.
In the example of Figure 1, each case is one submission. The Case ID could be a DOI, the activity set A would be {Submit, Assign reviewers, Review1, Review2, Review3, Combine reviews, Send notification }. Events would relate these two together, providing information on when an activity for the given paper was completed. The process consists of only one variant, i.e. there is only one way to follow the process. Let C be a set of cases. We want to find bottlenecks in cases that have a long duration. We partition the set of cases into Hi and Li , each representing cases that take up to a given time d (Highthroughput) and cases that take more than d (Low-throughput) respectively, for variant i for i ∈ 1...N , N being the total number of variants in C. For activities to be considered bottlenecks, we have two requirements: Relevance and Resolvability.
If an activity has a long duration compared to other cases, but
a short duration compared to other activities in the same case,
it will be less efective to resolve a long duration of that activity
than activities that take up a larger part of the case duration. We
formalise this Relevance requirement by requiring that the fraction
of the total case duration of the activity is at least α , where α ∈ [
An activity is resolvable if it has a longer duration than a benchmark average for that activity. We only address bottlenecks in Li , as such we use the average duration of the activity in Hi as benchmark. This is the Resolvability requirement. We know that there must be at least one activity that satisfies this requirement, since the sum of all durations (i.e. the duration of the case) of any case in Li is larger than the duration of any case in Hi , so at least one activity must take longer than the average of that activity in Hi .
Finally, of all activities that pass both requirements, we choose the activity that deviates the most (in terms of the standard deviation in Hi from the benchmark average). This way ensures that the chosen bottleneck is least explained by the intrinsic variability of real-world processes. This procedure is described in Algorithm 1.
Line 1 loops over each Variant of C. First we derive the Trace of the Variant in Line 2. Note that this is the same as act (Li ). In Lines 3 and 4 we label each case in Hi as short. Lines 7 and 8 calculate the sample mean and standard deviation1. We next consider each case with a long duration in Lines 10 - 19. First we take all indices of the Trace in Line 11. Next we apply the Resolvability requirement in Line 12, and the Relevance requirement in Line 13. We then check if there is any activity that meets both requirements in Line 14. If there is, we apply as the label the activity whose duration deviates the most standard deviations from the mean throughput 1We could also have taken the population standard deviation, it does not make a diference since the sample size is the same for each activity. 4.3
This subsection proposes a method of dealing with concept drift. The general idea is to split available training data into smaller sets, and give weights to the models created by each set. The method is general, and we will demonstrate its efectiveness in our use case of predicting bottlenecks.
Let D be our dataset, and the points in D be di . Each datapoint has input features di .x , a timestamp di .time, and a label di .y. In our use case of business process bottleneck prediction, di is a case, di .x is information about a case, di .time is the timestamp of the first event of a case, and di .y is the bottleneck as labelled by Algorithm 1. In the light of Figure 1, di .x would be information on the author(s), the research area, the number of publications each author has, and the number of pages in the paper. di .time would be the time of the submission, and di .y would be the bottleneck, as indicated in Figure 1.
D contains data over a time period of length T = maxdi ∈D di .time− mindi ∈D di .time. This length is divided into smaller data sets Dj , each with length S, such that di ∈ Dj ⇔ ⌊ di .tSime ⌋ = j. In this paper S is regarded as a constant in time, and diferent values of end for k ∈ 1 . . . |σ | − 1 do x¯k ← |H1i | Íc ∈Hi c(k).time − c(k − 1).time sk ← r Íc∈Hi (c(k).t ime|H−ci (|k−1).t ime−x¯k )2 end for C ∈ Li do
K0 ← 1 . . . |σ | − 1 K1 ← {k |k ∈ K0 : c(k).time − c(k − 1).time > x¯k } K2 ← nk |k ∈ K1 : c(k).t dimurea−tci(okn−(1c)).t ime ≥ α o if |K2 | , 0 then label (c) ← c arg maxk ∈K2 h c(k).t ime−c(skk−1).t ime−x¯k i .act end else label (c) ← c(arg maxk ∈K1 c(k).time − c(k − 1).time).act
S are explored. Picking the right value of S is important, having too short time-frames will mean too few datapoints, having too long time-frames might fail to capture short-term concept drift. The splitting of data is visualised in Figure 2.
We then train a machine learning model on each Dj , resulting in multiple classifiers Mj . This creates an ensemble classifier, and we use a weighting function explained below to decide the importance of each classifier in the ensemble. In the running example, one could decide to train a classifier monthly ( S = 1 month), creating twelve models per year, each consisting of all papers that were submitted in a specific month.
When predicting a test data point, all models Mj receive a weight
based on how old the model is. We propose a combination of two
weights. The first weight is related to exponential decay, and is
inspired by for example [
The second weight relates to giving extra importance to models that are seasonally similar. Say we want to reduce the efects of recurrent concept drift that occurs every p ∈ IR+ time. We hence add weight τ ∈ IR+ to models that belong to d .time − p, d .time − 2p . . .. These additions are given on top of the exponential decay weight; though in most situations we will have that p >> S (we train models far more often than the recurrent concept drift occurs), and hence the exponential weight will be insignificant for models around time d .time − p.2 The determination of the weights is also presented in Algorithm 2.
We combine the models as follows: for datapoints in Dj we let each of the j existing trained prediction models (M0, M1, ..., Mj−1) make a prediction, resulting in j vectors (p1,k , p2,k , ..., pn,k ), where pl ,k is the probability of label l as predicted by model k (where we have a total of n labels in all of D). We determine the combined prediction for the test datapoint d by taking the weighted sum: 2In particular, the implementation only assigns exponential weights of at least 10−6.
3 4 end
Result: For the test prediction d, each model Mk gets a weight wk 1 j ← ⌊ d .tSime ⌋ 2 for k = 0 . . . j − 1 do
wk ← 10−(j−k+1)β 5 t ← d .time − p 6 while t > 0 do 7 k ← ⌊ St ⌋ 8 wk ← wk + τ
t ← t − p 9 10 end pl = Õ
wk · pl ,k 0≤k ≤j−1 where wk is the weight of the described above. The predicted label is then arg maxl pl . The combination of β , τ and p uniquely identifies a weighting assignment, together with S we form a complete concept drift adaption technique. Since this technique adapts to gradual and recurrent drift, we will refer to it as Gradual and Recurrent concept drift Adapting Ensemble Classifier, or GRAEC. Finding the best combination of β , τ , p and S is part of the training process. In this paper we will restrict to a single value for p. 5
This section describes the simulated (Subsection 5.1) and real-world data set used (Subsection 5.2), the experimental setup (Subsection 5.3), and additional information about how the models are trained (Subsection 5.4). The goal of the case study is to test the efectiveness of our proposed method. The actual predicted bottlenecks is of interest to the company, but falls outside the scope of this paper.
The code to run the full Simulation experiment including the implementations of Algorithms 1 and 2 is available at https://github. com/yorick-spenrath/GRAEC. 5.1
We simulate an event log based on the running example. We use
three features: the topic, the number of pages used in the paper,
and the number of publications the author has. The topic is used
to determine where a bottleneck will be, and the number of pages
is used to determine if there will be a bottleneck. As such, the
number of publications will not influence the simulation. The topic
is one of the following: ’Machine Learning’ (ML), ’Data Mining’
(DM), ’Process Mining’ (PM), and ’Operations Management’ (OM).
The number of pages and the number of publications are both
integers in the interval [
We add gradual concept drift by selecting an interval of size 20 in
[
We analyze part of the repair process at a Dutch installation services company. Their repair process is roughly divided into three steps: preparation, repair, and invoicing. We have an event log of about two and a half years, containing about 200 000 cases and about 2 000 000 events, with information on the resource and the time stamp of when an activity ended. We are interested in the invoicing part, which, in the light of Subsection 4.1, is considered as the full process starting at the last repair activity3. We define the throughput of the invoice process as the time diference between the last repair activity occurrence and the last invoice activity occurrence. The invoice consists of three activities and one optional activity, but the event log contains cases that still have repair activities after the first invoice activity, and duplicate or missing invoice activities. In the case of repair activities after an invoice activity, the throughput is measured from the last non-invoice activity before the first invoice activity. We further require that the three main invoice activities 3This also justifies not taking the first event of the case into account when determining the bottleneck (repair assessment, data check, and invoice creation) occur in the case, and that the case is completed (there is a final batching activity in the process that happens once a month). Again, each case from the dataset results in one datapoint. Cases have feature values, such as client, responsible resource, type of defect, client location, all of which are categorical.
The time in the dataset is measured in days, we use S ∈ {7, 14, 21, 28}. This is because the dataset is afected by working days, so taking any other value than a multiple of 7 will result with biased subsets. 5.3
This section describes how we use events logs, to which we refer as L, to assess diferent methods of predicting bottlenecks. Unless otherwise stated, the explanation holds for the simulation study as well as the real-world dataset.
From L we create four diferent datasets DS , one for each value of S. For each S, L is split into smaller subsets LSj , each of duration S, as discussed in Section 4.3. This creates subsets DSj , where information about cases (topic, pages, and publications for the simulation, client information for the Real-world dataset) are related to labels, for period j. DSj contains data about cases that started in [S · j, S · (j + 1)). Note that cases could have diferent bottleneck labels for diferent values of S, as a result of being compared within a diferent set in Algorithm 1. d and α are set to 21 days and 0.2 respectively. For the simulation dataset, this is set by the simulation design, for the real-world dataset this is per recommendation of the company’s domain expert. After labelling each set, the number of datapoints in each subset is reduced using k-medoids with Jaccard distance, to ensure that the largest class in a set is at most twice as big as the smallest class, to reduce overfitting. This is not required for the simulation dataset, as it is already balanced by design. For each subset DSj a model MjS is trained using the method described in the next subsection.
We then compare three diferent approaches. The first approach uses only the first year of data to create a single model, which is then used for all testing. This will be referred to as the Naive method. The second approach uses the model created from the dataset that was most recently completed; if a datapoint of DSj is tested, model MS
j−1 is used. This approach will be referred to as the Recent method. Finally, we use our approach, which will be referred to as GRAEC. Each method is tested on each value of S. Note that this also creates four configurations for the Naive method, since a diferent S results may result in diferent labelling.
We next use the full last year of data for evaluation. This part is split in a stratified 80% - 20% train-test split. The train split is used to optimise the parameters of GRAEC, using a complete grid search with β ∈ {0, 1, 2}, and τ ∈ {0, 0.01, 0.1, 1, 10, 100} for each value of S. We also set p on one year (12 in the simulation, 365.25 in the realworld dataset), as per design and domain expert recommendation. The test split is used to assess all approaches. 5.4
The model MjS is trained by optimising the hyperparameters of
Logistic Regression, kNN, Decision Tree, and Random Forest
classifiers using a stratified 5-fold cross validation on stratified 80%
of a dataset, all using the implementation of the scikit learn library
in Python [
In this section we show the results of applying our approach to the simulation dataset and the real-world dataset described in the previous section. Since the proposed solution aims to adapt to overcome the efects of concept drift and not to detect it, we are only interested in the score, but not in the drift in the process or derived models themselves. In Subsection 6.1 we present and discuss the results of the simulation dataset, in Subsection 6.2 we do the same for the real-world dataset. 6.1
The results of the simulation study are presented in Figure 4 and Table 2. Figure 4 shows the scores of each of the twelve methods applied. The best scores for GRAEC are underlined in Table 2 to indicate the optimal values of β and τ . Table 2 further shows the F1 and accuracy scores for all configurations of β , τ and S. 6.1.1 The efectiveness of GRAEC. The foremost result is the efectiveness of GRAEC. When comparing the scores for each method for a given value of S, GRAEC outperforms the other two methods. The best GRAEC score, for S = 1 outperforms every other option. This is expected, the design of the simulation was to make optimal use of the adaptions GRAEC could give for S = 1. The optimal parameters for GRAEC indicate the adaption for both gradual and recurrent concept drift. 6.1.2 The inefectiveness of Naive. The Naive method is completely inefective for any value of S. This makes sense, since one year of data contains four diferent recurrent concepts. As a result the Naive model will not even be able to properly explain the dataset it was trained on, let alone datasets that only contain a single recurrent concept, and datasets on which the gradual drift has had more efect. 6.1.3 The efect of S. We shortly discuss the efect of each value of S below. We will refer to the way topic the related to the bottleneck activity as a concept, and refer to this concept in quartile 1 as ‘A’, in quartile 2 as ‘B’, 3 as ‘C’, and 4 as ‘D’. A DSj can contain one or more concepts. For example, D01 contains only concept ‘A’, as do D11 and D21, where as D31 has concept ‘B’. On the other hand D12 has concepts ‘A’ and ‘B’ in an equal number of cases. We hence refer to the concept of D12 as ‘AB’, and in line, the concept of D02 is ‘AA’, the concept of D23 is ‘CCC’, and D14 has concept ‘BBCC’.
S = 1 For the Recent method, we have that in two out of the three periods, the previous period had the same concept. As a result, about one third of the predictions are made based on data from a diferent recurrent concept, decreasing the overall score of the Recent method.
S = 2 and S = 4 For S = 2 we will have 6 D2j’s per year, with concepts ‘AA’, ‘AB’, ‘BB’, ‘CC’, ‘CD’, ‘DD’. As a result it will be dificult to train models on the second and fifth D2j each year (with concepts ‘AB’ and ‘CD’ respectively). For the Recent method, predictions are suboptimal because: • in the third and sixth period each year predictions will be made with a bad model • in the second and fifth period each year, only half of the cases are the same as the previous concept • in the first and fourth period each year, none of the cases are the same as the previous concept As a result, the Recent method has a lower score than for S = 1. GRAEC only has the disadvantage of the poor models during predictions in the third and sixth periods, because of the optimal value for τ . The first, second, fourth, and fifth period belong to a single concept (‘A’ through ‘D’ respectively), and models of previous years are re-used. As a result, the negative efect on the score for GRAEC is weaker. The score is still weaker than for S = 1, since there is less adaption to gradual drift, due to the optimal value of τ . For S=4, the arguments follow the same reasoning, though their efect is more present (resulting in a lower score). This is because all consecutive periods have diferent recurrent concepts.
S = 3 The efect of the recurrent concept drift, and how Recent fails to adapt to it while GRAEC does, is most evident for S = 3. Each D3j will be based of a completely diferent concept compared to D3j−1. This has a devastating efect on the Recent method, which can at best tell something about short cases. The GRAEC on the other hand scores almost as well as for S = 1. The slightly decreased score comes from the inability to capture the gradual concept drift. The optimal β = 1, combined with τ = 100 causes the influence of models trained in diferent periods to be insignificant, and GRAEC only adapting to the recurrent concept drift. 6.2
The results of the real-world study are presented in Figure 5 and Table 3. Figure 5 shows the overall scores of each of the twelve methods applied, and Table 3 presents the values of β and τ that belong to each value of S for GRAEC.
S β τ ACC F1 ACC F1 ACC F1 7 1 0 0.417 0.418 0.405 0.405 0.251 0.245 14 1 0.1 0.418 0.417 0.412 0.413 0.253 0.245 21 1 0 0.412 0.410 0.405 0.406 0.264 0.258 28 1 1 0.419 0.416 0.415 0.418 0.267 0.259 Table 3: Optimal values for S, β , and τ , and the Accuracy and F1 scores for the real-world dataset.
The key result to take away from Figure 5 is that the improvement of GRAEC over Recent is present, albeit small. The most likely explanation is that there is no strong efect of recurrent concept drift present in the real-world dataset. This also matches the results for τ ; only S = 28 has a value for τ that puts significant weight to periodically similar models, though for S = 28, there will be two such models at best. Please note that the method: Recent does not exist, and that we used it as an intuitive method for comparison. The results do not disprove the efectiveness of GRAEC. The goal of GRAEC was to allow adaption to both gradual and recurrent concept drift. As is evident from the results for τ , GRAEC is in essence self-correcting the lack of recurrent concept drift. 7
The results from the Simulation study show the potential of GRAEC. We have developed a method that can adapt to both gradual as well as recurrent concept drift. The case study on the real-world dataset shows improvement, albeit it small, over retraining the data periodically. The Simulation study stresses the importance of a correctly chosen S.
Like the simulation study, the real-world scenario was analysed in a post-mortem setting; there was data on completed cases available during analysis. A future research direction is to apply the simulation study as an online setting and include online optimisation of β , τ and possibly S, to see if the adaptions to gradual and recurrent concept drift are still optimal. In such an online setting, care should be taken that supervised information is available with a delay; cases that start in a certain period might complete (long) after the period ends. In such a scenario, the most recent model available may not be from the preceding period. This is because all cases that started in the preceding period might not have ended once the next period starts. As a result both the Recent and GRAEC method will deteriorate, though we expect the Recent method to be more afected by this.
The advantage of the use of a weighted ensemble, as GRAEC,
is the availability of diferent machine learning models. Since we
build one model on each period, we can freely choose the type
of model each time. A diferent method, such as described in [
The weighting functions are based on related work and expert knowledge. In this work we have limited ourselves to one value for p. In future work, diferent values or a superposition of values could be created. Another update to GRAEC would be not to add weight to the single model from the period at d .time − p, but also (some) additional weight to the period before and after d .time − p.
One interesting further future direction is to borrow concepts
from the online process discovery of process models [
Additionally, we would like to address the relatively diferent
problem of drift detection in the more complicated and realistic
scenario where interval-based events are considered [