PTandLogGenerator: a Generator for Arti cial Event Data

Abstract

The empirical analysis of process discovery algorithms has recently gained more attention. An important step within such an analysis is the acquisition of the appropriate test event data, i.e. event logs and reference models. This requires an implemented framework that supports the random and automated generation of event data based on user speci cations. This paper presents a tool for generating arti cial process trees and event logs that can be used to study and compare the empirical workings of process discovery algorithms. It extends current tools by giving users full control over an extensive set of process control- ow constructs included in the nal models and event logs. Additionally, it is integrated within the ProM framework that o ers a plethora of process discovery algorithms and evaluation metrics which are required during empirical analysis.

Keywords

• arti cial event logs
• process simulation
• process discovery

-

The presented tool PTandLogGenerator ful lls all the requirements stated above as it enables the random and automated generation of process trees and event logs based on user-de ned control- ow speci cations. It applies a generic two-step approach: generate a process tree, then simulate this tree into an event log described in [ 4 ]. Firstly, the user speci es the control- ow constructs, de ned as meaningful process blocks that will be included in the generated process trees. In the second step, the trees are simulated into event logs.

The idea of implementing an arti cial data generator is not new. However, the existing tools still have some limitations with regard to the requirements stated above. The most advanced tool, PLG2 [ 1 ], allows for control of the basic work ow patterns, but does not allow for more complex constructs such as duplicate activity labels or long-term dependencies. Moreover, PLG2 is not directly integrated within the ProM framework, which is a disadvantage when doing empirical process discovery evaluation.

The remainder of this paper describes how to use the PTandLogGenerator tool in the case of comparing two process discovery algorithms. 2

Walkthrough of the Process Tree and Log Generator The PTandLogGenerator tool is available as a package in the open-source framework ProM2. This section will describe the di erent steps of generating a sample of event logs needed to evaluate two process discovery algorithms. Consider the comparison of the ++ miner [ 6 ] and the Inductive Miner [ 5 ] on logs including long-term dependencies, i.e. causal dependencies between tasks in di erent exclusive choice constructs. Consequently, one needs a set of event logs containing such long-term dependencies, while controlling for other control- ow constructs. The following paragraphs show how these can be created using the PTandLogGenerator, see https://drive.google.com/file/d/0B9nT4OtWjscVOV94VDEwb3I4V2s/ view?usp=sharing for a screencast.

A Population of Process Trees The starting point is the de nition of a process tree population. These process trees contain a combination of control- ow constructs (CFC), i.e. process tree building blocks, that are used as population parameters to describe the population. The user can assign probabilities to each of the CFC to express the probability that these constructs are added to a tree within the population. We distinguish between three types of constructs: activities, work ow patterns and complex constructs: { Activities (see area 1 in Fig. 1): users can in uence the size of the trees included in the population by specifying the triangular distribution of the number of activities by assigning a minimum, a mode and a maximum. Each time a process tree is generated, i.e. drawn from the population, a random number for the number of activities is taken from that triangular distribution. 2 Available in the ProM nightly builds at http://www.promtools.org/ { Work ow control- ow patterns (see area 2 in Fig. 1): basic fundamental patterns common to all business processes. These patterns include sequence, exclusive choice, multi-choice, concurrent behavior and loops, represented by the following operator nodes in Process trees: !; ; _; ^ and . { Complex constructs (see area 3 in Fig. 1): more complex control- ow constructs include silent activities, reoccurring activities (i.e. duplicate labels), long-term dependencies and infrequent paths. The last construct assigns unequal branch probabilities to each of the outgoing branches of an exclusive choice in order to make some paths less frequent in the process.

In our example use case, we want to evaluate two algorithms on long-term dependencies. Therefore we de ne a population of process trees with 50% probability of inserting long-term probabilities. The de nition of this population can be con gured using the settings wizard shown in Fig. 1.

Generating a Random Sample of Trees The next step involves drawing a random sample, i.e. generating random process trees, from the previously speci ed population. The size of this sample can be speci ed in the tree generator settings as can be seen in area 4 of Fig. 1. For the example use case we generate a random sample of size 10.

The algorithm described in [ 4 ] is implemented to build each process tree in a stepwise manner. It uses the probabilities speci ed in the population as input parameters to randomly Fig. 1: The Population of Process Trees in the Exadd nodes to the tree. ample

The output of this step is a set of process trees in the standard PTML-format. In this way the complete toolbox for import/export, analysis and visualization of process trees integrated into ProM is available to the user. The screenshot in Fig. 2 shows the visualization pane for tree number 3 in the sample. The annotations on the branches represent their execution probabilities. The tree shown in Fig. 2 contains a long-term dependency between the activity h and c expressing the causal relationship that if h is executed, c can never follow later on. For further information, the reader is referred to the tree generating algorithm described in [ 4 ]. Simulating Trees Into Event Logs Then in the third step the tool enables users to generate (an) event log(s) for each process tree in the sample. Each process tree can be seen as a population of event logs: an event log is a multiset of traces simulated from that process tree. The tool allows users to specify the number of traces that the nal event log(s) will contain as shown in Fig. 3a. In the example case we generate one event log with 1000 traces for each tree. The resulting event logs are in the standard XES-format providing all the log functionalities provided in ProM. Fig. 3b shows the log view for the event log generated from the tree in Fig. 2. (a) The Number of Traces in the Generated Event Logs

(b) Log View of the Generated Event Log Evaluating Process Discovery Techniques Once the event logs are generated, the empirical analysis of the evaluation of process discovery technique is enabled. In the running case we apply the ++ miner [ 6 ] and the Inductive Miner [ 5 ] in ProM and calculate quality metrics for each discovered model. In the running case the discovered models of the inductive miner have an average tness value of 100% and a precision value of 58.5%, whereas the models discovered by ++ miner have a lower average tness value of 32.1% and a higher average precision value of 77.9%. These results are used to demonstrate the possible use cases of the tool. A more thorough empirical analysis would need more observations which is outside the scope of this paper. 3

Maturity and Use Cases

The tool has reached a high level of maturity which enables its use in large scienti c experiments. This has been proven by the successful application of the tool in the large scale empirical assessments in [ 3 ]. Furthermore, the organizers of the rst process discovery contest3 have chosen this tool to create the benchmark event logs as it allows users the full control over an extensive range of control- ow constructs.

Acknowledgements

Special thanks to Alfredo Bolt and dr. Massimiliano de Leoni for their help on implementing and improving this tool. 3 http://www.win.tue.nl/ieeetfpm/doku.php?id=shared:process_discovery_ contest

References

1. Burattin , A. : PLG2: Multiperspective Processes Randomization and Simulation for Online and O ine Settings . ArXiv e-prints ( 1506 .08415) ( Jun 2015 )

2. De Weerdt , J. , De Backer , M. , Vanthienen , J. , Baesens , B. : A multi-dimensional quality assessment of state-of-the-art process discovery algorithms using reallife event logs . Information Systems 37 ( 7 ), 654 {676 (Nov 2012 ), http://www. sciencedirect.com/science/article/pii/S0306437912000464

3. Janssenswillen , G. , Jouck , T. , Creemers , M. , Depaire , B. : Measuring the quality of models with respect to the underlying system: An empirical study . In: Business Process Management 2016 . Springer (accepted)

4. Jouck , T. , Depaire , B. : Generating Arti cial Data for Empirical Analysis of Process Discovery Algorithms: a Process Tree and Log Generator . Technical Report , Universiteit Hasselt, Universiteit Hasselt ( Mar 2016 ), http://hdl.handle.net/ 1942 / 20818

5. Leemans , S.J. , Fahland , D., van der Aalst, W.M.: Discovering block-structured process models from event logs containing infrequent behaviour . In: Business Process Management Workshops . pp. 66 { 78 . Springer ( 2014 ), http://link.springer.com/ chapter/10.1007/978-3- 319 -06257- 0 _ 6

6. Wen , L., van der Aalst , W.M. , Wang , J. , Sun , J.: Mining process models with non-free-choice constructs . Data Mining and Knowledge Discovery 15 ( 2 ), 145 { 180 ( 2007 ), http://link.springer.com/article/10.1007/s10618-007-0065-y