Distance Similarity
Distance Similarity SPIs Overview
Distance-based similarity measures aim to establish similarity or independence based on the pairwise distance between bivariate observations. All of the methods presented in this section are implemented using one of the following toolboxes:
For distance correlation (and related) statistics, as well as reproducing kernel Hilbert space (RKHS)-based statistics, we use the Hypothesis Testing in Python (hyppo) package.
For dynamic time warping (and related) statistics, we use the tslearn package.
BarycenterKeywords: undirected, nonlinear, unsigned, bivariate, time-dependent.
Base Identifier:
bary
A barycenter (or Fréchet mean) is a (univariate) time series that minimizes the sum of squared distances between MTS. The tslearn package provides functions to obtain barycenters by minimising the sum-of-squares of the following distance metrics:
(Unwarped) Euclidean distance (
euclidean).Alignment via expectation maximisation (
dtw).Alignment via a differential loss function (
softdtw).Alignment via a sub-gradient descent algorithm (
sgddtw).
For each pair of (bivariate) time series in an M-variate MTS, we compute the raw barycenters then summarise them by taking their mean (modifier mean), maximum (max) or timepoint at which the maximum occurs (max_time).
Cross Distance CorrelationKeywords: undirected, nonlinear, unsigned, bivariate, time-dependent.
Base Identifier:
dcorrxKey References: [1]
The cross-distance correlation quantifies the independence between two univariate time series based on distance correlation. This measure is the average of lagged distance correlations between the past of time series x to the future of time series y, up to a given lag. We include both a low-order (lag-1, maxlag-1) and a high-order (lag-10, maxlag-10) assumption of the number of relevant lags.
Cross Multiscale Graph CorrelationKeywords: undirected, nonlinear, unsigned, bivariate, time-dependent.
Base Identifier:
mgcxKey References: [1]
The cross-multiscale graph correlation is defined similarly to Cross Distance Correlation (dcorrx) but uses lagged MGCs instead of lagged distance correlations. We include both a low-order (lag-1, maxlag-1) and a high-order (lag-10, maxlag-10) assumption of the number of relevant lags.
Distance CorrelationKeywords: undirected, nonlinear, unsigned, bivariate, contemporaneous.
Base Identifier:
dcorrKey References: [1]
Distance correlation is used to infer the independence between two random variables via pairwise distance metrics and hypothesis tests. The sample distance correlation is computed by summing over the entry-wise product of Euclidean distance matrices. This statistic is biased, however an unbiased estimator can be obtained by first double-centering the distance matrices. Although any pairwise distance metric can be used, here we only use Euclidean distance because distance correlation computed with this metric has been shown to be universally consistent (asymptotically converging to the true value). We compute both the biased and unbiased statistics from the hyppo package.
Dynamic Time WarpingKeywords: undirected, nonlinear, unsigned, bivariate, time-dependent.
Base Identifier:
dtwKey References: [1]
Dynamic time warping (DTW) extends the ideas of measuring the pairwise Euclidean distance between time series by allowing for potentially dilated time series of variable size. Specifically, DTW finds the minimum distance between two time series through alignment (shifting and dilating of the sequences). This algorithm (and many outlined below) also includes the Sakoe-Chiba band and the Itakura parallelogram global constraints on the alignments to prevent pathological warpings. We compute this statistic using the tslearn package for the three global constraints, given by each of the estimators:
Gromov-Wasserstein DistanceKeywords: undirected, nonlinear, unsigned, unordered, distance.
Base Identifier:
gwtauKey References: [1]
The Gromov-Wasserstein distance (GWτ) represents each time series as a metric space and computing the distances from the start of each time series to every point. These distance distributions are then compared using the Wasserstein distance, which finds the optimal way to match the distances between two time series, making it robust to shifts and perturbations. The "tau" in GWτ emphasises that this distance measure is based on comparing the distributions of distances from the root (i.e., the starting point) to all other points in each time series, which is analogous to comparing the branch lengths in two tree-like structures. This SPI is based on the algorithm proposed by Kravtsova et al. (2023).
Heller-Heller-Gorfine Independence CriterionKeywords: undirected, nonlinear, unsigned, bivariate, contemporaneous.
Base Identifier:
hhgKey References: [1]
The Heller-Heller-Gorfine (HHG) method yields an RKHS-based statistic that uses the ranks of random variables to obtain sample kernel matrices, rather than their distances. This SPI is computed via the hyppo package.
Hilbert-Schmidt Independence CriterionKeywords: undirected, nonlinear, unsigned, bivariate, contemporaneous.
Base Identifier:
hsicKey References: [1]
The Hilbert-Schmidt Independence Criterion (HSIC) is an RKHS-based statistic that quantifies a statistical dependence between random variables via a sample kernel matrix. As with distance correlation, HSIC yields a biased statistic, where the unbiased (and consistent) estimator can be derived by double centering the kernel distance matrix. Both biased and unbiased (no modifier) estimators are computed using hyppo.
Longest Common SubsequenceKeywords: undirected, nonlinear, unsigned, bivariate, time-dependent.
Base Identifier:
lcssKey References: [1]
The longest common subsequence (LCSS) generalises ideas from DTW by measuring the similarity between continuous subsections of time series, rather than the entire time series themselves, subject to distance thresholds and alignment constraints. We use the default threshold from the tslearn package (ε = 1), and include the three global constraints:
No constraints (no modifier)
The band (modifier
sakoe_chiba)The parallelogram (
itakura)
Multiscale Graph CorrelationKeywords: undirected, nonlinear, unsigned, bivariate, contemporaneous.
Base Identifier:
mgcKey References: [1]
Multiscale graph correlation (MGC) is a generalisation of distance correlation that is designed to overcome its limitations in inferring nonlinear relationships such as circles and parabolas. Specifically, the algorithm truncates the Euclidean distance matrices (the procedure at the core of distance correlation) at an optimal threshold. MGC also includes a smoothing function that is intended to remove any bias introduced by disconnected components in the graph introduced by truncating the distance matrix. Only this unbiased estimator is included here (as in hyppo).
Soft Dynamic Time WarpingKeywords: undirected, nonlinear, unsigned, bivariate, time-dependent.
Base Identifier:
softdtwKey References: [1]
Soft dynamic time warping uses a smoothed formulation of DTW to optimize the minimal-cost alignment as a differentiable loss function. This method is computed via the tslearn package (with the default hyperparameter, γ = 1), and includes the same global constraints as DTW:
No constraints (no modifier)
The band (modifier
sakoe_chiba)The parallelogram (
itakura)
Pairwise DistanceKeywords: undirected, nonlinear, unsigned, unordered.
Base Identifier:
pdist
Pairwise distance between time-series, computed using sklearn's pairwise distance function using the following distance metrics:
Euclidean
Cityblock
Cosine
Chebyshev
Canberra
Braycurtis
Last updated
