이번 포스팅에서는 process discovery 알고리즘 중 하나인 language based region theory에 대해 알아보겠다.
Motivation
예를 들어, 다음과 같은 페트리 넷이 있다고 하자.
이 페트리 넷이 만들 수 있는 trace에는 무엇이 있을까? b, c, d 액티비티가 마음대로 실행될 수 있기 때문에(input place가 없음) <a>, <a,b>, <b>, <b,c,d> 등 수많은 trace를 만들 수 있을 것이다. 그렇다면 다음 페트리 넷을 보자.
이 페트리 넷이 만들 수 있는 trace에는 무엇이 있을까? <a,b,c,d>, <a,c,b,d>, ... 위 페트리 넷보다 만들 수 있는 trace의 개수가 확 줄어든 것을 알 수 있다. 이와 같이 페트리 넷에 place를 추가하는 것은 페트리 넷의 움직임(behavior)를 제한하는 역할을 한다.
이렇게 모든 이벤트 로그의 behavior를 허용하는 place를 정해나가면서 맞는 프로세스 모델을 찾아나가는 과정이 language based region theroy의 기본적인 아이디어이다.
Language Based Region Theory
Language Based Region Theory에서는 region을 다음과 같이 정의한다.
위 부등식에서 왼쪽 부분은 어떤 place 내의 토큰의 개수를 말한다. 즉, 위 부등식의 뜻은 모든 place에 대해서 token의 개수는 0 이상이어야한다는 의미이다.
c는 place 내 토큰의 개수, w'(t)는 현재 이벤트 전까지 t가 일어난 횟수, x(t)는 해당 트랜지션 t로부터 place로의 input arc의 개수, w(t)는 현재 이벤트를 포함하여 t가 일어난 횟수, y(t)는 해당 place로부터 트랜지션 t로의 output arc의 개수를 말한다. 즉, 이렇게 만들어진 place에 의해 현재 이벤트가 disable되지 않아야 한다는 것을 표현한 식이다.
예시를 통해 Language based region theory의 과정을 하나하나 살펴보겠다. 다음과 같은 이벤트 로그가 있다고 하자.
1. prefix-closed language를 구한다.
우선, 이벤트 로그에 대해 prefix-closed language를 구한다. prefix-closed language란, 각 trace에 대한 모든 prefix의 집합을 말한다. 즉, <a,b>에 대해서는 공집합, <a>, <a,b>가 이에 해당된다. 우리의 예시에 대해 이를 구해보면 다음과 같다.
2. region의 정의에 따라 부등식을 구한다.
1에서 구한 prefix-closed language를 바탕으로 region의 정의에 따른 부등식을 구한다. 위에서 말한 region의 정의를 prefix-closed language에 대해 다시 정의하면 다음과 같이 정의할 수 있다.
즉, A'는 prefix-closed language에서 마지막 액티비티를 제외한 trace의 행렬이고 A는 모든 trace의 행렬이다. 말로 설명하는 것보다 예시를 통한 것이 이해가 더 쉬울 것 같다.
각 행렬의 행은 모든 prefix-closed closure을, 열은 모든 액티비티를 나타낸다. 그리고 행렬의 각 성분은 prefix-closed closure에 포함된 액티비티의 개수를 표시한다. 예를 들어, <a,b>의 마지막 액티비티는 b이기 때문에 A 행렬의 a, b는 모두 1, A' 행렬의 a는 1, b는 0(마지막 액티비티 제외)으로 표시된다. 이 행렬에 따라 부등식을 만들면 다음과 같다.
이 부등식들을 모두 만족하는 x, y, c 값이 place가 된다. 이 때, x와 y는 0 또는 1의 값만을 가진다. 우리의 예시에서 나타날 수 있는 place의 예시는 다음과 같다.
그런데 이 때, 위 그림과 같이 식을 만족하는 place의 개수가 한 개 이상일 수 있다. 그렇다면 어떤 place를 선택해야 할까?
3. Target function에 따라 가장 적절한 place를 선택한다.
프로세스 모델은 다양한 목적을 가질 수 있다. 가장 arc의 개수가 적은 프로세스 모델을 원할 수도 있고, 가장 place의 개수가 적은 모델을 원할 수도 있다. 이러한 다양한 목적에 따라 target function을 정하여 이에 부합하는 region들만을 선택한다.
가장 기본적인 Language based Region Theroy는 다음과 같은 target function을 minimize하는 것을 목표로 한다.
즉, 토큰의 개수를 최소화하고 input 트랜지션을 최소화함과 동시에 output 트랜지션을 최대화하는 것이다. 달리 말하면, 가장 적은 behavior를 허용하는 place를 찾는 것을 목표로 하는 것이다.
우리의 예시에서 2에서 찾을 수 있는 모든 region들에 대해서 target function 값을 찾으면 다음과 같다.
그러므로 우리는 goal function의 최솟값인 2를 가지는 위에 있는 두 개의 region을 place로 정하는 것이다.
위에서 설명한 내용들을 하나의 식으로 정리하면 다음과 같다.
이번 포스팅에서는 language based region theory에 대해 알아보았다. 이번 포스팅을 마지막으로 alpha algorithm, heuristic mining, inductive mining, state based region theory, language based region theory 등 가장 기본이 되는 process discovery 알고리즘들은 다 다루었다. 큰 과제를 끝낸 느낌 ㅎㅎ
References
1. Course: Advanced Process Mining. RWTH. Dr. Sebastiaan J. van Zelst
2. Section 7.4.3. of Wil van der Aalst. Process Mining: Data Science in Action (Second Edition) : Springer, 2016.
최근댓글