[Process Mining] Alpha Algorithm

α-Algorithm

알파 알고리즘은 event log를 입력으로 받아 petri-net을 산출하는 알고리즘이다. Process Discovery와 관련해서 baseline이 되는 가장 기본적이며 단순한 알고리즘이다.

먼저 α-Algorithm의 Basic Idea에 대해 알아 보자.

---

입력과 출력

• 입력: 이벤트 로그 $( L \in B(A^*) )$

  • $( A )$: 활동 집합 (activities)
  • $( L )$: 여러 trace들의 multiset

• 출력: WF-net 형태의 Petri net

---

로그 기반 순서 관계 (Log-based Ordering Relations)

이벤트 로그에서 activity 간 순서 관계를 정의하는 네 가지 규칙

• directly follows
  $( a >_L b )$: 로그의 어떤 trace에서 a 바로 뒤에 b가 나옴

• causality
  $( a \to_L b )$: $( a >_L b )$ 이면서 $( b \not>_L a )$
  → a 뒤에 b는 나오지만 b 뒤에 a는 나오지 않음

• parallel
  $( a \parallel_L b )$: $( a >_L b )$ 그리고 $( b >_L a )$
  → a와 b는 서로 순서가 바뀌어 나타남 → 동시 실행 가능

• no relation
  $(a \#_L b)$ : $( a \not>_L b )$ 이고 $( b \not>_L a )$
  → 둘 사이에 직접적 순서가 없음

---

Footprint Matrix

위 4가지 relation을 기반으로 행렬 형태로 정리한 것

---

Discovery Patterns

α-algorithm은 log footprint를 가지고 패턴을 식별한다.

• Sequence: a → b → …
  

• XOR-split / XOR-join

  • 로그에서 a → b, a → c 이면서 b # c → split (둘 중 하나 선택)
  • a → c, b → c 이면서 a # b → join(둘 중 하나에서 c로 이어짐)
    

• AND-split / AND-join

  • a → b, a → c 이면서 b ∥ c → 병렬 실행 (AND-split)
  • a → c, b → c 이면서 a ∥ b → 동시 실행 후 join (AND-join)
    

---

이제 본격적으로 알파 알고리즘이 어떻게 이벤트 로그가 주어졌을 때, 이를 Petri Net으로 생성하는 지 알아보자.

1. $T_L$: 로그에 등장하는 모든 activity 집합

• 어떤 activity들이 로그에 나타나는 지 확인한다.
  → Petri Net의 transition으로 대응

2. $T_I$: 로그에서 시작 activity 집합 (trace의 첫 번째 activity들)

3. $T_O$: 로그에서 종료 activity 집합 (trace의 마지막 activity들)
   

4. $X_L$ : 입력 activity 집합 A, 출력 activity 집합 B 쌍들 중에서,

   $a \to_L b$ (인과관계) 찾기

• A 내부 activity들은 서로 no relation (#)
• B 내부 activity들도 서로 no relation (#)

5. $Y_L$ : $X_L$에서 최대 쌍(maximal pairs)만 선택
   (중복/부분 집합 제거)
   

6. $P_L$: $Y_L$의 각 쌍 (A,B)에 대해 place $p(A,B)$ 생성 + 시작 place $i_L$, 종료 place $o_L$ 추가
   

7. $F_L$: $a \in A$이면 $(a, p(A,B))$ / $b \in B$이면 $(p(A,B), b)$
   시작 activity $(i_L, t)$, 종료 activity $(t, o_L)$
   

8. 결과: $\alpha(L) = (P_L, T_L, F_L)$
   

→ 이벤트 로그에 맞는 Petri Net 생성

---

References