Conversion of a log skeleton graph to a Petri net

Posted onAuthoradmin

Conversion

For every activity in the log skeleton graph, a single transition is created. The fragments below show which places and additional transitions are required and how they get connected to the activity transitions. Attempts are made to not include a fragment if it will be subsumed by another fragment.

Process

The place {i} is initially marked with a single token (the green fill), whereas the {o} place should be marked at the end with a single token (the double line). The process starts with the silent transition for the artificial |> activity, and ends with the silent transition for the artificial [] transition.

Equivalence

This shows the conversion if A, B and C are equivalent, and if A is the representative. Clearly, if activities A, B and C occur equally often, the additional places will be empty at the end.

If an edge exists in the log skeleton graph between, for example, from A to C, then C can be removed from this fragment, as there will be a place from A to C (see the next fragments).

Response

This shows the general conversion if A has B as Response in the log skeleton graph. If A has occurred, then there must be a token in the place, which can only be removed if B occurs. The additional transition is colored grey as it should not fire freely if enabled. It only should fire if A or B needs to fire and there is no token yet in the place.

If both A and B occur at most once, this can be simplified to the following:

Furthermore, if A and B are equivalent, the following fragment is used:

Precedence

This shows the general conversion if B has A as Precedence in the log skeleton graph. If B occurs, then A must have occurred before. The additional transition removes any tokens from the place at the end. Again, this transition is colored grey as it should not fire freely if enabled: A token in the place may be needed for B. Only at the end, should any tokens be removed from this place.

If both A and B occur at most once, this can be simplified to the following:

Furthermore, if A and B are equivalent, the following fragment is used:

Not Response and Not Precedence

This shows the conversion if either A has B as Not Precedence or B has A as Not Response. First, we allow A to occur any number times, then we allow B to occur any number of times.

If B occurs at most once, this can be simplified to the following:

After B has occurred, A cannot occur anymore, as the token in the place is then removed. If B occurs exactly once, then the additional transition can be removed.

If A occurs at most once, the this can be simplified to the following:

B can only occur if either A or the additional transition have occurred before. Once B has occurred, there is already a token in the place. If then A occurs again, the place will contain more than one token, which does not satisfy the final marking (the final marking contains this place only once). If A occurs exactly once, then the additional transition can be removed.

If both A and B occur exactly once, we get the following fragment:

Furthermore, if A and B are equivalent, the following fragment is used:

Not Co-Existence

This shows the conversion if A, B and C occur at most once. The additional transition is required in case none of the activities occurs. If some of the activities occur possible more than once, like C, we get a fragment as follows:

As before, the grey transitions should not fire freely if enabled. They should only fire if needed, that is, either at the end to remove tokens or in case C needs to occur (in the bottom fragment) while the token is still in the place labeled px.

Implementation

This conversion has been implemented in version 6.11.247 of the LogSkeleton package in ProM 6 as the “Convert Log Skeleton to Petri Net” plugin. We show the use of this plugin using a simple example: The a12f0n05 event log.

After having imported this event log, we first run the “Build Log Skeleton from Event Log” plugin using the event name as the classifier, which results in the following log skeleton graph:

Second, we select the “Advanced options” button in the right bottom corner, and set the noise levels all to 3%:

Third, we convert this log skeleton graph to a Petri net using the “Convert Log Skeleton to Petri Net” plugin:

To add information on the final marking as well, we use the “Pack Petri net” plugin to create an accepting Petri net from it:

Finally, to improve on the layout, we select the “Graphviz Accepting Petri net visualisation” from the InductiveVisualMiner package to visualize the net:

Results

Using this conversion from log skeleton graphs with 3% noise to Petri nets, we obtain the following results for the past instances of the Process Discovery Contest (PDC):

  • PDC 2016
    • 91%
    • 90 true positives, 10 false negatives
    • 5 false positives, 95 true negatives
  • PDC 2017
    • 78%
    • 97 true positives, 3 false negatives
    • 33 false positives, 67 true negatives
  • PDC 2019
    • 93%
    • 422 true positives, 31 false negatives
    • 31 false positives, 416 true negatives
  • PDC 2020
    • 84%
    • 91778 true positives, 8656 false negatives
    • 19046 false positives, 72520 true negatives

The following chart shows the accuracy values for the PDC 2020, with the average accuracy and the corresponding score:

The average positive accuracy is 91%, the average negative accuracy 79%.

Note that these results may differ from the results obtained using the log skeletons themselves. The Petri net is the result of the conversion of a log skeleton graph, which is a log skeleton with some reductions applied to it. First, the skeleton checker checks a property that cannot be checked on a log skeleton graph. Second, the reductions allow to reduce constraints that are not redundant. As such, the conversion from a log skeleton to a log skeleton graph may already lead to different results. Furthermore, the conversion from a log skeleton graph to a Petri net uses  simplifications (like using a single place if two activities are equivalent) that may lead to yet different results.