Segmented Dynamic Time Warping: A Comparative and Applicational Study

Segmented Dynamic Time Warping: A Comparative and Applicational Study

Ruizhe Ma (Georgia State University, USA), Azim Ahmadzadeh (Georgia State University, USA), Soukaina Filali Boubrahimi (Georgia State University, USA) and Rafal A. Angryk (Georgia State University, USA)
DOI: 10.4018/978-1-5225-8446-9.ch001

Abstract

Initially used in speech recognition, the dynamic time warping algorithm (DTW) has regained popularity with the widespread use of time series data. While demonstrating good performance, this elastic measure has two significant drawbacks: high computational costs and the possibility of pathological warping paths. Due to the balance between performance and the tightness of restrictions, the effects of many improvement techniques are either limited in effect or use accuracy as a trade-off. In this chapter, the authors discuss segmented-DTW (segDTW) and its applications. The intuition behind significant features is first established. Then considering the variability of different datasets, the relationship between specific global feature selection parameters, feature numbers, and performance are demonstrated. Other than the improvement in computational speed and scalability, another advantage of segDTW is that while it can be a stand-alone heuristic, it can also be easily combined with other DTW improvement methods.
Chapter Preview
Top

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.

Key Terms in this Chapter

Hungarian Algorithm: A combinatorial optimization algorithm used to find maximum-weight matchings, which can be used to solve the assignment problem.

K-Nearest Neighbors: A method applied in classification and regression for pattern recognition, where the input consists of the k closest examples in feature space.

Dynamic Time Warping: An elastic similarity measure for temporal sequences alignment.

Classification: A supervised learning method in machine learning, which is used to identify unknown instance categories based on known instances.

Time Series Data: An indexed series of data points taken at equally spaced points in time in a sequential order.

Parallel Process: A computation process in which one computation can be broken into several computations and processed simultaneously.

Complete Chapter List

Search this Book:
Reset