1 Introduction
2 Related work
3 Background
Event-id | Case-id | Activity | Resource | Time-stamp |
---|---|---|---|---|
\(\ldots \)
|
\(\ldots \)
|
\(\ldots \)
|
\(\ldots \)
|
\(\ldots \)
|
5 |
12
|
Decide
(
d
)
|
Boris
|
2017-05-08 09:45
|
6 |
13
|
Register request
(
a
)
|
Luke
|
2017-05-08 10:12
|
7 |
12
|
Update records
(
h
)
|
Harry
|
2017-05-08 10:14
|
8 |
13
|
Examine
(
b
)
|
Harry
|
2017-05-08 10:31
|
9 |
13
|
Check ticket
(
c
)
|
Pete
|
2017-05-08 10:40
|
10 |
13
|
Decide
(
d
)
|
Harry
|
2017-05-08 10:49
|
11 |
13
|
Pay compensation
(
e
)
|
Harry
|
2017-05-08 11:01
|
12 |
14
|
Register request
(
a
)
|
Boris
|
2017-05-08 11:03
|
\(\ldots \)
|
\(\ldots \)
|
\(\ldots \)
|
\(\ldots \)
|
\(\ldots \)
|
3.1 Event logs and process models
3.2 Alignments
4 Computing prefix-alignments on event streams
4.1 Event streams
4.2 Prefix-alignments
5 Computing prefix-alignments incrementally
5.1 An incremental framework
-
Base CaseI: \(i=0\) All alignments are \(\epsilon \).
-
Base CaseII: \(i=1\) Let \((c, a)\) be \(S(i)\). We know \(D_{\mathcal {C}}(c,i-1) = D_{\mathcal {C}}(c,0) = \epsilon \). In case we are able to fire some \(t\) with \(\lambda (t) = a\) in \(M_0\), we obtain alignment \(\langle (a,t)\rangle \), which, under the unit-cost function, is optimal.1 In case \(\not \exists _{t\in T}(\lambda (t) = a)\) we obtain \(\langle (a, \gg ) \rangle \) which is trivially an optimal prefix-alignment for trace \(\langle a \rangle \). In any other case, we compute \(\overline{\alpha }(N, M_i, M_f, \langle a\rangle )\) which is optimal by definition.
-
Induction Hypothesis Let \(i > 1\). For any \(c\in \mathcal {C}\), we assume that for \(\overline{\gamma }= D_{\mathcal {C}}(c,i)\), we have \(\overline{\gamma }\in \overline{\varGamma }\) and \(\overline{\gamma }\) is optimal.
-
Inductive Step We prove that, for any \(c\in \mathcal {C}\), for \(\overline{\gamma }= D_{\mathcal {C}}(c,i+1)\), we have \(\overline{\gamma }\in \overline{\varGamma }\) and \(\overline{\gamma }\) is optimal. Let \((c,a)\) be \(S(i+1)\). In case \(D_{\mathcal {C}}(c, i) = \epsilon \) we know that \(\overline{\gamma }\) is optimal (Base Case\(i=1\)). Let \(D_{\mathcal {C}}(c, i) = \overline{\gamma }'\) s.t. \(\overline{\gamma }' \ne \epsilon \). In case we are able to fire some \(t\) with \(\lambda (t) = a\) in \(M_0\) we obtain \(\overline{\gamma }= \overline{\gamma }' \cdot \langle (a,t)\rangle \). Since, under unit-cost function, \(\delta (a,t) = 0\), if \(\overline{\gamma }\) is non-optimal, then also \(\overline{\gamma }'\) is non-optimal which contradicts the IH. A similar rationale holds in case \(\not \exists _{t\in T}(\lambda (t) = a)\). In any other case, we compute \(\overline{\alpha }(N, M_i, M_f, \sigma \cdot \langle a\rangle )\) which is optimal by definition.\(\square \)
5.2 Parametrization
5.2.1 Cost upper-bounds
5.2.2 Limiting the search
5.3 Administering cases in finite memory
6 Evaluation
RapidProM
[21] extension for RapidMiner
.2 As a search algorithm, we use a the \(A^*\) algorithm provided by hipster4j
[22]. To evaluate the proposed algorithm, we generated several process models with different characteristics, i.e. different degrees of parallelism, choice and loops. Additionally we evaluated our approach using real event data, related to the treatment of hospital patients suspected of having sepsis. In this experiment, we additionally compare computing prefix-alignments with repeatedly computing conventional alignments on an event stream.6.1 Experimental set-up
RapidProM
which, conceptually, performs the following steps:Parameter | Type | Values |
---|---|---|
Use Upper-Bound | Boolean
| true , false |
Window Size | Integer
|
\(\{1,2,3,4,5,10,20,\infty \}\)
|
6.2 Results
6.2.1 Cost upper-bounds
6.2.2 Reverting alignments
6.3 Evaluation using real event data
-
If the difference of the current (prefix-)alignment cost with the eventual alignment cost is zero, and the eventual costs exceed zero, we define a True Positive, i.e. we have an exact estimate of non-compliant behaviour.
-
If the difference of the current (prefix-)alignment cost with the eventual alignment cost is greater than zero, we define a False Positive, i.e. we overestimate non-compliant behaviour.
-
If the difference of the current (prefix-)alignment cost with the eventual alignment cost is zero, and the eventual costs equals zero, we define a True Negate, i.e. we have an exact estimate of the fact that no deviation occurs.
-
If the difference of the current (prefix-)alignment cost with the eventual alignment cost is lower than zero, we define a False Negative, i.e. we underestimate non-compliant behaviour.
Variant | Window \(\sim \) 5 | Window \(\sim \) 10 | Window \(\sim \) 20 | Conventional |
---|---|---|---|---|
×
|