ارائه یک روش سریع و دقیق برای شناسایی رانش مفهوم با تحلیل سابقهی رویدادها
محورهای موضوعی : عمومىمهدی یعقوبی 1 , علی سبطی 2 , سهیلا کرباسی 3
1 - گروه مهندسی کامپیوتر، دانشکده فنی مهندسی گرگان، دانشگاه گلستان، گرگان
2 - گروه مهندسی کامپیوتر، دانشکده فنی مهندسی گرگان، دانشگاه گلستان، گرگان
3 - استادیار
کلید واژه: مدیریت فرآیندهای کسب و کار, شناسایی تغییرات در فرآیند, رانش مفهوم, فرآیندکاوی ,
چکیده مقاله :
در سازمان ها و شرکت های بزرگ که از سیستم های مدیریت فرآیندهای کسب و کار (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 |
|
ارائه یک روش سریع و دقیق برای شناسایی رانش مفهوم با تحلیل سابقهی رویدادها
مهدی یعقوبی* علی سبطی* سهیلا کرباسی*
*استادیار گروه مهندسی کامپیوتر، دانشکده فنی مهندسی گرگان، دانشگاه گلستان، گرگان
تاریخ دریافت: 07/02/1399 تاریخ پذیرش: 24/08/1399
نوع مقاله: پژوهشی
چکیده
در سازمانها و شرکتهای بزرگ که از سیستمهای مدیریت فرآیندهای کسب و کار (BPMS) بهره میبرند، در هر لحظه با توجه به قوانین بالادستی و شرایط بازار، ممکن است در فرآیندهای کسب و کار تغییرات رخ دهد. این تغییرات گاهی به صورت آنی و گاهی به صورت تدریجی روی سیستم اعمال میگردد. شناسایی به موقع این تغییرات میتواند در تصمیمگیری بهتر مدیران سازمان اثر گذار باشد. تجزیه و تحلیل سابقهی رویدادها در این سیستمها، امکان شناسایی تغییرات ایجاد شده در فرآیندهای کسب و کار را به صورت خودکار فراهم میکند. به این تغییرات در فرآیندها به اصطلاح رانش مفهوم در فرآیند کسب و کار گفته میشود. استخراج رانش مفهوم اشاره دارد به شناسایی محل و نوع تغییراتی که در طول زمان در فرآیندهای کسب و کار یا به طور کلی در سابقهی روبداد رخ داده است. در این مقاله یک روش ابتکاری با معرفی یک تابع فاصله اصلاح شده، برای شناسایی محل و زمان ایجاد رانش مفهوم ارائه میشود. آزمایشهای انجام شده بر روی 72 پایگاه دادِگان موجود در پیشینهی پژوهش که شامل 648 رانش مفهوم در 12 نوع مختلف است، نشان میدهد روش پیشنهادی 18/98 درصد از رانشها را تشخیص میدهد درحالی که روش پیشنهادی نسبت به بهترین روش موجود بسیار سریعتر است.
واژگان کلیدی: مدیریت فرآیندهای کسب و کار، شناسایی تغییرات در فرآیند، رانش مفهوم، فرآیندکاوی
1- مقدمه
تجزیه و تحلیل سابقهی رویداد1 در سیستم های مدیریت فرآیندهای کسب و کار(BPMS) یکی از محبوبترین تحقیقاتی است که در این حیطه انجام میشود. یکی از این تحقیقات فرآیند کاوی است. فرآیند کاوی به دستهای از تحقیقات بر روی سابقهی رویداد تمرکز دارد که هدف اصلی آنها استخراج2 مدل فرآیند، سازگاری یا تطبیق3 مدل استخراج شده با سابقهی رویداد و بهبود و توسعه مدل4 موجود میباشد[1] الگوریتمهای زیادی برای استخراج فرآیند از سابقهی رویداد وجود دارد که از آن دسته میتوان الگوریتمهای آلفا، آلفا+، آلفا++، آلفا# ، ابتکاری، نام برد. تکنیکهای فرآیند کاوی معاصر، عموماً فرآیندها را پایدار در نظر میگیرند، در صورتیکه امروزه در واقعیت فرآیندهای کسب و کار در طول زمان و در فواصل مختلف ممکن است دستخوش تغییر و تحول شوند. این تغییرات به دلایل مختلفی همچون تغییر در قوانین سازمانها، شرایط فصلی، تغییر در عرضه و تقاضا، تعادل بارِکاری، تعدیل نیرو و یا بروز بلایا و فجایع طبیعی صورت میگیرد. این تغییرات ممکن است در طول زمان تاثیرات عمیقی بر روی کارایی فرآیندهای سازمانی بگذارند، به همین دلیل شناسایی محل وقوع و دلیل این تغییرات، برای مدیران سازمانها از اهمیت ویژهای برخوردار است. به این نوع تغییرات در اجرای فرآیندهای کسب و کار که در طول زمان باعث تغییراتی در سابقهی رویداد میشود، رانش مفهوم5 میگویند. رانش مفهوم در فرآیند میتواند به صورت تدریجی، ناگهانی، افزایشی و مقطعی صورت بگیرد[2]. در تغییرات ناگهانی، فرآیند جدید جایگزین فرآیند موجود میشود و معمولاً در مواقع اضطراری یا با تغییر قوانین صورت میگیرد. در تغییرات تدریجی نیز فرآیند موجود توسط فرآیند جدید جایگزین میشود اما برخلاف تغییر ناگهانی، در اینجا هر دو فرآیند برای مدت زمانی با هم در حال اجرا هستند و سپس فرآیند پیشین به تدریج کنار گذاشته میشود. در تغییرات افزایشی تغییرات به صورت مرحله به مرحله انجام میشود و در تغییرات مقطعی، تغییرات برای مقطع زمانی کوتاهی اعمال میشود و دوباره به روال قبلی برمیگردد. در شکل (1) انواع رانشهای مفهوم (تغییرات) بین دو مفهوم (گونهی فرآیند کسب و کار) C1 و C2 به تصویر کشیده شده است. شناسایی انواع رانش و تفکیک هر یک از آنها از چالشهای اصلی در شناسایی رانش مفهوم است. در روشهای موجود توجه روی شناسایی رانشهای ناگهانی است و دقت شناسایی در انواع دیگر نسبت به رانشهای ناگهانی کمتر است.
| |||
(الف) مقطعی | (ب) تدریجی | (ج) افزایشی | (د) ناگهانی |
شکل 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]
|
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] به دلیل وجود حلقه روی کار میتواند به صورت تئوری بینهایت گونه تولید کند.
گونه 1 |
|
گونه 2 |
|
گونه 3 |
|
گونه 4 |
|
|
|
گونه n |
|
شکل 4. روند کلی روش پیشنهادی |
(1) |
|
(2) |
|
(3)
|
|
(4) |
|
شکل 5. روش ایجاد فایلهای پایگاه داده شناسایی رانش مفهوم [22] |
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) آمده است.
(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- پیچیدگی زمان الگوریتمهای مقایسه شده
الگوریتم | پیچیدگی زمانی |
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