Patterns extraction in time serie with DTW

Question

I have a long time serie, let's say 1000 items. I want to find patterns in it of different lengths from 10 to 100 elements. To do this, I extract sliding windows of different lengths and calculate distance matrix between them using DTW. But it works very slowly. Can you please tell me if there is a more efficient method?

My code:

def generate_sliding_windows(series, window_size):
    sliding_windows = []
    for i in range(0, len(series) - window_size + 1):
        window = tuple(series[i:i + window_size])
        indexes = (i, i + window_size)
        sliding_windows.append(
            SlidingWindow(data=np.array(window), indexes=np.array(indexes))
        )
    return sliding_windows

sliding_windows = []
for window_size in range(10, 100):
    sliding_windows.extend(
        generate_sliding_windows(time_serie, window_size))
        
n = len(sliding_windows)
distance_matrix = np.zeros((n, n))
for i in range(n):
    for j in range(i + 1, n):
        dist = fastdtw(x, y, dist=euclidean)[0]
        distance_matrix[i][j] = dist
        distance_matrix[j][i] = dist

The slowest piece of code here is the calculation of the distance matrix.

Answer 1

If you haven't done so already, the first thing I suggest doing is checking to see how many sliding windows you are generating, and therefore how many DTW distances you are calculating.

Also, do you really want to calculate the distance between all possible subsequences of lengths 10 to 100? What will be the DTW distance between, say, the subsequences time_series[10:20] and time_series[10:21] and is this relevant to what you are trying to do?

If this is still taking too long after you've cut down the number of DTW distances you are calculating, I'd suggest looking at lower-bounding techniques. Lower-bounding established a lower bound on the DTW distance using a calculation that is much faster than DTW. If the lower bound distance doesn't meet the criterion for inclusion as a pattern, then you know there's no point calculating the full DTW distance. Then you only need to calculate the expensive DTW distance when the lower bound distance meets the criterion.

A couple of references with more information about lower bounding are:

• Rakthanmanon et al.: Searching and mining trillions of time series subsequences under dynamic time warping
• Tan et al.: Elastic bands across the path: A new framework and method to lower bound DTW