시험 준비한다고 일주일 포스팅을 쉬었는데, 시험 공부 도저히 더 못하겠어서 내일 시험인데 쓰는 글 ^_^ 어차피 시험 범위니까 글 쓰는 것도 시험 공부의 일환 아닐까 ㅎㅎ (아님)
프로세스 모델의 quality를 평가하는 데에는 fitness, precision, generalization, simplicity의 4가지 척도가 있고, 그 중에서 Fitness는 Footprint matrix, alignment 등의 다양한 conformance checking 방법들에 의해 계산될 수 있다. 그렇다면 precision은 어떻게 계산할 수 있을까? 이번 포스팅에서는 프로세스 모델의 precision을 계산하는 방법에 대해 알아보겠다.
Precision이란?
Precision은 이벤트 로그에서 나타나지 않은 trace가 모델에서 나타나는 정도를 말한다. 즉, 모델이 이벤트 로그를 얼마나 잘 설명할 수 있는지를 말한다. 이벤트 로그와 전혀 관련이 없는 trace가 모델에서 많이 도출된다면 이 모델은 해당 trace에 적합하지 않은 모델일 것이다. 자세한 설명은 아래 포스팅의 precision 부분을 참고하도록 한다.
2019/07/29 - [Theory] - Process Model의 Quality 평가 (어떤 프로세스 모델이 좋은 모델일까?
Process Model의 Quality 평가 (어떤 프로세스 모델이 좋은 모델일까?)
우리는 알파 알고리즘, inductive miner, heuristic miner 등 다양한 process discovery 알고리즘들을 통해 프로세스 모델을 도출할 수 있다. 그렇다면 이 다양한 process discovery 알고리즘 중 가장 좋은 알고리..
process-mining.tistory.com
Precision의 계산법
*이벤트 로그가 모두 perfectly fitting trace라고 가정한다. 즉, 이벤트 로그는 모두 프로세스 모델에서 나타날 수 있는 behavior이다.
다음과 같은 이벤트 로그와 프로세스 모델이 있다고 하자. 이 때, 이벤트 로그는 모델에 완벽하게 fitting (fitness = 1)이라고 가정한다.
1. 페트리 넷의 Reachability Graph를 도출한다.
우선, 페트리 넷의 behavior를 파악하기 위하여 페트리 넷의 reachability graph를 도출한다. 그 결과는 다음과 같다. (이를 구하는 과정은 생략한다. reachability graph가 무엇인지 모른다면 다음 포스팅을 참고한다.)
2019/06/21 - [Theory/Process Model] - 트랜지션 시스템(Transition System)이란? Reachability Graph란?
트랜지션 시스템(Transition System)이란? Reachability Graph란?
트랜지션 시스템(Transition System)은 프로세스 모델의 한 종류로, 이름에서도 알 수 있 듯이 Transition과 함께 State를 나타내는 것을 목적으로 하는 모델이다. 이 때, state는 페트리 넷의 marking이 될 수도..
process-mining.tistory.com
2. 이벤트 로그의 automaton을 구한다.
이벤트 로그의 trace들의 behavior를 파악하기 위하여 이벤트 로그의 automaton을 구한다. 그 결과는 다음과 같다.
3. Reachability graph와 automaton을 비교하여 escaping edge를 구한다.
이제 모델의 beahvior과 이벤트 로그의 behavior를 비교할 차례이다. Precision의 정의에 따라 이벤트 로그의 automaton을 기준으로 하여 모델이 이벤트 로그에 나타나지 않는 behavior를 얼마나 허락하는지를 파악한다.
우선, automaton(이벤트 로그)의 1과 reachability graph(프로세스 모델)의 s1을 비교하면 enable하는 액티비티가 a로 일치한다. 다음으로, 2와 s2를 비교해보면 2는 b, d를 enable하지만 s2는 b, c, d를 enable한다. 즉, 모델이 c 액티비티를 하나 더 허락하는 것이다. 그러므로 우리는 일치하지 않는 c에 대해 automaton에 escaping edge를 추가해준다.
다음으로, a, b sequence가 일어난 3과 s3을 비교한다. 둘 다 c만 enable로 일치한다. 다음으로, a,b,c sequence에 해당하는 5와 s5를 비교한다. 둘 다 e만 enable로 일치한다. 다음으로, a, d sequence가 일어난 4와 s5를 비교한다. 둘 다 e만 enable로 일치한다.
4. Precision을 계산한다.
이제 precision을 계산할 차례이다. escaping edge까지 표시한 그래프에 대해서 각 state에 해당하는 이벤트 로그의 개수가 몇 개인지를 구한다.
우리의 이벤트 로그를 예로 들면, 전체 trace의 개수가 4이므로 initial state에서는 4, a가 일어났을 때에도 모두 a로 시작하므로 4, a, b는 abce만 해당하므로 2, a, d는 ade만 해당하므로 2 이런 식이다. 이들을 모두 표시한 automaton은 다음과 같다.
Precision의 계산식은 다음과 같다.
즉, 우리의 예시에서는 다음과 같은 식으로 이를 계산할 수 있다.
이번 포스팅에서는 process model의 quality를 판단하는 척도 중 하나인 precision을 계산하는 방법에 대해 알아보았다. 이 포스팅은 precision을 계산하는 방법을 좀 더 쉽게 설명하기 위하여 reachability graph와 automaton을 이용하여 눈에 보이는 방법으로 설명하였다. 다음 포스팅에서는 좀 더 정의에 입각하여 precision을 구하는 방법에 대해 다루어 보겠다.
References
1. Course: Advanced Process Mining. RWTH. Dr.ir. Sebastiaan J. van Zelst
최근댓글