مدل برنامه‌ریزی ریاضی فرایندکاوی در مسئله کشف گراف وابستگی

توکلی زانیانی, مریم; غلامیان, محمدرضا

doi:10.22054/IMS.2020.49943.1679

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

نویسندگان

¹ دانشجوی دکتری، مهندسی صنایع، دانشگاه علم و صنعت ایران، تهران، ایران.

² عضو هیئت‌علمی، دانشکده مهندسی صنایع، دانشگاه علم و صنعت ایران، تهران، ایران.( (نویسنده مسئول)؛ Gholamian@iust.ac.ir

https://doi.org/10.22054/IMS.2020.49943.1679

چکیده

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

کلیدواژه‌ها

عنوان مقاله [English]

A Mathematical Programming Model for the Process Mining in Dependency Graph Discovery Problem

نویسندگان [English]

Maryam Tavakoli Zaniani ¹
Mohammad Reza Gholamian ²

¹ Ph.D. Candidate, Faculty of Industrial Engineering, Iran University of Science and Technology, Tehran. Iran

² Faculty member, Faculty of Industrial Engineering, Iran University of Science and Technology, Tehran. Iran(Corresponding Author: Gholamian@iust.ac.ir)

چکیده [English]

Process discovery is a branch of process mining that by using event logs extracts the process model that describes the events’ behavior properly. Since, Heuristic process discovery algorithms are among the most significant and popular process discovery methods and due to the fact that the quality of outputs of these algorithms is heavily dependent on the quality of extracted dependency graph, in this paper for the first time, an approach to transform the problem of dependency graph discovery to a binary programming problem has been proposed and also, an objective function is introduced that simultaneously considers fitness and precision measures of output models. The weights dedicated to each of the measures are determined by means of a user-defined threshold. The mentioned measures are the most important metrics in assessing quality of output models of process discovery algorithms. Hence, in fact this approach focuses on improving quality metrics of output models. Moreover, by means of defining suitable constrains, the proposed approach is capable of involving domain knowledge in mining procedure, as well as guiding the result through whether the models that are more likely to be sound. This is depicted in a case study of a real company that is described in this paper. In the case study, the proposed approach has been applied to marketing event log of the mentioned company by utilizing the constrains defined according to domain knowledge and structural rules of dependency graph and at the end, the results were presented.

کلیدواژه‌ها [English]

Process Mining
Process Discovery
Dependency Graph
Binary Programming

مراجع

Adriansyah, A., van Dongen, B. F., & van der Aalst, W. M. P. (2011, August). Conformance Checking Using Cost-Based Fitness Analysis. In Proceedings of the 2011 IEEE 15th International Enterprise Distributed Object Computing Conference. (pp. 55-64). IEEE Computer Society.

Alves de Medeiros, A. (2006). Genetic process mining. Ph.D. thesis, TU Eindhoven.

Alves de Medeiros, A., van Dongen, B. F., van der Aalst, W. M. P., & Weijters, A. J. M. M. (2005). Process Mining for Ubiquitous Mobile Systems: An Overview and a Concrete Algorithm. In: L. Baresi, S. Dustdar, H. Gall, & M. Matera (Eds.) Ubiquitous Mobile Information and Collaboration Systems (Springer, Berlin Heidelberg 2005).

Amelia Effendi, Y. & Sarno, R. (2020). Time-based α+ miner for modelling business processes using temporal pattern. TELKOMNIKA (Telecommunication Computing Electronics and Control), 18(1), 114-123.

Buijs, J. C. A. M., van Dongen, B. F.., & van der Aalst, W. M. P. (2012). On the Role of Fitness, Precision, Generalization and Simplicity in Process Discovery. In: R. Meersman, H. Panetto, T. Dillon, S. Rinderle-Ma, P. Dadam, X. Zhou, S. Pearson, A. Ferscha, S. Bergamaschi, & I. Cruz (Eds.) On the Move to Meaningful Internet Systems: OTM 2012 (Springer, Berlin Heidelberg 2012).

Buijs, J. C. A. M., van Dongen, B. F., & van der Aalst, W. M. P. (2014). Quality Dimensions in Process Discovery: The Importance of Fitness, Precision, Generalization and Simplicity. International Journal of Cooperative Information Systems, 23(01), 1-39.

Burattin, A. (2015). Heuristics Miner for Time Interval. In: A. Burattin (Ed.) Process Mining Techniques in Business Environments: Theoretical Aspects, Algorithms, Techniques and Open Challenges in Process Mining (Springer International Publishing, Cham 2015).

Burattin, A., Sperduti, A., & van der Aalst, W. M. P. (2012). Heuristics Miners for Streaming Event Data. Computing Research Repository abs/1212.6383.

He, Z., Du, Y., Wang, L., Qi, L., & Sun, H. (2018). An Alpha-FL Algorithm for Discovering Free Loop Structures From Incomplete Event Logs. IEEE Access, 6, 27885-27901.

Li, J., Liu, D., & Yang, B. (2007). Process Mining: Extending α-Algorithm to Mine Duplicate Tasks in Process Logs. In: K.-C. Chang, W. Wang, L. Chen, C. Ellis, C.-H. Hsu, A. Tsoi, & H. Wang (Eds.) Advances in Web and Network Technologies, and Information Management (pringer, Berlin Heidelberg 2007).

Li, W., Fan, Y., Liu, W., Xin, M., Wang, H. & Jin, Q. (2019) A Self-Adaptive Process Mining Algorithm Based on Information Entropy to Deal With Uncertain Data. IEEE Access, 7, 131681-131691.

Măruşter, L., Weijters, A. J. M. M., van der Aalst, W. M. P., & Van Den Bosch, A. (2006). A Rule-Based Approach for Process Discovery: Dealing with Noise and Imbalance in Process Logs. Data Mining and Knowledge Discovery, 13(1), 67-87.

Prodel, M., Augusto, V., Jouaneton, B., Lamarsalle, L. & Xie, X. (2018). Optimal Process Mining for Large and Complex Event Logs. IEEE Transactions on Automation Science and Engineering, 15(3), 1309-1325.

Prodel, M., Augusto, V., Xie, X.,Jouaneton, B., & Lamarsalle, L. (2015). Discovery of patient pathways from a national hospital database using process mining and integer linear programming. in 2015 IEEE International Conference on Automation Science and Engineering (CASE). Gothenburg, 1409-1414

Roci, A., & Davidrajuh, R. (2018). A Polynomial-Time Alpha-Algorithm for Process Mining. International Journal of Simulation-Systems, Science & Technology, 19(5),12.1-12.7.

Sarno, R. & Sungkono, K. (2019). A survey of graph-based algorithms for discovering business processes. International Journal of Advances in Intelligent Informatics, 5(2), 137-149.

Sun, H., Du, Y., Qi, L., & He, Z. (2019). A Method for Mining Process Models With Indirect Dependencies via Petri Nets. IEEE Access, 7, 81211-81226.

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

van der Aalst, W. M. P., Adriansyah, A., & van Dongen, B. F. (2012). Replaying history on process models for conformance checking and performance analysis. WIREs Data Mining and Knowledge Discovery, 2(2), 182-192.

van der Aalst, W. M. P., Weijters, A. J. M. M., & Maruster, L. (2004). Workﬂow Mining: Discovering Process Models from Event Logs. IEEE Transactions on Knowledge and Data Engineering, 16(9), 1128–1142.

van der Werf, J. M. E. M., van Dongen, B. F., Hurkens, C. A. J., & Serebrenik, A. (2008). Process Discovery Using Integer Linear Programming. In: van Hee K.M., Valk R. (eds) Applications and Theory of Petri Nets (Springer, Berlin Heidelberg 2008).

van Zelst, S. J., van Dongen, B. F., & van der Aalst, W. M. P. (2015). ILP-Based Process Discovery Using Hybrid Regions. In Proceedings of the ATAED 2015 workshop. (pp. 47–61). CEUR-WS.org.

van Zelst, S. J., van Dongen, B. F., van der Aalst, W. M. P., & Verbeek, H. M. W. (2018). Discovering workflow nets using integer linear programming. Computing, 100(5), 529-556.

vanden Broucke, S. K. L. M., & De Weerdt, J. (2017). Fodina: A robust and flexible heuristic process discovery technique. Decision Support Systems, 100, 109-118.

Vidgof, M., Djurica, D., Bala, S. & Mendling, J. (2020). Cherry-Picking from Spaghetti: Multi-range Filtering of Event Logs. In: S. Nurcan, I. Reinhartz-Berger, P. Soffer, J. Zdravkovic (Ed.) Enterprise, Business-Process and Information Systems Modeling (Springer International Publishing, Cham 2020).

Weijters, A. J. M. M., van der Aalst, W. M. P., & alves de Medeiros, A. (2006). Process Mining with the Heuristics Miner-algorithm. BETA Working Paper Series WP, 166, Eindhoven University of Technology.

Weijters, A. J. M. M., & Ribeiro, J. T. S. (2011, April). Flexible Heuristics Miner (FHM). In 2011 IEEE Symposium on Computational Intelligence and Data Mining (CIDM) (pp. 310-317). IEEE.

Wen, L., van der Aalst, W. M. P., Wang, J., & Sun, J. (2007). Mining process models with non-free-choice constructs. Data Mining and Knowledge Discovery, 15(2), 145-180.

Wen, L., Wang, J., van der Aalst, W. M. P., Huang, B., & Sun, J. (2009). A novel approach for process mining based on event types. Journal of Intelligent Information Systems, 32(2), 163-190.

مطالعات مدیریت کسب و کار هوشمند

مدل برنامه‌ریزی ریاضی فرایندکاوی در مسئله کشف گراف وابستگی

مراجع

مراجع

دوره 9، شماره 33
آذر 1399
صفحه 217-246

مدل برنامه‌ریزی ریاضی فرایندکاوی در مسئله کشف گراف وابستگی

مراجع

مراجع

دوره 9، شماره 33آذر 1399صفحه 217-246

دوره 9، شماره 33
آذر 1399
صفحه 217-246