Vol-3170/poster4

From BITPlan ceur-ws Wiki
Jump to navigation Jump to search

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

load PDF 

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.
οΏ½
Retrieved from "http://ceur-ws.bitplan.com/index.php?title=Vol-3170/poster4&oldid=1775"