Introduction
Everyday, organizations deliver services and products to their customers by enacting
their business processes, the quality and efficiency of which directly influence the
customer experience. In competitive business environments, achieving a great customer
experience is fundamental to be a successful company. For this reason, companies rely
on programmatic business process management in order to discover, analyse, improve,
automate, and monitor their business processes [
8
].
One of the core activities of business process management is process discovery. The
goal of process discovery is to generate a graphical representation of a business process,
namely business process model, which is then used for analysis and optimization
purposes. Traditionally, process discovery has been a time-consuming activity performed
either by interviewing relevant process stakeholders, or by observing process
participants in action, or by analysing process reference documentation. However, with the
diffusion of information systems and specialised software in organizational settings, a
new form of process discovery is slowly emerging, which goes by the name of
automated process discovery [
15
].
Automated process discovery allows business analysts to exploit process’ execution
data (recorded into so-called event logs) to automatically generate process models.
Discovering high-quality process models is extremely important to reduce the time spent
to enhance them and avoid mistakes during process analysis. In the past two decades,
many research studies have addressed the problem of automated discovery of business
process models from event logs [
18, 11, 7, 3, 17
]. Despite the richness of proposals, the
state-of-the-art automated process discovery approaches (APDAs) struggle to
systematically discover accurate process models. In general, the quality of a discovered process
model depends on both the input log and the APDA that is applied. When the input
event log is simple, some state-of-the-art APDAs can output accurate and simple
process models. However, as the complexity of the input data increases, the quality of the
discovered process models can worsen quickly. Given that real-life event logs tend to
be highly complex (i.e. containing noise and incomplete event records),
state-of-theart APDAs turn to be unreliable. In addition, some of these APDAs do not scale up to
real-life logs in terms of time performance.
Against this backdrop, in this thesis, we address the following three research
questions.
• RQ1 - What are the state-of-the-art automated process discovery approaches, their
strengths and limitations?
• RQ2 - How to strike a trade-off between the various quality dimensions in
automated process discovery in an effective and efficient manner?
• RQ3 - How can the accuracy of an automated process discovery approach be
efficiently optimized?
2
Summary of Contributions
In order to answer RQ1, we conducted a Systematic Literature Review (SLR) [
4
] through
a scientific, rigorous and replicable approach as specified by Kitchenham [
10
]. We
formulated a set of research questions to scope the search and developed a list of search
strings that we ran on different academic databases. We applied inclusion criteria to
select the studies retrieved through the search. Our SLR highlights a growing interest in
the field of automated process discovery, and confirms the existence of a wide and
heterogeneous number of proposals. Between 2012 and 2017 more than 80 studies
proposing an automated process discovery approach have been published. We grouped these
studies into 34 groups, each referring to a specific APDA, and we described their
features, such as: the type of model they can discover, semantic they are able to represent,
type of implementation and available artefacts and tools, and type of evaluation.
Despite the variety of proposals, we could clearly identify two main streams: approaches
that output procedural process models, and approaches that output declarative process
models. Furthermore, while the latter ones only rely on declarative statements to
represent a process, the former provide various language alternatives, although most of
these methods output Petri nets. The predominance of Petri nets is driven by the
semantic power of this language, and by the requirements of the methods used to assess
the quality of the discovered process models (chiefly, fitness and precision). Finally, we
designed a benchmark framework to enable researchers to empirically compare new
APDAs against existing ones in a unified setting. Our benchmark shows that existing
APDAs are affected by one (or more) of the following three limitations when used with
their default input parameters: (i) they achieve limited accuracy; (ii) they are
computationally inefficient to be used in practice; (iii) they discover syntactically incorrect
process models. To analyse the importance and the impact of the APDAs input
parameters, we also ran a hyper-parameter optimization evaluation. The latter highlighted that
existing APDAs can achieve better results when their input parameters are finely tuned.
However, such a tuning is expensive in terms of computational power and time,
sometimes requiring up to 24 hours to discover a process model as opposed to seconds (or
minutes) when choosing default parameters.
To address the limitations identified in our benchmark, and to answer RQ2, we
proposed a novel APDA, namely Split Miner [
5
]. Split Miner operates over six steps: DFG
and loops discovery; concurrency discovery; filtering; splits discovery; joins discovery;
and OR-joins minimization. The algorithms that implement these six steps have been
designed with the goal to strike a trade-off between the various quality dimensions in
automated process discovery in an effective and efficient manner. In other words, each
of the six steps plays a fundamental role in the discovery of a highly fitting and precise
process model, that is at the same time simple and deadlock-free. About the latter
property, we formally proved that Split Miner guarantees to discover sound acyclic process
models, and deadlock-free cyclic process models. Differently than other APDAs that
guarantee soundness [
11, 7
], Split Miner does not achieve such a result by enforcing
full structuredness on its discovered process models, making SM the very first3 APDA
that guarantees to discover sound (or deadlock-free) process models that are not
(necessarily) fully structured. Furthermore, we showed that the time complexity of Split Miner
is polynomial, guaranteeing efficiency in terms of execution times. Finally, in line with
its formal properties, the results of the empirical evaluation of Split Miner highlighted
that our approach performs better than the state-of-the-art APDAs. In particular, Split
Miner achieved with statistical significance higher F-scores (of fitness and precision)
than state-of-the-art APDAs. This is achieved by balancing fitness and precision, while
maintaining a low complexity of the discovered process models. The empirical
evaluation also highlighted that despite SM cannot guarantee soundness for cyclic process
models, SM is still able to discover sound cyclic process models. Lastly, SM proved to
be the fastest APDA, discovering process models in less than a second regardless of the
size of the input event logs.
As in the majority of existing APDAs, Split Miner also requires input parameters.
Such parameters can be optimized to achieve considerable improvements in the quality
of the process models produced. As already noted, the quality improvement APDAs
achieve via hyper-parameter optimization comes at the cost of longer execution times
and higher computational requirements. This inefficiency is the direct consequence of
two different problems: (i) the low scalability of the accuracy measures, especially
precision; and (ii) a brute-force exploration of the solution space. By addressing both
problems we can tackle RQ3.
Over the past decade, several measures of fitness and precision have been proposed
and empirically evaluated in the literature [
9
]. Existing precision measures (and to a
lesser extent also fitness measures) suffer from scalability issues when applied to
models discovered from real-life event logs. In addition, Tax et al. [
14
] have shown that none
of the existing precision measures fulfils a set of five intuitive properties, namely
precision axioms. These axioms were then revised by Syring et al. [
13
], who also proposed
a set of desirable properties of fitness measures, namely fitness propositions, showing
that only the latest fitness and precision measures designed by Polyvyanyy et al. [
12
]
can fulfil the proposed properties.
In this thesis, we designed a family of fitness and precision measures [
2
] based on
the idea of comparing the kth-order Markovian abstraction of a process model against
that of an event log. We showed that the proposed measures fulfil all aforementioned
properties for a suitable k dependent on the log.
While fulfilling the proposed properties is desirable, this does not guarantee that
the proposed measures provide intuitive results in practice. To validate the intuitiveness
of our measures, we compared the ranking they induce against those induced by
existing fitness and precision measures using a collection of model-log pairs proposed by
3 According to our literature review and benchmark.
van Dongen et al. [
16
] (extended to cover fitness in addition to precision). For k 4,
the proposed fitness measures induce rankings that coincide with alignment-based
fitness [
1
] – a commonly used fitness measure. Meanwhile, for k 3, the proposed
precision measures induce rankings consistent with those of the anti-alignment precision
measure [
16
], previously posited as a ground-truth for precision measures.
A second evaluation using real-life event logs showed that the execution times of the
proposed fitness measures (for k 5) are considerably lower than existing fitness
measures, except when applied to process models that contain flower structures, in which
case alignment-based fitness offers the best performance. Similarly, the execution times
of the proposed precision measures (for k 5) are considerably lower than existing
precision measures, except for models that contain flower structures.
The comparison between the process model and the event log Markovian
abstractions allows us to identify the behaviour to add to (remove from) the process model
in order to improve its fitness (precision). Indeed, such information is encoded in the
edges of the event log Markovian abstraction that cannot be found in the process model
Markovian abstraction (and viceversa), and it is independent from the value of k and
not prone to approximation by design.
By employing our Markovian accuracy measures to efficiently explore the
solutionspace of APDAs based on directly-follows graphs (DFGs), we designed an optimization
framework powered by single-solution-based metaheuristics [
6
], that boosts the
capability of DFG-based APDAs to discover process models with higher accuracy. The core
idea of our framework is to perturb the intermediate representation of an event log used
by the majority of the available APDAs, namely the Directly-follows Graph (DFG).
Specifically, we consider perturbations that add or remove edges with the aim of
improving fitness or precision, and allowing the underlying APDA to discover a process
model from the perturbed DFG.
We instantiated our framework for three state-of-the-art APDAs: Split Miner,
Fodina, and Inductive Miner, and using a benchmark of 20 real-life logs, we compared
the accuracy gains yielded by four optimization metaheuristics relative to each other
and relative to the hyper-parameter optimized APDA. The evaluation of our
optimization framework highlights its effectiveness in optimizing DFG-based APDAs, allowing
APDAs to explore their solution-space beyond the boundaries of hyper-parameter
optimization and most of the times in a faster manner, ultimately discovering more accurate
process models in less time, compared to the traditional hyper-parameters optimization.
In order to foster reproducibility and reuse, all the artefacts designed and developed
for this thesis are publicly available as standalone open-source Java command-line
applications.4 Split Miner, our core contribution to the field of automated process
discovery, has also been integrated into Apromore, an open-source business process analytics
platform used by academics and practitioners alike.
4 Applications available at https://apromore.org/platform/tools/