How Do You Estimate The Complexity of a Time Series

[seanlaw]

In Section 3.4 of the Annotation Vector paper, it mentions a way to estimate the complexity of any subsequence by sliding a window across the time series and, by imagining each subsequence as a “chain” or “rope”, have their complexity measured by “stretching” them and measuring the length of the resulting taut lines. The intuition is that the more complex the time series is, the longer its corresponding line will be. This section references an older CID: A Complexity-Invariant Distance Measure for Time Series paper where a complexity estimator is described in and below Figure 9:

$CE(Q) = \sqrt{ \sum ({q_i - q_{i+1}})^2 }$

How is this be accomplished in practice?

[seanlaw]

First, based on CID: A Complexity-Invariant Distance Measure for Time Series paper, we can follow their equation and define a simple function for the complexity estimator:

import numpy as np

def complexity_estimator(Q):
    return np.sqrt(np.sum(np.square(np.diff(Q))))

We can (roughly) reproduce Figure 9 with:

T1 = np.ones(40)
T2 = np.square(np.arange(40)) - 40. * np.arange(40)
T3 = np.random.rand(40)

complexity_estimator(T1)
complexity_estimator(T2)
complexity_estimator(T3)

And we'll see that the random time series is the "most complex" while the constant time series is he "least complex".

Then, for any time series, T, with window size, m, the complexity estimate for each subsequence can be computed with:

from stumpy import core

subseqs = core.rolling_window(T, m)
complexity_subseqs = np.apply_along_axis(complexity_estimator, axis=subseqs.ndim-1, arr=subseqs)

Of course, one could estimate the complexity using stddev as well:

np.nanstd(subseqs, axis=1)

[NimaSarajpoor]

As a follow up to @seanlaw's comment:

I think the provided definition for complexity estimator is the two-norm of ramps. Note that the number of ramps in a sequence is one less than the number of time stamps in a sequence. Hence:

from stumpy import core

T_ramp = np.diff(T)
m_ramp = m - 1

complexities = np.linalg.norm(core.rolling_window(T_ramp, m_ramp))

Also, if someone is interested in calculating the complexities after z-normalization, they can do it by scaling complexities as follows:

_, sliding_std = core.compute_mean_and_std(T, m)
z_complexiies = complexities / sliding_std

Note that we do not need the sliding_mean as this is basically an offset and it will not affect the result of ramp, where two consecutive values are substracted from each other.

[seanlaw]

@NimaSarajpoor Can you please provide a reference that explains what a "ramp" is? I'm not familiar with it.

[NimaSarajpoor]

@seanlaw
My apologies. It seems that the term "ramp" is often not known outside of wind-energy domain (e.g. I found this stackoverflow post but it is not official) So, it is better to stick with what the doc says about np.diff. In wind-energy, one common definition of ramp is the first-order discrete difference in time series (I am borrowing the definition of np.diff as provided in the numpy document).

I took a look at the definiton of cid in tsfresh library but couldn't find the term ramp. So, better to just ignore the term ramp :)

So, to wrap up: By ramp, I meant the first-order discrete difference, $q_{i+1} - q_{i}$.