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

Tavakoli Zaniani, Maryam; Gholamian, Mohammad Reza

doi:10.22054/IMS.2020.49943.1679

Document Type : Research Paper

Authors

¹ 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)

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

Abstract

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.

Keywords

References

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.

Business Intelligence Management Studies

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

References

References

Volume 9, Issue 33
December 2020
Pages 217-246

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

References

References

Volume 9, Issue 33December 2020Pages 217-246

Volume 9, Issue 33
December 2020
Pages 217-246