ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (9): 1920-1930.doi: 10.7544/issn1000-1239.2017.20160756

Previous Articles     Next Articles

Alignment Based Conformance Checking Algorithm for BPMN 2.0 Model

Wang Yuquan1, Wen Lijie1, Yan Zhiqiang2   

  1. 1(School of Software, Tsinghua University, Beijing 100084);2(School of Information, Capital University of Economics and Business, Beijing 100070)
  • Online:2017-09-01

Abstract: Process mining is an emerging discipline providing comprehensive sets of tools to provide fact-based insights and to support process improvements. This new discipline builds on process model-driven approaches and data-centric analysis techniques such as machine learning and data mining. Conformance checking approaches, i.e., techniques to compare and relate event logs and process models, are one of the three core process mining techniques. It is shown that conformance can be quantified and that deviations can be diagnosed. BPMN 2.0 model has so powerful expression ability that it can express complex patterns like multi-instance, sub-process, OR gateway and boundary event. However, there is no existing conformance checking algorithm supporting such complex patterns. To solve this problem, this paper proposes an algorithm (Acorn) for conformance checking for BPMN 2.0 model, which supports aforesaid complex patterns. The algorithm uses A\+* algorithm to find the minimum cost alignment, which is used to calculate fitness between BPMN 2.0 model and the log. In addition, virtual cost and expected cost are introduced for optimization. Experimental evaluations show that Acorn can find the best alignment by exploiting the meanings of BPMN 2.0 elements correctly and efficiently, and the introduction of virtual cost and expectation cost indeed reduces the search space.

Key words: BPMN 2.0 model, complex pattern, A\+* search, conformance checking, alignment

CLC Number: