Conformane Checking (적합도 검증)이란, 프로세스 모델이 실제 이벤트 로그에 얼마나 잘 부합하는지, 즉 프로세스 모델이 실제 데이터와 비교해봤을 때 얼마나 잘 맞는지를 검증하는 것을 말한다. 이번 포스팅에서는 최근 가장 널리 쓰이는 conformance checking 방식인 Alignment based Conformance Checking이 무엇인지에 대해 알아볼 것이다.
Motivation
기존의 Footprint Comparison Conformance Checking과 Token Based Relplay Conformance Checking은 명확한 단점을 가지고 있었다. 우선, Footprint Comparison Conformance Checking은 이벤트 로그의 빈도에 대한 정보를 전혀 고려하지 않는다는 치명적인 단점을 가진다. 어떤 trace가 단 한 번만 일어났다 하더라도 이를 Footprint Matrix에 반영시킴으로써 왜곡된 결과를 낳는다. 또한 Token Based Replay Conformance Checking은 silent transition이나 같은 이름을 가지고 있는 transition (duplicate transition)이 있는 경우에는 적용시키지 못한다는 단점을 가진다. 프로세스 모델에 중복된 transition이 하나만 있더라도 conformance checking을 할 수 없게 되어버리는 것이다.
이에 프로세스 모델에 대한 제약이 없으면서 이벤트 로그가 가지고 있는 특성을 현실적으로 반영시킬 수 있는 Conformance Checking 방식에 대한 필요성이 대두되었고, 이벤트 로그의 trace와 가장 가까운 움직임을 보여주는 프로세스 모델의 trace ("Closest matching path") 를 바탕으로 적합도를 검증하는 ("Closest matching path") Alignment based conformance checking이 만들어졌다.
Terminology
Alignment Based Conformance Checking에서 사용되는 용어를 간단히 알아보겠다. 우선, alignment는 다음과 같이 표시한다.
Alignment
Alignment는 sequence of move를 의미한다. 위 그림에서 윗 줄은 이벤트 로그에서 나타난 시퀀스인 log move, 아랫 줄은 프로세스 모델에서 나타난 시퀀스인 model move를 말한다.
Move in log only
Move in log only는 말 그대로 log에서는 나타났지만 model에서는 나타나지 않는 이벤트를 말한다. 우리의 그림에서는 h가 이에 해당된다.
Move in model only
Move in model only는 말 그대로 model에서는 나타났지만 log에서는 나타나지 않는 이벤트를 말한다. 우리의 그림에서는 b가 이에 해당된다.
Synchronous move
로그와 모델 둘 다에서 나타난, 즉 일치하는 이벤트를 말한다. 우리의 그림에서는 a, d, e, g가 이에 해당한다.
Optimal Alignment
다음과 같은 trace와 프로세스 모델이 있다고 하자.
우리는 위 프로세스 모델로부터 <a, b, d, e, g>, <a, c, d, e, g> 등 다양한 trace를 만들어낼 수 있을 것이다. 이렇게 모델로부터 만들어낸 trace들과 이벤트 로그로부터 얻어낸 trace를 이용하여 다양한 alignment를 만들어낼 수 있다.
이렇게 수없이 많은 alignment들 중 log move와 가장 일치율이 높은 alignment를 optimal alignment라고 한다. 이 때, 일치율을 계산하는 방법은 사용자가 정의하기 나름이지만, 보통 move in log only와 move in model only의 cost를 1, synchronous move의 cost를 0으로 하여 cost가 가장 낮은 것을 일치율이 가장 높은 alignment로 정의한다. 즉, 우리의 예시 1은 cost가 0, 2는 cost가 2, 3은 cost가 10으로 모든 alignment 중 가장 cost가 낮은 예시 1이 optimal alignment이다.
Fitness의 계산
그렇다면 이 optimal alignment를 이용하여 fitness를 어떻게 계산할까? Fitness는 다음과 같이 계산할 수 있다.
즉, 1에서 optimal alignment의 cost / cost가 최대가 되는 alignment의 cost 값을 뺀 것이 fitness가 된다. 위에서 Optimal Alignment를 구하는 방법은 배웠는데, cost가 최대가 되는 alignment는 어떻게 찾을 수 있을까? 답은 간단하다. 모델에서 만들어낼 수 있는 가장 짧은 trace를 구해서 그것이 로그의 trace와 하나도 겹치지 않도록 alignment를 만드는 것이다. 그러므로 우리는 위 계산식을 다음과 같이 바꿀 수 있다.
예를 들어, 다음과 같은 trace와 프로세스 모델이 있다고 하자.
이 trace의 optimal alignment를 구하면 다음과 같다.
그리고 log move의 길이는 7, shortest path in model의 길이는 5 (<a,c,d,e,g>)이기 때문에 fitness를 계산하면 다음과 같다.
이런 방법으로 alignment를 이용하여 fitness를 계산할 수 있다.
이번 포스팅에서는 alignment based conformance checking의 기본적인 개념에 대해 알아보았다. Alignment based conformance checking은 계산이 굉장히 오래 걸리고 메모리가 많이 필요하다는 단점을 가지지만, 이벤트 로그의 behavior와 가장 가까운 프로세스 모델의 behavior를 찾음으로써 fitness를 계산하기 때문에 기존의 conformance checking 방법들에 비해 가장 현실적이고 정확한 적합도 검증 방법이다. 다음 포스팅에서는 하나의 trace가 아닌 전체 이벤트 로그에 대해 alignment를 이용하여 fitness를 계산하는 방법과 optimal alignment를 찾는 방법에 대해 알아보겠다.
Alignment based conformance checking이란? (Alignment를 이용한 적합도 검증) - 심화편 (1)
연구실에서 야근하면서 실험 돌려놓고 소재를 찾아 나서다가 과거의 나가 미래의 나에게 던져 놓은 소재 거리를 발견했다. 저번 포스팅에서 우리는 Alignment based conformance checking이 무엇인지에 대해 알아..
process-mining.tistory.com
References
1. Course: Business Process Intelligence. RWTH. Prof. Wil van der Aalst.
최근댓글