Inductive miner

<h2 id="definitions">Definitions</h2>
A directly follows graph is a directed graph that connects an activity A to another activity B if and only if activity B occurs chronologically right after activity A for any given case in the respective event log. A directly follows graph is represented mathematically by:

 
 
 
 G
 (
 L
 )
 =
 (
 
 A
 
 L
 
 
 ∪
 {
 ▸
 ,
 ◼
 }
 ,
 
 →
 
 L
 
 
 ,
 
 A
 
 L
 
 
 s
 
 
 ,
 
 A
 
 L
 
 
 e
 
 
 )
 
 
 {\displaystyle G(L)=(A_{L}\cup \{\blacktriangleright ,\blacksquare \},\rightarrow _{L},A_{L}^{s},A_{L}^{e})}
 
<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>
Where

 
 
 
 
 A
 
 L
 
 
 =
 N
 o
 d
 e
 s
 
 (activities in the log)
 
 ,
 ▸
 =
 
 virtual start node
 
 ,
 ◼
 =
 
 virtual end node
 
 
 
 {\displaystyle A_{L}=Nodes{\text{(activities in the log)}},\blacktriangleright ={\text{virtual start node}},\blacksquare ={\text{virtual end node}}}
 
 

 
 
 
 
 →
 
 L
 
 
 =
 e
 d
 g
 e
 s
 
 
 {\displaystyle \rightarrow _{L}=edges}
 
 (directly follows relation) If some activity a is ever the first activity, then

(
        ▸
        ,
        a
        )
        ∈
        
          →
          
            L
          
        
      
    
    {\displaystyle (\blacktriangleright ,a)\in \rightarrow _{L}}
  
. Similarly, if some activity a is ever the last activity, then 
  
    
      
        (
        a
        ,
        ◼
        )
        ∈
        
          →
          
            L
          
        
      
    
    {\displaystyle (a,\blacksquare )\in \rightarrow _{L}}

A
 
 L
 
 
 s
 
 
 =
 {
 a
 ∈
 
 A
 
 L
 
 
  
 
 |
 
  
 (
 ▸
 ,
 a
 )
 ∈
 
 →
 
 L
 
 
 }
 
 
 {\displaystyle A_{L}^{s}=\{a\in A_{L}\ |\ (\blacktriangleright ,a)\in \rightarrow _{L}\}}
 
 the set of all "starting nodes"

 
 
 
 
 A
 
 L
 
 
 e
 
 
 =
 {
 a
 ∈
 
 A
 
 L
 
 
  
 
 |
 
  
 (
 a
 ,
 ◼
 )
 ∈
 
 →
 
 L
 
 
 }
 
 
 {\displaystyle A_{L}^{e}=\{a\in A_{L}\ |\ (a,\blacksquare )\in \rightarrow _{L}\}}
 
 the set of all "ending nodes"
The inductive miner technique relies on the detection of various cuts on the directly follows graph created using the event log. The core idea behind inductive miner lies in the unique methodology of discovering various divisions of the arcs in the directly follows graph, and using the smaller components after division to represent the execution sequence of the activities. The inductive miner algorithm uses the directly follows graph to detect one of the following cuts.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<ul><li>Exclusive OR cut: The exclusive OR cut groups the activities such that the activities belonging to different groups have no relations between them.</li></ul>

 
 
 
 (
 ×
 ,
 
 A
 
 1
 
 
 ,
 .
 .
 .
 ,
 
 A
 
 n
 
 
 )
 
 
 {\displaystyle (\times ,A_{1},...,A_{n})}
 
 is an exclusive OR cut iff: 
 
 
 
 ∀
 i
 ,
 j
 ∈
 {
 1
 ,
 .
 .
 ,
 n
 }
 (
 ∀
 a
 ∈
 
 A
 
 i
 
 
 ,
 b
 ∈
 
 A
 
 j
 
 
 (
 i
 ≠
 j
 ⇒
 ¬
 (
 a
 
 →
 
 L
 
 
 b
 )
 )
 )
 
 
 {\displaystyle \forall i,j\in \{1,..,n\}(\forall a\in A_{i},b\in A_{j}(i\neq j\Rightarrow \neg (a\rightarrow _{L}b)))}

<ul><li>Sequence cut: The sequence cut groups activities such that activities between them have a directly follows relation from previous group to next group but not the other way around.</li></ul>

 
 
 
 (
 
 →
 
 L
 
 
 ,
 
 A
 
 1
 
 
 ,
 .
 .
 ,
 
 A
 
 n
 
 
 )
 
 
 {\displaystyle (\rightarrow _{L},A_{1},..,A_{n})}
 
 is a sequence cut iff: 
 
 
 
 ∀
 i
 ,
 j
 ∈
 {
 1
 ,
 .
 .
 ,
 n
 }
 (
 ∀
 a
 ∈
 
 A
 
 i
 
 
 ,
 b
 ∈
 
 A
 
 j
 
 
 (
 a
 
 →
 
 L
 
 
 b
 ∧
 ¬
 (
 b
 
 →
 
 L
 
 
 a
 )
 )
 )
 
 
 {\displaystyle \forall i,j\in \{1,..,n\}(\forall a\in A_{i},b\in A_{j}(a\rightarrow _{L}b\land \neg (b\rightarrow _{L}a)))}

<ul><li>Parallel cut: Parallel cut groups activities such that each group has a start activity and an end activity, and the activities between the groups have directly follows relations between them.</li></ul>

 
 
 
 (
 ∧
 ,
 
 A
 
 1
 
 
 ,
 .
 .
 ,
 
 A
 
 n
 
 
 )
 
 
 {\displaystyle (\land ,A_{1},..,A_{n})}
 
 is a parallel cut iff:
- 
 
 
 
 ∀
 i
 ∈
 {
 1
 ,
 .
 .
 ,
 n
 }
 (
 
 A
 
 i
 
 
 ∩
 
 A
 
 L
 
 
 s
 
 
 ≠
 ∅
 ∧
 
 A
 
 i
 
 
 ∩
 
 A
 
 L
 
 
 e
 
 
 ≠
 ∅
 )
 
 
 {\displaystyle \forall i\in \{1,..,n\}(A_{i}\cap A_{L}^{s}\neq \emptyset \land A_{i}\cap A_{L}^{e}\neq \emptyset )}

- 
 
 
 
 ∀
 i
 ,
 j
 ∈
 {
 1
 ,
 .
 .
 ,
 n
 }
 (
 ∀
 a
 ∈
 
 A
 
 i
 
 
 ,
 b
 ∈
 
 A
 
 j
 
 
 (
 i
 ≠
 j
 ⇒
 a
 
 →
 
 L
 
 
 b
 )
 )
 
 
 {\displaystyle \forall i,j\in \{1,..,n\}(\forall a\in A_{i},b\in A_{j}(i\neq j\Rightarrow a\rightarrow _{L}b))}

<ul><li>Redo loop cut: A loop cut groups elements into two parts. A do part and a redo part. The activities in the event log from a redo loop cut can start and end only with the activities from the do part.</li></ul>

 
 
 
 (
 ↺
 ,
 
 A
 
 1
 
 
 ,
 .
 .
 ,
 
 A
 
 n
 
 
 )
 
 
 {\displaystyle (\circlearrowleft ,A_{1},..,A_{n})}
 
 is a redo loop cut iff:
- 
 
 
 
 n
 ≥
 2
 
 
 {\displaystyle n\geq 2}

- 
 
 
 
 
 A
 
 1
 
 
 ⊇
 
 A
 
 L
 
 
 s
 
 
 ∪
 
 A
 
 L
 
 
 e
 
 
 
 
 {\displaystyle A_{1}\supseteq A_{L}^{s}\cup A_{L}^{e}}

- 
 
 
 
 ∀
 i
 ,
 j
 ∈
 {
 2
 ,
 .
 .
 ,
 n
 }
 (
 ∀
 a
 ∈
 
 A
 
 i
 
 
 ,
 b
 ∈
 
 A
 
 j
 
 
 (
 i
 ≠
 j
 ⇒
 ¬
 (
 a
 
 →
 
 L
 
 
 b
 )
 )
 )
 
 
 {\displaystyle \forall i,j\in \{2,..,n\}(\forall a\in A_{i},b\in A_{j}(i\neq j\Rightarrow \neg (a\rightarrow _{L}b)))}

- 
 
 
 
 ∀
 i
 ∈
 {
 2
 ,
 .
 .
 ,
 n
 }
 (
 ∀
 b
 ∈
 
 A
 
 i
 
 
 (
 ∃
 a
 ∈
 
 A
 
 L
 
 
 e
 
 
 (
 a
 
 →
 
 L
 
 
 b
 )
 )
 ⇒
 (
 ∀
 a
 ∈
 
 A
 
 L
 
 
 e
 
 
 (
 a
 
 →
 
 L
 
 
 b
 )
 )
 )
 
 
 {\displaystyle \forall i\in \{2,..,n\}(\forall b\in A_{i}(\exists a\in A_{L}^{e}(a\rightarrow _{L}b))\Rightarrow (\forall a\in A_{L}^{e}(a\rightarrow _{L}b)))}

- 
 
 
 
 ∀
 i
 ∈
 {
 2
 ,
 .
 .
 ,
 n
 }
 (
 ∀
 b
 ∈
 
 A
 
 i
 
 
 (
 ∃
 a
 ∈
 
 A
 
 L
 
 
 s
 
 
 (
 b
 
 →
 
 L
 
 
 a
 )
 )
 ⇒
 (
 ∀
 a
 ∈
 
 A
 
 L
 
 
 s
 
 
 (
 b
 
 →
 
 L
 
 
 a
 )
 )
 )
 
 
 {\displaystyle \forall i\in \{2,..,n\}(\forall b\in A_{i}(\exists a\in A_{L}^{s}(b\rightarrow _{L}a))\Rightarrow (\forall a\in A_{L}^{s}(b\rightarrow _{L}a)))}

<h2 id="types">Types</h2>
<ol><li>Inductive miner with fall through: The complex event log sometimes would make it impossible to detect any cuts using the above techniques. In that case, there are additional fall throughs that can be applied to obtain better representation of process tree instead of a flower model.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a></li>
<li>Inductive miner frequency-based: The less frequent relations in the event log sometimes creates problems in detecting any type of cuts. In that case, the directly follows relations below a certain threshold are removed from the directly follows graph and the resultant graph is used for detecting the cuts.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a></li>
<li>Inductive miner for big data: This includes an improvement on the existing inductive miner to handle big data sets.</li></ol>

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

<ol>
<li id="fn:1">Wil van der Aalst (March 2010). "Process Discovery Capturing the Invisible". IEEE Computational Intelligence Magazine. 5: 28–41. doi:10.1109/MCI.2009.935307. S2CID 14520822. <a href="/wiki/Wil_van_der_Aalst" target="_blank">/wiki/Wil_van_der_Aalst</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Leemans, Sander J. J.; Fahland, Dirk; van der Aalst, Wil M. P. (2013). Colom, José-Manuel; Desel, Jörg (eds.). "Discovering Block-Structured Process Models from Event Logs - A Constructive Approach". Application and Theory of Petri Nets and Concurrency. Lecture Notes in Computer Science. 7927. Berlin, Heidelberg: Springer: 311–329. doi:10.1007/978-3-642-38697-8_17. ISBN 978-3-642-38697-8. <a href="978-3-642-38697-8" target="_blank">978-3-642-38697-8</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Leemans, Sander J. J.; Fahland, Dirk; van der Aalst, Wil M. P. (2013). Colom, José-Manuel; Desel, Jörg (eds.). "Discovering Block-Structured Process Models from Event Logs - A Constructive Approach". Application and Theory of Petri Nets and Concurrency. Lecture Notes in Computer Science. 7927. Berlin, Heidelberg: Springer: 311–329. doi:10.1007/978-3-642-38697-8_17. ISBN 978-3-642-38697-8. <a href="978-3-642-38697-8" target="_blank">978-3-642-38697-8</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Leemans, Sander J. J.; Fahland, Dirk; van der Aalst, Wil M. P. (2013). Colom, José-Manuel; Desel, Jörg (eds.). "Discovering Block-Structured Process Models from Event Logs - A Constructive Approach". Application and Theory of Petri Nets and Concurrency. Lecture Notes in Computer Science. 7927. Berlin, Heidelberg: Springer: 311–329. doi:10.1007/978-3-642-38697-8_17. ISBN 978-3-642-38697-8. <a href="978-3-642-38697-8" target="_blank">978-3-642-38697-8</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Ghawi, Raji (2016). "Process Discovery using Inductive Miner and Decomposition". arXiv:1610.07989 [cs.AI]. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Leemans, S. J. J. (2017-05-09). Robust process mining with guarantees - SIKS Dissertation Series No. 2017-12 (PDF). TU/e - Eindhoven University of Technology. ISBN 978-90-386-4257-4. <a href="978-90-386-4257-4" target="_blank">978-90-386-4257-4</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Leemans, Sander J. J.; Fahland, Dirk; van der Aalst, Wil M. P. (2014). Lohmann, Niels; Song, Minseok; Wohed, Petia (eds.). "Discovering Block-Structured Process Models from Event Logs Containing Infrequent Behaviour". Business Process Management Workshops. Lecture Notes in Business Information Processing. 171. Cham: Springer International Publishing: 66–78. doi:10.1007/978-3-319-06257-0_6. ISBN 978-3-319-06257-0. <a href="978-3-319-06257-0" target="_blank">978-3-319-06257-0</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Inductive miner open-in-new

Inductive miner