Alpha algorithm: Difference between revisions

Revision as of 10:03, 13 April 2010

Revision as of 11:25, 13 April 2010

Line 4:

The '''α-algorithm''' is an algorithm used in [[process mining]].

It was first put forward by [[Wil van der Aalst]] <ref>van der Aalst, etW al.M P and Weijter, A J M M and Maruster, L (2003). "Workflow Mining: Discovering process models from event logs", ''IEEE Transactions on Knowledge and Data Engineering'', vol 16</ref>. Several extensions or modifications of it have since been presented, which will be listed below.

It constructs [[petri nets|P/T nets]] with special properties ([[workflow nets]]) from event logs (as might be collected by an [[ERP]] system). Each transition in the net corresponds to an observed task.

== Short description ==

The algorithm takes a workflow log <math>W\subseteq T^{*}</math>as input and results in a [[workflow net]] being constructed.

It does so by examining causal relationships observed between tasks. For example, task A might precede task B in every execution trace, which would be useful information.

It can be shown <ref>van der Aalst et al. 2003</ref> that in the case of a complete workflow log generated by a [[sound SWF net]], the net generating it can be reconstructed.

=== Definitions used ===

* A '''workflow trace''' or '''execution trace''' is a [[String (computer science)|string]] over an [[alphabet (computer science)|alphabet]] <math>T</math> of '''tasks'''.

* A '''workflow log''' is a set of workflow traces.

* A '''complete workflow log''' of a workflow net <math>N</math> is the set of firing sequences of <math>(N,m<sub>im_i)</submath>) resulting in the end marking m<submath>om_o</submath>.

<!--- need definitions of SWF net etc. --->

== Description ==

Declaratively, the algorithm can be presented as follows.

Three sets of tasks are determined:

* <math>T_W</math> is the set of all tasks which occur in at least one trace

* <math>T_I</math> is the set of all tasks which occur trace-initially

* <math>T_O</math> is the set of all tasks which occur trace-terminally

Basic ordering relations are determined (<math>{>}_{W}</math> first, the latter three can be constructed therefrom)

* <math>A{>}_{W}B</math> iff B directly precedes A in some trace

* <math>A\rightarrow_W B</math> iff <math>A>_WB \wedge B\not>_WA</math>

* <math>A#_WB</math> iff <math>A\not>_WB \wedge B\not>_WA</math>

* <math>

Places are discovered

* <math>X_W</math>

== Limitations ==

See <ref>A. de Medeiros, A K and van der Aalst, W M P and Weijters, A J M M (2003). "Workflow Mining: Current Status and Future Directions". in: "volume 2888 of Lecture Notes in Computer Science", Springer-Verlag</ref>

== Extensions ==

{{section stub}}

for example <ref name="extending_the">A. de Medeiros, A K and van Dongen, B F and van der Aalst, W M P and Weijters, A (2004). "Process mining: extending the α-algorithm to mine short loops"</ref>

== References ==

{{Reflist}}

*van der Aalst, W M P and Weijter, A J M M and Maruster, L (2003). "Workflow Mining: Discovering process models from event logs", ''IEEE Transactions on Knowledge and Data Engineering'', vol 16.

*A. de Medeiros, A K and van Dongen, B F and van der Aalst, W M P and Weijters, A (2004). "Process mining: extending the α-algorithm to mine short loops"

<!--- Categories --->