A Novel Approach to Process Discovery with Enhanced Loop Handling (Extended version)

Ali Nour Eldin, Benjamin Dalmas, Walid Gaaloul · 2024

Read A Novel Approach to Process Discovery with Enhanced Loop Handling (Extended version) by Ali Nour Eldin, Benjamin Dalmas, Walid Gaaloul (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-06653.txt.

Introduction

Ali Nour Eldin, Benjamin Dalmas, and Walid Gaaloul present a new process mining method in this 2024 paper. Process mining rebuilds a map of how work actually flows from the logs that software leaves behind. Loops, where steps repeat, are a weak spot for current tools, and gains in one quality score often cost another.

Their tool, Bonita Miner, filters the raw flow graph and then detects parallel steps, splits, and loops with fresh algorithms. The output is a standard business process diagram. On real event logs, their models beat rivals on fit, precision, and reach, while staying simple to read.

Catalog record

CREATORAli Nour Eldin, Benjamin Dalmas, Walid Gaaloul
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE29 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-06653

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

A Novel Approach to Process Discovery with Enhanced Loop Handling (Extended version) Ali Nour Eldin, Benjamin Dalmas, Walid Gaaloul Abstract Automated process discovery from event logs is a key component of process mining, allowing companies to acquire meaningful insights into their business processes. Despite significant research, present methods struggle to balance important quality dimensions: fitness, precision, generalization, and complexity, but is limited when dealing with complex loop structures. This paper introduces Bonita Miner, a novel approach to process model discovery that generates behaviorally accurate Business Process Model and Notation (BPMN) diagrams. Bonita Miner incorporates an advanced filtering mechanism for Directly Follows Graphs (DFGs) alongside innovative algorithms designed to capture concurrency, splits, and loops, effectively addressing limitations of balancing as much as possible these four metrics, either there exists a loop, which challenge in existing works. Our approach produces models that are simpler and more reflective of the behavior of real-world processes, including complex loop dynamics. Empirical evaluations using real-world event logs demonstrate that Bonita Miner outperforms existing methods in fitness, precision, and generalization, while maintaining low model complexity. 1 Introduction Process discovery [ 4 ] is one of the most prominent process mining techniques. It enables the automatic discovery of a process model that captures and explains the behavior recorded in event logs. The process model is typically represented in Petri nets [ 15 ] , but other formats are also possible (e.g., in the standard Business Process Model and Notation - BPMN [ 9 ] ). A discovered process model must accurately reflect the behavior observed in or inferred from the event log. Specifically, the process model should (i) parse the traces contained within the log, (ii) parse traces not present in the log but likely to belong to the process that generated the log, and (iii) refrain from parsing traces unrelated to the process. These properties are known as fitness, generalization, and precision, respectively. Furthermore, the model should be as simple as possible, a characteristic often quantified through complexity measures [ 8 ] . Despite extensive research [ 4 , 16 ] , achieving a balance across the four key quality dimensions — fitness, precision, generalization, and complexity — remains a challenge. When applied to real-life event logs, most automated process discovery techniques, such as the Heuristics Miner [ 17 ] and its derivatives, often produce large, spaghetti-like models that are behaviorally incorrect (e.g., prone to deadlocks). Another state-of-the-art technique, the Inductive Miner [ 12 ] , tends to generate block-structured models that are behaviorally sound with high fitness but exhibit low precision. Additionally, the SplitMiner approach [ 5 ] is capable of producing accurate and simple process models; however, these models become complex and unsound in the presence of loops, complicating the observed behavior in the event log and reducing the accuracy and structure of the results. We provide a basic example to illustrate a limitation addressed by existing methods, shown in Figure 1 . Consider an event log for the BPMN model represented in Figure 1(b) , where there exists a loop that includes the parallel blocks b and c . Current state-of-the-art algorithms are unable to accurately discover this BPMN pattern with a loop over parallel blocks. Instead, they produce a model like the one shown in Figure 1(a) , where these algorithms incorrectly represent b and c with individual self-loops. This misrepresentation significantly impacts the model’s accuracy, reducing its usability for real-world process analysis. (a) Discovered Model by Split Miner, Inductive Miner, Heuristics Miner. (b) BPMN to Discover Figure 1 : A simple example of the limitation of existing works. To address this limitation and bridge the identified gap, this paper introduce Bonita Miner, a novel process discovery method to generate simpler process models while still achieving a balance among fitness, precision, and generalization. The approach leverages a novel Depth-First Algorithm (DFA) for constructing splits and joins, coupled with advanced filtering of the directly-follows graph (DFG) derived from event logs. These constructs effectively capture concurrency, choices, causal relationships, and even loops within the DFG. The DFA reduces model complexity while maintaining a balance among evaluation metrics, making the method suitable for processes of varying complexity, including those with loops. We also treat the loops as blocks (with one or multiple sources and one or multiple targets). We empirically demonstrate that Bonita Miner surpasses three state-of-the-art baselines by evaluating its performance on BPIC real-life and synthetic loops event logs using eight comprehensive metrics that measure the four key quality dimensions, even in the presence of complex loop structures. The remainder of the paper is structured as follows. Section 2 reviews the existing process discovery methods. Section 3 introduces the Bonita Miner method, followed by Sections 4 and 5 , which detail the proposed approach. Section 6 discusses the empirical evaluation of Bonita Miner, and finally, Section 7 concludes the paper and outlines potential directions for future research. 2 Related work The section provides an overview of existing automated process discovery methods and discusses their limitations. The \alpha -algorithm [ 2 ] is a simple automated process discovery method based on the concept of DFG. While appealing due to its simplicity, the \alpha -algorithm is not applicable to real-life event logs since it assumes the log to be complete and is too sensitive to infrequent behavior. The Heuristics Miner [ 18 ] addresses these limitations and consistently performs better in terms of accuracy on incomplete and noisy logs. To handle noise, the Heuristics Miner relies on a relative frequency metric between pairs of event labels. However, while this technique demonstrates higher fitness, it faces the challenge of lower precision. Structured process models are generally more understandable than unstructured ones [ 10 , 11 ] . Moreover, structured models are sound, provided that the gateways at the entry and exit of each block match. Given these advantages, several algorithms have been designed to discover structured process models, represented for example as process trees. The Inductive Miner [ 13 ] uses a divide-and-conquer approach to discover process structured models, achieving high fitness. However, it tends to over-generalize the behavior observed in the log whenever the process model to be discovered is unstructured, generating undesired flower models [ 5990012 ] . The Structured Miner [ 3 ] addresses this limitation by relaxing the requirement of always producing a structured process model, in favor of achieving higher accuracy. Split Miner [ 5 ] is another method that addresses the balance between fitness, precision, and generalization. It focuses on filtering directly-follows graphs and discovering split gateways to produce simple, accurate, and deadlock-free process models. However, Split Miner is limited in handling loops effectively, which can lead to challenges in processes with loop-intensive behavior. To reduce these challenges, an improved approach is proposed, which enhances the handling of loops while maintaining a balance across other quality dimensions. This approach ensures better adaptability to loop-intensive scenarios, thereby improving model quality and applicability. 3 Approach Overview As mentioned in the introduction, the goal of the algorithm introduced in this paper is to ensure the balancing of key metrics even in the presence of loops. For example, it successfully identifies the pattern represented in the BPMN model of Figure 1(b) , achieving a model accuracy

Read the complete text