=Paper=
{{Paper
|id=Vol-1371/paper04
|storemode=property
|title=ILP-Based Process Discovery Using Hybrid Regions
|pdfUrl=https://ceur-ws.org/Vol-1371/paper04.pdf
|volume=Vol-1371
|dblpUrl=https://dblp.org/rec/conf/apn/ZelstDA15
}}
==ILP-Based Process Discovery Using Hybrid Regions==
https://ceur-ws.org/Vol-1371/paper04.pdf
ILP-Based Process Discovery Using Hybrid Regions
S.J. van Zelst, B.F. van Dongen, and W.M.P. van der Aalst
Department of Mathematics and Computer Science
Eindhoven University of Technology, The Netherlands
{s.j.v.zelst,b.f.v.dongen,w.m.p.v.d.aalst}@tue.nl
Abstract. The language-based theory of regions, stemming from the area of
Petri net synthesis, forms a fundamental basis for Integer Linear Programming
(ILP)-based process discovery. Based on example behavior in an event log, a pro-
cess model is derived that aims to describe the observed behavior. Building on
top of the existing ILP-formulation, we present a new ILP-based process discov-
ery formulation that unifies two existing types of language-based regions and,
additionally, we present a generalized ILP objective function that captures both
region-types and helps us to find suitable process discovery results.
Keywords: Process mining, process discovery, integer linear programming, re-
gion theory
1 Introduction
Process Mining [1] forms the connecting element between business process modeling
and data analysis. Its main aim is to extract knowledge from business process execution
data originating from a variety of data sources, e.g., enterprise information systems, so-
cial media, embedded systems etc. Within process mining, three main branches are dis-
tinguished being process discovery, conformance checking and process enhancement.
Within process discovery the aim is to, given an event log, reconstruct a process model.
Within conformance checking the aim is to assess, given a process model and an event
log, the conformance of the event log to the process model. Within process enhance-
ment the aim is to further improve and/or align existing process models by combin-
ing the two aforementioned disciplines, e.g., identification and removal of bottlenecks
within business processes.
The area of Petri net synthesis [2] is concerned with deciding whether there exists
a Petri net that exactly describes a given sequential behavioral system description. A
subclass of synthesis techniques is the area of region theory which is both defined on
transition systems, known as state-based region theory, and on languages, known as
language-based region theory.
Language-based region theory forms a fundamental basis for ILP-based process
discovery [3]. Within process discovery however, a process model is typically valued
w.r.t. four essential process mining quality dimensions being replay-fitness, precision,
generalization and simplicity [4]. Applying traditional Petri net synthesis techniques
in a process discovery context will result in models that have perfect replay-fitness,
maximal precision, low generalization and often low simplicity.
47
In this paper we propose a unified approach w.r.t. ILP-based process discovery,
based on the newly introduced concept of hybrid variable-based regions. Hybrid variable-
based regions unite two existing language-based region definitions and allow us to vary
the number of variables used within the ILP problems being solved. Therefore, we as-
sess the impact of using a different number of variables on the average computation
time of solving ILPs during ILP-based process discovery. Additionally we present a
new generalized ILP objective function that supports hybrid variable-based regions and
show that the objective function yields correct process discovery results.
The outline of this paper is as follows. In Section 2 we present basic preliminaries.
In Section 3 we present language-based regions. In Section 4 we show how to adopt
language-based regions within process discovery using ILP. In Section 5 we present
a brief evaluation of the performance of the approach. Section 6 covers related work.
Section 7 concludes the paper.
2 Preliminaries
2.1 Bags, Sequences and Vectors
Let Z denote the set of integers, let N denote the set of positive integers including 0
and let N+ denote the set of positive integers excluding 0. Let R denote the set of real
numbers and let R+ denote the set of positive real numbers excluding 0.
Let S denote a set. Let us define a bag B as a function B : S → N. Notation-wise
we write a bag as [en1 1 , en2 2 , ..., en3 3 ], where ei ∈ S, ni ∈ N+ and eni i ≡ B(ei ) = ni . If
for some element e, B(e) = 1, we omit its superscript. An empty bag is denoted as ∅.
As an example let S1 = {a, b, c, d} and let B1 denote a bag consisting of 3 a’s, 5 b’s,
1 c and 0 d’s, i.e. B1 = [a3 , b5 , c]. Element inclusion applies to bags as well, i.e. given
e ∈ S and B(e) > 0 then also e ∈ B. Thus we have a ∈ B1 whereas d ∈ / B1 .
A sequence σ is a function relating positions to elements e ∈ S, i.e. σ : {1, 2, ...,
k} → S. An empty sequence is denoted as . We write every non-empty sequence as
he1 , e2 , ..., ek i. The set of all possible sequences over a set S is denoted as S ∗ . We define
concatenation of sequences σ1 and σ2 as σ1 · σ2 , e.g., ha, bi · hc, di = ha, b, c, di. If we
are given a set X of sequences over S, i.e., X ⊆ S ∗ , we define X’s prefix-closure as
X = {σ1 ∈ S ∗ |∃σ2 ∈S ∗ (σ1 · σ2 ∈ X)}. Let X ⊆ S ∗ , X is prefix-closed if X = X. Let
X ⊆ S ∗ and let BX : X → N be a bag, we define BX ’s prefix closure as B X : X → N
X
B X (σ) = B(σ) + B X (σ · hei)
σ·hei∈X
Thus, for set X1 = {ha, bi, ha, ci} we have X 1 = {, hai, ha, bi, ha, ci} whereas for
bag B2 = [ha, bi5 , ha, ci3 ] we have B 2 = [8 , hai8 , ha, bi5 , ha, ci3 ].
Let S be a set on which we can pose some total order and let R ⊆ R be a range
of values. Vectors are denoted as ~z ∈ R|S| , where ~z(e) ∈ R and e ∈ S. A vector
~z represents a column vector. For vector multiplication we assume vectors to agree
on their indices. Thus,Pgiven a totally ordered set S = {e1 , e2 , ..., en } and ~z1 , ~z2 ∈
R|S| we have ~z1| ~z2 = i∈{1,2,...,n} ~z1 (ei )~z2 (ei ). Parikh vectors represent the number
of occurrences of a certain element within a sequence. A Parikh vector is a function
48
p~ : S ∗ → N|S| with p~(σ) = (σe1 , σe2 , ..., σen ) where σei = |{j | 1 ≤ j ≤ |σ|,
σ(j) = ei }|. As an example consider S = {a, b, c, d}, σ1 = ha, b, di and σ2 = ha, c, di.
We have p~(σ1 )| = (1, 1, 0, 1) and p~(σ2 )| = (1, 0, 1, 1). Note that σ1b = 1 whereas
σ2b = 0. Given a Parikh vector p~ : S ∗ → N|S| and a set Q ⊆ S, we define p~Q : S ∗ →
N|Q| . Thus given S = {a, b, c, d} and σ1 = ha, b, di we have p~{a,c,d} (σ1 )| = (1, 0, 1).
2.2 Event Logs and Petri Nets
The main goal of process discovery is to describe the observed behavior within an
event log by means of a process model. Thus, event logs act as the input of process
discovery whereas some process model acts as the output of process discovery. An
abstract example of an event log is presented in Table 1. Often more data attributes are
available in an event log, e.g., customer id, credit balance etc. In this paper we focus on
the sequential ordering of activities w.r.t. cases, i.e. the control-flow perspective.
Definition 1 (Event log). Let A be a set of activities, an event log L is a bag of se-
quences over A, i.e., L : A∗ → N.1
A sequence of activities σ ∈ L is referred to as a trace. We assume that any given set
of activities A is totally ordered (or we are able to trivially pose a total ordering on A).
We consider Petri nets to describe process models. A Petri net is a bipartite graph
consisting of a set of vertices called places and a set of vertices called transitions. Arcs
(directed edges) are connecting places and transitions and have an associated positive
weight.
Definition 2 (Petri net). A Petri net is a 3-tuple N = (P, T, W ), where P is a set of
places and T is a set of transitions with P ∩ T = ∅. W is the weighted flow relation of
N , W : (P × T ) ∪ (T × P ) → N.
For a given node x ∈ P ∪ T , the pre-set of x in N is defined as •x = {y | W (y,
x) > 0}. Correspondingly x• = {y | W (x, y) > 0} denotes the post-set of x in
N . Graphically we represent places as circles and transitions as boxes. For every (x,
y) ∈ (P × T ) ∪ (T × P ) with W (x, y) > 0 we draw an arc from x to y. If W (x, y) > 1
Table 1: An abstract example of an event log.
Case id Activity id Resource id Time-stamp
c1 a Lucy 2015-01-05T09:13:37+00:00
c2 a John 2015-01-05T13:37:25+00:00
c2 b Pete 2015-01-06T13:14:15+00:00
c2 d Lucy 2015-01-06T15:27:18+00:00
c1 c Pete 2015-01-07T14:28:56+00:00
c1 d John 2015-01-07T15:30:00+00:00
. . . .
. . . .
. . . .
1
In practice we extract an event log L from some information system. Consequently A is
implicitly defined by the event log, i.e., A only consists of events that are actually present L.
49
we denote the arc’s weight W (x, y) on top of the arc from x to y. A Petri net is pure
if it does not contain self-loops, i.e., if W (x, y) > 0 then W (y, x) = 0. An example
(pure) Petri net is depicted in Figure 1.
Definition 3 (Marked Petri net). Let N = (P, T, W ) be a Petri net. A marking of N
is a bag over N ’s places, i.e. M : P → N. A marked Petri net is a pair (N, M0 ), where
M0 represents N ’s initial marking.
Let N = (P, T, W ) be a Petri net and let M be a marking of N . A transition t ∈ T
is enabled, denoted (N, M )[ti, if and only if ∀p∈•t (M (p) ≥ W (p, t)). Graphically
we represent a marking by drawing exactly a place’s marking-multiplicity number of
dots inside the place (e.g. p1 in Figure 1 with M0 = [p1 ]). If a transition t is enabled
in (N, M ), t may fire, resulting in a new marking M 0 . When t fires, denoted as (N,
M )[ti(N, M 0 ), we have ∀p∈P (M 0 (p) = M (p) − W (p, t) + W (t, p)). For example in
Figure 1 we have (N1 , [p1 ])[ai(N1 , [p2 ]).
Definition 4 (Firing sequences). Let N = (P, T, W ) be a Petri net and let (N, M0 )
be a corresponding marked Petri net. Sequence σ = ht1 , t2 , ..., tn i ∈ T ∗ is a firing
sequence of (N, M0 ), written as (N, M0 )[σi(N, Mn ) if and only if for n = |σ| there
exist markings M0 , M1 , M2 , ..., Mn such that (N, M0 )[t1 i(N, M1 ), (N, M1 )[t2 i(N,
M2 ), ..., (N, Mn−1 )[tn i(N, Mn ).
Note that infinitely many firing sequences can exist given a Petri net. Some example
firing sequences of the Petri net depicted in Figure 1 are: (N1 , [p1 ])[haii(N1 , [p2 ]),
(N1 , [p1 ])[ha, bii(N1 , [p3 ]) and (N1 , [p1 ])[ha, c, d, e, f, e, f, e, gii(N1 , ∅). The set of all
possible firing sequences in a Petri net N is called N 0 s language, i.e., all sequences
σ ∈ T ∗ s.t. (N, M0 )[σi(N, Mi ). N ’s language is denoted as L(N ) ⊆ T ∗ and is prefix-
closed.
Consider Figure 1 and event log L1 = [ha, b, d, e, gi10 , ha, c, d, e, gi9 , ha, b, d, e,
f, e, gi11 , ha, c, d, e, f, e, gi8 ] over A1 = {a, b, c, d, e, f, g}. Clearly we have L1 ⊂
L(N1 ), and thus replay-fitness of L1 on N1 is perfect. We will use N1 , A1 and L1
throughout the paper as a running-example.
3 Regions
The concept of regions forms the basis of region theory within Petri net synthesis. Given
an event log L over a set of activities A, language-based regions are used to represent
b e
a d g
p1 p2 p3 p4 p5
c f
Fig. 1: A pure Petri net N1 = (P1 , T1 , W1 ) with P1 = {p1 , p2 , ..., p5 }, T1 = {a, b, ...,
g} and W1 (p1 , a) = W1 (a, p2 ) = ... = W1 (p5 , g) = 1.
50
places in a resulting Petri net N = (P, A, W ). A language-based region maps every
a ∈ A to an integer representing arc-weight. For such mapping over A to be a region
we pose the restriction that the corresponding place p ∈ P should not block any σ ∈ L,
i.e., σ ∈ L ⇒ σ ∈ L(N ). We identify two basic definitions of language-based regions
which we classify as single variable-based regions and dual variable-based regions.
The main difference is the number of variables used to define a region.
Definition 5 (Single variable-based regions). Let L be an event log over a set of ac-
tivities A. Let m ∈ N and let ~v ∈ Z|A| . A pair r = (m, ~v ) is a single variable-based
region iff:
∀σ∈L (m + p~(σ)|~v ≥ 0) (3.1)
Let Rs (L) denote the set of all possible single variable-based regions of L. Equation 3.1
generates a set of linear inequalities, i.e. applying Equation 3.1 on L1 yields:
m ≥0
m+~ v (a) ≥0 hai
m+~ v (a) + ~ v (b) ≥0 ha, bi
. . .
. . .
. . .
m+~
v (a) + ~
v (b) + ~
v (d) + 2~ v (e) + ~ v (g) ≥ 0 ha, b, d, e, f, e, gi
v (f ) + ~
m+~
v (a) + ~
v (c) + ~
v (d) + 2~ v (e) + ~ v (g) ≥ 0 ha, c, d, e, f, e, gi
v (f ) + ~
Single variable-based regions use one single decision variable for each a ∈ A,
represented by ~v ∈ Z|A| . Expressing a single variable-based region r = (m, ~v ) as
a place p ∈ P in a marked net (N, M0 ) with N = (P, A, W ) is straightforward.
We have M0 (p) = m, if ~v (a) > 0 then W (a, p) = ~v (a), if ~v (a) < 0 then W (p,
a) = −~v (a) and if ~v (a) = 0 then W (a, p) = W (p, a) = 0. Consider place p2 depicted
in Figure 1 which can be represented as a single variable-based region r = (m, (~v (a),
~v (b), ..., ~v (g))) = (0, (1, −1, −1, 0, 0, 0, 0)). Note that for each inequality generated by
Equation 3.1, place p2 has a value of at least 0 and hence is a member of Rs (L).
Single variable-based regions only allow us to synthesize/discover pure Petri nets.
As a consequence we can not find self-loops, i.e. we can not find a place p in a resulting
net N = (P, A, W ) s.t. p ∈ •a∩a•, for any a ∈ A. A lot of workflow patterns [5] in fact
exhibit places that include self-loops, e.g. milestone patterns, mutual-exclusion patterns,
priority patterns etc. Hence, we define dual variable-based regions which explicitly
allow us to distinguish between incoming and outgoing arcs.
Definition 6 (Dual variable-based regions). Let L be an event log over a set of activ-
ities A. Let m ∈ N and ~x, ~y ∈ N|A| . A triple r = (m, ~x, ~y ) is a dual variable-based
region iff:
∀σ=σ0 ·hai∈L (m + p~(σ 0 )| ~x − p~(σ)| ~y ≥ 0) (3.2)
Let Rd (L) denote the set of all possible dual variable-based regions of L. Like Defini-
tion 5, Definition 6 generates a set of linear inequalities. Applying Definition 6 on L1
yields:
m−~ y (a) ≥0 hai
m−~ y (a) + ~ x(a) − ~
y (b) ≥0 ha, bi
m−~ y (a) + ~ x(a) − ~
y (c) ≥0 ha, ci
. . .
. . .
. . .
m−~ x(a) − ~
y (a) + ~ x(b) − ~
y (b) + ~ x(d) − 2~
y (d) + ~ x(e) − ~
y (e) + 2~ x(f ) − ~
y (f ) + ~ y (g) ≥ 0 ha, b, d, e, f, e, gi
m−~ x(a) − ~
y (a) + ~ x(c) − ~
y (c) + ~ y (d) + ~x(d) − 2~ x(e) − ~
y (e) + 2~ x(f ) − ~
y (f ) + ~ y (g) ≥ 0 ha, c, d, e, f, e, gi
51
Dual variable-based regions use two decision variables per a ∈ A, represented by
~x, ~y ∈ N|A| . The variables allow us to distinguish between incoming arcs and outgoing
arcs when translating regions to Petri nets. Expressing a dual variable-based region
r = (m, ~x, ~y ) as a place p ∈ P in marked net (N, M0 ) with N = (P, A, W ) is again
straightforward. We have M0 (p) = m, W (a, p) = ~x(a) and W (p, a) = ~y (a). Again
consider place p2 depicted in Figure 1 which can be represented as a dual variable-based
region r = (m, (~x(a), ~x(b), ..., ~x(g)), (~y (a), ~y (b), ..., ~y (g))) = (0, (1, 0, 0, 0, 0, 0, 0),
(0, 1, 1, 0, 0, 0, 0)). Verify that for each linear in-equality generated by Definition 6,
place p2 has a value of at least 0 and hence is a member of Rd (L).
4 Hybrid Variable-Based Regions in Process Discovery
Using dual variable-based regions allows us to express non-pure places, i.e, self-loops,
milestones etc. However, this type of regions uses roughly twice as many variables
compared with single variable-based regions. To balance the number of variables used,
though still enhance the possibility of finding non-pure Petri net structures, we intro-
duce the new concept of hybrid regions, capturing both single and dual variable-based
regions.
Definition 7 (Hybrid variable-based regions). Let L be an event log over a set of
activities A. Let As , Ad ⊆ A be two sets of activities with As ∪ Ad = A and As ∩ Ad =
∅. Let m ∈ N, ~v ∈ Z|As | and ~x, ~y ∈ N|Ad | . A quadruple r = (m, ~v , ~x, ~y ) is a hybrid
variable-based region iff:
∀σ=σ0 ·hai∈L (m + p~As (σ)|~v + p~Ad (σ 0 )| ~x − p~Ad (σ)| ~y ≥ 0) (4.1)
Given a set of activities A and two sets of activities As , Ad ⊆ A with As ∪ Ad = A and
As ∩ Ad = ∅, we refer to a hybrid partition of A. If we choose Ad = A, Equation 4.1
is equal to Equation 3.2. If we choose As = A, Equation 4.1 can be reformulated as:
∀σ∈L\{} (m + p~(σ)|~v ≥ 0) (4.2)
Equation 4.2 does not equal Equation 3.1, however, as p~() = ~0 and m ∈ N, the
equations are equivalent in this context.
Note that the set of hybrid variable-based regions, i.e. the set of variable assignments
that adhere to Definition 7 depends on the hybrid partition of A into As and Ad . There-
fore, we let As act as a parameter for the set of feasible hybrid variable-based regions.
h
Let RA s
(L) denote the set of all possible hybrid variable-based regions of L where As
h
represent a hybrid partition of A. Note RA (L) = Rs (L) and R∅h (L) = Rd (L). Region
r = (0, ~0, ~0, ~0) is deemed the trivial region.
All three language-based region definitions, i.e. single, dual and hybrid variable-
based regions, provide means to accept and/or reject potential places in a to be con-
structed Petri net. In classical Petri net synthesis approaches, one keeps looking for
feasible places until either L = L(N ), or if this is impossible, L(N ) \ L is minimized.
Unfortunately, most models returned by classical Petri net synthesis techniques result
in models that are unusable from a process discovery perspective. Hence, we need to
relax the strict formal requirements posed on the relation between L and L(N ).
52
Definition 8 (Hybrid variable-based process discovery ILP-formulation). Let L be
an event log over a set of activities A and let As , Ad ⊆ A be a hybrid partition. Let
Ms , Md , M0d be three matrices where Ms is an |L| \ {} × As matrix with Ms (σ,
a) = p~(σ)(a) and Md , M0d are two |L| \ {} × Ad matrices with Md (σ, a) = p~(σ)(a)
and M0d (σ, a) = p~(σ 0 )(a) (where σ = σ 0 · ha0 i ∈ L). Let cm ∈ R, c~v ∈ R|As | and
c~x , c~y ∈ R|Ad | . The hybrid variable-based process discovery ILP-formulation, denoted
ILPLh , is defined as:
minimize z = cm m + c~v |~v + c~x | ~x + c~y | ~y objective function
such that m~1 + Ms~v + M0d ~x − Md ~y ≥ ~0 hybrid variable-based region
and ~ ≤ ~v ≤ ~1 i.e. ~v ∈ {−1, 0, 1}|As |
−1
~0 ≤ ~x ≤ ~1 i.e. ~x ∈ {0, 1}|Ad |
~0 ≤ ~y ≤ ~1 i.e. ~y ∈ {0, 1}|Ad |
0 ≤ m ≤ 1 i.e. m ∈ {0, 1}
The ILP-fromulation presented in Definition 8 uses the set of linear in-equalities
generated by Equation 4.1 within its constraint body. The formulation however binds
~v to {−1, 0, 1}|As | and ~x, ~y to {0, 1}|Ad | , i.e. the formulation only allows for discover-
ing Petri nets with arc weights restricted to {0, 1}. Additionally it defines an objective
function, i.e. z = cm m + c~v |~v + c~x | ~x + c~y | ~y , that maps each region to a real value,
h
i.e. z : RA s
(L) → R. In general we are free to choose whatever objective function
we like, however, using different objective functions will lead to different process dis-
covery results. Choosing cm = 0 and ~cv = ~cx = ~cy = ~1 leads to arc minimization
whereas maximizing the same objective leads to arc maximization, resulting in differ-
ent places/regions found by the underlying ILP solver. The objective function proposed
in [3], being a minimization function, tries to minimize the number of incoming arcs
and maximize the number of outgoing arcs. The P objective functionP can be defined in
terms of cm , c~v , c~x and c~y as cm = |L|, c~v = σ∈L p~As (σ), c~x = σ∈L p~Ad (σ) and
c~y = −c~x , i.e.:
X
z(r) = (m + p~As (σ)|~v + p~Ad (σ)| (~x − ~y )) (4.3)
σ∈L
4.1 Optimizing Token Throughput
The objective function used within [3], i.e. Equation 4.3 is less generic as the one pro-
posed in Definition 8. As shown in [3], it favors minimal regions. A minimal region is
a region that is not expressible as the sum of two other regions. The objective function
is solely based on the set-representation of the prefix-closure of an event log. However,
an event log is a bag of traces and thus consists of information on trace frequency. We
propose a generalized prefix-closure-based objective function that incorporates a word-
based scaling function β. The scaling function β is required to map all sequences in the
prefix-closure of the event log to some positive real value. The actual implementation
is up to the user, although we present an instantiation of β that works well for process
discovery. We show that the proposed generalized weighted prefix-closure-based hybrid
region objective function favors minimal regions, given any scaling function β.
53
Definition 9 (Generalized weighted prefix-closure-based hybrid region objective
function). Let L be an event log over a set of activities A and let As , Ad ⊆ A be a
h
hybrid partition. Let r = (m, ~v , ~x, ~y ) ∈ RA s
(L) be a hybrid variable-based region and
let β be a scaling function over L, i.e. β : L → R+ . The generalized weighted P prefix-
closure-based
P hybrid region objective
P function is instantiated as c m = σ∈L β(σ),
c~v = σ∈L β(σ)~ pAs (σ), c~x = σ∈L β(σ)~ pAd (σ) and c~y = −c~x , i.e.:
X
zβ (r) = β(σ)(m + p~As (σ)|~v + p~Ad (σ)| (~x − ~y )) (4.4)
σ∈L
Note that if we choose β(σ) = 1 for all σ ∈ L, denoted β1 , we instantiate the gen-
eralized objective function as the objective function proposed in [3]. We denote this
objective function as z1 , i.e. Equation 4.3.
To relate the behavior in a given event log to the objective function defined in Defi-
nition 9 we instantiate the scaling function β making use of the frequencies of the traces
present in the event log, i.e. we let β(σ) = L(σ) leading to:
X
zL (r) = L(σ)(m + p~As (σ)|~v + p~Ad (σ)| (~x − ~y )) (4.5)
σ∈L
To assess the difference between z1 and the newly proposed objective function zL ,
consider the Petri net depicted in Figure 2. Assume we are given some event log L =
[ha, b, di5 , ha, c, di3 ]. Let r1 denote the hybrid variable-based region corresponding to
place p1 , let r2 correspond to p2 and let r3 correspond to p3 . In this case we have
z1 (r1 ) = 1, z1 (r2 ) = 1 and z1 (r3 ) = 2. On the other hand we have zL (r1 ) = zL (r2 ) =
zL (r3 ) = 5 + 3 = 8. Thus, using zβL leads to more intuitive objective values compared
to using z1 as zL evaluates to the absolute number of discrete time-steps a token would
remain in the corresponding place when replaying log L w.r.t. the place.
In [3] it is shown that the objective function used favors minimal regions. The proof
cannot directly be adapted to hold for hybrid variable-based regions. Moreover it does
not provide means to show that any arbitrary instantiation of zβ favors minimal hy-
brid variable-based regions. Here we show that any instantiation of the generalized
weighted prefix-closure-based hybrid region objective function with some scaling func-
tion β : L → R+ favors minimal hybrid variable-based regions. We first show that the
objective value of a non-minimal hybrid region equals the sum of the two minimal re-
gions defining it after which we show that the given objective function maps each region
to some positive real value, i.e. rng(zβ ) ⊆ R+ .
b
a d
p1 p2 p3
c
Fig. 2: A simple Petri net N with L(N ) = {, hai, ha, bi, ha, ciha, b, di, ha, c, di}.
54
Lemma 1 (Objective value composition of non-minimal regions). Let L be an event
log over a set of activities A and let As , Ad ⊆ A be a hybrid partition. Let r1 = (m1 ,
~v1 , ~x1 , ~y1 ), r2 = (m2 , ~v2 , ~x2 , ~y2 ) and r3 = (m1 +m2 , ~v1 +~v2 , ~x1 +~x2 , ~y1 +~y2 ) with r1 ,
h h
r2 , r3 ∈ RA s
(L). Let zβ : RA s
(L) → R where zβ is an instantiation of the generalized
weighted objective function as defined in Definition 9, then zβ (r3 ) = zβ (r1 ) + zβ (r2 ).
Proof (By definition of zβ ). Let us denote zβ (r3 ):
X
β(σ)((m1 + m2 ) + p~As (σ)| (v~1 + v~2 ) + p~Ad (σ)| ((x~1 + x~2 ) − (y~1 + y~2 )))
σ∈L
X
pAs (σ)| v~1 +~
β(σ)(m1 +~ pAd (σ)| (x~1 − y~1 )+m2 +~
pAs (σ)| v~2 +~
pAd (σ)| (x~2 − y~2 ))
σ∈L
X
β(σ)(m1 + p~As (σ)| v~1 + p~Ad (σ)| (x~1 − y~1 )) +
σ∈L
X
β(σ)(m2 + p~As (σ)| v~2 + p~Ad (σ)| (x~2 − y~2 ))
σ∈L
Clearly zβ (r3 ) = zβ (r1 ) + zβ (r2 ).
Lemma 1 shows that the value of zβ for a non-minimal region equals the sum of the
zβ values of the two regions it is composed of. If we additionally show that zβ can
only evaluate to positive values, we show that zβ favors minimal hybrid variable-based
regions.
Lemma 2 (Range of zβ is strictly positive). Let L be an event log over a set of activ-
ities A and let As , Ad ⊆ A be a hybrid partition. Let r = (m, ~v , ~x, ~y ) be a non-trivial
h
region, i.e., r ∈ RA s
(L). If we let zβ be any instantiation of the generalized weighted
h
objective function as defined in Definition 9, then zβ : RA s
(L) → R+ .
h
Proof (By showing zβ (r) > 0, ∀r ∈ RA s
(L)). Let r = (m, ~v , ~x, ~y ) be a non-trivial
h h
hybrid variable-based region, i.e. r ∈ RAs (L). Because r ∈ RA s
(L) we have
∀σ=σ0 ·hai∈L\{} (m + p~As (σ)|~v + p~Ad (σ 0 )| ~x − p~Ad (σ)| ~y ≥ 0) (4.6)
Note that each Parikh value of an activity a ∈ A given a sequence σ, i.e. p~(σ)(a),
is greater or equal than the Parikh value of a, given σ’s prefix, i.e.,:
p(σ)(a) ≥ p~(σ 0 )(a))
∀σ=σ0 ·ha0 i∈L,a∈A (~ (4.7)
Using Equation 4.7 we can substitute p~Ad (σ 0 )| ~x with p~Ad (σ)| ~x in Equation 4.6:
∀σ=σ0 ·hai∈L\{} (m + p~As (σ)|~v + p~Ad (σ)| (~x − ~y ) ≥ 0) (4.8)
Combining rng(β) ⊆ R+ , p~() = ~0 and m ∈ N with Equation 4.8 we find zβ (r) ≥ 0:
X
β(σ)(m + p~As (σ)|~v + p~Ad (σ)| (~x − ~y )) ≥ 0 (4.9)
σ∈L
55
If m > 0 then β()(m+~ pAs ()|~v +~
pAd ()| (~x −~y )) > 0. Combined with Equations 4.8
and 4.9 leads to zβ (r) > 0.
Observe that if m = 0 then for r to be a non-trivial hybrid variable-based region,
h
i.e. r ∈ RA s
(L), either (I). ∃a ∈ As s.t. ~v (a) > 0 or (II). ∃a ∈ Ad s.t. ~x(a) > 0.
(I). Let m = 0 and a ∈ As s.t. ~v (a) > 0. We know ∃σ = σ 0 · hai ∈ L. Because
h
r ∈ RA s
(L) (using Equation 4.8) we have:
m + p~As (σ)|~v + p~Ad (σ)| (~x − ~y ) ≥ 0
If σ 0 = , we have p~Ad (σ) = ~0 and p~As (σ)|~v = ~v (a) hence we deduce:
m + p~As (σ)|~v + p~Ad (σ)| (~x − ~y ) > 0
Combining this with Equations 4.8 and 4.9 yields zβ (r) > 0.
If σ 0 6= we have (using Equation 4.8):
m + p~As (σ 0 )|~v + p~Ad (σ 0 )| (~x − ~y ) ≥ 0
Observe that p~As (σ)|~v = p~As (σ 0 )|~v + ~v (a), together with p~Ad (σ 0 ) = p~Ad (σ) leads us
to reformulate this to:
m + p~As (σ)|~v − ~v (a) + p~Ad (σ)| (~x − ~y ) ≥ 0
m + p~As (σ)|~v + p~Ad (σ)| (~x − ~y ) ≥ ~v (a)
Combining this with Equations 4.8 and 4.9 yields zβ (r) > 0.
(II) Let m = 0 and a ∈ Ad s.t. ~x(a) > 0. We know ∃σ = σ 0 · hai ∈ L. Because
h
r ∈ RA s
(L) (using Equation 4.6) we have:
m + p~As (σ)|~v + p~Ad (σ 0 )| ~x − p~Ad (σ)| ~y ≥ 0
Observe that p~Ad (σ)| ~x = p~Ad (σ 0 )| ~x + ~x(a) and thus:
m + p~As (σ)|~v + p~Ad (σ)| (~x − ~y ) ≥ ~x(a)
Combining this with Equations 4.8 and 4.9 yields zβ (r) > 0.
By combining Lemma 1 and Lemma 2 we can easily show that any instantiation of
zβ favors minimal regions.
Theorem 1 (Any instantiation of zβ favors minimal regions). Let L be an event log
over a set of activities A and let As , Ad ⊆ A be a hybrid partition. Let r1 = (m1 ,
~v1 , ~x1 , ~y1 ), r2 = (m2 , ~v2 , ~x2 , ~y2 ) and r3 = (m1 + m2 , ~v1 + ~v2 , ~x1 + ~x2 , ~y1 + ~y2 ) be
h h
three non-trivial regions, i.e., r1 , r2 , r3 ∈ RA s
(L). For any zβ : RA s
(L) → R being an
instantiation of the generalized weighted objective function as defined in Definition 9:
zβ (r3 ) > zβ (r1 ) and zβ (r3 ) > zβ (r2 ).
Proof (By composition of Lemma 1 and Lemma 2). By Lemma 1 we know zβ (r3 ) =
zβ (r1 ) + zβ (r2 ). By Lemma 2 we know that zβ (r1 ) > 0, zβ (r2 ) > 0 and zβ (r3 ) > 0.
Thus we deduce zβ (r3 ) > zβ (r1 ) and zβ (r3 ) > zβ (r2 ). Consequently, any instantiation
of the objective function as defined in Definition 9 favors minimal regions.
56
Both objective functions presented, i.e.z1 and zL , are expressible in terms of the more
general objective function zβ as presented in Definition 9. As we have seen the two
objective functions may favors different regions. Combining an objective function with
the ILP-formulation presented in Definition 8 establishes means to find Petri net places.
However, solving one ILP only yields one solution and hence we need means to find a
set of places, which together form a Petri net that represents the input event log L.
4.2 Finding Several Places
The most apparent technique to find multiple places is the use of causal relations within
an event log. Within the context of this paper we define a causal relation as follows.
Definition 10 (Causal relation). Let L be an event log over a set of activities A. A
causal relation γL is a function γL : A × A → R where γL (a, b) denotes the causality
between activity a and b exhibited in L.
Several approaches exist to compute causalities hence we refer to [6] for an overview of
the use of causalities within different process discovery approaches. As a consequence,
γL (a, b) can have different meanings w.r.t. the causality between a and b. Some ap-
proaches limit rng(γL ) to {0, 1} where γL (a, b) = 1 means that there is a causal
relation between a and b whereas γL ((a, b)) = 0 means there is no causal relation from
a to b. Other approaches map rng(γL ) to the real-valued domain (−1, 1) where a high
positive γL (a, b) value (close to 1) indicates a strong causal relation from a to b and a
low negative value (close to −1) indicates a strong causal relation from b to a.
When adopting a causal-based ILP process discovery strategy, we try to find places
which will be added in the resulting Petri net, each representing a causality found. A
first step is to compute γL values given some causal definition. Depending on the actual
meaning of the γL , whenever we find a causal relation from a to b (possibly because
γL (a, b) ≥ δ, where δ is some threshold value), we enrich the constraint body for the
given causal constraint as follows:
m = 0 and ~v (a) = 1 and ~v (b) = −1, if a, b ∈ As
m = 0 and ~x(a) = 1 and ~v (b) = −1, if a ∈ Ad , b ∈ As
m = 0 and ~v (a) = 1 and ~y (b) = 1, if a ∈ As , b ∈ Ad
m = 0 and ~x(a) = 1 and ~y (b) = 1, if a, b ∈ Ad
After the constraint body is enriched, we solve the ILP yielding a place having an opti-
mal value for the specific objective function chosen. We repeat the procedure for every
causal relation yielding a Petri net.
5 Performance
The hybrid variable-based ILP-formulation is implemented as a plug-in in the ProM-
Framework (http://www.promtools.org) [7]2 . The plug-in allows the user to
2
The source-code is available at https://svn.win.tue.nl/repos/prom/
Packages/HybridILPMiner/Trunk
57
specify parameters of ILP-based process discovery, e.g. several different objective func-
tions, additional constraints and causality based mining.
To test the performance of hybrid variable-based ILP process discovery we have
used the basic implementation within an experimentation framework3 . The framework
allows for generating random process models and from these models generate event
logs. We have generated 40 models containing a minimum of 2 activities and a maxi-
mum of 12 activities. For each model we have generated 10 event logs, each containing
5000 traces. For each log we ran three different instantiations of the process discovery
formulation, one purely single variable-based, one hybrid variant and one purely dual
variable-based. The distribution of event classes in A over As and Ad is depicted in
Table 2. For the hybrid variant the size of As was kept constant and independent of the
number of activities in A (as of |A| ≥ 3). We ran each instantiation 10 times per log
using causal relations as a process discovery strategy. For each run of an instantiation
we calculated the total time spend in solving all ILPs based on the causalities present
in the event log. These times have been aggregated based on the number of activities
present in an event log. The results of the experiment, plotted on a logarithmic scale,
are depicted in Figure 34 .
As shown in Figure 3, the average time to solve the hybrid formulation is in-between
the single and dual formulation. We additionally note the hybrid formulation to get
slightly closer to the dual formulation when |A| increases. This is as expected as the
number of single variables within the hybrid formulation is constant and hence the av-
erage time of solving the ILPs within the formulation increases with respect to the single
variable formulation. Figure 3 shows that reducing the number of variables used within
the ILP-formulation has an impact on the average time of solving ILPs. The differences
are however marginal, which is to be expected as solving ILPs is exponential by nature.
Therefore the experiments show that using ILPs for the aim of process discovery in
Table 2: Different settings used in performance measurements of the hybrid variable-
based ILP-formulation.
|A| 2 3 4 5 6 7 8 9 10 11 12
Purely single variable-based variant
|As | 2 3 4 5 6 7 8 9 10 11 12
|Ad | 000 00 00 0 0 0 0
Hybrid variable-based variant
|As | 233 33 33 3 3 3 3
|Ad | 001 23 45 6 7 8 9
Purely dual variable-based variant
|As | 000 00 00 0 0 0 0
|Ad | 2 3 4 5 6 7 8 9 10 11 12
3
All framework files and results can be found at https://svn.win.tue.nl/repos/
prom/Packages/HybridILPMiner/Tags/papers/source_files/hybrid_
ilp_runtime_experiments.tar.gz
4
The experiments where distributed over four servers (Dell PowerEdge R520, Intel Xeon E5-
2407 v2 2.40GHz, 10M Cache, 8 × 8GB RDIMM, 1600MT/s Memory), on each server a total
of 10 models and corresponding logs where generated.
58
Avg. time of solving ILP 0 s (ms.)
105
Pure single
Hybrid
Pure dual
102
10−1
2 3 4 5 6 7 8 9 10 11 12
|A|
Fig. 3: Average time in milliseconds to solve the three ILP-based process discovery
variants plotted on a logarithmic scale against the number of activities in the log.
a practical setting might need incorporation of more advanced techniques in order to
reduce the average time of solving the ILPs significantly.
6 Related Work
The concept of hybrid variable-based regions originates from language-based region
theory, which in turn originates from the area of Petri net synthesis. We identify two
main branches of language-based region theory within Petri net synthesis being the
separating regions approach [8–10] and the minimal linear basis approach [11, 12]. In
the separating regions approach, which uses single-variable based regions, behavior not
seen in a given prefix closed language is specified as being undesired. In the minimal
linear basis approach, given a prefix closed language, a polyhedral cone of integer points
is constructed based on dual variable-based regions. Using the cone a minimal basis of
the set of regions is calculated which defines a minimal set of places to be synthesized.
Both approaches try to minimize L(N ) \ L, where N represents the resulting Petri
net and L is a prefix-closed language. The approaches lead to Petri nets with perfect
replay-fitness. Moreover precision is maximized. A side effect of this property is the
fact that the synthesized net N scores low on both the generalization and the simplicity
dimension.
In [3] a first design of an ILP-formulation was presented based on the concept of
dual variable-based regions. The work presents objective function z1 which we have
further developed in this work to zL , and more generally, zβ . The work also focuses on
formulation of several different net-types in terms of linear in-equalities which even go
beyond classical Petri nets, e.g. reset- and inhibitor arcs.
An alternative approach is to use the concept of state-based regions for the purpose
of process discovery [13, 14]. Within this approach an abstraction of the event log is
computed in the form of a transition system. Regions are computed within the transition
system where, like in language-based region theory, each region corresponds to a place
in the resulting Petri net.
59
In [15] a process discovery algorithm is proposed based on the concept of numer-
ical abstract domains using Parikh vectors as a basis. Based on an event log, a prefix-
closed language is computed of which a convex polyhedron is approximated by means
of calculating a convex hull. The convex hull is then used to compute causalities within
the input log, by deducing a set of linear inequalities which represent places. The for-
mulation used to calculate these causalities is in essence based the concept of single
variable-based regions. The approach allows for finding pure Petri nets with arc weights
and multiple marked places.
A multitude of other Petri net-based process discovery approaches exist. For a de-
tailed description of these approaches we refer to [6].
7 Conclusion
We presented a new breed of language-based regions, i.e. hybrid variable-based regions,
that captures the two existing region types being single and dual variable-based regions.
Hybrid variable-based regions allow us to decide whether we want to use one or two
variables for an activity present in the input event log. This allows us to achieve gains
in terms of performance whilst maintaining the possibility to find complex (workflow)
patterns. We have shown that within the hybrid variable-based ILP process discovery
formulation, using only one variable per activity a ∈ A performs optimal in terms of
the average time spent in solving the ILPs constructed.
We presented a generalized weighted objective function and showed that any in-
stantiation of the objective function leads to ILPs that favor minimal regions. As a
result, practitioners may vary the scaling function within the objective function under
the guarantee that the objective function favors minimal regions. We presented a log-
based scaling function that exploits trace frequencies available in the input log. Using
the log based scaling function within the objective function assigns an objective value
to each region equal to the token throughput of the corresponding place, given the event
log. Hence, as we have shown using the new objective function leads to more intuitive
objective values.
As an interesting direction for future work we identify the assessment of the impact
of filtering, either a-priori or within the ILP itself, on the quality dimensions of the
resulting nets, i.e. are we able to leverage the perfect repaly-fitness property? Also,
an assessment of the impact of decomposition techniques [16] on the performance of
ILP-based approaches is an interesting direction for future work.
References
1. Aalst, W.M.P.v.d.: Process Mining: Discovery, Conformance and Enhancement of Business
Processes. 1st edn. Springer Publishing Company, Incorporated (2011)
2. Desel, J., Reisig, W.: The synthesis problem of Petri nets. Acta Inf. 33(4) (1996) 297–315
3. Werf, J.M.E.M.v.d., Dongen, B.F.v., Hurkens, C.A.J., Serebrenik, A.: Process discovery
using integer linear programming. Fundamenta Informaticae 94(3) (2009) 387–412
4. Buijs, J.C.A.M., Dongen, B.F.v., Aalst, W.M.P.v.d.: On the role of fitness, precision, gen-
eralization and simplicity in process discovery. In Meersman, R., Panetto, H., Dillon, T.,
60
Rinderle-Ma, S., Dadam, P., Zhou, X., Pearson, S., Ferscha, A., Bergamaschi, S., Cruz, I.F.,
eds.: On the Move to Meaningful Internet Systems: OTM 2012. Volume 7565 of Lecture
Notes in Computer Science. Springer Berlin Heidelberg (2012) 305–322
5. Aalst, W.M.P.v.d., Hofstede, A.H.M.t., Kiepuszewski, B., Barros, A.: Workflow patterns.
Distributed and Parallel Databases 14(1) (2003) 5–51
6. Dongen, B.F.v., Medeiros, A.K.A.d., Wen, L.: Process mining: Overview and outlook of
Petri net discovery algorithms. T. Petri Nets and Other Models of Concurrency 2 (2009)
225–242
7. Dongen, B.F.v., Medeiros, A.K.A.d., Verbeek, H.M.W., Weijters, A.J.M.M., Aalst,
W.M.P.v.d.: The ProM framework: A new era in process mining tool support. In Ciardo,
G., Darondeau, P., eds.: Applications and Theory of Petri Nets 2005. Volume 3536 of Lec-
ture Notes in Computer Science. Springer Berlin Heidelberg (2005) 444–454
8. Badouel, E., Bernardinello, L., Darondeau, P.: Polynomial algorithms for the synthesis of
bounded nets. In Mosses, P.D., Nielsen, M., Schwartzbach, M.I., eds.: TAPSOFT ’95: Theory
and Practice of Software Development. Volume 915 of Lecture Notes in Computer Science.
Springer Berlin Heidelberg (1995) 364–378
9. Badouel, E., Darondeau, P.: Theory of regions. In Reisig, W., Rozenberg, G., eds.: Lectures
on Petri Nets I: Basic Models. Volume 1491 of Lecture Notes in Computer Science. Springer
Berlin Heidelberg (1998) 529–586
10. Darondeau, P.: Deriving unbounded Petri nets from formal languages. In Sangiorgi, D.,
Simone, R.d., eds.: CONCUR’98 Concurrency Theory. Volume 1466 of Lecture Notes in
Computer Science. Springer Berlin Heidelberg (1998) 533–548
11. Bergenthum, R., Desel, J., Lorenz, R., Mauser, S.: Process mining based on regions of
languages. In Alonso, G., Dadam, P., Rosemann, M., eds.: Business Process Management.
Volume 4714 of Lecture Notes in Computer Science. Springer Berlin Heidelberg (2007)
375–383
12. Lorenz, R., Mauser, S., Juhas, G.: How to synthesize nets from languages - a survey. In:
Simulation Conference, 2007 Winter. (Dec 2007) 637–647
13. Solé, M., Carmona, J.: Process mining from a basis of state regions. In: Applications and
Theory of Petri Nets, 31st International Conference, PETRI NETS 2010, Braga, Portugal,
June 21-25, 2010. Proceedings. (2010) 226–245
14. Aalst, W.M.P.v.d., Rubin, V., Verbeek, H.M.W., Dongen, B.F.v., Kindler, E., Günther, C.W.:
Process mining: a two-step approach to balance between underfitting and overfitting. Soft-
ware and System Modeling 9(1) (2010) 87–111
15. Carmona, J., Cortadella, J.: Process discovery algorithms using numerical abstract domains.
IEEE Trans. Knowl. Data Eng. 26(12) (2014) 3064–3076
16. Aalst, W.M.P.v.d.: Decomposing Petri nets for process mining: A generic approach. Dis-
tributed and Parallel Databases 31(4) (2013) 471–507
61