Inductive miner explained

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]

__TOC__

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:

G(L) = (A _{L,} → _{L,} A ^{s} _{L,} A ^{e} _{L)}

Where

A _{L} = Nodes (activities in the log)→ _{L} = edges (directly follows relation)A ^{s} _{L} = Start node A ^{e} _{L} = End node

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.

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

( x , A _{1,} ... , A _{n)} is an exclusive OR cut iff: \forall i,j \in \{ 1 , .. , n\} (\forall a \in A _{i,} b \in A _{j} (i ≠ j ⇒ \neg(a → _{L} b) ))

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

( → _{L,} A _{1,} .. , A _{n)} is a sequence cut iff: \forall i,j \in \{ 1 , .. , n\} (\forall a \in A _{i,} b \in A _{j} (a → _{L} b \land \neg(b → _{L} a)) )

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

(\land, A _{1,} .. , A _{n)} is a parallel cut iff:

-

\forall i \in \{ 1 , .., n\} ( A _{i} \cap A ^{s} _{L} ≠ \emptyset \land A _{i} \cap A ^{e} _{L} ≠ \emptyset )

-

\forall i,j \in \{ 1 , .. , n\} (\forall a \in A _{i,} b \in A _{j} (i ≠ j ⇒ a → _{L} b ))

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

(\circlearrowleft, A _{1,} .. , A _{n)} is a redo loop cut iff:

-

n \geq 2

-

A _{1} \supseteq A ^{s} _{L} \cup A ^{e} _{L}

-

\forall i,j \in \{ 2 , .. , n\} (\forall a \in A _{i,} b \in A _{j} (i ≠ j ⇒ \neg(a → _{L} b) ))

-

\forall i \in \{ 2 , .. , n\} (\forall b \in A _{i} (\exists a \in A ^{e} _{L} (a → _{L} b)) ⇒ (\forall a \in A ^{e} _{L} (a → _{L} b) ))

-

\forall i \in \{ 2 , .. , n\} (\forall b \in A _{i} (\exists a \in A ^{s} _{L} (b → _{L} a)) ⇒ (\forall a \in A ^{s} _{L} (b → _{L} a) ))

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.

References

1. Process Discovery Capturing the Invisible. IEEE Computational Intelligence Magazine. Wil van der Aalst. March 2010. 5. 28–41. 10.1109/MCI.2009.935307. 14520822 .
2. Leemans. Sander J. J.. Fahland. Dirk. van der Aalst. Wil M. P.. 2013. Colom. José-Manuel. Desel. Jörg. 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. en. Berlin, Heidelberg. Springer. 311–329. 10.1007/978-3-642-38697-8_17. 978-3-642-38697-8.
3. 1610.07989. Ghawi. Raji. Process Discovery using Inductive Miner and Decomposition. 2016. cs.AI.
4. Book: Leemans, S. J. J.. 2017-05-09. Robust process mining with guarantees - SIKS Dissertation Series No. 2017-12. 978-90-386-4257-4. TU/e - Eindhoven University of Technology.
5. Leemans. Sander J. J.. Fahland. Dirk. van der Aalst. Wil M. P.. 2014. Lohmann. Niels. Song. Minseok. Wohed. Petia. Discovering Block-Structured Process Models from Event Logs Containing Infrequent Behaviour. Business Process Management Workshops. Lecture Notes in Business Information Processing. 171. en. Cham. Springer International Publishing. 66–78. 10.1007/978-3-319-06257-0_6. 978-3-319-06257-0.