C-net (Causal net)이란?

C-net(Causal net)이란, 액티비티 사이의 causal dependency를 표현한 그래프이다. C-net은 BPMN, EPCs, YAWL 등의 다양한 mainstream language에 아주 잘 맞게 이벤트 로그를 표현할 수 있고, 대부분의 프로세스 모델이 표현할 수 있는 XOR, AND 뿐만 아니라 OR까지 표현할 수 있으면서도 silent 액티비티나 중복 액티비티가 필요없는 강력한 프로세스 모델이다. 이번 포스팅에서는 C-net을 어떻게 만들고, 이 C-net을 어떻게 해석하는지에 대해 알아보겠다.

C-net의 구성 요소

C-net은 기본적으로 액티비티, arc, binding으로 구성되어 있다.

액티비티

액티비티는 우리가 알고 있는 이벤트 로그에 있는 액티비티 그 자체이다. 따로 설명할 것이 없다. C-net에서 액티비티는 위 그림과 같이 네모의 형태로 나타난다.

Arc

Arc는 액티비티들을 연결하는 화살표로, dependency relation을 의미한다. 즉, dependency graph에서 연결된 화살표들과 의미가 같다.

Binding

Binding이 C-net의 핵심이라고 할 수 있다. 각 액티비티들은 input binding(join)과 output binding(split)을 각각 가진다. Binding의 종류는 총 6가지가 있다. 예시를 들어 설명하도록 하겠다.

XOR split

위 그림처럼 원이 선으로 서로 연결되지 않고 따로따로 있는 binding을 XOR split라고 한다. 이는 원 중에서 하나를 선택해서(XOR) 다음 액티비티가 일어난다는 뜻이다. 위 그림의 예시에서는, <a,b>, <a,c> 가 일어날 수 있는 것이다.

AND split

위 그림처럼 원이 선으로 서로 연결되어 있는 binding을 AND split라고 한다. 이는 연결된 원의 액티비티를 모두 (AND) 다음 액티비티로 일어나게 한다는 뜻이다. 위 그림의 예시에서는, <a,b,c> 혹은 <a,c,b>가 일어날 수 있는 것이다.

OR split

위 그림처럼 여러 XOR, AND binding들이 섞여 있는 것을 OR split라고 한다. 이는 이름에서 예상할 수 있듯이, binding 중 하나를 선택하여 일어나는 것을 의미한다. 위 그림의 예시에서는, <a,b,c>, <a,c,b> 혹은 <a,d>가 일어날 수 있다.

join binding도 split binding과 같이 AND, XOR, OR join을 가지고 있고, 이는 split의 경우와 똑같은 의미를 가지기 때문에 설명을 생략하도록 하겠다.

C-net 만드는 법

예시 이벤트 로그와 함께 C-net을 만드는 방법을 알아보도록 하겠다.

1. Dependency Graph를 만든다.

위에서도 말했듯이 c-net은 dependency relation을 표시하는 프로세스 모델이기 때문에 dependency graph를 기본으로 한다. Dependency Graph를 만드는 방법을 모른다면 아래 포스팅을 참고하자.

2019/07/25 - [Theory/Process Model] - Dependency Graph란?

Dependency Graph란?

Dependency Graph란, 말 그대로 activity 사이의 dependency를 표현한 그래프이다. Dependency Graph는 또 다른 프로세스 모델인 C-net이나 process discovery의 한 방법인 heuristic mining의 기본이 되는 프로세..

process-mining.tistory.com

우리의 예시 이벤트 로그로 dependency graph를 만들면 아래와 같이 된다. (dependency graph를 만드는 과정은 생략한다.)

2. Binding 찾기 (split, join)

Binding을 찾는 방법에는 Optimization과 Heuristics의 두 가지 방법이 있다.

Optimization은 가능한 모든 binding에 대해서 어떤 목표 함수 (goal function)의 값을 계산하여 어떤 조합의 binding이 goal function의 값을 최대화/최소화 시키는지를 보고 binding을 선택하는 방법을 의미한다. 이는 실제 이벤트 로그를 각 binding 조합의 c-net에 replay함으로써 이루어진다. Heuristics에 비해 복잡하고 비용이 많이 들지만, 원하는 방향으로 c-net을 정확하게 얻을 수 있다는 장점을 가진다.

Heuristics는 각 액티비티들의 before와 after 액티비티를 보고, 이들의 빈도를 셈으로써 어떤 binding을 택해야하는지를 선택하는 방법을 의미한다. 설명으로는 와닿지 않을 것이기 때문에 예시를 통해 살펴보자.

우선, 우리는 time window를 정해야 한다. time window란, before와 after 액티비티를 어느 범위까지 볼 것인지를 의미한다. 예를 들어, time window가 1이면 바로 직전과 바로 직후의 액티비티만을 고려하고, time window가 2라면 전전 액티비티와 후후 액티비티까지 고려할 것이다. 우리는 여기서 time window를 2로 정하도록 하겠다. 또한 frequency에 대한 threshold가 필요하다. 이는 5로 하도록 하겠다.

맨 처음으로 a 액티비티를 보자. a 액티비티는 dependency graph 상에서 input은 없고 b, c, d, e로 가는 output만 존재하기 때문에 output binding을 정하면 된다. 즉, after 액티비티만 살펴보면 된다. 각 이벤트 로그에 대해서 a 뒤에 오는 액티비티들 (time window = 2)의 조합을 보면 다음과 같다.