Decomposing Petri Nets and Recomposing Alignments

Decomposing Petri Nets and Recomposing Alignments

Maximal Decomposition

Alignments represent a computationally expensive problem on models that contain a lot of concurrency. Yet, they are the conformance checking technique that provides the best results in term of finding a match between the process execution(s) and the model. To overcome the difficulties related to the size of the state space, various attempts to decompose the model into “smaller” pieces, into which the alignment is easier and still permit to diagnose problems, have been done.

We propose to use the decomposition technique (maximal decomposition of a Petri net) described in:

Van der Aalst, Wil MP. “Decomposing Petri nets for process mining: A generic approach.” Distributed and Parallel Databases 31.4 (2013): 471-507.

We can see an example of maximal decomposition on top of the Petri net extracted by the Alpha Miner on top of the Running Example log.

Let’s first load the running example log and apply the Alpha Miner.

import os
from pm4py.objects.log.importer.xes import importer as xes_importer
from pm4py.algo.discovery.alpha import algorithm as alpha_miner

log = xes_importer.apply(os.path.join("tests", "input_data", "running-example.xes"))
net, im, fm = alpha_miner.apply(log)

Then, the decomposition can be found using:

from pm4py.objects.petri.decomposition import decompose

list_nets = decompose(net, im, fm)

If we want to represent each one of the Petri nets, we can use a FOR loop:

for index, model in enumerate(list_nets):
    subnet, s_im, s_fm = model

    gviz.append(visualizer.apply(subnet, s_im, s_fm, parameters={"format": "png"}))
    visualizer.save(gviz[-1], str(index)+".png")

Obtaining the following nets:

A log that is fit according to the original model is also fit (projecting on the activities of the net) for these nets. Conversely, any deviation on top of these models represent a deviation also on the original model.

Alignments Recomposition

The approach described here has been published in:

Lee, Wai Lam Jonathan, et al. “Recomposing conformance: Closing the circle on decomposed alignment-based conformance checking in process mining.” Information Sciences 466 (2018): 55-91.

The recomposition permits to understand whether each step of the process has been executed in a sync way or some deviations happened. First, an alignment is performed on top of the decomposed Petri nets.

Then, the agreement between the activities at the border is checked. If a disagreement is found, the two components that are disagreeing are merged and the alignment is repeated on them.

When the steps are agreeing between the different alignments of the components, these can be merged in a single alignment. The order of recomposition is based on the Petri net graph. Despite that, in the case of concurrency, the “recomposed” alignment contains a valid list of moves that may not be in the correct order.

To perform alignments through decomposition/recomposition, the following code can be used. A maximum number of border disagreements can be provided to the algorithm. If the number of border disagreements is reached, then the alignment is interrupted a None as alignment of the specific trace is returned.

from pm4py.algo.conformance.decomp_alignments import algorithm as decomp_alignments

conf = decomp_alignments.apply(log, net, im, fm, parameters={decomp_alignments.Variants.RECOMPOS_MAXIMAL.value.Parameters.PARAM_THRESHOLD_BORDER_AGREEMENT: 2})

Since decomposed models are expected to have less concurrency, the components are aligned using a Dijkstra approach. In the case of border disagreements, this can degrade the performance of the algorithm.

It should be noted that this is not an approximation technique; according to the authors, it should provide the same fitness as the original alignments.

Since the alignment is recomposed, we can use the fitness evaluator to evaluate
the fitness (that is not related to the computation of fitness described in the paper).

from pm4py.evaluation.replay_fitness import evaluator as rp_fitness_evaluator

fitness = rp_fitness_evaluator.evaluate(conf, variant=rp_fitness_evaluator.Variants.ALIGNMENT_BASED)

.