We may start learning DTW(Dynamic Time Warping) with understanding what is time series. According to Wikipedia, a time series is a series of data points indexed in time order. Most commonly, a time series is a sequence taken at successive equally spaced points in time. Thus it is a sequence of discrete-time data. You can see simple time series example below. It shows temperature data collected from 4 different sensor over 4 days in some constant frequency.
Because many types of date can be transformed into time series similarity measurement can be beneficial. One of these similarity measurement algorithm is DTW. The algorithm can measure difference between two time series which may vary in time or speed. We can visualize our statement with below animation. Although these two people’s joint movement is almost same, their speed is different. DTW can match these two movement data.
In general, DTW is a method that calculates an optimal match between two given sequences (e.g. time series) with certain restriction and rules:
- Every index from the first sequence must be matched with one or more indices from the other sequence, and vice versa
- The first index from the first sequence must be matched with the first index from the other sequence (but it does not have to be its only match)
- The last index from the first sequence must be matched with the last index from the other sequence (but it does not have to be its only match)
- The mapping of the indices from the first sequence to indices from the other sequence must be monotonically increasing, and vice versa, i.e. if j > i are indices from the first sequence, then there must not be two indices l > k in the other sequence, such that index i is matched with index l and index j is matched with index k , and vice versa
The optimal match is denoted by the match that satisfies all the restrictions and the rules and that has the minimal cost, where the cost is computed as the sum of absolute differences, for each matched pair of indices, between their values.
