PaperlayerView exact revision on arXiv

Source-linked AI summary

Proximity Forest: An effective and scalable distance-based classifier for time series

Benjamin Lucas, Ahmed Shifaz, Charlotte Pelletier, Lachlan O'Neill, Nayyar Zaidi, Bart Goethals, Francois Petitjean, Geoffrey I. Webb

arXiv:1808.10594v2cs.LGstat.ML

TL;DR

Time-series classification methods often struggle to scale from benchmark-sized datasets to applications containing millions of series. This paper introduces Proximity Forest, an ensemble of proximity-based randomized trees that uses time-series similarity measures, and reports competitive accuracy with much faster training. On a 1M-series satellite dataset, it trains in 17 hours versus over 200 years for Elastic Ensemble, while remaining competitive on UCR datasets.

  • Problem

    Leading time-series classifiers provide strong accuracy but do not scale adequately to datasets containing millions of series.

  • Method

    Proximity Forest is an ensemble of trees that splits by proximity to exemplar series using randomly selected parameterized time-series similarity measures.

  • Results

    Proximity Forest has highly competitive UCR accuracy and trains on 1M satellite series in 17 hours versus over 200 years for Elastic Ensemble, a 103,000x speedup.

  • Takeaways & Limitations

    Proximity Forest offers accurate time-series classification at a scale where leading approaches such as Elastic Ensemble and COTE are impractical to train.

  • Takeaways & Limitations

    BOSS-VS sacrifices accuracy for scalability, ranking about 30 percentage points lower than state-of-the-art accuracy in the case study.

Abstract

from arXiv · show

Research into the classification of time series has made enormous progress in the last decade. The UCR time series archive has played a significant role in challenging and guiding the development of new learners for time series classification. The largest dataset in the UCR archive holds 10 thousand time series only; which may explain why the primary research focus has been in creating algorithms that have high accuracy on relatively small datasets. This paper introduces Proximity Forest, an algorithm that learns accurate models from datasets with millions of time series, and classifies a time series in milliseconds. The models are ensembles of highly randomized Proximity Trees. Whereas conventional decision trees branch on attribute values (and usually perform poorly on time series), Proximity Trees branch on the proximity of time series to one exemplar time series or another; allowing us to leverage the decades of work into developing relevant measures for time series. Proximity Forest gains both efficiency and accuracy by stochastic selection of both exemplars and similarity measures. Our work is motivated by recent time series applications that provide orders of magnitude more time series than the UCR benchmarks. Our experiments demonstrate that Proximity Forest is highly competitive on the UCR archive: it ranks among the most accurate classifiers while being significantly faster. We demonstrate on a 1M time series Earth observation dataset that Proximity Forest retains this accuracy on datasets that are many orders of magnitude greater than those in the UCR repository, while learning its models at least 100,000 times faster than current state of the art models Elastic Ensemble and COTE.

1 Introduction

Proximity Forest addresses the lack of scalable, accurate time-series classifiers by using proximity-based randomized trees. It scales to million-series datasets while remaining competitive in accuracy and substantially reducing training time.

  • Motivation: Million-series applications exceed the scale of UCR benchmarks, while leading classifiers such as COTE face quadratic runtime constraints.The UCR benchmark’s largest training set has 8,926 series, compared with 370,000-series phoneme and 1,000,000-series satellite datasets.
  • Method: Proximity Forest is a tree-based ensemble that uses time-series similarity measures and proximity to reference series rather than attribute-value thresholds.Its splits are supported by the time series themselves, allowing the method to exploit decades of work on similarity measures.
  • Scalability: Proximity Forest scales linearly with training-set size, whereas Elastic Ensemble scales quadratically.The comparison uses Elastic Ensemble because it is the component that limits COTE’s scalability.
  • Scalability: 17 hours versus over 200 years: Proximity Forest trains on 1M satellite time series 103,000x faster than Elastic Ensemble on one CPU.Shapelet Transform and COTE are slower than Elastic Ensemble, so their training times would be even larger.
  • Accuracy: Proximity Forest outperforms Elastic Ensemble in classification accuracy on the majority of UCR Archive datasets.The paper also reports competitive accuracy against the state of the art on UCR data.

2 Time series classification – related work

Related work spans nearest-neighbour, data-reduction, indexing, and feature-based approaches, but scalability remains difficult for accurate time-series classification. Time-series-specific measures are important because temporal alignment and distortion violate assumptions behind ordinary representations and indexing.

  • Time-series properties: Time-series applications require specialized similarity measures because series can be autocorrelated and nonlinearly distorted along the time axis.These properties make typical similarity measures severely flawed for time-series data.
  • Nearest-neighbour methods: Nearest-neighbour classification with parameterized time-series measures has historically been strong, but parameter tuning is usually quadratic in training-set size.Parameters are generally learned from the data through cross-validation rather than fixed defaults.
  • Nearest-neighbour methods: Nearest-neighbour classification is at least linear in training-set size, and measure costs are between linear and quadratic in series length.Parameter tuning and classification costs compound the scalability problem.
  • Scalability techniques: Data reduction simplifies training databases, while indexing is difficult because time-series measures generally do not obey the triangle inequality.Reduction may remove objects or replace groups of series with representative averages.
  • Elastic Ensemble: Elastic Ensemble combines 11 nearest-neighbour classifiers, each using a different time-series measure with tuned parameters.EE substantially influenced the design of Proximity Forest and serves as a central state-of-the-art comparison.

2.2 Approaches that learn features

Feature-learning approaches transform time series into discriminative representations such as shapelet distances or symbolic words. These methods can be accurate, but their training scalability varies substantially.

  • Shapelets: Shapelet methods identify discriminative subseries and classify series using the distance to each shapelet’s best matching position.Shapelets can be incorporated as splitting criteria in decision trees or used to construct transformed attributes.
  • Shapelets: Shapelet Transform selects the best k shapelets and converts each into a distance-based attribute for subsequent classification.The transformed dataset can be passed to a classifier or ensemble such as COTE.
  • Shapelets: O(n^2 · l^4): Shapelet Transform has limited potential to scale to large datasets because of its training complexity.Here n is the number of series and l is their length.
  • Bag of words: Bag-of-words methods discriminate classes using relative frequencies of discretized subseries rather than best-position similarity.They encode subseries as symbols to represent the original time series.
  • Bag of words: BOSS uses Symbolic Fourier Approximation to create noise-robust words, but its O(n^2) training complexity limits large-dataset use.BOSS-VS and WEASEL were subsequently proposed with improved scalability or speed-oriented goals.

2.3 Ensemble approaches

Ensemble and tree-based methods combine classifiers or build splits from time-series representations and exemplars. Their central trade-off is balancing accuracy with training and classification scalability.

  • Ensemble methods: Ensemble runtime is determined by its slowest constituent classifier, even when combining multiple algorithms can improve accuracy.EE and Shapelet Transform are examples of ensembles or approaches organized around one principal classifier type.
  • COTE: COTE combines 35 classifiers across time, frequency, change, and shapelet-transformation domains.Its time-domain component uses the 11 distance measures of Elastic Ensemble.
  • COTE: COTE achieves the highest average accuracy on UCR benchmarks, but its complexity is bounded by Shapelet Transform and Elastic Ensemble parameter searches.The cited bounds include O(n^2 · l^4) for Shapelet Transform and some O(n^2 · l^3) EE searches.
  • Decision trees: Time Series Forest summarizes intervals with means, standard deviations, and gradients before applying a Random Forest-like feature-selection strategy.Its training complexity is O(n log(n) · l · k) for k trees, lower than current state-of-the-art methods.
  • Decision trees: Generalized Random Shapelet Forest splits data by thresholded distance from a shapelet extracted from a randomly chosen series.This recursively applies exemplar-based splits until nodes are pure or contain fewer than three instances.
  • Decision trees: Exemplar-based time-series trees can split using a cut point relative to one exemplar or by assigning multiple exemplars to branches.These strategies replace ordinary attribute-value thresholds with similarity-based decisions.

3 Proximity Forest

Proximity Forest addresses the need for time-series classification that is accurate and scalable in both learning and classification. It combines exemplar-based tree splits, randomized similarity measures, and ensemble diversity to improve scalability and accuracy.

  • Motivation: Proximity Forest targets accurate learning and classification on datasets containing hundreds of thousands to millions of time series.Existing methods either fail to scale in learning or classification, or compromise accuracy for scalability.
  • Scalability: The expected average-case learning complexity is O(n log(n) · l2), with tree depth increasing as O(log n).The divide-and-conquer structure supports sublinear growth in depth relative to training-set size.
  • Model: The method combines exemplar-based similarity splits with randomly selected trees and similarity measures.Each branch uses an exemplar, and candidate measures are selected stochastically from a pool of 11 Elastic Ensemble measures.
  • Model: Proximity Trees branch queries toward the closest class-specific exemplar rather than on individual time-stamp attributes.This avoids relying on signals being aligned at the same time stamp.
  • Learning algorithm: Candidate splits are evaluated using weighted child-node Gini impurity, and tree construction recurses until nodes are pure.At each node, the algorithm evaluates r randomized candidates and selects the split maximizing the parent-to-child impurity reduction.
  • Model: Randomized measure and parameter selection skips quadratic cross-validation and increases variability between trees for ensemble learning.The design aims to produce lower-biased trees whose ensemble has stronger overall classification performance.

4 Experiments

The experiments evaluate Proximity Forest on a million-series satellite dataset and on the UCR benchmark repository. They emphasize scalability, accuracy, comparison with Elastic Ensemble, and reproducibility.

  • SITS experiments: The SITS dataset tests whether Proximity Forest can remain scalable and accurate on a very large Earth-observation time-series collection.The experiments contrast it with scalable but less accurate methods such as BOSS-VS.
  • UCR experiments: The UCR experiments assess whether Proximity Forest remains competitive with the current state of the art in classification accuracy.The study also examines the effect of varying the number of trees and the standard deviation of results.
  • Comparisons: Elastic Ensemble is the primary comparison because it is Proximity Forest’s closest relative and bounds COTE’s learning time.Neither method includes data transforms or shapelets.
  • Reproducibility: The authors provide code and full raw results to support reproducibility and further development.The materials are available through the project’s GitHub repository.

4.1 Case study: Satellite Image Time Series Dataset

On the approximately 1-million-series SITS dataset, Proximity Forest scales efficiently while maintaining higher accuracy than the compared classifiers at larger training sizes.

  • Dataset: Approximately 1 million time series comprise the SITS dataset, with length 46 and 24 land-use classes.The train-test split is approximately 90%-10%.
  • Training scalability: Proximity Forest trains in 79 seconds on about 2,000 series, compared with about 10 hours for EE.The fitted quadratic components are 6.3 for EE and −8.10 × 10−6 for Proximity Forest.
  • Training scalability: Proximity Forest scales quasi-linearly with training size, whereas EE exhibits quadratic training-time growth.The experiments compare training time as a function of increasing training-set size.
  • Training scalability: WEASEL could not scale beyond 8,000 training series with 64 GB of RAM, while Proximity Forest remained applicable at much larger sizes.WEASEL was designed for speed on small datasets rather than scalability.
  • Testing scalability: At 1M training series, Proximity Forest classifies a time series in 0.0679 ms, compared with 0.0077 ms for BOSS-VS.Testing time scales logarithmically with training-set size for Proximity Forest, while EE repeatedly scans the full database.
  • Accuracy: At 3,400 training series, Proximity Forest reaches 63.8% accuracy, exceeding BOSS-VS by 26.3 percentage points and WEASEL and EE by 4.6 and 4.7 points.Proximity Forest is more accurate than the other algorithms from 500 training instances upward.

4.2 Experiments on the UCR Archive

Across 85 UCR datasets, Proximity Forest is competitive with state-of-the-art accuracy and substantially faster to train than Elastic Ensemble, while its testing-time advantage depends on dataset size.

  • Comparison with EE: Proximity Forest is more accurate than EE on 60 UCR datasets, less accurate on 11, and tied on 14.For many datasets, the accuracy difference is substantial.
  • Comparison with EE: Proximity Forest has a several-orders-of-magnitude training-time advantage over EE across the UCR comparison.Its testing time is higher on 12 datasets, mostly those with fewer than 50 training instances.
  • Average-rank comparison: Proximity Forest ranks second by average rank at 2.88, behind COTE at 2.28 and ahead of EE and DTW.Its rank is not significantly different from COTE, ST, or BOSS, using a critical difference of 0.82.
  • Dataset-wise accuracy: Proximity Forest is the most accurate classifier on 22 of the 85 UCR datasets.The paper reports no obvious commonality among these datasets indicating when it is likely to excel.

4.3 Parameters of Proximity Forest

The experiments examine how forest size and the number of candidate splits affect Proximity Forest accuracy, variability, and computational cost.

  • Number of trees: Models with 100 trees achieve average rank 1.19, compared with 1.93, 2.98, and 3.89 for 50, 10, and 5 trees.The results are averaged over 50 runs on the UCR experiments.
  • Number of trees: Using 100 trees improves accuracy on most datasets versus 10 or 50 trees, but ratios near 1 indicate limited further improvement beyond 100.The comparison uses error-rate ratios for 100 trees against 10 and 50 trees.
  • Number of trees: Increasing the number of trees reduces the standard deviation of error rates, with results for 50 trees already close to the 100-tree reference.The comparison covers 85 UCR datasets.
  • Number of candidates: Selecting among 5 candidates produces higher accuracy than selecting among 1 or 2 candidates on 61 UCR datasets.At each node, candidate exemplars and parameterized distance measures are evaluated using the Gini index.
  • Number of candidates: Increasing the candidate count raises training time while slightly reducing testing time, creating an accuracy-versus-time trade-off.Better split selection produces slightly shallower trees, which require fewer splits to form pure leaves.

5 Conclusion

Proximity Forest is presented as a scalable, accurate time-series classifier whose quasi-linear scaling addresses datasets with millions of series. The conclusion reports competitive UCR accuracy and identifies randomized distance-measure selection as an area for improvement.

  • Conclusion: Proximity Forest is a novel ensemble of trees with a splitting criterion that leverages time-series distance measures.The method is designed for accurate classification while maintaining scalability.
  • Conclusion: Proximity Forest scales quasi-linearly with training-data quantity, whereas most state-of-the-art algorithms scale quadratically.
  • Conclusion: Proximity Forest has highly competitive accuracy relative to the current state of the art and is significantly more accurate than EE.
  • Future work: Improving randomized distance-measure parameter selection is proposed as a way to increase accuracy while maintaining quasi-linear complexity.The current strategy was designed primarily to emulate EE as directly as possible.
  • Future work: The paper proposes investigating whether Proximity Forest can provide new insight into time-series indexing.

A Detailed UCR results

Table 1 reports detailed UCR results comparing Proximity Forest with five state-of-the-art algorithms. Proximity Forest results use 100 trees and 5 candidates and are averaged over 10 runs.

  • UCR results: Table 1 compares Proximity Forest with five state-of-the-art algorithms on detailed UCR results.
  • Experimental setup: Proximity Forest results use 100 trees and 5 candidates.
  • Reporting: Proximity Forest results are averaged over 10 runs, with bold values indicating the best accuracy scores.

B On a variation of the Proximity Forest

The paper evaluates an “on tree” variant that selects one distance measure per tree instead of per node. The original “on node” approach has a slight advantage in the reported UCR comparison.

  • On tree variant: The “on tree” variant randomly selects a distance measure for each tree, while exemplars and metric parameters are selected at each node.The UCR experiments use 100 trees and 1 candidate for this variant, averaged over 50 runs.
  • Comparison: Figure 12 compares the original “on node” approach with the proposed “on tree” variant across UCR datasets.Each point represents one UCR dataset, with the number of trees fixed to 100.
  • Results: 44 wins, 39 losses and 2 ties give the “on node” approach a slight advantage over the “on tree” variant.The paper attributes greater robustness to inefficient metrics to the multiple measure combinations permitted within an “on node” tree.
Loading 1808.10594v2…