Discovering an S-Coverable WF-net using DiSCover

Leave a Comment

Presented at the ICPM 2022 International Conference on Process Mining in Bolzano, Italy, on October 25, 2022

  • [PDF] H. M. W. Verbeek, “Discovering an S-Coverable WF-net using DiSCover,” in Proceedings of the 2022 4th International Conference on Process Mining (ICPM 2022), 2022.
    [Bibtex] 
    @InProceedings{Verbeek22,
author = {Verbeek, H. M. W.},
booktitle = {{Proceedings of the 2022 4th International Conference on Process Mining (ICPM 2022)}},
date = {2022},
title = {Discovering an {S-Coverable WF-net} using {DiSCover}},
isbn = {979-8-3503-9714-7},
publisher = {IEEE},
url = {https://www.win.tue.nl/~hverbeek/wp-content/papercite-data/pdf/verbeek22.pdf},
abstract = {Although many algorithms exist that can discover a WF-net from an event log, only a few (if any at all) can discover advanced routing constructs. As examples, the Inductive miner uses process trees and cannot discover complex loops, or situations where choice and parallel behavior is mixed, and the Hybrid ILP miner cannot discover certain complex routing constructs because it cannot discover silent transitions. This paper introduces the DiSCover miner, a discovery algorithm that can discover these more complex constructs and that is implemented in ProM. The DiSCover miner discovers from the event log a WF-net that corresponds to a collection of state machines that need to synchronize on the visible transitions (that is, on the activities from the event log). As such, it discovers a WF-net that is S-Coverable but not necessarily sound. Initial results show that it can discover complex routing constructs and that it performs well on the data sets of the different Process Discovery Contests. It even preformed better than winners of the 2020 and 2021 contests.},
}

Slides

2-D: Sequence and choice
3-D: Sequence, choice and concurrency
Choice between c and d followed by choice between e and f
No problem for Alpha miner
3-D log: both e>c and c>e
Alpha miner: Can only replay <d,f>.
IM: Can replay all traces, but also many more, like <>.
2-D discovery algorithms introduce loops to handle concurrency. Can also replay more traces.
Same for Celonis
This approach and implementation result in this WF-net. It can exactly replay all traces in the log and nothing more.
Approach in a nutshell: Separate concurrency from discovery by removing concurrency prior to doing discovery.
Step 1: discover 2-D model on 3-D log.
Step 2: Identify possible 3-D patterns (back-and-forth arcs)
Step 3: Identify (maximal) activity sets that exhibit no concurrency. First set.
Step 3: Second set. In general, there may be many more. I’ve seen examples where this can go up to almost 30,000.
Step 4: Generate the 2-D sublogs from the 3-D log.
Step 5: Discover 2-D models from 2-D sublogs using 2-D discovery algorithm. Using 2-D algorithm now makes sense as the sublogs do not exhibit concurrency.
Step 6: Merge the 2-D models into a 3-D model by synchronizing on the activities.
Example: Start of trace: A token in the start ‘place’ for every model. Left model can do ‘c’ as there is an arc from the token to ‘c’. Right model has no ‘c’, hence also okay (token will not move).
Left model can now do an ‘f’, right model can also do an ‘f’.
Both models can now reach the final ‘place’ using one arc.
Successful replay: Model can replay this trace.
Implementation in ProM 6.12: DiSCover plugin. Not using Disco models but state-machine WF-nets as 2-D models. Result is a WF-net that is S-coverable.
This shows the two S-components of the discovered model.
Model that results when trace <f,d> is added to event log. If we fire the highlighted transitions, then we reach the marking as shown, which enables no transition.
Indication of relaxed soundness: As an example, if we fire d and f, then we need to include both silent transitions indicated by d+f. Together with the start and end silent transitions, this brings us from the initial marking to the final marking.
The highlighted transition cannot be relaxed sound, as firing it always results in the dark blue token to be left behind.
Results on the different PDC data sets as mentioned in the paper (except for the winning score of 2022…, which has been added here)
Additional results to see if we could ‘beat’ the 90.0% score of the Trace miner.
AR indicates alignment-based replay. All others use token-based replay (TR).
AR on (1,3) took more than 11 days and had many timeouts. TR on (1,3) needed only 8 hours.
-A visible transition for every regular activity.
-An invisible transition for every artificial (start, end) activity.
-A unique ‘preset’ place for every different preset. As an example, in the top net e and f have both the preset {start,d} (corresponds to {0,4}).
-An arc to an ‘activity’ transition from its preset place. For example, the arc from {0,4} to e.
-A unique ‘postset’ place for every different postset. Similar to preset.
-An arc from an ‘activity’ transition to its postset place.
-For every arc in the DFG: a silent transition between the postset of the ‘source activity’ transition and the preset of the ‘target activity’ transition.

Downloads

  • DiSCover_6.12.50_1_3
    • ZIP archive, 292.3 MB
    • Uses a tailored classification algorithm with token-based replay.
  • DiSCover_6.12.50_1_3_AR
    • ZIP archive, 348.2 MB
    • Uses the default classification algorithm for Petri nets (PNML) (that is, with alignment-based replay).

Both algorithms use an absolute threshold that equals 1, a relative threshold that equals 3, and default values for all other parameters. These thresholds are set in the “Scripts/Discover.txt” file, lines 31 and 32.

After setting the proper parameters values and making sure the data set and all other required algorithms are in place (see the PDC 2022 page), the entire experiment can be run by calling the “Run.bat” batch file. Before running the experiment, please remove any files “scores[123].csv” and the folders “Logs[123]” and “Models[123]”. These files and folders will be created by the experiment, but to do so they should not exist yet.

The classification results of the experiment are stored in the “scores1.csv”, “scores2.csv”, and “score3.csv” files. The contents of these files can be copy-pasted in the respective tabs of the “DiSCover_6.12.50_1_3_AR.xlsx” spreadsheet. The tab “pdc 2022” then shows the end results (see cells H485:M510).

Leave a Reply