Temporal Association Rules from Motifs

In machine learning, we distinguish between functional and symbolic learning. The former encompasses strategies for representing the theory underlying a certain phenomenon as functions, while the latter derives logical descriptions of that phenomenon. Traditional symbolic methods rely on propositional logic and assume static data, in which each instance is described by $n$ attributes. Temporal data, however, cannot be successfully dealt within the same schema in a native way, and it is commonly pre-processed (e.g., via averaging attributes along all dimensions) to appear static, enabling standard symbolic techniques.

Modal, and in particular temporal symbolic learning [8, 12] takes a different point of view: modal symbolic methods are characterized by being based on modal logic (e.g., temporal logic) so that non-static data can be dealt with natively, and that the extracted knowledge takes the form of interpretable modal logic formulas. Association rule extraction techniques can benefit from a similar approach [9, 14], with the introduction of the modal adaptation of the known frequent set extraction algorithms, namely APRIORI [1] and FP-Growth [5]. In particular, the temporal case is considered a representative example to illustrate the qualities and characteristics of modal association rules. Nevertheless, the original approach presents some important limitations, originating from the basic definition of temporal alphabet, which may cause difficult-to-interpret association rules. One way to overcome the limits in alphabet definition towards temporal association rule extraction is to consider time series motifs, that is, patterns that are considered interesting because they frequently occur.

In this paper, we consider the problem of temporal rule extraction from time series using a motif-based alphabet. We adapt the original definition of local support, introduced in [9, 14], to accommodate motifs suitably, and apply our methodology to two temporal datasets, showing how the obtained rules have an immediate natural language translation.

Motif discovery for time series was introduced in 2003 [4], generating quite a body of research. Virtually every time series data mining technique has been applied to the motif discovery problem, including indexing, data discretization, triangular-inequality pruning, hashing, early abandoning.

Given a subsequence, we can compute its distance to all subsequences in the same time series.

Distance profiles are collected in a distance matrix, from which a matrix profile is built.

For each position $i$ in a matrix profile $P$, if the value $P_i$ is lower than a threshold $\alpha$, we say that $T_{i(i+l)}$ is an instance of a motif.

Note that both the literature and the maintained packages on motif discovery are relatively extensive; in this work, we enrich the existing software ecosystem with the framework Sole.jl ¹¹1See https://github.com/aclai-lab/Sole.jl and https://github.com/aclai-lab/
ModalAssociationRules.jl., an open source solution for symbolic learning with non-tabular data, leveraging the MatrixProfile.jl ²²2https://github.com/baggepinnen/MatrixProfile.jl library, which implements the STAMP algorithm [15] for computing the matrix profile of a time series, allowing for motifs discovery.

In this paper, we are interested in learning association rules from data. Fixed an alphabet of propositional literals $𝒫=\{p_1,\mathrm{\dots },p_k\}$, a propositional rule is an object of the type $\rho :X\Rightarrow Y$, where $X\subset 𝒫$ is called antecedent, $Y\subset 𝒫$ is called consequent, and $X\cap Y=\mathrm{\varnothing }$; following the classical jargon, we refer to each literal as item and we call a set of items as itemset. In this scenario, $X\cup Y$ is considered interesting when it is frequent, that is, if it occurs more often than a predetermined threshold referred to as minimum support, and a rule $X\Rightarrow Y$ is extracted if the ratio between the support of $X$ and that of $X\cup Y$ is higher than another predetermined threshold known as minimum confidence.

While classical association rules are designed for propositional patterns to emerge, temporal association rules are designed to generalize this idea to patterns with a temporal component. The natural choice to describe temporalized co-occurrence of events or patterns with a duration is Halpern and Shoham modal logic of time intervals (HS), defined over Allen’s relations, as show in Tab. 1.

Interval temporal logic gives us a way to naturally describe temporal association rules, as time series can be naturally seen as interval models. Let $𝔗=\{{𝒯}_1,\mathrm{\dots },{𝒯}_m\}$ be a set of (multivariate) time series, or temporal dataset, and fix a propositional alphabet $𝒫$; let us also assume that each time series in $𝔗$ is based on the same temporal domain $D$. Each single multivariate time series $𝒯$ is a collection of $n$ time series $T_1,\mathrm{\dots },T_n$; elements of $𝒫$ are naturally associated to a specific time series. In this way, if $𝒯$ is a multivariate time series (i.e., an interval model), $[i,j]$ is an interval, and $\phi$ an interval formula, the notion of $𝒯,[i,j]⊩\phi$ can be interpreted as the notion of $𝒯$ satisfies $\phi$ at $[i,j]$.

A temporal itemset is a set of temporal items, that is, items enriched with a temporal relation, and temporal rules are such that antecedents and consequents are temporal itemsets. The notion of support is generalized to the case of a temporal dataset $𝔗$ by distinguishing a local support, computing the relative frequency of a temporal itemset occurring in some instance $𝒯\in 𝔗$, and a global support, counting the number of instances such that their local support is higher than a minimum local support threshold. An itemset $X$ is said to be frequent if its global support is greater than a minimum global support threshold. In this scenario, ModalAPRIORI [14] and ModalFP-Growth [9] can be used to extract temporal patterns as a particular case of modal patterns.

Let us consider a set of feature extraction functions $ℱ=\{F_1,\mathrm{\dots },F_k\}$, where each function $F$ is defined as $F:{ℝ}^d\to ℝ$ for some natural value $d\le N$. Theoretically speaking, given a multivariate time series $𝒯$, it is possible to define an alphabet of items based on $ℱ$, that is, $𝒫=\{\alpha \le F(T)\le \beta \mid F\in ℱ,T\in 𝒯,\alpha \in ℝ\cup \{-\mathrm{\infty }\},\beta \in ℝ\cup \{+\mathrm{\infty }\}\}$, which allows for mining temporal association rules, as items can be immediately interpreted over intervals, obtaining a scalar value which can be compared with lower and upper bounds $\alpha ,\beta$.

Unfortunately, it can be shown that this approach may introduce strong bias during (local) support computation, leading to promising association rules which, however, encode trivialities. An intuition about this is that the scalar value obtained by applying a feature extraction function to an interval $[i,j]$, could be redundant with many other identical values obtained by applying the same function on sub-intervals or super intervals of $[i,j]$ (e.g., considering max, min, average functions, but even more refined functions such as catch22 [7]).

To avoid flattening intervals with feature extraction functions, we modify the definition of the alphabet. We consider a set ${𝒜}_{𝔗}$ of the most representative motifs for the temporal dataset $𝔗$, that is, the distinct motifs approximating the largest fraction of data in $𝔗$ [6]. Fixed a distance function $\delta$ and a constant $\alpha$, we define a motif-based temporal alphabet as:

This is a first step towards dealing with intervals natively, as a given non-temporal item $p\in 𝒫$ is true on $T_{ij}$ if and only if the behaviour of $T$ within the segment is close enough to the motif $\mu$ encapsulated by $p$. However, the definition above is insufficient to guarantee that the computation of local support is unbiased. For example, we can consider a temporal item enriched with Allen’s $⟨B⟩$ relation: if it is true on $T_{ij}$, then it automatically inflates the support computation, as it is trivially true on all the interval $T_{i(j+1)}\mathrm{\dots }{T}_{iN}$.

To ensure a fair support computation, we must “anchor” temporal items to a specific temporal frame, that is, the temporal relations must be applied to the subset of intervals having at least one non-temporal item true on them, instead of possibly any interval. This consideration is also crucial when translating an itemset to natural language, as it naturally filters out two tricky scenarios: firstly, the case in which a conjunction of only temporal items is considered, as it is no clear the set of intervals they refer to, and, secondly, it ensures that two non-temporal items wrapping motifs of different lengths are not mixed, as the number of intervals the two items can be true at the same time is 0.

In this way, the length of intervals that may potentially satisfy the entire itemset is fixed, allowing us to define the frequency of that itemset in a truly representative way.

Using the motif-based support, we proceed to comment our experiments.

We consider two well-known public datasets concerning human gestures and gait recognition, namely NATOPS [13], from which we consider an arm gesture called “I have command”, and HuGaDB [3], from which we consider the “Walk” movement, aiming to describe insightful common patterns and to express them in natural language.

In both cases, we mine frequent itemsets by leveraging ModalAPRIORI. First of all, we extract the top $5$ motifs with length $10$ and the top $3$ with length $20$, in order to capture qualitatively appreciable patterns; the two class of motifs encodes a behaviour expressed respectively in nearly half a second and one second: shorter subsequences would bring little informativeness, while longer one would be too coarse. We establish two thresholds for minimum local and global support, respectively $s_l$ and $s_g$, to $0.1$, which is relatively low: this is not a problem, as the vast majority of the association rules generated after the itemset extraction phase ($14233$ for “I have command”, $253$ for “Walking”) are filtered out by leveraging confidence and lift [2] meaningfulness measures. In particular, the higher the lift, the more the antecedent and the consequent of a rule are positively correlated.

The motif-based alphabet is generated considering the Z-normalized Euclidean distance $\delta$. We choose the threshold $\alpha$ associated to a specific motif $\mu$ to be the tenth percentile of the values in the distance profile of $\mu$; in this way, we ensure each single non-temporal item to be frequent. We enrich the propositional alphabet with the set of temporal items ${\mathrm{\Lambda }}_{𝒫}$ obtained by considering every Allen’s relation.

Even if we did not graphically shown an example of “I have command” gesture, we try to describe a chunk of it with the following rule we extracted, which exhibits a perfect confidence (of $1.0$) and an high lift (of $6.7$). The rule is expressed in a compact format, fixing a coordinate, leveraging superscripts to provide an intuition about the movement captured by the motif underlying each item, and subscripts to indicate the length of the motif and which body part it refers to (e.g., re for right elbow, rh for right hand).

The rule above can be read as whenever the right hand of the operator is completely stretching in front of him/her and their elbow goes all the way up on the y-axis, the same elbow started the movement range in a rest position and, near the end of the movement range, the operator’s right hand is moving to the left, but will soon change direction.

The following pair of rules describes a non-trivial behaviour typical of the walking gait; note that rf (lf) stands for right (left) foot, while rt (lt) stands for right (left) thigh.

The rules states that when the right (left) foot accelerates forward (backwards) for approximately half of a second, then the left (right) thigh accelerates upward immediately after.

In this paper we introduced a motif-based approach to temporal alphabet definition and rule extraction. By leveraging motifs-based frequently recurring patterns in time series, we obtained a more interpretable and structurally robust framework for mining temporal association rules, solving the biases introduced by naive alphabet definitions and enhancing semantic clarity. We formalized the concept of anchored itemsets and introduced a novel definition of motif-based local and global support, ensuring that patterns are both meaningful and computationally tractable. Experimental validation on temporal datasets demonstrates the expressiveness and interpretability of the extracted rules, showing promise for applications in explainable temporal data analysis.