Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.12.2019 | Ausgabe 7/2019

Automatic Control and Computer Sciences 7/2019

Application of a Genetic Algorithm for Finding Edit Distances between Process Models

Zeitschrift:
Automatic Control and Computer Sciences > Ausgabe 7/2019
Autoren:
A. A. Kalenkova, D. A. Kolesnikov
Wichtige Hinweise
Translated by I. Tselishcheva

Abstract

Finding graph edit distances (determining the similarity of graph models) is an important task in various areas of computer science, such as image analysis, machine learning, and chemoinformatics. In recent years, due to the development of process mining techniques, it has become necessary to adapt the existing graph matching methods to be applied to the analysis of process models (annotated graphs) discovered from event logs of information systems. In particular, methods for finding the minimum graph edit distance can be used to reveal patterns (subprocesses) and to compare discovered process models. As was shown experimentally and theoretically substantiated, exact methods for finding the minimum edit distance between the discovered process models (and graphs in the general case) have a great time complexity and can be applied only to small-sized process models. In this paper, we estimate the accuracy and time performance characteristics of a genetic algorithm applied to find distances between process models discovered from the event logs. In particular, we find distances between BPMN (Business Process Model and Notation) models discovered from the event logs by using different synthesis algorithms. It is shown that the genetic algorithm proposed in the paper allows us to significantly reduce the computation time and produces results close to the optimal solutions (the minimum edit distances).

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 7/2019

Automatic Control and Computer Sciences 7/2019 Zur Ausgabe