페트리 넷(Petri Net)은 프로세스 마이닝의 가장 기본이 되는 프로세스 모델이다. 가장 간단한 형태로 프로세스를 나타낼 수 있기 때문에 많은 Process Discovery 알고리즘들이 이벤트 로그로부터 페트리 넷을 도출해 내는 것을 기본으로 한다.
페트리 넷 또한 가장 간단한 예시와 함께 설명하도록 하겠다. 예를 들어, 여행을 가는 프로세스가 있다고 가정하자. 우리는 맨 처음에 여행 계획을 짜고, 숙소 예약과 비행기 예약을 하고 여행을 출발할 것이다. (물론, 여행을 출발하고 숙소를 예약하는 나의 베를린 여행 같은 경우도 있겠지만 그런 것은 없다고 가정한다.) 그렇다면 다음과 같은 페트리 넷이 도출될 것이다. 이제 이를 하나하나 살펴 보겠다.
Place, Transition, Arc, Token
페트리 넷은 기본적으로 Token, Place, Transition, Arc의 네 가지 구성 요소로 구성된다.
Token
Token은 페트리 넷에서 작은 꽉 차 있는 원(그림에서는 검은색 원)으로 표현된다. Token은 페트리 넷 안을 화살표를 따라 움직이면서 프로세스를 진행시키는 역할을 한다.
Place
Place는 페트리 넷에서 원으로 표현된다. Place는 Token을 가지고 있을 수 있다. 위 페트리 넷에서는 p1, p2, ... , p5가 place이다.
Transition
Transition은 페트리 넷에서 사각형으로 표현된다. Transition은 주로 이벤트 로그에서의 액티비티를 뜻한다. 그래서 위의 경우에는 여행 계획, 비행기 예약, 숙소 예약, 여행 출발이 모두 Transition으로 표현되었다. Transition은 Token을 만들어내거나(produce) 소비한다(consume). Transition의 token 생성과 소비는 뒤에서 더 자세히 알아보도록 하겠다.
Arc
Arc는 페트리 넷에서 화살표로 표현된다. Arc는 transition과 place 혹은 place와 transition을 연결하는 역할을 하며, token이 이를 따라서 이동한다.
Enabled과 Fire
Enabled
Enabled란, transition이 실행(fire)될 수 있도록 준비된 상태를 의미한다. 이는 transition으로 들어오는(input) 모든 place들에 token이 한 개 이상 있는 상태를 말한다. 위에서 말한 여행 페트리 넷 예시를 통해 살펴보자.
우선, 여행 계획 transition을 보자. 여행 계획 transition으로 들어오는 place는 p1 한 개밖에 없는데, 이것에는 token이 있다. 그렇기 때문에 여행 계획 transition은 enabled 상태이다.
다음으로, 숙소 예약 transition을 보자. 숙소 예약 transition으로 들어오는 place는 p2 한 개인데, 이것에는 token이 없다. 그렇기 때문에 숙소 예약 transition은 enabled 상태가 아니다.
마지막으로, 여행 출발 transition을 보자. 여행 출발 transition으로 들어오는 place는 p4, p5인데, 이것에는 모두 token이 없다. 그렇기 때문에 여행 출발 transition은 enabled 상태가 아니다. 그런데 여기서, p4에만 token이 2개 있다면 여행 출발 trnasition은 enabled일까? 답은 아니다. 왜냐하면, 위의 enabled의 정의에서 모든 input place들에 token이 한 개 이상 있어야한다고 했기 때문이다.
Fire
Fire란, transition이 enabled되었을 때 그 transition이 실행되는 것을 뜻한다. 이 때, 모든 input place에 있는 한 개의 token들은 소비되고(consume), 모든 output place에 한 개의 token이 만들어진다(produce). 이 또한 예시를 통해 살펴보겠다.
위에서 우리는 여행 계획 transition이 enabled되었음을 확인하였다. 그러므로 우리는 여행 계획 transition을 fire할 수 있다. 그러면 아래 그림과 같이 모든 input place (p1)의 token이 소비되고, 모든 output place(p2, p3)에 token이 생성될 것이다.
Marking
Marking이란, 페트리 넷 안에 token이 있는 그 상태 자체를 의미한다. 위에서 우리는 p1에 token이 1개 있는 상태, p2, p3에 token이 각각 1개씩 있는 상태를 모두 보았는데, 이 각각의 상태가 p1에 token이 1개 있는 marking, p2, p3에 token이 각각 1개씩 있는 marking이다.
Initial Marking
Initial Marking이란, 말 그대로 처음 상태의 marking을 의미한다.
Reachable Marking, Unreachable Marking
Reachable Marking이란, initial marking으로부터 도달할 수 있는 marking을 의미한다. 또 다시 여행 페트리 넷이 등장한다. 여기에서 p1에 token이 한 개 있는 것을 initial marking이라고 하자.
이 initial marking에서 위에서 본 것처럼 여행 계획 transition이 fire되면 p2, p3에 token이 1개씩 있는 marking이 될 것이고, 이는 reachable marking이다. 거기에서 숙소 예약 transition이 fire되면, p4와 p3에 token이 1개씩 있을 것이고, 이 또한 reachable marking이다.
Unreachable marking이란, reachable marking의 반대말로, initial marking에서 도달할 수 없는 marking을 의미한다. 위와 같은 initial marking에서 우리는 p4에만 token이 3개 있는 marking에 도달할 수 없다. 이와 같은 marking이 unreachable marking이다.
오늘 우리는 페트리 넷의 기본적인 구성 요소와 이것이 어떻게 작동하는지에 대해 알아보았다. 위에서도 말했지만 페트리 넷은 프로세스 마이닝의 가장 기본이 되는 프로세스 모델 형태이기 때문에, 이를 정확하게 이해하는 것은 무척 중요하다!
이 페트리 넷을 도출하는 방법은 정말 많다. 페트리 넷을 도출하는 간단한 알고리즘 중 하나에 대해 알고 싶다면 다음 포스팅을 참고한다.
2019/05/31 - [Process Mining - Theory/Process Discovery] - 알파 알고리즘 (Alpha Algorithm)이란?
알파 알고리즘 (Alpha Algorithm)이란?
알파 알고리즘(Alpha Algorithm)은 이벤트 로그로부터 프로세스 모델을 찾는, Process Discovery의 가장 기본이 되는 가장 단순한 알고리즘이다. 여태까지 Process Discovery가 무엇인지를 직관적으로 이해하지 못..
process-mining.tistory.com
References
1. Course: Business Process Intelligence. RWTH. Prof. Wil van der Aalst.
최근댓글