Alfa algoritm

α-algoritmen eller α -miner är en algoritm som används i process mining , som syftar till att rekonstruera kausalitet från en uppsättning sekvenser av händelser . Det lades först fram av van der Aalst , Weijters och Măruşter. Målet med Alpha miner är att konvertera händelseloggen till ett arbetsflödesnät baserat på relationerna mellan olika aktiviteter i händelseloggen. En händelselogg är en multi-uppsättning spår, och en spårning är en sekvens av aktivitetsnamn. Flera tillägg eller modifieringar av den har sedan dess presenterats, vilka kommer att listas nedan.

Alpha miner var den första processupptäcktsalgoritm som någonsin föreslagits, och den ger en bra översikt över syftet med processupptäckt och hur olika aktiviteter inom processen utförs. Alpha miner var också grunden för utvecklingen av många andra process miner tekniker såsom heuristic miner , genetisk mining utvecklades utifrån idén alpha miner är byggd på.

Kort beskrivning

Algoritmen tar en arbetsflödeslogg $W\subseteq T^{*}$ som indata och resulterar i att ett arbetsflödesnät konstrueras.

Det gör det genom att undersöka orsakssamband som observeras mellan uppgifter. Till exempel kan en specifik uppgift alltid föregå en annan specifik uppgift i varje exekveringsspårning, vilket skulle vara användbar information.

Definitioner som används

• En arbetsflödesspårning eller exekveringsspårning är en sträng över ett alfabet $T$ av uppgifter .
• En arbetsflödeslogg är en uppsättning arbetsflödesspårningar.

Händelselogg

Händelselogg är det primära kravet för att tillämpa någon processupptäcktsalgoritm. En händelselogg består av en unik identifierare för ett ärende, aktivitetsnamn som beskriver åtgärden som inträffar i processen och tidsstämpel. En händelselogg kan representeras som en multi-uppsättning av aktiviteter. För enkelhetens skull skulle följande exempel använda alfabetisk bokstav för att representera en aktivitet. Betrakta ett exempel på en händelselogg som visas i följande figur:

Exempel på händelselogg

Ärende ID	Aktivitet	Tidsstämpel
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

En händelselogg är en multiuppsättning spår, och en spårning är en sekvens av aktiviteter. Således kan en händelselogg som ovan representeras med hjälp av följande notation:

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

Varje händelselogg kan kokas ner till en multi-uppsättning spår, och sådana spår kan användas ytterligare för att bryta ner relationer mellan olika aktiviteter i processen. Enligt reglerna för alpha miner kan aktiviteter som hör till olika fall ha fyra typer av relationer mellan dem:

• Direkt succession: x > y om och endast om någon relation x direkt följer av y. I vårt exempel kan vi anse att A > B , A > E , A > C.
• Kausalitet: x → y iff x > y och inte y > x. I vårt exempel kan vi anse att A → E.
• Parallell: x || y iff x > y och y > x. I vårt exempel har vi B || C.
• Val: x # y om inte(x > y) och inte(y > x). I vårt exempel har vi A # D.

Mönster

Sekvensmönster: A → B XOR-delat mönster: A → B, A → C och B # C

OCH-delat mönster: A → B, A → C och B || C

Beskrivning

Alfamineraren börjar med att konvertera en händelselogg till direktföljande, sekvens-, parallell- och valrelationer och använda dem för att skapa ett petrinät som beskriver processmodellen. Inledningsvis konstruerar algoritmen en fotavtrycksmatris. Med hjälp av fotavtrycksmatrisen och det ovan visade mönstret kan man konstruera en processmodell. Baserat på de fyra relationerna som beskrivits tidigare upptäcks först en fotavtrycksbaserad matris. Med hjälp av den fotavtrycksbaserade matrisen upptäcks platser. Varje plats identifieras med ett par uppsättningar uppgifter, för att hålla antalet platser lågt.

Footprint-matris för loggen L1

	a	b	c	d	e
a	#	→	→	#	→
b	←	#	||	→	#
c	←	||	#	→	#
d	#	←	←	#	←
e	←	#	#	→	#

• $Y_{W}$ är mängden av alla par $(A,B)$ av maximala uppsättningar av uppgifter så att
  • Varken $A\times A$ och $B\times B$ innehåller några medlemmar av > och
  • $A\times B$ är en delmängd av →
• $P_{W}$ innehåller en plats $p_{(A,B)}$ för varje medlem av $Y_{W}$ plus inmatningsplatsen $i_{W}$ och utgångsplatsen $o_{W}$

Flödesrelationen $F_{W}$ är föreningen av följande:

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

Resultatet är

• a Petri nätstruktur ${\displaystyle \alpha (W)=(P_{W},T_{W},F_{W})$
• med en ingångsplats $i_{W}$ och en utmatningsplats $o_{W}$
• eftersom varje övergång av $T_{W}$ är på en $F_{W}$ -väg från $i_{W}$ till $o_{W}$ , det är verkligen ett arbetsflödesnät.

För exemplet ovan skulle följande petrinet vara resultatet av tillämpningen av alpha miner.

Egenskaper

Det kan visas att i fallet med en komplett arbetsflödeslogg genererad av ett sundt SWF-nät, kan nätet som genererar den rekonstrueras. Komplett betyder att dess $\succ _{W}$ relation är maximal. Det inte att alla möjliga spår finns (vilket skulle vara oändligt för ett nät med en slinga).

Begränsningar

• Implicita platser: Alpha Miner kan inte skilja mellan implicita och nödvändiga platser och kan därför resultera i ytterligare icke nödvändiga platser i det upptäckta petrinetet.
• Slingor: Alpha Miner kan inte upptäcka slingor av längden 1 och 2 i processmodellen.
• Lokala beroenden saknas ofta i alpha miner.
• Representationsbias: Alpha Miner kan bara upptäcka petrinet och lägga till representationsbias som krav på unika synliga etiketter för varje övergång.