Alpha algorithm: Difference between revisions

Revision as of 16:27, 18 September 2010

Revision as of 12:51, 25 September 2010

Line 5:

It constructs [[petri nets|P/T nets]] with special properties ([[workflow net]]s) 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, 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 (computer science)|string]] over an [[alphabet (computer science)|alphabet]] <math>T</math> of ''tasks''.

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

Line 16:

<!--- draw an example --->

== Description ==

Declaratively, the algorithm can be presented as follows.

Three sets of tasks are determined:

Line 49:

<!--- consequence: short loops never occur. --->

== Properties ==

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. Complete means that its <math>\succ_W</math> 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 ==

General workflow nets may contain several types of constructs <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> which the α-algorithm cannot rediscover.

Line 61 ⟶ 60:

<!--- double-check, don't swallow! --->

== Extensions ==

{{Expand section|date=May 2010}}

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 J M M (2004). "Process mining: extending the α-algorithm to mine short loops"</ref>

Line 67 ⟶ 66:

"Data Mining and Knowledge Discovery" vol 15, p. 145--180, Springer-Verlag</ref>

== References ==

{{Reflist}}

Line 76 ⟶ 75:

{{DEFAULTSORT:Alpha Algorithm}}

[[Category:Articles created via the Article Wizard]]

[[Category:Data mining]]