Preprocessing Event Data in Process Mining

Abstract

Process mining aims at obtaining insights into business processes by analyzing event data recorded in information systems. Many of current process mining algorithms have di culties dealing with real event data because of two main reasons. Sometimes noisy and infrequent behavior in event data leads to having complex and incomprehensible results. Furthermore, some process mining algorithms are inapplicable for large event data using normal hardware. In this research, we aim to provide some general preprocessing approaches to deal with the above problems. Using these approaches, we aim to decrease the size and complexity of event data and consequently improve the performance of many process mining algorithms when holding similar results. Some of these approaches are also able to improve the quality of some process mining results. We also discuss some of the challenges of this research.

Keywords

• Process Mining Preprocessing Event Log Preprocessing Quality Improvement Performance Improvement

Introduction

Process Mining aims to bridge the gap between traditional data mining and business process management analysis [ 1 ]. In this eld of study, we extract knowledge from event data, also referred to as event logs, readily available in most current information systems. The main three sub- elds of process mining are 1) process discovery, i.e, nding a descriptive model of the underlying process, 2) conformance checking, i.e, monitoring and inspecting whether the execution of a process in reality conforms to the corresponding designed (or discovered) reference process model, and 3) enhancement, i.e, the improvement of a process model, based on related event data [ 1 ]. In all of the mentioned sub- elds, event logs are used as a starting point. An event log is a collection of events extracted in the context of a process that indicates which activity has happened at a speci c time.

Many of the proposed algorithms in each of the above categories are perfectly performing on synthetic event data; however, they are not useful or applicable for real scenarios because of two main reasons. First, real event data usually contains noise and/or infrequent behavior. Therefore, the statement "garbage in, garbage out", i.e., referring to the fact that low-quality data leads to low nal quality knowledge [ 22 ] also applies to the eld of process mining. For example, various automated process discovery algorithms work perfectly on synthetic Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). event data; but, dealing with real event data they usually return complex and incomprehensible process models concealing the correct and/or relevant behavior of the underlying process. Using event log preprocessing, we are able to improve the quality of process mining results [ 7 ]. Second, by increasing the size and variability of event logs in di erent information systems, many of process mining algorithms, e.g., conformance checking and trace clustering, are no longer feasible using standard hardware in limited time. Therefore, similar to the general data mining domain, we require some preprocessing steps to obtain event data which leads to having process mining results faster.

In this research, we have the following research questions. { Can we have process mining results with higher quality by preprocessing event logs? { Is it possible to improve the performance of process mining algorithms using the preprocessed event logs? { Do process mining results on preprocessed event logs are comparable with the cases that we used original event logs?

Therefore, we aim to provide some general preprocessing approaches that help a wide range of process mining algorithms. Using these approaches, we are able to apply the currently developed process mining algorithms directly on the preprocessed event data and it is not necessary to modify these algorithms. Moreover, we expect that the preprocessing algorithms require as little as possible business knowledge from the end-user. For example, to remove outlier behavior in event data, we assume that the user does not know the underlying process.

Note that, some process mining algorithms, e.g., conformance checking, are able to provide the accurate results. So, it is expected that by using preprocessing algorithms we can improve just their performances.

The remainder of this paper is structured as follows. Section 2 provides some related work in the area of preprocessing in process mining. The research approach is explained in Section 3. In Section 4, we show the results of applying some of the preprocessing methods. Thereafter, a couple of challenges that we have in this research are given in Section 5. Finally, Section 6 concludes the paper. 2

Related Work

A plethora of di erent process mining techniques exists, ranging from process discovery to prediction. However, given the focus of this paper, we limit related work to the eld of preprocessing techniques in the process mining domain. We refer to [ 17 ] for an overview of di erent preprocessing techniques in data mining.

[ 7 ] indicates many quality issues for event logs. In [ 23 ], the authors identify some event log imperfection patterns that reduce the trustworthiness of process mining results. Moreover, [ 25 ] outlines typical data quality problems in event data and possible approaches to tackle them. however, to use most of these approaches, we need to have business knowledge of the underling process of the event log.

Many process discovery algorithms, e.g., [ 20, 2 ], were designed to be able to handle infrequent behavior in event data and improve the quality of discovered process models. But, these ltering methods are tailored towards the internal working of the corresponding algorithms and they are not able to be used for general-purpose event log preprocessing. Besides, they typically focus on a speci c type of behavior, e.g, incompleteness. There are some research has been done to improve the quality of process discovery algorithms by preprocessing the event log. [ 24 ] proposes to lter out chaotic activities to have process models with higher quality. In [ 9 ], the authors propose to use an anomaly free automaton to remove infrequent behavior. Furthermore, it is also recommended to lter out process instances which contain infrequent behavior from event data using probabilistic [ 11 ] and sequence mining [ 12 ] approaches. Moreover, in [ 13, 14 ], we propose modifying infrequent behavior to more general ones in each process instance instead of removing them. In all of these approaches, the improvement in quality of discovered models is measured by F1-Measure, i.e., the combination of precision and tness [ 8 ]. In [ 10 ], a prototype selection approach based on a clustering algorithm is used to improve F1-Measure and simplicity of discovered process models. Moreover, [ 21 ] proposes to consider a sample of traces to make it feasible to clustering traces of large real event logs.

There is also some research has been done to improve the performance of process mining algorithms and providing an approximation of process mining results. In [ 5 ], the authors recommend a statistical trace-based sampling method to decrease the discovery time and memory footprint. Furthermore, [ 6 ] recommends a trace-based sampling method speci cally for the Heuristic miner. Likewise, in [ 15 ], we analyze random and biased sampling methods with which we are able to adjust the size of the sampled data for process discovery. Moreover, some research has been done to approximate the alignment value by preprocessing event logs. [ 4 ] proposes to statistically sample the event log and applying the conformance checking algorithm on the sampled data. In [ 16 ], we propose that if just a part of behavior in an event log is used for conformance checking, we are able to have a suitable approximation of it faster. There is also some research has been done on using preprocessing methods that help us to have an approximation of performance analysis [ 5 ]. 3

Research Approach

As shown in Figure 1, We consider preprocessing methods a function (i.e., ) that receives an event log (i.e., L) and returns a preprocessed event log (i.e., L' ). In this way, a process mining method (i.e., PM ) can be applied directly on the preprocessed event log without need to modify it. Here, we consider that PM has only one input (i.e., L), but in reality it may have more inputs. To evaluate the e ciency of the preprocessing methods, we are able to consider the performance of mining methods or quality of results. To compute performance improvement,

Original Event Log

(L) PM Result (M)

Preprocessing (ρ)

Preprocessed Event Log

(L’) PM Result (M’) we consider the time of PM on L and compare it with its computation time on L' plus preprocessing time. However, for some applications, we can ignore the preprocessing time. Note that, we compute the quality of both M and M' based on the original log. In general, with preprocessing methods, we reduce the complexity of event data by preprocessing methods. The complexity of an event log depends on many factors such as number of traces, number of unique trace-variants, number of activities and average length of traces in it. Therefore, the research goals of preprocessing functions that are presented in this research are 1- improving the quality of M 0 compared to M respect to L 2- Reducing the required time of PM on L0 when M 0 M .

Figure 2 shows di erent preprocessing approaches that can be used to reduce the complexity and size of event logs. To simplify the concept, we consider an event log as tabular data that rows correspond to traces (or process instances) and columns show the activities. Note that for each approach, it is possible to have di erent preprocessing methods. The rst approach that covers the majority of preprocessing methods aims to select some rows and put them as they are in the preprocessed event log. In other words, they focus on selecting some process instances of the original event log and putting them in the preprocessed event logs. Depends on the goal of preprocessing, some techniques try to not select process instances with outlier behavior (e.g., [ 11, 12, 18 ] and some others aim to select some representative process instances (e.g., [ 4, 15, 10, 16 ]).

Moreover, to improve the performance of process mining results (and sometimes their quality and at the same time) it is also possible to select some activities and project event logs on them (e.g., [ 24 ]). Note that many process mining algorithms are performing linear on the number of process instances in the given event log, but they perform exponential on the number of activities [ 19 ]. However, by removing activities, we sometimes add new behavior that does not exist in the original event log. For example, by removing b from sub-sequence ha; b; ci, we implicitly say that there is a direct relation between a and c that does not exist in the original sub-sequence. Trace Selection Activity Selection

Generalization

Finally, it is also possible to merge unique process instances or activities to more general ones. In this way, we reduce the complexity of event logs by decreasing the uniqueness of behavior in it. We are able to apply this approach on just unique trace-variants level, just activity level, and on both of them.

Let L 2 B(A ) be the original event log that is a multiset of sequence of activities where A is the set of activities in this event log. We de ne that L0 = (L) is a preprocessing function where L0 2 B(A0 ) is the preprocessed event log. For trace selection approach, we have L0 L. Therefore, using this approach, we do not add any new behavior to the event log. However, in activity selection approach, we have L0 2 B(A0 ) where A0 A. Moreover, for generalization approach, it may exist some a0 2 A0 where a0 2= A and some traces 0 2 L0 where 0 2= L. It should be noted that a preprocessing method can provide a hybrid approach that uses two or more of the mentioned approaches. 4

Current Results

In this section, we bring some results of current preprocessing functions considering the de ned research goals. For details of the experiments, please see the corresponding reference. Note that all the event logs that are used for these experiments are real event logs which belong to di erent elds, from health-care to insurance1. Table 1 shows how by providing di erent preprocessing functions we are able to improve results of process discovery algorithms. In this table, 1 The event logs are accessible from https://data.4tu.nl/repository/collection:event logs.

Nothing Log Fitness Precision F1-measure BPIC-2012 1.00 0.12 0.21 BPIC-2018-Dept. 1.00 0.83 0.90 BPIC-2018-Insp. 1.00 0.13 0.23 BPIC-2018-Ref. 1.00 0.91 0.95 BPIC-2019 1.00 0.36 0.53 Hospital 1.00 0.39 0.57 Road 1.00 0.53 0.69 Sepsis 1.00 0.20 0.34

Model Size 27.75×35.75×515

9×9×37.5 19×26.25×311 9.5×11×36 43.5×46×1242.25 20.75×23.5×410.5 15×17.25×134.5 20×30.25×389.5

Nothing refers to not using any preprocessing algorithm (i.e., our baseline). On the other hand, Sampling [ 15 ], Statistical [ 5 ], and Prototype Selection [ 10 ] are di erent preprocessing functions that all of them work based on the trace selection approach. To compute tness and precision, the original event logs are used. It is shown that using preprocessing methods leads to improve the quality of discovered process models. This goal is usually achieved by scarifying a little in tness and increasing a lot in precision.

In Figure 3, we show that how by applying di erent sampling process methods, we are able to improve the performance of process discovery algorithms. The red dotted line shows the case that no preprocessing method is used. The yaxis indicates how many times the process discovery algorithms are faster using di erent preprocessing methods. Here, we consider some di erent instance selection methods (i.e., [ 15, 5 ]). Results indicate that by applying these preprocessing methods we can improve the performance of process discovery algorithms. In Table 1 and in the cited papers in more detail, it is shown those process models that are discovered using some of these preprocessing methods have a higher quality compared to the case that the original event logs are used.

Using preprocessing is not limited to just process discovery algorithms. In Figure 4, it is shown how by using di erent preprocessing methods we can improve the performance of conformance checking. The red dotted line indicates the required time for the normal conformance checking method. Moreover, the y-axis shows how much faster the alignment value is computed using the preprocessing methods. It is indicated in [ 16 ] that most of the proposed methods are able to provide accurate conformance approximation values for these event logs. There are the following main challenges in front of this research. { How to measure the quality of process mining results in a quanti able way? For instance, much of the research uses F-Measure (i.e., the combination of tness and precision) to compare di erent process models. We think that using this measure is not accurate enough, speci cally because it contains the precision metric. For example, the split miner [ 2 ] usually returns a process model with high F-Measure, but with also a high complexity [ 3 ]. Moreover, for some other process mining results, the comparison is even more challenging because there is no speci c measure for them. As an example, it is challenging to compare performance analysis results that are gained by different prepossessing methods. It is also challenging to measure the accuracy of some approximated process mining results. { Finding the best preprocessing parameters setting. Most of preprocessing methods have some parameters that by changing them we will have di erent results. The best setting of preprocessing parameters is various when we deal with di erent event logs. Moreover, sometimes there is a trade-o between performance improvement and the quality of process mining results. Consequently, adjusting these parameters is di cult and sometimes needs to be done using a trial and error method. Therefore, it is worth to at least reduce the range of parameters' values based on the characteristics of the given event log. In this work, we explain that many process mining algorithms have di culties dealing with real large/noisy event data. To tackle these problems, we aim to provide some preprocessing functions that reduce the complexity of event logs. At the same time, the results of process mining algorithms on the preprocessed event logs should be close to the original ones. We discuss some related work in this area and provide three general approaches to preprocess event logs. Our preliminary results show that the trace selection approach is able to improve the performance/quality of process mining results. We plan to develop new event log preprocessing methods that work based on activity selection and generalization approaches.

Acknowledgement

This research is supervised by Prof. Wil van der Aalst and Dr. Sebastiaan van Zelst. We thank the Alexander von Humboldt (Avh) scholarship for funding this work.

References

1. van der Aalst , W.M.P. : Process Mining - Data Science in Action, Second Edition . Springer Berlin Heidelberg ( 2016 ). https://doi.org/10.1007/978-3- 662 -49851-4

2. Augusto , A. , Conforti , R. , Dumas , M. , La Rosa , M. , Polyvyanyy , A. : Split miner: Automated Discovery of Accurate and Simple Business Process Models from Event Logs. Knowledge and Information Systems pp. 1 { 34 ( 2019 )

3. Augusto , A. , Conforti , R. , Dumas , M. , Rosa , M.L. , Maggi , F.M. , Marrella , A. , Mecella , M. , Soo , A. : Automated discovery of process models from event logs: Review and benchmark . CoRR abs/1705 .02288 ( 2017 )

4. Bauer , M., van der Aa, H., Weidlich , M. : Estimating process conformance by trace sampling and result approximation pp. 179 { 197 ( 2019 )

5. Bauer , M. , Senderovich , A. , Gal , A. , Grunske , L. , Weidlich , M. : How much event data is enough? a statistical framework for process discovery . In: International Conference on Advanced Information Systems Engineering . pp. 239 { 256 . Springer ( 2018 )

6. Berti , A. : Statistical sampling in process mining discovery . In: The 9th International Conference on Information, Process, and Knowledge Management . pp. 41 { 43 ( 2017 )

7. Bose , R.J.C. , Mans , R.S., van der Aalst, W.M.P. : Wanna improve process mining results? In: 2013 IEEE symposium on computational intelligence and data mining (CIDM) . pp. 127 { 134 . IEEE ( 2013 )

8. Buijs , J.C., van Dongen , B. , van der Aalst , W.M.P. : On the Role of Fitness, Precision, Generalization and Simplicity in Process Discovery . In: OTM, " On the Move to Meaningful Internet Systems" . pp. 305 { 322 . Springer ( 2012 )

9. Conforti , R. , La Rosa , M. , ter Hofstede , A.: Filtering Out Infrequent Behavior from Business Process Event Logs . IEEE Trans. Knowl. Data Eng . 29 ( 2 ), 300 { 314 ( 2017 ). https://doi.org/10.1109/TKDE. 2016 .2614680

10. Fani Sani , M. , Boltenhagen , M., van der Aalst , W.: Prototype selection based on clustering and conformance metrics for model discovery . arXiv preprint arXiv: 1912 . 00736 ( 4 ), 471 { 507 ( 2019 )

11. Fani Sani , M., van Zelst , S.J., van der Aalst, W.M.P. : Improving Process Discovery Results by Filtering Outliers Using Conditional Behavioural Probabilities . In: Business Process Management BPM Workshops , Barcelona, Spain. pp. 216 { 229 ( 2017 )

12. Fani Sani , M., van Zelst , S.J., van der Aalst, W.M.P. : Applying sequence mining for outlier detection in process mining . In: OTM Confederated International Conferences" On the Move to Meaningful Internet Systems" . pp. 98 { 116 . Springer ( 2018 )

13. Fani Sani , M., van Zelst , S.J., van der Aalst, W.M.P. : Repairing outlier behaviour in event logs using contextual behaviour . Enterp. Model. Inf. Syst. Archit. Int. J. Concept. Model . 14 , 5 : 1 {5: 24 ( 2018 )

14. Fani Sani , M., van Zelst , S.J., van der Aalst, W.M.P. : Repairing outlier behaviour in event logs using contextual behaviour . Enterp. Model. Inf. Syst. Archit. Int. J. Concept. Model . 14 , 5 : 1 {5: 24 ( 2018 ). https://doi.org/10.18417/emisa.14.5, https://doi.org/10.18417/emisa.14.5

15. Fani Sani , M., van Zelst , S.J., van der Aalst, W.M.P.: The impact of event log subset selection on the performance of process discovery algorithms . In: New Trends in Databases and Information Systems , ADBIS 2019 Short Papers , Workshops BBIGAP , QAUCA, SemBDM, SIMPDA, M2P, MADEISD, and Doctoral Consortium, Bled, Slovenia, September 8- 11 , 2019 , Proceedings. pp. 391 { 404 ( 2019 )

16. Fani Sani , M., van Zelst , S.J., van der Aalst, W.M.: Conformance checking approximation using subset selection and edit distance . arXiv preprint arXiv: 1912 . 05022 ( 2019 )

17. Garc a, S., Luengo , J. , Herrera , F. : Data preprocessing in data mining . Springer ( 2015 )

18. Ghionna , L. , Greco , G. , Guzzo , A. , Pontieri , L. : Outlier Detection Techniques for Process Mining Applications . In: ISMIS 2008 . pp. 150 { 159 ( 2008 )

19. Hompes , B. , Verbeek , H., van der Aalst, W.M.P. : Finding suitable activity clusters for decomposed process discovery . In: International Symposium on Data-Driven Process Discovery and Analysis . pp. 32 { 57 . Springer ( 2014 )

20. Leemans , S.J. , Fahland , D., van der Aalst, W.M.P. : Discovering Block-Structured Process Models from Event Logs Containing Infrequent Behaviour . In: BPI, pp. 66 { 78 ( 2014 )

21. Lu , X. , Tabatabaei , S.A. , Hoogendoorn , M. , Reijers , H.A. : Trace clustering on very large event data in healthcare using frequent sequence patterns . In: Business Process Management - 17th International Conference, BPM 2019 , Vienna, Austria, September 1- 6 , 2019 , Proceedings. pp. 198 { 215 ( 2019 )

22. Pyle , D. : Data Preparation for Data Mining . morgan kaufmann ( 1999 )

23. Suriadi , S. , Andrews , R., ter Hofstede , A. , Wynn , M.T.: Event log imperfection patterns for process mining: Towards a systematic approach to cleaning event logs . Information Systems 64 , 132 { 150 ( 2017 )

24. Tax , N. , Sidorova , N., van der Aalst , W.M.P. : Discovering more Precise Process Models from Event Logs by Filtering out Chaotic Activities . Journal of Intelligent Information Systems pp. 1 { 33 ( 2018 )

25. Wynn , M.T. , Sadiq , S. : Responsible process mining-a data quality perspective . In: International Conference on Business Process Management . pp. 10 { 15 . Springer ( 2019 )