Segmented Dynamic Time Warping: A Comparative and Applicational Study

Introduction

Different data and applications usually require different distance measures. Generally speaking, distance measures can be categorized as either a lock-step measure or an elastic measure. Lock-step measure commonly refers to -norms, meaning that the -th element from one sequence is always mapped to the -th element in the compared sequence. Since the mapping between the two sequences is fixed, lock-step measures are sensitive to noise and misalignments (Ranacher et al., 2014). The elastic measure, on the other hand, allows one-to-many, or even one-to-none mappings (Wang et al., 2013). A suitable distance measure should be chosen based on the data and task at hand.

With the improvement of data storage capability and processing power, more and more data are now being collected and used in the form of time series. Time series data is widely applied in a variety of domains, such as voice recognition, the stock market, solar activities, medical research, and many other scientific and engineering fields where measurements in the temporal sense are important. Time series data enjoys its popularity because it records details that can be overlooked by the summarization of data. At the same time, small temporal discrepancies and unequal length are very common in time series sequences. This length difference means lock-step distance measures are not as effective as elastic measures when identifying similarities in time series data (Ranacher et al., 2014).

A widely used elastic measure is the Dynamic Time Warping (DTW) algorithm (Serra et al., 2014). The warping path, or shortest global route, for DTW is identified based on the computation and comparisons of several options at each step. While this contributes to the general success of the DTW algorithm’s performance with time series data, the large- scale computations make DTW a very time-consuming algorithm. Another common issue to run into when using DTW is the occurrence of pathological warping path, which happens when the warping path tries to compensate value differences by making wild and improbable mappings, as shown in Figure 1 (a). When the path is found in a greedy manner and never readjusted, the optimal warping path could be permanently missed. The root cause of pathological warping paths is that the decision at each step does not take significant global similarities into consideration; in other words, the bigger picture is neglected in standard DTW. In application, we can often observe the warping path between two time series does not match the expected intuitive mapping. Previously, it has been found that segmentation of time series based on feature peaks can alleviate this problem (Ma et al., 2018). Global similarity can be identified by adding a layer of peak identification, which acts as a form of restraints, then the focus on local similarity is found by mapping the points and computing the distances of each corresponding segments.