Control-flow discovery is considered as one of the crucial features of Process Mining [13]. Intuitively, discovering the control-flow of a process requires to analyze its executions and extract the causality relations between activities which, taken together, illustrate the structure and ordering of the process under consideration.
There are many factors that may hamper the applicability of a control-flow discovery algorithm. On the one hand, the log characteristics may induce the use of particular algorithms, e.g., in the presence of noise in the log it may be advisable to consider a noise-aware algorithm. On the other hand, the representational bias of an algorithm may hinder its applicability for elicitating the process underlying in a log.
Even in the ideal case where the more suitable control-flow discovery algorithm is used for tackling the discovery task, it may be the case that the default algorithm's parameters (designed to perform well over different scenarios) are not appropriate for the log at hand. In that case, the user is left alone in the task of configuring the best parameter values, a task which requires a knowledge of both the algorithm and the log at hand.
In this paper we present a method to automatically assess the impact of parameters of control-flow discovery algorithms. In our approach, we use an efficient technique from the discipline of sensitivity analysis for exploring the parameter search space. In the next section, we charaterize this sensitivity analysis technique and relate it with other work in the literature for similar purposes done in other areas.
We consider three direct applications of the method presented in this paper:
(A) As an aid to users of control-flow discovery algorithms: given a log, an algorithm and a particular quality metric the user is interested in, a method like the one presented in this paper will indicate the parameters to consider. Then the user will be able to influence (by assigning meaningful values to these parameters) the discovery experiment. (B) As an aid for recommending control-flow discovery algorithms: current recommendation systems for control-flow process discovery (e.g., [9]) do not consider the parameters of the algorithms. Using the methodology of this paper, one may determine classes of parameters whose impact refer to the same quality metric, and those can be offered as modes of the same algorithm tailored to specific metrics. Hence, the recommendation task (i.e., the selection of a discovery algorithm) may then be guided towards a better use of a control-flow technique. (C) As a new form of assessing the representational bias of an algorithm: given a log and an algorithm, it may well be the case that the impact of most of the algorithm's parameters is negligible. In that case, then if additionally the result obtained is not satisfactory, one may conclude that this is not the right algorithm for the log at hand.
The rest of the paper is organized as follows: Section 2 illustrates the contribution and provides related work. Section 3 provides the necessary background and main definitions. Then, Section 4 presents the main methodology of this paper, while Section 5 provides a general discussion on its complexity. Finally, Section 6 concludes the paper.
The selection of parameters for executing control-flow algorithms is usually a challenging issue. The uncertainty of the inputs, the lack of information about parameters, the diversity of outputs (i.e., the different process model types), and the difficulty of choosing a comprehensive quality measurement for assessing the output of a control-flow algorithm make the selection of parameters a difficult task.
The parameter optimization is one of the most effective approaches for parameter selection. In this approach, the parameter space is searched in order to find the best parameters setting with respect to a specific quality measure. Besides the aforementioned challenges, the main challenge of this approach is to select a robust strategy to search the parameter space. Grid (or exhaustive) search, random search [2], gradient descent based search [1] and evolutionary computation [7] are typical strategies, which have proven to be effective in optimization problems, but they are usually computationally costly. [16,6,3] are examples of parameter optimization applications on a control-flow algorithm. Besides the fact that only a single control-flow algorithm is considered, all of these approaches rely on quality measurements that are especially designed to work on a specific type of process model.
A different approach, which may also be used to facilitate the parameter optimization, is known as sensibility analysis [11] and consists of assessing the influence of the inputs of a mathematical model (or system) on the model's output. This information may help on understanding the relationship between the inputs and the output of the model, or identifying redundant inputs in specific contexts. Sensibility methods range from variance-based methods to screening techniques [11]. One of the advantages of screening is that it requires a relatively low number of evaluations when compared to other approaches. The Elementary Effect (EE) method [8,4,5] is a screening technique for sensibility analysis that can be applied to identify non-influential parameters of computationally costly algorithms. In this paper, the EE method is applied to assess the impact of the parameters of control-flow algorithms.
This section contains the main definitions used in this paper.
Process data describe the execution of the different process events of a business process over time. An event log organizes process data as a set of process instances, where a process instance represents a sequence of events describing the execution of activities (or tasks).
Definition 1 (Event Log). Let T be a set of events, T * the set of all sequences (i.e., process instances) that are composed of zero or more events of T , and δ ∈ T * a process instance. An event log L is a set of process instances, i.e., L ∈ P(T * ). 1A process model is an activity-centric model that describes the business process in terms of activities and their dependency relations. Petri nets, Causal nets, BPMN, and EPCs are examples of notations for modeling these models. For an overview of process notations see [13]. A process model can be seen as an abstraction of how work is done in a specific business. A process model can be discovered from process data by applying some control-flow algorithm.
A control-flow algorithm is a process discovery technique that can be used for translating the process behavior described in an event log into a process model. These algorithms may be driven by different discovery strategies and provide different functionalities. Also, the execution of a control-flow algorithm may be constrained (controlled) by some parameters.
Definition 2 (Algorithm). Let L be an event log, P a list of parameters, and R a process model. An (control-flow) algorithm A is defined as a function f A : (L, P ) → R that represents in R the process behavior described in L, and it is constrained by P . The execution of f A is designated as a discovery experiment.
A measure can be defined as a measurement that evaluates the quality of the result of an (control-flow) algorithm. A measure can be categorized as follows [13].
Simplicity measure: quantifies the results of an algorithm (i.e., a process model mined from a specific event log) in terms of readability and comprehension.
The number of elements in the model is an example of a simplicity measure. Fitness measure: quantifies how much behavior described in the log complies with the behavior represented in the process model. The fitness is 100% if the model can describe every trace in the log. Precision measure: quantifies how much behavior represented in the process model is described in the log. The precision is 100% if the log contains every possible trace represented in the model. Generalization measure: quantifies the degree of abstraction beyond observed behavior, i.e., a general model will accept not only traces in the log, but some others that generalize these.
Definition 3 (Measure). Let R be a process model and L an event log. A measure M is defined by a function g M : (R) → R that quantifies the quality of R, or a function g M : (R, L) → R that quantifies the quality of R according to L.
The execution of g M is designated as a conformance experiment.
Given an event log L, a control-flow algorithm A constrained by the list of pa-
, and a quality measure M : Assess the impact of each parameter p ∈ P on the result of the execution of A over L, according to M .
The Elementary Effect (EE) method [8,4,5] is a technique for sensibility analysis that can be applied to identify non-influential parameters of control-flow algorithms, which usually are computationally costly for estimating other sensitivity analysis measures (e.g., variance-based measures). Rather than quantifying the exact importance of parameters, the EE method provides insight into the contribution of parameters to the results quality.
One of the most efficient EE methods is based on Sobol quasi-random numbers [12] and a radial OAT strategy [5]. 2 The main idea is to analyze the parameter space by performing experiments and assessing the impact of changing parameters with respect to the results quality. A Sobol quasi-random generator is used to determine a uniformly distributed set of points in the parameter space. Radial OAT experiments [5] are executed over the generated points to measure the impact of the parameters. This information can be used either (i) to guide on the parameters setup by prioritizing the parameters to be tuned, or (ii) as a first step towards parameter optimization.
In this paper, an OAT experiment consists of a benchmark of some control-flow algorithm where the algorithm's parameters are assessed one at a time according to some quality measure. This means that k + 1 discovery and conformance experiments are conducted, the first to set a reference and the last k to compare the impact of changing one of the k algorithm's parameters. The parameter settings for establishing the reference and changing the parameter's values are defined by a pair of points from the parameter space. OAT experiments can use different strategies to explore these points. Figure 1 presents the most common strategies for performing OAT experiments. In the trajectory design, the parameter change compares to the point of the previous experiment. In the radial design, the parameter change compares always to the initial point. From these two, the radial design has been proven to outperform the trajectory one [10].
Radial OAT experiments can be defined as follows. First, a pair of points (α, β) is selected in the parameter space. Point α, the base point (point (1, 1, 2) in Figure 1), is used as the reference parameter setting of the experiment. A discovery and conformance experiment is executed with this parameters setting to set the reference quality value. Point β, the auxiliary point (point (2, 2, 0) in Figure 1), is used to compare the impact of changing the parameters, one at a time, from α to β. For each parameter p i ∈ P , a discovery and conformance experiment is executed using the parameter values defined by α for a parameter p j ∈ P ∧ p j = p i and the parameter value defined by β for p i (see the example in Figure 1b). Insight into the impact of each parameter is provided by aggregating the results of the radial OAT experiments.
Let A be a control-flow algorithm, M a given measure, and L an event log. The function f A•M (L, P ) computes the quality of the result of A over L with respect to M , where
2 OAT stands for One (factor) At a Time. The elementary effect of a parameter p i ∈ P on a radial OAT experiment is defined by
where α, β are parameter settings of P (the base and auxiliary points), α i and β i are the i th elements of α and β, and
where α is α with β i replacing α i . The measure µ for p i is defined by
where r is the number of radial OAT experiments to be executed, typically between 10 and 50 [4]. The total number of discovery and conformance experiments is r(k + 1), where k is the number of parameters of A.
The impact of a parameter p i ∈ P is given as the relative value of µ i compared to that for the other parameters of P . A parameter p j ∈ P (j = i) is considered to have more impact on the results quality than p i if µ j > µ i . The parameters p j and p i are considered to have equal impact on the results quality if µ j = µ i . The parameter p i is considered to have no impact on the results quality if µ i = 0. This measure is sufficient to provide a reliable ranking of the parameters [4,5].
Sobol quasi-random numbers (or sequences) are low-discrepancy sequences that can be used to distribute uniformly a set of points over a multidimensional space. These sequences are defined by n points with m dimensions. Table 1 1: The first ten points of a ten-dimensional Sobol quasi-random sequence.
Each element of a point of a Sobol sequence consists of a numerical value between zero and one (e.g., the element representing the second dimension (d 2 ) of point x 5 is 0.8750). A collection of these values (the entire point or part of it) may be used to identify a specific point in a parameter space. An element of a point of a Sobol sequence can be converted into a parameter value by some normalization process. For instance, a possible normalization process for an element e ∈ [0, 1] to one of the n distinct values of some discrete parameter p can be defined by e × n , which identifies the index of the parameter value in p corresponding to e. Notice that the parameter space must be uniformly mapped by the normalization process (e.g., each value of a Boolean parameter must be represented by 50% of all possible elements).
Using the approach proposed in [5], a matrix of quasi-random Sobol numbers of dimensions (r + 4,2k) can be used to analyze the elementary effects of the k parameters of a control-flow algorithm by executing r radial OAT experiments. The first k dimensions of the matrix's points define the base points, while the last k dimensions define the auxiliary points. Given that the first points of a Sobol sequence have the tendency to provide similar base and auxiliary points, it is identified in [5] the need of discarding the first four points of the sequence for the auxiliary points (i.e., the k rightmost columns should be shifted upward). Therefore, the base and auxiliary points can be computed from a Sobol sequence as follows. Let e j i be the element corresponding to the j th dimension (d j ) of the i th point (x i ) of the sequence. The i th base (α i ) and auxiliary (β i ) points are defined as following.
i , e 2 i , ..., e j i ) and β i = (e j+1 i+4 , e j+2 i+4 , ..., e 2j i+4 ).
(4)
The following example is used to illustrate the analysis of the parameter space of an algorithm in order to assess the impact of the algorithm's parameters on the results quality. Let us consider an event log that is characterized by two distinct traces: ABDEG and ACDF G. The frequency of any of these traces is high enough to not be considered as noise. The behavior described by these traces does not contain any kind of loop or parallelism, but it does contain two long-distance dependencies: B ⇒ E and C ⇒ F . Let us also consider the Flexible Heuristics Miner (FHM) [17] as the control-flow algorithm to explore the parameter space in order to assess the impact of the FHM's parameters on the results quality. The parameters of the FHM are summarized in Table 2. Notice that every parameter of the FHM is continuous, with a range between zero and one. The relative-to-best and the long-distance thresholds are optional. The former is only considered with the all-tasks-connected heuristic. The latter is only taken into account when the long-distance dependencies option is activated.
The parameters of the Flexible Heuristics Miner [17].
Figure 2 presents the two possible process models that can be mined with the FHM on the aforementioned event log, using all combinations of parameter values. Figure 2a shows the resulting Causal net where long-distance dependencies are not taken into account. Figure 2b shows the resulting Causal net with the long-distance dependencies. Notice that, depending on the quality measure, the quality of these process models may differ (e.g., the precision of the model with long-distance dependencies is higher than the other one). One may be interested on the exploration of the FHM's parameter space to get the process model that fulfills best some quality requirements.
The analysis of the parameter space of the FHM starts with the generation of the Sobol numbers. Let us consider that, for this analysis, one wants to execute r = 30 radial OAT experiments for assessing the elementary effects of the k = 5 FHM's parameters. So, a matrix of Sobol numbers of dimensions (30 + 4,2 × 5) has to be generated (cf. Section 4.2). Table 1 shows the first ten points of this matrix. Table 3 presents the first five base and auxiliary points as well as the parameter values corresponding to these points. Notice that the parameters are represented in the points according to the same ordering in Table 2 (i.e., the first element of a point represents the first parameter and so on). The normalization Fig. 2: The process models that can be mined with the FHM.
process in this example is defined as follows. For the non-optional parameters (cf. Table 2), an element e ∈ [0, 1] of a point of a Sobol sequence can be directly used to represent the value of the parameter. For the optional parameters, an element e ∈ [0, 1] of a point of a Sobol sequence is normalized to a value e ∈ [0, 2], which maps the parameter space uniformly (i.e., the value of the parameter and whether or not the parameter is enabled). If e ≤ 1 then e is assigned as the value of the parameter; the parameter is disabled otherwise. 3) as well as the result of the execution of f A•M (L, P ) and the elementary effect EE for each parameter. For executing f A•M (L, P ), A is the FHM, M the Node Arc Degree measure 3 , and L the aforementioned event log. The elementary effects are computed as described in Section 4. 1. 4 Notice that the elementary effect of a parameter can only be computed when the base and auxiliary points provide distinct parameter values (e.g., in Table 4, the first parameter is not assessed because it is disabled in both base and auxiliary points). 4: Radial sampling for the first radial OAT experiment. The first line corresponds to the base point, while the others consist of the base point in which the element regarding a specific parameter is replaced by that from the auxiliary point; the underlined values identify the replaced element and the parameter being assessed.
Table 5 presents the results of the analysis of the FHM's parameter space. The results identify the long-distance threshold as the only parameter to take into account for the parameter exploration. As expected, all other parameters have no impact on the results quality. This is explained by the fact that the log does not contain any kind of loop or noise. Notice that the µ absolute value does not provide any insight into how much a parameter influences the results quality. Instead, the µ measurement provides insight into the impact of a parameter on the results quality, compared to others.
Dependency Threshold 0.0 Relative-to-best Threshold 0.0 Length-one-loops Threshold 0.0 Length-two-loops Threshold 0.0 Long-distance Threshold 0.113 Table 5: The µ values of the FHM's parameters. 3 The Node Arc Degree measure consists of the average of incoming and outgoing arcs of every node of the process model. 4 For computing EEi, αi − βi is considered to be 1 when the parameter is changed from a disabled to an enabled state, or the other way around (e.g., the last parameter in Table 4).
most efficient form of assessing the impact of a parameter, with the method presented in this paper as a baseline. Second, we will try to incorporate the methodology described in this paper in the RS4PD, a recommender system for process discovery [9]. Finally, the application of the presented method with other goals, e.g., estimating the representational bias of control-flow discovery algorithms may be explored.
Acknowledgments. This work as been partially supported by funds from the Spanish Ministry for Economy and Competitiveness (MINECO) and the European Union (FEDER funds) under grant COMMAS (ref. TIN2013-46181-C2-1-R).
The EE method presented in the previous section can be applied to any controlflow algorithm constrained by many parameters, using some event log and a measure capable of quantifying the quality of the result of the algorithm. The presented method can be easily implemented on some framework capable of executing discovery and conformance experiments (e.g., ProM [15] or CoBeFra [14]). Several open-source generators of Sobol numbers are available on the web.
The computational cost of our approach can be defined as follows. Let L be an event log, A a control-flow algorithm constrained by the list of parameters
and M a quality measure. The computational cost of a discovery experiment using A (with some parameter setting) over L is given by C D . Considering R as the result of a discovery experiment, the computational cost of a conformance experiment over R and L (or just R) with regard to M is given by C C . Therefore, the computational cost of a radial OAT experiment is given by
where k is the number of parameters of A. The computational cost of the EE method based on r radial OAT experiments is given by C = r(k + 1)(C D + C C ).
Considering that both discovery and conformance experiments may be computationally costly, performance may become a critical issue for the application of this method. This issue can be partially addressed by identifying a set of potentially irrelevant parameters, and considering those parameters as a group. Then, by adjusting the µ measurement to work with groups of two or more parameters [4], the group of parameters can be analyzed together using radial experiments that iterate over all elements of the same group simultaneously.
Suppose, for instance, that it is known that a given log does not have loops. So, for the FHM's parameters, the length-one-loops and length-two-loops thresholds may be grouped in order to avoid the execution of discovery and conformance experiments that are not relevant for the analysis. Recalling the example presented in Section 4.3, the radial experiments will iterate over one group of two parameters and three indepedent parameters (i.e., the dependency, the relative-to-best, and the long-distance thresholds). This means that, for the group of parameters, all elements of the same group are replaced simultaneously by the corresponding elements from the auxiliary point. Table 6 presents the adjusted radial sampling presented in Table 4. The first line corresponds to the base point, while the others consist of the base point in which the element(s) regarding a specific parameter (or group of parameters) is replaced by that from the auxiliary point; the underlined values identify the replaced element(s) and the parameter (or group of parameters) being assessed.
(-, 0.50, 0.50, 0.50, -) (-, 0.50, 0.50, 0.50, -) (-, 0.88, 0.50, 0.50, -) (-, 0.50, 0.38, 0.38, -) (-, 0.50, 0.50, 0.50, 0.25) Table 6: Radial sampling for the first radial experiment considering a group of parameters.
The elementary effect of a group of parameters G ⊆ P on a radial experiment is defined by
where α, β are parameter settings of P (the base and auxiliary points), α G and β G are the elements of G in α and β, and
The function dist(A, B) computes the distance between A and B (e.g., the Euclidean distance). The measure µ for G is defined by
where r is the number of radial experiments to be executed. The total number of discovery and conformance experiments depends on the number of groups and independent parameters being assessed.
To the best of our knowledge, this work is the first in presenting a methodology to assess the impact of parameters in control-flow discovery algorithms. The method relies on a modern sensitivity analysis technique that requires considerably less exploration than traditional ones such as genetic algorithms or variance-based methods.
In this work, we have applied the methodology on the Flexible Heuristics Miner algorithm using 13 event logs. The results suggest the effectiveness of the method. We have noticed that simple conformance measures (and, thus, less computationally costly) are as good as any other complex measure for assessing the parameters influence. Nevertheless, we acknowledge that more experiments are necessary to get a better insight.
Future work is mainly oriented towards addressing three aspects, which are mainly addressed to apply the method of this paper to other control-flow algorithms. First, we are interested in the algorithmic perspective in order to study the