알파 알고리즘

α-알고리즘 또는 α-마이너는 일련의 사건으로부터 인과관계를 재구성하는 것을 목표로 하는 프로세스 마이닝에 사용되는 알고리즘이다.그것은 판 데르 알스트, 바이테르스, 멀슈테르에 ^[1]의해 처음 제안되었다.Alpha miner의 목표는 이벤트 로그의 다양한 활동 간의 관계를 기반으로 이벤트 로그를 워크플로우 네트워크로 변환하는 것입니다.이벤트 로그는 트레이스의 복수 세트이며 트레이스는 액티비티 이름의 시퀀스입니다.그 후 몇 가지 확장 또는 수정 사항이 제시되었으며, 이는 다음과 같습니다.

알파 마이너는 최초로 제안된 프로세스 디스커버리 알고리즘으로 프로세스 디스커버리 목적과 프로세스 내의 다양한 액티비티가 어떻게 실행되는지에 대한 개요를 제공합니다.알파 광부는 또한 발견적 광부와 같은 많은 다른 공정 채굴 기술의 개발의 기초가 되었고, 유전 채굴은 알파 광부가 ^[2]만들어졌다는 아이디어를 바탕으로 개발되었습니다.

간단한 설명

이 알고리즘은 $W\subseteq T^{*}$ W $W\subseteq T^{*}$ T ${\$ \ $displaystyle$ W \ $subseteq T^$ { * } 를 $W\subseteq T^{*}$ 입력으로 하여 워크플로우넷을 구축합니다.

작업 간에 관찰된 인과 관계를 조사함으로써 그렇게 합니다.예를 들어, 모든 실행 추적에서 특정 태스크가 항상 다른 특정 태스크보다 먼저 수행될 수 있으므로 유용한 정보가 됩니다.

사용되는 정의

워크플로우 트레이스 또는 실행 트레이스는 태스크의 알파벳 T $(\displaystyle$ T $)$ 위에 $T$ 있는 문자열입니다.
워크플로우 로그는 워크플로우 트레이스 세트입니다.

이벤트 로그

프로세스 디스커버리 알고리즘을 적용하기 위한 주요 요건은 이벤트 로그입니다.이벤트 로그는 케이스의 고유 식별자, 프로세스에서 발생하는 액션을 기술하는 액티비티 이름 및 타임스탬프로 구성됩니다.이벤트 로그는 여러 활동 집합으로 나타낼 수 있습니다.알기 쉽게 하기 위해 다음 예에서는 알파벳 문자를 사용하여 활동을 나타냅니다.다음 그림에 나타난 이벤트 로그의 예를 생각해 보겠습니다.

이벤트 로그 샘플
케이스 ID	활동	타임스탬프
1	A	2019/10/09 14:50:17.000
1	B	2019/10/09 15:50:17.000
1	C	2019/10/09 15:56:17.000
1	D	2019/10/10 13:50:17.000
2	A	2019/10/10 14:30:17.000
2	C	2019/10/10 14:50:14.000
2	B	2019/10/11 09:50:17.000
2	D	2019/10/11 10:50:17.000
3	A	2019/10/11 12:50:17.000
3	E	2019/10/21 14:50:17.000
3	D	2019/10/21 15:50:17.000

이벤트 로그는 트레이스의 복수 세트이며 트레이스는 액티비티의 시퀀스입니다.따라서 위와 같은 이벤트 로그는 다음 표기를 사용하여 나타낼 수 있습니다.

$L1=[<A,B,C,D>,<A,C,B,D>,<A,E,D>$

각 이벤트 로그를 여러 트레이스 세트로 요약할 수 있으며, 이러한 트레이스를 사용하여 프로세스 내의 다양한 액티비티 간의 관계를 더욱 세분화할 수 있습니다.알파 마이너의 규칙에 따르면,^[2] 다양한 경우에 속하는 활동은 4가지 유형의 관계를 가질 수 있습니다.

직접 승계: x > y 는 어떤 관계 x 가 y 뒤에 직접 이어지는 경우에만 해당됩니다.이 예에서는 A > B, A > E, A > C로 간주할 수 있습니다.
인과관계: x → y ifff x > y이지 y > x가 아닙니다. 이 예에서는 A → E라고 생각할 수 있습니다.
병렬: x y iff x > y 및 y > x. 이 예에서는 B C가 있습니다.
선택: x # y iff not(x > y) 및 not(y > x)입니다.이 예에서는 A # D가 있습니다.

패턴

시퀀스 패턴: A → B XOR 분할 패턴: A → B, A → C 및 B # C

AND 분할 패턴: A → B, A → C 및 B C

묘사

알파 마이너는 사건 로그를 직접 추적, 시퀀스, 병렬 및 선택 관계로 변환하고 이를 사용하여 공정 모형을 설명하는 페트리망을 생성합니다.처음에 알고리즘은 풋프린트 매트릭스를 작성합니다.풋프린트 행렬과 위에 표시된 패턴을 사용하여 프로세스 모델을 구성할 수 있습니다.앞에서 설명한 4가지 관계를 바탕으로 풋프린트 기반 매트릭스가 먼저 발견됩니다.풋프린트 베이스의 매트릭스 플레이스를 사용해 검출합니다.각 플레이스는 플레이스 수를 낮게 유지하기 위해 태스크 쌍으로 식별됩니다.

로그 L1의 풋프린트 매트릭스
	a	b	c	d	e
a	#	→	→	#	→
b	←	#		→	#
c	←		#	→	#
d	#	←	←	#	←
e	←	#	#	→	#

$Y_{W}$ W $(\$ 는 $Y_{W}$ 다음과 같은 최대 작업 세트의 모든 쌍 $(A,$ B $(A,B)$ 의 세트입니다.
- A $A\times A$ × $A\times A$ (\ $displaystyle$ A $\times$ A $)$ 와 $A\times A$ $B\times B$ B × $B\times B$ (\ $displaystyle$ B $\times$ B) 모두 $B\times B$ >의 멤버를 포함하지 $A\times A$ .
- $A\times B$ × $A\times B$ (\ $displaystyle$ A $\times$ B $)$ 는 $A\times B$ →의 하위 집합입니다.
$P_{W}$ W $(\$ 에는 $P_W$ $Y_{W}$ W $(\$ 의 $p_{{(A,B)}}$ $Y_{W}$ 멤버에 대해 $p_{(A,B)}$ p $A,$ 와 입력 $i_{W}$ (\ $displaystyle i_{$ W})가 포함됩니다. $W}}$ 및 $i_{W}$ 출력 $o_{W}$ $(\$ $W}}$

흐름 $F_{W}$ $F_{W}$ W $(\$ 는 $F_{W}$ 다음 조합입니다.

$(\displaystyle \{(a,p_{(C,B)})(A,B)\in Y_{W}\wedge a\in A\})$
$(\displaystyle \{(P_{(A,B)},b) (A,B)\in Y_{W}\wedge b\in B\})$
$\displaystyle \{(i_{W},t) t\in T_{I}\}}$
$T_{O}\}의 \{(t,i_{O}) t\displaystyle\}$

그 결과는

a Petri net $\alpha (W)=(P_{W},T_{W},F_{W})$ α ( $\alpha (W)=(P_{W},T_{W},F_{W})$ ) $\alpha (W)=(P_{W},T_{W},F_{W})$ ( $\alpha (W)=(P_{W},T_{W},F_{W})$ , $\alpha (W)=(P_{W},T_{W},F_{W})$ W , $\alpha (W)=(P_{W},T_{W},F_{W})$ ) { $display$ style \ $alpha$ ( W ) = ( $P$ _ { $W$ , $T _$ { $W$ , F _ { $W$ } }
$i_{W}$ $i_{W}$ I W $i_{W}$ {\ $displaystyle i_{$ $W}}$ 및 $i_{W}$ $o_{W}$ 의 출력 $o_{W}$ W $(\$ $W}}$
$T_{W}$ $TW의$ 트랜지션은 $($ F_ ${W})$ $F_{W}$ 에 있기 때문입니다. $i_{W}$ W로부터의 $i_{W}$ ({ $display$ style $i_{$ W}) $o_{W}$ $}$ ~ $o_{W}$ ${\$ $W$ 이것은 확실히 워크플로우넷입니다

위의 예에서, 다음의 페트리 네트는 알파 광산의 적용 결과일 것이다.

특성.

사운드 SWF 네트에 의해 생성된 완전한 워크플로우 로그의 경우 이를 생성하는 넷을 재구성할 수 있음을 알 수 있다.Complete는 $\succ _{W}$ W \ $style \succ$ _ ${W}$ 관계가 $\succ _{W}$ 최대임을 의미합니다.가능한 모든 트레이스가 존재할 필요는 없습니다(루프가 있는 넷의 경우 무한대입니다).

제한 사항

암묵적인 장소:알파 마이너는 암묵적인 장소와 필요한 장소를 구별할 수 없기 때문에 발견된 페트리 ^[4]네트에 불필요한 장소가 추가로 생길 수 있습니다.
루프: 알파 마이너는 프로세스 ^[5]모델에서 길이가 1과 2인 루프를 검색할 수 없습니다.
알파 ^[5]광산에서 로컬 종속성을 놓치는 경우가 많습니다.
표현 편향:알파 마이너는 페트리 네트만 검출할 수 있기 때문에 모든 ^[5]전환에 대해 고유한 가시적 라벨에 대한 요구와 같은 표현적 편견을 추가할 수 있습니다.

레퍼런스

^ Van der Aalst, W M P 및 Weijters, A J M M 및 Maruster, L(2004)."워크플로우 마이닝:이벤트 로그에서 프로세스 모델 검출", IEEE Transactions on Knowledge and Data Engineering, vol 16
^ ^a ^b van der Aalst, W.; Weijters, T.; Maruster, L. (September 2004). "Workflow mining: discovering process models from event logs". IEEE Transactions on Knowledge and Data Engineering. 16 (9): 1128–1142. doi:10.1109/TKDE.2004.47. ISSN 1558-2191.
^ 반 데 알스트 외 2003년
^ "(PDF) Discovering Petri Nets from Event Logs". ResearchGate. Retrieved 2021-08-31.
^ ^a ^b ^c "Limitations of Alpha miner" (PDF). Archived (PDF) from the original on 2021-08-31.

[1] Van der Aalst, W M P 및 Weijters, A J M M 및 Maruster, L(2004)."워크플로우 마이닝:이벤트 로그에서 프로세스 모델 검출", IEEE Transactions on Knowledge and Data Engineering, vol 16

[:02-2] van der Aalst, W.; Weijters, T.; Maruster, L. (September 2004). "Workflow mining: discovering process models from event logs". IEEE Transactions on Knowledge and Data Engineering. 16 (9): 1128–1142. doi:10.1109/TKDE.2004.47. ISSN 1558-2191.

[3] 반 데 알스트 외 2003년

[4] "(PDF) Discovering Petri Nets from Event Logs". ResearchGate. Retrieved 2021-08-31.

[:1-5] "Limitations of Alpha miner" (PDF). Archived (PDF) from the original on 2021-08-31.

[1]

[2]

[4]

[5]

Search