Generating time-based label refinements to discover more precise process models

2.1.Event logs and their components

An event is the most elementary element of an event log. Let I be a set of event identifiers, T be the time domain, and A1×⋯×An be an attribute domain consisting of n attributes (e.g., resource, activity name, cost, etc.). An event is a tuple e=(i,at,a1,…,an), with i∈I, at∈T, and (a1,…,an)∈A1×⋯×An. The event label of an event is formed by the values of its event attributes (a1,…,an). Functions id(e), label(e), and time(e) respectively return the id, the event label and the timestamp of event e. E=I×T×A1×⋯×An is a universe of events over A1,…,An. The rows of Table 1 are events from an event universe over the event attributes address, type, location and sensor value.

Events are often considered in the context of other events. We call E⊆E an event set if E does not contain multiple events with the same event identifier. The events in Table 1 together form an event set. A trace σ is a finite sequence formed by the events from an event set E⊆E that respects the time ordering of events, i.e., for all k,m∈N, 1⩽k<m⩽|E|, we have: time(σ(k))⩽time(σ(m)). We define the universe of traces over event universe E, denoted Σ(E), as the set of all possible traces over E. We omit E in Σ(E) and use the shorter notation Σ when the event universe is clear from the context.

Often it is useful to partition an event set into smaller sets in which events belong together according to some criterion. We might for example be interested in discovering the typical behavior within a household over the course of a day. In order to do so, we can group together events with the same address and the same day-part of the timestamp (both indicated in gray), as indicated by the horizontal lines in Table 1. For each of these event sets, we can construct a trace; timestamps define the ordering of events within the trace. For events of a trace having the same timestamps, an arbitrary ordering can be chosen within a trace.

Formally, this process of generating traces from an event set is performed based on an event partitioning function, which is a function ep:E→Tid that defines the partitioning of an arbitrary set of events E⊆E from a given event universe E into event sets E1,…,Ej,… where each Ej is the maximal subset of E such that for any e1,e2∈Ej, ep(e1)=ep(e2); the value of ep shared by all the elements of Ej defines the value of the trace attribute Tid. Note that multidimensional trace attributes are also possible, i.e., a combination of the name of the person performing the activity and the date of the event, so that every trace contains activities of one person during one day. The event sets obtained by applying an event partitioning can be transformed into traces (respecting the time ordering of events). Table 1 indicates one example of a trace that is generated by defining function ep such that events are grouped on the day-part of the timestamp as well as one the address (both indicated in gray).

An event log L is a finite set of traces L⊆Σ(E) such that ∀σ∈L:∀e1,e2∈σ:ep(e1)=ep(e2). AL⊆A1×⋯×An denotes the alphabet of event labels, also called the set of event labels, that occur in log L. The traces of a log are often transformed before doing further analysis: very detailed but not necessarily informative event descriptions are transformed into some coarse-grained and interpretable event labels. To form event labels for the events of the log in Table 1, the sensor values could be abstracted to on and off, or event labels can be redefined to a subset of the event attributes, e.g., leaving the sensor values out completely.

After this relabeling step, some traces of the log can become identically labeled (the event id’s would still be different). The information about the number of occurrences of a sequence of event labels in an event log is highly relevant for process mining, since it allows process discovery algorithms to differentiate between the mainstream behavior of a process (i.e., frequently occurring behavioral patterns) and the exceptional behavior.

Let E1,E2 be event universes. A function l:E1→E2 is an event relabeling function when it satisfies id(e)=id(l(e)) and time(e)=time(l(e)) for all events e∈E1. A relabeling function can be used to obtain more useful event labels than the full set of event attribute values, by lifting those elements of the attribute space to the event label that result in strong ordering relations in the resulting log. We lift l to event logs. Let E,E1,E2 be event universes with E,E1,E2 being pairwise different. Let l1:E→E1 and l2:E→E2 be event relabeling functions. Relabeling function l1 is a refinement of relabeling function l2, denoted by l1⪯l2, iff ∀e1,e2∈E:label(l1(e1))=label(l1(e2))⟹label(l2(e1))=label(l2(e2)); l2 is then called an abstraction of l1.

An example of an event relabeling function l would be one that relabels events from an event universe E1 over the event attributes address, type, location, and sensor value (the events in Table 1 are from E1) to the event universe E∈ over the event attributes type and address. Applying this relabeling function l to the events of the event log shown in Table 1 results for example in event label Motion sensor Bedroom for the event with id 1, Power sensor Water cooker for the event with id 5, etc.

2.2.Process models and process discovery

The goal of process discovery is to discover a process model that represents the behavior seen in an event log. The activities/transitions in this discovered process model describe allowed orderings over the event labels of the events in the event logs. A frequently used process modeling notation in the process mining field is the Petri net notation [29]. Petri nets are directed bipartite graphs consisting of transitions and places, connected by arcs. Transitions represent activities, while places represent the enabling conditions of transitions. Labels are assigned to transitions to indicate the type of activity that they model. A special label τ is used to represent invisible transitions, which are only used for routing purposes and not recorded in the log.

A labeled Petri net N=⟨P,T,F,AM,ℓ⟩ is a tuple where P is a finite set of places, T is a finite set of transitions such that P∩T=∅, F⊆(P×T)∪(T×P) is a set of directed arcs, called the flow relation, AM is an alphabet of labels representing activities, with τ∉AM being a label representing invisible events, and ℓ:T→AM∪{τ} is a labeling function that assigns a label to each transition. For a node n∈P∪T we use ∙n and n∙ to denote the set of input and output nodes of n, defined as ∙n={n′∣(n′,n)∈F} and n∙={n′∣(n,n′)∈F}. An example of a Petri net can be seen in Fig. 1, where circles represent places and rectangles represent transitions. Gray transitions having a smaller width represent invisible, or τ, transitions.

Fig. 1.

An example Petri net.

A state of a Petri net is defined by its marking M∈NP being a multiset of places. A marking is graphically denoted by putting M(p) tokens on each place p∈P. A pair (N,M) is called a marked Petri net. State changes occur through transition firings. A transition t is enabled (can fire) in a given marking M if each input place p∈∙t contains at least one token. Once a transition fires, one token is removed from each input place of t and one token is added to each output place of t, leading to a new marking. An accepting Petri net is a 3-tuple (N,Mi,Mf) with N a labeled Petri net, Mi an initial marking, and Mf a final marking. Visually, places that belong to the initial marking contain a token (e.g., p1 in Fig. 1), and places that belong to the final marking are depicted as . Many process modeling notations, including accepting Petri nets, have formal executional semantics and a model defines a language of accepting traces L. The language of a Petri net consists of all sequences of activities that have a firing sequence through the Petri net that starts in the initial marking and ends in the final marking. For the Petri net in Fig. 1, the language of accepting traces is {⟨A,B,D,E,F⟩,⟨A,B,D,F,E⟩,⟨A,C,D,E,F⟩,⟨A,C,D,F,E⟩}. In words: the process starts with activity A, followed by a choice between activity B and C, followed by activity D, finally followed by activity E and F in parallel (i.e., they can occur in any order). We refer the reader to [29] for a more thorough introduction of Petri nets.

For an event log L and a process model M we say that L is fitting on process model M if L⊆L(M). Precision is related to the behavior that is allowed by a process model M that was not observed in the event log L, i.e., L(M)∖L. The aim of process discovery is to discover a process model based on and event log L that has both high fitness (i.e., it allows for the behavior seen in the log) and high precision (i.e., it does not allow for too much behavior that was not seen in the log). Many process discovery algorithms have been proposed throughout the years, including techniques based on Integer Linear Programming and the theory of regions [48], Inductive Logic Programming [12], maximal pattern mining [24], or based on heuristic techniques [2,53]. We refer the reader to [46] for a thorough introduction of several process discovery techniques.

In process discovery tasks on event logs from the business process management domain, events are often simply relabeled to the value of an activity name attribute, which stores a generally understood name for the event (e.g., receive loan application, or decide on building permit application). However, event logs from the smart home environment domain generally do not contain a single attribute such that relabeling on that attribute enables the discovery of insightful process models [42]. In this paper we explore strategies to refine the event labels that are based on the name of the sensor in a smart home based on information about the time in the day at which the sensor was triggered.

3.1.Data-model pre-fitting stage

This stage consists of three procedures: a test for uniformity, a test for unimodality, and a method to select the number of clusters in the data. If the timestamps of a sensor type are considered to be uniformly distributed or follow a unimodal distribution, the data is considered not to be clusterable, and the sensor type will not be refined. If the timestamps are neither uniformly distributed nor unimodal, then the procedure for the selection of the number of clusters will decide on the number of clusters used for clustering.

3.2.Data-model fitting stage

A generic approach to estimate a probability distribution from data that lies on a circle or any other type of manifold (e.g., the torus and sphere) was proposed by Cohen and Welling in [6]. However, their approach estimates the probability distribution on a manifold in a non-parametric manner, and it does not use multiple probability distribution components, making it unsuitable as a basis for clustering.

We cluster events generated by one sensor using a mixture model consisting of components of the von Mises distribution, which is the circular equivalent of the normal distribution. This technique is based on the approach of Banerjee et al. [3] that introduces a clustering method based on a mixture of von Mises–Fisher distribution components, which is a generalization of the 2-dimensional von Mises distribution to n-dimensional spheres. A probability density function for a von Mises distribution with mean direction μ and concentration parameter κ is defined as pdf(θ∣μ,κ)=12πI0(κ)eκcos(θ−μ), where mean μ and data point θ are expressed in radians on the circle, such that 0⩽θ⩽2π,0⩽μ⩽2π,κ⩾0. I0 represents the modified Bessel function of order 0, defined as I0(k)=12π∫02πeκcos(θ)dθ. As κ approaches 0, the distribution becomes uniform around the circle. As κ increases, the distribution becomes relatively concentrated around the mean μ and the von Mises distribution starts to approximate a normal distribution. We fit a mixture model of von Mises components using the package movMF [17] provided in R, using the number of components found with the BIC procedure of the pre-fitting stage. A candidate label refinement is created based on the clustering result, where the original event label based on the sensor type is refined into a new number of distinct labels, each representing one von Mises component, where each event is relabeled according to the von Mises component that has the assigns the highest likelihood to the timestamp of that event.

3.3.Data-model post-fitting stage

This stage consists of two procedures: a statistical test to assess how well the clustering result fits the data, and a test to assess whether the ordering relations in the log become stronger by applying the relabeling function (i.e., whether it becomes more likely to discover a precise process model with process discovery techniques).

3.3.2.Control flow test

The clustering obtained can be used as a label refinement where we refine the original event label into a new event label for each cluster. We assess the quality of this label refinement from a process perspective using the label refinement evaluation method described in [42]. This method tests whether the log statistics that are used internally in many process discovery algorithms become significantly more deterministic by applying the label refinement. Hence, we test whether the models become more precise after time-based label refinement. An example of such a log statistic is the direct successor statistic: #L,>+(b,c) is the number of occurrences of b in the traces of L that are directly followed by c, i.e., in some σ∈L,i∈{1,…,|σ|} we have label([σ(i)])=b and label([σ(i+1)])=c, likewise, #L,>−(b,c) is the number of occurrences of b which are not directly followed by c. This control-flow test [42] outputs a p-value that indicates whether such log statistics of refined activities a1,a2,… of some activity a change with statistical significance. When #L,>+(b,c)=#L,>−(b,c) the entropy of b being directly followed by c is 1 bit, equal to a coin toss. In addition to the p-value, the test returns an information gain value, which indicates the ratio of the decrease in the total bits of entropy in the log statistics as a result of applying the label refinement. Information gain can be used as a selection criterion for label refinements when there are multiple sensor types that can be refined according to the three steps of this framework. While the entropy of a single log statistic cannot increase by applying a label refinement, the information gain of a refinement can still be negative when it is not useful, as it increases the number activities in the log and therefore also increases the total number of log statistics.

Fig. 3.

Process models discovered on the Van Kasteren data with sensor-level event labels (a) and refined event labels (b) with the Inductive Miner infrequent (20% filtering).

5.1.Label refinement selection strategies

To explore the effect of the order in which label refinements are applied, we investigate four strategies to select a set of label refinements to apply to the event log and we evaluate these four strategies on the evaluation logs. Each of the strategies assumes the desired number k of label refinements to be given.

Fig. 6.

Fitness, precision, and F-score of the Inductive Miner infrequent (20% filtering) models obtained from the original and refined versions of three event logs.

5.2.Experimental setup

Label refinements can lead to a decrease in the fitness of the resulting process model, while at the same time increasing its precision. The reason for this is that a very imprecise process model, i.e. one that allows for all behavior, is by definition perfectly fitting. As a result, changing to a process model that makes a more specific, i.e. more precise, description of the behavior can only bring fitness down. To see why refinements can increase precision while fitness can decrease, consider a refinement of a sensor type a into a refined a1 and a2 in such a way that 90% of the a1 events are directly followed by b while a2 is never followed by b. Before this refinement, the process discovery algorithm could not find any relation between a and b, as a could be followed by b, but that was not necessarily the case. After the refinement, it can find a sequential relation between a1 and b, which is more precise than the model before the refinement because it is more specific about the behavior that takes place. However, the model discovered after refinement has lower fitness, since those 10% of the a1 events were not followed by b were are not anymore adhering to the behavior that is described by the model.

We apply these four strategies on three event logs from smart home environments and measure the fitness, precision, and F-score of the models that are discovered with the Inductive Miner infrequent [21] with 20% filtering after each label refinement. The first event log is the Van Kasteren [50] event log which we introduced in Section 4. The other two event logs are two different households of a smart home experiment conducted by MIT [40]. The log Household A of the MIT experiment contains 2701 events spread over 16 days, with 26 different sensors. The Household B log contains 1962 events spread over 17 days and 20 different sensors. Note that, like for the Van Kasteren dataset, we consider the events from the MIT A and B datasets on the sensor level instead of on the human activity level. Therefore, the event labels in the log each correspond to a sensor.

The choice between the four strategies can be seen as a trade-off between the degree in which they can take the effect of the ordering of label refinements into account and the computational effort that they require. Note that when the impact of the label refinements that are already applied to the log on the information gain of succeeding label refinements is large, then we expect the exhaustive search strategy to outperform the other strategies. In contrast, in the case that label refinements are mostly mutually independent and there is no strong effect of which label refinements have already been applied to the log on the usefulness in terms of information gain when applying a certain other label refinement, then the all-at-once strategy would suffice to find a set of label refinements and the considerable computational effort needed to perform an exhaustive search would be unnecessary, thereby enabling us to find sets of label refinements for logs with high numbers of sensors. The experiments in which we apply the four search strategies to generate label refinements are intended to investigate the degree to which the order of label refinements matter, i.e., the degree to which one label refinement impacts the usefulness of other label refinements.

5.3.Results

Figure 6 shows the fitness, precision, and F-score values of the process models that were discovered after selecting label refinements with each of the four strategies on the three event logs. The precision can be improved considerably through label refinements on all three event logs.

While the fitness decreased on the MIT A log as an effect of the refinements, fitness is not so much affected by refining the labels on the MIT B and the Van Kasteren event logs. The reason for this is that is when the relation between sensors that is exposed by the label refinement holds in almost all cases, there is almost no loss in fitness, i.e., if 100% of the a1 in the previous label refinement example would have been directly followed by a b instead of only 90%, then the more precision sequential relation between a1 and b can be modeled without loss of fitness.

Note that all strategies find the exact same label refinement as first label refinement, since with only one label refinement there is no notion of interplay between label refinements. When refining a second event label the four strategies all select the same label refinement on all three logs, hinting that in practice the effect of interplay between label refinements is not very strong. Since all four strategies selected the same second label refinement, the F-score, fitness, and precision are also identical for the four strategies. Figure 6 shows that for the MIT household A data set there are 7 sensor types that can be refined, i.e., they passed the statistical tests of the pre-fitting stage and their obtained clustering passed the goodness-of-fit test. For the MIT household B data set there are 10 sensor types that can be refined and there are 8 sensor types that can be refined for the Van Kasteren data set. However, since the F-score for all strategies drops again after a few label refinements, not all of those label refinements lead to better process models. The four strategies perform very similar in terms of F-score.

Exhaustive search outperforms the other strategies for a few refinements on some logs, however, such improvements come with considerable computation times. On the MIT household B log, which has 10 possible label refinements, it takes about 25 minutes on an Intel i7 processor to evaluate all possible combinations of refinements. On logs with even more possible refinements the exhaustive strategy can quickly become computationally infeasible. The computational complexity of the exhaustive strategy stems from the fact that the ordering in which label refinements are applied can influence their information gain, and therefore the set of candidate label refinement sequences to consider is equal to the number of permutations on the number of activities (i.e. O(n!), with n the number of activities) when we restrict to only one label refinement per event label, and even more when we do not put this restriction and allow label refinements on activities that themselves originate from refinements of other activities.

The all-at-once strategy is computationally very fast and only takes milliseconds to compute on all event logs. Note that with this strategy the information gain only needs to be calculated once for every event label in the log, therefore the computational complexity is O(n), with n the number of activities. Yet, this strategy results in fitness, precision, and F-score values that are almost identical to what is obtained with the exhaustive strategy for MIT household A and Van Kasteren. When making six or more refinements on the MIT household B log, the quality of the obtained process model with the all-at-once strategy lags behind the other strategies, indicating that the label refinements that were applied earlier cause the later label refinements to be less effective. However, the optimum in F-score for this log lies at three refinements, therefore the sixth refinement, where a performance difference between non-exhaustive strategies emerges should not be performed with any of the strategies in the first place.

Since the F-score decreases again when applying too many label refinements it is important to have a stopping criterion that prevents refining the event log too much. The dashed line in Fig. 6 shows the results when we only refine a label when the information gain of the refinement is larger than zero. On the MIT households A and B logs this stopping criterion causes all strategies to stop at the best combination of label refinements in F-score, consists respectively of one and three refinements. This indicates that the control flow test [42] provides a useful stopping criterion for label refinements.

As the greedy search strategy iteratively selects the best label refinement, its computational complexity is O(n2), with n the number of activities, when we restrict to only one label refinement per event label. This is easy to see: picking the best a label refinement from all possible activities in the log that can be refined is O(n), and this procedure has to be repeated at most n times until there are no more activities left that can be refined. The computational complexity of the beam search strategy is depended on the beam size b, as b=1 is equivalent to a greedy search and b=∞ is equivalent to an exhaustive search. Note that on all logs the beam search approach with a beam size of only two resulted in the optimal process model in terms of F-score as found with the exhaustive search, while it reduces the computation time from around half an hour to milliseconds on all logs. Furthermore, the all-at-once and the greedy search strategies resulted in the optimal process model in terms of F-score as found with the exhaustive search on two of the three logs, while offering a better computational complexity than the beam search strategy, therefore these strategies might be more suitable for large-scale event logs.

All strategies except the exhaustive search strategy suggest as the fourth refinement for MIT B a refinement that decreases the F-score sharply, to increase it again with a fifth refinement. This is caused by an unhelpful refinement being found as the fourth refinement by those strategies, which causes the frequencies to drop below the filtering threshold of the Inductive Miner, leading to a model that is less precise. At the fifth refinement, the follows statistics of other activities drop as well, causing the follows statistics that dropped in the fourth refinement to be relatively higher and above the threshold again. On the Van Kasteren log the optimum in F-score is to make only one refinement, although the F-score after applying the second and third refinement as found by the exhaustive and beam search is almost identical. The all-at-once strategy stops after applying only two refinements while the other strategies apply a third refinement. The best refinement combination found with the all-at-once strategy using the stopping criterion is identical to the refinement combination found with the other strategies, suggesting that in practice the differences between the four approaches are small. On real-life smart home environment event logs the effect that one label refinement influences the control flow test outcome of others is limited.

Fig. 7.

The Inductive Miner infrequent (20% filtering) process model discovered from the original MIT a event log.

Fig. 8.

The Inductive Miner infrequent (20% filtering) process model discovered from the refined MIT A event log.

Figures 7 and 8 shows the process model that are discovered with the Inductive Miner infrequent with 20% filtering respectively from the original MIT household A event log and the event log obtained after applying the optimal combination of label refinements found in the results of Fig. 6. Because of the silent transitions, the process model discovered from the original event log allows for almost all orderings over the sensor types. Even though the transition labels in the process model discovered from the refined event log are not readable because of the size, it is clear from the structure of the process model that it is much more behaviorally specific, containing a mix of sequential orderings, parallel blocks, and choices over the sensor types. Especially interesting is the part indicated by the blue dashed ellipse, which contains a parallel block consisting of a cabinet, the oven and burner, and the dishwasher, showing a clearly recognizable cooking routine. Furthermore, the part indicated by the red dotted ellipse indicates a sequentially ordered part, consisting of some door sensor registering the opening of a door, followed by starting the washing machine and then the laundry dryer.

The time-based label refinement generation framework as well as the four strategies to generate multiple label refinements on the same event log are implemented and publicly available in the process mining toolkit ProM [49] as part of the LabelRefinements11 package.

6.1.Label splits and refinements in process mining

The task of finding refinements of event labels in the event log is closely related to the task of mining process models with duplicate activities, in which the resulting process model can contain multiple transitions/nodes with the same label. From the point of view of the behavior that is allowed by a process model, it makes no difference whether a process model is discovered on an event log with refined event labels, or whether a process model is discovered with duplicate activities such that each transition/node of the duplicate activity precisely covers one version of the refined event label. However, a refined event label may also provide additional insights as the new event labels are explainable in terms of time. The first process discovery algorithm capable of discovering duplicate tasks was proposed by Herbst and Karagiannis in 2004 [16], after which many others have been proposed, including the Evolutionary Tree Miner [5], the α∗-algorithm [23], the α#-algorithm [13], the EnhancedWFMiner [10]. An alternative approach has been proposed by Vázques-Barreiros [51] et al., who describe a local search based approach to repair a process model to include duplicate activities, starting from an event log and a process model without duplicate activities. Existing work on mining models with duplicate activities all base their duplicate activities on how well the event log fits the process model, and do not try to find semantic differences between the different versions of the activities in the form of attribute differences.

The work that is closest to our work is the work by Lu et al. [26], who describe an approach to pre-process an event log by refining event labels with the goal of discovering a process model with duplicate activities. The method proposed by Lu et al., however, does not base the relabelings on data attributes of those events and only uses the control flow context, leaving uncertainty whether two events relabeled differently are actually semantically different.

6.2.Data-aware process mining

Another area of related work is data-aware process mining, where the aim is to discover rules with regard to data attributes of events that decide decision points in the process. De Leoni and van der Aalst [7] proposed a method that discovers data guards for decision points in the process based on alignments and decision tree learning. This approach relies on the discovery of a behaviorally well-fitting process model from the original event log. When only overgeneralizing process models (i.e., allowing for too much behavior) can be discovered from an event log, the correct decision points might not be present in the discovered process model at all, resulting in this approach not being able to discover the data dependencies that are in the event log. Our label refinements use data attributes prior to process discovery to enable the discovery of more behaviorally constrained process models by bringing parts of the event attribute space to the event label.

6.3.Temporal relation mining for smart home environments

Galushka et al. [11] provide an overview of temporal data mining techniques and discuss their applicability to data from smart home environments. Many of the techniques described in the overview focus on real-valued time series data, instead of discrete sequences which we assume as input in this work. For discrete sequence data, Galushka et al. [11] propose the use of sequential rule mining techniques, which can discover rules of the form “if event a occurs then event b occurs with time T”.

Huynh et al. [18] proposed to use topic modeling to mine activity patterns from sequences of human events. Topic modeling originates from the field of natural language processing and addresses the challenge to find topics in textual documents and assign a distribution over these topics to each document. However, the discovered topics do not represent the human activities in terms of control-flow ordering constructs like sequential ordering, concurrent execution, choices, and loops.

Ogale et al. [31] proposed an approach to describe the temporal relation between human behavior activities from video data using context-free grammars, using the human poses extracted from the video as the alphabet. Like Petri nets, context-free grammars define a formal language over its alphabet. However, Petri nets have a graphical representation, which is lacking for grammars. Furthermore, as shown by Peterson [32], Petri net languages are a subclass of context-sensitive languages, and some Petri net languages are not context-free. This indicates that some relations over activities that can be expressed in Petri nets cannot be expressed in a context-free grammar.

One particularly related technique, called TEmporal RElation Discovery of Daily Activities (TEREDA), was proposed by Nazerfard et al. [30]. TEREDA leverages temporal association rule mining techniques to mine ordering relations between activities as well as patterns in their timestamp and duration. The ordering relations between activities that are discovered by TEREDA are restricted to the form “activity a follows activity b”, where our proposed approach of modeling the relations with Petri nets allow for modeling of more complex relations between larger number of activities, such as: “the occurrences of activity b that are preceded by activity a are followed by both activity d and e, but in arbitrary order”. The patterns in the timestamps are obtained by fitting a Gaussian Mixture Model (GMM) with the Expectation–Maximization (EM) algorithm, thereby ignoring problems caused by the circularity of the 24-hour clock introduced in this paper.

Jukkala and Cook [19] propose a method to mine temporal relations between activities from smart home environments logs where the temporal relation patterns are expressed in Allen’s interval algebra [1]. Allen’s interval algebra allows the expression of thirteen distinct types of temporal relations between two activities based on both the start and end timestamps of these activities. The approach of Jukkala and Cook [19] is limited to describing the relations between pairs of activities, and more complex relations between three or higher numbers of activities cannot be discovered. The aim of mining the patterns in Allen’s interval algebra representation is to increase the accuracy of activity recognition systems, while our goal is knowledge discovery. Several papers from the process mining area have focused on mining temporal relations between activities from smart home event logs. Leotta et al. [22] postulate three main research challenges for the applicability of process mining technique for smart home data. One of those three challenges is to improve process mining techniques to address the less structured nature of human behavior as compared to business processes. Our technique addresses this challenge, as the time-based label refinements help in uncovering relations between activities with process mining techniques that could not be found without applying time-based label refinements.

DiMaggio et al. [9] and Sztyler et al. [38,39] propose to mine Fuzzy Models [14] to describe the temporal relations between human activities. The Fuzzy Miner [14], a process discovery algorithm that mines a Fuzzy Model from an event log, is a process discovery algorithm that is designed specifically for weakly structured processes. However, Fuzzy Models, in contrast to Petri nets, do not define a formal language over the activities, and are therefore not precise on what activity orderings are allowed and which are not. While mining a Fuzzy Model description of human activities is less challenging compared to mining a process model with formal semantics, it is also limited in the insights that can be obtained from it.

Finally, insights in the human routines can be obtained through the discovery of Local Process Models [44], which bridges process mining and sequential pattern mining by finding patterns that include high-level process model constructs such as (exclusive) choices, loops, and concurrency. However, Local Process Models, as opposed to process discovery, only give insight into frequent subroutines of behavior and do not provide the global picture of the behavior throughout the day from start to end.