포항집에서 쓰는 첫 글.
프로세스 모델의 quality를 평가하는 데에는 fitness, precision, generalization, simplicity의 4가지 척도가 있고, 그 중에서 simplicity는 모델이 얼마나 복잡한지 혹은 모델이 얼마나 간단한지를 측정하는 요소이다. 이번 포스팅에서는 이러한 프로세스 모델의 simplicity(complexity)를 계산하는 다양한 방법 중, Cardoso Metric에 대해 알아보겠다.
Cardoso Metric이란?
Cardoso Metric은 프로세스 모델의 split에 주목한다. Split은 해당 노드에서 다음 flow로 넘어갈 수 있는 토큰의 수를 결정한다. Split을 좀 더 직관적으로 이해하고 싶다면, 다음 C-net 포스팅을 참고하도록 한다.
Split의 종류에는 XOR, OR, AND가 있다. XOR split은 연결된 out flow 중 하나에 토큰을 보내고, AND split은 연결된 out flow 모두에 토큰을 보내고, OR split은 연결된 out flow 중 아무 부분집합으로 토큰을 보낸다. 그러므로 OR split, XOR split, AND split 순으로 다음 flow의 경우의 수가 줄어든다는 것을 알 수 있다. Cardoso Metric은 이러한 점에 착안하여 OR split의 복잡도가 가장 높고, AND split의 복잡도가 가장 낮다고 생각하여 복잡도를 계산한다. 그 정의는 다음과 같다.
즉, XOR split의 복잡도는 out flow의 개수, OR split의 복잡도는 2의 out flow 개수제곱 - 1, AND split의 복잡도는 1으로 계산하는 것이다. 그리고 이들을 모두 더하여 하나의 프로세스 모델의 복잡도를 계산한다.
Extended Cardoso Metric
하지만 위에서 보인 Cardoso Metric에는 단점이 하나 있다. XOR, OR, AND split을 표현할 수 없는 프로세스 모델에 대해서는 복잡도를 계산할 수 없다는 점이다. 프로세스 마이닝에서 가장 흔하게 사용하는 프로세스 모델인 페트리 넷(Petri net)은 place와 transition으로 구성되어 있다. 그렇다면 Cardoso Metric을 페트리 넷에 적용시키려면 어떻게 해야 할까?
Cardoso Metric은 결국, 페트리 넷의 관점에서 봤을 때 하나의 place에서 얼마나 많은 선택지(경우의 수)가 존재하는지를 표현한 것이다. 그러므로 우리는, 페트리 넷에서의 Cardoso Metric을 다음과 같이 정의할 수 있다.
즉, 각 place들에서 out flow로 연결되어 있는 transition의 output place의 경우의 수를 페트리 넷의 Cardoso Metric으로 계산하는 것이다. 이해를 돕기 위해 예시와 함께 설명하겠다. 다음과 같은 페트리 넷이 있다고 하자.
우리는 위 페트리 넷에 대해서 각 place들의 ECFC 값을 계산하여 이를 합해야 한다. p_i의 ECFC 값은 out flow로 연결된 transition t1, t2, t3의 output place의 경우의 수가 {p1}, {p2}, {p3} 이기 때문에 3이 된다. p1, p2, p3의 ECFC 값은 out flow로 연결된 transition이 존재하지 않기 때문에 0이 된다. 그러므로 이 페트리 넷의 ECaM 값은 3이 된다.
좀 더 복잡한 예시를 하나 더 들도록 하겠다. 다음과 같은 페트리 넷이 있다고 하자.
우리는 위에서 한 것과 똑같이 각 place들의 ECFC 값을 계산하여 이를 합해야 한다. p_i의 ECFC 값은 out flow로 연결된 각 transition의 output place 개수의 합이다. t1이 {p1}, t2가 {p1, p2}, t3가 {p1, p2, p3}, t4가 {p2}, t5가 {p1, p3}, t6이 {p2, p3}, t7이 {p3}로 총 7이 된다. 이러한 방식으로 모든 페트리 넷의 Cardoso Metric을 계산할 수 있다.
이번 포스팅에서는 프로세스 모델의 복잡도를 계산하는 방법 중 하나인 Cardoso Metric에 대해 알아보았다. Cardoso Metric 이외에도 프로세스 모델의 simplicity를 계산하는 다양한 방법들이 있다. 예를 들어, PM4Py로 simplicity 계산하는 법은 이 포스팅에서 다룬 Cardoso Metric과 전혀 다른 방법을 사용한다. 또한 이외에도 Cyclomatic Metric 등의 또다른 계산 방법도 있다. 이러한 다양한 계산 방법에 대해서는 다음 포스팅에서 알아보도록 하겠다.
References
1. Lassen, Kristian & Aalst, Wil. (2009). Complexity metrics for Workflow nets. Information & Software Technology. 51. 610-626. 10.1016/j.infsof.2008.08.005.
2. Cardoso, Jorge. (2005). Control-flow Complexity Measurement of Processes and Weyuker's Properties. 8. 213-218.
최근댓글