이벤트 로그가 한 프로세스 모델로부터 나타날 수 있는 모든 behavior를 다 표시할 수 있다면 정말 아름다운 세상일 것이다. 하지만 현실은 그렇지 않다. 만약 나타날 수 있는 액티비티의 종류가 5개라고 하자. 그러면 모든 behavior를 다 허용한다고 할 때 가능한 behavior의 개수는 5*4*3*2*1 = 120개일 것이다. 하지만 만약 액티비티의 종류가 10개라면? 10! = 약 삼백육십만 개의 behavior가 가능하다. 이들을 모두 표현하는 이벤트 로그가 있을까? 현실적으로 불가능하다. 그렇기 때문에 우리는 incomplete한 이벤트 로그를 이용해서도 좋은 프로세스 모델을 도출할 수 있어야 한다. 이러한 생각에서 나온 inductive miner 알고리즘이 IMin 알고리즘이다. 이번 포스팅에서는 incomplete 이벤트 로그를 다루는 IMin 알고리즘에 대해서 알아볼 것이다.
* 수식 많음 주의. 하지만 심혈을 기울여 최대한 쉽게 풀어 썼다.
* 이 글의 이해를 위해서는 기본적인 inductive miner에 대한 이해가 필요하다. 자세한 것은 다음 포스팅을 참고한다.
2019/07/23 - [Process Mining - Theory/Process Discovery] - Inductive Miner란?
Inductive Miner란?
한 달 만의 글이다. 학회와 시험과 여행의 조합으로 이제야 일상으로 돌아왔다. 그리웠다... 20일 뒤에 또 시험인 것은 함정 ^_^ Inductive Miner는 Process Discovery 알고리즘 중 하나로, 이벤트 로그로부터 프..
process-mining.tistory.com
DFG와 Transitive Closure
IMin 알고리즘은 기본적으로 이벤트 로그가 incomplete하다는 가정을 하기 때문에, 이벤트 로그에서 실제로 보여진 cut을 찾는 것이 아닌, 가장 확률이 높은 cut을 찾는 것을 기본 아이디어로 한다. 이를 위해서는 DFG(Directly-Follows Graph)와 함께 transitive closure를 이용해야 한다. DFG가 무엇인지 모른다면 다음 포스팅을 참고한다.
2019/06/21 - [Process Mining - Theory/Process Model] - DFG(Directly Followed Graph)란?
DFG(Directly Followed Graph)란?
Directly Followed Graph란, 각 액티비티 간의 directly follow 관계 (a->b)만을나타낸 그래프를 말한다. 이는 가장 널리 쓰이는 Process Discovery 방식 중 하나인 Inductive Miner를 사용할 때에 기본이 된다...
process-mining.tistory.com
Transitive Closure란, DFG처럼 직접적인 연결관계를 찾는 것이 아닌, 최종적으로 a로부터 b state에 도달할 수 있는가를 의미한다. 예를 들어, 다음과 같은 이벤트 로그가 있다고 하자.
이 이벤트 로그에서 DFG를 찾으면 다음과 같다.
이 때, c로부터 d를 지나면 e로 도달할 수 있다. 이렇게 직접적으로 연결되지는 않았지만 결과적으로 도달할 수 있는 것까지 모두 그래프로 표현한 것을 transitive clsoure을 표현했다고 한다. 이를 그래프로 나타내면 다음과 같다.
Closest Cut 찾기
DFG와 Transitive clsoure graph를 다 만들었다면 이제 이를 바탕으로 closest cut을 찾을 차례이다. 이를 위해 다음과 같은 표를 사용한다.
이 표를 이용해서 앞으로 cut을 찾을 때에 각 액티비티 pair별 확률을 계산한다.
XOR, Sequence, Parallel Cut
우선, XOR, sequence, parallel cut에 대한 계산식은 다음과 같다.
예를 들어, 우리가 위에서 보았던 예시 이벤트 로그에서, {a,b,c}, {d,e,f,g}가 sequence cut으로 나뉘는 확률을 구하고 싶다고 하자. 그러면 sigma1은 {a,b,c}, sigma2는 {d,e,f,g}, operator는 sequence가 될 것이다. 그러므로 우리는 다음과 같은 식을 계산하면 된다.
이 식을 계속 계산해보면 다음과 같다.
그렇다면 이 p->(a,d)를 어떻게 계산할 수 있을까? 이들을 계산할 때 위에서 봤던 표를 사용한다. 우선, a와 d의 DFG와 transitive clsoue 관계를 다시 파악하기 위해 DFG와 transitive clsoure를 본다.
a->d (directly follows) 관계가 있고, a->+d (transitive clsoure) 관계가 있고 (DF가 있으니 당연하다.), d->a 관계는 없고 d->+a 관계도 없다. 그러므로 우리는 위 표에서 이 행을 선택할 수 있다.
이 때, z를 구하는 식은 ( |a| + |b| ) / 2이고 우리의 이벤트 로그로부터 a와 b가 일어난 횟수를 각각 구하면 2, 2이기 때문에 z가 2가 된다. 그러므로 p->(a,b)는 1-1/3 = 2/3이 된다. 이런 식으로 모든 관계에 대해 확률을 구하고, 식에 대입해주면 우리가 원하는 {a,b,c}, {d,e,f,g}가 sequence cut일 확률을 구할 수 있다. (모든 계산은 생략한다.)
Loop Cut
Loop Cut에 대한 계산식은 다음과 같다. 수식이 길어 어려워 보이지만 전혀 그렇지 않다.
우리에게는 다음과 같은 이벤트 로그가 있었다. (sigma1은 {d,e}, sigma2는 {f}라고 가정한다.)
위 식에서 End(L)과 Start(L)은 각각 각 trace의 end activity, start activity를 의미한다. 그러므로 우리의 이벤트 로그에서 End(L)은 {e,g}, Start(L)은 {a,b,c}가 된다.
그리고 S_2와 E_2는 각각 loop body end activity 뒤에 오는 액티비티 집합, loop body start activity 앞에 오는 액티비티 집합을 말한다. 예를 들어, 우리의 이벤트 로그에서는 d, e, f로 이루어진 루프가 보이는 것 같은 패턴이 나타난다. 이들은 {d,e,f,d,e,f,d,e}, {d,e}, {d,e,f,d,e}로 구성되어 있으므로 loop body는 d,e, body가 아닌 부분은 f가 될 것이다. 그러므로 loop body end activity는 e, loop body start activity는 d가 된다. 그러므로 이벤트 로그에서 S_2는 loop body end activity인 e 뒤에 오는 액티비티인 f가 되고, E_2는 loop body start activity인 d 앞에 오는 액티비티인 f가 된다. 즉, 우리가 구한 것들을 정리해보면 다음과 같다.
이에 따라서 위 식에 따라 redo_start, redo_end, indirect를 정리하면 다음과 같다.
이들을 이 표에 따라 계산해주고
아래 식에 대입해서 계산하면 loop cut 확률을 계산할 수 있다.
이런 식으로 각 액티비티 뭉치들에 대해서 XOR, Parallel, Sequence, Loop cut 확률을 모두 계산하여 가장 확률이 높은 Cut을 해당 trace의 Cut으로 정함으로써 process tree를 도출할 수 있다. 계산 과정을 모두 나열하면 글이 너무너무 길어질 것이기 때문에 결과를 보여주는 것으로 생략한다.
이번 포스팅에서는 Incomplete log들에 대해서 좋은 성능을 보이는 Inductive miner인 IMin 알고리즘에 대해 알아보았다. 이 알고리즘을 활용하면 trace의 개수가 적은 이벤트 로그에 대해서도 Inductive Miner를 이용해 좀 더 정확하게 process discovery를 하는 것이 가능하다.
References
1. Leemans S.J.J., Fahland D., van der Aalst W.M.P. (2014) Discovering Block-Structured Process Models from Incomplete Event Logs. In: Ciardo G., Kindler E. (eds) Application and Theory of Petri Nets and Concurrency. PETRI NETS 2014. Lecture Notes in Computer Science, vol 8489. Springer, Cham
최근댓글