- Source: Inductive miner
Inductive miner belongs to a class of algorithms used in process discovery. 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.
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
L
s
,
A
L
e
)
{\displaystyle G(L)=(A_{L},\rightarrow _{L},A_{L}^{s},A_{L}^{e})}
Where
A
L
=
N
o
d
e
s
{\displaystyle A_{L}=Nodes}
(activities in the log)
→
L
=
e
d
g
e
s
{\displaystyle \rightarrow _{L}=edges}
(directly follows relation)
A
L
s
=
S
t
a
r
t
n
o
d
e
{\displaystyle A_{L}^{s}=Startnode}
A
L
e
=
E
n
d
n
o
d
e
{\displaystyle A_{L}^{e}=Endnode}
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.
(
×
,
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)))}
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
)
{\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)))}
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.
(
∧
,
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))}
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.
(
↺
,
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)))}
Types
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.
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.
Inductive miner for big data: This includes an improvement on the existing inductive miner to handle big data sets.
References
Kata Kunci Pencarian:
- Inductive miner
- Process mining
- Inductive charging
- Business process discovery
- Machine learning
- Outline of machine learning
- Group method of data handling
- Scientific Revolution
- Formal concept analysis
- Light-emitting diode
