0
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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:

$\endgroup$
1
  • $\begingroup$ Thank you! I used the LB_Enhanced technique from the second reference. There is an implementation of it on github - github.com/moradabaz/KNN-LB $\endgroup$
    – AlexRonsky
    Mar 11, 2023 at 23:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.