Given an event log L, a control- ow discovery algorithm f , and a quality metric m, this paper faces the following problem: what are the parameters in f that mostly in uence its application in terms of m when applied to L? This paper proposes a method to solve this problem, based on sensitivity analysis, a theory which has been successfully applied in other areas. Clearly, a satisfactory solution to this problem will be crucial to bridge the gap between process discovery algorithms and nal users. Additionally, recommendation techniques and meta-techniques like determining the representational bias of an algorithm may bene t from solutions to the problem considered in this paper. The method has been evaluated over a set of logs and the exible heuristic miner, and the preliminary results witness the applicability of the general framework described in this paper.
Control- ow discovery is considered as one of the crucial features of Process
Mining [
There are many factors that may hamper the applicability of a control- ow 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- ow 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 di erent scenarios) are not appropriate for the log at hand. In that case, the user is left alone in the task of con guring 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- ow discovery algorithms. In our approach, we use an e cient 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- ow 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 in uence (by assigning meaningful values to these
parameters) the discovery experiment.
(B) As an aid for recommending control- ow discovery algorithms: current
recommendation systems for control- ow process discovery (e.g., [
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 de nitions. 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. 2
The selection of parameters for executing control- ow algorithms is usually a challenging issue. The uncertainty of the inputs, the lack of information about parameters, the diversity of outputs (i.e., the di erent process model types), and the di culty of choosing a comprehensive quality measurement for assessing the output of a control- ow algorithm make the selection of parameters a di cult task.
The parameter optimization is one of the most e ective approaches for
parameter selection. In this approach, the parameter space is searched in order to nd
the best parameters setting with respect to a speci c 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 [
A di erent approach, which may also be used to facilitate the parameter
optimization, is known as sensibility analysis [
This section contains the main de nitions used in this paper. 3.1
Process data describe the execution of the di erent 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).
De nition 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 2 T a process instance. An event log L is a set of process instances, i.e., L 2 P(T ).1
A 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 [
A control- ow 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 di erent discovery strategies and provide di erent functionalities. Also, the execution of a control- ow algorithm may be constrained (controlled) by some parameters. 1 P(X) denotes the powerset of some set X. De nition 2 (Algorithm). Let L be an event log, P a list of parameters, and R a process model. An (control- ow) algorithm A is de ned 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. 3.3
A measure can be de ned as a measurement that evaluates the quality of the result
of an (control- ow) algorithm. A measure can be categorized as follows [
The number of elements in the model is an example of a simplicity measure. Fitness measure: quanti es how much behavior described in the log complies with the behavior represented in the process model. The tness is 100% if the model can describe every trace in the log.
Precision measure: quanti es 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: quanti es 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.
De nition 3 (Measure). Let R be a process model and L an event log. A measure M is de ned by { a function gM : (R) ! { a function gM : (R; L) !
R that quanti es the quality of R, or
R that quanti es the quality of R according to L.
The execution of gM is designated as a conformance experiment. 3.4
Given an event log L, a control- ow algorithm A constrained by the list of parameters P = [p1 = v1; :::; pk = vk], and a quality measure M : Assess the impact of each parameter p 2 P on the result of the execution of A over L, according to M . 4
The Elementary E ect (EE) method [
One of the most e cient EE methods is based on Sobol quasi-random
numbers [
In this paper, an OAT experiment consists of a benchmark of some control- ow
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 rst 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 de ned by
a pair of points from the parameter space. OAT experiments can use di erent
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 [
Radial OAT experiments can be de ned 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 pi 2 P , a discovery and conformance experiment is executed using the parameter values de ned by for a parameter pj 2 P ^ pj 6= pi and the parameter value de ned by for pi (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- ow 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 P = [p1 = v1; :::; pk = vk] is the list of parameters of A. if M does not depend on a log (1) : gM (f A(L; P ); L) otherwise 2 OAT stands for One (factor) At a Time. (1,1,2) (2,2,0) (2,1,2) (2,1,0) (1,2,2) (1,1,2) (1,1,0) (2,1,2) p3 p1
p3 (a) Trajectory. (b) Radial.
The elementary e ect of a parameter pi 2 P on a radial OAT experiment is de ned by
EEi = where ; are parameter settings of P (the base and auxiliary points), i and i are the ith elements of and , and f A M (L; - i i) is the function f A M (L; 0) where 0 is with i replacing i. The measure ? for pi is de ned by i? =
Pr
j=1 jEEij
r
;
where r is the number of radial OAT experiments to be executed, typically between
10 and 50 [
The impact of a parameter pi 2 P is given as the relative value of i? compared
to that for the other parameters of P . A parameter pj 2 P (j 6= i) is considered
tpoj hanavdepmiaorree cimonpsaidcteroend tthoehraevseuletqsuqaul ailmitpyatchtaonnptihief rej?su>lts qi?u.aTlihtye pifaraj?m=eteri?s.
The parameter pi is considered to have no impact on the results quality if i? = 0.
This measure is su cient to provide a reliable ranking of the parameters [
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 de ned by n points with m dimensions. Table 1 presents an example of a Sobol sequence containing ten points with ten dimensions.
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 (d2) of point x5 is 0:8750). A collection of these values (the entire point or part of it) may be used to identify a speci c 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 2 [0; 1] to one of the n distinct values of some discrete parameter p can be de ned by be nc, which identi es 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 [
i = (ei1; ei2; :::; eij ) and i = (eij++41; eij++42; :::; ei2+j4): (4) 4.3
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) [
Relative-to-best Threshold Dependency Threshold Length-one-loops Threshold Length-two-loops Threshold Long-distance Threshold
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 di er (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 ful lls 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 e ects 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 rst ten points of this matrix. Table 3 presents the rst ve 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 rst element of a point represents the rst parameter and so on). The normalization (a) The Causal net without long-distance (b) The Causal net with long-distance dedependency relations. pendency relations. process in this example is de ned as follows. For the non-optional parameters (cf. Table 2), an element e 2 [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 2 [0; 1] of a point of a Sobol sequence is normalized to a value e0 2 [0; 2], which maps the parameter space uniformly (i.e., the value of the parameter and whether or not the parameter is enabled). If e0 1 then e0 is assigned as the value of the parameter; the parameter is disabled otherwise.
FHM, M the Node Arc Degree measure3, and L the aforementioned event log. The elementary e ects are computed as described in Section 4.1.4 Notice that the elementary e ect of a parameter can only be computed when the base and auxiliary points provide distinct parameter values (e.g., in Table 4, the rst parameter is not assessed because it is disabled in both base and auxiliary points).
P
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 in uences the results quality. Instead, the ? measurement provides insight into the impact of a parameter on the results quality, compared to others. 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).
The EE method presented in the previous section can be applied to any
controlow 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 [
The computational cost of our approach can be de ned as follows. Let L be an event log, A a control- ow algorithm constrained by the list of parameters P = [p1 = v1; :::; pk = vk], and M a quality measure. The computational cost of a discovery experiment using A (with some parameter setting) over L is given by CD. 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 CC . Therefore, the computational cost of a radial OAT experiment is given by CE = (k + 1)(CD + CC ), 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)(CD + CC ). 5.1
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 [
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 rst line corresponds to the base point, while the others consist of the base point in which the element(s) regarding a speci c 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.
where ; are parameter settings of P (the base and auxiliary points), G and
G are the elements of G in and , and f A M (L; - G G) is the function f A M (L; 0) where 0 is with G replacing G. The function dist(A; B) computes the distance between A and B (e.g., the Euclidean distance). The measure ? for G is de ned by ?G =
Pr j=1 jEEGj r ; 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. 6
To the best of our knowledge, this work is the rst in presenting a methodology to assess the impact of parameters in control- ow 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 e ectiveness 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 in uence. 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- ow
algorithms. First, we are interested in the algorithmic perspective in order to study the
(5)
(6)
most e cient 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 [
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).