The recognition, classification and grouping of distinct process behaviours in an event log is a key aspect of process analysis. In unstructured and flexible processes contexts this is not straightforward and the literature devises different techniques to tackle the problem. An effective one has been found in trace clustering, namely a set of techniques which automatically group similar traces according to specified criteria, allowing for better understandability and decreased complexity of the analysis. However, all available clustering techniques are designed exclusively with procedural process models. For those techniques the key aspect for trace similarity is the precise sequence of execution of events, as they consider only events that immediately follow or precede one another. Yet, the properties and relations of events in a process may fall outside such a narrow scope.
In our research, we want to explore the opportunity of employing declarative process mining for trace clustering. We believe that the characteristics of declarative specifications can lead to novel results given the focus on different relations of the events in the event log. Indeed, a declarative rule describes a desired property of the process, not a specific execution. Thus, grouping around them suggests clusters centred on flexible, complex, and yet specific behaviours of the process instead of strict events sequence similarity.
Any clustering technique is based on similarity (or distance) concepts describing how close or distant objects are. Nevertheless, the current declarative rules evaluation methods are limited to devise a comprehensive similarity concept for traces based on rules. To fill this gap it is required an extensive measurement system for declarative specifications.
Trace Clustering. The goal of trace clustering is to find traces of similar behaviour and group them into clusters. The guiding rule is to maximise the similarity within a cluster while maximising the distance with the other clusters. Three main class of approaches exist: (i) Vector-based, where the traces are transformed into feature vectors and distance metrics are used in the vector space (e.g. [1], [2]); (ii) Context-aware, where string distance metrics are applied directly on the whole traces (e.g. [4], [9]); (iii) Model-based, where traces are clustered around fitting process models (e.g. [5], [6]). Trace clustering has been employed in process mining to assist the discovery of procedural process models. Dividing the event log into It can be noticed that different approaches, perspectives, and algorithms have been tried, yet all the current trace clustering techniques in process mining share, not really a limit, but rather a common trait: only procedural models are considered. Accordingly the control-flow perspective is inspected only for its continuous subsequences, i.e., only directly following relations, thus local proximity of activities is preferred in the clustering composition. This is not a limit of the clustering techniques per se, but in the object used to devise the characteristics upon which basing the clustering. For example, consider two traces xa, b, c, d, e, f y and xb, a, d, c, f, ey where the events are couple-wise swapped, but a transitivity property between tasks a, b, and c is preserved (i.e., a Ñ c Ñ e). If this transitivity property is of interest, both the traces should be grouped in the same cluster, but the directly-follow relations between the two traces is messed, thus they may result too different to appear in the same cluster. As a result, similar traces may be disjoined or different ones may be grouped. Evaluation of declarative specifications. Declarative process mining mostly resorts to quality measures from association rule mining [12] to qualify single rules with respect to event logs. Support and confidence are the most adopted measures on that regard, yet they are reportedly not sufficient to avoid a great amount of spurious results [13], which threatens the statistical soundness of the results. Also, there are different
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). definitions for support [14], [15], [16] and confidence [14], [15], [16]. For example, the support measure of [16] cannot be compared to the support of [14] because of the different definitions. Furthermore these techniques defined the measures only for a limited set of rules (i.e., the standard DECLARE rules-set). Thus, the comparison of techniques is hampered by their customized definitions of the same measures and the transferability of measures themselves between techniques is limited. The result is a scattered adoption of a small set of measures dependent either to a specific language or set of rules. Different other measures have been studied to go beyond this limit [17], yet they have been not fully exploited in process mining area. Thus a more advanced and extensive evaluation system for declarative specifications is required to base efficiently trace clustering on them.
With this research we aim to explore the integration of declarative process mining and trace clustering. The expressiveness of declarative rules can allow for a new clustering based on clear desired properties of the process, and not strict events sequences. In order to do so, an extension of the current evaluation techniques for declarative specifications is required.
A declarative specification allows for complex relations among activities regardless of their distance in the execution flow. That is because each specification models a desired properties of the process, not a specific executions. At the best of our knowledge, the combination of declarative process mining with trace clustering is still unexplored. We believe that this novel intuition can lead to distinct and interesting results, beyond the reach of procedural processes. Also, clustering around rules makes the clustering semantic explicit, easing supervised techniques and the injection of experts knowledge.
To make this clustering possible, it is mandatory to devise a similarity concept between traces and rules. Indeed a declarative injection can be used for both model-based and vector-based techniques. For both is paramount to devise an informative evaluation of the rules on the trace. The validity or violation of a rule in a trace can be a possible direction, but the boolean evaluation may be too limited to clearly differentiate the clusters. Furthermore it would be a single perspective, not enough to build a feature vector. A more flexible and broad mean of rules evaluation would be desirable, but the current declarative techniques are limited on that regard. For this reason we will devise an extensive measurement framework for declarative specifications going beyond these limits.
The goal of our measurement framework is to provide a sound ground where to define, compute, and verify measures for generic temporal logic formulae. On top of it will be based the similarity function for clustering of traces. In order to validate these results, we are going to implement the measurement framework first and the overall behavioural clustering afterwards into a proof-of-concept software with which experimental evaluations will be conducted. The empirical evaluation of the techniques will be carried out both on simulated artificial data and publicly available real-life data like BPI Challenge datasets, e.g. [18]. The controlled environment of a simulation is required to check the validity of the results in absence of a ground truth, while real-life data allows to asses the feasibility of the technique in realistic settings.
Trace clustering is a relevant topic and the employment of declarative process mining in that regard is promising and especially still unexplored. Yet, the current evaluation systems for declarative specification are not enough for a truly effective trace clustering based on them. Given these open points, there is a call for: (i) an extended evaluation system for declarative specifications. (ii) a novel application of declarative process mining for trace clustering. Markedly, we recently achieved the first point in [19], based our previous work [20].