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

ردپای دیجیتال :

یک  DFG همان‌طور که در جدول 1 نمایش داده شده است می‌تواند در قالب یک ماتریس ارائه شود. این یک نمایش جدولی از یک گراف است. همان طور که مشخص است چون در این گراف هیچ فعالیتی تکرار نشده بنابراین فراوانی کمان‌ها روی قطر اصلی صفر است. اما فراوانی بین دو فعالیت c و e  10 است که بدین معنی است که 10 بار بعد از فعالیت c فعالیت e انجام شده است. برای در نظر گرفتن رابطه بین فعالیت‌ها (بدون در نظر گرفتن تکرار وقوع) می‌توانیم یک ماتریس ردپا ایجاد کنیم. جدول 2 ماتریس DFG در شکل 1 را نمایش می‌دهد.

جدول 1) ارائه ماتریسی DFG شکل 1

شکل1) DFG

بین دو فعالیت a و b یکی از 4 رابطه می‌تواند برقرار باشد

• a→b این رابطه بدین معناست که b برخی مواقع بعد از a قرار می‌گیرد اما برعکس آن اتفاق نمی افتد
• b→a این رابطه بدین معناست که a برخی مواقع بعد از b قرار می‌گیرد اما برعکس آن اتفاق نمی افتد
• a||b این رابطه بدین معناست که گاهی a بعد از b و گاهی b بعد از a قرار گرفته است
• a#b این رابطه بدین معناست که a و b هیچ گاه مستقیما بعد از هم قرار نگرفته‌اند

به ماتریسی که از قراردادن رابطه بین هر دو فعالیت حاصل می‌شود ماتریس ردپا می‌گویند.

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

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

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

ایده پایه‌ای :

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

الگوریتم α، گزارش رویداد را برای یافتن الگوهای خاص بیان شده در قسمت قبل اسکن می کند. به عنوان مثال، اگر فعالیت  b بعد از فعالیت a  قرار گیرد اما a هرگز بعد b قرار نگیرد، در این صورت فرض می شود که بین a و b وابستگی علی وجود دارد. برای انعکاس این وابستگی، شبکه پتری مربوطه باید مکانی داشته باشد که a به b را متصل می کند.

الگوریتم :

گام1 : گزارش رویداد را چک کنید هر فعالیتی در گزارش بود را به عنوان گذار (Transition) در شبکه پتری قرار دهید.

گام2: فعالیت‌هایی که دنباله‌ها در گزارش رویداد با آن فعالیت‌ها شروع شده‌اند را مشخص کرده و در ابتدای شبکه قرار دهید

گام3 : فعالیت‌هایی که دنباله‌ها در گزارشرویداد با آن‌ها تمام شده‌اند را مشخص کرده و در انتهای شبکه قرار دهید.

گام4: این گام هسته اصلی الگوریتم آلفا را تشکیل می‌دهد. در این گام مکان‌های  (Place) شبکه را ایجاد می‌کنیم و باید ورودی و خروجی کمان‌های این مکان‌ها را مشخص کنیم برای درک بیشتر شکل 2 را در نظر بگیرید

شکل2) مکان بالا که با دایره ای با نام P(A,B) مشخص شده است فعالیت‌های سمت چپ را به فعالیت‌های سمت راست متصل کرده

در واقع تمامی مولفه‌های مجموعه سمت چپ یعنی A باید رابطه از نوع علی () با تمامی مولفه های‌ مجموعه B داشته باشند و همچنین فعالیت‌های مجموعه A نباید هرگز همدیگر را دنبال کنند یعنی رابطه بین هر دو فعالیت در مجموعه A بایستی  باشد. بنابراین چالش در این قسمت تشکیل دو مجموعه A و B به نحوی است که فعالیت‌های A فعالیت‌های B را دنبال کنند و فعالیت‌های خودشان را دنبال نکنند.

برای شفاف تر شدن هرچه بیشتر به مثال زیر دقت کنید. گزارش رویداد زیر را در نظر بگیرید

به طور واضح اگر دو مجموعه A={a} و B={b,e} را در نظربگیریم پیش‌نیاز‌هایی که ذکر کردیم را دارند یعنی b و e هردو پس از فعالیت a قرار گرفته‌اند و نیز هیچگاه b و e همدیگر را دنبال نکرده‌اند. همچنین A={a} و B={b} نیز این شرایط را دارند مجموعه زیر تمام جفت فعالیت‌های مربوط به گزارش رویداد  را که شرایط گام 4 را دارند یک جا قرار داده است

اما دقت کنید اگر بخواهیم به ازای هر جفت فعالیت‌های بالا یک مکان قرار دهیم تعداد مکان‌ها بسیار زیاد می‌شود بنابراین بسیار حائز اهمیت است که «جفت‌های بیشینه» را در نظر بگیریم برای مثال اگر رابطه بین A={a} و B={b,e} وجود دارد و نیز همین رابطه بین A={a} و B={b} وجود دارد ما تنها جفت اول که بیشینه است را در نظر می‌گیریم.

برای مثال مجموعه بالا با در نظرگیری تنها جفت‌های بیشینه به مجموعه زیر تبدیل می‌شود

گام 5 : مجموعه شامل جفت‌های بیشینه مشابه مجموعه بالا از فعالیت‌ها ایجاد کنید.

گام6: به ازای شروع و پایان و تمام اعضای مجموعه Y یک مکان در شبکه ایجاد کنید.

گام7: به هر فعالیت شروع یک کمان از ابتدا و از هر فعالیت پایان یک کمان به انتهای شبکه وصل کنید و نیز به ازای تمام مکان‌های ایجاد شده در گام قبل فعالیت‌های مجموعه A  را به مکان‌ها وصل و به فعالیت‌های مجموعه B از مکان‌ها کمان وصل کنید

به مثال زیر دقت کنید :

گزارش رویداد زیر را در نظر بگیرید

به همین ترتیب مدل فرآیندی ایجاد شده به شکل زیر است

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

محدودیت‌های الگوریتم آلفا :

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

یکی دیگر از مشکلات الگوریتم آلفا عدم تضمین برای کشف مدل‌های فرآیندی Sound است. این مبحث به همراه معیار‌های ارزیابی کیفیت مدل‌های فرآیندی در مقاله بعدی شرح داده خواهد شد. اما محدودیت قابل توجه دیگر الگوریتم آلفا ناتوانی در مدیریت «وابستگی‌های غیر محلی» است.

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

جمع‌بندی :

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

در مقاله بعدی به بررسی نحوه ارزیابی مدل‌های کشف شده توسط این الگوریتم‌ها می‌پردازیم.