Dependency Graph란, 말 그대로 activity 사이의 dependency를 표현한 그래프이다. Dependency Graph는 또 다른 프로세스 모델인 C-net이나 process discovery의 한 방법인 heuristic mining의 기본이 되는 프로세스 모델임과 동시에 많은 프로세스 툴들에서 채택하고 있는 표현 방식이기도 하다. 이번 포스팅에서는 Dependency Graph를 어떻게 만들 수 있는지, depencency graph는 어떻게 생겼는지에 대해 알아보도록 하겠다.
Dependency란?
Dependency Graph가 무엇인지 알기 위해서 우리는 dependency가 무엇인지부터 알아야 한다. Dependency는 다음과 같은 식으로 표현된다.
여기서, 익숙한 > 기호가 보인다. 이는 directly followed relation을 나타낸다. 즉, |a>b|는 a 바로 다음에 b가 나타난 횟수(frequency)를 의미한다.
Dependency Graph 만드는 방법
다음과 같은 예시 이벤트 로그가 있다고 하자. 포스팅을 할 때마다 예시를 너무 많이 든다는 생각이 들기는 하는데, 내가 예시 없이 정의만 보고 바로 이해를 하는 똑똑이가 아니라 그렇다 하하
1. Directly follows relation 계산하기
각 액티비티들에 대해 directly follows relation의 횟수(frequency)를 계산해준다.
2. Dependency 계산하기
이제 위에서 말했던 dependency의 계산식대로 dependency를 계산해준다. 그 결과는 다음과 같다.
3. Threshold 고려하기
threshold란, 프로세스 모델을 간단하게 만들기 위한 제약조건이다. 즉, 너무 빈도가 낮은 outlier나 필요 없는 trace나 관계들을 생략하기 위해 어떤 값을 넘는 혹은 넘지 못하는 관계들은 생략하는 것이다. Dependency Graph에서는 두 개의 threshold가 존재한다.
1. directly follows relation
2. dependency
위에서 구한 두 개의 값들이 threshold로 사용된다. 예를 들어, directly follows relation에 대해 2, dependency에 대해 0.7의 threshold를 사용하면, 2를 넘지 못하는 모든 directly follows relation이 생략되고, 0.7을 넘지 못하는 모든 dependency들이 생략되는 것이다. 이 두 기준에서 살아남은 교집합만이 dependency graph에 표현된다.
우리의 예시 이벤트로그 L에 적용하여 한 예시를 들자면, b>c 관계가 directly followd relation에서는 4로 threshold를 만족하지만, dependency가 0이기 때문에 살아남지 못하고 생략되게 된다.
4. Dependency Graph 그리기
이제 위에서 구한 값들과 적용한 threshold를 이용하여 그래프를 그리면 된다. 그래프는 기본적으로 모든 액티비티를 네모 형태로, 모든 threshold를 만족하는 관계를 화살표로 표현한다. 또한 directly follows frequency와 dependency를 화살표 위에 표시해준다.
Dependency를 사용해야 하는 이유
갑작스럽지만 알파 알고리즘을 한 번 떠올려 보자. (dependency가 왜 사용되어야하는지를 위한 설명이기 때문에, 알파 알고리즘을 모른다면 생략해도 좋다.) 알파 알고리즘에서 우리는 빈도(frequency)를 고려했는가? 전혀 아니다. a>b가 100번 일어났든지 1번 일어났든지 신경쓰지 않고 오로지 액티비티 간의 relation만을 고려했다. 하지만 이렇게 빈도를 고려하지 않으면 1000번 일어난 관계와 1번 일어난 관계가 모두 똑같이 취급을 받게 된다. 그래서 dependency graph에서는 directly follows frequency를 고려한다.
그렇다면 빈도만 고려하면 되지 dependency까지 고려하는 이유는 무엇일까? 이는 concurrency를 고려하기 위해서이다. 예를 들어, <a,b,c>와 <a,c,b> 이벤트 로그가 있다고 하자. 이걸 보면 우리는, a 다음에 b, c가 AND split 으로 일어남, 즉 b, c가 병렬적으로 일어남을 예측할 수 있다. 하지만 directly follows frequency만 고려하게 된다면 b>c, c>b가 일어났기 때문에 b와 c가 병렬적으로 일어났음에도 불구하고 b>c와 c>b를 화살표로 연결하게 될 것이다. 하지만 이 경우에 dependency threshold를 고려하게 된다면, 각각의 dependency가 0이기 때문에 이들은 표시되지 않을 것이다. 이러한 경우를 위해 dependency를 고려해야 한다.
이번 포스팅에서 우리는 dependency가 무엇이고, 이를 왜 고려해야 하며 dependency graph는 어떻게 만들 수 있는지에 대해 알아보았다. 다음에는 이를 활용한 process discovery 알고리즘 중 하나인 heuristic minining과 process model인 c-net에 대해 알아보도록 하겠다.
References
1. Wil van der Aalst. Process Mining: Data Science in Action (Second Edition) : Springer, 2016.
최근댓글