Rust4PM - Process Mining Documentation

Directly-follows graph

A directly-follows graph (DFG) has one node per activity and an edge from a to b whenever b directly follows a in some trace, labelled with how often that happens. It is quick to compute and a good first look at a log.

import r4pm

log = r4pm.import_item("EventLog", "data/road-traffic-fines.xes.gz")
dfg = r4pm.bindings.discover_dfg(log)

print("start:", ", ".join(sorted(dfg["start_activities"])))
print("end:", ", ".join(sorted(dfg["end_activities"])))

# Edges are ((from, to), frequency) pairs.
edges = sorted(dfg["directly_follows_relations"], key=lambda edge: (-edge[1], edge[0]))
for (source, target), count in edges[:5]:
    print(f"{count:>7}  {source} -> {target}")

output

start: Create Fine
end: Appeal to Judge, Notify Result Appeal to Offender, Payment, Receive Result Appeal from Prefecture, Send Appeal to Prefecture, Send Fine, Send for Credit Collection
 103392  Create Fine -> Send Fine
  79757  Send Fine -> Insert Fine Notification
  72334  Insert Fine Notification -> Add penalty
  57182  Add penalty -> Send for Credit Collection
  46952  Create Fine -> Payment

In Python the DFG is plain data: activities (with counts), directly_follows_relations as ((from, to), count) pairs, start_activities and end_activities. Reference: discover_dfg.

Petri net with Alpha+++

DFGs cannot express concurrency and over-generalize loops. Alpha+++ discovers a Petri net, which can. It works on the activity projection of the log (each variant once, with its count), so it stays fast on large logs.

import r4pm
import r4pm.petri_net

log = r4pm.import_item("EventLog", "data/road-traffic-fines.xes.gz")
projection = r4pm.bindings.log_to_activity_projection(log)

# Thresholds for filtering rare behavior, explained in the table below the snippet.
config = {
    "balance_thresh": 0.1,
    "fitness_thresh": 0.8,
    "replay_thresh": 0.0,
    "log_repair_skip_df_thresh_rel": 4.0,
    "log_repair_loop_df_thresh_rel": 4.0,
    "absolute_df_clean_thresh": 1,
    "relative_df_clean_thresh": 0.01,
}
net = r4pm.bindings.discover_alphaplusplusplus(projection, config)

labels = sorted(t["label"] for t in net["transitions"].values() if t["label"] is not None)
print(len(net["places"]), "places")
print(len(labels), "visible transitions:", ", ".join(labels))

r4pm.petri_net.export_pnml(net, "model.pnml")

output

10 places
11 visible transitions: Add penalty, Appeal to Judge, Create Fine, Insert Date Appeal to Prefecture, Insert Fine Notification, Notify Result Appeal to Offender, Payment, Receive Result Appeal from Prefecture, Send Appeal to Prefecture, Send Fine, Send for Credit Collection

Alpha+++ first repairs the log for skips and loops, then cleans the directly-follows graph, and then builds and filters candidate places. The configuration controls each step:

Option	Meaning (from the crate documentation)
`absolute_df_clean_thresh`	Absolute threshold for weighted DFG cleaning
`relative_df_clean_thresh`	Relative threshold for weighted DFG cleaning
`log_repair_skip_df_thresh_rel`	Log repair threshold for skips, relative to the weighted DFG
`log_repair_loop_df_thresh_rel`	Log repair threshold for loops, relative to the weighted DFG
`balance_thresh`	Balance threshold for filtering place candidates
`fitness_thresh`	Fitness threshold for filtering place candidates
`replay_thresh`	Replay threshold for filtering place candidates

The thresholds trade model simplicity against how much of the log the model covers. Check conformance shows how to measure the effect of a change. Reference: discover_alpha+++.

Export the model

The Alpha+++ snippet ends by writing model.pnml. PNML is the standard Petri net format, so ProM, PM4Py and Propel open it directly. In Python, r4pm.petri_net.to_pm4py(net) converts the net into PM4Py objects without a file in between.

Next: check how well the model fits the log.