Fast, accurate and explainable time series classification through randomization

Time series classification (TSC) aims to predict the class label of a given time series (or its feature-based representation). A time series is an ordered time-stamped sequence of observations from a variable of interest. Various TSC methods have been proposed for a rich set of application areas such as economics (e.g., financial analysis (Pattarin et al. 2004)) and medicine (e.g., classification of electrocardiograms (Karpagachelvi et al. 2012)). Up to now, the key focus for TSC was on accuracy. However, while current techniques are able to generally achieve high levels of accuracy across a range of datasets, an important criterion has been largely unaddressed: the ability to classify large datasets. Most of current state-of-the-art TSC methods are impractical (i.e., they are computationally and/or memory expensive) when classifying large datasets. A recent approach, ROCKET (Dempster et al. 2020), has recognized the need for highly efficient TSC approaches and outperforms current state-of-the-art (SOTA) TSC approaches. The key contribution of our paper is to significantly increase the efficiency compared to ROCKET as the currently fastest approach. Our paper is the first that provides a comprehensive evaluation of TSC approaches for large datasets addressing an urgent research issue.

SOTA TSC methods such as the hierarchical vote collective of transformation-based ensembles (HIVE-COTE) (Lines et al. 2018) and time series combination of heterogeneous and integrated embedding forest (TS-CHIEF) (Shifaz et al. 2020) are highly accurate, but inefficient in terms of time and memory. TS-CHIEF’s complexity is quadratic and HIVE-COTE has a bi-quadratic time complexity in the length of the time series. Recent variations of HIVE-COTE such as HIVE-COTE v1.0 (HC1) (Bagnall et al. 2020) and HIVE-COTE v2.0 (HC2) (Middlehurst et al. 2021) are no longer bi-quadratic, but are still among the slowest TSC methods. Another method, InceptionTime (Fawaz et al. 2020) recently reported SOTA classification accuracy with faster training times. However, while InceptionTime is faster than HIVE-COTE and its variations, this is largely due to the use of a GPU. When running on a CPU, InceptionTime is approximately two times slower than HC1 and HC2.

The RandOm Convolutional KErnel Transform (ROCKET) (Dempster et al. 2020) has recently claimed SOTA classification accuracy and faster training times. ROCKET is fast at training, approximately two orders of magnitude faster than HC1 and HC2. However, at testing, the difference between ROCKET and HC1 and HC2 is significantly reduced to one order of magnitude. ROCKET is currently the best suited SOTA TSC method for big data, however, its testing time could represent a drawback when classifying large datasets with very long series (Middlehurst et al. 2021).

Neither ROCKET or any other SOTA TSC method report a mechanism to explain their classifications. As these methods extract complex features based on latent features from many different time series representations/transformations, the integration of explainability is difficult. Whilst it might be possible to apply methods that provide post-hoc explanations for black box models, we will not discuss them as they are beyond the scope of this paper. Instead, we focus on techniques that integrate explanations by design. For time series it is key to identify a subset of features, in our case time intervals, that can explain which feature led to a certain classification.

In this paper, we propose a novel TSC method: the Randomized-Supervised Time Series Forest (r-STSF). r-STSF is the fastest TSC method at both training and testing; and to the best of our knowledge, r-STSF is the only TSC method that integrates explainability and achieves SOTA classification accuracy (cf. Fig. 1). As shown in Fig. 1, r-STSF is the fastest TSC method. The SOTA TSC methods such as ROCKET, HC1 and InceptionTime (ITime) are slower and do not integrate explanations. All other depicted methods do not achieve SOTA accuracy. The TSC methods HC2 and DrCIF were published while this paper was under review (hence they are in grey). HC2 is the most accurate SOTA TSC method and DrCIF is statistically as accurate as r-STSF. Both approaches are two orders of magnitude slower than r-STSF.

r-STSF is a tree-based ensemble classifier whose trees are grown using features derived from summary statistics over a number of randomly selected sub-series (sub-intervals). Classifiers based on this paradigm are known as interval-based TSC methods. Typical examples of such classifiers include time series forest (TSF) (Deng et al. 2013), time series bag-of-features (TSBF) (Baydogan et al. 2013), learned pattern similarity (LPS) (Baydogan and Runger 2016), the supervised time series forest (STSF) (Cabello et al. 2020), canonical interval forest (CIF) Middlehurst et al. (2020a), and diverse representation canonical interval forest (DrCIF) Middlehurst et al. (2021). Interval-based methods classify time series according to discriminatory phase-dependent intervals (discriminatory intervals for short hereafter), i.e., sub-series located at the same time regions over all time series that maximize class separability. As Fig. 2 shows, interval 1 is an example of a discriminatory interval. This interval differentiates the blue time series from the red ones. In contrast, interval 2 is non-discriminatory because it cannot separate the red and the blue time series.

Interval-based methods are generally fast and memory-efficient, while their tree-based structure in tandem with meaningful features (the interval features) integrate explainable classifications by design. The interval features are derived from simple transformations (i.e., statistics such as mean or standard deviation) over a number of sub-series and their meaning is easy to understand. The interactions between these features are modeled by binary trees, which are interpretable (Breiman 2001).

Our previous work (Cabello et al. 2020) proposed a highly accurate interval-based classifier, STSF, which showed that a “supervised” selection of intervals is significantly more efficient compared to one that is completely at random. Similar to TSF (Bagnall et al. 2017), it trains an ensemble of trees. The original TSF approach grows an ensemble of trees for classification, and a different set of intervals features is computed at node level (on each of the trees from the ensemble). STSF, however, extracts a set of candidate discriminatory interval features for the training of each tree classifier instead of each tree node. Similar to TSF, STSF uses the interval features that split the tree nodes (i.e., discriminatory interval features) to integrate explainability into the classification results. STSF proposes the regions of interests (ROIs) to highlight the location of discriminatory intervals, which are the intersected regions of such intervals.

To achieve high classification accuracy without relying on complex features, r-STSF uses a novel perturbation scheme to grow an ensemble of uncorrelated trees. Uncorrelated trees reduce the variance of the ensemble and increase the classification accuracy (Louppe et al. 2013). The perturbation scheme consists of (i) random partitions of intervals when searching for discriminatory features and (ii) an ensemble of randomized trees. To allow for each tree in the ensemble to use a different set of interval features for classification (i.e., ensemble of uncorrelated trees), r-STSF randomly partitions the sub-series when searching for discriminatory interval features. In comparison, our previous STSF method uses fixed partitions (following a binary search-based scheme) to extract interval features. Fixed partitions are not suitable to create uncorrelated trees, because they may allow for the repetition of some interval features across different trees in the ensemble. We show that random instead of fixed partitions makes r-STSF significantly more accurate. To further decrease the variance of ensembles, r-STSF adopts the extra-tree (ET) algorithm (Geurts et al. 2006), which uses randomized trees. In such randomized trees, the cut-point of each feature is randomly selected when looking for the feature that provides the best split. These trees are different from those used in random forest (RF), where for each feature only the best cut-point (i.e., split with the lowest entropy) is selected.

Although trees built by using RF are also considered randomized trees, they are only weakly randomized because the cut point selection still relies on the lowest entropy. Methods based on ET, however, are strongly randomized because the cut point selection is random. Thus, we will use the term randomized trees exclusively for trees built using the ET algorithm; all other type of trees will be considered non-randomized. We show that randomized trees instead of regular or non-randomized trees (as those based on RF) significantly increase the effectiveness of r-STSF.

Further, we introduce two new aggregation functions to form new features which are shown to improve the classification accuracy substantially: (i) the number of intersections of a sub-series with the mean axis of the entire sub-series, denoted as counts of mean-crossings in this paper, and (ii) the number of data points above the mean of a sub-series. These aggregation functions capture the shape of the time series and increase the classification accuracy more than generic statistics such as the mean or standard deviation.

r-STSF is very fast because it does not need to extract a set of candidate interval features for each tree classifier as STSF does. The training process of r-STSF is designed to require a small number (denoted by d) of sets of candidate discriminatory interval features. r-STSF extracts d sets of candidate interval features and merges all sets into a superset \(\mathscr {F}\). Then, each of the r trees in the ensemble is built by using a set of randomly selected interval features from \(\mathscr {F}\). Our experiments show that by setting \(d=0.1 \times r\), r-STSF achieves a similar classification accuracy (to computing a set of interval features for each tree) but being an order of magnitude faster.

An extensive experimental study on 112 time series datasets (Bagnall et al. 2019) shows that r-STSF is not significantly different in accuracy than most of the current SOTA classifiers, except for HC2, which was developed while this paper was under review. Whilst HC2 is more accurate than r-STSF, its long running time renders it impractical for classifying large time series datasets. Another approach, DrCIF which was proposed jointly with HC2, is slightly more accurate but not competitive in terms of runtime as it is two orders of magnitude slower. HC2 and DrCIF were published while r-STSF was under review. When reporting our results (e.g., ranking) comparing r-STSF against evaluated TSC methods we use the notation b(a), where b denotes r-STSF’s position before HC2 and DrCIF, whereas a includes them. r-STSF is ranked as the fourth (sixth) best classifier (according to the average ranks). Among all TSC methods that integrate explainability, only r-STSF achieves SOTA classification accuracy. Since r-STSF is at least two orders of magnitude faster than most of the SOTA TSC methods, it is ideal for classifying large data sets with long series. Its explainability supports applications requiring insights on the classifier decision.

In our previous work STSF (Cabello et al. 2020), we show that computing interval features in a supervised manner from different time series representations by using robust statistics is a highly efficient and accurate interval-based classification strategy. In this article, we design r-STSF with with the following new contributions:We provide the experimental results and source code at https://​github.​com/​stevcabello/​r-STSF.

Time series classification (TSC) methods can be categorised into distance-based, shapelet-based, dictionary-based, interval-based, kernel-based, hybrid, and deep learning-based methods. Distance-based methods, such as elastic ensemble (EE) (Lines and Bagnall 2015) and proximity forest (PF) (Lucas et al. 2019) focus on classify a time series according to the similarity of its ordered data points to those of time series with known class labels, where localized distortions of the data points are allowed. EE uses an ensemble of 11 elastic nearest neighbour classifiers, whereas PF builds an ensemble of proximity trees for classification. Proximity trees use elastic distance measures as the splitting criteria. Both EE and PF have a quadratic time complexity over the length of the time series, which makes them computationally inefficient for long series.

Shapelet-based methods (Rakthanmanon and Keogh 2011; Hills et al. 2014; Grabocka et al. 2014) use shapelets, i.e, sub-series that are representative of class membership, and time series are classified according to their similarity to the (discriminatory) shapelets. By conducting a post-transform clustering of the shapelets, these methods may provide some level of explainability. Shapelet Transform (ST) (Hills et al. 2014) achieves a competitive classification accuracy Bagnall et al. (2017) with a bi-quadratic time complexity over the length of the series (due to full enumeration of all possible shapelets), which makes it impractical for long series. To improve the efficiency and hence the applicability of shapelet-based classifications, methods such as random shapelet forest (RSF) (Karlsson et al. 2015) and its more recent and general version, the generalized random shapelet forest (gRSF) (Karlsson et al. 2016) construct an ensemble of randomized shapelet trees, where each tree is built using a random selection of time series instances and a random selection (rather than a full enumeration) of shapelets. RSF and gRSF integrate explainability by identifying relevant shapelet lengths and time-points for the classifier decision. Recently, Bagnall et al. (2020) found that a full enumeration of all possible shapelets is not only unnecessary, but often results in over-fitting. Bagnall et al. (2020) proposed the shapelet transform classifier (STC), which randomly selects shapelets (i.e., no longer bi-quadratic time complexity as ST) and uses rotation forest (Rodriguez et al. 2006) for classification.

Dictionary-based methods (Lin et al. 2012; Schäfer 2015) use the relative frequency of discriminatory sub-series for classification. These methods transform each sub-series into a symbolic representation such as the Symbolic Fourier Approximation (SFA) Schäfer and Högqvist (2012) or the Symbolic Aggregate Approximation (SAX) (Lin et al. 2003) and employ a bag-of-patterns (BOP) model (Lin et al. 2012) to transform the symbols into a histogram representation. The bag of SFA symbols (BOSS) (Schäfer 2015) is the best dictionary-based method according to Bagnall et al. (2017). Although more recent dictionary-based classifiers such as the Word ExtrAction for time SEries cLassification (WEASEL) Schäfer and Leser (2017), Spatial BOSS (S-BOSS) (Large et al. 2019), and Contractable BOSS (cBOSS) (Middlehurst et al. 2019) are more accurate than BOSS, their difference in classification accuracy is not significant (Middlehurst et al. 2020b), while WEASEL is even more memory-intensive than BOSS (Le Nguyen et al. 2019). This makes BOSS a more practical TSC method. BOSS computes the number of times that a discriminatory sub-series (represented as a symbol) appears in the time series. This provides more accurate classifications if the discriminatory sub-series appears in different classes, i.e., represents more than one class. In BOSS, the size of the alphabet grows exponentially to the word length, which makes this method memory intensive for long series. A recent TSC method, temporal dictionary ensemble (TDE) (Middlehurst et al. 2020b) combines features from four dictionary-based TSC methods BOSS, WEASEL, S-BOSS, and cBOSS. TDE is significantly more accurate than all other dictionary-based TSC methods. However, as mentioned in its original proposal, TDE is slow at testing and less scalable, which makes it impractical to classify large time series datasets. To the best of our knowledge, none of the previously discussed dictionary-based TSC methods has focused on providing explainable classifications. However, a recent dictionary-based method, mtSAX-SEQL+LR (Le Nguyen et al. 2019) enables classification explainability. It transforms the time series into a symbolic representation, but it uses a Sequential Learner (SEQL) (Ifrim and Wiuf 2011) for feature selection and a logistic regression (LR) classifier for classification. The LR classifier learns a linear classification model which is essentially a set of symbols and their coefficients. The symbols can be mapped back to their original location in the time series. Since the coefficients can be interpreted as the discriminatory power of the symbols, mtSAX-SEQL+LR uses such coefficients to enable explainability into their classification results. mtSAX-SEQL+LR has quasi-quadratic time complexity over the length of the series. It is more efficient than BOSS and WEASEL (quadratic time over the length of the series). However, it is not competitive to SOTA TSC methods in terms of accuracy. Instead of using SAX or SFA symbols, Baydogan and Runger (2015) propose SMTS. It employs a tree-based ensemble to compute a symbolic representation of the time series, identifying discriminatory sub-series by their relative frequency at the terminal nodes. Building upon this, Rand-TS (Görgülü and Baydogan 2021) includes a post-processing step with a supervised learner. This further refines the symbolic representation by filtering out irrelevant features. Classification is done using k-nearest neighbour with Manhattan distance. We compared the reported classification accuracy values of Rand-TS and SMTS against those of SOTA methods and found that neither is significantly more accurate than BOSS nor competitive with SOTA methods. This aligns with existing literature (Bailly et al. 2016).

Interval-based methods (Deng et al. 2013; Baydogan et al. 2013; Baydogan and Runger 2016) are well known to be highly efficient TSC methods (Bagnall et al. 2017). These methods, similar to the random patches (RP) approach (Louppe and Geurts 2012), rely on random subsets of features. However, unlike most TSC methods including the interval-based ones which use all training instances for model training, RP uses randomly sampled training instances. Interval-based methods explore sets of sub-series to extract discriminatory intervals. The idea is that time series from the same class tend to have intervals with similar characteristics. Time series forest (TSF) (Deng et al. 2013) relies on random searches to reduce the high-dimensional interval space (i.e., quadratic to the length of the time series) and to explore intervals of different lengths. TSF uses three statistical measurements (mean, standard deviation, and slope) and tree-based ensembles to capture discriminatory intervals. TSF is fast and memory efficient (Bagnall et al. 2017), and the discriminatory intervals can be identified by using the temporal importance curve (Deng et al. 2013), which enables explainable classifications. The random interval spectral ensemble (RISE) (Lines et al. 2018) was introduced to capture frequency-domain features. RISE works similar to TSF, but it extracts spectral features over each random interval instead of statistical measurements as in TSF. Both TSF and RISE are highly efficient but less accurate than other feature-based TSC methods. More recent interval-based TSC methods such as our previous supervised time series forest (STSF) (Cabello et al. 2020) and the canonical interval forest (CIF) (Middlehurst et al. 2020a) have improved considerably the classification accuracy, and are competitive to highly accurate shapelet and dictionary-based classifiers. STSF selects its intervals in a supervised manner rather than completely at random as TSF does, and it uses a set of seven summary statistics to compute the interval features. Besides, STSF computes interval features not only from the original (i.e. raw) time series but also from additional time series representations such as the periodogram and first-order difference representations. CIF is similar to TSF, while it randomly selects eight out of the twenty-two descriptive statistics proposed by Lubba et al. (2019) when building each tree. Both STSF and CIF can provide explainable classifications but are less accurate than SOTA TSC methods. A recent interval-based method proposed in a parallel work, diverse representation of canonical interval forest (DrCIF) (Middlehurst et al. 2021) draws on ideas presented in STSF and CIF, and achieves SOTA accuracy. However, as shown in Sect. 5.3, it requires of a long running time and does not scale to large time series datasets.

Kernel-based methods such as the RandOm Convolutional KErnel Transform (ROCKET) (Dempster et al. 2020) transforms the series into a feature-based representation by using a large number of random convolutional kernels, and it uses such features to train a linear ridge regression classifier. ROCKET achieves SOTA classification accuracy, but it has not reported classification explainability. ROCKET’s time complexity is quadratic to the number of time series or to the number of extracted features (depending on which is smaller). Large datasets with very long series may affect ROCKET’s scalability. An ensemble of smaller ROCKET classifiers, Arsenal, is proposed by Middlehurst et al. (2021) to integrate ROCKET into HC2’s ensemble. Arsenal by itself is statistically as accurate as ROCKET. However, HC2 with Arsenal is significantly better than HC2 with ROCKET.

Hybrid methods are heterogeneous ensembles. They classify time series datasets by combining information from different types of TSC methods. These methods are highly accurate but usually time and memory expensive. Two representatives are the hierarchical vote collective of transformation-based ensembles (HIVE-COTE) (Lines et al. 2018) and time series combination of heterogeneous and integrated embedding forest (TS-CHIEF) (Shifaz et al. 2020). HIVE-COTE uses EE, ST, BOSS, TSF, and RISE for classification and employs a modular hierarchical structure to allow a single probabilistic prediction from each classifier. HIVE-COTE achieves SOTA classification accuracy but is impractical for long series (bi-quadratic time complexity over the length of the time series). TS-CHIEF builds on PF and incorporates BOSS and RISE features as splitting criteria. TS-CHIEF is statistically similar to HIVE-COTE in classification accuracy, but more scalable (similar to PF). TS-CHIEF time complexity is quadratic to the series length, which makes it costly for long series.

To make HIVE-COTE faster and more scalable, Bagnall et al. (2020) proposed HIVE-COTE v1.0 (HC1). HC1 makes modifications such as dropping the elastic ensemble (EE), no longer fully enumerating the shapelet space (i.e., STC), and setting running time limits. In terms of accuracy, HC1 is statistically similar to HIVE-COTE, but significantly faster. The recent HIVE-COTE v2.0 (HC2) (Middlehurst et al. 2021) method, which is proposed in a parallel work, replaces three of the four classifiers from HC1. HC2 still uses STC, but it replaces BOSS with TDE and TSF with DrCIF. HC2 not longer uses RISE, and it adds Arsenal to the ensemble. To the best of our knowledge, HC2 is the new SOTA TSC method in terms of accuracy. However, as shown in Sect. 5.3, HC2 is among the slowest and most memory expensive classifiers. It does not scale to large datasets. No hybrid methods have reported classification explainability.

Deep learning-based methods such as the fully convolutional networks (FCN) and residual networks (ResNet) obtain competitive accuracy (Wang et al. 2017) and integrate explanations into the model decisions using the class activation map (CAM) (Zhou et al. 2016) to highlight relevant sub-series. However, they are also computationally expensive for long series and require a GPU. InceptionTime (Fawaz et al. 2020) is the best deep learning-based classifier, and it is competitive to SOTA TSC methods. It improves ResNet’s accuracy by using an ensemble of five different Inception networks which are randomly initialized. InceptionTime is faster than HIVE-COTE as it uses GPU parallelization; however, it is very slow when running without GPU (Bagnall et al. 2020) and does not report classification explainability.

Table 1 summarizes the representative TSC methods. Most current TSC methods have time complexities that are quadratic or bi-quadratic to the length of the time series, which makes them less practical on long time series. Besides, to the best of our knowledge, with the exception of TSF, RSF, gRSF, ST, FCN, ResNet, mtSAX-SEQL+LR, STSF and CIF no existing TSC methods provide insights about the classifier decision.

We take an interval-based approach to classify time series and identify discriminatory features. The basic idea is to extract sub-series for which aggregates (e.g., mean and standard deviation) are computed and used as features. To allow for explainable classifications, we focus on phase-dependent intervals, i.e., discriminatory features located at the same time regions over all time series in a given dataset. Although r-STSF’s explainability is oriented towards phase-dependent intervals, this does not imply that r-STSF cannot provide explanations in case of phase-independent discriminatory intervals (or in the absence of phase-dependent discriminatory intervals). As discussed in Sect. 4.1, r-STSF uses different time series representations as a proxy to indirectly detect phase-independent discriminatory intervals, i.e., phase-independent intervals in the time domain may become phase-dependent when being moved into the frequency-domain.

Interval feature: Given a set of time series X = \(\{ \varvec{x^{1}}, \varvec{x^{2}},\varvec{x^{3}},\ldots ,\varvec{x^{n}} \}\), where \(\varvec{x^{i}}\) = \(\{x_{1}^i,x_{2}^i,\ldots ,x_{m}^i\}\), an aggregation function \(a(\cdot )\), and an interval (s,e), an interval feature \(\varvec{f} = a(X,s,e)\) is a vector of length n, defined as follows: where \(a(\varvec{x}^i,s,e) = a(\{x_{s}^i,x_{s+1}^i,\ldots ,x_{e-1}^i,x_{e}^i\})_{ 1 \leqslant s \leqslant e \leqslant m}\). With s=2, e=4, a=mean, an interval feature \(\varvec{f}=\text{ mean }(X,2,4)\) is represented with the dashed rectangle as:

Problem statement: Consider a set of n univariate time series X = \(\{ \varvec{x^{1}}, \varvec{x^{2}},\ldots ,\varvec{x^{n}} \}\), where each time series \(\varvec{x^{i}}\) = \(\{x_{1}^i,x_{2}^i,\ldots ,x_{m}^i\}\) has m ordered real-valued observations, sampled at equally-spaced time intervals. Each time series \(\varvec{x^{i}}\) is also associated with a class label \(y^{i}\). We aim to find the set of interval features that yield the highest time series class prediction accuracy. Finding such a set of interval features is NP-hard. For a time series of length m, there are \(\mathscr {O}(m^{2})\) different intervals, and hence \(\mathscr {O}(2^{m^2})\) subsets of intervals. For a large m, it is prohibitively expensive to explore all subsets. We present an efficient heuristic to avoid the exhaustive search while retaining a high classification accuracy

Table 2 summarizes the symbols frequently used in this paper.

Our proposed TSC algorithm, r-STSF, takes a stochastic optimization approach to select a set of interval features with a high discriminating power (i.e., candidate discriminatory interval features) from the high dimensional interval feature space (i.e., all \(\mathscr {O}(m^2)\) possible interval features). For a time series of length m, we reduce the interval feature space size to \(\mathscr {O}(\log \,m)\). We search for the best interval features subset \(\mathscr {F}^*\) (i.e., discriminatory interval features) through an ensemble of binary trees, which has a time complexity of \(\mathscr {O}(r \cdot n \cdot \log \,n \cdot \log \,m)\), where r is the total number of trees in the ensemble and n is the number of time series instances. The trees in the ensemble are built in a randomized manner following the extra-trees algorithm (see Sect. 4.3) to reduce the variance of the ensemble and improve the classification accuracy. Figure 3 shows an overview of r-STSF when training the ensemble of randomized binary trees.

For a given time series training set X, r-STSF does not only uses its original (raw) representation, i.e., \(X_O\), but derives its periodogram, i.e., \(X_P\), derivative, i.e., \(X_D\), and autoregressive representation, i.e., \(X_G\). For each representation, r-STSF selects a group of candidate discriminatory interval features \(F_{O},\ F_{P},\ F_{D}\), and \(F_{G}\), respectively. Next, a union set \(\mathscr {F}\) is formed by merging all candidate discriminatory interval features. It is worth noting that the process of extracting candidate interval features is repeated for d times, where d is a system constant parameter. In other words, d sets of candidate discriminatory interval features are extracted. In our empirical study, we find that a small value, e.g., \(d = 0.1 \times r\), is sufficient to yield a high TSC accuracy. This means that, for an ensemble of 500 trees, we just extract 50 sets of candidate discriminatory intervals. Lastly, each randomized tree is built by using a number of randomly selected interval features from \(\mathscr {F}\). We set this number to the square root of the size of \(\mathscr {F}\) following other tree-based ensemble approaches such as random forest (RF) (Breiman 2001). A tree classifier, due to its intrinsic feature selection capability, enables the selection of a set of discriminatory intervals \(\mathscr {F}^*\) with which TSC is performed. Features from \(\mathscr {F}^*\) enable the explainability of the TSC task, which will be discussed in Sect. 7.

r-STSF and STSF share a similar logic, i.e., extract features in a supervised manner and use them to build an ensemble of trees for classification. However, every component of r-STSF is designed with the goal of improving classification accuracy and decreasing training/testing time, while retaining explainability. A summary of the main differences between r-STSF and STSF is discussed in Sect. 4.4.

We evaluate the classification effectiveness (i.e., accuracy) and computational efficiency (i.e., memory consumption and running time) of r-STSF. Our results show that r-STSF achieves classification accuracies competitive to those of SOTA methods, while it is orders of magnitude faster and requires less memory than most of them. By default, r-STSF is trained with 500 trees (similar to all interval-based methods) and uses four time series representations and nine aggregation functions as summarized in Table 3. We compare r-STSF against interval-based, shapelet-based, dictionary-based, kernel-based, deep learning-based and hybrid TSC methods as detailed in Sect. 5.1. All methods use their default settings and are tested on the 112 benchmark datasets from the UCR Time Series Classification Repository (Bagnall et al. 2019), i.e., \(UCR_{112}\). We use the default train and test split of each dataset from the repository.

Classification effectiveness: To evaluate the effectiveness of r-STSF, we use the well-known average ranking metric. For a visual comparison according to the average rank, we use the critical difference diagram (Demšar 2006) which is widely used by the TSC community to assess the statistical differences of the ranks when comparing multiple classifiers over multiple datasets. Horizontal, bold lines show groups of statistically similar methods. A smaller rank indicates a better classifier. Ranks are based on classification accuracies. Accuracy results from each competitor TSC method are obtained from its original paper. In cases where results from a dataset are missing, we use the results reported in the UCR repository or in recent works (Middlehurst et al. 2021). We report the overall effectiveness comparison results against the competitors in Sect. 5.2. We also report the average ranks of r-STSF and competitors when evaluated on different application domains in Sect. 5.2.1.

Computational efficiency: To assess efficiency, we measure the algorithms’ maximum memory consumption, and total training and testing times when running on \(UCR_{112}\). r-STSF is implemented in Python. For a fair efficiency comparison with the competitor methods, we used their implementations in sktime Löning et al. (2019) (a library for time series analysis in Python). For the deep learning-based methods, ResNet and InceptionTime, we used their original Python implementations (we did not use sktime-dl because of errors found when running those methods). For gRSF (originally implemented in Java) we used a Python implementation from Wildboar (Samsten 2020), a Python module for temporal machine learning and fast distance computations. We report the overall efficiency comparison results against the competitors in Sect. 5.3. In addition, we evaluate the computational efficiency of TSC methods running on a set of eight large time series datasets from Bagnall et al. (2019) and report our results in Sect. 5.3.1.

All experiments are run on the High Performance Computing (HPC) system Spartan at The University of Melbourne. Each job runs on a single core and consists of a single dataset and TSC method. A job has a maximum run time of seven days and the maximum memory allowed is 500 GB.

To provide a comprehensive analysis of r-STSF, we present experimental results to support (i) our decision for a supervised selection of intervals features instead of an unsupervised one (i.e., random selection) and (ii) our decision to use Fisher score as the feature ranking metric in the supervised search. Further, we explore the impact of different parameters of r-STSF on its classification accuracy. The parameters to consider are: (i) number of candidate discriminatory interval feature sets, (ii) time series representations, and (iii) aggregation functions. The number of trees in the ensemble is not considered in this analysis. It is set to 500 following the other tree-based TSC methods (Deng et al. 2013; Shifaz et al. 2020). Moreover, we present experimental results to support our claims regarding the improvements to the average classification accuracy of r-STSF when (i) using random partitions (instead of middle-point partitions) of intervals when searching for candidate discriminatory interval features, and (ii) building ensembles of randomized binary trees (i.e., extra-trees) instead of non-randomized binary trees (i.e., random forest). All the results presented in this section are based on the average classification accuracy over three runs of r-STSF when classifying on \(UCR_{112}\). r-STSF uses by default (unless said otherwise) the four time series representations and the nine aggregation functions mentioned in Sect. 4.

To provide further insights to the classification decisions of r-STSF, we use the discriminatory intervals computed by it. Each discriminatory interval has information on its interval boundary (i.e., starting and ending indices), the aggregation function (e.g., mean), and the time series representation (e.g., periodogram) that was used to generate the corresponding feature. To highlight the regions of the time series which are discriminatory, i.e., maximizing class separability, we count the number of times that each data point of a testing series is contained in the discriminatory intervals. We normalize such counts and use a heatmap to visualize the most interesting regions.

As discussed in Sect. 4, r-STSF uses different time series representations for classification. These representations allow for explanations directly, i.e., it is not necessary to rely only on relevant features from the original series. In this section, we present cases where the original time series does not support the identification of discriminatory features and show how our additional representations provide more discriminatory features while enabling explainability. More importantly, since r-STSF uses simple statistics to compute its features, our explanations are not only limited to highlighting discriminatory regions, i.e., we can also provide explanations for the classifier’s decision. For example, if a discriminatory interval was extracted with the slope, it can be explained that sub-series from one class may exhibit a different trend from that of sub-series of another class.

We proposed r-STSF, an extremely fast and highly efficient interval-based algorithm for time series classification. r-STSF integrates explainability into its classification and achieves SOTA classification accuracy. To achieve competitive classification accuracies, r-STSF builds an ensemble of randomized trees for classification. It uses four time series representations, nine aggregation functions, and a supervised search strategy combined with a feature ranking metric when searching for highly discriminatory sets of interval features. The discriminatory interval features enable explainable classification results. Extensive experiments on real-world datasets validate the accuracy and efficiency of our proposed method – r-STSF is as accurate as SOTA TSC methods but orders of magnitude faster, enabling it to classify large datasets with long series.

While randomized trees have shown to improve the classification accuracy (when compared to non-randomized trees) for a large number of datasets, they are less likely to identify relevant features in datasets with a small number of relevant features as they might miss those. As future work, we plan to make r-STSF adaptive. When a dataset is expected to have a high percentage of relevant features – estimated with techniques such as permutation importance (Louppe et al. 2013) – r-STSF trains an ensemble of randomized trees for classification. Otherwise, r-STSF uses non-randomized trees. Moreover, the intrinsic multivariate nature of time series signals (e.g., 3-axis accelerometer) leads us to extend r-STSF towards multivariate or multidimensional scenarios. Other methods such as CIF extend to multivariate scenarios by searching for discriminatory interval features in different dimensions of a series. However, extracting interval features per dimension (i) could potentially miss discriminatory features only found when data from every dimension is combined, e.g., an interval from series of the x, y, and z-axis of the accelerometer may not be discriminatory when assessed by separate, but it is discriminatory when data from each axis is combined, and (ii) may hinder the explainability when classifying datasets with a high number of dimensions due to such explainability has to be done per dimension (by highlighting discriminatory regions in the series from each dimension). We plan to transform the individual (per dimension) time series into a single (unified) representation from where to extract discriminatory interval features.

We consider r-STSF highly relevant to enable further studies on interval-based classifiers. Results from an extensive experimental study on TSC methods (Bagnall et al. 2017) reported that interval-based TSC methods were the least competitive family of TSC methods. However, more recent studies including ours have positioned the interval-based methods among the best ranking TSC methods. As shown in Fig. 6, r-STSF ranks just behind time and memory expensive hybrid methods such as HC2 and TS-CHIEF, and non-explainable by design kernel-based approaches such as ROCKET. Our proposed r-STSF achieves similar classification accuracy to that of DrCIF while being two orders of magnitude faster.