저어어엉말 간만에 정신 차리고 논문 읽고 쓰는 글. 정신없는 학기가 끝나고 2주 만에 페이스를 찾았다. (그리고 한 달 반 뒤 다시 잃게 된다.)
Process discovery 알고리즘의 성능을 평가하려면 어떻게 해야할까? 많은 Conformance checking 방법들이 존재하지만, classification 또한 process discovery 알고리즘의 성능을 평가하는 좋은 방법이 될 수 있다. 예를 들어, 20개의 프로세스 패턴(variant) 중 10개가 의도한 패턴이고 나머지 10개가 의도하지 않은 패턴이라고 할 때, process discovery 알고리즘이 의도한 패턴 10개와 의도하지 않은 패턴 10개를 올바르게 구분할 수 있다면 이는 좋은 알고리즘이라고 할 수 있을 것이다. 이번 포스팅에서는 이렇게 process discovery와 classification을 연결할 수 있다는 아이디어에서 착안한, 그리고 특정 trace가 이벤트 로그의 language에 속하는지를 가장 정확하게 판단할 수 있는 개념인, log skeleton에 대해서 알아보겠다.
Log skeleton
Log skeleton은 이벤트 로그의 특성을 나타내는 9가지의 항목이다. 이에는 다음과 같은 종류가 있다. 쉬운 이해를 위해, 다음과 같은 이벤트 로그가 있다고 하자.
Equivalance relation
Equivalance relation은 다음과 같이 정의할 수 있다.
즉, 각 trace 내에서 같은 횟수로 일어난 액티비티 쌍을 말한다. 예를 들어, 우리의 예시 이벤트 로그에서 a4 액티비티와 a5 액티비티는 모든 trace에서 같은 횟수로 일어났기 때문에, a4와 a5는 equivalance relation이다. 이 equivalance relation을 표현하면 다음과 같다. (Equivalnace relation의 액티비티는 같은 색으로 표현되었다.)
Always-after relation
Always-after relation은 다음과 같이 정의할 수 있다.
즉, 첫 번째 액티비티가 일어나면, 두 번째 액티비티는 그 이후에 무조건 일어나는 관계를 말한다. 예를 들어, 우리의 예시 이벤트 로그에서 a2 액티비티가 일어난 이후에는 a5 액티비티가 반드시 일어나므로, a2와 a5는 always-after 관계에 있다. 이 always-after 관계를 그림으로 표현하면 다음과 같다.
Always-before relation
Always-before relation은 다음과 같이 정의할 수 있다.
즉, 첫 번째 액티비티가 일어나기 전에 두 번째 액티비티는 무조건 일어나는 관계를 말한다. 예를 들어, 우리의 예시 이벤트 로그에서 a2 액티비티 이전에 a1 액티비티는 항상 일어나므로, a2와 a1은 always-before 관계에 있다. 이 always-before 관계를 그림으로 표현하면 다음과 같다.
Never-together relation
Never-together relation은 다음과 같이 정의할 수 있다.
즉, 어떤 trace에서도 함께 일어나지 않는 액티비티들을 말한다. 예를 들어, a7과 a8 액티비티는 어떤 trace에서도 함께 일어나지 않기 때문에 a7과 a8은 never-togehter 관계에 있다. 이 never-together 관계를 그림으로 표현하면 다음과 같다.
Directly-follows relation
Directly-follows relation은 다음과 같이 정의할 수 있다.
즉, 이벤트 로그 내에 directly-follows 관계가 존재하면 이에 모두 포함된다. <a1, a2>, <a2, a4> 등 다양한 액티비티 쌍이 이 관계에 있다. 이 directly-follows 관계를 그림으로 표현하면 다음과 같다.
Directly-follows counter
Directly-follows counter은 다음과 같이 정의할 수 있다.
즉, 각 directly-follows relation이 일어난 빈도를 말한다. 예를 들어, a1과 a2 directly follows relation은 10번 일어났기 때문에 이들의 directly-follows counter은 10이다.
Sum counter
Sum-counter은 다음과 같이 정의할 수 있다.
즉, 각 액티비티가 이벤트 로그 전체에서 일어난 횟수를 말한다. 예를 들어, a1 액티비티는 이벤트 로그 전체에서 20번 일어났기 때문에 a1의 sum counter는 20이다.
Min & Max counter
Min&Max counter은 다음과 같이 정의할 수 있다.
즉, 각 액티비티가 하나의 trace 안에서 일어날 수 있는 최소와 최대 횟수를 말한다. 예를 들어, a2 액티비티는 최소 0번 최대 3번 일어날 수 있기 때문에 min counter는 0, max counter는 3이다.
Visualization
Log skeleton의 visualization은 위에서 보인 log skeleton의 visualization들을 하나로 합치는 것이다. 이들을 하나로 합치기 전에, 위의 equivalance relation에서 설명하지 않은 각 액티비티 아래쪽에 있는 세 개의 칸에 대해 설명하겠다. 가장 왼쪽은 사전상 가장 앞쪽에 있는 equivalent activity를 말한다. 가운데는 각 액티비티가 이벤트 로그 내에서 일어난 횟수, 즉 sum counter를 표시한다. 마지막으로, 가장 오른쪽은 각 액티비티의 min counter ... max counter를 표시한다.
각 액티비티에 equivalent activity, sum counter, min & max counter를 표시했으면 이들의 always-after relation과 always-before relation을 함께 표시한다.
이제 이것에 directly-follows relation과 never-together relation 또한 함께 표현한다. 이 때, always relation들과 directly-follows relation이 겹치는 경우에는 always relation이 우선순위를 가진다.
Classification
이제, 이 log skeleton 정보를 이용해 특정 trace가 이벤트 로그에 부합하는지를 판단할 차례이다. 이를 위해 우리는, subsum이라는 개념을 사용한다. 우선, 하나의 이벤트 로그가 다른 이벤트 로그에 subsum한다는 것은 다음과 같이 정의한다.
즉, 이벤트 로그 L이 이벤트 로그 L'을 subsum하려면,
- 이벤트 로그 L에서 두 액티비티가 equivalance relation, always-after relation, always-before relation이면 이벤트 로그 L'에서도 두 액티비티가 각 관계를 가지고 있어야 한다.
- 이벤트 로그 L'에서 directly follows relation을 가지는 두 액티비티는 이벤트 로그 L에서도 directly follows relation을 가진다.
이 개념을 확장하여 우리는 하나의 이벤트 로그가 하나의 trace를 subsum한다는 것을 다음과 같이 정의할 수 있다.
즉, 모든 A_req를 포함하고 A_fbd를 포함하지 않는 이벤트로그 내 trace가 해당 trace를 subsum하면, 이벤트 로그가 trace를 subsum한다고 할 수 있다. 그리고 이렇게 이벤트 로그가 trace를 subsum하면, 해당 trace는 이벤트 로그로부터 등장할 수 있는 trace로 구분(classified)된다.
이번 포스팅에서는 process discovery와 classification 개념을 접목한 log skeleton에 대해 알아보았다. Log skeleton은 다음과 같은 상황에서 활용될 수 있을 것이다.
- 이벤트 로그에 나타나지 않은 trace가 이벤트 로그에 부합하는지 알고 싶을 때
- 프로세스 모델에 이벤트 로그가 부합하는지를 알고 싶은데 replay를 하기에는 비용 부담이 클 때
다양한 conformance checking 알고리즘들을 각자의 상황에 맞게 적재적소에 활용한다면 연구가 아닌 실제로 프로세스 마이닝을 활용할 때에 더욱 도움이 될 것이다.
References
Log skeletons: A Classification Approach to Process discovery. H.M.W. Verbeek and R.M. de Carvalho.
최근댓글