Adaptive Dynamic Time Warping for Variable Structure Pattern Recognition

Authors: S. V. Yendiyarov

Abstract:

Pattern discovery from time series is of fundamental importance. Particularly, when information about the structure of a pattern is not complete, an algorithm to discover specific patterns or shapes automatically from the time series data is necessary. The dynamic time warping is a technique that allows local flexibility in aligning time series. Because of this, it is widely used in many fields such as science, medicine, industry, finance and others. However, a major problem of the dynamic time warping is that it is not able to work with structural changes of a pattern. This problem arises when the structure is influenced by noise, which is a common thing in practice for almost every application. This paper addresses this problem by means of developing a novel technique called adaptive dynamic time warping.

Keywords: Pattern recognition, optimal control, quadratic programming, dynamic programming, dynamic time warping, sintering control.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1088596

References:

[1] D. Berndt, J. Clifford.: Using Dynamic Time Warping to Find Patterns in Time Series. In KDD-94: AAAI Workshop on Knowledge Discovery in Databases, Seattle, Washington, July 1994, pp. 359-370.
[2] K. Hiri-o-tappa, S. Narupiti, S. Pattara-atikom.: A novel approach of dynamic time warping for short-term traffic congestion prediction, Transportation Research Board 90th Annual Meeting, January 23-27, Washington, D.C., 2011, pp. 1-15.
[3] E. Keogh and C. Ratanamahatana.: Exact indexing of dynamic time warping, Knowl. Inf. Syst. 7(3), 2005, pp. 358-386.
[4] Y. Sakurai.: FTW: fast similarity search under the time warping distance, PODS, 2005, pp. 326-337.
[5] A. Fu, E. Keogh, L. Lau, C. Ratanamahatana, R. Wong.: Scaling and time warping in time series querying, VLDB, 17, 4, pp. 899-921, 2008.
[6] N. Gillian, R. Knapp, S. O’Modhrain.: Recognition of multivariate temporal musical gestures using n-dimensional dynamic time warping. Proc of the 11th Int'l conference on New Interfaces for Musical Expression, 2011.
[7] E. Keogh, L. Wei, X. Xi, M. Vlachos, S.H. Lee, P. Protopapas.: Supporting exact indexing of arbitrarily rotated shapes and periodic time series under Euclidean and warping distance measures. VLDB J. 18, 3, pp. 611-630, 2009.
[8] A. Mueen, E. Keogh.: Online discovery and maintenance of time series motifs. KDD, pp. 1089-1098, 2010.
[9] L. Ye, E. Keogh.: Time series shapelets: a new primitive for data mining. KDD, pp. 947-956, 2009.
[10] Y. Zhang, J. Glass.: An inner-product lower-bound estimate for dynamic time warping. ICASSP, pp. 5660-5663, 2011.
[11] E. Keogh.: Exact indexing of dynamic time warping.In VLDB, pp. 406– 417, 2002.
[12] E. Keogh, M. Pazzani.: Scaling up dynamic time warping for data mining applications, KDD 2000, pp. 285-289, 2000.
[13] B. Yi.: Efficient Retrieval of Similar Time Sequences Under Time Warping, ICDE 1998, pp. 201-208, 1998.
[14] Yendiyarov, S., Zobnin B., Petrushenko S. Expert system for sintering process control based on the information about solid-fuel flow composition // Proceedings of World Academy of Science, Engineering and Technology, France, Issue 68, August 2012, pp. 861-868