Source-linked AI summary
A review on distance based time series classification
Amaia Abanda, Usue Mori, Jose A. Lozano
TL;DR
Time series classification must handle temporal structure and other data characteristics that make distance selection difficult, while 1-NN's performance may depend heavily on its underlying distance. The review presents a taxonomy of distance-based methods using direct k-NN classification, distance-derived features, or kernels, and discusses their strengths, shortcomings, and kernel definiteness challenges. It reports that newer distance-based approaches can be competitive with or outperform classic 1-NN approaches, while highlighting difficulties in consistently processing new unlabeled instances and in using indefinite kernels.
Problem
Time series classification is challenging because temporal structure, noise, high dimensionality, and variable lengths complicate distance definition, while 1-NN performance may rely strongly on the underlying distance.
Method
The review develops a taxonomy of methods that use time-series distances directly with k-NN classifiers, to construct feature vectors, or to construct kernels.
Results
New distance-based approaches achieve competitive performance with or outperform classic 1-NN approaches, including approaches based on distance-derived features and kernels.
Takeaways & Limitations
Distance measures can be exploited beyond direct 1-NN classification through feature representations and kernels, with positive semi-definiteness remaining a central kernel concern.
Takeaways & Limitations
Consistently processing new unlabeled instances is not straightforward, including when embedded features or regularized indefinite kernels are used.
Abstract
from arXiv · showhide
Time series classification is an increasing research topic due to the vast amount of time series data that are being created over a wide variety of fields. The particularity of the data makes it a challenging task and different approaches have been taken, including the distance based approach. 1-NN has been a widely used method within distance based time series classification due to it simplicity but still good performance. However, its supremacy may be attributed to being able to use specific distances for time series within the classification process and not to the classifier itself. With the aim of exploiting these distances within more complex classifiers, new approaches have arisen in the past few years that are competitive or which outperform the 1-NN based approaches. In some cases, these new methods use the distance measure to transform the series into feature vectors, bridging the gap between time series and traditional classifiers. In other cases, the distances are employed to obtain a time series kernel and enable the use of kernel methods for time series classification. One of the main challenges is that a kernel function must be positive semi-definite, a matter that is also addressed within this review. The presented review includes a taxonomy of all those methods that aim to classify time series using a distance based approach, as well as a discussion of the strengths and weaknesses of each method.
1 Introduction
Time series classification is challenging because temporal ordering, high dimensionality, noise, and varying lengths complicate distance definition. This review examines methods that exploit time-series distances within more complex classifiers, feature representations, and kernels.
- 1 Introduction: Time series classification is challenging because series are ordered, potentially high-dimensional, noisy, and of different lengths.These properties make defining a proper distance measure a key issue.
- 1 Introduction: Distance measures include lock-step comparisons such as Euclidean distance and elastic alignments such as Dynamic Time Warping.Elastic measures permit one-to-many point comparisons through nonlinear mappings.
- 1 Introduction: Most distance-based classification research has used distance measures with k-NN classifiers, especially 1-NN.The review attributes 1-NN's strong performance partly to time-series distances that account for temporal structure.
- 1 Introduction: New approaches use existing distances in more complex classifiers by transforming series into feature vectors or constructing kernels.Feature representations are order-free vectors, while kernels provide similarities for kernel methods.
- 1 Introduction: The review proposes a taxonomy of distance-based classification methods and discusses the strengths and shortcomings of each approach.The paper also identifies future research directions through its discussion of the reviewed methods.
2 A taxonomy of distance based time series classification
The taxonomy organizes distance-based time series classification according to how each method uses the distance. It distinguishes direct k-NN use, distance-derived feature vectors, and distance-derived kernels.
- 2 A taxonomy of distance based time series classification: The taxonomy divides methods into direct distance use with k-NN classifiers, distance-based feature vectors, and time-series kernels.These are the three main categories from the paper's general perspective.
2.1 k-Nearest Neighbour
The k-NN category directly combines existing time-series distances with nearest-neighbour classification. 1-NN is emphasized because it is simple, competitive, and can work particularly well with suitable distances.
- 2.1 k-Nearest Neighbour: 1-NN predicts a series' class from the class of its closest training-set object under a chosen distance.The method directly exploits an existing time-series distance during classification.
- 2.1 k-Nearest Neighbour: 1-NN has been widely used because of its simplicity and competitive performance in time series classification.Its asymptotic error is guaranteed to be lower than two times the Bayes error as the training set grows.
- 2.1 k-Nearest Neighbour: 1-NN combined with Dynamic Time Warping has achieved the best accuracy reported on many benchmark datasets.This combination has led many time-series studies and reviews to include 1-NN.
- 2.1 k-Nearest Neighbour: 1-NN is sensitive to noise in the training set, which is common in time-series datasets.The paper identifies this sensitivity as an important weakness of the approach.
2.2 Distance features
Distance features transform time series distances into representations usable by more complex classifiers, including global, local, and embedded approaches. These methods can improve or match 1-NN performance, but introduce computational and test-instance handling constraints.
- Global distance features: Global distance features use each series’ distances to other series as an order-free feature vector for conventional classifiers.The method builds a pairwise distance matrix and uses each row as the feature vector for one time series.
- Global distance features: Distance-feature representations bridge time-series distances and conventional classifiers, while potentially requiring large n×n matrices and costly training or prediction.For a new series, distances to all training series must be computed; the cost depends on the distance measure.
- Local distance features: Local distance features measure similarity to shapelets—class-representative subsequences—and use the resulting distances as classifier inputs.Shapelet transformation was evaluated with seven classifiers across multiple datasets, and extensions reported accuracy improvements on several datasets or across 85 UCR datasets.
- Embedded features: Embedded features learn vectors whose Euclidean distances approximate time-series distances such as DTW, but consistent treatment of unlabeled test samples depends on the embedding method.Some approaches learn transformed data rather than the transformation itself, while shapelet-based embeddings transform new instances using distances to learned shapelets.
2.3 Distance kernels
Distance kernels use time-series distances to construct similarities for kernel methods, either as general distance substitutions or as kernels designed to remain positive semi-definite. The review emphasizes that indefinite kernels weaken theoretical guarantees and leave the relationships among metricity, definiteness, and performance unresolved.
- Kernel-method pipeline: Kernel methods operate on pairwise similarities, forming a Gram matrix that is then used to produce a function for unseen instances.The kernel matrix contains entries Kij = κ(xi, xj) for input pairs xi and xj.
- Definiteness: A kernel is positive semi-definite when it satisfies the kernel inequality for all finite samples and coefficients, thereby defining an inner product in a Hilbert space.PSD kernels also support implicit feature mappings through the kernel trick.
- Indefinite distance kernels: Most distance measures do not directly yield PSD kernels, so indefinite-kernel methods either use them as-is, modify them, or analyze their theoretical properties.The review identifies approaches that learn with indefinite kernels, address their adverse effects, or study their relationship to distance properties.
- Indefinite distance kernels: Indefinite kernels lack guaranteed feature-space geometry and can make SVM optimization non-convex, although good classification results may still be obtained.Regularizing the kernel matrix can also produce large diagonal entries and overfitting, while consistent treatment of new instances is nontrivial.
- Distance kernels: Distance-based kernels replace conventional similarity construction with a time-series distance, extending kernel methods to temporal data.The review includes kernels defined directly on raw series and distinguishes them from kernels built on transformed representations such as Fourier expansions or autocorrelations.
- Open issues: Metricity, kernel definiteness, and classification performance appear related, but their individual contributions remain difficult to separate and constitute an open research direction.Metric distances tend to produce kernels closer to definiteness than non-metric distances, but the accuracy relationship is not clear.
3 Discussion and future work
The review organizes distance-based time series classification into distance-driven feature representations and kernels, while highlighting computational, definiteness, and benchmarking challenges. It identifies promising directions for improving scalability, understanding transformations, and developing PSD time-series kernels.
- Taxonomy: The review’s taxonomy distinguishes direct 1-NN methods, distance-based feature representations, and kernels constructed from distance measures.These categories organize methods according to how each approach uses the given distance.
- Distance features: Distance features bridge time series with conventional classifiers and can outperform existing benchmark classification methods.Their representations may be more discriminative and appropriate than raw series, but their discriminative properties remain insufficiently compared.
- Distance features: Distance-feature learning can become computationally intractable as training-set size grows, motivating dimensionality reduction and prototype selection.Prototype selection computes distances to representative series rather than the entire training set and remains almost unexplored in time series classification.
- Distance kernels: Distance-based kernels do not generally produce PSD kernels, making kernel definiteness a central issue for the mathematical foundations of kernel methods.Existing approaches either tolerate indefinite kernels or attempt regularization, whose effects have produced ambiguous results in time series classification.
- Distance kernels: Elastic PSD kernels can outperform 1-NN benchmarks, and REDK improves over GDS kernels especially when GDS kernel matrices are far from definite.The reported construction replaces recursive min or max operations with sums, preserving time elasticity while producing PSD kernels.
- Future work: The review emphasizes the scarcity of benchmark time-series kernels, particularly kernels that model temporal structure while remaining PSD.Many reviewed methods are general distance-based classification techniques that become time-series-specific through the chosen distance.