PaperlayerView exact revision on arXiv

Source-linked AI summary

TS-CHIEF: A Scalable and Accurate Forest Algorithm for Time Series Classification

Ahmed Shifaz, Charlotte Pelletier, Francois Petitjean, Geoffrey I. Webb

arXiv:1906.10329v2cs.LGstat.ML

TL;DR

High-accuracy time-series classifiers such as HIVE-COTE can be computationally impractical as data volumes grow. TS-CHIEF addresses this by combining heterogeneous time-series embeddings in a tree-based ensemble, achieving state-of-the-art accuracy with substantially better scalability. On a land-cover mapping application, it trained on 130,000 time series in 2 days, while HIVE-COTE required 8 days for only 1,500.

  • Problem

    HIVE-COTE provides state-of-the-art TSC accuracy, but its computational complexity makes it infeasible for many applications and larger datasets.

  • Method

    TS-CHIEF is a stochastic tree-based ensemble that selects among heterogeneous TSC methods and representations at each node.

  • Results

    On 85 UCR datasets, TS-CHIEF achieves state-of-the-art accuracy that rivals HIVE-COTE while scaling substantially better.

  • Takeaways & Limitations

    TS-CHIEF learns from 130,000 time series in 2 days, whereas HIVE-COTE takes 8 days for 1,500 and TS-CHIEF takes 13 minutes for that quantity.

  • Takeaways & Limitations

    The current study focuses on univariate fixed-length time series; extending TS-CHIEF to multivariate and variable-length series remains future work.

Abstract

from arXiv · show

Time Series Classification (TSC) has seen enormous progress over the last two decades. HIVE-COTE (Hierarchical Vote Collective of Transformation-based Ensembles) is the current state of the art in terms of classification accuracy. HIVE-COTE recognizes that time series data are a specific data type for which the traditional attribute-value representation, used predominantly in machine learning, fails to provide a relevant representation. HIVE-COTE combines multiple types of classifiers: each extracting information about a specific aspect of a time series, be it in the time domain, frequency domain or summarization of intervals within the series. However, HIVE-COTE (and its predecessor, FLAT-COTE) is often infeasible to run on even modest amounts of data. For instance, training HIVE-COTE on a dataset with only 1,500 time series can require 8 days of CPU time. It has polynomial runtime with respect to the training set size, so this problem compounds as data quantity increases. We propose a novel TSC algorithm, TS-CHIEF (Time Series Combination of Heterogeneous and Integrated Embedding Forest), which rivals HIVE-COTE in accuracy but requires only a fraction of the runtime. TS-CHIEF constructs an ensemble classifier that integrates the most effective embeddings of time series that research has developed in the last decade. It uses tree-structured classifiers to do so efficiently. We assess TS-CHIEF on 85 datasets of the University of California Riverside (UCR) archive, where it achieves state-of-the-art accuracy with scalability and efficiency. We demonstrate that TS-CHIEF can be trained on 130k time series in 2 days, a data quantity that is beyond the reach of any TSC algorithm with comparable accuracy.

1 Introduction

TSC addresses growing classification needs across diverse applications, but high-accuracy methods can be computationally impractical. TS-CHIEF combines heterogeneous time-series methods in a tree-based ensemble to retain accuracy while improving scalability.

  • TSC supports applications including satellite-image, human-activity, medical, and power-consumption classification.
  • TS-CHIEF is a stochastic tree-based ensemble that selects, at each node, a well-performing method from a random selection of TSC methods.Its components use different time-series representations and combine specialized classification techniques.
  • TS-CHIEF achieves accuracy rankings on the UCR archive that are almost indistinguishable from HIVE-COTE while being orders of magnitude faster.
  • 900x faster: TS-CHIEF trains on 1,500 time series in 13 minutes versus 8 days for HIVE-COTE.
  • 46,000x faster at 132k instances: TS-CHIEF requires 2 days, compared with an estimated 234 years for HIVE-COTE.
  • The efficiency strategy combines stochastic construction and parameter selection with tree-based training and improved transformation components.The approach excludes a computationally expensive HIVE-COTE component.

2 Related Work

Related TSC methods represent series through elastic similarities, intervals, shapelets, or combinations of transformations. These approaches provide specialized information, while ensemble methods improve accuracy but can incur substantial computational costs.

  • The paper focuses on univariate, fixed-length time series, although the approach could be extended to multivariate and variable-length data.
  • Similarity-based techniques: Elastic similarity methods address local distortions, misalignments, and warpings within time series.
  • Similarity-based techniques: Ensembles of 1-NN classifiers using diverse similarity measures improve accuracy over any single measure, but EE has O(n^2 · ℓ2) training complexity and O(n · ℓ2) classification time.
  • Similarity-based techniques: Proximity Forest improves scalability and accuracy over EE by using classification trees whose splits compare series with class reference series under randomly selected similarity measures.
  • Interval-based techniques: Interval-based algorithms transform randomly selected intervals into feature vectors and commonly train forests of random trees on those features.
  • Interval-based techniques: RISE extracts time- and frequency-domain features from intervals using ACF, PACF, AR, and PS transformations.
  • Shapelet-based techniques: Shapelet methods seek discriminative subsequences independent of their locations, with original methods recursively selecting candidates and thresholds for tree splits.
  • Shapelet-based techniques: Fast Shapelets accelerate discovery through approximation but are less accurate than Learned Shapelets, while GRSF uses random shapelets within tree nodes.

3 TS-CHIEF

TS-CHIEF is a tree-based ensemble that integrates time-series-specific similarity, dictionary, and interval splitters while preserving ensemble diversity. Its stochastic, tree-structured design supports quasi-linear average complexity and high accuracy with substantially lower training time.

  • Overview: TS-CHIEF uses time-series-specific splitting criteria instead of treating each time step as an independent attribute.This design is intended to exploit the information contained in series order.
  • Heterogeneous splitters: Each tree node can select among similarity-based, dictionary-based, and interval-based splitters derived from Proximity Forest, BOSS, and RISE.The three splitter types may be used at any node of the tree.
  • Tree construction: TS-CHIEF builds a forest of k trees that recursively partitions data using time-series-specific splitting functions.The candidate splitters are generated for each node and the best splitter is stored in that node.
  • Similarity-based splitting: Similarity-based splitters randomly parameterize one of 11 measures and use randomly selected reference series, including one exemplar per class.With only similarity-based splitting enabled, TS-CHIEF is exactly Proximity Forest.
  • Dictionary- and interval-based splitting: Dictionary-based splitting uses BOSS transformations and exemplar histograms, while interval-based splitting samples random intervals and transformed attributes.These mechanisms extend the integrated forest beyond similarity-based comparisons.

4 Experiments

Across 85 UCR datasets, TS-CHIEF rivals HIVE-COTE in accuracy while substantially reducing training time. Its efficiency scales favorably with dataset size and series length, with ensemble size and splitter combinations affecting accuracy and variance.

  • Accuracy on the UCR Archive: 40/7/38 and 47/5/33: TS-CHIEF records these win/draw/loss counts against HIVE-COTE and FLAT-COTE, respectively.The pairwise accuracies differ substantially on some datasets, despite the aggregate similarity to the COTE methods.
  • Increasing training set size: 46,000x: at about 132k instances, TS-CHIEF reaches 67% accuracy after 2 days, versus an estimated 234 years for HIVE-COTE.For one million SITS series, the estimated times are 44 days for TS-CHIEF and 13,550 years for HIVE-COTE, a 90,000-times speedup.
  • Increasing length: 24x: for 100 series of length 2,048, TS-CHIEF trains in about 4 hours versus more than 3 days for HIVE-COTE.The observed scaling matches O(ℓ^2) for TS-CHIEF and O(ℓ^4) for HIVE-COTE with respect to series length.
  • Ensemble Size and Variance: 500 trees provide a practical accuracy–runtime trade-off by significantly improving over 100 trees while substantially reducing accuracy variance between runs.The accuracy difference is small, but the variance reduction is substantial; the comparison has p-value <0.001 after Holm correction.

5 Conclusions

TS-CHIEF combines tree-based scalability with heterogeneous time-series representations to achieve high accuracy and substantially broader scalability than HIVE-COTE. The authors identify extensions for memory, splitter balancing, and multivariate or variable-length data as future improvements.

  • TS-CHIEF achieves state-of-the-art accuracy that rivals HIVE-COTE across 85 datasets, whose computational complexity limits its use in many applications.
  • 130,000 time series can be learned in 2 days with TS-CHIEF, whereas HIVE-COTE requires 8 days for 1,500 time series in land-cover mapping.
  • TS-CHIEF is presented as a general framework intended to support integrating novel transformations and similarity measures at scale.
  • Future improvements include reducing computation time and memory footprint, balancing candidate splitters adaptively, and extending to multivariate or variable-length series.

Appendix

The appendix provides comparative accuracy and complexity information for leading time-series classification methods. It identifies the datasets, classifiers, ranking summaries, and parameters used to describe method complexity.

  • Table 4 compares eight leading TSC classifiers across 85 UCR datasets using accuracy, wins, and average ranking.
  • The compared classifiers include DTW, BOSS, Proximity Forest, Shapelet Transform, ResNet, FLAT-COTE, HIVE-COTE, and TS-CHIEF.
  • Table 3 reports the complexities of methods discussed in Section 2, using average-case complexity for tree-based methods.
  • The complexity table defines parameters for training size, series length, classes, window size, tree count, candidate splits, iterations, shapelet scale, SFA word length, and subseries count.
Loading 1906.10329v2…