Page 193 -

6.4 Region-Based Mining 175

Fig. 6.12 Transition system
TS L 1 ,l 1 state () derived from
3
L 1 =[ a,b,c,d ,
2
a,c,b,d , a,e,d ] using
k
l state (σ,k) = hd (σ)
1

k
l state (σ,k) = ∂ multiset (hd (σ)) =[a 1 ,a 2 ,...,a k ] is a state representation function
3
converting the full history into a multi-set. This function assumes that for the current
state the order of events is not important, only the frequency of activities matters.
3
1
1
1
3

l state (σ ,9) =[a ,b ,c ,d ,e ], i.e., in the state shown in Fig. 6.11 a, b, and e have
3
been executed once and both c and d have been executed three times.
k
l state (σ,k) = ∂ set (hd (σ)) ={a 1 ,a 2 ,...,a k } is a state representation function
4
taking a set representation of the full history. For this state representation function
the order and frequency of activities do not matter. For the current state, it only mat-

ters which activities have been executed at least once. l state (σ ,9) ={a,b,c,d,e}.
4
Functions l state (), l state (), and l state () all consider the full history of the case
1 3 4
after k events: l 1 state () does not abstract from the order and frequency of past ac-
tivities, l state () abstracts from the order, and l state () abstracts from both order and
3 4
frequency. Hence, l 4 state () provides a coarser abstraction than l 1 state (). By defini-
tion l state (σ 1 ,k) = l state (σ 2 ,k) if l state (σ 1 ,k) = l state (σ 2 ,k) (but not the other way
4 4 1 1
around). Function l state () is based on the future rather than the past.
2
Using some state representation function l state (), we can automatically construct
a transition system based on some event log L.
∗
Definition 6.2 (Transition system based on event log) Let L ∈ B(A ) be an event
log and l state () a state representation function. TS L,l state = (S,A,T ) is a transition
()
system based on L and l state () with:
• S ={l state (σ,k) | σ ∈ L ∧ 0 ≤ k ≤|σ|} is the state space.
• A ={σ(k) | σ ∈ L ∧ 1 ≤ k ≤|σ|} is the set of activities.
• T ={(l state (σ,k),σ(k + 1),l state (σ,k + 1)) | σ ∈ L ∧ 0 ≤ k< |σ|} is the set of
transitions.
• S start ={l state (σ,0) | σ ∈ L} is the set of initial states.
• S end ={l state (σ,|σ|) | σ ∈ L} is the set of final states.
3
2
Let us consider event log L 1 =[ a,b,c,d , a,c,b,d , a,e,d ]. Figure 6.12
shows transition system TS state . Consider, for example, a case with trace σ =
L 1 ,l ()
1
a,b,c,d . Initially, the case is in state l 1 state (σ,0) = . After executing a the case
is in state l state (σ,1) = a . After executing b state l state (σ,2) = a,b is reached.
1 1
Executing c results in state l 1 state (σ,3) = a,b,c . Executing the last event d results
in state l state (σ,4) = a,b,c,d . The five states visited by this case are added to the
1
transition system. The corresponding transitions are also added. The same is done
for a,c,b,d and a,e,d , thus resulting in the transition system of Fig. 6.12.