الگوریتم آلفا

الگوریتم α یا α-miner الگوریتمی است که در کاوش فرایند (فرآیندکاوی) استفاده می‌شود و هدف آن بازسازی علت با استفاده از مجموعه‌ای از زنجیره اتفاقات است که اولین بار توسط van der Aalst , Weijters و Măruşter مطرح شد. هدف آلفا ماینر تبدیل گزارش رویداد، که بر اساس ارتباطات میان فعالیت‌های متفاوت انجام می‌پذیرد، به یک گردش کار شبکه محور در گزارش رویداد است. گزارش رویداد مجموعه ای از چندین ردیابی است و یک ردیابی، دنباله ای از اسم‌های هر فعالیت است. از آن زمان تا به حال تعدادی افزونه یا اصلاحاتی ارائه شده‌است که در زیر فهرست می‌شود.

آلفا ماینر اولین الگوریتم کشف فرایند (process discovery) بود که مطرح شد.

و همچنین یک نمای مناسبی از هدف کشف فرایند و اینکه چگونه فعالیت‌های مختلف داخل این فرایند اجرا می‌شوند، ارائه می‌دهد. آلفا ماینر همچنین اساس و پایه توسعه بسیاری از تکنیک‌های کاوش فرایند از جمله heuristic miner و genetic mining است که بر اساس ایده آلفا ماینر ساخته و توسعه داده شده‌است.

توضیح کوتاه

این الگوریتم به عنوان ورودی، یک گزارش گردش کار می‌گیرد ($W\subseteq T^{*}$) که منجر به ایجاد یک شبکه گردش کار می‌شود.

این کار را با بررسی روابط علت و معلولی مشاهده شده در بین کارها انجام می‌دهد. به عنوان نمونه، در هر ردیابی اجرا، یک کار خاص ممکن است همیشه مقدم بر کار خاص دیگری باشد که این، اطلاعات مفیدی را ارائه خواهد داد.

تعاریف استفاده شده

• ردیابی گردش کار یا ردیابی اجرا، رشته ای است بر روی الفبایی از وظایف ($T$)
• گزارش گردش کار مجموعه ای از ردیابی گردش کار است.

گزارش

گزارش رویداد از الزامات اولیه برای به کار بردن هر الگوریتم کشف فرایند است. هر گزارش رویداد متشکل از یک شناسه یکتا برای یک حالت و یک اسم فعالیت (که عمل رخ داده در فرایند و برچسب زمان آن عمل را توصیف می‌کند) است. یک گزارش رویداد را می‌توان به عنوان مجموعه ای از فعالیت‌ها نشان داد.

در مثال زیر برای سادگی، برای نشان دادن یک فعالیت از حروف الفبا استفاده می‌شود. یک نمونه گزارش رویداد را که در شکل زیر نشان داده شده‌است را در نظر بگیرید:

نمونه گزارش رویداد

شناسه مورد	فعالیت	برچسب زمان
۱	A	۲۰۱۹/۱۰/۰۹ ۱۴:۵۰:۱۷٫۰۰۰
۱	B	۲۰۱۹/۱۰/۰۹ ۱۵:۵۰:۱۷٫۰۰۰
۱	C	۲۰۱۹/۱۰/۰۹ ۱۵:۵۶:۱۷٫۰۰۰
۱	D	۲۰۱۹/۱۰/۱۰ ۱۳:۵۰:۱۷٫۰۰۰
۲	A	۲۰۱۹/۱۰/۱۰ ۱۴:۳۰:۱۷٫۰۰۰
۲	C	۲۰۱۹/۱۰/۱۰ ۱۴:۵۰:۱۴٫۰۰۰
۲	B	۲۰۱۹/۱۰/۱۱ ۰۹:۵۰:۱۷٫۰۰۰
۲	D	۲۰۱۹/۱۰/۱۱ ۱۰:۵۰:۱۷٫۰۰۰
۳	A	۲۰۱۹/۱۰/۱۱ ۱۲:۵۰:۱۷٫۰۰۰
۳	E	۲۰۱۹/۱۰/۲۱ ۱۴:۵۰:۱۷٫۰۰۰
۳	D	۲۰۱۹/۱۰/۲۱ ۱۵:۵۰:۱۷٫۰۰۰

یک گزارش رویداد مجموعه ای از چندین ردیابی است و هر ردیابی شامل دنباله ای از فعالیت‌ها است. در نتیجه، یک گزارش رویداد مانند مثال بالا را می‌توان با استفاده از نماد زیر نشان داد:

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

هر گزارش رویداد را می‌توان در مجموعه‌ای از ردیابی‌ها خلاصه کرد، و از چنین ردیابی‌هایی می‌توان برای تقسیم‌بندی روابط بین فعالیت‌های مختلف در فرایند استفاده کرد. بر اساس قوانین آلفا ماینر، فعالیت‌های مربوط به حالت‌های مختلف، می‌توانند ۴ نوع رابطه بینشان داشته باشند:

• جانشینی مستقیم: x > y اگر و تنها اگر رابطه x مستقیماً توسط y دنبال شود. در مثال می‌توانیم در نظر بگیریم که A > B، A > E.
• علیت: x → y اگر و تنها اگر x > y باشد و y > x نباشد. در مثال می‌توانیم A → E را در نظر بگیریم.
• موازی: x || y اگر و تنها اگر x > y و y > x. در مثال داریم B ||C .
• انتخاب: x # y اگر و تنها اگر x > y نباشد و y > x نباشد. در مثال داریم A # D.

الگوها

الگوی توالی: A → B

الگوی تقسیم XOR:

A → B A → C و B # C

الگوی تقسیم AND:

A → B, A → C و B || C

شرح

آلفا ماینر برای ایجاد شبکه پتری که مدل فرایند را توصیف می‌کند، شروع به تبدیل یک گزارش رویداد به روابط مستقیم، دنباله ای، انتخابی و موازی می‌کند. در ابتدا الگوریتم یک ماتریس ردپا را می‌سازد. با استفاده از ماتریس ردپا و الگوی نشان داده شده در بالا، می‌توان یک مدل فرایند ساخت. بر اساس چهار رابطه ایی که قبلاً توضیح داده شد، در ابتدا یک ماتریس مبتنی بر ردپا یافت می‌شود. با استفاده از ماتریس مبتنی بر ردپا، جایگاه‌ها نیز کشف می‌شوند که هر جایگاه برای اینکه تعداد جایگاه‌ها تا حد امکان کم باشد با یک جفت مجموعه وظایف شناسایی می‌شود.

ماتریس رد پای برای لاگ L1

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

• $Y_{W}$ مجموعه تمام جفت‌ها است $(A,B)$ از حداکثر مجموعه وظایف به گونه ای که:
  • هیچ‌کدام از $A\times A$ و $B\times B$ شامل هر عضوی از > نباشند.
  • $A\times B$ زیر مجموعه ای از → است.
• $P_{W}$ شامل یک مکان $p_{(A,B)}$ برای هر عضو $Y_{W}$ ، به علاوه محل ورودی $i_{W}$ و محل خروجی $o_{W}$.

رابطه جریان $F_{W}$ اجتماع موارد زیر است:

• $\{(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}\}$

نتیجه این است:

• ساختار شبکه پتری $\alpha (W)=(P_{W},T_{W},F_{W})$
• با یک محل ورودی $i_{W}$ و یک محل خروجی $o_{W}$
• به خاطر اینکه هر گذار از $T_{W}$ ، روی مسیر $F_{W}$ از $i_{W}$ به $o_{W}$ است، در واقع یک شبکه گردش کار است.

برای مثال داده شده در بالا، شبکه پتری زیر حاصل کاربرد آلفا ماینر است.

خواص

می‌توان نشان داد که شبکه تولیدکننده یک گزارش گردش کار کامل که توسط یک شبکه SWF صدا تولید می‌شود، می‌تواند بازسازی شود. کامل در اینجا به این معنی است که رابطه $\succ _{W}$ حداکثر است. لازم نیست که همه ردیابی‌های ممکن نمایش داده شود (که برای یک شبکه با یک حلقه بی‌نهایت خواهد بود).

محدودیت‌ها

• مکان‌های ضمنی: آلفا ماینر نمی‌تواند بین مکان‌های ضمنی و مکان‌های مورد نیاز تمایز قائل شود و در نتیجه ممکن است مکان‌های غیر ضروری اضافی را در شبکه پتری به وجود آمده ایجاد کند.
• حلقه‌ها: آلفا ماینر نمی‌تواند حلقه‌هایی به طول ۱ و ۲ را در مدل فرایند کشف کند.
• وابستگی‌های محلی اغلب در آلفا ماینر نادیده گرفته می‌شوند.
• سوگیری بازنمایی: آلفا ماینر فقط می‌تواند شبکه پتری را کشف کند، بنابراین برای هر انتقال سوگیری بازنمایی را (مانند نیاز به برچسب‌های قابل مشاهده یکتا) را اضافه می‌کند.