The α-algorithm or α-miner is an algorithm used in
process mining
Process mining is a family of techniques relating the fields of data science and process management to support the analysis of operational processes based on event logs. The goal of process mining is to turn event data into insights and actions. ...
, 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. 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 Business process discovery (BPD) related to business process management and process mining is a set of techniques that manually or automatically construct a representation of an organisations' current business processes and their major process varia ...
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 a
heuristic minergenetic miningwas developed based on the idea alpha miner is built on.
Short description
The algorithm takes a workflow log
as input and results in a workflow net being constructed.
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.
Definitions used
* A workflow trace or execution trace is a
string
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
over an
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
of ''tasks''.
* A workflow log is a set of workflow traces.
Event log
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:
An event log is a multi set of traces, and a trace is a sequence of activities. Thus, an event log such as above can be represented using the following notation:
Patterns

Sequence Pattern: A → B

XOR-split Pattern: A → B, A → C, and B # C

AND-split Pattern: A → B, A → C, and B , , C
Description
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.
*
is the set of all pairs
of maximal sets of tasks such that
** Neither
and
contain any members of > and
**
is a subset of →
*
contains one place
for every member of
, plus the input place
and the output place
The flow relation
is the union of the following:
*
*
*
*
The result is
* a
Petri net
A Petri net, also known as a place/transition (PT) net, is one of several mathematical modeling languages for the description of distributed systems. It is a class of discrete event dynamic system. A Petri net is a directed bipartite graph that ...
structure
* with one input place
and one output place
* because every transition of
is on a
-path from
to
, it is indeed a workflow net.
For the example given above, the following petri net would be resultant of the application of alpha miner.
Properties
It can be shown 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
relation is maximal. It is ''not'' required that all possible traces be present (which would be countably infinite for a net with a loop).
Limitations
* Implicit places: Alpha miner cannot distinguish between implicit and required places and thus might result in additional non required places in the discovered petri net.
* Loops: Alpha miner cannot discover loops of the length 1 and 2 in the process model.
* Local dependencies are often missed in alpha miner.
[
* Representational bias: Alpha miner can only discover petri net thus adding representational bias such as requirement on unique visible labels for every transition.][
]
References
{{DEFAULTSORT:Alpha Algorithm
Process mining
Data mining algorithms