Source-linked AI summary
A Time Series Forest for Classification and Feature Extraction
Houtao Deng, George Runger, Eugene Tuv, Martyanov Vladimir
TL;DR
Time series classification requires accurate methods that also reveal useful temporal characteristics. The paper proposes TSF, which combines Entrance-gain splitting with random feature sampling and a temporal importance curve. Across 45 benchmark data sets, Entrance gain improves TSF accuracy, while TSF remains efficient and outperforms widely used alternatives using simple features.
Problem
NNDTW can be accurate and robust to time-axis distortion, but provides limited insight into temporal characteristics; interval-feature methods face large feature spaces and computational concerns.
Method
TSF is a tree ensemble using Entrance gain, random feature sampling, and a temporal importance curve derived from the forest.
Results
Across 45 benchmark data sets, Entrance gain improves TSF accuracy, and TSF using simple statistical features outperforms widely used alternatives.
Takeaways & Limitations
TSF is an accurate, efficient classifier that provides insights into temporal characteristics useful for distinguishing time-series classes.
Takeaways & Limitations
TSF assumes time series have the same length; varying-length series require alignment techniques such as dynamic time warping.
Abstract
from arXiv · showhide
We propose a tree ensemble method, referred to as time series forest (TSF), for time series classification. TSF employs a combination of the entropy gain and a distance measure, referred to as the Entrance (entropy and distance) gain, for evaluating the splits. Experimental studies show that the Entrance gain criterion improves the accuracy of TSF. TSF randomly samples features at each tree node and has a computational complexity linear in the length of a time series and can be built using parallel computing techniques such as multi-core computing used here. The temporal importance curve is also proposed to capture the important temporal characteristics useful for classification. Experimental studies show that TSF using simple features such as mean, deviation and slope outperforms strong competitors such as one-nearest-neighbor classifiers with dynamic time warping, is computationally efficient, and can provide insights into the temporal characteristics.
1. Introduction
Time series classification needs methods that tolerate time-axis distortion while revealing temporal characteristics useful for distinguishing classes. TSF addresses this with an Entrance-gain tree ensemble, random feature sampling, and a temporal importance curve.
- NNDTW is robust to time-axis distortion and difficult to beat, but provides limited insight into useful temporal characteristics.
- Interval features can capture temporal characteristics and handle time-axis distortion, but their large feature space creates computational concerns and ties among entropy-gain splits.
- TSF uses Entrance gain, combining entropy gain with a distance measure, to identify high-quality splits.
- TSF randomly samples features at each node, giving computational complexity linear in time-series length and supporting parallel construction.
- The temporal importance curve captures temporal characteristics informative for time series classification.
2. Definition and Related Work
Time series classification methods include instance-based approaches that compare examples and feature-based approaches that build models on temporal features. Prior work spans robust nearest-neighbor methods, interpretable shapelets, and large feature sets, motivating effective, efficient classifiers with simple features.
- Time series classification methods are divided into instance-based and feature-based approaches.
- NNDTW is robust to time-axis distortion and generally outperforms NNEuclidean, but instance-based classifiers provide limited temporal insight.
- Feature-based classifiers can be more interpretable, but global statistical features may miss informative local properties.
- Shapelet methods produce highly interpretable results and were comparable to NNDTW on nine investigated data sets.
- Massive feature sets can be accurate but hard to interpret and computationally expensive.
- The work aims to produce an effective, efficient classifier using simple features that can contribute to domain knowledge.
3. Interval Features
Interval features summarize values over selected time-series intervals using simple statistics such as mean, standard deviation, and slope. Their quadratic feature space motivates random sampling to reduce the features considered at each tree node.
- Interval features are calculated over time-series intervals, with mean and standard deviation offered as simple, interpretable examples.
- The paper considers three interval-feature types: mean, standard deviation, and slope.
- The slope feature is the least-squares regression-line slope over the selected interval.
- Considering all intervals yields an O(M^2) feature space, while random sampling reduces the feature space to O(M) at each tree node.
4. Time Series Forest Classifier
TSF builds time series trees using interval features, a tie-breaking Entrance gain criterion, and random interval sampling. It combines ensemble prediction with temporal importance curves that expose informative intervals, while maintaining complexity linear in time-series length.
- 4.1. Splitting criterion: The candidate threshold range is divided into κ equal-width intervals, avoiding sorting and requiring only κ threshold tests.The number of candidate thresholds is fixed, for example κ = 20.
- 4.1. Splitting criterion: Entrance gain combines entropy gain with Margin, using a small α primarily to break ties between splits with equal entropy gain.Margin measures the distance between a candidate threshold and its nearest feature value.
- 4.1. Splitting criterion: Entrance gain selects S3 when three candidate splits have identical entropy gain but S3 has the largest margin.The example contains six instances from three classes and candidate splits S1, S2, and S3.
- 4.2. Time Series Tree and Time Series Forest: Randomly sampling O(M) starting positions and interval sizes reduces the feature space to O(M) at each tree node.This strategy adapts random-forest feature sampling to interval features.
- 4.2. Time Series Tree and Time Series Forest: TSF is a collection of time series trees whose votes determine the majority-class prediction for a testing instance.Each tree is constructed top-down and recursively using Entrance gain for splitting.
- 4.3. Computational Complexity: O(nTreeMN log N) bounds TSF complexity, making it linear in time-series length.The bound assumes maximum tree depth O(log N).
- 4.4. Temporal Importance Curve: The temporal importance curve sums split entropy gains over intervals containing each time index, providing insights into informative temporal characteristics.With Entrance gain, curves peak in the known informative intervals, whereas entropy-gain curves can have long tails.
5. Experiments
Experiments evaluate TSF's accuracy, robustness, interpretability, and computational efficiency against interval-feature and nearest-neighbor classifiers across benchmark time-series data sets. Results support Entrance gain, temporal importance curves, and scaling behavior as useful components of TSF.
- Experimental Setup: Experiments compare TSF with TSF-entropy, interRF, NNEuclidean, DTWBest, and DTWNoWin on benchmark time-series data sets.The benchmark summary covers training and testing instances, class counts, and time-series lengths.
- Accuracy Comparison: The Friedman test found a significant difference among the six classifiers at the 0.001 level, enabling Bonferroni-Dunn post hoc comparisons.The comparison uses average classifier ranks across 45 data sets.
- Accuracy Comparison: TSF differed significantly from TSF-entropy, interRF, NNEuclidean, DTWNoWin, and DTWBest at the 0.1 level in Wilcoxon signed-ranks tests.The reported comparison treats TSF as the reference classifier against all listed competitors.
- Robustness: Error rates generally decrease as the number of trees increases, with relatively small changes for most data sets after 100 trees.Figure 5 plots individual data-set error rates and the average error rate against the number of trees.
- Interpretability: Temporal importance curves identify class-discriminative characteristics, including GunPoint mean differences in interval [60,100] and Wafer changes near the 100th point.For GunPoint, standard deviation and slope curves capture differences on the time-series sides; for Wafer, the standard-deviation curve captures sudden changes in class 1.
- Computational Complexity: Computational time tends to be linear in both time-series length and number of training instances, while dynamic feature calculation avoids storing O(M^2) interval features but can repeat calculations.The implementation was built in parallel, and the authors note that caching previously calculated interval features could improve it.
6. Conclusions
TSF addresses accuracy, interpretability, and scalability challenges through Entrance gain, random feature sampling, and the temporal importance curve. It is accurate and efficient, but assumes equal-length time series.
- Entrance gain combines entropy gain with a distance measure to identify high-quality splits and improve TSF accuracy.
- TSF randomly samples O(M) features from O(M^2) features, making computational complexity linear in time-series length.
- TSF trees are grown independently, enabling modern parallel computing techniques to speed up construction.
- The temporal importance curve captures informative interval features and identifies temporal characteristics useful for classification.
- Using simple summary statistical features, TSF outperforms widely used alternatives, while more complex features may improve accuracy at the cost of interpretability.
- TSF assumes time series have the same length; dynamic time warping can align unequal-length series, while direct handling remains future work.