• صفحه اصلی
  • ارائه یک روش سریع و دقیق برای شناسایی رانش مفهوم با تحلیل سابقه‌ی رویدادها

اشتراک گذاری

آدرس مقاله


کد مقاله : 2020042613598 بازدید : 10128 صفحه: 105 - 117

20.1001.1.27170414.1399.12.43.7.8

نوع مقاله: پژوهشی

ارائه یک روش سریع و دقیق برای شناسایی رانش مفهوم با تحلیل سابقه‌ی رویدادها

محورهای موضوعی : عمومى

مهدی یعقوبی 1 * , علی سبطی 2 , سهیلا کرباسی 3

1 - گروه مهندسی کامپیوتر، دانشکده فنی مهندسی گرگان، دانشگاه گلستان، گرگان
2 - گروه مهندسی کامپیوتر، دانشکده فنی مهندسی گرگان، دانشگاه گلستان، گرگان
3 - استادیار

تاریخ دریافت : 1399/02/07 تاریخ پذیرش : 1399/10/17 تاریخ انتشار : 1399/07/30

کلید واژه: مدیریت فرآیندهای کسب و کار, شناسایی تغییرات در فرآیند, رانش مفهوم, فرآیندکاوی ,

چکیده مقاله :

در سازمان ها و شرکت های بزرگ که از سیستم های مدیریت فرآیندهای کسب و کار (BPMS) بهره می برند، در هر لحظه با توجه به قوانین بالادستی و شرایط بازار، ممکن است در فرآیندهای کسب و کار تغییرات رخ دهد. این تغییرات گاهی به صورت آنی و گاهی به صورت تدریجی روی سیستم اعمال می گردد. شناسایی به موقع این تغییرات می تواند در تصمیم گیری بهتر مدیران سازمان اثر گذار باشد. تجزیه و تحلیل سابقه ی رویدادها در این سیستم ها، امکان شناسایی تغییرات ایجاد شده در فرآیندهای کسب و کار را به صورت خودکار فراهم می کند. به این تغییرات در فرآیندها به اصطلاح رانش مفهوم در فرآیند کسب و کار گفته می شود. استخراج رانش مفهوم اشاره دارد به شناسایی محل و نوع تغییراتی که در طول زمان در فرآیندهای کسب و کار یا به طور کلی در سابقه‌ی روبداد رخ داده است. در این مقاله یک روش ابتکاری با معرفی یک تابع فاصله اصلاح شده، برای شناسایی محل و زمان ایجاد رانش مفهوم ارائه می-شود. آزمایش های انجام شده بر روی 72 پایگاه دادِگان موجود در پیشینه ی پژوهش که شامل 648 رانش مفهوم در 12 نوع مختلف است، نشان می دهد روش پیشنهادی 18/98 درصد از رانش ها را تشخیص می‌دهد درحالی که روش پیشنهادی نسبت به بهترین روش موجود بسیار سریع‌تر است.

چکیده انگلیسی:

In organizations and large companies that are using business process management systems (BPMSs), process model can change due to upstream laws, market conditions. BPMSs have flexible to these changes. Effect of these change are saved in storage devises and event logs; these changes are sometimes applied suddenly or gradually on the event logs. Changing the season or starting a new financial term can be a factor to make these changes. This change is called concept drift in business process model. On time detection and recognition of process concept drift can affect the decision making of managers and administrations of systems. An analysis of the event logs in BPMS allows the automatic detection of the concept drift. This paper presents an innovative method by introducing a modified distance function to identify the concept drift. Experimental results were performed on 72 datasets in the research history, which included 648 concept drifts in 12 different types. It shows that the proposed method detects 98.18% of the drifts, while the proposed method is much faster than other state of the art methods.

منابع و مأخذ:

W. M. P. van der Aalst, Process Mining: Discovery, Conformance and Enhancement of Business Processes. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011.
2. R. P. J. C. Bose, W. M. P. van der Aalst, I. . Žliobait\.e, and M. Pechenizkiy, “Handling concept drift in process mining,” in International Conference on Advanced Information Systems Engineering, 2011, pp. 391–405.
3. A. Tsymbal, M. Pechenizkiy, P. Cunningham, and S. Puuronen, “Handling local concept drift with dynamic integration of classifiers: Domain of antibiotic resistance in nosocomial infections,” in 19th IEEE Symposium on Computer-Based Medical Systems (CBMS’06), 2006, pp. 679–684.
4. M. Pechenizkiy, J. Bakker, I. Žliobaitė, A. Ivannikov, and T. Kärkkäinen, “Online mass flow prediction in CFB boilers with explicit detection of sudden concept drift,” ACM SIGKDD Explor. Newsl., vol. 11, no. 2, pp. 109–116, 2010.
5. M. Van Leeuwen and A. Siebes, “Streamkrimp: Detecting change in data streams,” in Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2008, pp. 672–687.
6. D. Brzezinski and J. Stefanowski, “Reacting to different types of concept drift: The accuracy updated ensemble algorithm,” IEEE Trans. Neural Networks Learn. Syst., vol. 25, no. 1, pp. 81–94, 2014.
7. A. Maaradji, M. Dumas, M. La Rosa, and A. Ostovar, “Fast and accurate business process drift detection,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 9253, pp. 406–422, 2015.
8. M. Reichert, C. Hensinger, and P. Dadam, “Supporting adaptive workflows in advanced application environments,” 1998.
9. S. Rinderle, M. Reichert, and P. Dadam, “Correctness criteria for dynamic changes in workflow systems, a survey,” Data Knowl. Eng., vol. 50, no. 1, pp. 9–34, 2004.
10. A. Adriansyah et al., “Process mining manifesto,” 2012.
11. R. Accorsi and T. Stocker, “Discovering workflow changes with time-based trace clustering,” in International Symposium on Data-Driven Process Discovery and Analysis, 2011, pp. 154–168.
12. J. Carmona and R. Gavalda, “Online techniques for dealing with concept drift in process mining,” in International Symposium on Intelligent Data Analysis, 2012, pp. 90–102.
13. A. Ostovar, S. J. J. Leemans, and M. La Rosa, “Robust drift characterization from event streams of business processes,” ACM Trans. Knowl. Discov. from Data, vol. 14, no. 3, pp. 1–57, 2020.
14. J. Martjushev, R. P. J. C. Bose, and W. M. P. van der Aalst, “Change point detection and dealing with gradual and multi-order dynamics in process mining,” in International Conference on Business Informatics Research, 2015, pp. 161–178.
15. C. W. Günther, S. Rinderle, M. Reichert, and W. Van Der Aalst, “Change mining in adaptive process management systems,” in OTM Confederated International Conferences" On the Move to Meaningful Internet Systems", 2006, pp. 309–326.
16. R. P. J. C. Bose, W. M. P. Van Der Aalst, I. . Žliobait\.e, and M. Pechenizkiy, “Dealing with concept drifts in process mining,” IEEE Trans. neural networks Learn. Syst., vol. 25, no. 1, pp. 154–171, 2014.
17. A. Seeliger, T. Nolle, and M. Mühlhäuser, “Detecting Concept Drift in Processes using Graph Metrics on Process Graphs,” pp. 1–10, 2017.
18. A. Ostovar, M. Abderrahmane, M. La Rosa, A. H. ter Hofstede, and B. F. van Dongen., “Detecting drift from event streams of unpredictable business processes,” in International Conference on Conceptual Modeling, 2016, pp. 330–346.
19. R. Accorsi and T. Stocker, “Discovering workflow changes with time-based trace clustering,” in International Symposium on Data-Driven Process Discovery and Analysis, 2011, pp. 154–168.
20. B. Hompes, J. C. A. M. Buijs, W. M. P. van der Aalst, P. Dixit, and H. Buurman, “Detecting Change in Processes Using Comparative Trace Clustering.,” in SIMPDA, 2015, pp. 95–108.
21. Y. Xie, C. F. Chien, and R. Z. Tang, “A dynamic task assignment approach based on individual worklists for minimizing the cycle time of business processes,” Comput. Ind. Eng., vol. 99, no. 12, pp. 401–414, 2016.
22. A. Maaradji, M. Dumas, M. La Rosa, and A. Ostovar, “Detecting sudden and gradual drifts in business processes from execution traces,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 10, pp. 2140–2154, 2017.
متن کامل:


 

دو فصلنامه علمي

فناوري اطلاعات و ارتباطات ایران

سال دوازدهم، شماره‌هاي 43 و 44، بهار و تابستان 1399

صص: 105_117

E:\E Drive\logo\iicta Logo0.JPG 

ارائه یک روش سریع و دقیق برای شناسایی رانش مفهوم با تحلیل سابقه‌ی رویدادها

مهدی یعقوبی*        علی سبطی*        سهیلا کرباسی*

*استادیار گروه مهندسی کامپیوتر، دانشکده فنی مهندسی گرگان، دانشگاه گلستان، گرگان

تاریخ دریافت: 07/02/1399                         تاریخ پذیرش: 24/08/1399

نوع مقاله: پژوهشی

چکیده

در سازمان­ها و شرکت­های بزرگ که از سیستم­های مدیریت فرآیندهای کسب و کار (BPMS) بهره می­برند، در هر لحظه با توجه به قوانین بالادستی و شرایط بازار، ممکن است در فرآیندهای کسب و کار تغییرات رخ دهد. این تغییرات گاهی به صورت آنی و گاهی به صورت تدریجی روی سیستم اعمال می­گردد. شناسایی به موقع این تغییرات می­تواند در تصمیم­گیری بهتر مدیران سازمان اثر گذار باشد. تجزیه و تحلیل سابقه­ی رویدادها در این سیستم­ها، امکان شناسایی تغییرات ایجاد شده در فرآیندهای کسب و کار را به صورت خودکار فراهم می­کند. به این تغییرات در فرآیندها به اصطلاح رانش مفهوم در فرآیند کسب و کار گفته می­شود. استخراج رانش مفهوم اشاره دارد به شناسایی محل و نوع تغییراتی که در طول زمان در فرآیندهای کسب و کار یا به طور کلی در سابقه‌ی روبداد رخ داده است. در این مقاله یک روش ابتکاری با معرفی یک تابع فاصله اصلاح شده، برای شناسایی محل و زمان ایجاد رانش مفهوم ارائه می­شود. آزمایش­های انجام شده بر روی 72 پایگاه دادِگان موجود در پیشینه­ی پژوهش که شامل 648 رانش مفهوم در 12 نوع مختلف است، نشان می­دهد روش پیشنهادی 18/98 درصد از رانش­ها را تشخیص می‌دهد درحالی که روش پیشنهادی نسبت به بهترین روش موجود بسیار سریع‌تر است.

واژگان کلیدی: مدیریت فرآیندهای کسب و کار، شناسایی تغییرات در فرآیند، رانش مفهوم، فرآیندکاوی 

 

 

1-                      مقدمه

تجزیه و تحلیل سابقه­ی رویداد1 در سیستم های مدیریت فرآیندهای کسب و کار(BPMS) یکی از محبوب­ترین تحقیقاتی است که در این حیطه انجام می­شود. یکی از این تحقیقات فرآیند کاوی است. فرآیند کاوی به دسته‌ای از تحقیقات بر روی سابقه­ی رویداد تمرکز دارد که هدف اصلی آنها استخراج2 مدل فرآیند، سازگاری یا تطبیق3 مدل استخراج شده با سابقه­ی رویداد و بهبود و توسعه مدل4 موجود می­باشد[1] الگوریتم­های زیادی برای استخراج فرآیند از سابقه­ی رویداد وجود دارد که از آن دسته می­توان الگوریتم­های آلفا، آلفا+، آلفا++، آلفا# ، ابتکاری، نام برد. تکنیک­های فرآیند کاوی معاصر، عموماً فرآیندها را پایدار در نظر می­گیرند، در صورتیکه امروزه در واقعیت فرآیندهای کسب و کار در طول زمان و در فواصل مختلف ممکن است دست­خوش تغییر و تحول شوند. این تغییرات به دلایل مختلفی همچون تغییر در قوانین سازمان­ها، شرایط فصلی، تغییر در عرضه و تقاضا، تعادل بارِکاری، تعدیل نیرو و یا بروز بلایا و فجایع طبیعی صورت می­گیرد. این تغییرات ممکن است در طول زمان تاثیرات عمیقی بر روی کارایی فرآیندهای سازمانی بگذارند، به همین دلیل شناسایی محل وقوع و دلیل این تغییرات، برای مدیران سازمان­ها از اهمیت ویژه­ای برخوردار است. به این نوع تغییرات در اجرای فرآیندهای کسب و کار که در طول زمان باعث تغییراتی در سابقه­ی رویداد می­شود، رانش مفهوم5 می­گویند. رانش مفهوم در فرآیند می­تواند به صورت تدریجی، ناگهانی، افزایشی و مقطعی صورت بگیرد[2]. در تغییرات ناگهانی، فرآیند جدید جایگزین فرآیند موجود می­شود و معمولاً در مواقع اضطراری یا با تغییر قوانین صورت می­گیرد. در تغییرات تدریجی نیز فرآیند موجود توسط فرآیند جدید جایگزین می­شود اما برخلاف تغییر ناگهانی، در اینجا هر دو فرآیند برای مدت زمانی با هم در حال اجرا هستند و سپس فرآیند پیشین به تدریج کنار گذاشته می­شود. در تغییرات افزایشی تغییرات به صورت مرحله به مرحله انجام می­شود و در تغییرات مقطعی، تغییرات برای مقطع زمانی کوتاهی اعمال می­شود و دوباره به روال قبلی برمی­گردد. در شکل (1) انواع رانش­های مفهوم (تغییرات) بین دو مفهوم (گونه­ی فرآیند کسب و کار) C1 و C2 به تصویر کشیده شده است. شناسایی انواع رانش و تفکیک هر یک از آنها از چالش‌های اصلی در شناسایی رانش مفهوم است. در روش‌های موجود توجه روی شناسایی رانش‌های ناگهانی است و دقت شناسایی در انواع دیگر نسبت به رانش‌های ناگهانی کمتر است.

img0 

(الف) مقطعی

(ب) تدریجی

(ج) افزایشی

(د) ناگهانی

شکل 1- انواع رانش مفهوم از نظر اثر تغییر در سابقه­ی رویداد در طول زمان [2]

1-1-                      رانش مفهوم

فرآیندکاوی یکی از مسائل مورد توجه در BPMS است که هدف آن استخراج مدل فرآیند از سابقه­ی رویداد است. مدل فرآیند شامل ساختارهای هم­زمانی، انتخابی، توالی و حلقه­ها است که اجرای آن به شکل دنباله­ای از رویدادها در سابقه­ی رویداد ذخیره می­شود. در حالی که شناسایی و استخراج رانش مفهوم مسئله­ی پیچیده­تری است و هدف آن کشف تغییرات رخ داده در ساختار مدل فرآیند است که باید با آنالیز و تحلیل داده های ذخیره شده در سابقه­ی رویداد کشف شود. استخراج رانش مفهوم نیز یکی از مسایل پر طرفدار در شاخه­های مختلف هوش مصنوعی است و در داده کاوی به عنوان یک مسئله رایج هم به صورت یادگیری با نظارت و هم بدون نظارت مورد مطالعه قرار گرفته است [3-6] با این حال، این مسایل به عنوان بخشی از مراحل فرآیند کاوی مورد توجه قرار نگرفته است. اگر چه تجربیات بدست آمده در داده کاوی و یادگیری ماشین در فرآیند کاوی قابل استفاده است، اما پیچیدگی های ساختار فرآیند مانند ساختارهای انتخابی6، حلقه، هم روندی، انصراف7 و انتخاب­های مشروط8 (وابسته به انتخاب­های قبلی در اجرای فرآیند) چالش­های زیادی را در استخراج رانش مفهوم از سابقه­ی رویداد ایجاد می­کند.

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

1_2        عوامل ایجاد رانش مفهوم در فرآیندها

ماراجی و همکاران [7] عوامل تغییر فرآیند را معرفی کردند و این عوامل را با 12 الگو متفاوت طبقه بندی کردند، در جدول(1) لیست این عوامل ذکر شده است. ماراجی این عوامل را در سه گروه درجی(I)، انتخابی(O) و تغییر ترتیب(R) دسته‌بندی کرد و بر هر یک از عوامل جدول (1) چهار فایل پایگاه دادِگان با اندازه های 10000، 7500، 5000 و 2500 پیمایش9 با استفاده از تکنیک های شبیه سازی روی فرآیند درخواست وام (شکل(2)) ایجاد کرد و 6 فایل دادِگان ترکیبی نیز از ترکیب عوامل هر دسته ایجاد کردند که در مجموع 72 فایل دادگان (12 عامل اصلی و 6 عامل ترکیبی در 4 اندازه مختلف) توسط ماراجی و همکاران ایجاد شد. در هر فایل دادگان، 9 رانش مفهوم به صورت عمدی ایجاد شده است که در مجموع 648 رانش مفهوم را شامل می‌شود. پایگاه دادگان ماراجی در مقالات بعدی مورد توجه نویسندگان و محققان قرار گرفت و محققان برای آزمایش روش‌های خود از آن استفاده کردند. 

 

ردیف

شرح

اختصار

گروه

1

حذف یا ایجاد یک بخش در فرآیند

re

درجی (I)

2

قرار دادن یا خارج کردن یک بخش در انشعاب شرطی

cm

3

تکرار دوتایی یک بخش

cp

4

قرار دادن یا خارج کردن یک بخش در انشعاب موازی

pm

5

تعویض یک بخش از فرآیند

rp

6

جابجایی دو بخش

sw

7

ایجاد حلقه رو یک بخش یا حذف حلقه

lp

انتخابی (O)

8

ایجاد پرش از روی یک بخش یا حذف پرش

Cb

9

تغییر در فراوانی انشعاب انحصاری

Fr

10

همگام سازی دو بخش

cd

تغییر ترتیب(R)

11

تغییر دو بخش از انتخاب انحصاری به توالی و بالعکس

cf

12

تغییر دو بخش با اجرای موازی به توالی و بالعکس

pl

جدول 1- عوامل ایجاد رانش مفهوم در فرآیندها[7]

شکل 2- فرآیند درخواست وام جهت ایجاد پایگاه دادگان[7]

 

در این مقاله، از یک روش رایج جهت استخراج رانش مفهوم از سابقه­ی رویداد استفاده می­شود که با حرکت دو پنجره با اندازه یکسان و ثابت اطلاعات دو بردار ویژگی را از دو ناحیه کنار هم در سابقه­ی رویداد استخراج می­کند، سپس به یک روش ابتکاری دو بردار ویژگی برای هر پنجره ایجاد می‌شود و از یک تابع فاصله‌ی جدید(معرفی شده در این مقاله) با عنوان symgTest10 استفاده می‌شود که منجر به استخراج بهتر رانش مفهوم در فرآیندهای کسب و کار می­شود. 

2-                      پیشینه پژوهش

سیستم­های مدیریت فرآیندهای کسب و کار به گونه‌ای طراحی شده­اند که امکان تغییر در فرآیندهای کسب و کار را به سادگی برای کاربران فراهم می­کند. این تغییرات به صورت مداوم در پاسخ به عوامل خارجی مانند اسناد بالادستی، قوانین و مقررات جدید، شرایط بازار، تغییر در تقاضای مشتریان، تغییرات فصلی و سال مالی به وجود می­آید. برخی از این تغییرات با اطلاع قبلی و مستند می­باشد، ولی برخی از آنها بدون آگاهی و گاهی به­صورت سهوی به موجود می­آیند و بعد از گذشت مدتی به عنوان یک تغییر هنجار در سیستم باقی می­مانند. برخی از این تغییرات ممکن است در کد منبع سیستم­های اطلاعاتی خارج از مدل فرآیند ایجاد شود که ناشی از نبودن امکان یا عدم پشتیبانی سیستم مدیریت فرآیند باشد. اگرچه پژوهش­های زیادی برای شناسایی فرآیندها از سابقه­ی رویداد انجام شده است[8، 9] ولی اکثر پژوهش­های انجام شده فرض می­کنند فرآیند در طول دوره­ای که اجرا شده است تغییری در آن رخ نداده است [10] در حالی که عبارت رانش مفهوم در فرآیند یک اصطلاح شناخته شده است و شناسایی آن قبل از استخراج فرآیند می­تواند باعث بهبود فرآیند کاوی و ارائه فرآیندهای مستخرج شده قابل انطباق­11تر شود [11-14].

گوندر و همکاران [15] برای شناسایی تغییرات در فرآیند از سابقه­ی تغییرات در مدل فرآیند استفاده شده است این بدان معناست که نویسندگان از یک دانش بالا دستی برای شناسایی تغییرات استفاده کرده­اند و در واقع امکان شناسایی تغییراتی که مستند سازی نشده است در روش آنها وجود ندارد و صرفاً تغییرات مدل فرآیند (نه اثر تغییرات در اجرای فرآیند) مورد بررسی قرار گرفته است.

بوز (Bose) و همکاران [16] تنها با بررسی سابقه­ی رویدادها توانستند محل رانش مفهوم در فرآیند را شناسایی کنند. آنها برای شناسایی محل رانش هم از ویژگی­های محلی و هم از ویژگی­های عمومی رویدادها استفاده کردند، با این حال قادر به شناسایی همه انواع رانش مفهوم در فرآیند نبودند. از طرف دیگر در روش آنها لازم بود، کاربر پارامتری را تحت عنوان اندازه‌ی پنجره تنظیم کند تا رانش مفهوم به درستی شناسایی شود در حالی که تنظیم این پارامتر نیاز به یک دانش اولیه در مورد سابقه­ی رویداد ورودی دارد، در روش آنها میزان دقت نتایج بسیار به پارامتر اندازه‌ی پنجره وابسته بود.

ماراجی و همکاران [7] برای رفع مشکل بوز از یک پنجره‌ی انطباقی برای شناسایی رانش مفهوم استفاده کردند. در روش آنها از آزمون آماری G-test بر روی دو پنجره استفاده می­شود، یک پنجره، به عنوان پنجره‌ی ارجاع و دیگری به عنوان پنجره‌ی تشخیص، در هر کدام، تعدادی از پیمایش­ها12 موجود در سابقه­ی رویداد مورد بررسی قرار می­دهند و تفاوت در توزیع آماری داده­ها ملاک اصلی تشخیص رانش مفهوم در پنجره‌ی تشخیص است. 

مارتجوشو (Martjushev) و همکاران [14] مانند ماراجی از ایده پنجره انطباقی استفاده کردند و الگوریتمی را تحت عنوان Change Point معرفی کردند. آنها الگوریتم خود را برای شناسایی رانشهای مفهوم تدریجی توسعه دادند. سیلیگر (Seeliger) و همکاران [17] از الگوریتمChange Point  استفاده کردند و برای استخراج ویژگی‌های پنجره های ارجاع و تشخیص از ويژگی‌های گراف مدل فرآیند استخراج شده در هر پنجره استفاده کرد و برای آزمایش الگوریتم خود از پایگاه دادگان ماراجی استفاده کرد و به دقت شناسایی 66/94 درصد دست یافتند. 

استوار (Ostovar) و همکاران [18] یک مفهوم سطح بالاتر به عنوان «اجرا» تعریف کردند، این مفهوم به معنای مجموعه از پیمایش­ها است که در اجرای فرآیند کسب و کار، با هم به صورت موازی اجرا شوند. استوار و همکاران علاوه بر اطلاعات آماری «اجرا» در سابقه­ی رویدادها از روابط دوتایی بین رویدادها که در الگوریتم آلفا+ معرفی شده بود برای شناسایی رانش مفهوم استفاده کردند. این روابط دوتایی شامل هم روندی13، تقدم-تاخر14، حلقه به خود15 و حلقه به طول دو16 (دوتایی) می­باشد. استوار و همکاران در ادامه‌ی تحقیقات خود [13] با معرفی درخت فرآیند و استخراج درخت فرآیند در دو پنجره‌ی ارجاع و تشخیص به جای استخراج مدل فرآیند، دقت و سرعت روش خود را بهبود دادند که باعث شد به دقت 74/99 درصدی دست یابند. 

آکورسی و همکاران [19] و هومپز و همکاران [20] هم از روش‌های متفاوتی برای شناسایی رانش مفهوم استفاده می‌شود. آنها از خوشه‌بندی پیمایش­ها و محاسبه‌ی فاصله­ی هر جفت رویداد در هر پیمایش استفاده کردند. در حقیقت ساختار فرآیند در قالب محل قرار گرفتن هر رویداد در پیمایش در روش آنها مورد توجه قرار گرفت. در روش آنها هم مانند روش بوز و همکاران اندازه‌ی پنجره باید توسط کاربر تنظیم می­شد. کارمونا و همکاران [12] یک روش بلادرنگ با توانایی آموزش را برای شناسایی رانش مفهوم ارائه شد. در روش آنها اندازه‌ی پنجره طبق یک الگوریتم یادگیری تخمین زده می­شد سپس یک پنجره‌ی انطباقی با استفاده از پارامتر بدست آمده نقاط رانش مفهوم را شناسایی می­کرد.

3-                      روش پژوهش

سیستم­های مدیریت فرآیندهای کسب و کار (BPMS) حداقل شامل سه بخش اساسی هستند. یک بخش شامل یک ویرایش­گر گرافیکی قدرتمند برای طراحی مدل فرآیند است و بخش دوم که می­توان مهم­ترین بخش این سیستم­ها دانست موتور اجرای فرآیند سازمانی است و بخش سوم آن تحلیل و بهینه سازی اجرای فرآیندها می­باشد. در سازمان­هایی که از BPMS برای مدیریت و اداره‌ی سیستم­های اطلاعاتی خود استفاده می­کنند، هر فرآیند برای پاسخ دهی به یک درخواست مشتری یا یک درخواست از سایر بخش­های سازمان طراحی می­شود. با ایجاد یک درخواست، از مدل فرآیند مربوطه با آن درخواست یک نمونه فرآیند17 ایجاد می­شود و این نمونه فرآیند در موتور اجرای فرآیند اجرا می­شود. در جریان اجرای یک فرآیند مجموعه­ای از رویدادها رخ می­دهد که مهم­ترین آنها ایجاد یک کار، تخصیص یک کار به منبع(نیروی انسانی)، شروع انجام کار و اتمام کار می­باشد و دنباله ای از این رویدادها به صورت یک یا چند فایل که غالباً به دو فرمت XES یا MXML است به عنوان سابقه­ی رویداد ذخیره می­شوند. تحلیل سابقه­ی ایجاد شده از اجرای فرآیندها پیشین می­تواند باعث بهبود و بهینه سازی اجرای فرآیندهای آتی شود. یکی از این موارد می­تواند شناسایی رانش مفهوم در سابقه­ی رویداد باشد. در ادامه قبل از بیان ایده­ی اصلی این مقاله لازم است برخی از مفاهیم موجود در این زمینه را تعریف کنیم. 

3-1 مفاهیم پایه و تعاریف

3-1-1 مدل فرآیند، سابقه رویداد، پیمایش، گونه

مدل فرآیند  پنج­تایی است که شامل مجموعه­ای از کار18ها  است و مجموعه­ی مشخصی از راس­های کنترلی  و دو راس start و end به عنوان راس­های شروع و پایان است که در یک گراف جهت­دار  به هم وصل شده­اند به­طوری­که  و  که بیانگر تقدم و تاخر انجام کارها در مدل فرآیند است. 

یک سابقه­ی رویداد  شامل مجموعه­ای از پیمایش­ها  است. که  اندازه‌ی سابقه­ی رویداد یا همان تعداد پیمایش­های موجود در سابقه­ی رویداد را مشخص می­کند. هر پیمایش خود شامل دنباله­ای از رویدادهایی است که در اجرای یک نمونه فرآیند مربوط به یک درخواست مشخص در سابقه­ی رویداد ثبت می­شود. بنابراین هر پیمایش را می­توان به صورت  نشان داد. در هر عنصر  از این پیمایش متناظر با رویدادی که در زمان i ام روی کار  از فرآیند رخ داده است. از آنجایی که در گراف F می­تواند حلقه وجود داشته باشد؛ مقدار  در رویدادهای یک پیمایش می­تواند تکراری باشد. تابع  را به عنوان مسیر حرکت پیمایش  روی گرافF تعریف می­کنیم. پیمایش­های موجود در سابقه­ی رویداد را می­توان بر اساس مسیر حرکتش روی گراف F دسته بندی کرد به عبارت دیگر دو پیمایش  که  یک مسیر یکسان را روی گراف F پیمایش می­کنند؛ در یک دسته قرار می­گیرند در ادامه این مقاله به هر دسته از پیمایش­ها یک «گونه19» می­گوییم. به عنوان مثال در شکل(3) اجرای فرآیند تولید [21] به دلیل وجود حلقه روی کار  می­تواند به صورت تئوری بینهایت گونه تولید کند.

img0 

شکل 3. مدل فرآیند تولید [21]

1-3-                      ایده­ی اصلی

از آنجایی که عامل­های اصلی رانش مفهوم به نوع تغییر در فرآیند برمی­گردد. هر نوع تغییری در فرآیند کسب و کار (به جز تغییر در احتمال انتخاب انشعاب XOR) در طول(تعداد رویدادهای موجود در پیمایش) پیمایش و دسته­بندی گونه­ی پیمایش اثر گذار خواهد بود. و باعث تغییر در توزیع و فراوانی گونه­ها می­شود. در این مقاله برای شناسایی رانش مفهوم از دو پنجره‌ی زمانی با عنوان­های پنجره‌ی «ارجاع» و پنجره‌ی «تشخیص» استفاده می­شود. این دو پنجره در طول زمان روی سابقه­ی رویداد حرکت می­کنند. طول هر دو پنجره با هم برابر است و عبارت است از تعداد پیمایش­هایی از سابقه­ی رویداد که در این پنجره‌ها قرار می­گیرد. ایده­ی اصلی در شناسایی رانش مفهوم، تغییر توزیع آماری گونه­های موجود در این دو پنجره­ی ارجاع و تشخیص می­باشد.

2-3-                      شناسایی رانش مفهوم براساس فراوانی گونه

روند کلی روش پیشنهادی در شکل(4) آمده است. در ابتدا، دو پنجره با اندازه‌ی یکسان روی سابقه­ی رویداد حرکت می­کند از هر پنجره یک بردار از میزان فراوانی جفت کارهای پشت سر هم داخل پنجره ایجاد می­شود. در این مرحله دو بردار فراوانی یا بردار ویژگی به نام­های VR و VD ایجاد می­شود سپس با یک آزمون آماری یا یک تابع مشخص، فاصله‌ی این دو بردار محاسبه می­شود. با حرکت دو پنجره بر روی کل سابقه­ی رویداد و محاسبه‌ی فاصله‌ی بردارهای ویژگی، نمودار تغییرات فاصله برای کل سابقه­ی رویداد ایجاد می­شود. سپس در مرحله‌ی بعد با تعیین مقدار آستانه، نقاط رانش مفهوم شناسایی می­شود. بنابراین با توجه به شکل(4) می­توان مراحل شناسایی رانش مفهوم را در روش پیشنهادی به صورت ذیل بیان کرد.

1)       ایجاد دو پنجره با اندازه‌ی w تحت عنوان پنجره­ی ارجاع  و پنجره‌ی تشخیص  بر روی سابقه­ی رویداد به­طوری­که در مجموع 2w پیمایش از سابقه­ی رویداد را در بر بگیرد.

2)       استخراج بردار ویژگی برای هر پنجره با شمارش جفت کارهای پشت سر هم در گونه­های موجود در هر پنجره به نام­های VR و VD به ترتیب برای پنجره­های ارجاع و تشخیص

3)       محاسبه­ی فاصله دو بردار ویژگی بر اساس رابطه(4) در بخش 3-3-1 (تابع پیشنهادی این مقاله) 

4)       تکرار مراحل 1 الی 3 با حرکت دادن دو پنجره در طول زمان تا کل پیمایش­های موجود در سابقه­ی رویداد مشاهده شوند و استخراج تغییرات فاصله بردارهای VR و VD

5)       محاسبه­ی مقدار آستانه با استفاده از هیستوگرام مقادیر فاصله­ی بردارهای ویژگی 

1-2-3-                      محاسبه­ی فاصله‌ی دو بردار ویژگی

گونه 1

 

گونه 2

 

گونه 3

 

گونه 4

 

 

 

گونه n

 

img0 

 

شکل 4. روند کلی روش پیشنهادی

در این مقاله برای محاسبه­ی فاصله­ی دو بردار ویژگی از دو آزمون آماری  و gTest و فاصله­ی زاویه­ای دو بردار (کسینوسی) و یک تابع فاصله­ی پیشنهادی استفاده کرده­ایم که نتایج آن به صورت تفکیک شده در بخش نتایج گزارش می­شود. از آنجایی که در تابع فاصله­ی پیشنهادی مشابه به آزمون آماری gTest است. آنرا در ادامه symgTest می­نامیم.

(1) 

 

(2)

 

(3)

 

 

(4)

 

img0 

شکل 5. روش ایجاد فایلهای پایگاه داده شناسایی رانش مفهوم [22]

 در رابطه­های (1) و (2) هر پیمایش به عنوان یک متغیر تصادفی در نظر گرفته می­شود و جامعه آماری در پنجره­ی ارجاع را به عنوان مرجع قرار می­دهد و انتظار دارد نمونه­های(پیمایش­های) مشاهده شده در پنجره تشخیص جامعه­ی آماری مشابهی با پنجره­ی ارجاع داشته باشد. رابطه­ی(3) فاصله کسینوسی دو بردار را نشان می­دهد و در مواقعی که فضای بردارهای ویژگی فضای متریک است و اگر تغییرات فاصله­ی دو بردار به صورت نسبی مشابه هم باشد، می­تواند نتایج بهتری را در شناسایی رانش مفهوم نشان دهد. رابطه­ی(4) نسخه­ی متقارن شده­ی رابطه­ی(2) است که در این مقاله پیشنهاد شده است، این تغییر توانسته علاوه بر متقارن کردن فاصله gTest با اضافه کردن پارامتر  نقش پیمایش­هایی که در یکی از دو پنجره وجود دارد و در دیگری وجود ندارد را برجسته کند. هرچه مقدار  کوچک­تر باشد این اثر برجسته­تر می­شود. 

4-                      تجزیه و تحلیل یافته‌ها 

ماراجی و همکاران [7] برای آزمایش روش پیشنهادی خود 72 فایل سابقه­ی رویداد در فرمت MXML با استفاده از شبیه­ساز BIMP20 ایجاد کردند. ماراجی برای ایجاد پایگاه دادگان خود، روی فرآیند درخواست وام (شکل(2)) تغییرات جدول(1) را ایجاد کرد و هر دو فرآیند اصلی و تغییر یافته را در شبیه ساز BIMP برای تعداد درخواست 5000، 3750، 2500 و 1250 اجرا شده است و مانند شکل (5) درخواست به 5 دسته­ی به ترتیب 1000 یا 750، 500 و 250 تایی تقسیم شده و به صورت یکی در میان از فرآیند اصلی و تغییر یافته با هم ادغام شدند و در نهایت به ترتیب فایل‌هایی شامل 10000 یا 7500، 5000 و 2500 پیمایش ایجاد شد. هر فایل شامل 9 رانش مفهوم از فرآیند اصلی به تغییر یافته و بعکس را دارا است. به همین ترتیب برای هر یک از 12 عامل لیست شده در جدول(1) (و 6 عامل با ترکیب و انتخاب یک عامل از هر گروه) چهار فایل دادگان ایجاد کردند. به عنوان مثال برای «حذف یا ایجاد یک بخش در فرآیند» چهار فایل به عنوان re10k، re7.5k، re5k و re2.5k با فرمت MXML ایجاد شده است. 

1-4-                      روش اندازه گیری دقت شناسایی

برای اندازه گیری دقت شناسایی از معیار F1 استفاده می­کنیم که روش محاسبه­ی آن در رابطه­ی (7) آمده است.

در هر فایل از سابقه­ی رویداد 9 رانش مفهوم وجود دارد. در شکل 6) یک نمونه از اجرای روش پیشنهادی روی فایل fr5k را نشان می­دهد در این فایل 9 رانش در محل­های 500k برای مقادیر  وجود دارد. در این اجرا 7 رانش مفهوم به درستی تشخیص داده شده است، یک رانش مفهوم در شماره پیمایش 4119 به اشتباه تشخیص داده شده است و دو رانش مفهوم در محلهای 1500 و 2000 تشخیص داده نشده است. بنابراین طبق رابطه­ی (7) مقدار  خواهد شد. به همین صورت مقدار  برای72 اجرا محاسبه خواهد شد.

 

شکل 6- نمودار فاصله بردار ویژگی بین دو پنجره‌ی ارجاع و تشخیص حاصل از اجرای الگوریتم پیشنهادی روی فایل fr5k

2-4-                      اثر اندازه پنجره در دقت شناسایی

از آنجایی که الگوریتم پیشنهادی بر اساس حرکت دو پنجره­ی ارجاع و تشخیص طراحی شده است اندازه­ی این دو پنجره در دقت شناسایی تاثیر گذار است. هرچه اندازه­ی پنجره بزرگتر باشد پیمایش­های بیشتری در هر پنجره بررسی می­شود و بردارهای ایجاد شده ابعاد بزرگتری خواهد داشت، در نتیجه باعث بهبود دقت شناسایی می­شود. برای نمایش این اثر در روش پیشنهادی از تابع فاصله  (رابطه­ی(4)) و مقادیر اندازه­ی پنجره 25 الی 250 پیمایش با افزایش 25تایی استفاده می­شود و مقدار میانگین آن برای 72 فایل ورودی پایگاه دادگان محاسبه می­شود که نتیجه­ی آن در شکل (7) نمایش داده شده است.

 

شکل 7- اثر اندازه‌ی پنجره های تشخیص و ارجاع در دقت شناسایی () رانش مفهوم

در شناسایی رانش مفهوم علاوه بر دقت شناسایی زمان یا سرعت تشخیص رانش نیز اهمیت دارد، مخصوصاً در کاربردهای برخط که بعد از شناسایی رانش توسط مدیریت تصمیماتی در مورد عملکرد سیستم گرفته می­شود، بنابراین شناسایی به موقع و زود هنگام رانش مفهوم از اهمیت ویژه­ای در این حیطه برخوردار است. همانطور که در شکل 7) مشاهده شد؛ افزایش اندازه‌ی پنجره باعث بهبود در دقت شناسایی رانش مفهوم شد. اما همین افزایش می­تواند باعث افزایش تاخیر در شناسایی شود. برای این منظور در آزمایش انجام شده مطابق با شکل 8) برای شناسایی­های درست تشخیص داده شده میانگین تاخیر به ازای هر اندازه پنجره اندازه­گیری شد که نتیجه­ی آن در شکل 9) آمده است.

img0 

شکل 8- روش محاسبه‌ی تاخیر در شناسایی رانش مفهوم

 

شکل 9- اثر اندازه پنجره در تاخیر شناسایی رانش مفهوم

همان­طور که در شکل 9) نشان داده شده است، افزایش اندازه‌ی پنجره‌ی تاخیر شناسایی را تا ابتدای پنجره‌ی تشخیص کاهش می­دهد ولی از آنجایی که در پیشینه‌ی پژوهش تاخیر شناسایی تا انتهای پنجره تشخیص تعریف شده است. متاسفانه با افزایش اندازه­ی پنجره تاخیر افزایش می­یابد. این اثر در شکل 9) در نمودار تاخیر تا انتهای پنجره‌ی تشخیص مشهود است. بنابراین با اینکه افزایش اندازه‌ی پنجره باعث بهبود دقت شناسایی می­شود ولی در کاربردهای برخط که کاهش تاخیر شناسایی نیز دارای اهمیت است باید اندازه پنجره خیلی بزرگ نباشد. در نتیجه با توجه به نمودارهای دقت شناسایی و تاخیر شناسایی که در شکل 7) و شکل 9) آمده است می­توان اندازه­ی پنجره­ی 100 را مقدار مناسبی که نتیجه­ی این دو تقابل است در نظر گرفت. که هم دقت به اندازه­ی کافی افزایش یافته است و هم تاخیر هنوز خیلی زیاد نشده است. البته نگاه دقیق­تر به پیشینه­ی پژوهش، اندازه­ی پنجره­ی 100 را روی پایگاه دادِگان مورد آزمایش تایید می­کند.

[1] نویسنده مسئول: مهدی یعقوبی  m.yaghoubi@gu.ac.ir

 

 

 Event log

[2]  Discovery

[3]  Conformance checking

[4]  Enhancement of process models

[5]  Concept drift

[6]  Choice

[7]  Cancelation

[8]  Non-free Choice

[9]  Trace

[10]  Symmetric Goodness of fit Test

[11]  Fitness

[12]  Traces

[13]  Concurrency

[14]  Causality

[15]  Self-loop

[16]  Length-two loop

[17]  Process Instance

[18]  Task

[19]  Variant

[20]  http://bimp.cs.ut.ee/

 

شکل 10- دقت شناسایی به تفکیک عامل‌های رانش

 

شکل 11- مقایسه توابع فاصله بردارهای ویژگی در میزان دقت شناسایی

 

3-4-                      اثر عامل‌های رانش مفهوم در دقت شناسایی

برای آزمایش دقیق­تر اثر عامل­های رانش بر روی روش پیشنهادی، با اینکه در پایگاه دادگان برای 12 ماهیت رانش (و 6 نوع ترکیبی) 4 فایل وجود داشت و در هر فایل 9 رانش با فاصله های 250، 500، 750 و 1000 پیمایش؛ برای حذف اثر اندازه­ی پنجره در نتایج آزمایش برای مقادیر 25 الی 250 با فاصله 25تایی (در مجموع 10 اندازه پنجره) تکرار شد. در واقع برای هر نوع رانش 40 آزمایش انجام شد. میانگین دقت شناسایی در شکل 10) نشان داده شده است. همانطورکه در شکل 10) مشهود است بجز رانش مفهوم از نوع fr (تغییر در فراوانی انشعاب انحصاری) در سایر عامل‌ها دقت بالای 96 درصد بدست آمده است و در 12 مورد به دقت 100 درصد حاصل شده است. با توجه به نتایج حاصل می­توان به این نتیجه رسید که رانش­های مفهومی که در سابقه­ی رویداد باعث ایجاد و یا حذف یک گونه از پیمایش­ها می­شوند روش پیشنهادی در شناسایی آنها دقت بالایی دارد و در مواردی که فقط فراوانی گونه‌های تغییر می­کند دقت  کمتری خواهد داشت. 

4-4-                      اثر نوع توابع فاصله در دقت شناسایی

در این مقاله علاوه بر تابع symgTest (تابع پیشنهادی) به عنوان فاصله­ی دو بردار ویژگی در پنجره­های ارجاع و تشخیص سه تابع gTest ، Chi2-Test و فاصله کسینوسی (رابطه­های (1) الی (3)) مورد آزمایش قرار گرفتند. شکل (11) اثر بهتر تابع پیشنهادی را نسبت به سایر توابع را نشان می­دهد. لازم به ذکر است تابع gTest، تابع استفاده شده در سایر پژوهش‌ها ذکر شده در این مقاله است. مقایسه با الگوریتم های موجود

1-4-4-                      از نظر دقت شناسایی 

جهت مقایسه­ی روش پیشنهادی، چهار روش از بهترین الگوریتم­های موجود در پیشینه­ی پژوهش، استوار [13،18]، ProDrift [22] و Change Point [17] و یک الگوریتم پایه­ای که توسط بوز (Bose) و همکاران[16] ارائه شده است را انتخاب کردیم. دو تا روش‌های مورد مقایسه، از استوار و همکاران انتخاب شده است که یکی از آنها در 2016 ارائه شده است و دیگری در مارس 2020 ارائه شده است که بهترین الگوریتم ارائه شده در شناسایی رانش مفهوم تا کنون است. برای مشخص شدن این دو روش از یکدیگر، در ادامه از عناوین Ostovar و Ostovar20 استفاده شده است. نتایج اجرای الگوریتم پیشنهادی و پنج الگوریتم انتخاب شده بر روی 72 فایل پایگاه داده معرفی شده توسط ماراجی [7]، در شکل (12) نمایش داده شده است. در این آزمایش اندازه‌ی پنجره­ها برای هر الگوریتم، مقدار(مقدار اولیه برای پنجره انطباقی) 100 پیمایش در نظر گرفته شده است، البته روش‌های Ostovar و Chage Point از پنجره های انطباقی(طول متغییر) استفاده کرده اند. نتایج به تفکیک 12 عامل رانش مفهوم و 6 عامل ترکیبی نمایش داده شده است. 

(5)

 

(6)

 

(7)

 

دقت شناسایی

 

 

 

 

 

 

 

 

شکل 12- مقایسه‌ی روش­های Ostovar20[13]، Ostovar[18]، Change Point[17]، ProDrift[22] و Bose[16] با روش پیشنهادی با اندازه‌ی 100 پیمایش در پنجره‌ی ارجاع و تشخیص

2-4-4-                      از نظر سرعت

الگوریتم ارائه شده در این مقاله مشابه الگوریتم­های Bose و ProDrift است با این تفاوت که نحوه‌ی استخراج بردارهای ویژگی از پنجره­های ارجاع و تشخیص متفاوت است. در این الگوریتم­ها دو پنجره با طول ثابت w پیمایش بر روی فایل دادگان با  پیمایش حرکت داده می­شود و ویژگی های آماری با پیچیدگی زمانی  از هر پنجره استخراج می­شود که در بدترین حالت پیچیدگی بررسی کل فایل دادگان  خواهد شد. در روش پیشنهادی در هر پنجره به ازای هر پیمایش، جفت کارهای کنار هم نیز شمارش می‌شود که باعث می‌شود ضریب  در پیچیدگی زمانی آن ظاهر می‌شود. در الگوریتم Change Point نیز از دو پنجره با طول متوسط w استفاده می­شود (طول پنجره در زمان اجرا تغییر می‌کند) با این تفاوت که در هر پنجره به جای استخراج ویژگی­های آماری، مدل فرآیند هر پنجره با استفاده از الگوریتم فرآیندکاوی ابتکاری(HM) استخراج می­شود سپس از روی گراف حاصل شده ویژگی­های متریک آن استخراج می­گردد که در مجموع در بدترین حالت استخراج مدل فرآیند و ویژگی‌ها آن  زمان خواهد برد کهw ، t و l به ترتیب متوسط طول پنجره‌‌ی تطبیقی، تعداد کارهای(Task) مدل فرآیند (تعداد راس­های گراف) و متوسط طول پیمایش است. الگوریتم‌های Ostovar و همکاران هم بر اساس دو پنجره با اندازه­ی تطبیقی شناسایی رانش مفهوم را در بدترین حالت با پیچیدگی زمانی  انجام می­دهد که مستقل از اندازه‌ی پنجره است[18].

جدول 2- پیچیدگی زمان الگوریتم­های مقایسه شده

برای آزمایش پیچیدگی زمانی تحلیل شده برای الگوریتم پیشنهادی، زمان اجرای الگوریتم پیشنهادی روی یک پردازنده Core i3 8109U با فرکانس 3GHz با مقدار حافظه 4GB در زبان برنامه‌نویسی Python اندازه‌گیری شده است. در شکل(13) مقایسه‌ی زمان اجرای روش پیشنهادی با سایر االگوریتم‌ها را نشان می‌دهد. این آزمایش روی 72 فایل (18 الگو در چهار اندازه فایل دادگان) و اندازه پنجره‌ی 25 الی 250 پیمایش انجام شده است. همانطور که در جدول 2 و شکل (13) مشخص است سه الگوریتم Bose، ProDrift و روش پیشنهادی زمان اجرای خیلی کمتری نسبت به سه الگوریتم Ostovar، Ostovar20 و ChangePoint هست که می‌توان علت اصلی این تفاوت را در استفاده از پنجره انطباقی دانست، درحالی که دقت شناسایی الگوریتم پیشنهادی از بهترین روش کمتر از یک درصد است. در شکل(13) نتایج اجرای روش پیشنهادی به تفکیک اندازه‌ی پنجره و اندازه‌ی فایل دادگان به صورت جداگانه نمایش داده شده است. همانطورکه در شکل(14) مشخص است زمان اجرای الگوریتم پیشنهادی، با افزایش اندازه‌ی پنجره و افزایش فایل دادگان به صورت خطی افزایش یافته است.

 

 

شکل 13- اندازه‌گیری زمان اجرا و مقایسه‌ی روش پیشنهادی با سایر روش‌ها (محور افقی تغییرات اندازه‌ی فایل دادگان و اندازه‌ی پنجره را نشان می‌دهد و محور عمودی زمان اجرای الگوریتم را به میلی ثانیه در مقیاس لگاریتمی نشان می‌دهد)

الگوریتم

پیچیدگی زمانی

Ostovar

 

20Ostovar

 

Change Point

 

ProDrift

 

Bose

 

روش پیشنهادی

 

 

 

شکل 14- اندازه‌گیری زمان اجرای الگوریتم پیشنهادی (الف) برای مقادیر مختلف اندازه‌ی پنجره و (ب) برای مقادیر مختلف اندازه فایل دادگان که با افزایش آنها زمان استخراج رانش به صورت خطی افزایش میابد

 

شکل15- استخراج رانش مفهوم روی پایگاه دادگان فرآیند مدیریت بلیط که دو رانش ناگهانی و یک رانش مقطعی را نشان می‌دهد

 

شکل16- استخراج رانش مفهوم روی داده‌های ترافیکی شهر مقدس مشهد که هفت رانش مقطعی را نشان می‌دهد

 

5-                      آزمایش روش پیشنهادی روی پایگاه دادگان واقعی

1-5-                      شناسایی رانش در فرآیند مدیریت بلیط

مشابه با آزمایش انجام شده توسط استوار و همکاران [13] روش پیشنهادی روی یک پایگاه دادگان فرآیند مدیریت بلیط1 در یک شرکت نرم افزاری ایتالیایی اجرا شد. در این پایگاه 21348 رویداد، 14 فعالیت، 4580 پیمایش وجود دارد. در اجرای الگوریتم پیشنهادی  مشابه آزمایش استوار، اندازه پنجره‌ها 1000 پیمایش در نظر گرفته شده است که با پرش‌های 10 پیمایش در شکل (15) نشان داده شده است. مشابه گزارش استوار و همکاران روش پیشنهادی در این مقاله نیز دو رانش اصلی در محل های 1150 و 1530 را نشان می‌دهد، روش پیشنهادی علاوه بر گزارش استوار و همکاران یک رانش کوچکتر را نیز در محل 1370 را یافته است که البته گزارش نشدن آن توسط استوار و همکاران می‌تواند به علت متفاوت بودن مقدار حد استانه تغییرات در شناسایی رانش مفهوم باشد. 

2-5-                      شناسایی رانش روی داده‌های ترافیکی مشهد

پایگاه دادگان واقعی دومی که برای آزمایش در این مقاله استفاده شده است یک پایگاه داده غیر فرآیندی است که با یک تغییر جزئی در استخراج بردار ویژگی در روش پیشنهادی، امکان استخراج رانش‌های مفهوم در داده های ترافیک شهری را نشان می‌دهد و اهمیت موضوع مورد بحث در این مقاله را روشن‌تر می‌کند. پایگاه دادگان ترافیک شهری مشهد شامل 073,979,5 رویداد ثبت اطلاعات استفاده از من‌کارت در 2696 ترمینال اتوبوسرانی و قطار شهری در شهر مقدس مشهد است که در بازه‌ی تاریخی 03/2011 الی 03/2018 ثبت شده است. با شمارش تعداد من‌کارت‌های استفاده شده در هر ترمینال بردار ویژگی هر پنجره حاصل می‌شود. در این آزمایش از پنجره‌های زمانی یک هفته‌ای با پرش‌های یک هفته استفاده شده است و از تابع پیشنهادی symgTest برای مقایسه‌ی بردارهای استفاده شده است. شکل (16) محل‌های رانش‌های اصلی را در داده‌های ترافیکی شهر مقدس مشهد را نشان می‌دهد. در این شکل محل‌های رانش مفهوم مربوط به دو مناسبت رحلت رسول اکرم (ص) و شهادت امام رضا (ع) است که تاثیر چشم‌گیری در رفتار ترافیک شهری مشهد گذاشته است که با فواصل مرتب یکسال قمری در شکل (16) مشهود است.

6-                      جمع بندی و نتیجه گیری

در این مقاله یک روش ابتکاری جهت استخراج رانش مفهوم در فرآیندهای کسب و کار ارائه شد. در این روش با حرکت دو پنجره‌ی ارجاع و تشخیص، بر روی سابقه‌ی رویداد و استخراج مولفه‌های آماری پنجره‌ها و مقایسه‌ی آنها جهت شناسایی رانش استفاده شده است. ایده‌ی اصلی مقاله شمارش جفت کارهای انجام شده پشت سر هم در اجرای فرآیند است که ویژگی مفیدی در استخراج الگوهای رانش مفهوم است. علاوه بر این در این مقاله یک تابع مقایسه تحت عنوان symgTest معرفی شد که نسبت به gTest نتیجه‌ی بهتری (76/1 درصد) را در دقت شناسایی در روش پیشنهادی داشت. در صورتی که فاصله‌ی دو بردار از حد آستانه افزایش یابد، شناسایی رانش انجام می‌شود. برای محاسبه‌ی حد آستانه نیز از هیستوگرام نمودار فاصله‌ی دو بردار استفاده شده است. آزمایش عملکرد و دقت روش پیشنهادی بر روی یک پایگاه دادگان موجود در پیشینه‌ی پژوهش انجام شد. آزمایش انجام شده دقت شناسایی 18/98 درصد برای اندازه پنجره 100 را نشان می‌دهد. این مقدار بهترین نتیجه‌ی حاصل در روشهای ارائه شده با اندازه پنجره ثابت است در حالی که بهترین دقت شناسایی (74/99 درصد) مربوط به استوار و همکاران روشی با اندازه پنجره تطبیقی است. تغییر اندازه پنجره در زمان شناسایی رانش مفهوم هزینه زمانی بیشتری را نسبت به روشها با پنجره ثابت دارد. با اینکه روش پیشنهادی دقت کمی کمتر از روش استوار دارد ولی هزینه زمانی بسیار کمتری را نسبت روش استوار دارد. در روش پیشنهادی هزینه زمانی نسبت به اندازه فایل دادگان به صورت خطی رشد می‌کند در حالی که روش استوار نسبت به اندازه فایل دادگان از نوع چندجمله‌ای درج دوم است. یکی از مزایای روش پیشنهادی عدم وابستگی روش به ساختار گراف در مدل فرآیند است و فقط از توالی جفت کارهای پشت سر هم استفاده می‌کند. به دلیل سادگی روش پیشنهادی در پیاده سازی، این روش را به راحتی می‌توان برای سایر داده‌های غیر فرآیندی نیز استفاده کرد.

مراجع

1.       W. M. P. van der Aalst, Process Mining: Discovery, Conformance and Enhancement of Business Processes. Berlin, Heidelberg: Springer Berlin Heidelberg, 2011.

2.       R. P. J. C. Bose, W. M. P. van der Aalst, I. . Žliobait\.e, and M. Pechenizkiy, “Handling concept drift in process mining,” in International Conference on Advanced Information Systems Engineering, 2011, pp. 391–405.

3.       A. Tsymbal, M. Pechenizkiy, P. Cunningham, and S. Puuronen, “Handling local concept drift with dynamic integration of classifiers: Domain of antibiotic resistance in nosocomial infections,” in 19th IEEE Symposium on Computer-Based Medical Systems (CBMS’06), 2006, pp. 679–684.

4.       M. Pechenizkiy, J. Bakker, I. Žliobaitė, A. Ivannikov, and T. Kärkkäinen, “Online mass flow prediction in CFB boilers with explicit detection of sudden concept drift,” ACM SIGKDD Explor. Newsl., vol. 11, no. 2, pp. 109–116, 2010.

5.       M. Van Leeuwen and A. Siebes, “Streamkrimp: Detecting change in data streams,” in Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 2008, pp. 672–687.

6.       D. Brzezinski and J. Stefanowski, “Reacting to different types of concept drift: The accuracy updated ensemble algorithm,” IEEE Trans. Neural Networks Learn. Syst., vol. 25, no. 1, pp. 81–94, 2014.

7.       A. Maaradji, M. Dumas, M. La Rosa, and A. Ostovar, “Fast and accurate business process drift detection,” Lect. Notes Comput. Sci. (including Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), vol. 9253, pp. 406–422, 2015.

8.       M. Reichert, C. Hensinger, and P. Dadam, “Supporting adaptive workflows in advanced application environments,” 1998.

9.       S. Rinderle, M. Reichert, and P. Dadam, “Correctness criteria for dynamic changes in workflow systems, a survey,” Data Knowl. Eng., vol. 50, no. 1, pp. 9–34, 2004.

10.       A. Adriansyah et al., “Process mining manifesto,” 2012.

11.       R. Accorsi and T. Stocker, “Discovering workflow changes with time-based trace clustering,” in International Symposium on Data-Driven Process Discovery and Analysis, 2011, pp. 154–168.

12.       J. Carmona and R. Gavalda, “Online techniques for dealing with concept drift in process mining,” in International Symposium on Intelligent Data Analysis, 2012, pp. 90–102.

13.       A. Ostovar, S. J. J. Leemans, and M. La Rosa, “Robust drift characterization from event streams of business processes,” ACM Trans. Knowl. Discov. from Data, vol. 14, no. 3, pp. 1–57, 2020.

14.       J. Martjushev, R. P. J. C. Bose, and W. M. P. van der Aalst, “Change point detection and dealing with gradual and multi-order dynamics in process mining,” in International Conference on Business Informatics Research, 2015, pp. 161–178.

15.       C. W. Günther, S. Rinderle, M. Reichert, and W. Van Der Aalst, “Change mining in adaptive process management systems,” in OTM Confederated International Conferences" On the Move to Meaningful Internet Systems", 2006, pp. 309–326.

16.       R. P. J. C. Bose, W. M. P. Van Der Aalst, I. . Žliobait\.e, and M. Pechenizkiy, “Dealing with concept drifts in process mining,” IEEE Trans. neural networks Learn. Syst., vol. 25, no. 1, pp. 154–171, 2014.

17.       A. Seeliger, T. Nolle, and M. Mühlhäuser, “Detecting Concept Drift in Processes using Graph Metrics on Process Graphs,” pp. 1–10, 2017.

18.       A. Ostovar, M. Abderrahmane, M. La Rosa, A. H. ter Hofstede, and B. F. van Dongen., “Detecting drift from event streams of unpredictable business processes,” in International Conference on Conceptual Modeling, 2016, pp. 330–346.

19.       R. Accorsi and T. Stocker, “Discovering workflow changes with time-based trace clustering,” in International Symposium on Data-Driven Process Discovery and Analysis, 2011, pp. 154–168.

20.       B. Hompes, J. C. A. M. Buijs, W. M. P. van der Aalst, P. Dixit, and H. Buurman, “Detecting Change in Processes Using Comparative Trace Clustering.,” in SIMPDA, 2015, pp. 95–108.

21.       Y. Xie, C. F. Chien, and R. Z. Tang, “A dynamic task assignment approach based on individual worklists for minimizing the cycle time of business processes,” Comput. Ind. Eng., vol. 99, no. 12, pp. 401–414, 2016.

22.       A. Maaradji, M. Dumas, M. La Rosa, and A. Ostovar, “Detecting sudden and gradual drifts in business processes from execution traces,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 10, pp. 2140–2154, 2017.

[1] https://doi.org/10.4121/uuid:0c60edf1-6f83-4e75-9367-4c63b3e9d5bb

 

 

Fast and accurate concept drift detection from event logs

 

Abstract

In organizations and large companies that are using business process management systems (BPMSs), process model can change due to upstream laws, market conditions. BPMSs have flexible to these changes. Effect of these change are saved in storage devises and event logs; these changes are sometimes applied suddenly or gradually on the event logs. Changing the season or starting a new financial term can be a factor to make these changes. This change is called concept drift in business process model. On time detection and recognition of process concept drift can affect the decision making of managers and administrations of systems. An analysis of the event logs in BPMS allows the automatic detection of the concept drift. This paper presents an innovative method by introducing a modified distance function to identify the concept drift. Experimental results were performed on 72 datasets in the research history, which included 648 concept drifts in 12 different types. It shows that the proposed method detects 98.18% of the drifts, while the proposed method is much faster than other state of the art methods.

 

Keywords: Business process management systems, Process mining, Concept drift, Process drift detection

105


مقالات مرتبط

حقوق این وب‌سایت متعلق به سامانه مدیریت نشریات رایمگ است.
حق نشر © 1403-1396

صفحه اصلی| عضویت/ ورود| درباره رایمگ| تماس با ما|
[English] [العربية] [en] [ar]