Inductive Miner Fall Through (Inductive Miner에서 Cut을 찾을 수 없을 때)

 저번 포스팅에서 우리는 Inductive Miner가 어떻게 프로세스 모델을 도출하는지에 대해 알아보았다. 

2019/07/23 - [Theory/Process Discovery] - Inductive Miner란?

불러오는 중입니다...

 Inductive MIner는 기본적으로 DFG로부터 Cut을 찾아냄으로써 이를 이용하여 프로세스 트리를 만들어내는 알고리즘이다. 그렇다면 만약 DFG로부터 cut을 찾을 수 없다면 어떻게 해야할까? 그렇다면 로그에 해당하는 모든 trace를 표현할 수 있는 프로세스 모델이 도출되어야 할 것이다. 그 때 적용해야 하는 것이 Fall Through이다. 이번 포스팅에서는 이 Fall Through에 대해 설명하려고 한다.

 Fall Through

  Empty Trace

 Inductive Miner를 적용하다가 empty trace가 발생했다고 하자. 이 empty trace는 DFG에 표현되지 않기 때문에 이를 projection하는 것은 불가능하다. 그러므로 empty trace가 로그에 있을 때에는, silent transition과 나머지 trace 사이의 Exclusive Choice를 return한다. 예를 들어, 다음과 같은 empty trace가 포함된 이벤트 로그가 있다고 하자.

empty trace가 있는 이벤트 로그

 그렇다면 이것은 다음과 같이 처리될 것이다.

즉, silent transition을 추가한 후 empty trace를 제외한 나머지 trace에 대해 inductive miner를 다시 진행하면 된다. 

 

 Activity once per Trace

 DFG에서 cut을 찾을 수 없는데 하나의 액티비티가 모든 트레이스에 대해서 딱 한 번씩 일어나는 이벤트 로그가 있다고 하자. 그러면 우리는 이 액티비티와 나머지 trace들이 parallel 관계에 있다고 취급한다. 만약 이러한 액티비티가 여러 개라면 하나만 선택하여 진행한다. 예를 들어, 다음과 같은 이벤트 로그가 있다고 하자. 

a가 한 번씩 일어나는 이벤트 로그

 위 이벤트 로그에서는 액티비티 a가 모든 trace에 대해 한 번씩 일어난다. 그렇기 때문에 우리는 이를 다음과 같이 처리할 수 있다.

Activity Concurrent

 DFG에서 cut을 찾을 수 없는 상황에서 어떤 액티비티를 없애는 것이 cut을 찾아주는 경우가 있을 수 있다. 그런 경우에는 해당 액티비티에 대한 sublog와 다른 액티비티들에 대한 sublog를 분리하고, 서로가 parallel한 모델을 return한다. 예를 들어, 다음과 같은 이벤트 로그가 있다고 하자.

 위 이벤트 로그에서 a 액티비티를 없애면 c, d에 대해 sequence cut을 찾을 수 있다. 그렇기 때문에 우리는 이를 다음과 같이 처리할 수 있다.

Strict Tau Loop

 이벤트 로그에서 start activity 다음에 end activity가 오는 것이 있으면, 그 부분을 cut하고 이를 이벤트 로그로 projection한다. 다음과 같은 이벤트 로그가 있다고 하자.

이 이벤트 로그의 start activity는 a, d, b이고, end activity는 d, b, c이다. 우리는 start activity 바로 다음에 end activity가 오는 것을 찾는 것이 목적이므로, 다음과 같이 이를 찾을 수 있다.

start activity followed by end activity

그러면 우리는 다음과 같은 이벤트 로그 L'를 return할 수 있다. 

위 예시처럼 하나 이상의 split이 일어났다면, 우리는 다음과 같은 프로세스 트리를 return한다.

Tau loop

이벤트 로그에서 start activity가 일어난다면 그 뒤를 무조건 cut하고 이를 이벤트 로그 L'로 분리한다. 

 위에서도 보았듯이 이 이벤트 로그의 start activity는 a, d, b이고, end activity는 d, b, c이다. 우리는 start activity를 찾는 것이 목적이므로, 다음과 같이 이를 찾을 수 있다.

start activity

그러면 우리는 다음과 같은 이벤트 로그 L'를 return할 수 있다.

위 예시처럼 하나 이상의 split이 일어났다면, 우리는 strict tau loop와 마찬가지로 다음과 같은 프로세스 트리를 return한다. 

Flower Model

만약 위의 방법이 모두 적용 불가능하다면 어떻게 해야 할까? 답은 해당 DFG에 있는 모든 액티비티에 대해서 flower model을 만듦으로써 모든 trace를 표현할 수 있게 만드는 것이다. 그러므로 다음과 같은 프로세스 트리를 return한다.

 

 이번 포스팅에서는 저번 포스팅에 이어서 Inductive Miner에서 Cut을 찾을 수 없을 때 이를 어떻게 처리해야 하는지에 대해 알아보았다. Fall Through의 핵심은 로그에 해당하는 모든 trace를 표현할 수 있는 프로세스 모델이 도출되도록 하는 것이다. 다음 포스팅에서는 자주 일어나지 않는 패턴(Infrequent behavior)이나 완전하지 못한 패턴(Incomplete behavior), 그리고 빅 데이터에 대해서 inductive miner를 어떻게 적용할 수 있는지에 대해 알아보겠다.

 

References

1. Course: Advanced Process Mining. RWTH. Dr. Sebastiaan van Zelst.