Visualization of Process Behavior Using Structured Petri Nets
Explore the concept of mining structured Petri nets for visualizing process behavior, distinguishing between overfitting and underfitting models, and proposing a method to extract structured slices from event logs. The approach involves constructing LTS from logs, synthesizing Petri nets, and presenting a systematic flow for slicing event logs. This innovative methodology captures the essence of process behavior efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Mining Structured Petri Nets for the Visualization of Process Behavior Javier de San Pedro Jordi Cortadella Universitat Politecnica de Catalunya (Barcelona) 1
Background Process Event Log Discovery Model Petri Nets, etc. Event log: a Trace 1: a c c Trace 2: b c Trace 3: a c b 2
Overfitting vs. Underfitting Process behavior = Model behavior Overfitting Useless for visualization! Spaghetti models Useful models? Process behavior Underfitting Useless for analysis! Flower models Model behavior 3
Our proposal Log slice 1 Discovery Model 1 Discovery Slicing Event Log Model Discovery Log slice n Discovery Model n Model 1 Model 2 Model 3 Process behavior Process behavior Process behavior Model Model Few models, each is low-complexity 4
Extracting structured slices Most frequent behavior Captures more than 90% of log Slicing Less frequent 5
Outline Introduction Proposed slicing flow LTS construction and saturation LTS slicing Synthesis Results and related work 6
Proposed slicing flow LTS slice 1 Synthesis Petri net 1 Labeled Transition System Event Log Synthesis Saturation Slicing LTS slice n Synthesis Petri net n Slicing is based on LTS properties Log slice n Mining Model n Our proposed flow constructs Petri nets from the LTS slices However, alternative miners may be used on the discovered slices 7
Constructing LTS from log Event log: Trace 1: a a b Trace 2: b a a {} b a {b} {a} a a {a,b} {a2} a b Multiset rule: New state for every different trace prefix considered as a multiset (i.e. regardless of event order) {a2 ,b} Same event multiset same state W. van der Aalst, V. Rubin, H. Verbeek, B. van Dongen, E. Kindler, and C. Gunther, Process mining: a two-step approach to balance between underfitting and overfitting. Software & Systems Modeling, 2010 8
Arc-completed LTS Event log: Trace 1: a a b Trace 2: b a a {} b a {b} {a} a b a {a,b} {a2} a b Arc-completion rule: New arc ? between any two states where the multiset of ?2is that of ?1 ? . {a2 ,b} Increases generalization Trace a b a now also possible Preserves fitness 9
Saturation of concurrency x c b b a a c c a a b b c ?,? in conflict ?,? concurrent ?,? concurrent Saturation of concurrency: Two events ?,? are concurrent in any state ?,? concurrent in every state All pairs of events have a single relation type (either choice or concurrency) Preserves fitness, yet simplifies Petri net structure: 10
Slicing flow: LTS slicing LTS slice 1 Synthesis Petri net 1 Labeled Transition System Event Log Synthesis Saturation Slicing LTS slice n Synthesis Petri net n 11
Desirable properties of slices Each slice should be visualization-friendly Simple control flow E.g., free choice Petri nets: Nonfree choice Free choice Book Bus Book Bus Take Bus Take Bus Book Hotel Book Hotel Book Flight Book Flight Book Hotel Take Flight Take Flight Other structural constraints may be used Marked graphs, etc. 12
Desirable properties in LTSs How to ensure an LTS slice results in a visually- friendly Petri net when synthesized? Which properties should an LTS satisfy to ensure it is synthesizable into a specific structural Petri net type? Marked graph E. Best and R. Devillers, Characterisation of the State Spaces of Live and Bounded Marked Graph Petri Nets. In Language and Automata Theory and Applications, 2014. Free choice J. Cortadella, M. Kishinevsky, L. Lavagno, and A. Yakovlev, Deriving Petri nets from finite transition systems. IEEE Transactions on Computers, 1998. . 13
Well-behaved LTS slices Marked graph: too strict (no choice) Free choice: allows choice May still result in complicated models Our proposal: well-behaved LTS slices Satisfy all free choice properties Satisfy most marked graph restrictions Still allows choice Local-level properties We show how to model these properties as SAT 14
SAT model Log: a b c e a c b e a d b c e a ?1= 0 ?1= 1 ?2= 0 ?2= 1 ?7= 0 d b c ?3= 0 ?8= 0 b c ?9= 0 b c ?4= 0 ?4= 1 ?5= 0 b c ?10= 0 ?11= 0 e ?6= 0 ?6= 1 ?12= 0 e One Boolean variable per LTS transition ??is true if corresponding arc is selected in slice Every valid assignment forms an LTS slice (subset) 15
Example: forward persistency Forward persistency: If a and b exist in a LTS slice, then a and b must exist too. ?1 ?2 ?3 ?4 ?2 b a ?1 a b ?4 ?3 Log: a b c e a c b e a d b c e a ?1 ?7 ?2 d b c ?3 ?8 SAT constraints: ?2 ?3 ?4 ?5 ?8 ?9 ?10 ?11 ?3 ?7 b c ?9 b c ?4 ?5 b c ?10 ?11 e ?6 ?12 e 16
Example: forward persistency a b c e a c b e a d b c e a b c e a c b e a d b c e 17
Slicing approach Given LTS ?, find set of slices ?1, ,??that: Each slice satisfies well-behavedness (WB) properties Minimize the number of slices required to fit all traces Optimization (MinSAT) problem Implemented using Integer Linear Programming Each solution of ILP model is a WB-slice Maximize number of traces covered by each slice not covered in any previous slice 18
Slicing flow: synthesis step Proposed synthesis procedure directly constructs Petri net from LTS slice result Based on theory of regions Modified to allow for less overfitting models LTS slice 1 Synthesis Petri net 1 Labeled Transition System Event Log Synthesis Saturation Slicing LTS slice n Synthesis Petri net n Other mining algorithms may be used instead Allows process models other than Petri nets Log slice n Mining Model n 19
Outline Introduction Proposed slicing flow LTS construction and saturation LTS slicing Synthesis Results and related work 20
Results Benchmark: incidenttelco Used benchmarks available online Original Petri net mined with ILP miner: Original 448 arcs 9800 crossings 100% fitness 32% precision 21
Results: incidenttelco 65 slices required for 100% fitness However, centering on the first slice only: 1stslice 15 arcs Planar (0 cros.) Covers most behavior of log 92.6% fitness 53.7% precision Original With minimal trade-off in accuracy compared to original model 448 arcs 9800 crossings 100% fitness 32% precision 22
Results Similar results in other benchmarks Only 1-3 slices required for >90% of behavior Every slice is low visual complexity For >95% of behavior Benchmark # of slices # of crossings # of slices # of crossings documentflow 1 0 4 8 fhmilu 1 4 1 4 fhmn5 1 1 1 1 incidenttelco 1 0 2 1 kim 1 0 2 0 purchasetopay 1 0 1 0 receipt 1 3 1 3 tsl 3 3 10 9 23
Related work Clustering of traces by simplicity and quality of models J. De Weerdt, S. vanden Broucke, J. Vanthienen, and B. Baesens, Active Trace Clustering for Improved Process Discovery. IEEE Trans. on Knowledge and Data Engineering, 2013. Uses specific miner (Heuristic Miner) as clustering linkage criteria Generates less visualization-friendly models Comparable runtime cost Clustering of traces by vector distance M. Song, C. W. G nther, and W. P. van der Aalst, Trace Clustering in Process Mining In Business Process Management Workshops, 2009. Less effective for visualization of process models 24
Conclusions New method to mine a series of well-structured process models from a log Low-complexity models that are competitive in accuracy Few models required to observe most behavior of a log Future work: Additional criteria for slicing Extended free choice Applications outside process mining E.g., reverse engineering of asynchronous circuits (ASYNC 2016) 25
