Process Discovery란?
Process Discovery는 event log를 통해 process model을 도출하는 과정이다.
(여기서 event log는 이전 글에서 소개했듯 multiset of traces이고, process model은 set of traces를 정의한다.)
DFG(Directly Follows Graph)
process discovery의 기본적인 접근 방식인 DFG(Directly Follows Graph)의 경우 node와 arc로 구성된다. nodes는 시작/종료를 포함한 activity, arcs는 직접적으로 이어지는 activity의 관계를 나타낸다.
DFG는 직관적이며 이해하기 쉽고, 구현이 간단하다는 장점이 있지만 복잡한 흐름을 정확히 표현하지 못하는 구조적인 한계가 존재한다.
Petri Net
직관적이며, 동시성, 분기 등의 흐름을 명확히 표현할 수 있다는 장점이 있다.
Petri-Net N = (P, T, F)
P: place 집합
T: transition 집합
F : Directed arcs
Petri net은 node를 Place/Transition 2가지로 구분한다.
Place : 원으로 표시되며, token이 머물 수 있는 node이다.
Transition : 사각형으로 표시되며, activity를 나타낸다.
input place에서 token을 소비하고, output place에 token을 생성한다.
Arc : 화살표로 표시되며, place와 Transition을 연결한다. (P-P / T-T는 연결하지 않는다.)
Marked Petri-Net = (N, M)
여기서 N은 Petri-Net / M은 Marking의 집합이다.
Marking이란 현재 token의 상태/분포를 의미하는데,
token은 검은 원으로 표시되며, marking에 따라 현재 상태를 결정한다.
Labeled Petri-Net N = (P, T, F, A, I)
Petri-Net + A - activity에 label을 붙인 형태, I - labeling 함수
실제 activity 명을 붙여 현실의 프로세스를 모델링
위 사진을 통해 구조를 설명하면,
Place (○) : c1, c2, c3, c4, c5 (원) → 상태를 의미
Transition (□) : a, b, c, d, e, f, g, h (사각형) → activity
Token (●) : start에 있는 검은 점 → 현재 상태
Label
Transition에는 단순 기호뿐 아니라 실제 활동명이 라벨링되어 있음.
a: register request / b: examine thoroughly 등 ..
위 그림 예시에서 흐름을 정리해보면
시작 (start) : 토큰 1개가 위치
a (register request) 실행
AND-split → 토큰이 c1, c2 두 곳에 분산
- c1에서는 XOR-split -> b (examine thoroughly) 또는 c (examine casually) 중 하나 선택
- c2에서는 d (check ticket) 실행
c3, c4의 토큰이 AND-join 되고 e (decide) 실행
c5에서 XOR-split → g (pay compensation) 또는 h (reject request) 선택 ( f로 갈 경우 루프 )
end place에서 종료
추가 개념 정리
enabled : 특정 Transtion의 input place에 모두 token이 있는 상태
Firing : 특정 Transiton이 Enabled일 때, input place의 token을 소비 -> output place에 token을 생성
Initial Marking : 처음 상태의 Marking
Reachable marking : Transition Firing을 통해 도달할 수 있는 marking
Unreachable marking : Transition Firing을 통해 도달할 수 없는 marking
References
-
A practitioner's guide to process mining: Limitations of the directly-follows graph https://www.vdaalst.com/publications/p1101.pdf
-
https://www.researchgate.net/figure/Processing-of-the-directly-follows-graph_fig7_378827766 (DFG 사진 자료)
