이것 때문에 연구할 때 많이 헤맸다. 고통스러웠던 기억. + 논문만 읽고 쓰는 첫 번째 포스팅. 왕부담 흑흑 그래서 글 쓰기를 시작하는 데에 오래 걸렸다. 이번 포스팅에서는 state based region theory를 적용할 때 minimal region을 찾는 방법 중 하나에 대해 알아보겠다. State Based Region Theory가 무엇인지 모른다면 다음 포스팅을 참고한다.
2019/07/30 - [Process Mining - Theory/Process Discovery] - State Based Region Theory란?
State Based Region Theory란?
이 포스팅을 미루고 미뤘던 이유는 지금 연구실에서 내가 하고 있는 것이기 때문이다. 집에서까지 이 친구를 마주치고 싶지 않았다. 워라밸 소중해 우리는 이벤트 로그를 transition system으로 바꿀 수 있다. 이..
process-mining.tistory.com
바로 minimal region을 구하는 알고리즘에 대해 설명하겠다.
1. 각 이벤트에 대해 ER(e)를 구한다.
ER이란, Excitation Region의 준말로, 해당 트랜지션이 enable된 모든 state들의 집합을 말한다. 해당 transtion을 enable한다는 말은 해당 transition을 exit한다는 말이고, 달리 말하면 region에는 이 ER이 모두 포함되어야 하는 것이다. 이 알고리즘은 이 아이디어에서 출발한다.
다음과 같은 예시 transition system이 있다고 하자.
이 트랜지션 시스템에서 ER(a)는 무엇일까? a를 enable하는 state가 s1밖에 없기 때문에 {s1}이 된다. 그렇다면 ER(c)는 무엇일까? s2와 s6이 c를 enable하기 때문에 {s2,s6}이 된다. 이와 같이 각 액티비티에 대해 ER(e)를 구하면 다음과 같다.
| ER(a) | {s1} |
| ER(b) | {s1} |
| ER(c) | {s2,s6} |
| ER(d) | {s3,s5} |
| ER(e) | {s4} |
| ER(f) | {s7} |
2. 각 ER(e)에 대해 이들이 region인지 아닌지를 조사하고, 아니라면 region의 특성을 violate하는 액티비티를 구한다.
이제 각 ER(e)를 구했으면 이들이 region인지 아닌지를 조사하고, 만약 region이 아니라면 region이 되지 못하도록 방해하는 액티비티를 구한다. 우선, 우리의 예시에서 ER(a)를 보자. {s1}은 region인가? a, b가 exit, e, f가 enter, c, d가 no cross이기 때문에 region이다. 그렇다면 ER(c)를 보자. 이것은 region인가? exit에 c, enter에 a, d, no cross에 b, e, f, d가 있다. d가 enter와 no cross에 모두 있으므로 region이 아니고, 이를 violate하는 액티비티는 d이다. 이를 각 ER에 대해 모두 구하면 다음과 같다.
| activity | ER | is_region | violate |
| ER(a) | {s1} | O | - |
| ER(b) | {s1} | O | - |
| ER(c) | {s2,s6} | X | d(enter, out) |
| ER(d) | {s3,s5} | X | c(enter, out) |
| ER(e) | {s4} | X | d(enter, out) |
| ER(f) | {s7} | X | c(enter, out) |
3. 각 violation에 대해 violation의 4가지 종류 중 어디에 속하는지를 파악한다.
violation에는 다음과 같이 4 종류가 있다.
각각 1은 in과 enter 혹은 in과 exit, 2는 enter과 exit, 3은 enter과 out, 4는 exit과 out을 말한다. (in과 out은 둘 다 no cross이므로 violation이 아니다.) 각 violation이 어디에 속하는지를 파악한다. 우리의 예시는 모두 enter, out이기 때문에 3에 속한다.
4. 각 violation의 종류에 따라 다음 알고리즘에 따라 ER을 region으로 만든다.
각 조건들에 대해 설명하자면 다음과 같다. 1의 violation인 경우에 해당 violation한 액티비티의 시작 state와 끝 state를 ER에 포함시켜 새로운 region을 만든다. 2도 1과 같이 해당 violation한 액티비티의 시작 state와 끝 state를 ER에 포함시켜 새로운 region을 만든다. 3은 해당 violation한 액티비티의 끝 state가 ER에 포함되어 있을 경우 시작 state를 포함시킨 새로운 region과 해당 액티비티의 시작 state가 ER에 포함되어 있지 않은 경우 끝 state를 포함시킨 새로운 region을 각각 만든다. 4는 해당 violation한 액티비티의 시작 state가 ER에 포함되어 있을 경우 끝 state를 포함시킨 새로운 region과 해당 액티비티의 끝 state가 ER에 포함되어 있지 않은 경우 시작 state를 포함시킨 새로운 region을 각각 만든다. 글이 장황한데, 예시를 통해 알아보겠다.
우리의 예시에서 ER(c)는 d 액티비티가 enter, out으로 3번 violation에 해당된다. 그러므로 아래와 같이 두 개의 새로운 후보 region을 만들 수 있다.
이와 같이 모든 violation에 대해 후보 region들을 만든다. 그 결과는 다음과 같다.
| activity | ER | is_region | violate | 후보 region |
| ER(a) | {s1} | O | - | - |
| ER(b) | {s1} | O | - | - |
| ER(c) | {s2,s6} | X | d(enter, out) | {s2,s5,s6}, {s2,s4,s6} |
| ER(d) | {s3,s5} | X | c(enter, out) | {s3,s5,s7}. {s3,s5,s2} |
| ER(e) | {s4} | X | d(enter, out) | {s4, s6}, {s4, s3} |
| ER(f) | {s7} | X | c(enter, out) | {s7, s3}, {s7, s6} |
5. 새로운 후보 region들에 대해 2, 3, 4 과정을 다시 진행한다.
새로운 후보 region들에 대해서 이들이 region인지를 파악하고 region이 아니라면 violation이 무엇인지를 파악하고 이들로부터 새로운 후보 region을 만드는 것을 모든 후보 region들이 region일 때까지 반복한다.
우리의 예시에서, {s2, s5, s6}, {s2,s4,s6}, {s3,s5,s7}. {s3,s5,s2}은 모두 region이다. 하지만 {s4, s6}, {s4, s3}, {s7, s3}, {s7, s6}은 region이 아니다. 이들에 대해서 다시 2, 3, 4 과정을 반복한다. (글이 너무 길어지는 것 같아 이 과정은 생략한다.)
6. 모든 후보 region이 region이라면 알고리즘을 종료하고, 만들어진 region들이 minimal region들이다.
이 알고리즘에 따라 예시 transition system의 minimal pre-region을 모두 구하면 다음과 같다.
이들을 이용해 state based region theory에 따라 페트리 넷(minimal saturated net)을 만들면 다음과 같다.
이번 포스팅에서는 미루고 미뤄왔던 minimal region을 구하는 방법들 중 하나의 방법에 대해 알아보았다. 이 방법을 이용해서 state based region theory를 통해 페트리 넷을 도출하는 것이 가능하다.
References
1. J. Cortadella, M. Kishinevsky, L. Lavagno and A. Yakovlev, "Deriving Petri nets from finite transition systems," in IEEE Transactions on Computers, vol. 47, no. 8, pp. 859-882, Aug. 1998.
최근댓글