연구실에서 야근하면서 실험 돌려놓고 소재를 찾아 나서다가 과거의 나가 미래의 나에게 던져 놓은 소재 거리를 발견했다.
저번 포스팅에서 우리는 Alignment based conformance checking이 무엇인지에 대해 알아보았다.
Alignment based conformance checking이란? (Alignment를 이용한 적합도 검증) - 기본편
Conformane Checking (적합도 검증)이란, 프로세스 모델이 실제 이벤트 로그에 얼마나 잘 부합하는지, 즉 프로세스 모델이 실제 데이터와 비교해봤을 때 얼마나 잘 맞는지를 검증하는 것을 말한다. 이번 포스팅에..
process-mining.tistory.com
하지만 저번 포스팅에서는 하나의 trace에 대해 alignment와 이를 기반으로 한 conformance를 계산하는 방법에 대해서만 알아보았다. 하지만 실제 이벤트 로그는 대부분의 경우에(항상이라고 해도 무방) 하나의 trace로 구성되어 있지 않다. 그래서 이번 포스팅에서는 실제 이벤트 로그에 대해서 alignment based conformance checking을 하는 방법에 대해 알아보고자 한다.
사실 위 포스팅만 이해하면 정말 간단하다. 다음과 같은 페트리 넷과 이벤트 로그가 있다고 하자.
각 trace의 optimal alignment 도출
우선, 각 trace에 대해서 optimal alignment를 찾아야 한다. (optimal alignment를 찾는 구체적인 방법에 대해서는 다음 포스팅에서 다루도록 하겠다. 지금은 manual 하게 찾도록 하자.) 우선, <b, c, a, c, d>는 위 페트리 넷에서 perfectly fitting 한다.
| b | c | a | d | e |
| b | c | a | d | e |
그리고 <c, b, a, b, c, e>에 대한 optimal alignment는 다음과 같고, 이것의 cost는 3이다.
| c | b | >> | a | b | c | e | >> | >> |
| c | b | tau | a | >> | c | >> | d | tau |
| t3 | t6 | t7 | t1 | t3 | t4 | t7 |
(위 표에서 tau는 silent transition을, 가장 아래의 행은 transition의 이름을 말한다. (중복 transition 때문에 표시함))
식에 따른 fitness 계산
각 trace의 optimal alignment를 도출했으면, 이제 이를 바탕으로 식에 따라 alignment based fitness를 계산할 차례이다. 그 계산식은 다음과 같다.
위 식에서 각각의 수식의 의미는 다음과 같다.
- cost(L, M): 이벤트 로그 전체의 cost의 합. 우리의 예시의 경우에는 <b,c,a,c,d>의 cost가 0이고 <c,b,a,b,c,e>의 cost가 3이기 때문에 cost(L,M) = 5*0 + 5*3 = 15가 된다.
- move_L(L): 이벤트 로그의 trace 길이의 합을 말한다. 우리의 예시의 경우에는 5*5 + 6*5 = 55가 된다.
- |L|: 이벤트 로그의 trace 개수를 말한다. 우리의 예시의 경우에는 10이 된다.
- move_M(M): model에서 나타날 수 있는 가장 짧은 하나의 fitting trace의 길이를 말한다. 우리의 예시의 경우에는 <b, c, tau>이기 때문에 2가 된다.
이 식의 의미를 설명하자면 다음과 같다. (식만 이용해도 되는 사람들은 넘어가도 좋다.) optimal alignment는 cost가 0인, 즉 perfectly fitting 하는 trace를 말한다. 하지만 optimal alignment가 아닌 경우에는 cost가 발생하게 되고, 이 cost가 가장 cost가 클 때 (worst fitting trace)에 비해 얼마나 큰지에 따라 fitness를 계산할 수 있다. 즉, optimal alignment의 cost가 worst fitting trace의 cost에 가까우면 가까울수록 fitness 값이 작아지는 것이다.
그러므로 우리의 예시를 위 식에 따라 계산해보면 다음과 같이 fitness를 구할 수 있다.
이번 포스팅에서는 하나의 trace에 대해 alignment를 구하는 방법을 다루었던 저번 포스팅에 이어 전체 이벤트 로그에 대해 alignment based conformance checking을 하는 방법에 대해 알아보았다. 이 방법을 통해 이벤트 로그의 behavior와 가장 가까운 프로세스 모델의 behavior를 찾음으로써 fitness를 계산하는, 가장 정확하고 현실적인 conformance checking이 가능하다.
최근댓글