저번 포스팅에서 우리는 Elementary Transition system에 대해서 state based region theory를 적용하여 프로세스 모델을 도출하는 방법에 대해 알아보았다.
2019/08/18 - [Theory/Process Model] - Elementary Transition System이란?
Elementary Transition System이란?
전 State based region theory 포스팅에서 우리는 transition system이 Elemenatry Transition System이라는 가정을 했다. 2019/07/30 - [Theory/Process Discovery] - State Based Region Theory란? State Based..
process-mining.tistory.com
하지만 대부분의 실제 Transition System은 elementary하지 않거나 elementary인지 판별하기가 쉽지 않다. 그래서 이번 포스팅에서는 Non-elementary transition system에 대해서 state based region theory를 적용하는 방법인 트랜지션 시스템의 처리와 label splitting에 대해 알아보겠다.
* 이 포스팅의 이해를 위해서는 다음 포스팅의 이해가 필요하다.
2019/07/30 - [Theory/Process Discovery] - State Based Region Theory란?
State Based Region Theory란?
이 포스팅을 미루고 미뤘던 이유는 지금 연구실에서 내가 하고 있는 것이기 때문이다. 집에서까지 이 친구를 마주치고 싶지 않았다. 워라밸 소중해 우리는 이벤트 로그를 transition system으로 바꿀 수 있다. 이..
process-mining.tistory.com
트랜지션 시스템 처리
첫 번째 방법은 트랜지션 시스템을 Elementary Transition System의 형태로 처리해주는 것이다. 이에는 세 가지 방법이 있다.
self-loop 제거
첫 번째는 단순히 트랜지션 시스템의 self-loop를 제거하는 것이다. 하지만 이 방법은 이벤트 로그에 대한 fitness를 낮춘다는 단점이 있다는 것에 유의해야 한다.
Improve diamond structure
두 번째는 improve diamond structure이다. 이는 특히 set으로 state를 표현한 트랜지션 시스템에 대해 유용하다. 이는 이벤트 로그의 trace에는 표현되지 않았지만 한 state에서 다른 state로 가는 하나의 액티비티를 추가하는 것이 가능하다면 이 트랜지션을 추가하는 것이다. 예를 들어, 아래 예시에서 {A,C}와 {A,C,E} 사이에 원래 이벤트 로그에서는 E라는 액티비티를 통해 이 두 state 사이 이동이 불가능했지만, 이 트랜지션을 추가함으로써 이를 가능하게 하는 것이다.
Merge similar states
세 번째는 비슷한 state들을 merge하는 것이다. 이에는 input이 같은 state를 merge하는 것, output이 같은 state를 merge하는 것 등 다양한 방법이 있을 수 있다.
Label Splitting
두 번째 방법은 Label splitting이다. 이는 forward closure property를 만족하지 못하는 트랜지션 시스템에 대해 적용시킬 수 있는 방법이다. 예시와 함께 label splitting 알고리즘에 대해 알아보겠다.
1. 트랜지션 시스템의 minimal region을 모두 구한다.
트랜지션 시스템에 대해 minimal region을 모두 구한다. 이 포스팅에서는 그 과정은 생략하겠다.
2. 각 액티비티에 대해 pre-region, pre-region의 intersection, GER(Generalizaed Excitation Region)을 구한다.
여기서 pre-region은 해당 액티비티를 exit으로 가지는 minimal region을, pre-region의 intersection은 pre-region이 두 개 이상일 때 그 region들의 교집합에 해당하는 state를, GER은 해당 액티비티를 enable하는 state를 말한다. 이를 우리의 트랜지션 시스템에 대해 구해보면 다음과 같다. (이들에 대한 자세한 설명은 elementary transition system 포스팅을 참고한다.)
3. Intersection과 GER이 일치하지 않는 액티비티에 대해서 label splitting을 진행한다.
Intersection과 GER이 일치하지 않는 것에 대해서 label splitting을 진행한다. 우리의 예시에서는 이벤트 c에 대해서 GER이 {s0,s1,s3}이고 intersection이 {i,s0,s1,s3}이므로 이들이 일치하지 않았다. 이 GER을 region으로 만들기 위해서 우리의 트랜지션 시스템을 다시 본다.
이를 보면, GER인 {s0,s1,s3}에서 a,b가 no cross와 enter를 둘 다 하기 때문에 region이 되지 못함을 알 수 있다. 그러므로 a와 b를 각각 a1과 a, b1과 b로 splitting 해준다.
4. splitting한 트랜지션 시스템에 대해 다시 label splitting 알고리즘을 진행한다.
split한 트랜지션 시스템에 대해 다시 label splitting 알고리즘을 진행하기 위해 minimal region, 각 액티비티에 대한 pre-region, intersection, GER을 찾는다.
새로운 트랜지션 시스템에 대해서는 intersection과 GER이 모두 일치하기 때문에 (forward closure property 만족) label splitting이 끝난 것을 알 수 있다.
5. 페트리 넷을 만든다.
label splitting이 끝난 트랜지션 시스템에 대해 state based region theory를 바탕으로 페트리 넷을 도출한다.
이번 포스팅에서는 non-elementary transition system에 대해 다양한 후처리나 label splitting을 이용하여 state based region theory를 통해 페트리 넷을 도출하는 방법에 대해 알아보았다.
References
1. Course: Advanced Process Mining. RWTH. Dr. Sebastiaan J. van Zelst
2. Wil van der Aalst, V.Rubin, B.F. van Dongen, E. Kindler, C.W. Gunther, Process Mining: A Two-Step Approach using Transition Systems and Regions
최근댓글