Vol-3170/poster4

Paper

Paper
edit
description
id	Vol-3170/poster4
wikidataid	Q117351499→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.
�