Proximity Forest: an effective and scalable distance-based classifier for time series (2018-08-31T00:00:00.000000Z)

TL;DR

Proximity Forest is introduced, an algorithm that learns accurate models from datasets with millions of time series, and classifies a time series in milliseconds, and ranks among the most accurate classifiers while being significantly faster on the UCR archive.

Abstract

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,000 time series only; which may explain why the primary research focus has been on 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.

References53 items

Comparison-Based Random Forests

Similarity Forests

Comparison-Based Nearest Neighbor Search

Fast and Accurate Time Series Classification with WEASEL

Indexing and classifying gigabytes of time series under time warping

The great time series classification bake off: a review and experimental evaluation of recent algorithmic advances

Fast classification of univariate and multivariate time series through shapelet discovery

Generalized random shapelet forests

Scalable time series classification

Overcoming Key Weaknesses of Distance-based Neighbourhood Methods using a Data Dependent Dissimilarity Measure

The BOSS is concerned with time series classification in the presence of noise

Faster and more accurate classification of time series by exploiting a novel dynamic time warping averaging algorithm

Time-Series Classification with COTE: The Collective of Transformation-Based Ensembles

Times Series Averaging and Denoising from a Probabilistic Perspective on Time–Elastic Kernels

Time series classification with ensembles of elastic distance measures

Dual-Domain Hierarchical Classification of Phonetic Time Series

Dynamic Time Warping Averaging of Time Series Allows Faster and More Accurate Classification

SAX-VSM: Interpretable Time Series Classification Using SAX and Vector Space Model

The Move-Split-Merge Metric for Time Series

Classification of time series by shapelet transformation

Using derivatives in time series classification

A time series forest for classification and feature extraction

Rotation-invariant similarity in time series using bag-of-patterns representation

SFA: a symbolic fourier approximation and index for similarity search in high dimensional datasets

Classification trees for time series

Weighted dynamic time warping for time series classification

Experimental comparison of representation methods and distance measures for time series data

Nearest neighbor search: algorithmic perspective

Faster retrieval with a two-pass dynamic-time-warping lower bound

Time Warp Edit Distance with Stiffness Adjustment for Time Series Matching

Anytime Classification Using the Nearest Neighbor Algorithm with Applications to Stream Mining

Decision Trees for Functional Variables

Statistical Comparisons of Classifiers over Multiple Data Sets

LB_Keogh supports exact indexing of shapes under rotation invariance with arbitrary representations and distance measures

Extremely randomized trees

Prototype selection for dissimilarity-based classifiers

Robust and fast similarity search for moving object trajectories

On The Marriage of Lp-norms and Edit Distance

Decision-tree Induction from Time-series Data Based on a Standard-example Split Test

A special case.

Dynamic programming algorithm optimization for spoken word recognition

Dynamic timewarping averaging

IEEE 13th international conference on data mining, pp 1175–1180

Fast Shapelets: A Scalable Algorithm for Discovering Time Series Shapelets

Indexing with Annoy

Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment

Time series shapelets: a novel technique that allows accurate, interpretable and fast classification

Indexing Multidimensional Time-Series

Random Forests

Derivative Dynamic Time Warping

A Dynamic Programming Approach to Continuous Speech Recognition

FLANN-Fast library for approximate nearest neighbors

COTE’s runtime complexity is bounded by (a) Shapelet Transform, which is O ( n 2 · l 4 ) [2] for n time series of length l , and (b) the parameter searches for EE, some of which are O ( n 2 · l 3 )