만약 우리가 Conformance Checking을 원하는 프로세스 모델이 액티비티 100000개로 구성된 복잡한 프로세스 모델이라면 우리는 정해진 시간과 메모리 내에 Conformance Checking을 할 수 있을까? 아마 높은 확률로 실패할 것이다. 이러한 문제를 해결하기 위해 등장한 개념이 이벤트 로그와 페트리 넷을 쪼개어 연산하는 decomposition이다. 이번 포스팅에서는 decomposition 중에서도 activity based decomposition을 이용하여 페트리 넷을 decomposition하는 방법들에 대해서도 알아보겠다.
Petri net의 cut
가장 먼저 해야할 일은 프로세스 모델(페트리 넷)을 자르는 것이다. 이 잘린 subnet의 액티비티에 따라서 이벤트 로그도 나뉘게 된다. 그렇다면 페트리 넷을 어떻게 나눠야 할까?
Valid Decomposition
페트리 넷을 적절한 방법으로 자르는 것을 valid decomposition이라고 한다. Valid decomposition은 다음 조건들을 만족해야 한다.
1. place와 edge는 하나의 subnet 안에만 포함되어야 한다.
모든 place와 edge는 하나의 subnet 안에만 포함되어야 한다. 즉, 한 place가 서로 다른 두 subnet에 모두 포함되는 경우가 없어야 한다. 또한 한 edge가 서로 다른 subnet에 모두 포함되는 경우도 없다.
2. unique, visible transition만이 여러 subnet에 포함될 수 있다.
중복된 라벨을 가지는 transition이거나 silent transition인 경우에는 하나의 subnet 안에 있어야 한다. 즉, silent transition은 silent transition끼리 하나의 subnet을 구성해야 하고, 중복된 transition은 하나의 subnet 안에 그 중복된 transition들이 모두 포함되어야 한다.
3. subnet의 합집합이 original net이 되어야 한다.
subnet들을 모두 합하면 나누기 전의 original net이 되어야 한다.
다음 예시 decomposition을 보자.
이 decomposition은 valid decomposition인가? 답은 맞다. 각 subnet 내에 place가 두 번 들어가거나 silent transition, duplicate transition이 존재하지 않고, 이들을 합하면 subnet이 되기 때문이다. 그렇다면 다음 예시를 보자.
이 decomposition은 valid decomposition인가? 답은 아니다. 왜냐하면 dupliace transition인 t3과 t6이 서로 다른 subnet에 속해 있기 때문이다.
Maximal Decomposition
Maximal decomposition은 다음과 같은 방법으로 찾을 수 있다.
1. 하나의 arc를 선택한다.
2. 그 arc의 시작이나 끝이 place나 invisible(silent) transition이면 그 place나 invisible transition에 연결된 다른 arc도 subnet의 구성원이 된다.
다음과 같은 예시 페트리 넷이 있다고 하자.
우선 하나의 arc를 선택한다. 우리는 (c0,t1)을 선택하겠다.
이 arc에 연결된 silent transition이나 place에 연결된 arc가 있는가? place c0에는 다른 연결된 arc가 없다. 그렇기 때문에 이것 하나가 maximal decomposition의 subnet이 된다.
다음으로, (t1,c1)을 선택한다.
이 arc에 연결된 silent transition이나 place에 연결된 arc가 있는가? place c1에 연결된 (c1,t2), (c1, t3), (c1, t6)이 있다. 이들을 subnet에 포함시킨다.
여기에서 또 연결된 silent transition이나 place에 연결된 arc가 있는가? silent transition t2가 있다. 이에 연결된 (t2, c3)를 subnet에 포함시킨다.
여기에서 또 연결된 silent transition이나 place에 연결된 arc가 있는가? place c3에 연결된 (t3, c3), (c3, t5)가 있다. 이들을 subnet에 포함시킨다.
이러한 방식으로 모든 maximal decomposition을 찾으면 다음과 같다.
Maximal Valid Decomposition
위에서 설명한 maximal decomposition과 valid decomposition을 합한 개념이 maximal valid decomposition이다. 이는 간단하게 maximal decomposition에서 valid decomposition 조건을 만족시키지 못하는 subnet(silent transition이 여러 net에 포함되어 있거나 duplicate transition이 여러 넷에 포함되어 있는 경우 등)들을 하나의 subnet으로 합해주면 된다. 예를 들어 다음과 같은 페트리 넷이 있다고 하자.
우선, 이에 대해서 maximal decomposition을 찾는다. 그 결과는 다음과 같다.
이 때, 같은 label을 가진 t3, t7, t8이 서로 다른 subnet에 포함되어 있다. 그러므로 이들을 valid decomposition으로 만들기 위해 같은 subnet으로 합해준다.
이들 subnet을 표시하면 다음과 같이 표시할 수 있다.
Conformance Checking
이렇게 petri net의 decomposition이 끝나면, 이 나눠진 subnet들을 바탕으로 하여 conformance checking을 진행할 수 있다. 그리고 이 때, petri net의 decomposition이 valid하고 기존의 이벤트 로그가 페트리 넷에 대해 replayable했다면 subnet을 기준으로 나눠진 이벤트 로그 또한 replay가 가능하다. 그렇기 때문에 각 subnet에 포함된 액티비티 셋을 구하고, 이 액티비티 셋에 따라 이벤트 로그를 activity-based decomposition하여 각 net에 대해 conformance checking을 진행하는 것이 가능해진다.
이번 포스팅에서는 activity를 기준으로 하여 페트리 넷을 decomposition하고, 이를 바탕으로 간단히 conformance checking을 하는 방법에 대해 알아보았다. 이를 통해 우리는 복잡하고 큰 프로세스 모델을 여러 개의 작고 단순한 프로세스 모델로 나눌 수 있고, 이에 대해 conformance checking을 진행함으로써 연산 시간과 메모리를 획기적으로 절약할 수 있다. 이는 특히 액티비티의 개수에 의해 알고리즘의 복잡도가 결정되는 알고리즘에 유용할 것이다. 다음 포스팅에서는 conformance checking 알고리즘 중에서 alignment에 activity-based decomposition을 이용하는 방법에 대해 알아보겠다.
References
1. Course: Advanced Process Mining. RWTH. Dr. Sebastiaan J. van Zelst
2. Section 12.3.1. of Wil van der Aalst. Process Mining: Data Science in Action (Second Edition) : Springer, 2016.
최근댓글