Efficient Deviation Detection Between a Process Model and Event Logs

Lu Wang; Yuyue Du; Liang Qi

doi:10.1109/JAS.2019.1911750

Volume 6 Issue 6

Nov. 2019

IEEE/CAA Journal of Automatica Sinica

JCR Impact Factor: 15.3, Top 1 (SCI Q1)

CiteScore: 23.5, Top 2% (Q1)
Google Scholar h5-index: 77， TOP 5

Turn off MathJax

Article Contents

Article Navigation > IEEE/CAA Journal of Automatica Sinica > 2019 > 6(6): 1352-1364

Lu Wang, Yuyue Du and Liang Qi, "Efficient Deviation Detection Between a Process Model and Event Logs," IEEE/CAA J. Autom. Sinica, vol. 6, no. 6, pp. 1352-1364, Nov. 2019. doi: 10.1109/JAS.2019.1911750

Citation:

Lu Wang, Yuyue Du and Liang Qi, "Efficient Deviation Detection Between a Process Model and Event Logs," IEEE/CAA J. Autom. Sinica, vol. 6, no. 6, pp. 1352-1364, Nov. 2019. doi: 10.1109/JAS.2019.1911750

Citation:

PDF( 1319 KB)

Efficient Deviation Detection Between a Process Model and Event Logs

doi: 10.1109/JAS.2019.1911750

Funds: This work was supported by the National Natural Science Foundation of China (61170078, 61472228, 61903229, 61902222), the “Taishan Scholar” Construction Project of Shandong Province, China, the Natural Science Foundation of Shandong Province (ZR2018MF001), the Scientific Research Foundation of Shandong University of Science and Technology for Recruited Talents (2017RCJJ044), and the Key Research and Development Program of Shandong Province (2018GGX101011)

More Information

Author Bio:
Lu Wang received the B.S. and Ph.D. degrees at the College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao, China, in 2013 and 2018, respectively. She is currently a Lecturer of computer science and technology at Shandong University of Science and Technology, Qingdao, China. Her current research interests include process mining, Petri nets, and workflow

Yuyue Du received the B.S. degree from Shandong University, Jinan, China, in 1982, the M.S. degree from Nanjing University of Aeronautics and Astronautics, Nanjing, China, in 1991, and the Ph.D. degree in computer application from Tongji University, Shanghai, China, in 2003. He is currently a Professor at the College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao, China. He is a member of Professional Committee of Petri Nets of China Computer Federation. His research interests include formal engineering, Petri nets, real-time systems, web services, and workflows. He has taken in over ten projects supported by National Nature Science Foundation of China, National Key Basic Research Developing Program of China and other important and key projects at provincial levels. He has published more than 140 papers in domestic and international academic publications, and they are embodied more than 80 times by SCI and EI, cited more than 270 times by others

Liang Qi (S’16–M’18) received the B.S. degree in information and computing science and M.S. degree in computer software and theory from Shandong University of Science and Technology, Qingdao, China, in 2009 and 2012, respectively. He received the Ph.D. degree in computer software and theory from Tongji University, Shanghai, China in 2017. He is currently a Lecturer of computer science and technology at Shandong University of Science and Technology, Qingdao, China. From 2015 to 2017, he was a visiting student in the Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ, USA. He has (co)-authored over 45 technical papers in journals and conference proceedings, including IEEE Transactions on System, Man and Cybernetics: Systems, IEEE Transactions on Intelligent Transportation Systems, IEEE/CAA Journal of Automatica Sinica, and Enterprise Information Systems. He received the Best Student Paper Award-Finalist in the 15th IEEE International Conference on Networking, Sensing and Control (ICNSC’2018). His current research interests include Petri nets, discrete event systems, process mining, and optimization algorithms
Corresponding author: L. Wang and L. Qi are with the College of Computer Science and Engineering, Shandong University of Science and Technology, Qingdao 266590, China (e-mail: wanglu253@126.com; qiliangsdkd@163.com)
¹http://pan.baidu.com/s/1qYp0GrU
²http://pan.baidu.com/s/1c2nNrFE
Received Date: 2018-01-30
Revised Date: 2018-05-17
Accepted Date: 2018-07-19

Available Online: 2019-09-24

Abstract

Abstract

Business processes described by formal or semi-formal models are realized via information systems. Event logs generated from these systems are probably not consistent with the existing models due to insufficient design of the information system or the system upgrade. By comparing an existing process model with event logs, we can detect inconsistencies called deviations, verify and extend the business process model, and accordingly improve the business process. In this paper, some abnormal activities in business processes are formally defined based on Petri nets. An efficient approach to detect deviations between the process model and event logs is proposed. Then, business process models are revised when abnormal activities exist. A clinical process in a healthcare information system is used as a case study to illustrate our work. Experimental results show the effectiveness and efficiency of the proposed approach.
- Detect deviations,
- event log,
- model repair,
- Petri net,
- process model

FullText(HTML)

¹http://pan.baidu.com/s/1qYp0GrU
²http://pan.baidu.com/s/1c2nNrFE

References(38)

References

[1]	D. L. Olson and S. Kesharwani, " Enterprise information systems: Contemporary trends and issues,” World Scientific, vol. 2, pp. 13–16, 2010.
[2]	W. M. P. van der Aalst, Process Mining: Discovery, Conformance and Enhancement of Business Processes. Berlin Heidelberg: Springer Verlag, 2011, pp. 1–10.
[3]	W. Song, X. Xia, H. A. Jacobsen, P. Zhang, and H. Hu, " Efficient alignment between event logs and process models,” IEEE Trans. Services Computing, vol. 10, no. 1, pp. 1939–1374, 2017.
[4]	P. Weber, B. Bordbar, and P. Tino, " A framework for the analysis of process mining algorithms,” IEEE Trans. Systems Man and Cybernetics Systems, vol. 43, no. 2, pp. 303–317, 2013.
[5]	W. M. P. van der Aalst, T. Weijters, and L. Maruster, " Workflow mining: discovering process models from event logs,” IEEE Trans. Knowledge and Data Engineering, vol. 16, no. 9, pp. 1128–1142, 2004.
[6]	M. Weidlich, A. Polyvyanyy, N. Desai, J. Mendling, and M. Weske, " Process compliance analysis based on behavioural profiles,” Information Systems, vol. 36, no. 7, pp. 1009–1025, 2011. doi: 10.1016/j.is.2011.04.002
[7]	A. Rozinat, and W. M. P. van der Aalst, " Conformance checking of processes based on monitoring real behavior,” Information Systems, vol. 33, no. 1, pp. 64–95, 2008. doi: 10.1016/j.is.2007.07.001
[8]	L. Wang and Y. Y. Du, " An alignment-based identifying method of the problem areas within process models,” J. Shandong University of Science and Technology (Nature Science), vol. 34, no. 1, pp. 42–46, 53, 2015.
[9]	R. Lenz and M. Reichert, " IT support for healthcare processes – premises, challenges, perspectives,” Data and Knowledge Engineering, vol. 61, no. 1, pp. 39–58, 2007.
[10]	M. Poulymenopoulou, F. Malamateniou, and G. Vassilacopoulos, " Specifying workflow process requirements for an emergency medical service,” J. Medical Systems, vol. 27, no. 4, pp. 325–335, 2003. doi: 10.1023/A:1023701219563
[11]	K. Anyanwu, A. Sheth, J. Cardoso, J. Miller, and K. Kochut, " Healthcare enterprise process development and integration,” J. Research and Practice in Information Technology, vol. 35, no. 2, pp. 83–98, 2003.
[12]	R. Álvaro and D. R. Ferreira, " Business process analysis in healthcare environments: a methodology based on process mining,” Information Systems, vol. 37, no. 2, pp. 99–116, 2012. doi: 10.1016/j.is.2011.01.003
[13]	A. Rodrguez, E. Fernndez-Medina, and M. Piattini, " A BPMN extension for the modeling of security requirements in business processes,” IEICE Trans. Information and Systems, vol. 90, no. 4, pp. 745–752, 2007.
[14]	W. M. P. van der Aalst, " Formalization and verification of event-driven process chains,” Information and Software Technology, vol. 41, no. 10, pp. 639–650, 1999. doi: 10.1016/S0950-5849(99)00016-6
[15]	T. Murata, " Petri nets: properties, analysis and applications,” Proc. IEEE, vol. 77, no. 4, pp. 541–580, 1989. doi: 10.1109/5.24143
[16]	L. Qi, M. C. Zhou, and W. J. Luan, " A two-level traffic light control strategy for preventing incident-based urban traffic congestion,” IEEE Trans. Intelligent Transportation Systems, vol. 19, no. 1, pp. 13–24, 2018. doi: 10.1109/TITS.2016.2625324
[17]	C. Liu, Q. T. Zeng, H. Duan, M. C. Zhou, F. M. Lu, and J. J. Cheng, " E-net modeling and analysis of emergency response processes constrained by resources and uncertain durations,” IEEE Trans. Systems,Man,and Cybernetics:Systems, vol. 45, no. 1, pp. 84–96, 2015. doi: 10.1109/TSMC.2014.2330555
[18]	L. Qi, M. C. Zhou, and W. J. Luan, " Impact of driving behavior on traffic delay at a congested signalized intersection,” IEEE Trans. Intelligent Transportation Systems, vol. 18, no. 7, pp. 1882–1893, 2017. doi: 10.1109/TITS.2016.2613598
[19]	X. Y. Cong, M. P. Fanti, A. M. Mangini, and Z. W. Li, " Decentralized diagnosis by Petri nets and integer linear programming,” IEEE Trans. Systems Man and Cybernetics Systems, vol. 50, no. 1, pp. 13624–13629, 2017.
[20]	Y. X. Teng, Y. Y. Du, L. Qi, and W. J. Luan, " A logic Petri net-based method for repairing process models with concurrent blocks,” IEEE Access, vol. 7, pp. 8266–8282, 2018.
[21]	J. J. Cheng, C. Liu, M. C. Zhou, Q. T. Zeng, and A. Ylä-Jääski, " Automatic composition of semantic web services based on fuzzy predicate petri nets,” IEEE Trans. Autom. Science and Engineering, vol. 12, no. 2, pp. 680–689, 2015. doi: 10.1109/TASE.2013.2293879
[22]	Y. Y. Du, L. Qi, and M. C. Zhou, " Analysis and application of logical Petri nets to E-commerce systems,” IEEE Trans. Systems,Man,and Cybernetics:Systems, vol. 44, no. 4, pp. 468–481, 2014. doi: 10.1109/TSMC.2013.2277696
[23]	D. Xiang, G. Liu, C. Yan, and C. Jiang, " Detecting data-flow errors based on Petri nets with data operations,” IEEE/CAA J. Autom. Sinica, vol. 5, no. 1, pp. 251–4118, 2016. doi: 10.1109/ACCESS.2016.2597061
[24]	Y. Y. Du, L. Wang, and M. Qi, " Constructing service clusters based on service space,” International J. Parallel Programming, vol. 45, no. 4, pp. 982–1000, 2017. doi: 10.1007/s10766-016-0437-2
[25]	X. Y. Lu, M. C. Zhou, A. C. Ammari, and J. C. Ji, " Hybrid Petri nets for modeling and analysis of microgrid systems,” IEEE/CAA J. Autom. Sinica, vol. 3, no. 4, pp. 349–356, 2016. doi: 10.1109/JAS.2016.7510070
[26]	G. J. Liu, " Some complexity results for the soundness problem of workflow nets,” IEEE Trans. Services Computing, vol. 7, no. 2, pp. 322–328, 2014. doi: 10.1109/TSC.2013.36
[27]	G. J. Liu, " Complexity of the deadlock problem for Petri nets modeling resource allocation systems,” Information Sciences, vol. 363, pp. 190–197, 2016. doi: 10.1016/j.ins.2015.11.025
[28]	M. Petković, D. Prandi, and N. Zannone, " Purpose control: did you process the data for the intended purpose?” VLDB Int. Conf. Secure Data Management, pp. 145–168, 2011.
[29]	A. Rozinat, M. Veloso, and W. M. P. van der Aalst., " Using hidden Markov models to evaluate the quality of discovered process models.,” Technical Report,BPMcenter.org BPM Center Report BPM, pp. 8–10, 2008.
[30]	M. D. Leoni, F. M. Maggi, and W. M. P. van der Aalst, " An alignment-based framework to check the conformance of declarative process models and to preprocess event-log data,” Information Systems, vol. 47, no. 3, pp. 258–277, 2014.
[31]	A. Adriansyah, B. F. van Dongen, and W. M. P. van der Aalst, " Conformance checking using cost-based fitness analysis,” in Proc. 15th IEEE Int. Enterprise Distributed Object Computing Conf., pp. 55–64, 2011.
[32]	L. Wang, Y. Y. Du, and W. Liu, " Aligning observed and modelled behaviour based on workflow decomposition,” Enterprise Information Systems, vol. 11, no. 8, pp. 1207–1227, 2017. doi: 10.1080/17517575.2016.1193633
[33]	M. De Leoni, and W. M. P. van der Aalst, " Aligning event logs and process models for multi-perspective conformance checking: an approach based on integer linear programming,” Int. Conf. Business Process Management, pp. 113–129, 2013.
[34]	D. Fahland, and W. M. P. van der Aalst, " Model repair-aligning process models to reality,” Information Systems, vol. 47, no. 1, pp. 220–243, 2015.
[35]	J. Wang, S. Song, X. Lin and J. Pei, " Cleaning structured event logs: a graph repair approach,” in Proc. IEEE, Int. Conf. Data Engineering, pp. 30–41, 2015.
[36]	J. Wang, S. Song, X. Zhu, and X. Lin, " Efficient recovery of missing events,” Proc. the VLDB Endowment, vol. 6, no. 10, pp. 841–852, 2013. doi: 10.14778/2536206.2536212
[37]	S. J. J. Leemans, D. Fahland, and W. M. P. van der Aalst, " Discovering block-structured process models from event logs: a constructive approach,” Application and Theory of Petri Nets and Concurrency, pp. 311–329, 2013.
[38]	J. Li, Y. Fan, and M. Zhou, " Timing constraint workflow nets for workflow analysis,” IEEE Trans. Systems,Man,and Cybernetics,Part A, vol. 33, no. 2, pp. 179–93, 2003. doi: 10.1109/TSMCA.2003.811771

Supplements(0)

Cited By

Proportional views

Proportional views

通讯作者: 陈斌, bchen63@163.com

1.
沈阳化工大学材料科学与工程学院沈阳 110142

Figures(12) / Tables(2)

Get Citation

PDF

XML

Article Metrics

Article views (1342) PDF downloads(58)

Highlights

By comparing an existing process model with event logs, we can detect inconsistencies called deviations, verify and extend the business process model, and accordingly improve the business process. In this paper, some abnormal activities in business processes are formally defined based on Petri nets.
Given a block-structured process model and a trace that does not conform to the process model, their deviations, can be obtained in a formal way. An efficient approach to detect deviations between them is proposed. The approach can find all the abnormal activities, namely missing, additional and dislocated activities, in traces.
When the deviations between a process model and an event log are obtained, we can repair the process model accordingly. The missing activities should be removed from the process model; the additional ones should be inserted into the process model; and for the dislocated ones, the structure of the process model should be changed.

Efficient Deviation Detection Between a Process Model and Event Logs

doi: 10.1109/JAS.2019.1911750

Abstract

References

Proportional views

Catalog

通讯作者: 陈斌, bchen63@163.com

Article Metrics

Highlights

Export File

Citation

Format

Content