많은 process discovery 알고리즘들이 빅 데이터에 대해서는 좋지 못한 성능을 보여준다. 그렇기 때문에 이를 해결하기 위해 이벤트 로그를 샘플링하여 이를 분석하거나, 몇몇 성능을 포기하기도 한다. 하지만 실제로 데이터를 분석할 때에는 액티비티의 종류가 너무 많아 샘플링이 너무 많은 정보를 잃게 하여 샘플링이 불가능한 경우도 있고, 성능을 포기할 수 없는 경우도 있다. 그렇다면 샘플링이 불가능한 빅 데이터에 대해서 process discovery를 하는 방법에는 어떤 것이 있을까? 이번 포스팅에서는, 위에서 설명한 문제를 해결하기 위해 등장한 process discovery 알고리즘인 Inductive Miner - directly follows based (IMD) 알고리즘에 대해 알아보겠다.
* 이번 포스팅은 Inductive Miner에 대한 이해가 있다는 것을 가정한다.
2019/07/23 - [Process Mining - Theory/Process Discovery] - Inductive Miner란?
Inductive Miner란?
한 달 만의 글이다. 학회와 시험과 여행의 조합으로 이제야 일상으로 돌아왔다. 그리웠다... 20일 뒤에 또 시험인 것은 함정 ^_^ Inductive Miner는 Process Discovery 알고리즘 중 하나로, 이벤트 로그로부터 프..
process-mining.tistory.com
IMD 알고리즘
우선, 다음과 같은 예시 이벤트로그가 있다고 하자.
1. DFG 도출 및 Cut Detection
가장 먼저 해야 할 일은 보통의 Inductive Miner와 같이 이벤트 로그로부터 Directly Follows Graph를 도출하고, 그 DFG에서 cut을 찾는 일이다. (자세한 것은 위의 Inductive MIner 포스팅을 참고한다.) 이렇게 DFG와 Cut을 찾으면 다음과 같다.
우리는 우리의 예시로부터 세 개의 sequential cut을 찾을 수 있다. 여기에서 기존의 Inductive Miner와 다른 부분이 나온다. 기존의 Inductive Miner는 cut이 찾아지면 이에 따라 이벤트 로그를 다시 돌아가면서 하나하나를 projection하는 방식으로 DFG를 만들어 주었다. 하지만 IMD에서는, 이벤트 로그를 다시 하나하나 돌아가는 것이 아니라 DFG 자체를 cut에 따라 바로 나누어 준다. 데이터가 크면 클수록 이벤트 로그를 하나하나 다시 돌아가며 projection하는 것이 부담스러워지겠지만, IMd의 경우 맨 처음에 DFG를 찾을 때만 이벤트 로그를 참고하기 때문에 빅 데이터에 대해 process discovery를 하는 것이 가능해지는 것이다.
이 찾아진 cut에 따라 나눠진 DFG를 그려주면 다음과 같다.
이 때, 잘라진 DFG를 나타낼 때 주의해야 할 점은 sequential cut과 loop cut의 경우 새로운 start activity와 end activity를 지정해주어야 한다는 점이다. 예를 들어, 자르기 전의 DFG에서는 a가 start activity이고 end activity는 아니었지만, 잘라진 DFG의 a가 포함된 DFG에서는 end activity가 따로 없기 때문에 다른 cluster로 나가는 액티비티인 a를 end activity로 지정해주어야 하는 것이다.
2. Recursion
나누어진 DFG에 따라 기존 Inductive Miner처럼 base case만 남을 때까지 다시 1번의 cut detection을 반복해준다. 첫 번째 DFG(D2)와 마지막 DFG(D5)는 이미 base case이기 때문에 recursion을 하지 않아도 된다. 그러므로 현재 우리의 process tree는 다음과 같다.
먼저 D3를 보자. D3에는 {b,c} / {d,e}에 XOR cut이 존재한다. 그리고 b와 c 사이에는 parallel cut이, d와 e 사이에는 loop cut이 존재한다. 이를 표현하면 다음과 같다.
그리고 이를 process tree로 표현하면 다음과 같다.
다음으로 D4를 보자. D4에서는 아무 cut도 찾을 수 없다. 이럴 때 등장하는 것이 FallThrough이다.
3. FallThrough
기존의 Inductive MIner에서 FallThrough는 아래 포스팅과 같이 진행되었다. (넘어가도 좋다.)
Inductive Miner Fall Through (Inductive Miner에서 Cut을 찾을 수 없을 때)
저번 포스팅에서 우리는 Inductive Miner가 어떻게 프로세스 모델을 도출하는지에 대해 알아보았다. 2019/07/23 - [Theory/Process Discovery] - Inductive Miner란? 불러오는 중입니다... Inductive MIner는 기본..
process-mining.tistory.com
Inductive Miner의 Fall Through는 이벤트 로그의 projection이 필수적으로 동반되어야 한다. 하지만 IMD 알고리즘은 빅 데이터에 대한 Inductive miner이기 때문에 그것을 원하지 않는다. 그러므로 IMD에서 아무 cut도 찾을 수 없을 때에는 해당 DFG의 액티비티로 만들 수 있는 모든 behavior를 허용하는 flower model을 도출한다. D4로부터 도출된 flower model은 다음과 같이 표현할 수 있다.
4. 프로세스 모델 완성
이제 모든 DFG에 대해 프로세스 트리를 도출했다. 프로세스 모델이 완성된 것이다.
장점과 단점
장점
IMD 알고리즘의 가장 큰 장점은 이벤트 로그를 한 번만 순회해도 된다는 것이다. 기존의 Inductive Miner와는 달리 이벤트 로그를 DFG를 생성할 때만 순회하기 때문에 빅 데이터에 대해서도 process discovery가 가능하다. 또한 기존의 Inductive miner와 같이 sound한 프로세스 모델을 도출한다는 장점도 가진다.
단점
이벤트 로그를 한 번만 순회하기 위해서 fallthrough 상황에서 무조건 flower model만을 도출한다. 그렇기 때문에 기존의 fallthrough보다는 더 많은 behavior를 허용하는, precision이 낮은 프로세스 모델을 도출할 수도 있다는 단점을 가진다.
이번 포스팅에서는 빅 데이터에 대해 Inductive Miner를 적용시키기 위한 알고리즘인 IMD 알고리즘에 대해 알아보았다. 요즘 너무너무 바쁘고 연구에서 스트레스를 많이 받아서 집에서 집안일하고 쉬기 바쁨 + 프로세스 마이닝 논문 집에서 못 쳐다보겠음 + 이론 글은 별로 인기 없음 ㅎㅎ 의 이유로 이론 글을 오랜만에 썼는데, 잘 썼는지 모르겠다 하하..
다음 포스팅에서는 Infrequent behavior를 필터링하는 Inductive Miner, Incomplete log를 다루는 Inductive Miner들에 대해서도 알아보겠다.
References
1. Leemans S.J.J., Fahland D., van der Aalst W.M.P. (2015) Scalable Process Discovery with Guarantees. In: Gaaloul K., Schmidt R., Nurcan S., Guerreiro S., Ma Q. (eds) Enterprise, Business-Process and Information Systems Modeling. BPMDS 2015, EMMSAD 2015. Lecture Notes in Business Information Processing, vol 214. Springer, Cham
최근댓글