Weighted dynamic time warping for time series classification

Dynamic time warping (DTW), which finds the minimum path by providing non-linear alignments between two time series, has been widely used as a distance measure for time series classification and clustering. However, DTW does not account for the relative importance regarding the phase difference between a reference point and a testing point. This may lead to misclassification especially in applications where the shape similarity between two sequences is a major consideration for an accurate recognition. Therefore, we propose a novel distance measure, called a weighted DTW (WDTW), which is a penalty-based DTW. Our approach penalizes points with higher phase difference between a reference point and a testing point in order to prevent minimum distance distortion caused by outliers. The rationale underlying the proposed distance measure is demonstrated with some illustrative examples. A new weight function, called the modified logistic weight function (MLWF), is also proposed to systematically assign weights as a function of the phase difference between a reference point and a testing point. By applying different weights to adjacent points, the proposed algorithm can enhance the detection of similarity between two time series. We show that some popular distance measures such as DTW and Euclidean distance are special cases of our proposed WDTW measure. We extend the proposed idea to other variants of DTW such as derivative dynamic time warping (DDTW) and propose the weighted version of DDTW. We have compared the performances of our proposed procedures with other popular approaches using public data sets available through the UCR Time Series Data Mining Archive for both time series classification and clustering problems. The experimental results indicate that the proposed approaches can achieve improved accuracy for time series classification and clustering problems.     

Exact indexing of dynamic time warping

The problem of indexing time series has attracted much interest. Most algorithms used to index time series utilize the Euclidean distance or some variation thereof. However, it has been forcefully shown that the Euclidean distance is a very brittle distance measure. Dynamic time warping (DTW) is a much more robust distance measure for time series, allowing similar shapes to match even if they are out of phase in the time axis. Because of this flexibility, DTW is widely used in science, medicine, industry and finance. Unfortunately, however, DTW does not obey the triangular inequality and thus has resisted attempts at exact indexing. Instead, many researchers have introduced approximate indexing techniques or abandoned the idea of indexing and concentrated on speeding up sequential searches. In this work, we introduce a novel technique for the exact indexing of DTW. We prove that our method guarantees no false dismissals and we demonstrate its vast superiority over all competing approaches in the largest and most comprehensive set of time series indexing experiments ever undertaken.     

Shape retrieval using triangle-area representation and dynamic space warping

In this paper, we present a shape retrieval method using triangle-area representation for nonrigid shapes with closed contours. The representation utilizes the areas of the triangles formed by the boundary points to measure the convexity/concavity of each point at different scales (or triangle side lengths). This representation is effective in capturing both local and global characteristics of a shape, invariant to translation, rotation, and scaling, and robust against noise and moderate amounts of occlusion. In the matching stage, a dynamic space warping (DSW) algorithm is employed to search efficiently for the optimal (least cost) correspondence between the points of two shapes. Then, a distance is derived based on the optimal correspondence. The performance of our method is demonstrated using four standard tests on two well-known shape databases. The results show the superiority of our method over other recent methods in the literature.     

Boundary-based lower-bound functions for dynamic time warping and their indexing

Dynamic time warping (DTW) is a powerful technique in the time-series similarity search. However, its performance on large-scale data is unsatisfactory because of its high computational cost and the fact that it cannot be indexed directly. The lower bound technique for DTW is an effective solution to this problem. In this paper, we explain the existing lower-bound functions from a unified perspective and show that they are only special cases under our framework. We then propose a group of lower-bound functions for DTW and compare their performances through extensive experiments. The experimental results show that the new methods are better than the existing ones in most cases, and a theoretical explanation of the results is also given. We further implement an index structure based on the new lower-bound function. Experimental results demonstrate a similar conclusion.     

Improving the training time of support vector regression algorithms through novel hyper-parameters search space reductions

The selection of hyper-parameters in support vector machines (SVM) is a key point in the training process of these models when applied to regression problems. Unfortunately, an exact method to obtain the optimal set of SVM hyper-parameters is unknown, and search algorithms are usually applied to obtain the best possible set of hyper-parameters. In general these search algorithms are implemented as grid searches, which are time consuming, so the computational cost of the SVM training process increases considerably. This paper presents a novel study of the effect of including reductions in the range of SVM hyper-parameters, in order to reduce the SVM training time, but with the minimum possible impact in its performance. The paper presents reduction in parameter C, by considering its relation with the rest of SVM hyper-parameters (γ and ε), through an approximation of the SVM model. On the other hand, we use some characteristics of the Gaussian kernel function and a previous result in the literature to obtain novel bounds for γ and ε hyper-parameters. The search space reductions proposed are evaluated in different regression problems from UCI and StatLib databases. All the experiments carried out applying the popular LIBSVM solver have shown that our approach reduces the SVM training time, maintaining the SVM performance similar to when the complete range in SVM parameters is considered.     

On the dynamic time warping of cyclic sequences for shape retrieval

In recent years, in shape retrieval, methods based on dynamic time warping and sequences where each point of the contour is represented by elements of several dimensions have had a significant presence. In this approach each point of the closed contour contains information with respect to the other ones, this global information is very discriminant. The current state-of-the-art shape retrieval is based on the analysis of these distances to learn better ones.     

A prediction scheme using perceptually important points and dynamic time warping

An algorithmic method for assessing statistically the efficient market hypothesis (EMH) is developed based on two data mining tools, perceptually important points (PIPs) used to dynamically segment price series into subsequences, and dynamic time warping (DTW) used to find similar historical subsequences. Then predictions are made from the mappings of the most similar subsequences, and the prediction error statistic is used for the EMH assessment. The predictions are assessed on simulated price paths composed of stochastic trend and chaotic deterministic time series, and real financial data of 18 world equity markets and the GBP/USD exchange rate. The main results establish that the proposed algorithm can capture the deterministic structure in simulated series, confirm the validity of EMH on the examined equity indices, and indicate that prediction of the exchange rates using PIPs and DTW could beat at cases the prediction of last available price.     

Dynamic time warping constraint learning for large margin nearest neighbor classification

Nearest neighbor (NN) classifier with dynamic time warping (DTW) is considered to be an effective method for time series classification. The performance of NN-DTW is dependent on the DTW constraints because the NN classifier is sensitive to the used distance function. For time series classification, the global path constraint of DTW is learned for optimization of the alignment of time series by maximizing the nearest neighbor hypothesis margin. In addition, a reduction technique is combined with a search process to condense the prototypes. The approach is implemented and tested on UCR datasets. Experimental results show the effectiveness of the proposed method.     

Efficient dynamic time warping for 3D handwriting recognition using gyroscope equipped smartphones

Handwriting character recognition from three-dimensional (3D) accelerometer data has emerged as a popular technique for natural human computer interaction. In this paper, we propose a 3D gyroscope-based handwriting recognition system that uses stepwise lower-bounded dynamic time warping, instead of conventional 3D accelerometer data. The results of experiments conducted indicate that our proposed method is more effective and efficient than conventional methods for user-independent recognition of the 26 lowercase letters in the English alphabet.     

CSDTW: 一种时间序列流上的受限动态弯曲距离

针对SPRING提出的使用精确DTW距离造成弯曲矩阵中有许多无用的计算数据格的不足,提出一种受限的动态时间弯曲距离CSDTW。通过限制某时刻弯曲路径的弯曲程度,同时结合DTW上的提前终止算法,以减少无用数据格的出现。实验对比表明,CSDTW能够避免大量冗余数据格的计算,加快流环境下精确DTW处理的效率。     

On the time series support vector machine using dynamic time warping kernel for brain activity classification

A new data mining technique used to classify normal and pre-seizure electroencephalograms is proposed. The technique is based on a dynamic time warping kernel combined with support vector machines (SVMs). The experimental results show that the technique is superior to the standard SVM and improves the brain activity classification. This research was partially supported by Rutgers Research Council grant 202018, NSF grants CCF-0546574, DBI-980821, EIA-9872509, and CCF 0546574, and NIH grant R01-NS-39687-01A1. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 159–173, January–February 2008.     

基于动态时间弯曲的多模板匹配车型分类

感应线圈采集到的频率变化曲线,取决于车速、车辆自身结构及其通过感应线圈时的相对位置.针对同类车辆的频率变化曲线存在伸长或压缩情况.研究一种基于动态时间弯曲(DTW)的车型分类新方法.首先对采集到的车辆频率变化数据序列进行预处理;其次,结合DTW方法和最优聚类分析原理,选取同类车型的多个频率变化特征曲线作为分类模板,以改善单模板匹配方法的分类正确率;再次,确定同类车型的局部区分度指标,并优化调整局部区分度指标范围;最后对考察车辆的采样曲线进行多模板匹配分析,得出车型分类结论.仿真实验分析了本文方法与其他方法比较存在的优势.     

Scaling and time warping in time series querying

The last few years have seen an increasing understanding that dynamic time warping (DTW), a technique that allows local flexibility in aligning time series, is superior to the ubiquitous Euclidean distance for time series classification, clustering, and indexing. More recently, it has been shown that for some problems, uniform scaling (US), a technique that allows global scaling of time series, may just be as important for some problems. In this work, we note that for many real world problems, it is necessary to combine both DTW and US to achieve meaningful results. This is particularly true in domains where we must account for the natural variability of human actions, including biometrics, query by humming, motion-capture/animation, and handwriting recognition. We introduce the first technique which can handle both DTW and US simultaneously, our techniques involve search pruning by means of a lower bounding technique and multi-dimensional indexing to speed up the search. We demonstrate the utility and effectiveness of our method on a wide range of problems in industry, medicine, and entertainment.     

Supporting exact indexing of arbitrarily rotated shapes and periodic time series under Euclidean and warping distance measures

Shape matching and indexing is important topic in its own right, and is a fundamental subroutine in most shape data mining algorithms. Given the ubiquity of shape, shape matching is an important problem with applications in domains as diverse as biometrics, industry, medicine, zoology and anthropology. The distance/similarity measure for used for shape matching must be invariant to many distortions, including scale, offset, noise, articulation, partial occlusion, etc. Most of these distortions are relatively easy to handle, either in the representation of the data or in the similarity measure used. However, rotation invariance is noted in the literature as being an especially difficult challenge. Current approaches typically try to achieve rotation invariance in the representation of the data, at the expense of discrimination ability, or in the distance measure, at the expense of efficiency. In this work, we show that we can take the slow but accurate approaches and dramatically speed them up. On real world problems our technique can take current approaches and make them four orders of magnitude faster without false dismissals. Moreover, our technique can be used with any of the dozens of existing shape representations and with all the most popular distance measures including Euclidean distance, dynamic time warping and Longest Common Subsequence. We further show that our indexing technique can be used to index star light curves, an important type of astronomical data, without modification. Reproducible Research Statement: All datasets and images used in this work are freely available at .     

Automated evaluation of physical therapy exercises using multi-template dynamic time warping on wearable sensor signals

We develop an autonomous system to detect and evaluate physical therapy exercises using wearable motion sensors. We propose the multi-template multi-match dynamic time warping (MTMM-DTW) algorithm as a natural extension of DTW to detect multiple occurrences of more than one exercise type in the recording of a physical therapy session. While allowing some distortion (warping) in time, the algorithm provides a quantitative measure of similarity between an exercise execution and previously recorded templates, based on DTW distance. It can detect and classify the exercise types, and count and evaluate the exercises as correctly/incorrectly performed, identifying the error type, if any. To evaluate the algorithm's performance, we record a data set consisting of one reference template and 10 test executions of three execution types of eight exercises performed by five subjects. We thus record a total of 120 and 1200 exercise executions in the reference and test sets, respectively. The test sequences also contain idle time intervals. The accuracy of the proposed algorithm is 93.46% for exercise classification only and 88.65% for simultaneous exercise and execution type classification. The algorithm misses 8.58% of the exercise executions and demonstrates a false alarm rate of 4.91%, caused by some idle time intervals being incorrectly recognized as exercise executions. To test the robustness of the system to unknown exercises, we employ leave-one-exercise-out cross validation. This results in a false alarm rate lower than 1%, demonstrating the robustness of the system to unknown movements. The proposed system can be used for assessing the effectiveness of a physical therapy session and for providing feedback to the patient.     

嵌入式语音识别系统中的DTW在线并行算法*

为提高语音识别系统的实时性,利用动态规划和并行计算思想,提出一种适用于嵌入式语音识别系统的DTW(动态时间规整)在线并行算法。通过分析标准DTW及其主要衍生算法,对DTW算法的数据结构进行改进以满足在线算法要求,在寻找最佳路径过程中动态连续地分配和释放内存或预先分配固定大小的内存,并将多个关键词的DTW计算分布到多个运算单元;最后汇总各运算单元的结果得到识别结果。实验表明,该算法比经典DTW降低了内存使用和识别时间,并使语音识别的实时系数达到1.17,具有较高的实时性。     

飞机牵引车语音识别的动态时间规整优化算法

为研究飞机牵引车智能语音控制,实现机场环境下牵引车对飞行员语音命令的精确、高效识别,同时针对传统动态时间规整（DTW）算法计算量大、时间复杂度高、算法识别效率低的问题,提出了一种车辆语音识别的六边形弯曲窗口约束DTW优化算法。首先,从DTW算法原理、牵引车指令的语音特性和机场环境三方面,分析了弯曲窗口对DTW算法识别精度、效率的影响;然后,在Itakura Parallelogram菱形弯曲窗口约束DTW优化算法的基础上,进一步提出了六边形弯曲窗口约束的DTW全局优化算法;最后,通过改变优化系数,实现了最优六边形弯曲窗口约束的DTW算法方案。基于孤立词识别的实验结果表明,所提最优算法与传统DTW算法、菱形弯曲窗口约束的DTW算法相比,识别错误率分别降低77.14%和69.27%,识别效率分别提高48.92%和27.90%。该最优算法更具鲁棒性、时效性,可以作为飞机牵引车智能控制的理想指令输入端口。     

Improved Tabu search heuristics for the dynamic space allocation problem

The dynamic space allocation problem (DSAP) presented in this paper considers the task of assigning items (resources) to locations during a multi-period planning horizon such that the cost of rearranging the items is minimized. Three tabu search heuristics are presented for this problem. The first heuristic is a simple basic tabu search heuristic. The second heuristic adds diversification and intensification strategies to the first, and the third heuristic is a probabilistic tabu search heuristic. To test the performances of the heuristics, a set of test problems from the literature is used in the analysis. The results show that the tabu search heuristics are efficient techniques for solving the DSAP. More importantly, the proposed tabu search heuristic with diversification/intensification strategies found new best solutions using less computation time for one-half of all the test problems.     

Summarizing a set of time series by averaging: From Steiner sequence to compact multiple alignment

Summarizing a set of sequences is an old topic that has been revived in the last decade, due to the increasing availability of sequential datasets. The definition of a consensus object is on the center of data analysis issues, since it crystallizes the underlying organization of the data.Dynamic Time Warping (DTW) is currently the most relevant similarity measure between sequences for a large panel of applications, since it makes it possible to capture temporal distortions. In this context, averaging a set of sequences is not a trivial task, since the average sequence has to be consistent with this similarity measure.The Steiner theory and several works in computational biology have pointed out the connection between multiple alignments and average sequences. Taking inspiration from these works, we introduce the notion of compact multiple alignment, which allows us to link these theories to the problem of summarizing under time warping. Having defined the link between the multiple alignment and the average sequence, the second part of this article focuses on the scan of the space of compact multiple alignments in order to provide an average sequence of a set of sequences. We propose to use a genetic algorithm based on a specific representation of the genotype inspired by genes. This representation of the genotype makes it possible to consistently paint the fitness landscape.Experiments carried out on standard datasets show that the proposed approach outperforms existing methods.