On the application of sequential pattern mining primitives to process discovery: Overview, outlook and opportunity identification

Focus Article

Marwan Hassani, Sebastiaan J. Zelst, Wil M. P. Aalst

Published Online: May 10 2019

DOI: 10.1002/widm.1315

Full article on Wiley Online Library: HTML PDF

Can't access this content? Tell your librarian.

Abstract Sequential pattern mining (SPM) is a well‐studied theme in data mining, in which one aims to discover common sequences of item sets in a large corpus of temporal itemset data. Due to the sequential nature of data streams, supporting SPM in streaming environments is commonly studied in the area of data stream mining as well. On the other hand, stream‐based process discovery (PD), originating from the field of process mining, focusses on learning process models on the basis of online event data. In particular, the main goal of the models discovered is to describe the underlying generating process in an end‐to‐end fashion. As both SPM and PD use data that are comparable in nature, that is, both involve time‐stamped instances, one expects that techniques from the SPM domain are (partly) transferable to the PD domain. However, thus far, little work has been done in the intersection of the two fields. In this focus article, we therefore study the possible application of SPM techniques in the context of PD. We provide an overview of the two fields, covering their commonalities and differences, highlight the challenges of applying them, and, present an outlook and several avenues for future work. This article is categorized under: Algorithmic Development > Spatial and Temporal Data Mining Fundamental Concepts of Data and Knowledge > Key Design Issues in Data Mining Fundamental Concepts of Data and Knowledge > Big Data Mining

Typical process discovery result based on the example data of Table

[ Normal View | Magnified View ]

An abstract overview of the online–offline stream process discovery model

[ Normal View | Magnified View ]

Example local process model (BPMN) based on corpus of event data containing a large amount of traces of the form 〈…, a, b, c, d, …〉 and 〈…, a, c, b, d, …〉. BPMN, Business Process Modeling Notation

[ Normal View | Magnified View ]

Mining models employed in stream SPM. Both (a) batch‐based and (b) sliding‐window‐based approaches forward their intermediate output to an offline SPM approach. SPM, sequential pattern mining

[ Normal View | Magnified View ]

References

Abouelhoda,, M., & Ghanem,, M. (2010). String mining in bioinformatics. In Scientific data mining and knowledge discovery—Principles and foundations (pp. 207–247). Berlin: Springer.
Agrawal,, R., & Srikant,, R. (1995). Mining sequential patterns. In 11th International Conference on Data Engineering (pp. 3–14). Washington, DC: IEEE Computer Society.
Augusto,, A., Conforti,, R., Dumas,, M., Rosa,, M. L., Maggi,, F. M., Marrella,, A., … Soo,, A. (2018). Automated discovery of process models from event logs: Review and benchmark. IEEE Transactions on Knowledge and Data Engineering, 31(4), 1–1.
Buijs,, J. C. A. M. (2014). Receipt phase of an environmental permit application process (‘WABO’), CoSeLoG project. Eindhoven: Eindhoven University of Technology. https://doi.org/10.4121/uuid:a07386a5-7be3-4367-9535-70bc9e77dbe6
Burattin,, A., Cimitile,, M., Maggi,, F. M., & Sperduti,, A. (2015). Online discovery of declarative process models from event streams. IEEE Transactions on Services Computing, 8(6), 833–846.
Burattin,, A., Sperduti,, A., & van der Aalst,, W. M. P. (2014). Control‐flow discovery from event streams. In CEC IEEE (pp. 2420–2427). New York, NY: IEEE.
Cao,, F., Ester,, M., Qian,, W., & Zhou,, A. (2006). Density‐based clustering over an evolving data stream with noise. In In 2006 SIAM conference on data mining (pp. 328–339). Philadelphia, PA: SIAM.
Chang,, L., Wang,, T., Yang,, D., & Luan,, H. (2008). Seqstream: Mining closed sequential patterns over stream sliding windows. In ICDM IEEE (pp. 83–92). New York, NY: IEEE.
Chen,, C. C., Shuai,, H. H., & Chen,, M. S. (2017). Distributed and scalable sequential pattern mining through stream processing. Knowledge and Information Systems, 53(2), 365–390.
Chen,, G., Wu,, X., & Zhu,, X. (2005). Sequential pattern mining in multiple streams. In ICDM IEEE (pp. 585–588). New York, NY: IEEE.
Chen,, Y. C., Chen,, C. C., Peng,, W. C., & Lee,, W. C. (2014). Mining correlation patterns among appliances in smart home environment. In Advances in knowledge discovery and data mining (pp. 222–233). Berlin: Springer International Publishing.
Cormode,, G., & Hadjieleftheriou,, M. (2010). Methods for finding frequent items in data streams. VLDB Journal, 19(1), 3–20.
Dalmas,, B., Tax,, N., & Norre,, S. (2017). Heuristics for high‐utility local process model mining. In ATEAD (pp. 106–121). Aachen, Germany: CEUR‐WS.org.
De Leoni,, M., & Mannhardt,, F. (2015). Road traffic fine management process. Eindhoven: Eindhoven University of Technology. https://doi.org/10.4121/uuid:270fd440-1057-4fb9-89a9-b699b47990f5
Djenouri,, Y., Belhadi,, A., & Fournier‐Viger,, P. (2018). Extracting useful knowledge from event logs: A frequent itemset mining approach. Knowledge‐Based Systems, 139, 132–148.
Ester,, M., Kriegel,, H. P., Sander,, J., & Xu,, X. (1996). A density‐based algorithm for discovering clusters a density‐based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the second international conference on knowledge discovery and data mining KDD’96 (pp. 226–231). AAAI Press. http://dl.acm.org/citation.cfm?id=3001460.3001507
Evermann,, J., Rehse,, J., & Fettke,, P. (2016). Process discovery from event stream data in the cloud—A scalable, distributed implementation of the flexible heuristics miner on the Amazon kinesis cloud infrastructure. In CloudCom IEEE (pp. 645–652). New York, NY: IEEE.
Ezeife,, C. I., & Lu,, Y. (2005). Mining web log sequential patterns with position coded pre‐order linked WAP‐tree. Data Mining and Knowledge Discovery, 10(1), 5–38.
Gama,, J. (2010). Knowledge discovery from data streams. In Chapman and Hall/CRC data mining and knowledge discovery series. Boca Raton, FL: CRC Press.
Hassani,, M. (2015). Efficient clustering of big data streams (PhD thesis). RWTH Aachen University.
Hassani,, M., & Seidl,, T. (2011). Towards a mobile health context prediction: Sequential pattern mining in multiple streams. In MDM IEEE (pp. 55–57). New York, NY: IEEE.
Hassani,, M., Siccha,, S., Richter,, F., & Seidl,, T. (2015). Efficient process discovery from event streams using sequential pattern mining. In SSCI IEEE (pp. 1366–1373). New York, NY: IEEE.
Hassani,, M., Spaus,, P., Gaber,, M. M., & Seidl,, T. (2012). Density‐based projected clustering of data streams. In Proceedings of the 6th international conference on scalable uncertainty management SUM ‘12 (pp. 311–324). Berlin, Germany: Springer‐Verlag.
Hassani,, M., Spaus,, P., & Seidl,, T. (2014). Adaptive multiple‐resolution stream clustering. In MLDM `14 (pp. 134–148). Cham, Switzerland: Springer.
Hassani,, M., Töws,, D., Cuzzocrea,, A., & Seidl,, T. (2017). BFSPMiner: An effective and efficient batch‐free algorithm for mining sequential patterns over data streams. International Journal of Data Science and Analytics. Springer International Publishing. https://doi.org/10.1007/s41060-017-0084-8
Hassani,, M., Töws,, D., & Seidl,, T. (2017). Understanding the bigger picture: Batch‐free exploration of streaming sequential patterns with accurate prediction. In SAC (pp. 866–869). New York, NY: ACM.
Ho,, C. C., Li,, H. F., Kuo,, F. F., & Lee,, S. Y. (2006). Incremental mining of sequential patterns over a stream sliding window. In ICDM Workshops IEEE (pp. 677–681). New York, NY: IEEE.
Koper,, A., & Nguyen,, H. S. (2011). Sequential pattern mining from stream data. Advanced Data Mining and Applications. Lecture Notes in Computer Science (Vol. 7121, pp. 278–291). Berlin, Germany: Springer‐Verlag.
Le,, H. B., Duong,, H. V., Truong,, T. C., & Fournier‐Viger,, P. (2017). FCloSM, FGenSM: Two efficient algorithms for mining frequent closed and generator sequences using the local pruning strategy. Knowledge and Information Systems, 53, 71–107.
Leemans,, M., & van der Aalst,, W. M. P. (2014). Discovery of frequent episodes in event logs. In SIMPDA, revised selected papers (pp. 1–31). Cham, Switzerland: Springer.
Leemans,, S. J. J., Fahland,, D., & van der Aalst,, W. M. P. (2013). Discovering block‐structured process models from event logs—A constructive approach. In J. M. Colom, & J. Desel, (Eds.), Application and theory of Petri nets and concurrency (pp. 311–329). Berlin, Heidelberg: Springer.
Leno,, V., Armas‐Cervantes,, A., Dumas,, M., Rosa,, M. L., & Maggi,, F. M. (2018). Discovering process maps from event streams. In ICSSP (pp. 86–95). New York, NY: ACM.
Lu,, X., Fahland,, D., Andrews,, R., Suriadi,, S., Wynn,, M. T., ter Hofstede,, A. H. M., & van der Aalst,, W. M. P. (2017). Semi‐supervised log pattern detection and exploration using event concurrence and contextual information. In OTM, CoopIS, C%26TC, and ODBASE (pp. 154–174). Rhodes, Greece: Springer Verlag.
Manku,, G. S., & Motwani,, R. (2002). Approximate frequency counts over data streams. In VLDB (pp. 346–357). VLDB Endowment. http://www.vldb.org/
Mannhardt,, F., de Leoni,, M., Reijers,, H. A., van der Aalst,, W. M. P., & Toussaint,, P. J. (2018). Guided process discovery—A pattern‐based approach. Information Systems, 76, 1–18.
Mannhardt,, F., & Tax,, N. (2017). Unsupervised event abstraction using pattern abstraction and local Process models. CEUR Workshop Proceedings 1859 (pp. 55–63). Aachen, Germany: CEUR‐WS.org.
Mannhardt,, F. F. (2017). Hospital billing—Event log. Eindhoven: Eindhoven University of Technology. https://doi.org/10.4121/uuid:76c46b83-c930-4798-a1c9-4be94dfeb741
Mannila,, H., Toivonen,, H., & Verkamo,, A. I. (1997). Discovery of frequent episodes in event sequences. Data Mining and Knowledge Discovery, 1(3), 259–289.
Mendes,, L. F., Ding,, B., & Han,, J. (2008). Stream sequential pattern mining with precise error bounds. In ICDM IEEE (pp. 941–946). New York, NY: IEEE.
Mooney,, C., & Roddick,, J. F. (2013). Sequential pattern mining—Approaches and algorithms. ACM Computing Surveys, 45, 19:1–19:39.
Muthukrishnan,, S. (2005). Data streams: Algorithms and applications. Foundations and Trends in Theoretical Computer Science, 1(2), 117–236.
Pei,, J., Han,, J., Mortazavi‐Asl,, B., Pinto,, H., Chen,, Q., Dayal,, U., & Hsu,, M.‐C. (2001). Prefixspan: Mining sequential patterns efficiently by prefix‐projected pattern growth. Proceedings 17th International Conference on Data Engineering (ICDE) (pp. 0215–0225). Washington, DC: IEEE Computer Society.
Reisig,, W. (2013). Understanding Petri nets—modeling techniques, analysis methods, case studies. Berlin: Springer.
Sani,, M. F., van Zelst,, S. J., & van der Aalst,, W. M. P. (2018). Applying sequence mining for outlier detection in process mining. In On the move to meaningful internet systems (CoopIS 2018) Lecture notes in computer science. Berlin: Springer.
Tax,, N., Genga,, L., & Zannone,, N. (2017). On the use of hierarchical subtrace mining for efficient local process model mining. CEUR Workshop Proceedings 2016 (pp. 8–22). Aachen, Germany: CEUR‐WS.org.
Tax,, N., Sidorova,, N., Haakma,, R., & van der Aalst,, W. M. P. (2016). Mining local process models. Journal of Innovation in Digital Ecosystems, 3(2), 183–196.
Tax,, N., Sidorova,, N., van der Aalst,, W. M. P., & Haakma,, R. (2016). Heuristic approaches for generating local process models through log projections. In IEEE SSCI (pp. 1–8). New York, NY: IEEE.
Tax,, N., Sidorova,, N., van der Aalst,, W. M. P., & Haakma,, R. (2018). LocalProcessModelDiscovery: Bringing Petri nets to the pattern mining world. In PETRI NETS (pp. 374–384). Cham, Switzerland: Springer.
van der Aalst,, W. M. P. (2013). Decomposing Petri nets for process mining: A generic approach. Distributed and Parallel Databases, 31(4), 471–507.
van der Aalst,, W. M. P. (2016). Process mining—Data science in action (2nd ed.). Berlin: Springer.
van Dongen,, B. F. (2011). Real‐life event logs—Hospital log. Eindhoven: Eindhoven University of Technology. https://doi.org/10.4121/uuid:d9769f3d-0ab0-4fb8-803b-0d1120ffcf54
van Zelst,, S. J., van Dongen,, B. F., & van der Aalst,, W. M. P. (2018). Event stream‐based process discovery using abstract representations. Knowledge and Information Systems, 54(2), 407–435. https://doi.org/10.1007/s10115-017-1060-2
Weijters,, A. J. M. M., & Ribeiro,, J. T. S. (2011). Flexible heuristics miner (FHM). In IEEE CIDM (pp. 310–317). New York, NY: IEEE.
Weijters,, A. J. M. M., & van der Aalst,, W. M. P. (2003). Rediscovering workflow models from event‐based data using little thumb. Integrated Computer‐Aided Engineering, 10(2), 151–162.
Zaki,, M. J. (2001). SPADE: An efficient algorithm for mining frequent sequences. Machine Learning, 42, 31–60.
Zhong,, N., Li,, Y., & Wu,, S. T. (2012). Effective pattern discovery for text mining. IEEE Transactions on Knowledge and Data Engineering, 24, 30–44.
Zhou,, C., Cule,, B., & Goethals,, B. (2015). A pattern based predictor for event streams. Expert Systems with Applications, 42, 9294–9306.

Access to this WIREs title is by subscription only.

Recommend to Your
Librarian Now!

On the application of sequential pattern mining primitives to process discovery: Overview, outlook and opportunity identification

Browse by Topic

Access to this WIREs title is by subscription only.

The latest WIREs articles in your inbox