Vol-3170/poster4
Jump to navigation
Jump to search
Paper
| Paper | |
|---|---|
 edit
| |
| description | |
| id | Vol-3170/poster4 |
| wikidataid | →Q117351499 |
| title | Trace Language: Mining Micro-configurations from Process Transition Traces |
| pdfUrl | https://ceur-ws.org/Vol-3170/poster4.pdf |
| dblpUrl | https://dblp.org/rec/conf/apn/ShivhareJ22 |
| volume | Vol-3170→Vol-3170 |
| session | → |
Trace Language: Mining Micro-configurations from Process Transition Traces
Trace Language: Mining Micro-configurations from Process
Transition Traces
Karnika Shivhare1 , Rushikesh K Joshi1
1
Department of Computer Science and Engineering, Indian Institute of Technology Bombay, Mumbai - 400 076, India.
Abstract
The paper presents Trace Language, a language for compact encoding of process trace sets. Thirteen micro-configurations
are proposed and tested over a few process mining algorithms to identify success and failure points of the latter. Trace
expressions are developed for the micro-configurations using Trace Language.
Keywords
Micro-configurations, Patterns, Petri Nets, Process Mining, Process Models, Traces, Trace Language.
1. Introduction 𝑎 ‖ 𝑏 represents trace set with two possible traces {ab, ba}
A process is a progression of activities, and its exe- and 𝑎𝑏 ‖ 𝑝𝑞 represents trace set {abpq, apbq, apqb, pqab,
cution stamps footprints in form of series of triggered pabq, paqb}. In the operators below, the operands can be
transitions as the process progresses. These footprint individual transitions or composites defined by chronicle
trails are known as traces, which together form a trace orderings. Chronicle Ordering is the default operator if
set corresponding to the set of traces generated out of there is no operator specified, as in trace abcd, which
multiple executions of the process. Process Mining algo- represents 𝑎 → 𝑏 → 𝑐 → 𝑑.
rithms routinely use trace sets to recover or build process Swapper (∦) It operates on chronicle orderings as
models from them. We observed that there are certain in- operands, treating them as atomic (indivisible) substrings.
herent patterns among processes which we call as micro- It concatenates them in both permutations to represent
configurations, that get over-passed by process mining two possible traces. For example, 𝑎 ∦ 𝑏 represents trace
algorithms and stand as fracture points for them. At this set {ab, ba} and 𝑎𝑏𝑐 ∦ 𝑝𝑞𝑟 represents trace set {abcpqr,
stretch, realizing the need of a language that can repre- pqrabc}. The operator is commutative but not associative.
sent trace sets compactly, help in automating implemen- Bowtie operator (◁▷) This operator represents a gener-
tations and serve as basis for refinements and improve- ator of two particularly fashioned traces that are struc-
ments in mining algorithms, we propose a compact novel tured as ordered and pairwise concatenations of tran-
trace language. It serves the purpose of trace set genera- sition sequences sandwiching the common transition
tor when used for representing micro-configurations. sequence. The common transition sequence is written
The paper first expounds the operators of the Trace as superscript on the operator symbol. For example,
Language, followed by a discussion of results enlist- < 𝑎, 𝑏 >◁▷𝑐 < 𝑑, 𝑒 > produces two traces {acd, bce}.
ing Trace Language expressions for thirteen micro- The operator is neither commutative nor associative.
configurations which were tested over five process min- m-Subsequence Operator (S𝑚 ) This operator repre-
ing algorithms in the Python (pm4py) framework [1]. sents all valid subsequences of length m for the given
The algorithms tested are Alpha Mining [2], Alpha(+) unary operand that represents a sequence of chronicle
miner [3], Heuristics Miner [4], Inductive Miner [5] and orderings. The subsequences are valid if they are in grow-
Directly-Follows Graphs (DFG) [6]. ing sequence of chronicles. For example, S2 < 𝑥𝑦𝑧 >
2. Trace Language Operators represents traces {xy, xz, yz}. With m as 1, the operator
Chronicle Ordering (→), Alternative (⋊), Concur- functions as a shredder that creates all traces of length 1.
rent (‖) These are basic operations of sequence, choice For example, S1 < 𝑥𝑦𝑧 > represents traces {x, y, z}.
and parallel composition. For example, 𝑎 → 𝑏 → 𝑐 any-Subsequence Operator (S𝑎𝑛𝑦 ) This unary opera-
represents trace set with single trace {abc}, 𝑎 ⋊ 𝑝𝑞𝑟 rep- tor represents all subsequences that are in growing se-
resents trace set with two possible traces {a, pqr}, and quence of chronicle orderings of the operand. For exam-
ple, S𝑎𝑛𝑦 < 𝑥𝑦 > represents trace set { x, y, xy}. There
International Workshop on Petri Nets and Software Engineering 2022,
PNSE’22 are no empty or null subsequences.
$ karnika@cse.iitb.ac.in (K. Shivhare); rkj@cse.iitb.ac.in Floating Operator (F) It represents insertion of an indi-
(R. K. Joshi) visible floating operand as prefixed, in-fixed or suffixed
https://www.cse.iitb.ac.in/~karnika/ (K. Shivhare); subsequence into the divisible host (i.e. base) operand
https://www.cse.iitb.ac.in/~rkj/ (R. K. Joshi)
© 2022 Copyright for this paper by its authors. Use permitted under Creative provided as superscript in the operator symbol. For exam-
CEUR
Commons License Attribution 4.0 International (CC BY 4.0).
CEUR Workshop Proceedings (CEUR-WS.org)
Workshop
Proceedings
http://ceur-ws.org
ISSN 1613-0073
ple, < 𝑎𝑏 >F<𝑐> forms traces cab, acb and abc. Similarly,
�Figure 1: Micro-configurations
Table 1
Sr. No. Microconfigurations A A+ H I D Trace Expressions
1 Ticketed Service ✗ ✗ ✗ ✓ ✓ 𝑎 → 𝑋 → 𝑑 where, 𝑋 = (𝜑 ⋊ 𝑏 ⋊ 𝑐) → 𝑋
2 Asynchronous Service Loop ✗ ✗ ✗ ✓ ✗ 𝑎 → (𝑋 ‖ 𝑐) where, 𝑋 = (𝑏 → 𝑋) ⋊ 𝜖
3 Critical Section ✗ ✗ ✗ ✗ ✗ 𝑎𝑏 ∦ 𝑐𝑑
4 Concurrent Branching ✗ ✓ ✗ ✓ ✗ < 𝑎𝑏 > 𝐹 <𝑐>
5 Early Completion Option ✗ ✗ ✗ ✗ ✗ 𝑎 → (< 𝑐, 𝜑 >◁▷𝑏 < 𝜑, 𝑑 >)
6 Bowtie ✗ ✗ ✗ ✗ ✗ < 𝑎, 𝑏 >◁▷𝑐 < 𝑑, 𝑒 >
7 Seniority ✗ ✗ ✓ ✗ ✗ 𝑆 𝑎𝑛𝑦 < 𝑎 → 𝑏 >
8 Initial Bypass ✗ ✗ ✓ ✓ ✗ D𝑎 (𝑎𝑏𝑐)
9 Intertwined Vanilla Bypass ✗ ✗ ✗ ✗ ✓ D<𝑐,𝑏> (𝑎𝑏𝑐𝑑𝑒)
10 Intertwined Active Bypass ✓ ✓ ✓ ✗ ✓ B<𝑐𝑑/𝑔,𝑏𝑐/𝑓 > (𝑎𝑏𝑐𝑑𝑒)
11 Intertwined Long Bypass ✗ ✗ ✓ ✗ ✓ D<𝑐𝑑,𝑏𝑐> (𝑎𝑏𝑐𝑑𝑒)
12 Ordered Subsequences ✗ ✗ ✗ ✗ ✗ 𝑆 2 < 𝑎𝑏𝑐 >
13 Crossover ✗ ✗ ✓ ✗ ✓ B<𝑝𝑞/𝑎> (𝑝𝑞𝑟𝑠) ⋊B<𝑎𝑏/𝑝> (𝑎𝑏𝑐𝑑)
< 𝑎𝑏 >F<𝑐𝑑> creates {cdab, acdb, abcd}. This does not
include any trace involving d before 𝑐 or 𝑏 before 𝑎 since
the floating operand is indivisible. The operator is neither
commutative nor associative. References
Substring Bypass Operator (B) This ternary opera-
[1] A. Berti, S. J. van Zelst, W. van der Aalst, Process min-
tor operates on one host operand and a bypass pairing,
ing for python (pm4py): Bridging the gap between
which is a pair of chronicle orderings (substrings). In
process- and data science, 2019.
host trace, an occurrence of pair’s former substring is
[2] W. Aalst, A. Weijters, L. Maruster, Workflow mining:
replaced to generate another trace. Substring bypass op-
Discovering process models from event logs, IEEE
erator generates host trace and also a bypass trace formed
Trans. Knowledge and Data Engineering (2004).
by replacement. For example, B 𝑥/𝑎 < 𝑥𝑦𝑧 > represents
[3] A. Weijters, Process mining: Extending the alpha-
{ayz, xyz}. A compact notation for bulk bypass results is
algorithm to mine short loops (2004).
B 𝑥/𝑎,𝑦/𝑏 < 𝑥𝑦𝑧 > to represent {xyz, ayz, xbz}.
[4] A. Weijters, W. Aalst, A. A. K. Medeiros, Process min-
Substring Drop Operator (D) A special case of Sub-
ing with the HeuristicsMiner algorithm, Technische
string Bypass Operator, it bypasses substring in host
Universiteit Eindhoven, 2006.
operand with an empty substring, i.e., it drops the speci-
[5] S. Leemans, D. Fahland, W. Aalst, Discovering block-
fied substring from the host to generate a new trace. For
structured process models from event logs - a con-
example, D𝑝 < 𝑝𝑞𝑟𝑠 > constructs trace set {pqrs, qrs}
structive approach, in: Int. Conf. on Application and
and D𝑝,𝑞𝑟 < 𝑝𝑞𝑟𝑠 > represents trace set {pqrs, qrs, ps}.
Theory of PN and Concurrency, Springer, 2013.
3. Results Table 1 shows trace expressions for mi-
[6] W. Aalst, Process discovery from event data: Relating
croconfigurations (elementary nets in Fig. 1), and suc-
models and logs through abstractions, 2018.
cess/failures of Alpha (A), Alpha+ (A+), Heuristics (H),
Inductive (I) and DFG (D) algorithms in Pm4Py[1] library.
�