Loading [MathJax]/extensions/MathMenu.js
Segmentation of Time Series in Improving Dynamic Time Warping | IEEE Conference Publication | IEEE Xplore

Segmentation of Time Series in Improving Dynamic Time Warping


Abstract:

Since its introduction to the computer science community, the Dynamic Time Warping (DTW) algorithm has demonstrated good performance with time series data. While this ela...Show More

Abstract:

Since its introduction to the computer science community, the Dynamic Time Warping (DTW) algorithm has demonstrated good performance with time series data. While this elastic measure is known for its effectiveness with time series sequence comparisons, the possibility of pathological warping paths weakens the algorithms potential considerably. Techniques centering on pruning off impossible mappings or lowering data dimensions such as windowing, slope weighting, step pattern, and approximation have been proposed over the years to reduce the possibility of pathological warping paths with Dynamic Time Warping. However, because the current DTW improvement techniques are mostly global methods, they are either limited in effect or limit the warping path excessively. We believe segmenting time series at significant feature points will alleviate some of the pathological warpings, and at the same time allowing us to obtain more intuitive warpings. Our heuristic approaches the problem from the human perspective of sequence comparison: by identifying global similarity before local similarities. We use easily identifiable peaks as the significant feature. The final distance is the DTW distance sum of all segments of time series. In this paper, we explore the impact of different peak identification parameters on Dynamic Time Warping and demonstrate how segmentation can help to avoid pathological warpings.
Date of Conference: 10-13 December 2018
Date Added to IEEE Xplore: 24 January 2019
ISBN Information:
Conference Location: Seattle, WA, USA
References is not available for this document.

I. Introduction

With the development of data collection and storage, time series data is now commonly applied in a variety of domains, from voice recognition, the stock market, to solar activities, medical research, and many other scientific and engineering fields where measurements in the temporal sense are important. With more data, the need to effectively process and compare data is essential. Distance measures can be categorized as lock-step and elastic. Lock-step measures generally refer to Lp norms, meaning the i-th element in one sequence is always mapped to the i-th element in another sequence. While elastic measures allow for one-to-many, or even one-to-none mappings [1]. With the commonly seen temporal discrepancies in time series sequences, traditional lock-step measures are not as effective as elastic when identifying similarities [2].

Select All
1.
X. Wang, A. Mueen, H. Ding, G. Trajcevski, P. Scheuermann and E. Keogh, "Experimental comparison of representation methods and distance measures for time series data", Data Mining and Knowledge Discovery, vol. 26, no. 2, pp. 275-309, 2013.
2.
P. Ranacher and K. Tzavella, "How to compare movement? a review of physical movement similarity measures in geographic information science and beyond", Cartography and geographic information science, vol. 41, no. 3, pp. 286-307, 2014.
3.
J. Serra and J. L. Arcos, "An empirical evaluation of similarity measures for time series classification", Knowledge-Based Systems, vol. 67, pp. 305-314, 2014.
4.
H. Sakoe and S. Chiba, "Dynamic programming algorithm optimization for spoken word recognition", IEEE transactions on acoustics speech and signal processing, vol. 26, no. 1, pp. 43-49, 1978.
5.
E. J. Keogh and M. J. Pazzani, "Derivative dynamic time warping", Proceedings of the 2001 SIAM International Conference on Data Mining, pp. 1-11, 2001.
6.
M. Müller, Information retrieval for music and motion, Springer, vol. 2, 2007.
7.
D. J. Berndt and J. Clifford, "Using dynamic time warping to find patterns in time series" in KDD workshop, Seattle, WA, vol. 10, pp. 359-370, 1994.
8.
M. Biba and F. Xhafa, Learning Structure and Schemas from Documents, Springer, vol. 375, 2011.
9.
F. Itakura, "Minimum prediction residual principle applied to speech recognition", IEEE Transactions on Acoustics Speech and Signal Processing, vol. 23, no. 1, pp. 67-72, 1975.
10.
J. Kruskall and M. Liberman, "The symmetric time warping algorithm: From continuous to discrete. time warps string edits and macromolecules", 1983.
11.
T. Giorgino et al., "Computing and visualizing dynamic time warping alignments in r: the dtw package", Journal of statistical Software, vol. 31, no. 7, pp. 1-24, 2009.
12.
H. Sakoe and S. Chiba, "Comparative study of dp-pattern matching techniques for speech recognition", 1973 Tech. Group Meeting Speech Acoust. Soc. Japan, 1973.
13.
L. R. Rabiner and B.-H. Juang, "Fundamentals of speech recognition", 1993.
14.
B.-K. Yi, H. Jagadish and C. Faloutsos, "Efficient retrieval of similar time sequences under time warping", Data Engineering 1998. Proceedings. 14th International Conference on, pp. 201-208, 1998.
15.
S.-W. Kim, S. Park and W. W. Chu, "An index-based approach for similarity search supporting time warping in large sequence databases", Data Engineering 2001. Proceedings. 17th International Conference on, pp. 607-614, 2001.
16.
E. Keogh and C. A. Ratanamahatana, "Exact indexing of dynamic time warping", Knowledge and information systems, vol. 7, no. 3, pp. 358-386, 2005.
17.
E. J. Keogh and M. J. Pazzani, "Scaling up dynamic time warping for datamining applications", Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 285-289, 2000.
18.
J. Zhao and L. Itti, "shapedtw: shape dynamic time warping", 2016.
19.
Y. Chen, E. Keogh, B. Hu, N. Begum, A. Bagnall, A. Mueen, et al., "The ucr time series classification archive", July 2015, [online] Available: www.cs.ucr.edu/∼eamonn/timeseriesdata/.

References

References is not available for this document.