Диссертация (1137084)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

National Research University Higher School of EconomicsFaculty of Computer ScienceManuscriptAlexey Alexandrovich MitsyukStructure-Preserving Process Model Repair Based on Event LogsPh.D. Dissertationfor the purpose of obtainingDoctor of Philosophy in Computer Science HSEAcademic Supervisor:Doctor of Science, ProfessorIrina A. LomazovaMoscow — 20192ContentsIntroduction .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.11.21.31.4Basic Notions . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .231.1.1Multisets, Functions, Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . .231.1.2Process Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .241.1.3Event Logs . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .26Overview of Process Mining Techniques . . . . . . . . . . . . . . . . . . . . . . . . . .291.2.1Process Discovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . .301.2.2Conformance Checking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .34Process Model Repair: Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . .401.3.1Process Model Repair using Event Logs . . . . . . . . . . . . . . . . . . . . . .411.3.2Impact-Driven Model Repair . . .

. . . . . . . . . . . . . . . . . . . . . . . . .431.3.3Improving Structured Business Process Models using Event Logs . . . . . .431.3.4Interactive and Incremental Business Process Model Repair . . . . . . . . . .441.3.5Automated Error Correction of Business Process Models . . . . .

. . . . . .451.3.6Other Model Repair Techniques . . . . . . . . . . . . . . . . . . . . . . . . . .451.3.7Process Model Simplification . . . . . . . . . . . . . . . . . . . . . . . . . . . .47Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . .472 Process Model Repair using Decomposition . . . . . . . . . . . . . . . . . . . . . . 492.1Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .492.2Modular Technique for Process Model Repair . . . . . . . . .

. . . . . . . . . . . . . .502.3Modular Repair using Maximal Decomposition . . . . . . . . . . . . . . . . . . . . . .552.4Improved Algorithm for Local Process Model Repair . . . . . . . . . . . . . . . . . .622.5Non-Local Repair of Process Models . . . . . . . . . . . . . . . . . . . . .

. . . . . . .682.6Process Model Decomposition: Related Work . . . . . . . . . . . . . . . . . . . . . . .722.7Discussion and Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .733 Generating Artificial Event Logs .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . 753.1Event Log Generation Techniques: Related Work . . . . . . . . . . . . . . . . . . . . .763.2Generating Event Logs for Petri nets . . . . . . . . . . . . . . . . . . . . . . . . . . . .8033.33.43.2.1Algorithms for Event Log Generation . . . . . . . . . . . . .

. . . . . . . . . .813.2.2Tool Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .863.2.3Tool Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .90Generating Event Logs for BPMN 2.0 Models . . . . . . . . . . . . . . . . . . . . . .933.3.1Algorithms for Event Log Generation . . . .

. . . . . . . . . . . . . . . . . . . 1023.3.2Tool Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1083.3.3Tool Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110Conclusions . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1134 Implementation and Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1154.1Prototype Tool Description . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1154.2Description of the Experiment and Input Data . . . . . . . . . . . . . .

. . . . . . . . 1244.3Experimental Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1264.44.3.1Local Process Model Repair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1284.3.2Non-Local Process Model Repair . . . . . . . . . . . . . . . . . . . . . . . . . . 1474.3.3Repair of Larger Process Models .

. . . . . . . . . . . . . . . . . . . . . . . . . 155Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163Acknowledgments . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184List of Tables . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1894IntroductionWe can not imagine our life without information systems. Processes in different domains(information technology, banking, healthcare, industrial production etc.) are supported by softwaresystems that store and transform data related to these processes. That is why the concept ofprocess-aware information systems emerged in recent years [1, 2]. Systems of that type are basedon core models describing process nature.Complex software and information systems can be designed using model-driven softwareengineering approaches [3,4]. They involve designing a system structure and processes using formalmodelling notations, and then implementing carefully elaborated blueprints in code.

However, theexact implementation of a prescriptive design model in real-life systems is a rare case. Moreover,processes tend to evolve and erode during the system’s life-cycle. That is why a description of areal system’s structure and behaviour usually differs from its design model.System owners want relevant, up-to-date models describing structure and behaviour of theirsystem according to real processes which are executed with this systems’ support. This leadsto the development of different methods to reverse engineer a system, analyse its structure andbehaviour.In particular, the real behaviour of a software system can be studied by analysing its event logs.Process mining [5] is a field of research and technology that proposes algorithms and methods forthis kind of an analysis.

One can discover the model of a real system from event logs. Moreover,process engineers can diagnose the discrepancies between observed (event logs) and modelled(process models) behaviours using conformance checking techniques.Conformance information can be used to improve or enhance models. For instance, it is possibleto repair process model using event logs [6], i.e.

to construct a new process model which is basedon a given initial model but conforms better to a given event log. Using process model repairtechniques a system owner may keep a process model up-to-date. This thesis is devoted to aconstruction of such algorithms.Process model repair aims at improving the quality of a model1 with an additional constraint.The repair should change as few model parts as possible, thus preserving its structure. The latterdiffers model repair from process discovery, where the goal is to synthesize a model based onthe given event log such that this model meets specified conformance characteristics.

Thus, model1A model quality is calculated according to some quality criteria. In particular, a model needs to conform to agiven event log.5repair is applied when existing process model is of value, and its owner does not want to completelyre-build it.The problem can be illustrated with the following example. Figure 1 shows a process modelthat does not fit2 the observed behaviour of a system. In particular, its fitness according to theevent log is 0,97 (where 1 is perfect fitness).Figure 1: Given process modelWe may apply one of process discovery algorithms, and synthesize a completely new modelperfectly fitting the same log. For example, Figure 2 shows a model that has been discovered usingInductive miner with a zero noise threshold from the event log.Figure 2: Model discovered from scratch using the Inductive minerThis model perfectly fits the event log.

It models the same process with the same set ofactivities, and contains transitions with labels from the same set as the initial model. However,these models are structurally different. Note that the fitness of the initial model is almost perfect.Thus, inconsistencies in it are not serious. Virtually, the model shown in Figure 1 can be repairedreplacing two of its elements (transitions). Such problems do not always need the complete rediscovery. Often, they can be repaired without substantial change in the model.In such a case, structure-preserving algorithms are relevant. This type of model repair is difficultbecause it needs to find a balance between necessary conformance to an event log, and desire topreserve a structure of the initial model.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов диссертации