Revisiting the Transition Matrix-Based Concept Drift Approach: Improving the Detection Task Reliability Through Additional Experimentation | SN Computer Science Skip to main content
Springer Nature Link
Log in

Revisiting the Transition Matrix-Based Concept Drift Approach: Improving the Detection Task Reliability Through Additional Experimentation

  • Original Research
  • Published:
SN Computer Science Aims and scope Submit manuscript

Abstract

Coping with concept drifts in process mining remains highly pertinent, given the inherently dynamic essence of real-world business processes. Daily operations see processes undergoing continuous changes due to changing market demands, technological advances, or organizational restructuring. Conceptual drifts may emerge unexpectedly at any time, impacting process behavior significantly. Neglecting to manage these drifts can lead to obsolete process models, inaccurate performance analyses, and misguided decision-making. Researchers have been struggling to address several issues related to concept drifts in process mining; nevertheless, this question persists open. As a contribution, we previously proposed an approach based on transformed transition matrices as an efficient, simple, and extensible data structure, first applied to the task of detecting concept drifts. For this purpose, three strategies were adjusted to function with transformed transition matrices. We evaluated the approach’s effectiveness by initially using one set of event logs, contrasting its performance against cutting-edge benchmark methods in experimental settings. In this paper, we revisit the proposed approach, by expanding and reinforcing its evaluation through an additional set of event logs. The findings underscore the transformed transition matrix’s capability to encapsulate manifold features drawn from event logs, particularly those tied to process drifts via windowed comparisons. We show how these extracted features contribute to pinpointing sudden process drifts in control flow, specifically in an offline scenario. The experimental outcomes hold promise, signifying the potential of the three adapted detection strategies.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16

Similar content being viewed by others

Availability of Data and Materials

Not applicable.

Code Availability

https://github.com/pm-usp/concept_drift/tree/main/Transition_Matrix_Process_Drift.

Notes

  1. This matrix would more correctly be called directly-follows relation matrix rather than transition matrix, as one activity directly followed by another in an event trace does not necessarily represent a transition in a process [8]. However, for simplicity, as done by [6], we kept the nomenclature used by previous authors [49, 50].

  2. Code available at https://github.com/pm-usp/concept_drift/tree/main/Transition_Matrix_Process_Drift.

  3. Code available at https://github.com/pm-usp/concept_drift/tree/main/Transition_Matrix_Process_Drift.

References

  1. Maaradji A, Dumas M, La Rosa M, Ostovar A. Fast and accurate business process drift detection. In: Proceedings of the 13th International Conference on Business Process Management, 2015;p. 406–22.

  2. Ostovar A, Maaradji A, La Rosa M, Hofstede AHM, Dongen BFV. Detecting drift from event streams of unpredictable business processes. In: Proceedings of the 35th International Conference on Conceptual Modeling, 2016;p. 330–46.

  3. Sato DMV, De Freitas SC, Barddal JP, Scalabrin EE. A survey on concept drift in process mining. ACM Comput Surv. 2021;54(9).

  4. Aalst W et al. Process mining manifesto. In: Proceedings of the 7th International Workshop on Business Process Intelligence, 2012; p. 169–94.

  5. Bose RPJC, Van Der Aalst WMP, Zliobaite I, Pechenizkiy M. Dealing with concept drifts in process mining. IEEE Trans Neural Netw Learn Syst. 2014;25(1):154–71.

    Article  Google Scholar 

  6. Sousa RG, Peres SM, Fantinato M, Reijers HA. Concept drift detection and localization in process mining: An integrated and efficient approach enabled by trace clustering. In: Proceedings of the 36th ACM/SIGAPP Symposium on Applied Computing, 2021; p. 364–73

  7. Aalst W. Process mining in the large: a tutorial. In: Proceedings of the 3rd European Summer School on Business Intelligence, 2014; p. 33–76.

  8. Aalst W. Process Mining: Data Science in Action. 2nd ed. Berlin: Springer; 2016.

    Book  Google Scholar 

  9. Manoj Kumar MV, Thomas L, Annappa B. Capturing the sudden concept drift in process mining. In: Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data, 2015; p. 132–43.

  10. Meira Neto AC, Sousa RG, Fantinato M, Peres S. Towards a transition matrix-based concept drift approach: experiments on the detection task. In: Proceedings of the 25th International Conference on Enterprise Information Systems, vol. 2, 2023;p. 361–72.

  11. Bose RPJC, Van Der Aalst WMP, Žliobaite I, Pechenizkiy M. Handling concept drift in process mining. In: Proceedings of the 23rd International Conference on Advanced Information Systems Engineering, 2011; p. 391–405.

  12. Martjushev J, Jagadeesh Chandra Bose RP, Aalst WMP. Change point detection and dealing with gradual and multi-order dynamics in process mining. In: Proceedings of the 14th International Conference on Business Process Management, 2015;p. 161–78.

  13. Weber P, Bordbar B, Tino P. Real-time detection of process change using process mining. In: Proceedings of the Imperial College Computing Student Workshop, 2011;p. 108–14.

  14. Luengo D, Sepúlveda M. Applying clustering in process mining to find different versions of a business process that changes over time. In: Proceedings of the 7th International Workshop on Business Process Intelligence, 2012;pp. 153–8.

  15. Accorsi R, Stocker T. Discovering workflow changes with time-based trace clustering. In: Proceedings of the 1st International Symposium on Data-Driven Process Discovery and Analysis, 2011; p. 154–68.

  16. Carmona J, Gavaldà R. Online techniques for dealing with concept drift in process mining. In: Proceedings of the 11th International Symposium on Advances in Intelligent Data Analysis XI, 2012; p. 90–102.

  17. Hompes BFA, Buijs JCAM, Van Der Aalst WMP, Dixit PM, Buurman J. Detecting change in processes using comparative trace clustering. In: Proceedings of the 5th International Symposium on Data-Driven Process Discovery and Analysis, 2015;p. 95–108.

  18. Hompes BFA, Buijs JCAM, Van Der Aalst WMP, Dixit PM, Buurman J. Detecting changes in process behavior using comparative case clustering. In: Proceedings of the 5th International Symposium on Data-Driven Process Discovery and Analysis – Revised Selected Papers, 2017;p. 54–75.

  19. Maaradji A, Dumas M, Rosa ML, Ostovar A. Detecting sudden and gradual drifts in business processes from execution traces. IEEE Trans Knowl Data Eng. 2017;29(10):2140–54.

    Article  Google Scholar 

  20. Ostovar A, Maaradji A, La Rosa M, Ter Hofstede AHM. Characterizing drift from event streams of business processes. In: Proceedings of the 29th International Conference on Advanced Information Systems Engineering, 2017;p. 210–28.

  21. Ostovar A, Leemans SJJ, Rosa ML. Robust drift characterization from event streams of business processes. ACM Trans Knowl Discover Data. 2020;14(3).

  22. Seeliger A, Nolle T, Mühlhäuser M. Detecting concept drift in processes using graph metrics on process graphs. In: Proceedings of the 9th Conference on Subject-oriented Business Process Management. 2017.

  23. Zheng C, Wen L, Wang J. Detecting process concept drifts from event logs. In: Proceedings of the International Conference on Cooperative Information Systems, 2017;p. 524–42.

  24. Richter F, Seidl T. Tesseract: Time-drifts in event streams using series of evolving rolling averages of completion times. In: Proceedings of the 16th International Conference on Business Process Management, 2017; p. 289–305.

  25. Barbon Junior S, Tavares GM, Da Costa VGT, Ceravolo P, Damiani E. A framework for human-in-the-loop monitoring of concept-drift detection in event log stream. In: Proceedings of the Companion of the The Web Conference on The Web Conference, 2018;p. 319–26.

  26. Tavares GM, Ceravolo P, Da Costa VGT, Damiani E, Junior SB. Overlapping analytic stages in online process mining. In: Proceedings of the IEEE International Conference Service Computing, 2019; p. 167–75.

  27. Liu N, Huang J, Cui L. A framework for online process concept drift detection from event streams. In: Proceedings of the IEEE International Conference Service Computing, 2018;p. 105–12.

  28. Stertz F, Rinderle-Ma S. Process histories - detecting and representing concept drifts based on event streams. In: Proceedings of the International Conference on Cooperative Information Systems, 2018;p. 318–35.

  29. Pauwels S, Calders T. An anomaly detection technique for business processes based on extended dynamic bayesian networks. In: Proceedings of the 36th ACM/SIGAPP Symposium on Applied Computing, 2019;p. 494–501.

  30. Hassani M. Concept drift detection of event streams using an adaptive window. In: Proceedings of the 33rd International ECMS Conference on Modelling and Simulation, 2019;p. 230–9.

  31. Kurniati AP, McInerney C, Zucker K, Hall G, Hogg D, Johnson O. A multi-level approach for identifying process change in cancer pathways. In: Proceedings of the 2nd International Workshop on Process-Oriented Data Science for Healthcare, 2019;p. 595–607.

  32. Kurniati AP, McInerney C, Zucker K, Hall G, Hogg D, Johnson O. Using a multi-level process comparison for process change analysis in cancer pathways. Int J Environ Res Public Health. 2020;17(19):1–16.

    Article  Google Scholar 

  33. Yeshchenko A, Ciccio CD, Mendling J, Polyvyanyy A. Comprehensive process drift analysis with the visual drift detection tool. In: Proceedings of the 38th International Conference on Conceptual Modeling, 2019;pp. 108–12.

  34. Yeshchenko A, Di Ciccio C, Mendling J, Polyvyanyy A. Comprehensive process drift detection with visual analytics. In: Proceedings of the 38th International Conference on Conceptual Modeling, 2019;p. 119–35.

  35. Yeshchenko A, Mendling J, Di Ciccio C, Polyvyanyy A. VDD: A visual drift detection system for process mining. In: Proceedings of the ICPM Doctoral Consortium and Tool Demonstration Track, 2020;pp. 31–4.

  36. Yeshchenko A, Di Ciccio C, Mendling J, Polyvyanyy A. Visual drift detection for event sequence data of business processes. IEEE Trans Visual Comput Graphics. 2021;28(8):3050–68.

    Article  Google Scholar 

  37. Brockhoff T, Uysal MS, Van Der Aalst WMP. Time-aware concept drift detection using the earth mover’s distance. In: Proceedings of the International Conference Process Mining, 2020;p. 33–40.

  38. Impedovo A, Mignone P, Loglisci C, Ceci M. Simultaneous process drift detection and characterization with pattern-based change detectors. In: Proceedings of the 3rd International Conference on Discovery Science, 2020;p. 451–67.

  39. Adams JN, Zelst SJ, Quack L, Hausmann K, Aalst WMP, Rose T. A framework for explainable concept drift detection in process mining. In: Proceedings of the 19th International Conference on Business Process Management, 2021;p. 400–16.

  40. Lu Y, Chen Q, Poon S. A robust and accurate approach to detect process drifts from event streams. In: Proceedings of the 19th International Conference on Business Process Management, 2021;p. 383–99.

  41. Lu Y, Chen Q, Poon S. Detecting and understanding branching frequency changes in process models. In: Proceedings of the 22nd International Conference on Enterprise, Business-Process and Information Systems Modeling, 2021;p. 39–46.

  42. Richter F, Maldonado A, Zellner L, Seidl T. Otoso: online trace ordering for structural overviews. In: Proceedings of the 1st International Workshop on Streaming Analytics for Process Mining, 2021;p. 218–29.

  43. Zellner L, Richter F, Sontheim J, Maldonado A, Seidl T. Concept drift detection on streaming data with dynamic outlier aggregation. In: Proceedings of the 1st International Workshop on Streaming Analytics for Process Mining, 2021;p. 206–17.

  44. Sato DMV, Barddal JP, Scalabrin EE. Interactive process drift detection framework. In: Proceedings of the 20th International Conference on Artificial Intelligence and Soft Computing, 2021;p. 192–204.

  45. Yang L, McClean S, Donnelly M, Burke K, Khan K. Process duration modelling and concept drift detection for business process mining. In: Proceedings of the IEEE SmartWorld, Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Internet of People and Smart City Innovation, 2021;p. 653–8.

  46. Ceravolo P, Tavares G, Barbon Junior S, Damiani E. Evaluation goals for online process mining: a concept drift perspective. IEEE Trans Service Comput. 2022;15(4):2473–89.

    Article  Google Scholar 

  47. Lu J, Liu A, Dong F, Gu F, Gama J, Zhang G. Learning under concept drift: a review. IEEE Trans Knowl Data Eng. 2019;31(12):2346–63.

    Google Scholar 

  48. Gemaque RN, Costa AFJ, Giusti R, Santos EM. An overview of unsupervised drift detection methods. WIREs Data Min Knowl Discovery. 2020;10(6):1381.

    Article  Google Scholar 

  49. Song M, Günther CW, Aalst W. Trace clustering in process mining. In: Proceedings of the International Workshop on Business Process Intelligence, 2009;p. 109–20.

  50. Appice A, Malerba D. A co-training strategy for multiple view clustering in process mining. IEEE Trans Service Comput. 2016;9(6):832–45.

    Article  Google Scholar 

  51. Truong C, Oudre L, Vayatis N. Selective review of offline change point detection methods. Signal Process. 2020;167.

  52. McDonald JH. Handbook of Biological Statistics. 2nd ed. Baltimore: Sparky House Publishing; 2009.

    Google Scholar 

  53. Killick R, Fearnhead P, Eckley IA. Optimal detection of changepoints with a linear computational cost. J Am Stat Assoc. 2012;107(500):1590–8.

    Article  MathSciNet  Google Scholar 

  54. Sousa RGd. Trace clustering approach for detection and localization of concept drift in business processes. Master’s thesis, Graduate Program in Information Systems, School of Arts, Science and Humanities, University of São Paulo, Brazil (2021)

Download references

Funding

Not applicable.

Author information

Authors and Affiliations

  1. School of Arts, Science and Humanities, University of São Paulo, Rua Arlindo Béttio, 1000, São Paulo, 03828-000, SP, Brazil

    Antonio Carlos Meira Neto, Rafael Gaspar de Sousa, Marcelo Fantinato & Sarajane Marques Peres

Authors
  1. Antonio Carlos Meira Neto
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rafael Gaspar de Sousa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Marcelo Fantinato
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Sarajane Marques Peres
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

Not applicable.

Corresponding author

Correspondence to Antonio Carlos Meira Neto.

Ethics declarations

Conflict of Interest

The authors declare that they have no conflict of interest.

Ethical Approval

Not applicable.

Consent to Participate

Not applicable.

Consent for Publication

Not applicable.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This article is part of the topical collection “Recent Trends on Enterprise Information Systems” guest edited by Joaquim Filipe, Michał Śmiałek, Alexander Brodsky and Slimane Hammoudi.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Meira Neto, A.C., de Sousa, R.G., Fantinato, M. et al. Revisiting the Transition Matrix-Based Concept Drift Approach: Improving the Detection Task Reliability Through Additional Experimentation. SN COMPUT. SCI. 5, 188 (2024). https://doi.org/10.1007/s42979-023-02536-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s42979-023-02536-z

Keywords

Search

Navigation