During the past years, companies are increasingly storing and collecting event data. This type of data describes the occurrences of events during the execution of a business process. Originally, its main source are IT systems supporting business operations. Recently, Internet of Things, with all its sensors measuring changes in the environment, has become a new important source of event data.
The analysis of event data and the underlying process belongs to the domain of process mining. Within process mining, three broad categories exist: process discovery, conformance checking and process enhancement [1]. This project fits in the subdomain of process discovery. The goal of process discovery is to create a (visual) model representing the process based on event data. These models are typically visualised in a graph based language such as Petri nets or BPMN.
Models learned from data serve multiple purposes. In this project we focus on the purpose to describe and summarise event data and to reveal interesting patterns within this data. Such models are used for exploratory research. Exploratory data analysis (EDA) is an important preliminary to confirmatory and predictive analysis. John Tukey stated that: "Exploratory data analysis can never be the whole story, but nothing else can serve as the foundation stone as the first step" [17]. When presented with a large event log, EDA provides a good understanding of the data at hand which is essential for a useful further analysis of the underlying process.
Researchers from the domain of process mining proposed many discovery techniques which can be used to create a process representation of event data. However, these techniques come with a limitation for EDA. They tend to generate process models which contain more process behaviour than is observed in the data, because they were developed with the rationale that an event log is incomplete. Therefore, they produce models which generalise the behaviour in the event log to represent all possible behaviour.
Figure 1 shows a simple example process model which was discovered with event data. A process can be executed multiple times and each execution refers to a case. The sequence of the events during the process execution is called a trace. Two cases share the same trace if the events occur in the same order. The left side of Figure 1 shows an example of an event log containing several traces.
The model of figure 1 shows the BPMN representation of the model discovered by Evolutionary Tree Miner [3] using the traces on the left side. Other miners discover similar models. While the model is a concise representation of the event data, it is not perfectly precise. In process mining, a perfectly precise model only contains the observed process behaviour. The model in Figure 1 is not perfectly precise, because it allows the execution of the unobserved traces ACDEFG and ABDEGF. To our knowledge, there are not many process discovery techniques that guarantee a perfectly precise model as outcome. We consider this an important research gap for EDA as caution is needed when visualising patterns which are not completely present within the data. Such patterns might mislead the researcher in its conclusions. Based on the model in Figure 1 the researcher might conclude that E, F and G occur in any order. However, the data does not support this conclusion. Close inspection of the data reveals for example that G never occurs between E and F. Therefore, a good exploratory model should only hint at patterns that are not fully supported in the data, but should never present them as facts.
Mining a perfectly precise model is not difficult. The trace model, which consists of a single exclusive choice where each possible path represents a trace from the event log, is always perfectly precise. Figure 2 shows the trace model for the traces in Figure 1. Although the trace model is perfectly precise, it performs poorly in some aspects of comprehensibility, because it is difficult to identify patterns of choice and concurrency. Exploratory models should not only be perfectly precise, but also be optimised for comprehensibility. Figure 3, for example, illustrates a perfectly precise model for the traces in Figure 1, but has a higher comprehensibility than the trace model. The main difference between both models is the number of duplicate tasks. The relation between duplicate tasks and comprehensibility is complex and non-linear. Too many duplicate tasks hide patterns (cfr. Figure 2) and decrease the comprehensibility. However, a certain number of duplicate tasks also adds structure to the process and reduces clutter [13] which increases comprehensibility.
This leads to the second research gap which we will address in this project. According to a recent literature review [5], none of the existing metrics measuring process model comprehension account for the influence of duplicate tasks on comprehensibility. This is due to the fact that it is implicitly assumed that process models have unique labels.
This research project is important because the current discovery algorithms produce imprecise models which limit their value for EDA. As EDA is an impor-Fig. 3. A perfectly precise model with limited duplicate activities tant first step for any data analysis project, having an algorithm which produces comprehensible and precise models will make it significantly easier to identify interesting patterns and ideas for follow-up (confirmatory/predictive) analysis. Our research is unconventional in the sense that the guiding principles for our discovery algorithm will be precision and comprehensibility, whereas current techniques rely on the assumption that the event log is incomplete.
The overall research goal is to develop a process discovery algorithm for exploratory data analysis which generates a perfectly precise and comprehensible process visualization of the event data. To achieve this overall research goal, three research objectives need to be achieved:
Firstly, a discovery algorithm needs to be developed. This algorithm should be able to generate models with perfect precision, optimised comprehensibility and representing a certain number of traces from the event log. In addition to generating perfectly precise models, the algorithm must meet the following requirements to be of value during exploratory research:
-Generate comprehensible models: the purpose of EDA is to get a good understanding of the data and to easily recognise interesting patterns. Optimization of comprehensibility must directly guide the algorithm. -Generate models representing a certain number of traces: traditional discovery algorithms focus on learning a model for the entire event log, which often results in overly complex models. During EDA, the researcher is not always interested in a single model representing all traces. Therefore, the data analyst should be able to set the number of traces which should be represented by the model. The algorithm should select the set of traces which results in the most comprehensible perfectly precise model.
-Allow for different comprehensibility measures: the algorithm should be flexible enough such that a different measure can be used without changes to the algorithm. -Be extensible: part of this project will focus on how to optimally visualise certain aspects of a process. These insights will be incorporated into the algorithm. The mechanism to do so must be flexible enough such that future insights can be easily incorporated. -Use BPMN as the graphical notation: empirical research has shown that the BPMN notation appears to be the strongest in providing for a good understanding by model readers [6].
Secondly, more comprehensible visualizations for partial parallelism and longterm dependencies need to be designed. Partial parallelism occurs when a set of activities seem to happen in parallel, but not all possible combinations are observed in the event log. Long-term dependencies are observed when an exclusive choice is partially determined by the occurrence or non-occurrence of previous activities in the trace. Both constructs are present in the data of Figure 1. Activities E, F and G are only partially in parallel since we never observe a trace with G occuring between E and F. The exclusive choice after activity D is limited to activity H when activity C occurred. Both constructs have a tendency to make a model less comprehensible. The goal of this research objective is to search for different kinds of visualization to improve comprehensibility.
Thirdly, an empirically validated comprehensibility measure needs to be developed. This measure should be applicable to the models generated by our algorithm. Our algorithm uses a comprehensibility measure as its guiding mechanism. This implies that the measure also needs to account for the comprehensibility cost of duplicate tasks and the different visualizations developed as part of research objective two.
In the domain of process mining, many algorithms have been developed to discover the control-flow of process models. To our knowledge, none of the existing algorithms create perfectly precise models while optimizing for the understandability. Most algorithms put a less stringent notion of completeness than global completeness. The notion of global completeness implies that all possible behaviour of the process is included in the log [4]. As the creators of most existing algorithms made the assumption that the log is incomplete, there are patterns included into the process models which are not present in the log.
Existing discovery algorithms can be categorized into five categories [4]. The first category is the abstraction-based algorithms. One of the best known discovery algorithms is the α-algorithm [2]. The α-algorithm and its derivatives are all abstraction-based algorithms. The heuristics miner [18] is the only algorithm belonging to the heuristic-based algorithms category and takes into account the presence of noise. The third category is the search-based algorithms, which contains the Evolutionary Tree Miner based on genetic algorithms [3]. This category contains all algorithms which use metaheuristics to infer a process model. Models created by existing algorithms of the first three categories are not perfectly precise, because one of the underlying assumptions is the incompleteness of the event log. Language-based region algorithms can generate perfectly precise models. This fourth category uses the theory of regions to construct a process model [14]. However, the algorithms do not directly optimize for understandability. The last category contains the state discovery algorithms [4]. These algorithms first construct a transition system and then derive a Petri net. Nevertheless, they do not directly optimise for understandability either.
The general methodology for this project follows the principles of design science research (DSR). DSR deals with the creation of artifacts and scientific knowledge about these artifacts with the goal to provide solutions to a class of problems [8]. A typical DSR project consists of five steps: problem identification, requirement specification, artifact design and development, artifact evaluation and result communication. The problem identification step has largely been done during the preliminary study in preparation for this research paper. For each research objective of Section 2, a methodology will be described.
We start with the development of the empirically validated comprehensibility measure, because the new discovery algorithm can only be created using the measure. The first step in the development of this measure is a literature review to identify different aspects of a process model which have been empirically proven to influence comprehensibility. Through this literature review, we are able to gather the requirements for the measure. Therefore, this step is the requirement specification.
During the artifact design and development phase, we will develop an algorithm which quantifies the presence of these aspects within the process model. This part of the study has already been executed. 23 existing metrics were identified and implemented using the programming language R. The results are published in the form of an R package on CRAN1 and will be sent to the journal paper SoftwareX. At the moment, there are no other software packages that can calculate all implemented metrics for a batch of BPMN models. In addition, an exploratory factor analysis is performed. This factor analysis allows to discover the underlying dimensions of the large number of metrics. The sample of models used for the factor analysis consisted of BPMN models from the BPM AI (Business Process Management Academic Initiative) [11] and models generated by the PTandLogGenerator [9]. The results of this factor analysis are published as conference proceedings and are presented at the EOMAS (Enterprise & Organizational Modeling and Simulation) workshop which takes place in conjunction with CAISE 2018.
Next, we will conduct an experiment to determine the impact of each dimension on comprehensibility. Participants will receive process models and a set of questions to test their understanding of the models. We apply a within-subjects design to control for the effects on comprehensibility related to the model reader. The dependent variables will be an objective comprehension accuracy measure such as percentage of correct answers, a time-taken measure and a subjective comprehension difficulty measure. The independent variables in this study will be the quantifications of the different model aspects within the models. After running the experiment, we will apply a multi-level regression analysis on the collected data to determine the impact of each factor on comprehensibility. The parameter estimates will become the empirically-validated weights for our new comprehension measure. The artifact will afterwards be evaluated and demonstrated and the results will be communicated as a journal paper.
When the comprehensibility measure is created, the discovery algorithm can be created. Two versions of the discovery algorithm will be developed: one which generates a model representing all traces and one which generates a model representing a predefined minimum number of traces. To develop and design the algorithms, we will transform the discovery problem into an optimization problem. This approach has been applied before by [3], which used genetic algorithms as search strategy. However, genetic algorithms are less suited for our problem since it would be difficult to define mutate and cross-over operators that are necessary to result in perfectly precise models.
Our approach is inspired by Iterated Local Search [15], which has not been applied before in this context. Our algorithm will use the trace model as initial solution and apply domain-specific local search operators (LSOs) to modify the model by transforming duplicate tasks into more complex process structures. For the first version, we will develop at least two LSOs: one for parallel constructs and one for exclusive choice constructs. Other LSOs may be defined later. Each LSO should guarantee perfect precision after transformation. The LSOs are the mechanism that make the algorithm extensible.
For the second version of the algorithm, two new operators will be created: a trace removal and a trace imputation operator. The removal operator will remove parts of the process model that correspond to entire traces. The imputation operator will add entire traces from the event log to the model. Both operators should modify the model in such a way that perfect precision remains guaranteed.
To verify whether our models are perfectly precise and represent all traces, we first use the Behavior Recall metric [7] to check whether all traces are represented by the model. If so, we will use the ETC Precision [12] to test if the model is perfectly precise. Because both metrics require the process model to be represented as a Petri net, we will use the transformation algorithm in [10]. For the BPMN constructs in our models, this algorithm guarantees bisimilarity. To evaluate the comprehensibility of the models, there is no other algorithm to compare with. Therefore, we are limited to a descriptive analysis of the algorithms performance in terms of comprehensibility. We will analyze the improvements with respect to the trace model and apply a sensitivity analysis to see which aspects influence the algorithms ability to improve comprehensibility. For evaluation we will use a broad set of event logs, both real and artificial. The real data will be taken from the collection made available by the IEEE Task Force on Process Mining. The artificial data sets will be created using [9]. The results will be made available in an R package on CRAN and scientific papers.
We aim to create more comprehensible visualizations for partial parallelism and longterm dependencies. To determine the requirements of these alternative visualizations, we will apply a multi-dimensional long-term case study with expert users as suggested in [16]. Since the purpose of the case study is to increase transferability to people who have the same needs, a sample of 3 to 5 expert users is appropriate [16]. Experts will be data analysts, both from academia and industry. The case study is multi-dimensional because it combines different research methods such as interviews and observations. It is also long-term, because it involves a longitudinal study throughout the entire DSR cycle. These new visualisations need to be incorporated in the comprehensibility measure of Section 4.1 and in the discovery algorithm of Section 4.2.
Industry is becoming increasingly data-driven. The past decade both the amount of data collected and the nature of the data has changed. This project focusses on event data, which describes how (business) processes are executed. The first step for retrieving insights from data is through exploratory data analysis (EDA). Despite the many algorithms which discover process models from event data, none of them are really suited for EDA for two reasons. Firstly, they tend to create models which contain behaviour that was not observed data. Secondly, almost none of the existing algorithms optimise their models in terms of comprehensibility, while this is necessary to recognise easily interesting patterns.
This project contributes to both process mining and data analytics. It creates a discovery algorithm suitable for EDA. The resulting models only represent the observed behaviour and are optimised for comprehensibility. Further contributions of this project are a first comprehensibility measure which takes duplicate tasks into account and alternative visualizations for partial parallelism and longterm dependencies.
Acknowledgments I would like to thank FWO for my PhD scholarship.