Welcome to the PADS Blog!

This post has been authored by Viki Peeva.

Local process models (LPMs) are behavioral patterns that describe process fragments and are used to analyze processes.

If we take our “definition” apart, there are three important parts regarding LPMs:

1. They are a specific type of pattern.
2. They do not care about the entire process but only about parts of it.
3. They help us analyze and understand the process locally.

Now, let us begin!

Why are patterns important?

In data science, patterns are recurring structures or trends in the dataset. Frequent item sets and building association rules are classic examples. However, we can also consider pattern mining when we find correlations (correlation patterns), classification or clustering boundaries (separation patterns), the common ground of outliers (outlier patterns), or the famous king – man + woman = queen in word embeddings (latent patterns).

Example association rule and word embedding pattern.

Conclusion: Patterns are omnipresent in the data world, even when it does not look like that at first glance. This deduction also holds with event data. In the process mining world, we characterize patterns linked to control flow as behavioral patterns. So, next, we look at what are behavioral patterns.

What are behavioral patterns?

Consider sequential patterns, like the market basket analysis, but with time. Such sequential patterns are one example of behavioral patterns. Sequential patterns describe sequences of steps in our analyzing process [1]. If that process is buying in the supermarket, we can track what is put in the basket and in which order. That way, the supermarket might adapt product placement. However, considering hundreds or even thousands of customers visit the supermarket every day, if we try to model all their behaviors, it will probably look like a big plate of spaghetti. Hence, patterns.

Example sequential patters for buying behavior in supermarket.

The term behavioral patterns also covers patterns allowing more elaborate control-flow constructs* or defining constraints. For example, while sequences can model only sequential relationships, episodes allow concurrency modeling [2], and LPMs additionally allow choices and loops [3]. Declarative patterns allow defining constraints of what should happen first, how often, or in what order [4].

Example sequence, episode, and LPM pattern.

 

*Only if you are interested: These control-flow constructs are a subset of workflow patterns covered by the workflow initiative (see http://www.workflowpatterns.com/patterns/data/).

 

How do LPMs fit the picture?

LPMs are behavioral patterns that can model sequence, concurrency, choice, and loop. This realization covers the first important point we made at the start. In the beginning, the purpose of LPMs was the explainability of highly unstructured processes [3]. Remember the buying process in the supermarket and the thousands of customers. For these processes, traditional discovery approaches have difficulty discovering a structured process model, so they would return a spaghetti or a flower model. Hence, LPMs were supposed to have the expressiveness of traditional process models but show what happens locally and ignore the rest. However, practice has shown that LPMs are much more versatile. To prove our third point – LPMs are used to analyze processes – process miners have used them for trace encoding, event abstraction, trace classification and clustering, discovery, or in different use-case scenarios [5-8].

LPMs as replacement for flower and spaghetti process models together with various other applications like event abstraction, trace embedding, and model repair.

Nevertheless, to truly understand LPMs, we have to go back to the event log and make the connection to why LPMs describe process fragments. The simple answer is that they are patterns, but let’s dig deeper.

Let us consider the trace below. When we talk about LPMs, we look at things locally, and this locality can be as small as two events or as big as the entire process execution. Second, LPMs can ignore or skip events. Patterns do not say: “oh, excuse me, I won’t occur unless I cover everything”. No, patterns can occur hidden between events that do not matter as shown in the figure below. So when we search for them, we should be able to handle these situations. If we consider these two crucial parts together, we get to the second point of LPMs: they describe process fragments and not entire processes.

 

Mapping an LPM onto a trace. Locality is denoted with orange boundaries, activity mappings with blue arrows, and ignored events as question marks in red bounding box.

So far, we have covered LPMs, how they look, and their link to event logs. The next step would be discovery. Several discovery approaches exist [3,9-10], but we won’t discuss those here. We will finish with our opinion of what is next in this research area.

Where do we go from here?

Discovery. As mentioned before, multiple LPM discovery algorithms are available. All of them have strengths and weaknesses, so one way forward is to consider alternative discovery techniques or extensions of existing ones where specific weaknesses are addressed.

Pattern Explosion. On the one hand, LPM discovery, similar to any pattern discovery, suffers from the significant challenge of pattern explosion. In other words, too many patterns or LPMs are built for a human analyst to analyze. On the other hand, LPMs are versatile, meaning they can be used with different end goals in mind. Hence, the ideal solution would be to choose a unique subset of discovered LPMs that best fit the posed research question.

Conformance Checking. After discovering and choosing the optimal set of LPMs, we would like to go back to the data. Which parts of the event log do the LPMs cover? This can enable enhancing the LPMs with data perspective or specific key performance indicators (KPIs).

Much More. The world of LPMs is vast, and there’s always more to explore. If you have questions or ideas, I encourage you to share them in the comments below.

Keywords: behavioral patterns, local process models, complex models.

Icon attribution: The icons used in all figures are listed in https://github.com/VikiPeeva/SharingResources/blob/main/attribution/icons/LPMIntroPADSBlog.md

References

[1] Srikant, R., & Agrawal, R. (1996). Mining sequential patterns: Generalizations and performance improvements. In P. Apers, M. Bouzeghoub, & G. Gardarin (Eds.), Advances in Database Technology—EDBT ’96 (Vol. 1057, pp. 1–17). Springer Berlin Heidelberg. https://doi.org/10.1007/BFb0014140

[2] Leemans, M., & Van Der Aalst, W. M. P. (2015). Discovery of Frequent Episodes in Event Logs. In P. Ceravolo, B. Russo, & R. Accorsi (Eds.), Data-Driven Process Discovery and Analysis (Vol. 237, pp. 1–31). Springer International Publishing. https://doi.org/10.1007/978-3-319-27243-6_1

[3] 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. https://doi.org/10.1016/j.jides.2016.11.001

[4] Pesic, M., & Van Der Aalst, W. M. P. (2006). A Declarative Approach for Flexible Business Processes Management. In J. Eder & S. Dustdar (Eds.), Business Process Management Workshops (Vol. 4103, pp. 169–180). Springer Berlin Heidelberg. https://doi.org/10.1007/11837862_18

[5] Mannhardt, F., & Tax, N. (2017). Unsupervised Event Abstraction using Pattern Abstraction and Local Process Models (No. arXiv:1704.03520). arXiv. http://arxiv.org/abs/1704.03520

[6] Pijnenborg, P., Verhoeven, R., Firat, M., Laarhoven, H. V., & Genga, L. (2021). Towards Evidence-Based Analysis of Palliative Treatments for Stomach and Esophageal Cancer Patients: A Process Mining Approach. 2021 3rd International Conference on Process Mining (ICPM), 136–143. https://doi.org/10.1109/ICPM53251.2021.9576880

[7] Leemans, S. J. J., Tax, N., & Ter Hofstede, A. H. M. (2018). Indulpet Miner: Combining Discovery Algorithms. In H. Panetto, C. Debruyne, H. A. Proper, C. A. Ardagna, D. Roman, & R. Meersman (Eds.), On the Move to Meaningful Internet Systems. OTM 2018 Conferences (Vol. 11229, pp. 97–115). Springer International Publishing. https://doi.org/10.1007/978-3-030-02610-3_6

[8] Kirchner, K., & Marković, P. (2018). Unveiling Hidden Patterns in Flexible Medical Treatment Processes – A Process Mining Case Study. In F. Dargam, P. Delias, I. Linden, & B. Mareschal (Eds.), Decision Support Systems VIII: Sustainable Data-Driven and Evidence-Based Decision Support (Vol. 313, pp. 169–180). Springer International Publishing. https://doi.org/10.1007/978-3-319-90315-6_14

[9] Peeva, V., Mannel, L. L., & Van Der Aalst, W. M. P. (2022). From Place Nets to Local Process Models. In L. Bernardinello & L. Petrucci (Eds.), Application and Theory of Petri Nets and Concurrency (Vol. 13288, pp. 346–368). Springer International Publishing. https://doi.org/10.1007/978-3-031-06653-5_18

[10] Acheli, M., Grigori, D., & Weidlich, M. (2019). Efficient Discovery of Compact Maximal Behavioral Patterns from Event Logs. In P. Giorgini & B. Weber (Eds.), Advanced Information Systems Engineering (Vol. 11483, pp. 579–594). Springer International Publishing. https://doi.org/10.1007/978-3-030-21290-2_36