요즘 프로세스 마이닝을 잠시 접어 두고 데이터 마이닝 세포 되살리기를 좀 하느라 포스팅이 뜸했다. 간만의 포스팅!!
저번 포스팅까지 우리는 alignment based conformance checking이 무엇인지에 대해서 알아보았다. (이 포스팅의 이해를 위해서는 아래 포스트에 대한 이해가 필요하다.)
Alignment based conformance checking을 위해서 우리가 모든 trace에 대해 하나하나 optimal alignment를 손으로 찾을 수는 없을 것이다. 그래서 이번 포스팅에서는, 이 optimal alignment를 계산하는 구체적인 방법에 대해 알아보겠다.
Synchronous Product Net
한 trace의 Optimal Alignment를 계산하기 위해서는 우선 해당 trace와 페트리 넷 사이의 synchronous product net을 도출해야 한다. 우선, 쉬운 설명을 위해 언제나처럼 예시와 함께 설명하도록 하겠다. <add items, add items, finalize, finalize>라는 trace와 다음과 같은 페트리 넷이 있다고 하자.
Synchronous Product Net은 다음과 같은 과정을 통해서 도출할 수 있다.
1. Trace의 움직임을 나타내는 페트리 넷을 만든다. (Log Move)
해당 trace의 움직임을 나타내는 페트리 넷을 만든다. 우리의 예시 trace는 <add items, add items, finalize, finalize>이기 때문에 이에 해당하는 페트리 넷을 다음과 같이 만들 수 있다.
이 페트리 넷에서 transition이 일어나는 것은 log에서 transition이 일어나는 log move와 같을 것이다.
2. 1에서 만든 페트리 넷과 프로세스 모델의 페트리 넷(model move)의 비교를 위해 이들을 각각 위아래에 배치한다.
3. synchronous move를 표시한다.
위에서 log move, model move를 표시하는 페트리 넷을 각각 만들었으니 이들이 일치해서 움직이는 것을 표시하는 synchonous move를 표시할 차례이다. 이는 log move의 페트리 넷에 있는 transition과 model move의 페트리 넷에 있는 transition의 label이 일치하는 pair를 모두 표시함으로써 나타낸다.
예를 들어, add items라는 synchronous move를 표시하고 싶다고 하자. log move net에서는 t1'과 t2', model move net에서는 t1과 t2가 add items transition이다. 그러면 우리는 (t1', t1), (t1', t2), (t2', t1), (t2', t2)의 네 개의 synchronous transition을 표시할 수 있다. 이때, 이 synchornous transition의 input place와 output place는 log move와 model move에서 해당 transition의 input place와 output place가 된다. 글보다는 아래 그림이 더 이해가 쉬울 것 같다.
(t1', t1)에 해당하는 synchronout transition의 input place가 t1'의 input place인 p1'과 t1의 input place인 p1, output place가 t1'의 output place인 p2'과 t1의 output place인 p2임을 알 수 있다. 이와 같은 형태로 (t1', t2)를 매핑하면 다음과 같다.
이런 식으로 transition 이름이 일치하는 transition pair를 모두 매핑하면 다음과 같은 형태가 된다.
이와 같이 도출된 net을 synchronous product net이라고 한다.
Optimal Alignment 찾기
위에서 우리는 synchronous product net을 도출하는 방법에 대해 알아보았다. 이제 이를 기반으로 optimal alignment를 찾을 차례이다. 이의 원리는 간단하다. synchronous product net에서 initial marking으로부터 synchronous move를 가장 많이 지나가는 방향으로 final marking까지 도달하는 방법을 찾는 것이다. 예를 들어, 위의 예시에서 optimal alignment를 찾는다고 하자.
우리는 최대한 synchronous move(초록 화살표)를 많이 하는 것을 목표로 해야 하기 때문에, 우선 (t1', t1) transition을 실행한다. 그러면 p2', p2에 marking이 생긴다.
다음으로 synchronous move 중 (t2', t2)를 실행시킬 수 있다. 그 결과는 다음과 같다.
다음으로 synchronous move 중 (t3', t3)를 실행시킬 수 있다. 그 결과는 다음과 같다.
다음으로 synchronous move를 실행하려고 봤더니 실행할 수 있는 것이 없다. 우리의 final marking은 [p4, p5']이기 때문에 이에 도달하기 위해 우선 log move 중 t4'(finalize)을 실행한다.
다음으로 final marking인 p4에 도달하기 위해 model move 중 t5(deliver)를 실행한다. 최종적으로 final marking에 도달했다.
우리의 alignment는 (t1', t1), (t2', t2), (t3', t3), (t4', >>), (>>, t5) 순으로 실행되었다. 이를 alignment 표로 나타내면 다음과 같다.
| log move | add items | add items | finalize | finalize | >> |
| model move | add items | add items | finalize | >> | deliver |
이것이 우리의 optimal alignment가 되고, alignment cost는 2가 된다. 이런 과정을 통해서 optimal alignment를 구할 수 있다!
alignment based conformance checking이 무엇인지에 대해 알아보고, 모든 이벤트 로그에 대해서 fitness 값을 어떻게 구할 수 있는지에 대해 알아본 포스팅에 이어 이번 포스팅에서는 optimal alignment를 어떻게 구하는지에 대해 알아보았다.
이번 포스팅에서 한 가지 의문이 들 수 있다. synchronous product net을 구한 후 optimal alignment를 찾는, 페트리 넷에서 토큰을 하나하나 synchronous move를 찾으며 이동시키는 과정이 약간은 휴리스틱 하게 느껴질 수 있다는 점이다. 이를 해결하기 위해 shortest path를 찾는 algorithm(A* algorithm 등)을 synchronous product net에 적용시켜 optimal alignment를 찾는 것도 가능하다. 이는 다음 포스팅에서 다루도록 하겠다. 영원히 끝나지 않는 시리즈물 alignment.... based.... conformance.... checking...
References
1. Course: Advanced Process Mining. RWTH. Dr.ir. Sebastiaan J. van Zelst
최근댓글