maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2017-4-459-480mais-535Research ArticleОригинальные статьиArticlesИспользование журналов событий для локальной корректировки моделей процессовUsing Event Logs for Local Correction of Process Modelshttps://orcid.org/0000-0003-2352-3384МицюкАлексей АлександровичMitsyukAlexey A.

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

research fellow, Laboratory of Process-Aware Information Systems

amitsyuk@hse.ruhttps://orcid.org/0000-0002-9420-3751ЛомазоваИрина АлександровнаLomazovaIrina A.

д-р физ.-мат. наук, профессор, лаборатория ПОИС

doctor of sciences, professor, Laboratory of Process-Aware Information Systems

ilomazova@hse.ruhttps://orcid.org/0000-0002-0955-6940ван дер АалстВил М.П.Van der AalstWil M.P.

профессор, группа «Архитектура информационных систем»

PhD, dr.ir., professor, Architecture of Information Systems

w.m.p.v.d.aalst@tue.nlНациональный исследовательский университет «Высшая школа экономики»РоссияNational Research University Higher School of EconomicsRussian FederationТехнический университет Эйндховена (TU/e)НидерландыEindhoven University of Technology (TU/e)Netherlands201731082017244459480Copyright © Мицюк А.А., Ломазова И.А., ван дер Аалст В., 20172017Мицюк А.А., Ломазова И.А., ван дер Аалст В.Mitsyuk A.A., Lomazova I.A., van der Aalst W.Данная работа распространяется под лицензией 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/535

В ходе жизненного цикла информационной системы (ИС) ее реальное поведение может перестать соответствовать исходной модели системы. Между тем для поддержки системы очень важно иметь актуальную модель, отражающую текущее поведение системы. Для корректировки модели можно использовать информацию из журнала событий системы. Журналы событий процессно-ориентированных информационных систем содержат запись истории исполнения поддерживаемых процессов в виде более или менее детальных списков событий. Такие журналы, как правило, записываются всеми современным ИС. Эта информация может использоваться для анализа реального поведения ИС и ее усовершенствования. В работе рассматривается задача корректировки (исправления) модели процесса на основе информации из журнала событий. Исходными данными для этой задачи являются первоначальная модель процесса в виде сети Петри и журнал событий. Результатом корректировки должна быть новая модель процесса, лучше отображающая реальное поведение ИС, чем исходная модель. Актуальная модель может быть построена и полностью заново, например, с помощью одного из известных алгоритмов автоматического синтеза модели процесса по журналу событий. Однако структура исходной модели при этом может полностью измениться. Полученную модель будет трудно сопоставить с прежней моделью процесса, что затруднит ее понимание и анализ. Поэтому при корректировке модели важно по возможности сохранить ее прежнюю структуру. Предлагаемый в настоящей работе алгоритм корректировки модели основан на принципе «разделяй и властвуй». Исходная модель процесса декомпозируется на фрагменты. Для каждого из фрагментов проверяется, соответствует ли он актуальному журналу событий. Фрагменты, для которых выявлены несоответствия, заменяются на заново синтезированные. Новая модель собирается из фрагментов путем слияния переходов. Проведенные эксперименты показывают, что наш алгоритм корректировки дает хорошие результаты, если применяется для исправления локальных несоответствий. Работа содержит описание алгоритма, формальное обоснование его корректности, а также результаты экспериментального тестирования на искусственных примерах. 

During the life-cycle of an Information System (IS) its actual behaviour may not correspond to the original system model. However, to the IS support it is very important to have the latest model that reflects the current system behaviour. To correct the model, the information from the event log of the system may be used. In this paper, we consider the problem of process model adjustment (correction) using the information from an event log. The input data for this task are the initial process model (a Petri net) and the event log. The result of correction should be a new process model, better reflecting the real IS behavior than the initial model. The new model could be also built from scratch, for example, with the help of one of the known algorithms for automatic synthesis of the process model from an event log. However, this may lead to crucial changes in the structure of the original model, and it will be difficult to compare the new model with the initial one, hindering its understanding and analysis. It is important to keep the initial structure of the model as much as possible. In this paper, we propose a method for process model correction based on the principle of “divide and conquer”. The initial model is decomposed in several fragments. For each fragment its conformance to the event log is checked. Fragments which do not match the log are replaced by newly synthesized ones. The new model is then assembled from the fragments via transition fusion. The experiments demonstrate that our correction algorithm gives good results when it is used for correcting local discrepancies. The paper presents the description of the algorithm, the formal justification for its correctness, as well as the results of experimental testing by some artificial examples.

извлечение и анализ процессовисправление моделей процессовсети Петридекомпозиция моделей процессовразделяй и властвуйprocess miningprocess model repairPetri netsprocess model decompositiondivide and conquerReferencesvan der Aalst W. M. P., “Decomposing Process Mining Problems Using Passages”, Lecture Notes in Computer Science, 7347, Springer-Verlag, 2012, 72–91.van der Aalst W. M. P., “Decomposing Process Mining Problems Using Passages”, Lecture Notes in Computer Science, 7347, Springer-Verlag, 2012, 72–91.van der Aalst W. M. P., “Decomposing Petri Nets for Process Mining: A Generic Approach”, Distributed and Parallel Databases, 31:4 (2013), 471–507.van der Aalst W. M. P., “Decomposing Petri Nets for Process Mining: A Generic Approach”, Distributed and Parallel Databases, 31:4 (2013), 471–507.van 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., Adriansyah A., van Dongen B. F., “Replaying History on Process Models for Conformance Checking and Performance Analysis”, WIREs Data Mining and Knowledge Discovery, 2 (2012), 182–192.van der Aalst W. M. P., Adriansyah A., van Dongen B. F., “Replaying History on Process Models for Conformance Checking and Performance Analysis”, WIREs Data Mining and Knowledge Discovery, 2 (2012), 182–192.van der Aalst W. M. P., Bolt A., van Zelst S. J., “RapidProM: Mine Your Processes and Not Just Your Data”, CoRR, abs/1703.03740 (2017).van der Aalst W. M. P., Bolt A., van Zelst S. J., “RapidProM: Mine Your Processes and Not Just Your Data”, CoRR, abs/1703.03740 (2017).van der Aalst W. M. P., Kalenkova A. A., Rubin V. A., Verbeek H. M.W., “Process Discovery Using Localized Events”, LNCS, 9115, Springer, 2015, 287–308.van der Aalst W. M. P., Kalenkova A. A., Rubin V. A., Verbeek H. M.W., “Process Discovery Using Localized Events”, LNCS, 9115, Springer, 2015, 287–308.van der Aalst W. M. P, Weijters A. J. M. M., Maruster L., “Workflow Mining: Discovering Process Models from Event Logs”, IEEE Transactions on Knowledge and Data Engineering, 16 (2004), 1128–1142.van der Aalst W. M. P, Weijters A. J. M. M., Maruster L., “Workflow Mining: Discovering Process Models from Event Logs”, IEEE Transactions on Knowledge and Data Engineering, 16 (2004), 1128–1142.Adriansyah A., Aligning observed and modeled behavior, Ph.D. Thesis, Technische Universiteit Eindhoven, 2014.Adriansyah A., Aligning observed and modeled behavior, Ph.D. Thesis, Technische Universiteit Eindhoven, 2014.Begicheva A. K., Lomazova I. A., Does Your Event Log Fit the High-level Process Model? Modeling and Analysis of Information Systems, 22:3 (2015), 392–403.Begicheva A. K., Lomazova I. A., Does Your Event Log Fit the High-level Process Model? Modeling and Analysis of Information Systems, 22:3 (2015), 392–403.Begicheva A. K., Lomazova I. A., “Discovering High-Level Process Models from Event Logs”, Modeling and Analysis of Information Systems, 24:2 (2017), 125–140.Begicheva A. K., Lomazova I. A., “Discovering High-Level Process Models from Event Logs”, Modeling and Analysis of Information Systems, 24:2 (2017), 125–140.Buijs J. C. A. M., van Dongen B. F., van der Aalst W. M. P., “On the Role of Fitness, Precision, Generalization and Simplicity in Process Discovery”, On the Move to Meaningful Internet Systems: OTM 2012, Confederated International Conferences: CoopIS, DOA-SVI, and ODBASE 2012 (Rome, Italy, September 10-14, 2012), Proceedings, Part I, 2012, 305– 322.Buijs J. C. A. M., van Dongen B. F., van der Aalst W. M. P., “On the Role of Fitness, Precision, Generalization and Simplicity in Process Discovery”, On the Move to Meaningful Internet Systems: OTM 2012, Confederated International Conferences: CoopIS, DOA-SVI, and ODBASE 2012 (Rome, Italy, September 10-14, 2012), Proceedings, Part I, 2012, 305– 322.Buijs J. C. A. M., La Rosa M., Reijers H. A., van Dongen B. F., van der Aalst W. M. P., “Improving Business Process Models Using Observed Behavior”, LNBIP, 162, SpringerVerlag, Berlin, 2013, 44–59.Buijs J. C. A. M., La Rosa M., Reijers H. A., van Dongen B. F., van der Aalst W. M. P., “Improving Business Process Models Using Observed Behavior”, LNBIP, 162, SpringerVerlag, Berlin, 2013, 44–59.Burattin A., Maggi F. M., Sperduti A, “Conformance checking based on multi-perspective declarative process models”, Expert Syst. Appl., 65 (2016), 194–211.Burattin A., Maggi F. M., Sperduti A, “Conformance checking based on multi-perspective declarative process models”, Expert Syst. Appl., 65 (2016), 194–211.Dijkman R. M., Dumas M., Garcia-Banuelos L., “Graph matching algorithms for business process model similarity search”, Lecture Notes in Computer Science, 5701, 2009, 48–63.Dijkman R. M., Dumas M., Garcia-Banuelos L., “Graph matching algorithms for business process model similarity search”, Lecture Notes in Computer Science, 5701, 2009, 48–63.van Dongen B. F., Carmona J., Chatain T., “A Unified Approach for Measuring Precision and Generalization Based on Anti-alignments”, Lecture Notes in Computer Science, 9850, Springer, 2016, 39–56.van Dongen B. F., Carmona J., Chatain T., “A Unified Approach for Measuring Precision and Generalization Based on Anti-alignments”, Lecture Notes in Computer Science, 9850, Springer, 2016, 39–56.Fahland D., van der Aalst W. M. P., “Repairing Process Models to Reflect Reality”, Lecture Notes in Computer Science, 7481, Springer-Verlag, 2012, 229–245.Fahland D., van der Aalst W. M. P., “Repairing Process Models to Reflect Reality”, Lecture Notes in Computer Science, 7481, Springer-Verlag, 2012, 229–245.Fahland D., van der Aalst W. M. P., “Model repair - Aligning process models to reality”, Inf. Syst., 47 (2015), 220–243.Fahland D., van der Aalst W. M. P., “Model repair - Aligning process models to reality”, Inf. Syst., 47 (2015), 220–243.Fahland D., van der Aalst W. M. P., “Simplifying discovered process models in a controlled manner”, Inf. Syst., 38:4 (2013), 585–605.Fahland D., van der Aalst W. M. P., “Simplifying discovered process models in a controlled manner”, Inf. Syst., 38:4 (2013), 585–605.Gambini M., La Rosa M., Migliorini S., Ter Hofstede A. H. M., “Automated Error Correction of Business Process Models”, Lecture Notes in Computer Science, 6896, Springer, 2011, 148–165.Gambini M., La Rosa M., Migliorini S., Ter Hofstede A. H. M., “Automated Error Correction of Business Process Models”, Lecture Notes in Computer Science, 6896, Springer, 2011, 148–165.G¨unther C.W., van der Aalst W. M. P., “Fuzzy mining: Adaptive process simplification based on multi-perspective metrics”, BPM, Lecture Notes in Computer Science, 4714 (2007), 328–343.G¨unther C.W., van der Aalst W. M. P., “Fuzzy mining: Adaptive process simplification based on multi-perspective metrics”, BPM, Lecture Notes in Computer Science, 4714 (2007), 328–343.Hompes B. F. A., On Decomposed Process Discovery: How to Solve a Jigsaw Puzzle with Friends, Master’s Thesis, Technische Universiteit Eindhoven, 2014.Hompes B. F. A., On Decomposed Process Discovery: How to Solve a Jigsaw Puzzle with Friends, Master’s Thesis, Technische Universiteit Eindhoven, 2014.Hompes B. F. A., Verbeek H. M.W., van der Aalst W. M. P., “Finding suitable activity clusters for decomposed process discovery”, SIMPDA 2014, 1293 (2014), 16–30.Hompes B. F. A., Verbeek H. M.W., van der Aalst W. M. P., “Finding suitable activity clusters for decomposed process discovery”, SIMPDA 2014, 1293 (2014), 16–30.Kalenkova A. A., Lomazova I. A., van der Aalst W. M. P., “Process Model Discovery: A Method Based on Transition System Decomposition”, Application and Theory of Petri Nets and Concurrency, Proceedings of 35th International Conference, PETRI NETS 2014, Lecture Notes in Computer Science, 8489, Springer, 2014, 71–90.Kalenkova A. A., Lomazova I. A., van der Aalst W. M. P., “Process Model Discovery: A Method Based on Transition System Decomposition”, Application and Theory of Petri Nets and Concurrency, Proceedings of 35th International Conference, PETRI NETS 2014, Lecture Notes in Computer Science, 8489, Springer, 2014, 71–90.Leemans S. J. J., Fahland D., van der Aalst W. M. P., “Discovering Block-Structured Process Models from Incomplete Event Logs”, 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”, Lecture Notes in Computer Science, 8489, Springer, 2014, 91–110.Leemans S. J. J., Fahland D., van der Aalst W. M. P., “Scalable Process Discovery with Guarantees”, LNBIP, 214, Springer, 2015, 85–101.Leemans S. J. J., Fahland D., van der Aalst W. M. P., “Scalable Process Discovery with Guarantees”, LNBIP, 214, Springer, 2015, 85–101.Mans R., van der Aalst W. M. P., Verbeek H. M.W., “Supporting Process Mining Workflows with RapidProM”, Proceedings of the BPM Demo Sessions 2014 Co-located with the 12th International Conference on Business Process Management (BPM 2014), CEUR-WS.org, 2014, 56–60.Mans R., van der Aalst W. M. P., Verbeek H. M.W., “Supporting Process Mining Workflows with RapidProM”, Proceedings of the BPM Demo Sessions 2014 Co-located with the 12th International Conference on Business Process Management (BPM 2014), CEUR-WS.org, 2014, 56–60.Мицюк А. А., Шугуров И. С., “Синтез моделей процессов по журналам событий с шумом”, Моделирование и анализ информационных систем, 21:4 (2014), 181–198Mitsyuk A. A., Shugurov I. S., “On Process Model Synthesis Based on Event Logs with Noise”, Automatic Control and Computer Sciences, 50:7 (2016), 460–470.Mitsyuk A. A., Lomazova I. A., Shugurov I. S., van der Aalst W. M. P., “Process Model Repair by Detecting Unfitting Fragments”, Supplementary Proceedings of AIST 2017, CEUR-WS.org, 2017.Mitsyuk A. A., Lomazova I. A., Shugurov I. S., van der Aalst W. M. P., “Process Model Repair by Detecting Unfitting Fragments”, Supplementary Proceedings of AIST 2017, CEUR-WS.org, 2017.Mu˜noz-Gama J., “Conformance Checking and Diagnosis in Process Mining — Comparing Observed and Modeled Processes”, LNBIP, 270 (2016).Mu˜noz-Gama J., “Conformance Checking and Diagnosis in Process Mining — Comparing Observed and Modeled Processes”, LNBIP, 270 (2016).Mu˜noz-Gama J., Carmona J., van der Aalst W. M. P., “Single-Entry Single-Exit Decomposed Conformance Checking”, Inf. Syst., 46 (2014), 102–122.Mu˜noz-Gama J., Carmona J., van der Aalst W. M. P., “Single-Entry Single-Exit Decomposed Conformance Checking”, Inf. Syst., 46 (2014), 102–122.Polyvyanyy A., van der Aalst W. M. P., ter Hofstede A. H. M., Wynn M. T., “Impact-driven process model repair”, ACM Transactions on Software Engineering and Methodology (TOSEM), 25:4 (2017), 28:1–28:60.Polyvyanyy A., van der Aalst W. M. P., ter Hofstede A. H. M., Wynn M. T., “Impact-driven process model repair”, ACM Transactions on Software Engineering and Methodology (TOSEM), 25:4 (2017), 28:1–28:60.de San Pedro J., Carmona J., Cortadella J., “Log-based simplification of process models”, BPM, Lecture Notes in Computer Science, 9253 (2015), 457–474.de San Pedro J., Carmona J., Cortadella J., “Log-based simplification of process models”, BPM, Lecture Notes in Computer Science, 9253 (2015), 457–474.Шершаков С. А., “Графический язык DPMine для автоматизации экспериментов в области автоматического построения и анализа процессов”, Моделирование и ана- лиз информационных систем, 21:5 (2014), 102–115Shershakov S. A., “DPMine graphical language for automation of experiments in process mining”, Automatic Control and Computer Sciences, 50:7 (2016), 477–485.Shugurov I. S., Mitsyuk A. A., “Iskra: A Tool for Process Model Repair”, Proceedings of the Institute for System Programming of the Russian Academy of Sciences, 27:3 (2015), 237–254.Shugurov I. S., Mitsyuk A. A., “Iskra: A Tool for Process Model Repair”, Proceedings of the Institute for System Programming of the Russian Academy of Sciences, 27:3 (2015), 237–254.Shugurov I. S., Mitsyuk A. A., “Applying MapReduce to Conformance Checking”, Proceedings of the Institute for System Programming of the Russian Academy of Sciences, 28:3 (2016), 103–122.Shugurov I. S., Mitsyuk A. A., “Applying MapReduce to Conformance Checking”, Proceedings of the Institute for System Programming of the Russian Academy of Sciences, 28:3 (2016), 103–122.Shugurov I. S., Mitsyuk A. A., “Generation of a Set of Event Logs with Noise”, Proceedings of the 8th Spring/Summer Young Researchers Colloquium on Software Engineering (SYRCoSE 2014), 2014, 88–95.Shugurov I. S., Mitsyuk A. A., “Generation of a Set of Event Logs with Noise”, Proceedings of the 8th Spring/Summer Young Researchers Colloquium on Software Engineering (SYRCoSE 2014), 2014, 88–95.Verbeek H. M.W., Buijs J. C. A. M., van Dongen B. F., van der Aalst W. M. P., “ProM 6: The Process Mining Toolkit”, Proc. of BPM Demonstration Track 2010, 615, CEURWS.org, 2010, 34–39.Verbeek H. M.W., Buijs J. C. A. M., van Dongen B. F., van der Aalst W. M. P., “ProM 6: The Process Mining Toolkit”, Proc. of BPM Demonstration Track 2010, 615, CEURWS.org, 2010, 34–39.Verbeek H. M.W., “Decomposed Process Mining with Divide And Conquer”, BPM 2014 Demos, 1295 (2014), 86–90.Verbeek H. M.W., “Decomposed Process Mining with Divide And Conquer”, BPM 2014 Demos, 1295 (2014), 86–90.Verbeek H. M.W., van der Aalst W. M. P., Mu˜noz-Gama J., “Divide and Conquer: A Tool Framework for Supporting Decomposed Discovery in Process Mining”, The Computer Journal, 08.05.2017. https://doi.org/10.1093/comjnl/bxx040.Verbeek H. M.W., van der Aalst W. M. P., Mu˜noz-Gama J., “Divide and Conquer: A Tool Framework for Supporting Decomposed Discovery in Process Mining”, The Computer Journal, 08.05.2017. https://doi.org/10.1093/comjnl/bxx040.Weber I., Rogge-Solti A., Li C., Mendling J., “CCaaS: Online Conformance Checking as a Service”, BPM 2015 Demos, 1418 (2015), 45–49.Weber I., Rogge-Solti A., Li C., Mendling J., “CCaaS: Online Conformance Checking as a Service”, BPM 2015 Demos, 1418 (2015), 45–49.van derWerf J. M. E. M., van Dongen B. F., Hurkens C. A. J., Serebrenik A., “Process Discovery using Integer Linear Programming”, Fundam. Inform., 94 (2009), 387–412.van derWerf J. M. E. M., van Dongen B. F., Hurkens C. A. J., Serebrenik A., “Process Discovery using Integer Linear Programming”, Fundam. Inform., 94 (2009), 387–412.Weijters A. J. M. M., Ribeiro J., Chawla N., “Flexible Heuristics Miner”, IEEE Symposium on Computational Intelligence and Data Mining (CIDM 2011), 2011, 310–317.Weijters A. J. M. M., Ribeiro J., Chawla N., “Flexible Heuristics Miner”, IEEE Symposium on Computational Intelligence and Data Mining (CIDM 2011), 2011, 310–317.

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