DTW-Distance Based Kernel for Time Series Data

Hiroyuki NARITA  Yasumasa SAWAMURA  Akira HAYASHI 

Publication
IEICE TRANSACTIONS on Information and Systems  Vol.E92-D  No.1  pp.51-58
Publication Date: 2009/01/01
Online ISSN: 1745-1361
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Pattern Recognition
Keyword: 
DTW,  SDP,  SVM, 

Full Text: PDF(484.9KB)

Summary: 
One of the advantages of the kernel methods is that they can deal with various kinds of objects, not necessarily vectorial data with a fixed number of attributes. In this paper, we develop kernels for time series data using dynamic time warping (DTW) distances. Since DTW distances are pseudo distances that do not satisfy the triangle inequality, a kernel matrix based on them is not positive semidefinite, in general. We use semidefinite programming (SDP) to guarantee the positive definiteness of a kernel matrix. We present neighborhood preserving embedding (NPE), an SDP formulation to obtain a kernel matrix that best preserves the local geometry of time series data. We also present an out-of-sample extension (OSE) for NPE. We use two applications, time series classification and time series embedding for similarity search, to validate our approach.