저번 포스팅에서 우리는 dynamic bottleneck이 무엇이고, 이것의 static bottleneck과의 차이점이 무엇인지에 대해 알아보았다. 이번 포스팅에서 우리는 dynamic bottleneck을 프로세스 마이닝 관점에서 도출하는 방법에 대해 알아보겠다.
개요
이 방법은 다음의 세 가지 질문에 대해 대답하는 것을 목표로 한다.
- system-level event를 도출할 수 있는가?
- dynamic bottleneck으로 이어지는 system-level event를 도출할 수 있는가?
- dynamic bottleneck으로 이어지는 frequent pattern이 존재하는가?
이 질문들에 대답하기 위해, 우리는 다음과 같은 단계를 거친다.
방법론
이 방법론은 event definitions on different levels, detecting system-level events, detecting system-level event cascades, detecting frequent patterns in cascades의 총 4가지 단계로 이루어진다.
Event definitions on different levels
가장 먼저 우리는 dynamic bottleneck을 나타내는 system level event를 찾기 위해 기존의 프로세스 마이닝에서 사용하던 이벤트 로그로부터 segment event log와 system level event log를 도출한다. 이들을 간단한 그림으로 나타내면 다음과 같다.
지금부터 각각의 이벤트가 무엇인지에 대해 하나하나 알아보겠다.
case-level event
case-level event log는 우리가 알고 있는, 프로세스 마이닝에서 기본적으로 사용하는 그 이벤트 로그를 말한다. case-level event는 case id, activity, time으로 이루어져 있으며 이 이벤트들의 순서는 하나의 케이스 안에서 시간 순서에 따라 정해진다. 이를 수학적으로 나타내면 다음과 같다.
이 case-level event log의 예시는 다음과 같다.
segment-level event
segement-level event log는 directly related되어 있는 case-level event의 pair로 이루어진다. 즉, 하나의 케이스 안에 속해 있는 바로 연속한 두 이벤트 쌍을 말한다. segment-level event는 case id, source activity, target activity, start time, end time으로 이루어져 있으며, start time은 source activity가 일어난 시각, end time은 tartet activity가 일어난 시각을 말한다. 이 이벤트의 순서는 source activity와 target activity가 같을 때 start time 혹은 end time 중 하나의 기준의 순서에 의해 결정된다. 이를 수학적으로 나타내면 다음과 같다.
이 segment-level event log의 예시는 다음과 같다.
system-level event
system-level event log는 연속한 segement-level event의 집합으로 이루어진다. system-level event는 event type, source activity, target activity, start time, end time, segment events로 이루어지고, start time은 첫 segment의 시작 시각, end time은 마지막 segement의 종료 시각을 말한다. (event type에는 BL(Blockage)과 HL(High Load)가 있다. 이들 이벤트 타입에 대해서는 뒤에 좀 더 자세히 설명하겠다.) 이 이벤트의 순서는 start time 혹은 end time 중 하나의 기준의 순서에 의해 결정된다. 이를 수학적으로 나타내면 다음과 같다.
이 system-level event log의 예시는 다음과 같다.
Detecting system-level events
다음으로 우리는 위에서 정의한 system-level event를 찾는 방법에 대해 알아볼 것이다. 우리의 궁극적인 목표는 dynamic bottleneck이 되는 system-level event를 도출하는 것이다. 이를 위해 우리는BL(Blockage)과 HL(High Load)의 두 가지 system-level event type을 정의한다.
Blockage (Dyanmic Bottleneck)
Blockage는 액티비티 a로부터 액티비티 b로 진행할 때에 시간이 과하게 오래 걸리는 경우를 말한다. 그렇다면 이 '시간이 과하게 오래 걸리는 경우'를 어떻게 정의할 수 있을까?
이를 예시와 함께 알아보겠다. 다음과 같은 segment level event log가 있다고 하자.
우선, 우리는 시간이 과하게 오래 걸리는 경우를 찾기 위해 각 segment들의 소요 시간의 중앙값을 찾는다. 이를 t tilde로 정의한다. 우리의 예시에서는 소요 시간이 10, 10, 12, 15, 15, 30이기 때문에 이것이 12가 될 것이다. 그 후에 아래 식에 따라 modified z-score 값을 계산한다.
해당 segement의 M(s) 값이 특정 threshold k보다 높으면 이를 delay로 생각하는 것이다. 만약 우리가 k를 5라고 하면, s2가 delay된 segment로 정의된다. 그 이후에 이러한 delay된 연속한 segment들이 있으면 이들을 모아 blockage system-level event라고 부르고, 이들을 dynamic bottleneck으로 생각한다.
High Load
High Load는 특정 구간에서 너무 많은 수의 케이스가 밀려 있는 경우를 말한다. 그렇다면 이 '너무 많은 수의 케이스가 밀려 있는 경우'를 어떻게 정의할 수 있을까?
이를 예시와 함께 알아보겠다. 다음과 같은 segment-level event log가 있다고 하자. (위의 blockage 부분에서 본 예시 segment level event log와 같다.)
우선, 우리는 특정 단위 시간에 많은 케이스가 몰리는 경우를 찾기 위해 각 시간을 bin으로 나눈다. 예를 들어 우리의 k를 5분이라고 하고 시작 시각을 10:20:00이라고 하면, bin_0은 10:20:00-10:24:59, bin_1은 10:25:00-10:29:59가 되는 식이다. 그렇게 bin을 나눈 뒤 해당 bin에 포함되는 segment를 도출하면 다음과 같다.
각 bin에 포함되는 segment 개수를 우리는 workload로 정의한다. 이 workload가 전체 bin들의 75% percentile보다 많으면 이를 우리는 highload로 정의한다. 우리의 예시에서는 75% percentile이 1이기 때문에, workload가 3인 bin_0에 해당하는 segment들의 집합인 system-level event가 highload가 되는 것이다.
Detecting system-level event cascades
Relation detection
여태까지 우리는 system-level event를 어떻게 정의하는지에 대해 알아보았다. 이제부터 우리는 각 system-level event 사이에 어떤 관계가 있는지에 대해 알아볼 것이다. 우리는 이를 평가하기 위해 spatial property와 temporal property의 두 가지 property를 사용한다.
- spatial property: segement의 어떤 위치에 위치하는가를 의미한다. 즉, source activity와 target activity가 무엇인지를 말한다. 두 system-level event의 source activity와 target activity 중 하나라도 겹치면 spatial relation이 있다고 한다.
- temporal property: 어떤 시각에 일어났는가를 의미한다. 즉, start time과 end time 시각의 특성을 말한다. start time과 end time에 겹쳐지는 부분이 있으면 temporal relation이 있다고 한다.
우리는 이 두 property를 활용하여 각 system-level event가 related 되어있는지를 판단한다. 다음과 같은 예시 system-level event들이 있다고 하자.
a, b, c, d, e의 system-level event 중에서 서로 related되어 있는 이벤트는 어떤 것이 있을까? 우선, a와 b가 있을 것이다. a의 target activity인 L3과 b의 source activity인 L3가 겹치고, 시간도 겹치는 부분이 있기 때문이다. 이런 방법으로 쌍을 찾으면 (a, b), (b, d), (b, c), (c, e)가 related되어 있다고 판단할 수 있다.
cascades of system-level events detection
이렇게 윗단계에서 각 system-level event들의 relation을 찾았다면, 이를 바탕으로 cascade를 도출한다. cascade의 node는 각 system-level event가 되고, edge는 해당 system-level event들이 related되어 있으면 생성된다. 이 때, 이 edge의 방향은 start time 시각 기준으로 만들어진다. 위 예시 system-level event들로부터 우리는 다음과 같은 cascade를 도출할 수 있다.
Detecting frequent patterns in cascades
마지막으로 우리는 도출된 cascade로부터 dynamic bottleneck(Blockage)으로 이어지는 frequent pattern을 도출한다. 이는 간단히 event type, source activity, target activity가 같은 노드들로 이루어진 빈도가 상위인 패턴들을 도출하는 것으로 해결된다.
결론
이번 포스팅을 통해 우리는 dynamic bottleneck을 프로세스 마이닝의 기본적인 이벤트 로그로부터 도출하는 방법에 대해 알아보았다. 이를 통해 우리는 static bottleneck을 도출하는 기존의 bottleneck analysis로부터 한걸음 더 나아가 더 현실적이고 정확한 dynamic bottleneck을 도출할 수 있을 것이다.
References
1. Z. Toosinezhad, D. Fahland, Ö. Köroğlu and W. M. P. van der Aalst, "Detecting System-Level Behavior Leading To Dynamic Bottlenecks," 2020 2nd International Conference on Process Mining (ICPM), Padua, Italy, 2020, pp. 17-24, doi: 10.1109/ICPM49681.2020.00014.
최근댓글