DBAResult(cost,converged,iterations,cost_trace)

Holds results of a DTW Barycenter Averaging (DBA) fit.

DBAclustResult(centers,clustids,result)

Holds results of a DBAclust run.

struct DTW{D,N} <: DTWDistance{D}

Keyword arguments:

• radius: The maximum allowed deviation of the matching path from the diagonal
• dist: Inner distance
• transportcost If >1, an additional penalty factor for non-diagonal moves is added.
• normalizer: defaults to Nothing. Supported options are the normalizers defined in SlidingDistancesBase.jl

If the two time-series are of equal length, dtw_cost is called, if not, dtwnn is called.

struct FastDTW{D} <: DTWDistance{D}

• radius
• dist inner distance

GDTWWorkspace{T}(M, N)

Creates a cache of numeric type T for use in gdtw.

LinearInterpolation(x::AbstractVector) -> Function

Provides a linear interpolation of x on the interval [0,1].

struct SoftDTW{D, T} <: DTWDistance{D}

Arguments:

• γ: smoothing parameter default to 1. Smaller value makes the distance closer to standard DTW.
• dist: Inner distance, defaults to SqEuclidean().
• transportcost

inds = align_signals(s::AbstractVector{<:AbstractArray}, master = argmax(length.(s)); method = :dtw, output=:indices)

Compute a set of indices such that s[i][inds[i]] is optimally aligned to s[master]. All elements of inds will have the same length.

Arguments:

• s: A vector of signals to align
• master: Index of the signal used as reference. All the other signals will be aligned to this one.
• method: :dtw uses the warping paths from dtw between s[master] and s[i]. :xcorr uses DSP.finddelay which internally computes the cross correlation between signals, which often results in a slight misalignment.
• output: The default is to output the aligning indices, alternatively, the aligned :signals themselves can be outputted.

avgseq, results = dba(sequences, dist::DTWDistance; kwargs...)

Perfoms DTW Barycenter Averaging (DBA) given a collection of sequences and the current estimate of the average sequence.

Example usage:

x = [1., 2., 2., 3., 3., 4.]
y = [1., 3., 4.]
z = [1., 2., 2., 4.]
avg,result = dba([x,y,z], DTW(3))

Performs one iteration of DTW Barycenter Averaging (DBA) given a collection of sequences and the current estimate of the average sequence, dbavg. Returns an updated estimate, and the cost/loss of the previous estimate

dbaclust(
    sequences,
    nclust::Int,
    dtwdist::DTWDistance;
    n_init::Int           = 1,
    iterations::Int       = 100,
    inner_iterations::Int = 10,
    rtol::Float64         = 1e-4,
    rtol_inner::Float64   = rtol,
    threaded::Bool        = false,
    show_progress::Bool   = true,
    store_trace::Bool     = true,
    i2min::AbstractVector = [],
    i2max::AbstractVector = [],
)

Arguments:

• nclust: Number of clsuters
• n_init: Number of initialization tries
• inner_iterations: Number of iterations in the inner alg.
• i2min: Bounds on the warping path
• threaded: Use multi-threading

dbaclustinitialcenters(sequences, nclust, dtwdist::DTWDistance; threaded::Bool = false)

Uses kmeans++ (but with dtw distance) to initialize the centers for dba clustering.

avgseq, results = dbaclust_single(sequences, dist; kwargs...)

Perfoms a single DTW Barycenter Averaging (DBA) given a collection of sequences and the current estimate of the average sequence.

Example usage:

x = [1,2,2,3,3,4]
y = [1,3,4]
z = [1,2,2,4]
avg,result = dba([x,y,z], DTW(3))

cost,i1,i2 = dtw(seq1, seq2, [dist=SqEuclidean, postprocess=nothing])
cost,i1,i2 = dtw(seq1, seq2, dist, i2min, i2max)

Perform dynamic-time warping to measure the distance between two sequences.

Find a set of indices (i1,i2) that align two series (seq1,seq2) by dynamic axis warping. Also returns the distance (after warping) according to the SemiMetric dist, which defaults to squared Euclidean distance (see Distances.jl). If seq1 and seq2 are matrices, each column is considered an observation.

If i2min/max are provided, do DTW to align seq1 and seq2 confined to a window. Vectors i2min and i2max specify (inclusive) lower and upper bounds for seq2 for each index in seq1. Thus, i2min and i2max are required to be the same length as seq1.

If filternernel::AbstractMatrix is provided, it's used to filter the cost matrix. Create a suitable kerlen using, e.g., ImageFiltering.Kernel.gaussian(3). The filtering of the cost matrix makes the warping smoother, effectively penalizing small-scale warping.

See also dtw_cost and dtwnn.

dtw_cost(a::AbstractArray, b::AbstractArray, dist::Distances.SemiMetric, r::Int; best_so_far = Inf, cumulative_bound = Zeros(length(a)))

Perform dynamic time warping to measure the distance between two sequences.

Calculate the DTW cost between a and b with maximum warping radius r. You may provide values of best_so_far and cumulative_bound in order to enable early stopping.

Keyword arguments:

• best_so_far: The best cost value obtained so far (optional)
• cumulative_bound: A vector the same length as a and b (optional)
• s1: Optional storage vector of length 2r+1, can be used to save allocations.
• s2: Optional storage vector of length 2r+1, can be used to save allocations.

Providing the two vectors s1, s2 does not save very much time, but it makes the function completely allocation free. Can be useful in a threaded context.

See also dtw and dtwnn. This code was inspired by https://www.cs.ucr.edu/~eamonn/UCRsuite.html

search_result = dtwnn(q, y, dist, rad, [normalizer::Type{Nothing}]; kwargs...)

Compute the nearest neighbor to q in y. An optinal normalizer type can be supplied, see, ZNormalizer, DiagonalZNormalizer, NormNormalizer.

Arguments:

• q: query (the short time series)
• y: data ( the long time series)
• dist: distance
• rad: radius
• showprogress: Defaults to true
• prune_endpoints = true: use endpoint heuristic
• prune_envelope = true: use envelope heuristic
• bsf_multiplier = 1: If > 1, require lower bound to exceed bsf_multiplier*best_so_far.
• saveall = false: compute a dense result (takes longer, no early stopping methods used). If false, then a vector of lower bounds on the distance is stored in search_result.dists, if true, all distances are computed and stored.
• avoid: If an integer index (or set of indices) is provided, this index will be avoided in the search. This is useful in case q is a part of y.

dtwplot(seq1, seq2, [dist=SqEuclidean()]; transportcost=1, diagonal=false)
dtwplot(seq1, seq2, D, i1, i2; transportcost=1, diagonal=false)
dtwplot(seq1, seq2, D; transportcost=1, diagonal=false)

Given two sequences, perform dynamic time warping and plot the results. If alignment has already been computed, pass the indices i1 and i2 to make the plot.

diagonal = true plots a diagonal marker as visual aid.

cost,i1,i2 = fastdtw(seq1,seq2,dist,radius)

Perform dynamic-time warping using the FastDTW algorithm to measure the distance between two sequences. Note that regular DTW often performs better than FastDTW https://arxiv.org/abs/2003.11246

Computes FastDTW approximation to the DTW, described in Salvador & Chan, Intelligent Data Analysis (2007).

See also dtw, dtw_cost, dtwnn.

gdtw(
    x,
    y,
    ::Type{T}  = Float64;
    symmetric::Bool = true,
    M::Int     = 100,
    N::Int     = 100,
    t          = range(T(0), stop = T(1), length = N),
    cache::GDTWWorkspace = GDTWWorkspace(T, M, length(t)),
    λcum       = T(0.01),
    λinst      = T(0.01),
    η          = T(1 / 8),
    max_iters  = 3,
    metric     = (x, y) -> norm(x - y),
    Rcum       = abs2,
    smin::Real = T(0.001),
    smax::Real = T(5.0),
    Rinst      = symmetric  ?
                    ϕ′ -> ( (smin <= ϕ′ <= smax)
                        && (smin <= 2 - ϕ′ <= smax) ) ? (ϕ′-1)^2 : typemax(T)
                            :
                    ϕ′ -> (smin <= ϕ′ <= smax) ? (ϕ′-1)^2 : typemax(T),
    verbose    = false,
    warp       = zeros(T, length(t)),
    callback   = nothing,
) where T -> cost, ϕ, ψ

Computes a general DTW distance following DB19.

Aims to find ϕ(s) to minimize

∫ metric(x(ϕ(s)), y(ψ(s))) + λinst*Rinst(ϕ'(s) - 1) + λcum*Rcum(ϕ(s) - s) ds

over the interval s ∈ [0,1], where ψ(s) = 2s - ϕ(s) (if symmetric=true) or ψ(s) = s (if symmetric = false). The integral is discretized in time into N points (or according to the times t, if t is specified). Additionally, the possible values obtained by ϕ (and hence ψ) at each possible time s are discretized into M points.

If max_iters > 1, then after solving the doubly-discretized problem to obtain the optimal ϕ, the problem is solved again by choosing a new discretization of M possible values of ϕ(s) in an interval (whose width is governed by the parameter η) around the previous optimal value. This is repeated until the problem has been solved max_iters times in total. Setting verbose=true prints the cost at each iteration; a "high enough" value of max_iters can be chosen by inspecting when the cost stabilizes sufficiently.

The parameters are:

• x: the continuous time signal to warp (see LinearInterpolation for generating such a signal from discrete data)
• y: the continuous-time signal to warp to
• T: the numeric type to be used in the problem
• symmetric: if true, ψ(s) = 2s - ϕ(s), otherwise ψ(s) = s.
• t: the discretization of time on [0,1]; either t or N should be specified
• M: the discretization of the values obtained by the warping path
• metric: a function metric(u,v) -> ℝ to compute differences between the signals at a time point (such as a Distances.jl distance)
• Rcum: penalty function on the cumulative warp
• Rinst: penalty function on the instantaenous warping. Should be infinite outside of [smin, smax].
• smin, smax: minimum and maximum allowed instantaenous warping. Should have smin > 0 and smin < smax.
• λcum, λinst: the regularization constants for Rcum and Rinst, respectively

The following may be pre-allocated and reused between distance computations with the same M and N (or length(t)).

• cache: a cache of matrices and vectors, generated by GDTW.GDTWWorkspace{T}(N,M)

gdtw_warpings(data) -> ϕ, ψ

Computes the interpolations from a data NamedTuple with entries for the time points t, warping points warp, and a boolean symmetric.

iterative_gdtw!(data; max_iters = data.max_iters, verbose = data.verbose) -> cost

Runs the GDTW algorithm with iterative refinement for max_iters iterations, returning the resulting cost. Uses the GDTWWorkspace in data.cache and updates the data.warp vector. Here, data is usually obtained by prepare_gdtw.

This can be called multiple times on the same data with a higher value of max_iters to refine a calculation without starting over, which can be useful for checking convergence.

Example

data = prepare_gdtw(x,y; max_iters = 3)
cost3 = iterative_gdtw!(data) # performs 3 iterations, returns the cost
cost10 = iterative_gdtw!(data; max_iters = 10) # performs 7 more iterations, returns the cost
ϕ, ψ = gdtw_warpings(data)

# Equivalently,
cost10, ϕ, ψ = gdtw(x,y; max_iters = 10)

matchplot2

Like matchplot, but works with 2d and 3d signals.

Inputs

Positional args

For available positional argument patterns, see DynamicAxisWarping.handleargs

Generally, it can accept a x and y signal to warp and optionally dtw_cost_matrix inputs, or x and y signal plus dtw or dtw_cost_matrix outputs (skipping the warp step).

Keyword args

• transportcost – see dtw_cost_matrix
• separation – extra separation/padding added between the signals in in ℜⁿ
• showindex – Whether to add an axis in the plot for the index/"time" axis (appends to the last dimension)

prepare_gdtw(x, y; kwargs...)

Creates a NamedTuple of parameters, using the same keyword argments as dist. A preprocessing step before calling iterative_gdtw!.

imin, imax = radiuslimits(r, n::Int, m::Int)
imin, imax = radiuslimits(r, seq1, seq2)

soft_dtw_cost(args...; γ = 1, kwargs...)

Perform Soft DTW. This is a differentiable version of DTW. The "distance" returned by this function is quite far from a true distance and can be negative. A smaller value of γ makes the distance closer to the standard DTW distance.

To differentiate w.r.t. the first argument, try

using ReverseDiff
da = ReverseDiff.gradient(a->soft_dtw_cost(a,b), a)

Ref: "Soft-DTW: a Differentiable Loss Function for Time-Series" https://arxiv.org/pdf/1703.01541.pdf

#Arguments:

• args: same as for dtw
• γ: The smoothing factor. A small value means less smoothing and a result closer to dtw_cost
• kwargs: same as for dtw

dists, inds = sparse_distmat(y::Vector{<:AbstractVector{T}}, k, dist, radius; kwargs...) where T

Compute the k nearest neighbors between signals in y, corresponding to the k smallest entries in each row of the pairwise distance matrix. The return values are vectors of length-k vectors with the calculated distances and neighbor indices.

#Arguments:

• y: Vector of vectors containing the signals
• k: number of neighbors
• dist: the inner metric, e.g., SqEuclidean()
• kwargs: these are sent to dtw_cost.
• showprogress = true

cost,cols,rows = trackback(D::Matrix)

Given the cost matrix D, computes the optimal track from end to beginning. Returns cols and rows which are vectors respectively holding the track.

distance_profile(d::DTWDistance, Q::AbstractArray{S}, T::AbstractArray{S}; kwargs...) where S

Optimized method for computing the distance profile using DTW distances. kwargs are sent to dtwnn.

optional_threaded(cond, ex)

Execute ex with multi-threading if cond is true, otherwise execute with one core

fakedata_gaussian(pts_per_clust::Int = 10, nclust::Int = 2, xmin = 0.0, xmax = nclust * 7.0, nx = round(Int, (xmax - xmin) * 10), σ = 1.0, amin = 1.0, amax = 2.0)

DOCSTRING

Arguments:

• pts_per_clust: DESCRIPTION
• nclust: DESCRIPTION
• xmin: DESCRIPTION
• xmax: DESCRIPTION
• nx: DESCRIPTION
• σ: DESCRIPTION
• amin: DESCRIPTION
• amax: DESCRIPTION