=Paper=
{{Paper
|id=Vol-2703/paperTD6
|storemode=property
|title=Entropia: A Family of Entropy-Based Conformance
Checking Measures for Process Mining
|pdfUrl=https://ceur-ws.org/Vol-2703/paperTD6.pdf
|volume=Vol-2703
|authors=Artem Polyvyanyy,Hanan Alkhammash,Claudio Di Ciccio,Luciano Garcı́a-Bañuelos,Anna Kalenkova,Sander J. J. Leemans,Jan Mendling,Alistair Moffat,Matthias Weidlich
|dblpUrl=https://dblp.org/rec/conf/icpm/PolyvyanyyACGKL20
}}
==Entropia: A Family of Entropy-Based Conformance
Checking Measures for Process Mining==
https://ceur-ws.org/Vol-2703/paperTD6.pdf
Entropia: A Family of Entropy-Based Conformance
Checking Measures for Process Mining
Artem Polyvyanyy Hanan Alkhammash Claudio Di Ciccio
The University of Melbourne The University of Melbourne Sapienza Università di Roma
artem.polyvyanyy@unimelb.edu.au halkhammash@student.unimelb.edu.au claudio.diciccio@uniroma1.it
Luciano Garcı́a-Bañuelos Anna Kalenkova Sander J. J. Leemans
Tecnológico de Monterrey The University of Melbourne Queensland University of Technology
luciano.garcia@tec.mx anna.kalenkova@unimelb.edu.au s.leemans@qut.edu.au
Jan Mendling Alistair Moffat Matthias Weidlich
Wirtschaftsuniversität Wien The University of Melbourne Humboldt-Universität zu Berlin
jan.mendling@wu.ac.at ammoffat@unimelb.edu.au matthias.weidlich@hu-berlin.de
Abstract— This paper presents a command-line tool, called publicly available1 and supports process analysts in several
Entropia, that implements a family of conformance checking scenarios in which commonalities and discrepancies between
measures for process mining founded on the notion of entropy process models and event logs are measured. Finally, the
from information theory. The measures allow quantifying classi-
cal non-deterministic and stochastic precision and recall quality reader can take a look at a screencast2 that demonstrates the
criteria for process models automatically discovered from traces tool and check the user guide3 that contains a comprehensive
executed by IT-systems and recorded in their event logs. A collection of examples and tutorials on using Entropia.
process model has “good” precision with respect to the log it The paper proceeds as follows. Section II gives an overview
was discovered from if it does not encode many traces that are of the theoretical foundations of conformance checking. Sec-
not part of the log, and has “good” recall if it encodes most of
the traces from the log. By definition, the measures possess useful tion III introduces the Entropia tool using a practical use case
properties and can often be computed quickly. highlighting its analysis features. Section IV discusses the
maturity of the work. Section V provides illustrative examples.
Section VI discusses computational performance and current
I. I NTRODUCTION limitations, before Section VII concludes.
Process mining is a research field concerned with extracting II. C ONFORMANCE C HECKING
knowledge from event sequence data that is stored in event The assessment of the model quality with respect to an
logs. Conceptually, process mining techniques assume that event log is paramount for process mining [1]. Buijs et
events have at least three attributes: a timestamp, a case identi- al. [10] introduce four main quality dimensions, namely fitness,
fier and an activity type [1]. Process mining techniques support precision, generalization, and simplicity, which are currently
various process analysis tasks including automatic process considered the de facto standard. Fitness captures the degree
discovery, conformance checking, and variant analysis [2]. to which the traces recorded in the event log can be replayed
Conformance checking refers to those process mining tech- on the process model. Precision penalizes the extra behavior
niques that compare the behavior captured in an event log with introduced by the model that is not recorded in the event
a normative process model [3]. A key challenge for research log. Conversely, generalization indicates how well the model
on conformance checking is the definition of appropriate can support unforeseen traces. Finally, simplicity denotes the
measures that quantify the extent of correspondence between capability of the model to express the behavior of the event
the log and the model. A rich spectrum of measures have been log while keeping the model easy to understand.
proposed, albeit many of them in an ad hoc manner [4]. The Conformance checking techniques provide a number of
recent stream of work on entropy-based techniques provides approaches for assessing the four quality dimensions. One
a solid theoretical foundation for conformance checking mea- can broadly classify them into two categories: descriptive and
sures with sound properties [5], [6], [7], [8], [9], but in the quantitative. Descriptive techniques construct comprehensive
past tool support has been somewhat limited. artifacts that aim to explain various aspects of the studied
In the paper at hand, we address this gap. Specifically, we 1 https://github.com/jbpt/codebase/tree/master/jbpt-pm
present a command-line tool, called Entropia, that implements 2 https://youtu.be/RZVEFMuH684
entropy-based conformance checking techniques. The tool is 3 https://github.com/jbpt/codebase/tree/master/jbpt-pm/entropia/guide.pdf
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
criterion, e.g., a description of all the commonalities and dis- In the figure, rel and ret represent the relevant behavior and
crepancies between a trace and a process model. Quantitative retrieved behavior, respectively. Function m is used to measure
techniques measure the quantity of the studied phenomenon, the magnitude of the corresponding (part) of the behavior. The
e.g., as a number between zero and one. Orthogonal to this conformance checking approaches implemented in Entropia
classification is the partitioning of conformance checking interpret the behaviors of the compared models as collections
techniques into non-stochastic and stochastic ones. Stochastic of the traces that these models describe, where a trace is a
conformance checking techniques study relations between sequence of process actions. Function m is implemented as the
some stochastic aspects of the compared model and log, e.g., measure of the entropy of a collection of traces; note that the
distributions of traces recorded in the log and described in implemented conformance checking techniques use different
the model. In contrast, non-stochastic techniques, even though notions of entropy, and in different ways, refer to Section IV.
they may rely on the probabilistic aspects of the individual The benefit from using the entropy to measure the magni-
compared artifacts, do not analyze the relations between them. tudes of collections of traces when calculating precision and
recall is twofold. First, one can measure entropy of an arbitrary
III. E NTROPIA (potentially infinite) collection of traces. Second, the entropy-
This section presents Entropia by specifying the use cases it based precision and recall measures can achieve a range of
supports (Section III-A), the core principle behind the entropy- desired properties [4], [11], [5], [8].
based measuring of precision and recall (Section III-B), and C. Interface
the command-line interface (CLI) of the tool (Section III-C).
As of August 2020, the Entropia tool is in version 1.5. It is
A. Use Cases invoked by executing the command:
java -jar jbpt-pm-entropia-1.5.jar
Entropia implements the techniques for quantifying the pre-
cision and recall quality criteria in conformance checking The core CLI options of Entropia are listed in Table I.
presented in [5], [6], [7], [8], and [9]. Two techniques [8], TABLE I
[9] can be used to measure aspects that relate to stochastic C ORE CLI OPTIONS OF THE Entropia TOOL .
precision and recall quality criteria. Option (full) Option Parameter Description
--help -h print help message
B. Entropy-Based Conformance Checking --relevant -rel model that describes relevant traces
--retrieved -ret model that describes retrieved traces
The key idea for quantifying precision and recall between a --silent -s run tool in the silent mode
--version -v get version of this tool
model that describes “relevant” behavior and a model that
captures “retrieved” behavior is to measure the magnitude of The -h and -v options print the help message and tool
the behavior the two models share in relation to the magnitude version, respectively, while options -rel and -ret are
of the behavior of one of the models. used to specify the models of relevant and retrieved traces,
Specific to the process mining context, one can think of an respectively. To refer to a model, the user specifies its file path.
event log as a model that specifies the relevant behavior, i.e., Option -s runs the tool in silent mode, in which the result
the behavior that provides information about the true behavior of the invocation is printed, without any debug information or
it was sampled from. On the other hand, a process model execution data. The tool accepts input models specified in one
discovered from an event log specifies the “retrieved” behavior, of the following formats: eXtensible Event Stream (XES) [12],
i.e., the behavior the applied discovery algorithm constructed Petri Net Markup Language (PNML) [13], Stochastic Petri Net
from the input event log. Markup Language (sPNML), Directly-Follows Graph (DFG),
Then, by following the principle for defining the corre- Stochastic Deterministic Finite Automaton (SDFA). The latter
sponding quality criteria in information retrieval [5], precision three formats are specific to our tool.
can be defined as the ratio of the magnitude of the shared Further CLI options allow selection of a conformance
behavior specified by the models of relevant and retrieved measure to be applied to the input data, and configuration
behaviors to the magnitude of the retrieved behavior. Similarly, of it, and are detailed in the next section.
recall is the ratio of the magnitude of the shared behavior to
IV. M ATURITY
the magnitude of the relevant behavior.
Figure 1 visualizes these ideas. Note that rel ∩ ret refers to The work on the code base of the tool started in August
the behavior shared by the relevant and retrieved behaviors of 2017, together with the start of the work on the entropy-based
the compared models. approach for measuring precision and recall presented in [5].
The tool is integrated into the jBPT library [14], a compendium
m ( rel ∩ ret ) of open-source business process technologies, the work on
Precision:
rel m ( ret ) which commenced in January 2009.
rel \ ret ∩ ret \ rel
m ( rel ∩ ret )
The approach presented in [5] suggests measuring precision
ret
Recall: and recall by interpreting the compared models, e.g., process
m ( rel )
model and event log, as collections of traces that they de-
Fig. 1. Precision and recall quotients [5]. scribe. The models are said to specify shared behavior if and
2
only if they describe identical traces. The magnitude of the TABLE III
behavior captured by each of the compared models, and of the C HARACTERISTICS OF CONFORMANCE CHECKING APPROACHES .
Publ. L-L L-M M-M Stoch. Log Model
behavior shared by the models, is determined as topological
[5] yes yes yes no XES PNML
entropy [15] of the corresponding collection of traces. [6] yes yes yes no XES PNML
In [6], the authors generalize the approach from [5] by [7] yes yes yes no XES PNML
[8] yes yes yes yes XES sPNML
replacing every collection of traces involved in the calculations [9] yes yes no yes XES DFG, SDFA
of the precision and recall measures with the collection of
all subtraces of all the traces it contains. Consequently, the retrieved and relevant traces (L–event log, M–process model)
shared behavior of two collections of traces is identified as supported by the approach presented in the corresponding
a collection of all sequences of actions that are subtraces publication (Publ.); the ability to address the stochastic aspect
of some traces in both compared collections. That is, this of the input models of traces (Stoch.); and the event log and
approach considers all the shared subsequences of actions in process model formats supported (Log–event log, and Model–
the compared models of traces for the measurements. process model).
The measures described in [5] and [6] can be seen as The approaches listed in Table III, except the technique
extremes of the spectrum, with either no or all subtraces presented in [9], can be used to quantify precision and recall
considered when determining the magnitudes of the collections conformance criteria between two (possibly infinite) collec-
of traces. The approach presented in [7] allows for a flexible tions of traces. The approach in [9] measures the entropic
analysis. In particular, based on knowledge of the compared relevance of a stochastic process model to an event log.
models, the user can specify the maximal number of allowed Relevance reflects a compromise between the precision and
skipped actions in a trace described by each of the models of recall criteria and has meaningful units.
traces for determining the shared subtraces. This way, the user
can tune the measures towards the desired sensitivity to the V. E XAMPLES
discrepancies in the compared behaviors. In this section we provide some examples of Entropia, using
In [8], entropy is used to extend conformance checking to the Petri net N in Fig. 2, the SDFA A in Fig. 3, and an event
stochastic process mining. An event log and a stochastic pro- log E = [abce, ace, bce2 , abcdcbe, abdcbe, aaacbe].
cess model can be compared based on whether they exhibit the Note that E contains two instances of bce.
same control flow, but also based on whether the frequency of p1 t1 p3
behavior in the event log matches the probabilities of behavior b
in the model. To this end, both log and model are translated p0 t0 t4 p5
into stochastic deterministic finite automata, the conjunction • a d t2 e
of these automata is constructed, and the entropy of these
three automata yields two measures: stochastic recall and c
stochastic precision. In [8], an evaluation shows the practical p2 t3 p4
applicability by searching for pairwise similar process models
in a 4000-model repository. Fig. 2. A Petri net.
Finally, the entropic relevance measure presented in [9] is s2
0
a stochastic conformance measure computed as the average b(1/2) c(1)
number of bits required to compress (i.e., to perform the a(1) d(1/2) e(1/2)
0 0 0 1
entropy coding of) a trace from the log using the information
s0 s1 s3 s5
on the relative likelihood of traces encoded in the model. c(1/2) b(4/5)
1/5 s4
Table II lists the tool options to select and configure the
supported conformance measures. Table III then summarizes Fig. 3. An SDFA.
the characteristics of the conformance checking approaches
implemented in Entropia by specifying the input models of The entropy-based exact matching precision between N and
E presented in [5] is computed using the CLI options:
TABLE II -emp -rel=E.xes -ret=N.pnml
S PECIFIC CLI OPTIONS OF THE Entropia TOOL .
To allow up to two skips in traces of the Petri net and up
Option Parameter Description Publ.
-emp exact matching precision [5] to one skip in the traces of the log, as described in [7], when
-emr exact matching recall [5] identifying similar traces in the computation of precision, these
-pmp partial matching precision [6]
-pmr partial matching recall [6]
CLI options should be employed:
-cpmp controlled partial matching precision [7] -cpmp -rel=E.xes -ret=N.pnml -srel=1 -sret=2
-cpmr controlled partial matching recall [7]
-srel number of allowed skips in relevant traces [7] These options compute the entropic relevance of A to E:
-sret number of allowed skips in retrieved traces [7] -r -rel=E.xes -ret=A.sdfa
-sp stochastic precision [8]
-sr stochastic recall [8] The computed values of exact matching precision, con-
-r entropic relevance [9] trolled partial matching precision, and entropic relevance using
3
the above CLI options for net N , SDFA A and log E are ideas are provided on using entropy to measure the simplicity
0.776, 0.833, and 11.368 bits, respectively. Further examples of a model automatically discovered from a log.
of Entropia and the serialized models and log used in the
VII. C ONCLUSION
examples discussed above appear in the user guide.3
This paper presents Entropia, an open-source command-line
VI. D ISCUSSION tool for quantifying precision and recall conformance quality
criteria in process mining. The current version of the tool
All the techniques implemented in Entropia ver. 1.5 support implements several measures, all grounded in the notion of the
process models that describe arbitrary (potentially infinite) entropy of a collection of traces described by a process model
collections of traces and impose no limitations on input logs or event log. The supported measures can be used to assess
provided that they are explicitly recorded and, thus, are finite. both classical and stochastic precision and recall, and fulfill
However, process models must be bounded, i.e., they must a wide range of desired properties suggested by the process
induce finite reachability graphs. Various notions of semantic mining community. The development of the tool’s code base
correctness of process models require process models to be commenced in 2017 and is maintained by the authors of the
bounded. Nevertheless, process models used in practice can implemented techniques.
be incorrect, thus potentially unbounded. Hence, each process Acknowledgment. Artem Polyvyanyy and Anna Kalenkova
model provided as input to Entropia, which is not guaran- were in part supported by the Australian Research Council
teed by definition to be bounded, is tested by default for project DP180102839.
boundedness using LoLA ver. 2.0 [16]. One can check if a
process model is bounded using option -b of the tool. If the R EFERENCES
boundedness of process models is established, one can invoke [1] W. M. P. van der Aalst, Process Mining—Data Science in Action, 2nd ed.
Springer, 2016.
Entropia with option -t to skip the model correctness tests. [2] M. Dumas, M. L. Rosa, J. Mendling, and H. A. Reijers, Fundamentals
Entropia is implemented in Java and integrates with the of Business Process Management, 2nd ed. Springer, 2018.
LoLA tool compiled for Windows. To use Entropia on another [3] J. Carmona, B. F. van Dongen, A. Solti, and M. Weidlich, Conformance
Checking—Relating Processes and Models. Springer, 2018.
platform, one needs to recompile LoLA for that platform. [4] N. Tax, X. Lu, N. Sidorova, D. Fahland, and W. M. P. van der Aalst, “The
Different conformance techniques implemented in Entropia imprecisions of precision measures in process mining,” Inf. Process.
have different performance characteristics. The computation Lett., vol. 135, pp. 1–8, 2018.
[5] A. Polyvyanyy, A. Solti, M. Weidlich, C. D. Ciccio, and J. Mendling,
time of entropic relevance [9] is linear in the size of the “Monotone precision and recall measures for comparing executions and
event log (number of traces times average length of a trace). specifications of dynamic systems,” ACM Trans. Softw. Eng. Methodol.,
The computation of entropy-based precision and recall [5], vol. 29, no. 3, 2020.
[6] A. Polyvyanyy and A. Kalenkova, “Monotone conformance checking for
[6], [7] is low polynomial in the size of the reachability partially matching designed and observed processes,” in ICPM. IEEE,
graphs of the compared models of traces. However, in practice, 2019, pp. 81–88.
a reachability graph can be large, and possibly exponential [7] A. Kalenkova and A. Polyvyanyy, “A spectrum of entropy-based preci-
sion and recall measurements between partially matching designed and
in the size of the original model due to state explosion. observed processes,” in ICSOC, ser. LNCS. Springer, 2020.
Empirical evidence suggests that the approach grounded in [8] S. J. J. Leemans and A. Polyvyanyy, “Stochastic-aware conformance
the exact matching of traces [5] runs in the order of seconds checking: An entropy-based approach,” in CAiSE, ser. LNCS, vol.
12127. Springer, 2020, pp. 217–233.
on real-world datasets, as the state explosion does not manifest [9] A. Polyvyanyy, A. Moffat, and L. Garcı́a-Bañuelos, “An entropic rele-
often. Grounding in the partial matching of traces [6], on vance measure for stochastic conformance checking in process mining,”
the other hand, induces large reachability graphs. Thus, it in ICPM. IEEE, 2020, In Press.
[10] J. C. A. M. Buijs, B. F. van Dongen, and W. M. P. van der Aalst,
is recommended for small inputs, e.g., when calibrating a “Quality dimensions in process discovery: The importance of fitness,
new automated process discovery technique. The controlled precision, generalization and simplicity,” Int. J. Cooperative Inf. Syst.,
partial matching technique [7] can be configured by the user vol. 23, no. 1, pp. 1–40, 2014.
[11] A. F. Syring, N. Tax, and W. M. P. van der Aalst, “Evaluating con-
to the desired performance, balancing the number of allowed formance measures in process mining using conformance propositions,”
mismatches between similar traces and runtime, with fewer Trans. Petri Nets Other Model. Concurr., pp. 192–221, 2019.
allowed mismatches allowing faster computation. The tech- [12] “IEEE standard for eXtensible Event Stream (XES) for achieving
interoperability in event logs and event streams,” IEEE Std 1849-2016,
niques reported in [5], [6] constitute the two extremes of the pp. 1–50, 2016.
trade-off spectrum. Finally, the computation of the stochastic [13] J. Billington, S. Christensen, K. M. van Hee, E. Kindler, O. Kummer,
measures presented in [8] relies on an iterative procedure L. Petrucci, R. Post, C. Stehno, and M. Weber, “The Petri Net Markup
Language: Concepts, technology, and tools,” in ATPN, ser. LNCS, vol.
which converges deterministically to the correct values, and is 2679. Springer, 2003, pp. 483–505.
often quick; but which can also lead to prolonged computation [14] A. Polyvyanyy and M. Weidlich, “Towards a compendium of process
times on real-world datasets. technologies—the jBPT library for process model analysis,” in CAiSE
Forum, ser. CEUR, vol. 998. CEUR-WS.org, 2013.
Future work on Entropia will both aim to improve the [15] T. Ceccherini-Silberstein, A. Machı́, and F. Scarabotti, “On the entropy
runtime performance of the current techniques and also im- of regular languages,” Theor. Comput. Sci, vol. 307, no. 1, 2003.
[16] K. Schmidt, “LoLA: A low level analyser,” in ATPN, 2000, pp. 465–474.
plement new state-of-the-art information theoretic approaches [17] A. Kalenkova, A. Polyvyanyy, and M. La Rosa, “A framework for
to conformance checking, including those that assess quality estimating simplicity of automatically discovered process models based
criteria beyond precision and recall. For example, in [17] initial on structural and behavioral characteristics,” in BPM. Springer, 2020.
4