The α-algorithm or α-miner is an algorithm used in process mining, aimed at reconstructing causality from a set of sequences of events.It was first put forward by van der Aalst, Weijters and Măruşter.[1] The goal of Alpha miner is to convert the event log into a workflow-net based on the relations between various activities in the event log. An event log is a multi-set of traces, and a trace is a sequence of activity names. Several extensions or modifications of it have since been presented, which will be listed below.
Alpha miner was the first process discovery algorithm ever proposed, and it gives a good overview of the aim of process discovery and how various activities within the process are executed. Alpha miner was also the basis for the development of many other process mining techniques such as heuristic miner, genetic mining was developed based on the idea alpha miner is built on.[2]
The algorithm takes a workflow log
W\subseteqT*
It does so by examining causal relationships observed between tasks. For example, one specific task might always precede another specific task in every execution trace, which would be useful information.
T
Event log is the primary requirement for applying any process discovery algorithm. An event log consists of a unique identifier for a case, activity name describing the action occurring in the process and timestamp. An event log can be represented as a multi-set of activities. For the sake of simplicity the following example would use alphabetic letter to represent an activity. Consider an example event log shown in the following figure:
| 1 | A | 2019/10/09 14:50:17.000 | |
| 1 | B | 2019/10/09 15:50:17.000 | |
| 1 | C | 2019/10/09 15:56:17.000 | |
| 1 | D | 2019/10/10 13:50:17.000 | |
| 2 | A | 2019/10/10 14:30:17.000 | |
| 2 | C | 2019/10/10 14:50:14.000 | |
| 2 | B | 2019/10/11 09:50:17.000 | |
| 2 | D | 2019/10/11 10:50:17.000 | |
| 3 | A | 2019/10/11 12:50:17.000 | |
| 3 | E | 2019/10/21 14:50:17.000 | |
| 3 | D | 2019/10/21 15:50:17.000 |
L1=[<A,B,C,D>,<A,C,B,D>,<A,E,D>]
Every event log can be boiled down into a multi-set of traces, and such traces can be further used to break down relationships between various activities in the process. According to the rules of alpha miner, activities belonging to various cases can have 4 types of relationships between them:[2]
Sequence Pattern: A → B
XOR-split Pattern: A → B, A → C, and B # C
AND-split Pattern: A → B, A → C, and B || C
The alpha miner starts with converting an event log into directly-follows, sequence, parallel, and choice relations, and using them to create a petri net describing the process model. Initially the algorithm constructs a footprint matrix. Using the footprint matrix and the above shown pattern, one can construct a process model.Based on the four relations described earlier a footprint based matrix is first discovered. Using the footprint based matrix places are discovered. Each place is identified with a pair of sets of tasks, in order to keep the number of places low.
| a | → | → | → | |||
| b | ← | || | → | |||
| c | ← | || | → | |||
| d | ← | ← | ← | |||
| e | ← | → |
YW
(A,B)
A x A
B x B
A x B
PW
p(A,B)
YW
iW
oW
The flow relation
FW
\{(a,p(A,B))|(A,B)\inYW\wedgea\inA\}
\{(p(A,B),b)|(A,B)\inYW\wedgeb\inB\}
\{(iW,t)|t\inTI\}
\{(t,iO)|t\inTO\}
The result is
\alpha(W)=(PW,TW,FW)
iW
oW
TW
FW
iW
oW
It can be shown [3] that in the case of a complete workflow log generated by a sound SWF net, the net generating it can be reconstructed. Complete means that its
\succW