Inductive miner

Inductive miner belongs to a class of algorithms used in process discovery. ^[1] Various algorithms proposed previously give process models of slightly different type from the same input. The quality of the output model depends on the soundness of the model. A number of techniques such as alpha miner, genetic miner, work on the basis of converting an event log into a workflow model, however, they do not produce models that are sound all the time. Inductive miner relies on building a directly follows graph from event log and using this graph to detect various process relations. ^[2]

Definitions

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:

${\displaystyle G(L)=(A_{L}\cup \{\blacktriangleright ,\blacksquare \},\rightarrow _{L},A_{L}^{s},A_{L}^{e})}$ ^[2]

Where

${\displaystyle A_{L}=Nodes{\text{(activities in the log)}},\blacktriangleright ={\text{virtual start node}},\blacksquare ={\text{virtual end node}}}$

${\displaystyle \rightarrow _{L}=edges}$ (directly follows relation) If some activity a is ever the first activity, then ${\displaystyle (\blacktriangleright ,a)\in \rightarrow _{L}}$. Similarly, if some activity a is ever the last activity, then ${\displaystyle (a,\blacksquare )\in \rightarrow _{L}}$

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

${\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. ^[2]

• Exclusive OR cut: The exclusive OR cut groups the activities such that the activities belonging to different groups have no relations between them.

${\displaystyle (\times ,A_{1},...,A_{n})}$ is an exclusive OR cut iff: ${\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)))}$

XOR cut - inductive miner

• 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.

${\displaystyle (\rightarrow _{L},A_{1},..,A_{n})}$ is a sequence cut iff: ${\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)))}$

Sequence cut - inductive miner

• 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.

${\displaystyle (\land ,A_{1},..,A_{n})}$ is a parallel cut iff:

- ${\displaystyle \forall i\in \{1,..,n\}(A_{i}\cap A_{L}^{s}\neq \emptyset \land A_{i}\cap A_{L}^{e}\neq \emptyset )}$

- ${\displaystyle \forall i,j\in \{1,..,n\}(\forall a\in A_{i},b\in A_{j}(i\neq j\Rightarrow a\rightarrow _{L}b))}$

Parallel cut - inductive miner

• 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.

${\displaystyle (\circlearrowleft ,A_{1},..,A_{n})}$ is a redo loop cut iff:

- ${\displaystyle n\geq 2}$

- ${\displaystyle A_{1}\supseteq A_{L}^{s}\cup A_{L}^{e}}$

- ${\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)))}$

- ${\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)))}$

- ${\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)))}$

Loop cut - inductive miner

Types

1. 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. ^{[3] [4]}
2. 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. ^[5]
3. Inductive miner for big data: This includes an improvement on the existing inductive miner to handle big data sets.^{[ citation needed ]}

References

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.
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.
3. Ghawi, Raji (2016). "Process Discovery using Inductive Miner and Decomposition". arXiv: 1610.07989 [cs.AI].
4. 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.
5. 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.