کشف فرآیند ها (قسمت اول)

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

الگوریتم آلفا به‌عنوان یکی از پایه‌ای‌ترین الگوریتم‌های کشف فرآیند ارائه می‌شود. این رویکرد محدودیت‌های زیادی دارد، اما ایده کشف محدودیت‌های محلی را به‌خوبی معرفی می‌کند. الگوریتم پایه‌ای Inductive Miner به‌عنوان نمونه‌ای از تکنیک‌های از بالابه‌پایین ارائه شده است. این رویکرد، همراه با فیلتر مبتنی بر فراوانی، در اکثر گزارش‌های رویداد به‌خوبی کار می‌کند. این الگوریتم‌ها به‌عنوان‌مثال‌هایی برای نشان‌دادن مبانی کشف فرآیند استفاده می‌شوند.

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

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

شکل 1) چارچوب کلی فرآیند‌کاوی: در این مقاله فقط روی گام 1 تمرکز می‌کنیم

رویدادها ممکن است ویژگی‌های زیادی داشته باشند و به چندین شی (Object) از انواع مختلف اشاره کنند. بااین‌حال، در این مقاله، از داده‌های رویداد بسیار ابتدایی شروع می‌کنیم. ما فرض می‌کنیم که هر گزارش رویداد دارای یک نمونه اجرا (Case)، یک فعالیت (Activity) و اطلاعات زمانی (Timestamp)  است. ممکن است بسیاری از ویژگی‌های دیگر (به‌عنوان‌مثال، منبع) وجود داشته باشد، اما ما آنها را نادیده می‌گیریم. در ابتدا، ما فرض می‌کنیم که اطلاعات زمانی فقط برای ترتیب رویدادهای مربوط به یک نمونه اجرا استفاده می‌شوند. این به این معنی است که هر نمونه اجرا با دنباله‌ای از فعالیت‌ها نشان داده می‌شود. ما به این دنباله از فعالیت‌ها Trace می‌گوییم. به‌عنوان‌مثال دنباله نشان دهنده یک نمونه اجرای فرآیند است که فعالیت هایa، b، c و e  در آن رخ داده است. توجه داشته باشید که ممکن است نمونه اجراهای زیادی از فرآیند وجود داشته باشد که دارای همان دنباله است.

بنابراین، ما یک گزارش رویداد را به‌عنوان چند مجموعه‌ای (Multiset) از دنباله‌ها نشان می‌دهیم. برای مثال در مجموعه،  یک گزارش رویداد است که 16 نمونه اجرا داشته و 63 رویداد را توصیف می کند. توجه داشته باشید که دنباله 10بار ظاهر می شود. در ابتدا ما از اصطلاح رویداد ساده شده استفاده کردیم. در اینجا صفت «ساده‌شده» را حذف می‌کنیم تا ادبیات ساده‌تری در سراسر مقاله استفاده شود.

برای مطالعه بیشتر در مورد مفهوم و انواع گزارش رویداد به مقاله گزارش رویداد مراجعه کنید

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

شکل 2 یک Directly Follows Graph (DFG) را نشان می‌دهد. شروع، پایان و پنج فعالیت گره‌های گراف هستند. فعالیت‌های aو  16e  بار، b و 15c بار و d فقط یک بار رخ داده است. کمان‌های شکل 2 نشان می‌دهند که هر چند وقت یک‌بار یک فعالیت مستقیماً با فعالیت دیگری دنبال می‌شود. به عنوان مثال، 10b بار مستقیماً بعد از a ، c و5بار مستقیما بعد از a، و d یک بار مستقیماً بعد a قرار گرفته است. برای نشان دادن شروع و انتهای نمونه اجرا، از یک گره شروع و یک گره پایان استفاده می کنیم. می توان فعالیت ها یا حالت های «ساختگی» را مشاهده کرد. اگرچه آنها فعالیت های واقعی را ارائه نمی کنند، اما برای توصیف مناسب فرآیند مورد نیاز هستند. از آنجایی که همه 16 مورد با  شروع می شوند، کمان اتصال به  دارای فراوانی 16 است. توجه داشته باشید که به دلیل چرخه های موجود در DFG، دنباله‌ای مانند a، b، c، b، c، b، c، b، e نیز وجود دارد. طبق DFG ممکن است (اما در گزارش رویداد ظاهر نشده است).

شکل 2) یک مدل فرآیندی DFG کشف شده از گزارش رویداد

شکل 3 یک شبکه پتری (Petrinet) را نشان می‌دهد که با استفاده از همان گزارش رویداد  کشف شده است. Transition یا گذار ‌ها (یعنی مربع ها) با پنج فعالیت در گزارش رویداد مطابقت دارند. مکان ها (یعنی دایره ها) رفتار را محدود می کنند. شبکه پتری اجازه وقوع 3 دنباله را در گزارش رویداد می دهد و نه بیشتر. در ابتدا، فقط انتقال  قابل انجام است. هنگامی که یک شلیک رخ می دهد (یعنی فعال شدن یا وقوع یک فعالیت)، یک توکن از محل ورودی مصرف می شود و یک توکن برای هر یک از دو مکان خروجی تولید می شود. در نتیجه، گذار های ،  و  قابل انجام هستند. اگر  فعال شود، هر دو توکن حذف می شوند و دو توکن برای مکان های ورودی  تولید می شود. اگر  فعال شود، فقط یک توکن  مصرف می شود و یک توکن تولید می شود. بعد از فعال شدن ،  همچنان قابل فعال شدن است و  برای به کار انداختن  فعال می شود. گذار  نیز می تواند قبل از  اتفاق بیفتد، یعنی  و  همزمان باشند و می توانند در یک زمان یا به هر ترتیبی اتفاق بیفتند. بین  و ترکیب  و  یک انتخاب وجود دارد. یعنی یا فعالیت   و یا  و  اتفاق می‌افتد. شروع فرآیند با توکن در محل منبع مدل سازی می شود و انتهای فرآیند توسط محل انتهایی که دارای حاشیه دو خطی است مدل‌سازی می‌شود.

شکل 3) شبکه پتری کشف شده از گزارش رویداد

همچنین درخت فرآیندی کشف شده از گزارش رویداد  که در شکل 4 نمایش داده شده است تنها به 3 دنباله اجازه وقوع می‌دهد. گره ریشه یک توالی ( → ) را با 3 فرزند (Child) نمایش می‌دهد. این 3 فرزند عبارتنداز فعالیت  ، یک انتخاب و فعالیت  . این گره‌ها بار دیده شده‌اند (یک بار به ازای هر نمونه ااجرا) . گره انتخاب (×) 2 گره فرزند دارد یک گره موازی (⋀) و فعالیت . گره موازی (⋀) دو فرزند دارد فعالیت  و فعالیت  .

دقت کنید که گره  فقط یک بار دیده شده است اما گره‌های ⋀، b و  15 بار دیده شده‌اند. در این مثال هر گره درخت یک برچسب منحصر به فرد دارد اما در مثال‌های پیشرفته‌تر می‌تواند اینطور نباشد.

شکل 4) درخت فرآیند کشف شده از گزارش رویداد

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