Footprints on process trees

Footprints on process trees

As seen in

Conformance Checking using Footprints

Footprints are a very scalable conformance checking technique that permits to compare the behavior of an event log against a process model. For Petri nets, the main issue is the computation of the footprints of the Petri net. This operation can take quite some time.

If we change the underlying model, from Petri nets to process tree, it is possible to exploit its bottomup structure in order to calculate the footprints almost instantaneously.

Let’s open a log, calculate a process tree and then apply the discovery of the footprints. We open the running-example log:

from pm4py.objects.log.importer.xes import importer as xes_importer

log = xes_importer.apply("tests/input_data/running-example.xes")

And apply the inductive miner:

from pm4py.algo.discovery.inductive import algorithm as inductive_miner

tree = inductive_miner.apply_tree(log)

Then, the footprints can be discovered. We discover the footprints on the entire log, we discover the footprints trace-by-trace in the log, and then we discover the footprints on the process tree:

from pm4py.algo.discovery.footprints import algorithm as fp_discovery

fp_log = fp_discovery.apply(log, variant=fp_discovery.Variants.ENTIRE_EVENT_LOG)
fp_trace_trace = fp_discovery.apply(log, variant=fp_discovery.Variants.TRACE_BY_TRACE)
fp_tree = fp_discovery.apply(tree, variant=fp_discovery.Variants.PROCESS_TREE)

Each one of these contains:

  • A list of sequential footprints contained in the log/allowed by the model
  • A list of parallel footprints contained in the log/allowed by the model
  • A list of activities contained in the log/allowed by the model
  • A list of start activities contained in the log/allowed by the model
  • A list of end activities contained in the log/allowed by the model

It is possible to execute an enhanced conformance checking between the footprints of the (entire) log, and the footprints of the model, by doing:

from pm4py.algo.conformance.footprints import algorithm as fp_conformance

conf_result = fp_conformance.apply(fp_log, fp_tree, variant=fp_conformance.Variants.LOG_EXTENSIVE)

The result contains, for each item of the previous list, the violations.

Given the result of conformance checking, it is possible to calculate the footprints-based fitness and precision of the process model, by doing:

from pm4py.algo.conformance.footprints.util import evaluation

fitness = evaluation.fp_fitness(fp_log, fp_tree, conf_result)
precision = evaluation.fp_precision(fp_log, fp_tree)

These values are both included in the interval [0,1]