Preview

Труды Института системного программирования РАН

Расширенный поиск

Применение MapReduce для проверки соответствия моделей процессов и логов событий

https://doi.org/10.15514/ISPRAS-2016-28(3)-7

Полный текст:

Аннотация

Process mining - это относительно новая область исследований, в рамках которой разрабатываются методы исследования и улучшения бизнес-процессов. Спецификой методов process mining является то, что они основываются на анализе истории выполнения процессов, которая представляется в виде логов событий. Проверка соответствия моделей процессов и логов событий является одним из ключевых направлений в области process mining. Алгоритмы проверки соответствия используются для того, чтобы оценить, насколько хорошо данная модель бизнес-процесса, представленная, например, в виде сети Петри, описывает поведение, записанное в логе событий. Проверка соответствия, базирующаяся на использовании так называемых "выравниваний", на данный момент является самым передовым и часто используемым алгоритмом проверки соответствия. В данной работе рассматривается проблема большой вычислительной сложности данного алгоритма. В настоящее время проверка соответствия на основе выравниваний является не слишком эффективной с точки зрения потребления памяти и времени, необходимого для вычислений. Решение этой проблемы имеет большое значение для успешного применения проверки соответствия между реальными моделями бизнес-процессов и логами событий, что весьма проблематично с использованием существующих подходов. MapReduce является популярной моделью параллельных вычислений, которая упрощает реализацию эффективных и масштабируемых распределенных вычислений. В данной работе представлена модифицированная версия алгоритма проверки соответствия на основе выравниваний с применением MapReduce. Так же в работе показано, что проверка соответствия может быть распределена с помощью MapReduce, и что такое распределение может привести к уменьшению времени, требуемого для вычислений. Показано, что алгоритм проверки соответствия модели процесса и лога событий может быть реализован в распределенном виде с помощью MapReduce. Показано, что время вычисления растет линейно с ростом размера логов событий.

Об авторах

И. С. Шугуров
Национальный Исследовательский Университет «Высшая Школа Экономики»
Россия


А. А. Мицюк
Национальный Исследовательский Университет «Высшая Школа Экономики»
Россия


Список литературы

1. Wil M. P. van der Aalst, Process mining: discovery, conformance and enhancement of business processes. Springer, 2011. C. Lattner. LLVM: An Infrastructure for Multi-Stage Optimization. Master’s thesis, Computer Science Dept., University of Illinois at Urbana-Champaign, Urbana, IL.

2. S. A. Shershakov and V. A. Rubin, “System runs analysis with process mining,” Modeling and Analysis of Information Systems, vol. 22, no. 6, pp. 818-833, December 2015.

3. S. A. Shershakov, “VTMine framework as applied to process mining modeling,” International Journal of Computer and Communication Engineering, vol. 4, no. 3, pp. 166-179, May 2015.

4. W. M. van der Aalst, “Process Mining in the Large: A Tutorial,” in Business Intelligence. Springer, 2014, pp. 33-76.

5. C. Bratosin, N. Sidorova, and W. van der Aalst, “Distributed Genetic Process Mining,” in Evolutionary Computation (CEC), 2010 IEEE Congress on, 2010, pp. 1-8.

6. S. J. J. Leemans, D. Fahland, and W. M. P. van der Aalst, “Discovering Block-Structured Process Models from Event Logs Containing Infrequent Behaviour,” in Business Process Management Workshops, ser. Lecture Notes in Business Information Processing, N. Lohmann, M. Song, and P. Wohed, Eds. Springer International Publishing, 2014, vol. 171, pp. 66-78.

7. A. A. Kalenkova, I. A. Lomazova, and W. M. P. van der Aalst, “Process Model Discovery: A Method Based on Transition System Decomposition,” in Petri Nets, ser. Lecture Notes in Computer Science, vol. 8489. Springer, 2014, pp. 71-90.

8. D. Fahland and W. M. P. van der Aalst, “Model Repair - Aligning Process Models to Reality,” Inf. Syst., vol. 47, pp. 220-243, 2015. [Online]. Доступно по ссылке: http://dx.doi.org/10.1016/j.is.2013.12.007.

9. I. S. Shugurov and A. A. Mitsyuk, “Iskra: A Tool for Process Model Repair,” Proceedings of the Institute for System Programming, vol. 27, no. 3, pp. 237-254, 2015.

10. J. Dean and S. Ghemawat, “MapReduce: Simplified Data Processing on Large Clusters,” Commun. ACM, vol. 51, no. 1, pp. 107-113, 2008. [Online]. Доступно по ссылке: http://doi.acm.org/10.1145/1327452.1327492.

11. W. M. P. van der Aalst, “Distributed Process Discovery and Conformance Checking,” in Fundamental Approaches to Software Engineering, ser. Lecture Notes in Computer Science, J. de Lara and A. Zisman, Eds. Springer Berlin Heidelberg, 2012, vol. 7212, pp. 1-25.

12. A. Adriansyah, “Aligning Observed and Modeled Behavior,” PhD Thesis, Technische Universiteit Eindhoven, Eindhoven, The Netherlands, 2014.

13. A. Adriansyah, B. van Dongen, and W. M. van der Aalst, “Conformance Checking using Cost-Based Fitness Analysis,” in IEEE International Enterprise Computing Conference (EDOC 2011), C. Chi and P. Johnson, Eds. IEEE Computer Society, 2011, pp. 55-64.

14. D. Miner and A. Shook, MapReduce Design Patterns: Building Effective Algorithms and Analytics for Hadoop and Other Systems, 1st ed. O’Reilly Media, Inc., 2012.

15. W. M. P. van der Aalst, “Decomposing Petri Nets for Process Mining: A Generic Approach,” Distributed and Parallel Databases, vol. 31, no. 4, pp. 471-507, 2013.

16. J. Munoz-Gama, “Conformance checking and diagnosis in process mining,” PhD Thesis, Universitat Politecnica de Catalunya, 2014.

17. W. M. P. van der Aalst, “Decomposing Process Mining Problems Using Passages,” in Application and Theory of Petri Nets, ser. Lecture Notes in Computer Science, S. Haddad and L. Pomello, Eds. Springer Berlin Heidelberg, 2012, vol. 7347, pp. 72-91.

18. J. Munoz-Gama, J. Carmona, and W. M. van der Aalst, “Single-Entry Single-Exit Decomposed Conformance Checking,” Information Systems, vol. 46, pp. 102-122, 2014.

19. “Apache hadoop,” доступно по ссылке: http://hadoop.apache.org/, 2016-04-01.

20. W. M. P. van der Aalst and. B. van Dongen, C. Gunther, A. Rozinat, ¨ E. Verbeek, and T. Weijters, “ProM: The Process Mining Toolkit,” in Business Process Management Demonstration Track (BPMDemos 2009), ser. CEUR Workshop Proceedings, A. Medeiros and B. Weber, Eds., vol. 489. CEUR-WS.org, 2009, pp. 1-4.

21. “Prom framework,” доступно по ссылке: http://www.promtools.org/doku.php, 2016-04-01.

22. IEEE Task Force on Process Mining, “XES Standard Definition,” www.xes-standard.org, 2013.

23. “Apache mahout,” доступно по ссылке: http://mahout.apache.org/,: 2016-04-01.

24. “Amazon EMR,” доступно по ссылке: https://aws.amazon.com/ru/elasticmapreduce/, accessed: 2016-04-01.

25. W. M. P. van der Aalst, A. H. M. ter Hofstede, B. Kiepuszewski, and A. P. Barros, “Workflow Patterns,” Distrib. Parallel Databases, vol. 14, no. 1, pp. 5-51, Jul. 2003. [Online]. Доступно по ссылке: http://dx.doi.org/10.1023/A:1022883727209

26. I. S. Shugurov and A. A. Mitsyuk, “Generation of a Set of Event Logs with Noise,” in Proceedings of the 8th Spring/Summer Young Researchers Colloquium on Software Engineering (SYRCoSE 2014), 2014, pp. 88-95.

27. H. Reguieg, F. Toumani, H. R. Motahari-Nezhad, and B. Benatallah, “Using MapReduce to Scale Events Correlation Discovery for Business Processes Mining,” in Business Process Management. Springer, 2012, pp. 279-284.

28. J. Evermann, “Scalable Process Discovery using Map-Reduce,” IEEE Transactions on Services Computing, vol. PP, no. 99, pp. 1-1, 2014.

29. J. Evermann and G. Assadipour, “Big Data meets Process Mining: Implementing the Alpha Algorithm with Map-Reduce,” in Proceedings of the 29th Annual ACM Symposium on Applied Computing. ACM, 2014, pp. 1414-1416.

30. W. M. P. van der Aalst, A. J. M. M. Weijters, and L. Maruster, “Workflow Mining: Discovering Process Models from Event Logs,” IEEE Transactions on Knowledge and Data Engineering, vol. 16, no. 9, pp. 1128-1142, 2004.

31. A. J. M. M. Weijters and J. T. S. Ribeiro, “Flexible Heuristics Miner (FHM),” in Computational Intelligence and Data Mining (CIDM), 2011 IEEE Symposium on, April 2011, pp. 310-317.

32. S. Hernandez, S. Zelst, J. Ezpeleta, and W. M. P. van der Aalst, “Handling big (ger) logs: Connecting ProM 6 to Apache Hadoop,” in Proceedings of the BPM2015 Demo Session, ser. CEUR Workshop Proceedings, vol. 1418, 2015, pp. 80-84.

33. S. J. J. Leemans, D. Fahland, and W. M. P. van der Aalst, “Discovering Block-Structured Process Models from Incomplete Event Logs,” in Application and Theory of Petri Nets and Concurrency, ser. Lecture Notes in Computer Science, G. Ciardo and E. Kindler, Eds. Springer.


Для цитирования:


Шугуров И.С., Мицюк А.А. Применение MapReduce для проверки соответствия моделей процессов и логов событий. Труды Института системного программирования РАН. 2016;28(3):103-122. https://doi.org/10.15514/ISPRAS-2016-28(3)-7

For citation:


Shugurov I.S., Mitsyuk A.A. Applying MapReduce to Conformance Checking. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2016;28(3):103-122. https://doi.org/10.15514/ISPRAS-2016-28(3)-7

Просмотров: 110


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)