Alpha Miner

Process Discovery using the Alpha Algorithm

Process Discovery algorithms want to find a suitable process model that describes the order of events/activities that are executed during a process execution. The Alpha Algorithm is one of the most known Process Discovery algorithm and is able to find:

  • A Petri net model where all the transitions are visible and unique and correspond to classified events (for example, to activities).
  • A initial marking that describes the status of the Petri net model when a execution starts
  • A final marking that describes the status of the Petri net model when a execution ends

We provide an example where a log is read, the Alpha algorithm is applied and the Petri net along with the initial and the final marking are found. The log we take as input is the running-example.xes XES log that can be found in the folder tests/input_data.

The following code imports the running-example.xes log:

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

log = xes_importer.import_log(os.path.join("tests","input_data","running-example.xes"))

Then, the log is loaded in memory and the Alpha Miner algorithm can be applied:

from pm4py.algo.discovery.alpha import factory as alpha_miner

net, initial_marking, final_marking = alpha_miner.apply(log)

To export the process model, to visualize it or to save the visualization of the model, the functions presented in the Petri net management section can be used.

The following picture represents the Petri net mined from the running-example.xes log by applying the Alpha Miner:

The place colored green is the source place and belongs to the initial marking. In the initial marking, a token is assigned to that place (indicated by the number 1 on the place). The place colored orange is the sink place and belongs to the final marking. We see that transitions here correspond to activities in the log. Models extracted by the Alpha Miner often have deadlock problems, so it is not sure that each trace is replayable on this model.

SIMPLE algorithm

SIMPLE is an algorithm provided in PM4Py that selectively applies the Alpha Miner to the top variants of the log, in order to retrieve a sound workflow net from the log. The algorithm works on logs as follows:

  • An auto filter (see the Filtering logs page) is applied to the end activities of the log (to remove incomplete traces).
  • An auto filter (see the Filtering logs page) is applied to the start activities of the log (to remove traces with inusual start activities).
  • The variants of the log are retrieved and ordered by the number of their occurrences
  • For each variant having the top-N occurrences (where N is specified by the user), starting from the most frequent one:
    • The addition of the variant to a filtered log is done
    • The Alpha Miner is applied
    • The soundness and the replayability (on the filtered log) of the Petri net is checked
    • If the network is not sound or not replayable, then the given variant is removed from the filtered log

To apply the SIMPLE algorithm to the top-20 variants of the log, the following code could be used:

from pm4py.algo.discovery.simple.model.log import factory as simple_algorithm

net, initial_marking, final_marking = simple_algorithm.apply(log, classic_output=True, parameters={"max_no_variants": 20})

Obtaining the following model on the Road Traffic Fine Management log: