Research On Alignment Approaches Based On Workflow Nets And Event Logs

The goal of process mining is to discover,monitor and improve actual business processes by extracting valuable information from event logs.The research of process mining is of great significance for deploying new business processes as well as analyzing and improving the already deployed ones.In recent years,process mining is a hot issue in related field at home and abroad.The application categories of process mining include process discovery,conformance checking,process enhancement,and so on.Conformance checking compares events in event logs with activities in process models in order to find the similarities and discrepancies between observed behaviors and modeled behaviors.Alignment is a main approach of conformance checking between traces in event logs and process models,and it can accurately fix the locations of deviations.The existing alignment approaches can obtain all the alignment results between event logs and process models,but their execution procedures are very complex.Based on the intensive study of the existing alignment approaches,the key contributions of this thesis are as follows:(1)On the basis of the research on the similarities and differences of log moves,model moves and synchronous moves between optimal alignments,the definitions of similar optimal alignments are given.Meanwhile,several properties of similar optimal alignments are analyzed,and some theorems and corollaries are proved.The similar relations between optimal alignments are given,and a partition of the optimal alignment set can be determined according to the relations.A representative of every partition is chosen to represent all the deviations,which can simplify the optimal alignment set.A multi-phase alignment algorithm is presented based on four basic patterns of workflow nets.The algorithm is suitable for block-structure process models which can be segmented.All the representatives of similar optimal alignments between process models and restricted traces can be obtained by the algorithm.(2)To improve the efficiency of calculating optimal alignments,a new alignment approach based on optimal alignment trees is presented between event logs and process models based on workflow nets.The approach compares the relations between events and activities by observing the behaviors in event logs and firing the transitions in process models.Meanwhile,the current states of logs and models are recorded as well as the compared results.Then an optimal alignment tree is generated.In this tree,every path from the initial node to the final node stands for an optimal alignment.The approach simplifies the procedures to align observed behaviors with modeled behaviors.However,due to too much nodes generated in the tree,the approach is only applicable to the models and the traces studied in this thesis or the simpler ones.(3)A rapid and reduced alignment approach based on optimal alignment graphs is proposed to improve the previous approach.The approach reduces the number of nodes in the search space to a great extent,and it is suitable for a wider range of models and traces.According to this approach,an optimal alignment graph is generated.In this graph,the paths from the source node to the target node include all of the optimal alignments.A specific and rigorous characterization is given to illustrate the availability of this approach,and its reasonability and validity are proved theoretically.(4)To resolve the problem that existing alignment algorithms can obtain the alignments between only one trace and process models,an alignment approach between batch of traces and process models is presented.A transition system is generated by the approach,which includes all the optimal alignments between multi traces and process models.An optimal alignment between each trace in original event logs and process models could be obtained by A+ algorithm,and all the optimal alignments between each trace in original event logs and process models could be obtained by A++algorithm.The complexity of the approach is analyzed and its validity is proved theoretically.All the approaches mentioned above are implemented,and a large number of event logs and process models are used to evaluate the effectiveness comprehensively.After a series of the simulation experiments,the robustness and applicability of the proposed approaches are verified.