Alpha algorithm

<h2 id="short-description">Short description</h2>
<p>The algorithm takes a workflow log 
  
    
      
        W
        ⊆
        
          T
          
            ∗
          
        
      
    
    {\displaystyle W\subseteq T^{*}}
  
 as input and results in a workflow net being constructed.
</p><p>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.
</p>
<h3>Definitions used</h3>
<ul><li>A workflow trace or execution trace is a <a href="/facts/String_(computer_science)/4ChJu5WS">string</a> over an <a href="/facts/Alphabet_(computer_science)/6KW9qYRW">alphabet</a> 
  
    
      
        T
      
    
    {\displaystyle T}
  
 of <i>tasks</i>.</li>
<li>A workflow log is a set of workflow traces.</li></ul>
<h2 id="event-log">Event log</h2>
<p>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:
</p>
Sample event log<table><tbody><tr><th>Case id</th><th>Activity</th><th>Timestamp</th></tr><tr><td>1</td><td>A</td><td>2019/10/09 14:50:17.000</td></tr><tr><td>1</td><td>B</td><td>2019/10/09 15:50:17.000</td></tr><tr><td>1</td><td>C</td><td>2019/10/09 15:56:17.000</td></tr><tr><td>1</td><td>D</td><td>2019/10/10 13:50:17.000</td></tr><tr><td>2</td><td>A</td><td>2019/10/10 14:30:17.000</td></tr><tr><td>2</td><td>C</td><td>2019/10/10 14:50:14.000</td></tr><tr><td>2</td><td>B</td><td>2019/10/11 09:50:17.000</td></tr><tr><td>2</td><td>D</td><td>2019/10/11 10:50:17.000</td></tr><tr><td>3</td><td>A</td><td>2019/10/11 12:50:17.000</td></tr><tr><td>3</td><td>E</td><td>2019/10/21 14:50:17.000</td></tr><tr><td>3</td><td>D</td><td>2019/10/21 15:50:17.000</td></tr></tbody></table>
<p>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:
</p><p>
  
    
      
        L
        1
        =
        [
        <
        A
        ,
        B
        ,
        C
        ,
        D
        >
        ,
        <
        A
        ,
        C
        ,
        B
        ,
        D
        >
        ,
        <
        A
        ,
        E
        ,
        D
        >
        ]
      
    
    {\displaystyle L1=[<A,B,C,D>,<A,C,B,D>,<A,E,D>]}

</p><p>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:<a class="footnote-ref" id="fnref:3" href="#fn:3"><sup>3</sup></a>
</p>
<ul><li>Direct Succession: x > y if and only if some relation x is directly following by y. In our example, we can consider that A > B, A > E, A > C.</li>
<li>Causality: x → y iff x > y and not y > x. In our example, we can consider that A → E.</li>
<li>Parallel: x || y iff x > y and y > x. In our example, we have B || C.</li>
<li>Choice: x # y iff not(x > y) and not(y > x). In our example, we have A # D.</li></ul>
<h2 id="patterns">Patterns</h2>
<p> Sequence Pattern: A → B
</p><p> XOR-split Pattern: A → B, A → C, and B # C
</p><p> AND-split Pattern: A → B, A → C, and B || C
</p>
<h2 id="description">Description</h2>
<p>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 <i>sets of</i> tasks, in order to keep the number of places low.
</p>
Footprint matrix for the log L1<table><tbody><tr><th></th><th>a</th><th>b</th><th>c</th><th>d</th><th>e</th></tr><tr><td>a</td><td>#</td><td>→</td><td>→</td><td>#</td><td>→</td></tr><tr><td>b</td><td>←</td><td>#</td><td>||</td><td>→</td><td>#</td></tr><tr><td>c</td><td>←</td><td>||</td><td>#</td><td>→</td><td>#</td></tr><tr><td>d</td><td>#</td><td>←</td><td>←</td><td>#</td><td>←</td></tr><tr><td>e</td><td>←</td><td>#</td><td>#</td><td>→</td><td>#</td></tr></tbody></table>
<ul><li>
  
    
      
        
          Y
          
            W
          
        
      
    
    {\displaystyle Y_{W}}
  
 is the set of all pairs 
  
    
      
        (
        A
        ,
        B
        )
      
    
    {\displaystyle (A,B)}
  
 of maximal sets of tasks such that
<ul><li>Neither 
  
    
      
        A
        ×
        A
      
    
    {\displaystyle A\times A}
  
 and 
  
    
      
        B
        ×
        B
      
    
    {\displaystyle B\times B}
  
 contain any members of > and</li>
<li>
  
    
      
        A
        ×
        B
      
    
    {\displaystyle A\times B}
  
 is a subset of →</li></ul></li>
<li>
  
    
      
        
          P
          
            W
          
        
      
    
    {\displaystyle P_{W}}
  
 contains one place 
  
    
      
        
          p
          
            (
            A
            ,
            B
            )
          
        
      
    
    {\displaystyle p_{(A,B)}}
  
 for every member of 
  
    
      
        
          Y
          
            W
          
        
      
    
    {\displaystyle Y_{W}}
  
, plus the input place 
  
    
      
        
          i
          
            W
          
        
      
    
    {\displaystyle i_{W}}
  
 and the output place 
  
    
      
        
          o
          
            W
          
        
      
    
    {\displaystyle o_{W}}
  
</li></ul>
<p>The flow relation 
  
    
      
        
          F
          
            W
          
        
      
    
    {\displaystyle F_{W}}
  
 is the union of the following:
</p>
<ul><li>
  
    
      
        {
        (
        a
        ,
        
          p
          
            (
            A
            ,
            B
            )
          
        
        )
        
          |
        
        (
        A
        ,
        B
        )
        ∈
        
          Y
          
            W
          
        
        ∧
        a
        ∈
        A
        }
      
    
    {\displaystyle \{(a,p_{(A,B)})|(A,B)\in Y_{W}\wedge a\in A\}}
  
</li>
<li>
  
    
      
        {
        (
        
          p
          
            (
            A
            ,
            B
            )
          
        
        ,
        b
        )
        
          |
        
        (
        A
        ,
        B
        )
        ∈
        
          Y
          
            W
          
        
        ∧
        b
        ∈
        B
        }
      
    
    {\displaystyle \{(p_{(A,B)},b)|(A,B)\in Y_{W}\wedge b\in B\}}
  
</li>
<li>
  
    
      
        {
        (
        
          i
          
            W
          
        
        ,
        t
        )
        
          |
        
        t
        ∈
        
          T
          
            I
          
        
        }
      
    
    {\displaystyle \{(i_{W},t)|t\in T_{I}\}}
  
</li>
<li>
  
    
      
        {
        (
        t
        ,
        
          i
          
            O
          
        
        )
        
          |
        
        t
        ∈
        
          T
          
            O
          
        
        }
      
    
    {\displaystyle \{(t,i_{O})|t\in T_{O}\}}
  
</li></ul>
<p>The result is
</p>
<ul><li>a <a href="/facts/Petri_net/BK7eTHNm">Petri net</a> structure 
  
    
      
        α
        (
        W
        )
        =
        (
        
          P
          
            W
          
        
        ,
        
          T
          
            W
          
        
        ,
        
          F
          
            W
          
        
        )
      
    
    {\displaystyle \alpha (W)=(P_{W},T_{W},F_{W})}
  
</li>
<li>with one input place 
  
    
      
        
          i
          
            W
          
        
      
    
    {\displaystyle i_{W}}
  
 and one output place 
  
    
      
        
          o
          
            W
          
        
      
    
    {\displaystyle o_{W}}
  
</li>
<li>because every transition of 
  
    
      
        
          T
          
            W
          
        
      
    
    {\displaystyle T_{W}}
  
 is on a 
  
    
      
        
          F
          
            W
          
        
      
    
    {\displaystyle F_{W}}
  
-path from 
  
    
      
        
          i
          
            W
          
        
      
    
    {\displaystyle i_{W}}
  
 to 
  
    
      
        
          o
          
            W
          
        
      
    
    {\displaystyle o_{W}}
  
, it is indeed a workflow net.</li></ul>
<p>For the example given above, the following petri net would be resultant of the application of alpha miner.
</p>
<h2 id="properties">Properties</h2>
<p>It can be shown <a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> 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 
  
    
      
        
          ≻
          
            W
          
        
      
    
    {\displaystyle \succ _{W}}
  
 relation is maximal. It is <i>not</i> required that all possible traces be present (which would be countably infinite for a net with a loop).
</p>
<h2 id="limitations">Limitations</h2>
<ul><li>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.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a></li>
<li>Loops: Alpha miner cannot discover loops of the length 1 and 2 in the process model.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a></li>
<li>Local dependencies are often missed in alpha miner.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a></li>
<li>Representational bias: Alpha miner can only discover petri net thus adding representational bias such as requirement on unique visible labels for every transition.<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>van der Aalst, W M P and Weijters, A J M M and Maruster, L (2004). "Workflow Mining: Discovering process models from event logs", IEEE Transactions on Knowledge and Data Engineering, vol 16 <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>van der Aalst, W.; Weijters, T.; Maruster, L. (September 2004). "Workflow mining: discovering process models from event logs". IEEE Transactions on Knowledge and Data Engineering. 16 (9): 1128–1142. doi:10.1109/TKDE.2004.47. ISSN 1558-2191. S2CID 5282914. <a href="https://ieeexplore.ieee.org/document/1316839" target="_blank">https://ieeexplore.ieee.org/document/1316839</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>van der Aalst, W.; Weijters, T.; Maruster, L. (September 2004). "Workflow mining: discovering process models from event logs". IEEE Transactions on Knowledge and Data Engineering. 16 (9): 1128–1142. doi:10.1109/TKDE.2004.47. ISSN 1558-2191. S2CID 5282914. <a href="https://ieeexplore.ieee.org/document/1316839" target="_blank">https://ieeexplore.ieee.org/document/1316839</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>van der Aalst et al. 2003 <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>"Discovering Petri Nets from Event Logs". ResearchGate. Retrieved 2021-08-31. <a href="https://www.researchgate.net/publication/265764352" target="_blank">https://www.researchgate.net/publication/265764352</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>"Limitations of Alpha miner" (PDF). Archived (PDF) from the original on 2021-08-31. <a href="https://courses.edsa-project.eu/pluginfile.php/281/mod_resource/content/0/17%20Alpha%20Algorithm%20-%20Limitations.pdf" target="_blank">https://courses.edsa-project.eu/pluginfile.php/281/mod_resource/content/0/17%20Alpha%20Algorithm%20-%20Limitations.pdf</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>"Limitations of Alpha miner" (PDF). Archived (PDF) from the original on 2021-08-31. <a href="https://courses.edsa-project.eu/pluginfile.php/281/mod_resource/content/0/17%20Alpha%20Algorithm%20-%20Limitations.pdf" target="_blank">https://courses.edsa-project.eu/pluginfile.php/281/mod_resource/content/0/17%20Alpha%20Algorithm%20-%20Limitations.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>"Limitations of Alpha miner" (PDF). Archived (PDF) from the original on 2021-08-31. <a href="https://courses.edsa-project.eu/pluginfile.php/281/mod_resource/content/0/17%20Alpha%20Algorithm%20-%20Limitations.pdf" target="_blank">https://courses.edsa-project.eu/pluginfile.php/281/mod_resource/content/0/17%20Alpha%20Algorithm%20-%20Limitations.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
</ol>

Alpha algorithm open-in-new

Alpha algorithm