Algorytm alfa

Algorytm α lub α-górnik to algorytm stosowany w eksploracji procesów , mający na celu odtworzenie przyczynowości ze zbioru sekwencji zdarzeń . Po raz pierwszy wysunęli go van der Aalst , Weijters i Măruşter. Celem Alpha Miner jest przekształcenie dziennika zdarzeń w sieć przepływu pracy w oparciu o relacje między różnymi działaniami w dzienniku zdarzeń. Dziennik zdarzeń to wiele zestawów śladów, a ślad to sekwencja nazw działań. Od tego czasu zaprezentowano kilka jego rozszerzeń lub modyfikacji, które zostaną wymienione poniżej.

Alpha Miner był pierwszym algorytmem wykrywania procesów, jaki kiedykolwiek zaproponowano, i daje dobry przegląd celu odkrywania procesów i sposobu wykonywania różnych działań w ramach procesu. Alpha Miner był również podstawą do rozwoju wielu innych technik eksploracji procesów, takich jak koparka heurystyczna , eksploracja genetyczna została opracowana w oparciu o ideę, na której zbudowany jest alfa górnik.

Krótki opis

Algorytm przyjmuje dziennik przepływu pracy $dane$ wejściowe i tworzy sieć

Czyni to poprzez badanie związków przyczynowych obserwowanych między zadaniami. Na przykład jedno określone zadanie może zawsze poprzedzać inne określone zadanie w każdym śledzeniu wykonania, co byłoby przydatną informacją.

Zastosowane definicje

Ślad przepływu pracy lub $ślad$ wykonania to ciąg znaków nad alfabetem zadań
Dziennik przepływu pracy to zestaw śladów przepływu pracy.

Dziennik zdarzeń

Dziennik zdarzeń jest podstawowym wymogiem zastosowania dowolnego algorytmu wykrywania procesów. Dziennik zdarzeń składa się z unikalnego identyfikatora sprawy, nazwy czynności opisującej akcję występującą w procesie oraz znacznika czasu. Dziennik zdarzeń może być reprezentowany jako wiele zestawów działań. Dla uproszczenia w poniższym przykładzie do reprezentowania czynności użyto litery alfabetu. Rozważmy przykładowy dziennik zdarzeń pokazany na poniższym rysunku:

Przykładowy dziennik zdarzeń
ID sprawy	Działalność	Znak czasu
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	mi	2019/10/21 14:50:17.000
3	D	2019/10/21 15:50:17.000

Dziennik zdarzeń to wiele zestawów śladów, a ślad to sekwencja działań. Zatem dziennik zdarzeń, taki jak powyżej, można przedstawić za pomocą następującej notacji:

${\ Displaystyle L1 = [<A, B, C, D>, <A ,C,B,D>,<A,E,D>]}$

Każdy dziennik zdarzeń można sprowadzić do wielu zestawów śladów, które następnie można wykorzystać do rozbicia relacji między różnymi działaniami w procesie. Zgodnie z zasadami Alpha Miner, czynności należące do różnych przypadków mogą mieć między sobą 4 rodzaje relacji:

Sukcesja bezpośrednia: x > y wtedy i tylko wtedy, gdy po jakiejś relacji bezpośrednio następuje y. W naszym przykładzie możemy przyjąć, że A > B , A > E , A > C.
Przyczynowość: x → y iff x > y, a nie y > x. W naszym przykładzie możemy uznać, że A → E.
Równolegle: x || y jeśli x > y i y > x. W naszym przykładzie mamy B || C.
Wybór: x # y jeśli nie(x > y) i nie(y > x). W naszym przykładzie mamy A#D.

Wzory

Wzorzec sekwencji: A → B Wzorzec podziału XOR: A → B, A → C i B#C

Wzór z podziałem AND: A → B, A → C i B || C

Opis

Alpha górnik zaczyna od przekształcenia dziennika zdarzeń w relacje bezpośredniego śledzenia, sekwencji, równoległości i wyboru, a następnie wykorzystania ich do stworzenia sieci Petriego opisującej model procesu. Początkowo algorytm konstruuje macierz śladu. Wykorzystując macierz śladu i przedstawiony powyżej wzór, można zbudować model procesu. Na podstawie czterech opisanych wcześniej relacji najpierw odkrywana jest macierz oparta na śladzie. Używając matrycy opartej na śladzie, odkrywane są miejsca. Każde miejsce jest identyfikowane za pomocą pary zestawów zadań, aby liczba miejsc była niska.

Macierz śladu dla dziennika L1
	A	B	C	D	mi
A	#	→	→	#	→
B	←	#	\|\|	→	#
C	←	\|\|	#	→	#
D	#	←	←	#	←
mi	←	#	#	→	#

${\ Displaystyle Y_ {W}}$ $Y_{W}$ to zbiór wszystkich par maksymalnych zestawów zadań ${\ Displaystyle (A, B)}$ $(A,B)$
- Ani $\ razy A}$ i ${\ Displaystyle B \ razy B}$ nie zawierają żadnych członków > i
- ${\ Displaystyle A \ razy B}$ jest podzbiorem →
${\ Displaystyle P_ {W}}$ zawiera jedno miejsce dla każdego członka ${\ Displaystyle Y_ {W}$ $}$ plus miejsce wejściowe ${\ Displaystyle i_ {W}}$ i miejsce wyjściowe ${\ Displaystyle o_ {W}}$

Relacja przepływu jest połączeniem następujących elementów: ${\ displaystyle F_ {W}}$

${\ Displaystyle \ {(a, p_ {(C, B)}} | (A, B) \ w Y_ {W} \ klin a \ w A \} }$
${\ Displaystyle \ {(p_ {(A, B)}, b) | (A, B) \ w Y_ {W} \ klin b \ w B \} }$
${\ Displaystyle \ {(i_ {W}, t) | t \ w T_ {I} \}}$
${\ Displaystyle \ {(t, i_ {O}) | t \ w T_ {O} \}}$

Wynik to

za Struktura sieci Petriego ${\ Displaystyle \ alfa (W) = (P_ {W}, T_ {W}, F_ {W})}$
z jednym miejscem wejściowym $o$ miejscem wyjściowym $\ Displaystyle o_ {W}}$
ponieważ każde przejście jest na $}$ - od $W}$ do ${\ displaystyle o_ {W}}$ $}$ ${\ displaystyle T_ {W}$ , jest to rzeczywiście sieć przepływu pracy.

Dla powyższego przykładu następująca sieć Petriego byłaby wypadkową zastosowania Alpha Miner.

Nieruchomości

Można wykazać, że w przypadku kompletnego dziennika przepływu pracy wygenerowanego przez solidną sieć SWF, sieć, która go generuje, może zostać zrekonstruowana. Kompletny oznacza, że jego $relacja$ . Nie jest wymagane, aby wszystkie możliwe ślady były obecne (co byłoby policzalnie nieskończone dla sieci z pętlą).

Ograniczenia

Niejawne miejsca: Alpha Miner nie może rozróżnić niejawnych i wymaganych miejsc, co może skutkować dodatkowymi niewymaganymi miejscami w odkrytej sieci Petriego.
Pętle: Alpha Miner nie może wykryć pętli o długości 1 i 2 w modelu procesu.
Lokalne zależności są często pomijane w Alpha Miner.
Odchylenie reprezentatywne: górnik Alpha może odkryć tylko sieć Petriego, dodając w ten sposób odchylenie reprezentatywne, takie jak wymóg umieszczania unikalnych widocznych etykiet dla każdego przejścia.