Revealing the Importance of Setting Parameters in Declarative Discovery Algorithms: An Evolutionary-Based Methodology

Revealing the Importance of Setting Parameters in Declarative Discovery Algorithms: An Evolutionary-Based Methodology Vanessa Pradas Fernández , Ángel Jesús Varela-Vaca , and María Teresa Gómez-López(B) University of Seville, IDEA Research Group, Seville, Spain {vpradas,ajvarela,maytegomez}@us.es https://www.idea.us.es Abstract. Through constraints, declarative process models represent the permitted behaviour associated with a business process, by limiting the potential correct traces. These models can be discovered by analysing an event log. However, various declarative business models can be extracted from a single event log, depending on the desirable level of metrics, such as fitness and generalisation. Existing discovery algorithms enable the type of discovered declarative process model to be customised through a set of configuration parameters. Depending on the values of these parameters, the discovered process can be of high or low quality. Unfortunately, the high number of combinatorial parameters and the high time consumption of process discovery make it impractical to conduct an exhaustive analysis of the configuration parameters to determine the most suitable declarative process model discovered. As a solution, we propose a methodology supported by an implemented framework that uses evolutionary algorithms to reduce computational complexity and to select the highest quality declarative business processes. An experiment is included to show the feasibility of our proposal. Keywords: Process mining ·Declarative process model discovery · Evolutionary algorithms 1 Introduction Process mining [1] is a discipline aimed at creating a union between data mining and business process management. By combining model-based process analysis and data-driven analysis techniques to better understand business performance. Although this discipline encompasses three subareas (discovery, enhancement, and conformance checking), in this paper, we focus on process discovery. Process discovery aims to produce process models from a given event log. An event log represents the execution traces for a business process, including the timestamp of when the activities are executed. Process discovery algorithms can be orientated c The Author(s) M. Indulska et al. (Eds.): CAiSE 2023, LNCS 13901, pp. 158–173, 2023. https://doi.org/10.1007/978-3-031-34560-9_10 Revealing Setting Parameters in Declarative Discovery Algorithms 159 to obtain imperative or declarative models. An imperative process model explicitly describes the acceptable behaviour of the process with regard to control-flow patterns, whereas a declarative process model is used in environments of a more flexible nature where constraints limit undesirable traces. The use of declarative models takes place when the precise order of the activities remains unknown, although there are certain constraints between the different activities. Since any behaviour that is not explicitly prohibited by such constraints is assumed to be allowed, the number of possible discovered models can be vast. Existing declarative discovery algorithms [25] take an event log and a set of configuration parameters to discover a process model. The nature of these configuration parameters varies depending on the characteristics of the algorithm employed, such as the maximum branching level for discovered constraints and the minimum confidence level threshold required to consider a discovered constraint as significant; in this respect, different settings of these parameters can discover a variety of process models that differ from each other in terms of multiple aspects (metrics), although a number thereof can optimise major quality metrics according to user requirements [5]. However, to obtain these optimal models, it is necessary to explore the entire domain space to set the configuration parameters [3]; furthermore, it is impossible to previously ascertain the characteristics of the process models generated by these parameters. Moreover, this search for the setting that produces the most suitable process models could require excessive computational resources and time. Given this situation, we propose tackling three main research questions. –RQ1: How can we handle the computational complexity of exploring the entire domain space of configuration parameters for discovery algorithms? Configuration parameters can take hundreds of thousands of possible values. It is even more difficult since the domain of the parameters can be real-valued, which would make it necessary to discretise the possible values evaluated or divide them into segments. –RQ2: What is/are ‘the best’ process model(s) discovered? According to the configuration parameters, one or a subset thereof can be chosen as the most suitable. One process model can be better than another, for example, when one optimises the fitting or another optimises the simplicity. This means that several models can be ‘the best’, since multiple objectives can be taken into account. –RQ3: How can we face (dis)similarity in process models to select the most representative in a set? Many of the discovered processes can be very similar, as there are numerous parameter configurations that generate small changes. It is impossible to present all of them as a solution, although they can be optimal yet slightly different. To face these challenges, we propose the Selevminer methodology which is supported by an implemented framework that includes the following: – Related to RQ1, we propose combining the discovery of the declarative process with evolutionary algorithms to reduce the evaluation of the setting of every configuration parameter. 160 V. P. Fernández et al. – Related to RQ2, we include a multi-objective optimisation algorithm in order to obtain a Pareto front with the process models that optimise a set of quality metrics. – Related to RQ3, we propose including clustering techniques to select the canonical representative solutions by obtaining a set of non-similar process models. The rest of this paper is organised as follows: Sect. 2presents the fundamentals for understanding the paper. Section 3describes the details of the approach. Section 4contains the experiments carried out and the analysis of the results. Section 5analyses related work in the area. Finally, Sect. 6summarises several conclusions and presents various lines of research. 2 Preliminaries Declarative processes describe permissible and prohibited actions in a business process. Declarative models enable the specification of what is to be performed in a business process, instead of how it must be performed [17]. These are described by a set of activities and constraints between them, for example, “Activity B cannot be executed before activity A”, and “if A is executed, B must be executed later”. This example supports various traces where A and/or B can or cannot be executed. An example of a declarative process model is given in Fig. 1.Thereare multiple examples of constraints in the figure, e.g., the precedence between order and accepted activities, or the cardinality ‘0..1’ on accepted that indicates that it can execute at most once. Derived from the flexibility of declarative models, various models can represent the same trace of events. Fig. 1. A book-purchase process modelled in Declare [18]. From a process modelling perspective, imperative models should be completely known and specified at design time, since they explicitly represent the allowed sequences of activities. However, declarative models describe which orders of activities are permitted in an open-world assumption (everything that is not explicitly specified is permitted). For example, if activity A is executed, activity B has to be executed afterwards, and, as long as this rule is satisfied, any behaviour is allowed. Several languages are proposed in the literature to describe declarative processes, such as the Compliance Rule Graph [10], EM-BrA2CE [8], Declare [19]. Revealing Setting Parameters in Declarative Discovery Algorithms 161 In an equivalent way to which Process Mining techniques are defined for imperative models, they can be used for declarative models [1]. Stated earlier, our focus is on process discovery, a paradigm that aims to create a process model through the analysis of event logs, but that has to date focused mainly on imperative process models [1]. Declarative process discovery [13,25] has also been consolidated as a mature discipline in the Process Mining arena. In this respect, there exist a plethora of techniques, approaches, and tools in the literature, such as Declare Miner [12], MINERful [4], HeuristicMiner [15], ILP Miner [9], AGNEsMiner [7], DisCoveR [2], and DeciClareMiner [16]. Depending on the algorithm used and the parameters settings, a variety of process models can be discovered, which can be measured using quality metrics. Typical measurements related to control flow include those of simplicity, fitness, precision, and generalisation, although several metrics can also be extracted, such as density, cyclic number, coefficient of connectivity, and control flow complexity [20] by conducting the possible process discovery algorithms. 3 Selevminer: An Evolutionary-Based Methodology to Discover Optimal Declarative Process Models We present Selevminer as a methodology for discovering optimal declarative processes that evaluate the possible configuration parameters used in the discovering algorithms. Optimisation is based on a multi-objective function that integrates a set of quality metrics of the discovered processes. The Selevminer workflow (shown in Fig. 2) is aligned with the three research queries presented: discover various declarative processes to configure the input parameters; extract the optimal solution based on a multi-objective solution; and apply clustering techniques to ascertain the representative solutions from among all the potential solutions. This methodology combines a multi-objective optimisation algorithm (in particular, evolutionary algorithms), a declarative process discovery algorithm, a clustering algorithm, and a selection algorithm. Furthermore, to support this methodology, we provide a framework developed for the community at https:// doi.org/10.5281/zenodo.7730789. In the following, each research query is related to Selevminer’s task devoted to it’s solution. 1. Discover and Measure models: Given an event log and the set of configuration parameters that are used as input in the discovery algorithms, this task performs a discovery algorithm to obtain a declarative process model based on the configuration parameters. The discovered model must be measured in terms of a set of quality metrics defined by a user in order to ascertain where a discovered process is better or worse than another. This task is crucial for the handling of RQ1 and RQ2 concerning the models discovered and for the assessment of their quality. 162 V. P. Fernández et al. Fig. 2. Selevminer workflow overview. 2. Apply multi-objective optimisation algorithm: This task aims to solve RQ1, by considerably minimising the computational complexity of the search for the configuration parameter. In order to obviate the need for the analysis of every possible configuration parameter, we propose the use of an algorithm based on a local search instead of on an exhaustive search. In this case, an evolutionary algorithm is employed that infers another setting for the configuration parameters to optimise the quality metrics during the search. This is performed as many times as the number of generations established for the evolutionary algorithm. This task answers RQ2 by generating a Pareto front of “optimal” models based on the set of quality metrics. 3. Cluster models: This task applies a clustering technique to the process models that belong to Pareto front solutions, to reduce the number of similar solutions obtained in response to RQ3. In this way, similar redundant results are avoided and a set of models that can be assumed by a user is obtained. 4. Select canonical models: Since the ultimate goal of Selevminer is to obtain a set of models, a canonical model from each cluster is selected and returned as a result. This task strives to respond to RQ3. 3.1 Discovering and Measuring Declarative Process Models A fundamental aspect of any discovery approach is the event log used. An event log can be seen as a collection of cases, where a case is a sequence of events. Any event can contain multiple attributes, such as the identifier of the activity that produces it and the timestamp when the event occurred. Different processes can be discovered even when utilising the same event log and the same discovery algorithm, depending on the configuration parameters employed. In general, a set of configuration parameters {p0,p 1,...,p n}is used as input to a discovery algorithm to customise the features of the obtained business process. Revealing Setting Parameters in Declarative Discovery Algorithms 163 These parameters are usually Float, Integer (that can be bounded), and Boolean values. There are various algorithms for discovering declarative business processes, such as Declare Miner [14] and UnconstrainedMiner [30]. In Selevminer, we incorporate MINERful [4] because, based on the analysis performed in [4], its performance scales better than other proposals with respect to the number of traces, the length of traces, and the number of activities of the process. In addition, MINERful includes various configuration parameters. We may consider the maximum branching level for discovered constraints, the minimum confidence level threshold required to consider a discovered constraint significant, the hiding of redundant or inconsistent constraints, and the minimum interest factor threshold required for a discovered constraint to be considered significant. Once the discovery process is complete and the process models are obtained, a set of quality metrics is measured, that is, {q1,...,q m}. A wide range of metrics can be found in the literature [21], such as the number of states, transitions, and constraints. Slightly more advanced metrics include the coefficient of connectivity, the ratio of states to transitions, and the cyclomatic complexity. More robust in nature are the dimensions of process mining, that is, precision, fitness, simplicity, and generalisation. It should be borne in mind to note that the desired value of each metric can be maximised or minimised, depending on the case. 3.2 Apply Multi-objective Optimisation Algorithms The use of several metrics to evaluate the discovered declarative process calls for the definition of a multi-objective function for the optimisation. From our point of view, no metric is more important than another, and hence no special weights have been associated with each partial objective. However, as explained above, the metrics could be maximised or minimised. In a multi-objective optimisation where not all objectives can be optimised at the same time, the Pareto optimal solutions are usually employed. The well-known Pareto front describes a set of solutions as the best according to a multi-objective function if no solution improves in any of the objectives without degrading at least one of the others. Whenever there are nfunctions the so-called Pareto front,fi,mustbe found, which is a set containing all the solutions to the optimisation problems given by any function. In our approach, the discovery algorithm is performed iteratively until the best possible result is obtained for the quality metrics, by changing the setting of the configuration parameter values in each execution. When the latter has been achieved, the Pareto front is generated from the values they provide. In order to obviate the need to study every possible combination of the configuration parameters, which can imply an untractable problem, we propose the use of a local search algorithm. There is a wide range of local search algorithms, such as Simulated Annealing, Local Beam Search, Genetic, and Hill-climbing Search [26]. In our solution, genetic algorithms are applied because this is a mature area used in several scenarios. Furthermore, the similarity between the set of metrics to be improved and the chromosomes used has made it easier to 164 V. P. Fernández et al. develop. In particular, we have used the evolutionary algorithm of NSGA-II [6], which is an extended algorithm utilised to solve multi-objective optimisation problems by finding multiple Pareto solutions. Selevminer works on populations of numerical chromosomes of size n,wherenis the number of configuration parameters used as input in the MINERful discovery algorithm. These chromosomes use this discovery algorithm when calculating fitness, which is the m different quality metrics predefined by the user before execution. With respect to these metrics, it is important to note that they depend on the output used (finite-state machines, in the case of MINERful). Therefore, given quality metrics {q1,...,q m},thefitness of a chromosome c would be calculated as the tuple (c, {q1,q 2,...,q m}). All these quality metrics, some of which may be opposed to each other, are those that the algorithm strives to optimise over the generations specified as input variables. For the current implementation, declarative process models have been analysed in the form of declarative finite state machines where activities, constraints and cardinalities are mapped to states, transitions and guards1respectively. Then, the quality metrics are related to the number of states, the ratio of states to transitions, the cyclomatic complexity, and the number of transition guards (i.e., choice conditions to split or join paths between states). The objective is to minimise all of these metrics. The output of this multi-objective optimisation algorithm is an approximation of the Pareto front for the given metrics with as many points as the number of elements in the population. Normally, this final number of elements should be and is too large to deal with manually, since evolutionary algorithms require a large population to converge quickly. Our approach proposes solving it by using clustering techniques, as explained in the following section. 3.3 Cluster Models Different configuration parameters can discover very similar declarative process models, where some parameters optimise certain metrics but not others. The number of solutions obtained as a Pareto front is often too large for a human to analyse. Additionally, the process models obtained can be very similar and can hinder the subsequent analysis carried out by the expert. For this reason, we propose the creation of clusters with the found solutions, where each cluster gathers similar declarative models. We propose the selection of one model of each cluster as a representative thereof. Cluster analysis measures the similarity between elements, by creating clusters with those that have similar characteristics. To this end, a clustering algorithm has been proposed to reduce the number of optimal discovered models returned. All clustering techniques require a distance metric between the elements that make up the clusters; our approach proposes using a metric based on Manhattan Distance between the quality metrics of the models. Other distance metrics could be used if necessary, but this is the most efficient and the easiest to interpret. 1Conditions allow transitions to occur only under specific circumstances. Revealing Setting Parameters in Declarative Discovery Algorithms 165 The algorithm that has been employed to apply clustering in Selevminer is Single-Linkage Agglomerative Clustering: a hierarchical clustering technique of extended use. This is a computationally efficient algorithm that can be applied to large datasets. It starts with one cluster for each of the elements and gradually merges the clusters using a distance metric between them. Thus, it only needs the calculation of the distance between the two closest objects or clusters at each step, which can be very efficient. The two clusters closest to each other are unified in each iteration until the desired number of clusters is found. This raises the question of which particular algorithm has been employed to define the distance between clusters in process models, since there are several alternatives. In that case, the selected algorithm is the average distance between all the elements of the first cluster (cl1) and all the elements of the second cluster (cl2). clusterdist(cl1,cl 2)= 1 |cl1|·|cl2|·a∈cl1b∈cl2dist(a, b)(1) 3.4 Selection of Canonical Models The obtained clusters can include a high number of declarative models, which can be very similar. To tackle this issue, a selection algorithm is proposed that consists of selecting one element from each cluster to return, under the assumption that this element subsumes all the others in the cluster. Therefore, this element can be understood as representative canonical process model. In our approach, assumptions cannot be made regarding the structure of the data, since these could be incorrect; therefore, the approach currently implemented in Selevminer would be random selection. Based on the heuristic that the clustering algorithm uses, this is responsible for grouping the most similar models according to their metrics. 4 Experimentation In this section, we intend to demonstrate the feasibility of our implementation of the Selevminer methodology. To this end, an exhaustive analysis of the configuration parameters was conducted to compare our solution, by using various event logs from the literature. 4.1 Experimental Settings Since there is more than one metric to optimise in the discovered processes, various processes can be chosen as the most feasible. For this reason, we propose the Pareto front as a reference to manage optimisation with multiple objectives. More similar to the exhaustive solutions are those found with Selevminer, better than our solution. To obtain every best solution: (1) every possible process model has been discovered for all combinations for the five configuration parameters by using MINERful; and (2) the optimal front (with non-dominated solutions) 166 V. P. Fernández et al. has been chosen, which are the set of the discovered models with the optimised metric. Note that the optimal front obtained exhaustively does not necessarily correspond to the Pareto front of the possible models, since the granularity of the partitions in which Float parameters are discretised, the timeout, and the computational power of the systems used may cause certain models not to be discovered. However, it should be noted that the non-dominated solutions would correspond to the current Pareto front, in the case where all possible models in the event log are discovered. This cannot be assured in any simple way, and hence partitions are as small as possible, without excessively compromising performance. Once this front is obtained, several Selevminer executions are performed with different numbers of configurations as population, to compare their discovered models with the optimal solutions obtained by the exhaustive solution. This answers the question of whether this new approach is capable of generating satisfactory results in a significantly shorter time. The following MINERful parameters have been set in the implementation of the exhaustive discovery: (MBL) the maximum branching level for discovered constraints; (MCL) the minimum confidence level threshold required for a discovered constraint to be considered as meaningful; (HRIC) the hiding of redundant or inconsistent constraints; (MIF) the minimum interest factor threshold required for a discovered constraint to be considered as meaningful; and (MST) the minimum support threshold required for a discovered constraint to be considered as meaningful. For each of these parameters, a partition has been made according to their nature and the range of values that they allow, in the order in which they appear in Table 1a. Given these, the total possible combinations to set the parameters are calculated from the resulting fragments as 3·21·2·21·21, resulting in 55,566 possible discovered processes. Both the exhaustive discovery and the Selevminer have been evaluated on a system with an Intel Xeon at 2.6GHz (4cores), 8GB of RAM, and a 256GB SSD disk. By running both tests on the same server, we ensure that time and computation capacity bias are eliminated. Furthermore, the event logs used to run the tests, which are provided by the Business Process Intelligence Challenges, are listed in Table 1b. In this table, it can be observed that datasets of different sizes are employed to assess how discovery time is affected. Once the exhaustive Pareto fronts and the different Selevminer solutions have been extracted, the Averaged Hausdorff Distance (AHD) [24]isemployed to check how close are the two solutions are in terms of the Manhattan distance. The result of this metric determines the effectiveness of Selevminer in converging to the optimal front provided by the exhaustive algorithm. Furthermore, the Minimum Pairwise Distance (MPD) is utilised to measure the dissimilarity between the models returned after clustering. The higher the value of this metric, the more separated the models are. Revealing Setting Parameters in Declarative Discovery Algorithms 173 16. Mertens, S., Gailly, F., Van Sassenbroeck, D., Poels, G.: Integrated declarative process and decision discovery of the emergency care process. Inf. Syst. Front. 24(1), 305–327 (2022) 17. Parody, L., Gomez-Lopez, M.T., Gasca, R.M.: Hybrid business process modeling for the optimization of outcome data. Inf. Softw. Technol. 70, 140–154 (2016) 18. Pesic, M., van der Aalst, W.M.P.: A declarative approach for flexible business processes management. In: Eder, J., Dustdar, S. (eds.) Business Process Management Workshops, pp. 169–180. Springer, Heidelberg (2006). https://doi.org/10. 1007/11837862_18 19. Pesic, M., Schonenberg, H., van der Aalst, W.M.P.: Declarative workflow. In: ter Hofstede, A.H.M., van der Aalst, W.M.P., Adams, M., Russell, N. (eds.) Modern Business Process Automation - YAWL and its Support Environment, pp. 175–201. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-03121-2_6 20. Ramos-Gutiérrez, B., Varela-Vaca, Á.J., Galindo, J.A., Gómez-López, M.T., Benavides, D.: Discovering configuration workflows from existing logs using process mining. Empir. Softw. Eng. 26(1), 1–41 (2021). https://doi.org/10.1007/s10664-020- 09911-x 21. Ramos-Gutiérrez, B., Varela-Vaca, Á.J., Ortega, F.J., Gómez-López, M.T., Wynn, M.T.: A NLP-oriented methodology to enhance event log quality. In: Augusto, A., Gill, A., Nurcan, S., Reinhartz-Berger, I., Schmidt, R., Zdravkovic, J. (eds.) BPMDS/EMMSAD -2021. LNBIP, vol. 421, pp. 19–35. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-79186-5_2 22. Ribeiro, J., Carmona, J.: A method for assessing parameter impact on control-flow discovery algorithms. In: Koutny, M., Desel, J., Kleijn, J. (eds.) Transactions on Petri Nets and Other Models of Concurrency XI. LNCS, vol. 9930, pp. 181–202. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53401-4_9 23. Ribeiro, J., Carmona, J., Mısır, M., Sebag, M.: A recommender system for process discovery. In: Sadiq, S., Soffer, P., Völzer, H. (eds.) Business Process Management, pp. 67–83. Springer International Publishing, Cham (2014). https://doi.org/10. 1007/978-3-319-10172-9_5 24. Schutze, O., Esquivel, X., Lara, A., Coello, C.A.C.: Using the averaged Hausdorff distance as a performance measure in evolutionary multiobjective optimization. IEEE Trans. Evol. Comput. 16(4), 504–522 (2012) 25. Slaats, T.: Declarative and hybrid process discovery: recent advances and open challenges. J. Data Semant. 9(1), 3–20 (2020) 26. Stützle, T.: Local search algorithms for combinatorial problems - analysis, improvements, and new applications. Ph.D. thesis, Darmstadt University of Technology, Germany (1999) 27. Tavares, G.M., Junior, S.B., Damiani, E.: Automating process discovery through meta-learning. In: Sellami, M., Ceravolo, P., Reijers, H.A., Gaaloul, W., Panetto, H. (eds.) Cooperative Information Systems, pp. 205–222. Springer International Publishing, Cham (2022). https://doi.org/10.1007/978-3-031-17834-4_12 28. Tipping, M.E., Bishop, C.M.: Mixtures of probabilistic principal component analyzers. Neural Compu. 11(2), 443–482 (1999) 29. Weijters, A.: An optimization framework for process discovery algorithms. In: Proceedings of the International Conference on Data Mining, Las Vegas, Nevada, USA (2011) 30. Westergaard, M., Stahl, C.: Leveraging super-scalarity and parallelism to provide fast declare mining without restrictions. In: Fauvet, M., van Dongen, B.F. (eds.) Proceedings of the BPM Demo sessions 2013, Beijing, China, 26–30 August 2013. CEUR Workshop Proceedings, vol. 1021. CEUR-WS.org (2013)