저번 포스팅에서 우리는 Activity based decomposition을 페트리 넷에 대해서 어떻게 적용시키고, 이를 이용해 conformance checking을 하는 방법에 대해 간단히 알아보았다. 이번 포스팅에서는 이에 좀 더 심화하여 이를 활용하여 alignment based conformance checking을 하는 방법에 대해 알아보겠다.
* 이번 포스팅의 이해를 위해서는 다음 포스팅에 대한 이해가 필요하다.
Activity Based Decomposition을 이용한 Conformance Checking (빅 데이터와 Conformance Checking)
만약 우리가 Conformance Checking을 원하는 프로세스 모델이 액티비티 100000개로 구성된 복잡한 프로세스 모델이라면 우리는 정해진 시간과 메모리 내에 Conformance Checking을 할 수 있을까? 아마 높은 확률로..
process-mining.tistory.com
Alignment의 계산 과정
우선, 다음과 같은 예시 페트리 넷과 trace가 있다고 하자.
1. 페트리 넷의 maximal valid decomposition을 구한다.
가장 먼저 페트리 넷의 maximal valid decomposition을 구한다. (이 과정은 이번 포스팅에서는 생략한다.)
2. trace를 subnet에 해당하는 액티비티에 따라 나눠준다.
각 subnet에 포함된 액티비티 셋에 따라 해당하는 trace를 나누어 준다.
예를 들어, 첫 번째 subnet(SN1)에는 a 액티비티만 포함되므로 <a>, 두 번째 subnet(SN2)에는 a, b, d, e 액티비티가 포함되므로 <a,b,d,e,d>, 세 번째 subnet(SN3)에는 a,c,e 액티비티가 포함되므로 <a,e,c>, 네 번째 subnet(SN4)에는 c,d 액티비티가 포함되므로 <d,c,d>, SN5에는 d,e,f,g,h 액티비티가 포함되므로 <d,e,d,g,f,h>, SN6에는 f,g,h 액티비티가 포함되므로 <g,f,h>로 trace가 나누어진다.
3. 각 subnet에 대해 나눈 각 trace들의 optimal alignment를 구한다.
이제 나눈 trace들을 각각의 subnet에 대해 optimal alignment를 구해준다. Optimal alignment가 무엇인지 모른다면 다음 포스팅을 참고한다. (이 과정은 이번 포스팅에서 생략한다.)
Alignment based conformance checking이란? (Alignment를 이용한 적합도 검증) - 기본편
Conformane Checking (적합도 검증)이란, 프로세스 모델이 실제 이벤트 로그에 얼마나 잘 부합하는지, 즉 프로세스 모델이 실제 데이터와 비교해봤을 때 얼마나 잘 맞는지를 검증하는 것을 말한다. 이번 포스팅에..
process-mining.tistory.com
우리의 예시에 대해 이를 구하면 다음과 같다.
이제 이 일치하지 않는 부분들에 대한 cost를 모두 더하면 끝이 날까? 여기에서 우리의 cost를 구하면 4가 된다. 이 이벤트 로그를 그대로 전체 페트리 넷에 적용시키면 optimal alignment의 cost가 몇일까?
2가 된다. cost에서 꽤 큰 차이가 남을 확인할 수 있다. 이는 하나의 액티비티가 여러 subnet에 출연했기 때문에 발생하는 문제이다. 이에 대한 보정을 해 주어야 한다.
4. 각 액티비티가 subnet들에 출연한 횟수를 조사한다.
모든 액티비티에 대해 각 subnet들에 몇 번씩 나타났는지를 모두 조사한다. 우리의 예시에서의 각 액티비티의 빈도는 다음과 같다.
5. subnet의 alignment cost를 해당하는 액티비티의 빈도로 나누고 이를 합한다.
각 alignment들이 해당하는 액티비티의 빈도로 cost를 나누고, 이들을 모두 합해서 최종 alignment cost를 구한다. 우리의 예시에서는 c가 2번, h가 2번 있었으므로 이들을 각각 해당하는 빈도인 2와 2로 나누어 더하면 최종 cost는 2가 된다. 원래의 페트리 넷에 대한 alignment cost와 일치함을 확인할 수 있다. (일치하지 않는 경우도 있다.)
이번 포스팅에서는 activity based decomposition을 이용하여 conformance chcecking, 그 중에서도 alignment based conformance checking을 하는 방법에 대해 알아보았다. Alignment based conformance checking은 최근 가장 핫한 conformance checking 방식이지만 그 연산의 복잡도가 높고 연산 시간이 오래 걸린다는 단점을 가지고 있는데, 이러한 decomposition을 통해서 빅 데이터에 대해서도 alignment based conformance checking의 성능을 끌어올릴 수 있을 것이다.
References
1. Course: Advanced Process Mining. RWTH. Dr. Sebastiaan J. van Zelst
최근댓글