maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2018-6-711-725mais-768Research ArticleОригинальные статьиArticlesПрименение генетического алгоритма для нахождения редакционного расстояния между моделями процессовApplication of Genetic Algorithms for Finding Edit Distance between Process Modelshttps://orcid.org/0000-0002-5088-7602КаленковаАнна АлексеевнаKalenkovaAnna A.

ст. науч. сотр., лаборатория ПОИС

ул. Мясницкая, 20, г. Москва, 101000

senior research fellow, Laboratory of Process-Aware Information Systems

20 Myasnitskaya St., Moscow 101000

akalenkova@hse.ruhttps://orcid.org/0000-0002-9010-8415КолесниковДанил АлександровичKolesnikovDanil A.

студент, факультет компьютерных наук

ул. Мясницкая, 20, г. Москва, 101000

student, Faculty of Computer Science

20 Myasnitskaya St., Moscow 101000

dakolesnikov@edu.hse.ruНациональный исследовательский университет «Высшая школа экономики»РоссияNational Research University Higher School of EconomicsRussian Federation201819122018256711725Copyright © Каленкова А.А., Колесников Д.А., 20182018Каленкова А.А., Колесников Д.А.Kalenkova A.A., Kolesnikov D.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/768

Поиск редакционного расстояния между графовыми моделями (определение схожести графовых моделей) является важной задачей в различных областях компьютерных наук, таких как анализ изображений, машинное обучение, химическая информатика. В последнее время, в связи с развитием методов извлечения и анализа процессов, появилась необходимость в адаптации существующих методов сравнения графовых моделей для анализа моделей процессов (аннотированных графов), извлекаемых из логов событий информационных систем. Методы нахождения минимального редакционного расстояния между графами могут быть использованы для обнаружения шаблонов (подпроцессов), а также для сравнения извлекаемых моделей процессов. Как было показано экспериментально и теоретически обосновано, точные методы нахождения минимального редакционного расстояния между извлекаемыми моделями процессов (и графами в общем случае) имеют большую временную сложность и могут быть применены лишь к небольшим моделям процессов. В этой статье мы оцениваем точность и временные характеристики генетического алгоритма, применяемого для нахождения расстояний между моделями процессов, извлекаемых из логов событий. В частности мы находим расстояния между BPMN (Business Process Model and Notation) моделями, извлекаемыми из логов событий с помощью различных алгоритмов синтеза. В этой работе показано, что представленный генетический алгоритм позволяет в значительной степени уменьшить время вычислений, при этом показывая результаты, близкие к оптимальным (минимальным редакционным расстояниям).

Finding graph-edit distance (graph similarity) is an important task in many computer science areas, such as image analysis, machine learning, chemicalinformatics. Recently, with the development of process mining techniques, it became important to adapt and apply existing graph analysis methods to examine process models (annotated graphs) discovered from event data. In particular, finding graph-edit distance techniques can be used to reveal patterns (subprocesses), compare discovered process models. As it was shown experimentally and theoretically justified, exact methods for finding graph-edit distances between discovered process models (and graphs in general) are computationally expensive and can be applied to small models only. In this paper, we present and assess accuracy and performance characteristics of an inexact genetic algorithm applied to find distances between process models discovered from event logs. In particular, we find distances between BPMN (Business Process Model and Notation) models discovered from event logs by using different process discovery algorithms. We show that the genetic algorithm allows us to dramatically reduce the time of comparison and produces results which are close to the optimal solutions (minimal graph edit distances calculated by the exact search algorithm).

минимальное редакционное расстояние между графамиизвлечение и анализ процессовBPMN (Business Process Model and Notation)генетический алгоритмminimal graph edit distanceprocess miningBPMN (Business Process Model and Notation)genetic algorithmИсследование выполнено при поддержке Гранта Президента РФ для молодых российских ученых — кандидатов наук MK-4188.2018.9.This work was funded by the President Grant MK-4188.2018.9.ReferencesVan der Aalst W.M.P., Process Mining — Data Science in Action, Second Edition, Springer, 2016.Van der Aalst W.M.P., Process Mining — Data Science in Action, Second Edition, Springer, 2016.Van der Aalst W. M. P., Weijters T., Maruster L., “Workflow Mining: Discovering Process Models from Event Logs”, IEEE Transactions on Knowledge and Data Engineering, 16:9 (2004), 1128–1142.Van der Aalst W. M. P., Weijters T., Maruster L., “Workflow Mining: Discovering Process Models from Event Logs”, IEEE Transactions on Knowledge and Data Engineering, 16:9 (2004), 1128–1142.Leemans S. J. J., Fahland D., van der Aalst W. M. P., “Discovering Block-Structured Process Models from Incomplete Event Logs”, Application and Theory of Petri Nets and Concurrency, Lecture Notes in Computer Science, 8489, Springer, 2014, 91–110.Leemans S. J. J., Fahland D., van der Aalst W. M. P., “Discovering Block-Structured Process Models from Incomplete Event Logs”, Application and Theory of Petri Nets and Concurrency, Lecture Notes in Computer Science, 8489, Springer, 2014, 91–110.Kalenkova A.A., Ageev A.A., Lomazova I.A., van der Aalst W.M.P., “E-Government Services: Comparing Real and Expected User Behavior”, Business Process Management Workshops, Springer International Publishing, 2018, 484–496.Kalenkova A.A., Ageev A.A., Lomazova I.A., van der Aalst W.M.P., “E-Government Services: Comparing Real and Expected User Behavior”, Business Process Management Workshops, Springer International Publishing, 2018, 484–496.Garey M. R., Johnson D. S., Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., 1990, ISBN: 0716710455.Garey M. R., Johnson D. S., Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., 1990, ISBN: 0716710455.Ivanov S. Y., Kalenkova A. A., van der Aalst W. M. P., “BPMNDiffViz: A Tool for BPMN Models Comparison”, Proceedings of the BPM Demo Session 2015 Co-located with the 13th International Conference on Business Process Management (BPM 2015) (Innsbruck, Austria, September 2, 2015), 2015, 35–39.Ivanov S. Y., Kalenkova A. A., van der Aalst W. M. P., “BPMNDiffViz: A Tool for BPMN Models Comparison”, Proceedings of the BPM Demo Session 2015 Co-located with the 13th International Conference on Business Process Management (BPM 2015) (Innsbruck, Austria, September 2, 2015), 2015, 35–39.Hart P.E, Nilsson N.J, Raphael B., “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, 4:2 (1968), 100–107.Hart P.E, Nilsson N.J, Raphael B., “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, 4:2 (1968), 100–107.Business Process Model and Notation (BPMN), Object Management Group, formal/2013-12-09, 2013.Business Process Model and Notation (BPMN), Object Management Group, formal/2013-12-09, 2013.Cross A. D. J., Wilson R. C., Hancock E. R., “Inexact Graph Matching Using Genetic Search”, Pattern Recognition, 30:6 (1997), 953 – 970.Cross A. D. J., Wilson R. C., Hancock E. R., “Inexact Graph Matching Using Genetic Search”, Pattern Recognition, 30:6 (1997), 953 – 970.Riesen K., Fischer A., Bunke H., “Improving Approximate Graph Edit Distance Using Genetic Algorithms”, Structural, Syntactic, and Statistical Pattern Recognition, Springer Berlin Heidelberg, 2014, 63–72.Riesen K., Fischer A., Bunke H., “Improving Approximate Graph Edit Distance Using Genetic Algorithms”, Structural, Syntactic, and Statistical Pattern Recognition, Springer Berlin Heidelberg, 2014, 63–72.Kalenkova A. A., van der Aalst W. M. P., Lomazova I. A., Rubin V. A., “Process Mining Using BPMN: Relating Event Logs and Process Models”, Software & Systems Modeling, 16:4 (2017), 1019–1048.Kalenkova A. A., van der Aalst W. M. P., Lomazova I. A., Rubin V. A., “Process Mining Using BPMN: Relating Event Logs and Process Models”, Software & Systems Modeling, 16:4 (2017), 1019–1048.Levenshtein V. I., “Binary Codes Capable of Correcting Deletions, Insertions and Reversals”, Soviet Physics Doklady, 10 (1966), 707.Levenshtein V. I., “Binary Codes Capable of Correcting Deletions, Insertions and Reversals”, Soviet Physics Doklady, 10 (1966), 707.Гладков Л.А., Курейчик В.В, Курейчик В.М., Генетические алгоритмы, Физматлит, М., 2010, 368 с.;Gladkov L. A., Kureichik V. V., Kureichik V. M., Genetic Algorithms, Fizmatlit, Moscow, 2010, 368 pp., (in Russian).

The authors declare that there are no conflicts of interest present.