Transition system의 종류 (Transition system의 abstraction)

 트랜지션 시스템(Transition System)은 프로세스 모델의 한 종류로, state에서 state로 넘어가는 트랜지션을 나타내는 것을 목적으로 하는 모델이다. 트랜지션 시스템에 대해 자세히 알아보려면 다음 포스팅을 참고한다.

2019/06/21 - [Theory/Process Model] - 트랜지션 시스템(Transition System)이란? Reachability Graph란?

트랜지션 시스템(Transition System)이란? Reachability Graph란?

 저번 포스팅에서도 언급했지만, 이 트랜지션 시스템의 state는 사용자가 정의하는대로 marking이 될 수도 있고, enabled된 트랜지션의 개수가 될 수도 있다. 이번 포스팅에서는 이 다양한 state의 종류들에 따른 다양한 트랜지션 시스템의 종류에 대해 알아보겠다.

 Past, Future, Past & Future

 우선, state의 종류를 나누는 기준에는 Past, Future, 그리고 Past & Future이 있다. 다음과 같은 trace가 있고, 현재의 state가 화살표와 같다고 하자.

예시 trace

Past

 Past는 과거까지 일어난 시퀀스를 기준으로 현재의 state를 표시하는 것이다. Past를 기준으로 현재의 state를 표시하면 <a,b,c,d,c,d,c,d,e>가 될 것이다.

Past를 기준으로 표시한 state

Future

 Future은 미래에 일어날 시퀀스를 기준으로 현재의 state를 표시하는 것이다. Future를 기준으로 현재의 state를 표시하면 <f,a,g,h,h,h,i>가 될 것이다.

Future을 기준으로 표시한 state

Past & Future

 Past & Future은 과거와 미래의 모든 시퀀스를 기준으로 현재의 state를 표시하는 것이다. 이는 다음 그림과 같이 표시할 수 있다.

Past & Future를 기준으로 표시한 state

Abstraction

 위에서 현재, 과거, 그리고 현재와 과거를 모두 이용하여 현재의 state를 나타내는 것에 대해 알아보았다. 하지만 만약 하나의 trace의 길이가 엄청 길거나 복잡한 구조라면 위 방식만으로 transition system을 만들었을 때 아주 복잡한 모델이 될 것이다. 이를 해결하기 위해 다양한 abstraction을 적용한다. 

 

Sequence abstraction

 Sequence abstraction이란, 위에서 설명한 것처럼 시퀀스 전체로 state를 표현하는 것이다. 즉, 액티비티들의 순서와 빈도가 모두 고려되어서 state가 정해진다. 위 설명처럼 past를 기준으로 sequence abstraction을 하여 만든 transition system을 prefix automaton이라고 부른다.

 

Set abstraction

 Set abstraction이란, 시퀀스 중에서 순서와 빈도를 고려하지 않고, 어떤 액티비티가 등장했는지만을 이용하여 state를 표현하는 것이다. 

예시 trace

우리의 예시 trace를 past 기준으로 set abstraction 한다고 하자. 그러면 우리는 <a,b,c,d,c,d,c,d,e> 시퀀스를 {a,b,c,d,e}로 표현할 수 있을 것이다.

set abstraction based on past

 

Multiset Abstraction

 Multiset Abstraction이란, 시퀀스 중에서 순서는 고려하지 않되 빈도는 고려하여 state를 표현하는 것을 말한다. 우리의 예시 trace를 past 기준으로 multiset abstraction한다고 하자. 그러면 우리는 <a,b,c,d,c,d,c,d,e> 시퀀스를 [a, b, c^3, d^3, e]로 표현할 수 있을 것이다. 

multiset abstraction based on past

Limited Horizon

 이외에도 과거와 현재의 모든 시퀀스를 고려하는 것이 아니라, 일정 길이만큼의 시퀀스만을 고려하여 state를 만드는 것도 가능하다. 예를 들어, 과거의 4개의 event만을 이용하여 set abstraction으로 state를 정한다고 하자. 현재 state의 과거의 4개의 event는 <d,c,d,e>이고, 이를 set abstraction하면 {c,d,e}의 state로 표현될 것이다. 

set abstraction based on last 4 events

정리

 새로운 예시와 함께 transition system의 다양한 종류들에 대해 정리해보도록 하겠다. 다음과 같은 이벤트 로그가 있다고 하자.

예시 이벤트 로그 L

 위 이벤트 로그에 대해서 abstraction 없이 past를 기준으로 transition system (Prefix automaton)을 만든다면 어떤 형태가 될까? 다음 그림과 같은 형태가 될 것이다. 

prefix automaton

 그렇다면 past with multiset abstraction으로 transition system을 만들면 어떤 형태가 될까? 위에서 본 prefix automaton과는 형태가 분명하게 달라질 것이다. 왜냐하면, <a,c,b,d> state와 <a,b,c,d> state가 [a,b,c,d]로 같은 state로취급되는 등의 변화가 있을 것이기 때문이다. 이는 다음 그림과 같은 형태가 될 것이다.

past with multiset abstraction

 

 이번 포스팅에서는 실제 이벤트 로그에 대해서 다양한 방법으로 state를 정의하고, 이를 abstraction을 통해서 간단히 만듦으로써 트랜지션 시스템을 도출하는 방법에 대해 알아보았다. 자신의 데이터셋에 적절한 abstraction을 적용하고, 이를 이용하여 적절한 트랜지션 시스템을 도출한다면 데이터의 behavior를 한 눈에 파악하는 데에 큰 도움이 될 것이다.

 

References

1. Course: Business Process Intelligence. RWTH. Wil van der Aalst.