Distance Similarity
Last updated
Last updated
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 (hyppo) package.
For dynamic time warping (and related) statistics, we use the package.
Barycenter: undirected, nonlinear, unsigned, bivariate, time-dependent.
Base Identifier:
bary
Key References: ,
A barycenter (or Fréchet mean) is a (univariate) time series that minimizes the sum of squared distances between MTS. The 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
) and maximum (max
).
Cross Distance CorrelationBase Identifier:
dcorrx
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 CorrelationBase Identifier:
mgcx
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 CorrelationBase Identifier:
dcorr
Dynamic Time WarpingBase Identifier:
dtw
Gromov-Wasserstein DistanceBase Identifier:
gwtau
Heller-Heller-Gorfine Independence CriterionBase Identifier:
hhg
Hilbert-Schmidt Independence CriterionBase Identifier:
hsic
Longest Common SubsequenceBase Identifier:
lcss
No constraints (no modifier)
The band (modifier sakoe_chiba
)
The parallelogram (itakura
)
Multiscale Graph CorrelationBase Identifier:
mgc
Soft Dynamic Time WarpingBase Identifier:
softdtw
No constraints (no modifier)
The band (modifier sakoe_chiba
)
The parallelogram (itakura
)
Pairwise DistanceBase Identifier:
pdist
Euclidean
Cityblock
Cosine
Chebyshev
Canberra
Braycurtis
: undirected, nonlinear, unsigned, bivariate, time-dependent.
Key References:
: undirected, nonlinear, unsigned, bivariate, time-dependent.
Key References:
: undirected, nonlinear, unsigned, bivariate, contemporaneous.
Key References:
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 package.
: undirected, nonlinear, unsigned, bivariate, time-dependent.
Key References:
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 package for the three global constraints, given by each of the estimators:
: undirected, nonlinear, unsigned, unordered, distance.
Key References:
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 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 .
: undirected, nonlinear, unsigned, bivariate, contemporaneous.
Key References:
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 package.
: undirected, nonlinear, unsigned, bivariate, contemporaneous.
Key References:
The Hibert-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 .
undirected, nonlinear, unsigned, bivariate, time-dependent.
Key References:
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 package (ε = 1), and include the three global constraints:
undirected, nonlinear, unsigned, bivariate, contemporaneous.
Key References:
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 ).
: undirected, nonlinear, unsigned, bivariate, time-dependent.
Key References:
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 package (with the default hyperparameter, γ = 1), and includes the same global constraints as DTW:
: undirected, nonlinear, unsigned, unordered.
Pairwise distance between time-series, computed using sklearn's using the following distance metrics: