QP-DTW: Upgrading Dynamic Time Warping to Handle Quasi Periodic Time Series Alignment

1. Introduction

A time series is a continuation of couples < (v ₁ ,t ₁ ), (v ₂ ,t ₂ ), ..., (v _i ,t _i ), ... > where vi is a value or a vector of values taken at a moment ti. This notation can be abbreviated in < v ₁ , v ₂ , ..., v _i , ...> when the reference to the time does not need to be clarified [ 1 ].

There are an increasing amount of works related to time series, given their usefulness in different areas, especially in finance, where the calculation of changes in the exchange rate is very important. For example, the modeling of time series for financial forecasting was carried out by Barbulescu and Bautu [ 2 ]. In economics, Awad et al. [ 3 ] performed prediction of future values of time series related to economic activities. In industry, profiling and fault detections in systems have been performed by [ 4 , 5 ]. Classification and identification of electrocardiograms (ECGs) of patients with heart diseases is also a very active area related to time series [ 6 - 8 ]. The detection of abnormalities in ECG by aligning time series is much appreciated. It has particularly been performed by the Shape Exchange Algorithm (SEA) method of Boucheham [ 9 , 10 ]. Time series motif discovery from unbounded streams is also a growing field [ 11 ].

Studies in the field of time series data mining evolve around two key issues: the choice of distance/similarity measures to match time series (effectiveness), and the mechanisms to accelerate the efficiency of the match. Concerning the first question, the matching of time series is divided into two categories: comparison and alignment. The difference between the two is that the comparison is based on a measure of distance/similarity that renders a numerical value reflecting the degree of resemblance between the two time series. However, alignment is used to specify exactly where the time series differ and where they are similar. In other words, alignment is a kind of explanation of time series, one by the other, which, obviously, is a more difficult problem to resolve.

This study is dedicated to alignment of quasi-periodic time series and especially to heartbeats time series provided from the ECG records. Quasi-periodic time series are concatenations of quasi-similar forms called periods [ 9 ].

Fig. 1 presents the characteristics of an ECG composed of three quasi-regulars periods reflecting three heart cycles. Each cycle (period) is itself composed of three consecutive basic patterns: P wave, QRS complex, and T wave.

Alignment of time series and search of a query of time series pose difficult problems. These problems are: difference in time axis scales (Fig. 2(a)), difference in amplitude axis scales (Fig. 2(b)), shift on the amplitude axis (Fig. 2(c)) between the series, shift on the time axis (Fig. 2(d)) and different type of noise. Particularly, ECG traces are characterised by morphological changes due to the problems of variability of ECG measurement.

Time series are also characterized by very big sizes of collected data, big dimensionality and the need of permanent update [ 12 ]; what makes search, query, classification, which are all based on time series comparison and alignment, a very difficult task.

Dynamic time warping (DTW) [ 13 ] is generally recognized by several researchers [ 14 - 16 ] to be the most effective alignment technique for time series, because it handles the problems of distortion on the time and amplitude axis with great elegance.

However, the DTW has difficulties to deal with these problems when it comes to align quasi-periodic time series with different number of periods (cycles) each. In particular, the method completely fails in the alignment of quasi-periodic time series which are significantly phase shifted as illustrated in Fig. 3(a).

SEA [ 9 ] is a method that aligns quasi-periodic time series. However, when it comes to align time series which are seriously contaminated by noise, the SEA method shows some weaknesses as illustrated in Fig. 4.

To remedy to the problems of DTW and SEA, we propose in this work a novel algorithm that combines the advantages of these methods. Our method deals effectively with the quasi-periodic time series even when they are significantly phase shifted and contaminated by noise. The new method is then called QP-DTW (quasi-periodic dynamic time warping).

The tests were performed on ECG traces, selected from the public database “Massachusetts Institute of Technology - Beth Israel Hospital (MIT-BIH)” [ 17 ] and from the PTB Diagnostic ECG Database [ 18 ]. The results show that the proposed algorithm is more efficient than DTW and SEA in terms of alignment accuracy, quantitatively and qualitatively.

The remaining part of this paper is organized as follows. Section 2 presents some related works related to time series comparison/alignment. Section 3 presents the DTW method. Section 4 presents the SEA method. In Section 5, we present our proposed method QP-DTW. Section 6 is devoted to application of our method and to experimental results. Finally, this work is terminated with a general conclusion and future plans.

2. Related Works and Motivations

2.1 Related Works

According to Boucheham [ 14 ] matching methods for time series can be divided into two major classes. The first class is based on the nature of the algorithm; either they are comparison methods or alignment methods. Comparison methods render only one numerical value in the range [0, 1] that reflects the similarity of the sequences. Obviously these methods are incapable to align the time series. The second class is based on the type of the used data; either they are periodic methods or non-periodic methods.

2.1.1 Comparison or alignment methods

Comparison methods

The most famous comparison method is the Euclidean distance. It is fast and simple but works only for time series of equal lengths. It has been also demonstrated by several researchers that this distance is fragile [ 19 , 20 ] because it is unable to handle the time offsets of a time series with respect to one other. Fig. 5 shows that even the two time series are similar, the Euclidian distance notice that they are different. This is due to the point to point alignment.

Another very effective method of comparison is the discrete Fourier transform (DFT) [ 1 ]. The authors represent temporal sequences in the frequency domain with the first most significant k coefficients of Fourier and they use the Euclidian distance to compare them starting from the fact that the Euclidean distance between two time series in the time domain is the same in the frequency domain. The advantage of this method is that the amplitudes of the frequencies don’t change despite the time shifts. Another method of comparison is the histogram. Chen and Ozsu [ 21 ] build a histogram for each segment of both time series and compare the corresponding histograms. After that they developed multi-scale histograms. They proved that it can efficiently compare time series data even when they are of different length and contain noise or time shifting and scaling. The edit distance between two alphanumeric sequences is another comparison method. It is a way of quantifying how dissimilar are two strings (e.g., words) by counting the minimum number of operations required to transform one string into the other [ 22 ].

Alignment methods

Bozkaya et al. [ 23 ] proposed a modified version of the edit distance. They referred to the method by longest common sub-sequence (LCSS). The LCSS is an alignment method based on the number of pairs of ordered temporal sub-sequences which are similar but not overlapped. If there is enough the sequences will be regarded as similar. The method then compares each point in a series with 0 or 1 point on the other series. The LCSS is elastic and allows stretching in order to match the identical elements between them. It is mainly used for treating the noisy data because it ignores the extreme values by counting only the commons sub sequences. It is also effective for the problems of different time scaling.

The DTW is a very much appreciated alignment method. Fig. 5(b) illustrates the effectiveness of the DTW comparing to the Euclidian distance (Fig. 5(a)). Instead of comparing each point series with another point of another series, which occurs at the same time t, the measure compares each point series with one or many points of another series, these points can be shifted.

There are various applications of the DTW, we cite, ECG heart-beat clustering and analysis [ 24 , 25 ], ECG classification [ 26 , 27 ].

The SEA is a simple and parameter-free method. It was proposed by Boucheham [ 9 ] to deal with the problem of quasi-periodic time series alignment. The method is based on the sorting of time series on their amplitude axes. This sort gives the time series a kind of signature, in the sense that the resulting traces represents a stable and global characteristics of the used time series.

2.1.2 Periodic or non-periodic methods

Based on the nature of the used data, Boucheham [ 14 ] classifies alignment methods of time series in ascending order of complexity of the data.

Class A: Non-periodic or one period no phase shift

Methods in this class treat time series that are non periodic or periodic with only one period with the condition that none of the two periodic time series is significantly phase shifted with respect to the other (e.g., Fig. 3(a)). Methods in this category are DFT, LCSS, Euclidian distance, histograms, and DTW.

Class B: One period with phase shift

Time series in this class are quasi-periodic and composed of one period. However, each time series is phase-shifted with respect to the others (e.g., Fig. 3(b)). Time series can also be composed of the same number of periods. The phase independent DTW [ 15 ] is in this class.

Class C: Multiple periods with phase shift

Time series in this class are quasi-periodic and composed of many periods each, but not necessarily the same number of periods. Indeed, time series that contain many periods but the same number of periods brings the data to class A if there is no (significant) phase shift and to class B if there is (significant) phase shift [ 14 ].

Thus, the types of data specific to this class are time series that are phase-shifted, in addition of being composed of a different number of periods each (e.g., Fig. 3(c)). Methods in this class are SEA, FANSEA, ASEAL [ 9 , 14 , 28 ] and QP-DTW.

2.2 Motivation

The DTW method suffers from several problems which are subjects of many researches. In this context, we list:

• The DTW cannot deal with the phase shift problems in quasi-periodic time series. In Fig. 6, both ECG plots are similar because they result from the same person but they do not begin at the same time. In this case, the DTW done a bad alignment; only the QRS complex has been correctly aligned, the other components of the two ECG time series (P and T waves) have just been matched with their sequentially equivalent parts. This is a case of phase shift problem.

• For the matching of objects in the images by their contours, the alignment of the shapes can be solved with the DTW, by the transformation of the 2D forms into 1D signal. However if a rotation is applied to one of the objects, the task becomes impossible to achieve by the DTW. To solve this problem Keogh et al. [ 15 ] proposed the Phase Independent DTW method. Their method is very expensive because it implements techniques of indexation to allow the verification of all the possible rotations of shape. This method deals also with the phase shifted quasi-periodic time series; but these time series cannot have a different number of periods. They can have either a single period, or the same number of periods each.

• Another problem that DTW cannot solve is the alignment of similar time series that have some peaks of amplitudes with heights slightly difference as shown in Fig. 4, which implies difficulties in analysis and diagnosis. To solve this problem, Keogh and Pazzani [ 29 ] proposed a modification of the DTW that does not consider the values of the points of the amplitude axis, but rather the characteristic of the highest level of the shape by considering the first derivative of the sequence.

• The DTW sometimes gives pathological results because it tries to explain the variations of amplitudes by deforming the time axis. This problem is called the problem of “Singularity”. Most of the methods try to solve this problem by limiting the possible deformations [ 13 , 19 , 30 ]. However these methods cannot find the optimal warping path if the band of delimitation is too small or if it is too big [ 29 ].

• The SEA method has also difficulties to align similar time series that have some peaks of amplitude with heights slightly difference as shown in Fig. 4. In this figure the higher signal (blue) is significantly contaminated with low frequency noise (baseline wondering due to respiration). Improved versions of the SEA method have been proposed in [ 14 , 28 , 31 ].

2.3 Contribution

Our main contribution consists in the elevation of the DTW power of alignment from the lowest level (class A, non-periodic time series) to the highest level (class C, multiple periods with phase shift), according to the recent classification of time series alignment methods proposed by Boucheham [ 14 ]. Indeed, the DTW is inappropriate to align quasi periodic time series like ECG signals, capnogram signals (a plot reflecting the quantity of expired CO2, extensively used in asthmatic patients surveillance, urgency medicine and also in surgery medicine) and electroencephalogram (EEG) signals (a plot measuring the electrical activity of the brain) unlike our method which is capable of aligning very complex quasi-periodic time series (according to the classification of Boucheham [ 14 ]). On the other hand and compared to the existing SEA method of Boucheham [ 9 ] the proposed QP-DTW performs significantly much better.

3. Dynamic Time Warping

The famous DTW is an alignment method. It was applied at first for the recognition of vocal sequences by [ 13 , 30 ] then it has been introduced in the field of data mining by Berndt and Clifford [ 19 ] and knew a big success in this context.

The DTW method consists in establishing a non linear alignment of sequences to allow the mapping of sequences which have different lengths or suffer from the time-shift problem.

First, to align two sequences X= (x _i ), i = 1: n and Y = (y _j ), j = 1: m, we construct an accumulated distance matrix m×n , each cell represents the alignment between two points x _i and y _j calculated by one of the distances of Minkowski. The Euclidian distance (Eq. (1)) is the most often used metric to calculate these cells.

Technically, the values of the sequences to compare X = (x _i ), i = 1: n and Y = (y _j ), j = 1: m are replicated until obtaining the best matching between the sequences [ 32 ]. The obtained sequences have the same number of elements k with max (n,m) ≤ k ≤ n + m + 1.

In the example shown in Fig. 7, the accumulated distance matrix M is presented. The sequences to compare X and Y , are presented to the underside of the matrix. After the calculation of the cumulative matrix, we calculate the minimum warping path W and we obtain the sequences X' and Y' . The values of cells are calculated as follows:

1. First cell: [TeX:] $$M [ 1,1 ] = \left[ x _ { 1 } - y _ { 1 } \right]$$

2. First line: [TeX:] $$M [ 1 , j ] = \left[ x _ { j } - y _ { 1 } \right] + M [ 1 , j - 1 ]$$

3. First column: [TeX:] $$M [ i , 1 ] = \left[ x _ { 1 } - y _ { i } \right] + M [ i - 1,1 ]$$

4. All the other elements with the condition (i, j>1) :

The mapping chosen for the DTW is the one that minimizes the Euclidian distance: [TeX:] $$\sum _ { i = 1 } ^ { k } \left| a _ { i } - b _ { i } \right|$$

In this example the DTW(X, Y)=4. It is represented by the value of the last cell. The cells in gray colors represent the optimal warping path “W” . They indicate the replicated values and the alignment of the two sequences.

The values that are close in the two sequences are replicated, such as the value 5 of the sequence X which is replicated twice in the sequence X' and put in correspondence with the values 5 and 7 of the sequence Y'.

There are several constraints on the warping path we cite:

• Boundary Condition. w ₁ = (1, 1) and w _K = (m, n) , to force the end points in each series to match.

• Continuity. Given w _k = (a, b) then w _k-1 = (a', b') where a–a' ≤ 1 and b–b' ≤ 1 , to oblige the warping path to go to the adjacent cells.

• Monotony. Given w _k = (a, b) then w _k-1 = (a', b') where a–a' ≥ 0 and b–b' ≥ 0 to force the points of W to be spaced monotonically in time.

There are several warping path which satisfy these conditions, but we choose the one that minimizes the warping cost:

The k _th element of W is defined as w _k = (i,j) _k such that:

Eq. (4) illustrates the dynamic programming method used for the calculating of the optimal path which represents the DTW distance. Let D, this cumulative distance until w _k cell.

4. Shape Exchange Algorithm

The principle of the method is as follows:

Let X= (x _i ), i = 1: n and Y = (y _j ), j = 1: m be the two time series to match.

1. Decompose X and Y on temporal indexes and amplitude indexes.

2. Order the X and Y on their amplitudes indexes.

3. Exchange amplitude indexes between X and Y without changing their temporal indexes which are in disorder.

4. Reorder X and Y on their temporal indexes and reconstruct X and Y to X _REC and Y _REC .

5. Compare (X, X _REC ) and (Y, Y _REC ) .

5. The Proposed Method: Quasi-Periodic Dynamic Time Warping (QP-DTW)

Most of the methods that try to improve the DTW focus on the acceleration of its execution time [ 33 , 34 ]. However, the alignment quality of the DTW poses many problems [ 9 , 29 ], especially when the DTW comes to align quasi-periodic time series containing each a different number of quasisimilar phases. To overcome this problem Boucheham [ 9 ] propose the SEA method. However this method uses the linear mapping to equalize the series of different length. The principle of the linear mapping is to force the longest time series to shrink by accelerating the step in the temporal axis until it can match the shorter series and vice versa, the shortest series will stretch to match the longest series by browsing slowly the temporal index. The technique of linear mapping is not appropriate for the SEA method because the longest series loses some important values when shrinking. In our method, we have done a hybrid of the SEA and DTW methods, to take advantage of both methods.

5.1 Time and Space Complexities

Time complexity: Let n and m be the lengths of the time series to align, X and Y , respectively. Given that the time complexity of DTW is of O(nm) and the time complexity of SEA is of O(Max(n ² ,m ² )) , our hybrid method will have a time complexity of O(nm+Max(n ² ,m ² )) , which is of quadratic order.

Space complexity: Given that the space complexity of DTW is of O(nm) and the space complexity of SEA is of O(n+m) , our method QP-DTW will have a space complexity of O(nm+n+m) , which is of quadratic order.

Step 1: Finding the optimal warping path by the DTW

The algorithm DTW is executed to equalize the length of the two time series and make the first mapping between them by the replication of certain values which are close in both time series, as illustrated in Fig. 7.

Step 2: Sorting on the amplitude

The sorting of the stretched time series, on the coordinates of their amplitude indexes is established to give them a stable signature. The result of this step is a matrix for each time series containing the sorted amplitudes in ascendant or descendent order with their equivalents temporal coordinates (not sorted). In this way, if the time series are similar but phase shifted, they will always have almost the same trace which represents their signatures. An example of signatures is illustrated in Fig. 8.

Step 3: Signatures exchange

This step is divided into two parts. The first one consists in making the exchange of signatures between both time series. The first time series will receive the coordinates of amplitudes (signature) of the second time series and vice versa for the second series. The second part consists in restoring the normal size of the time series after the exchange of signature which requires that the time series are of equal length. Thus, the temporal indexes replied in every new series must be deleted with their equivalent amplitudes. This part does not affect the results of alignment; it just allows having a clearer visual inspection of the traces.

Step 4: Sorting on the time indexes and alignment

Signatures represent well the characteristics of the time series but they do not consider the shifts and the differences of timescales. The sorting of the time series on the respective temporal indexes allows reconstructing them.

Every time series will then be aligned with its reconstructed time series by using the correlation and PRD (percent root difference) factors as objective criteria and the visual inspection as subjective criteria.

The proposed algorithm is described in Fig. 9.

6. Experimental Tests and Discussion

In this section, we present an illustrative example and we proceed to the numerical and the visual comparison between QP-DTW, DTW and SEA. The numerical comparison is performed by the PRD (Eq. (5)) and the correlation factor (Eq. (6)). The correlation must be between 0 and 1 and the PRD must be between 0% and 100%.

We indicate that all applications have been performed on a machine with the following specifications: Intel Pentium CPU U5400 (1.20 GHz) with 3 GB main memory, running under Windows 7. We also mention that all methods have been implemented in the MATLAB 12 programming environment.

where

and

We start the comparison by introducing an example of time series in the class C. In this example, we refer to the time series rec.215 of the MIT-BIH ECG database. Fig. 8(a) and (b) present the signatures of the time series X and Y for the SEA and QP-DTW methods. We see that the signatures established by QP-DTW are attached which confirm that the series come from the same recording. Unlike the signatures of SEA which are detached. Fig. 10(a) shows the original traces X and Y. Fig. 10(b) and (c) illustrate the alignment done respectively by SEA and QP-DTW methods for the time series X and its reconstructed time series (left of Fig. 10(b) and (c)) and for the time series Y and its reconstructed time series (right of Fig. 10(b) and (c)). Fig. 10(d) presents the alignment done by the DTW method for the time series X and Y. Note that the two traces are from the same time series but that they are of different lengths. They also have some pikes of amplitude of slightly different lengths and they are not taken at the same time (offset of 35 seconds for Y). The segment (X) was purposely taking at the beginning of the recording and the segment (Y) at the end of the recording to illustrate the phase shift problem in quasi periodic time series.

Formulas are applied to the two traces (X and Y) with their respective reconstructed traces (X _rec and Y _rec ). As well we will report in Table 1, the PRD(X,X _rec ), Corr(X,X _rec ), PRD(Y,Y _rec ) and Corr(Y,Y _rec ) for SEA and QP-DTW methods and the PRD(X,Y), Corr(X,Y) for the DTW method.

The visual inspection of Fig. 10 and the numerical results reported in Table 1 show that despite all the problems previously cited, QP-DTW arrives to align these particularly very complex time series. We see also that SEA method doesn't do a good alignment because time series Y and its reconstruction are almost detached, only the QRSs have been correctly aligned. The DTW done a very bad alignment because, the second QRS of the time series Y haven’t been aligned with the QRSs of the time series X.

6.1. Comparison of Similar Traces from the MIT-BIH ECG Database

Fig. 11 shows the case of two plots of the same record with 1,000 samples of the time series rec.113 for X and 1,200 samples of the same time series with a shift of 30 seconds for Y. Fig. 11(a) presents the original time series. They have some peaks of amplitudes with heights slightly difference due to low frequency noise. Fig. 11(b) shows the alignment performed by SEA. We see that the original and the reconstructed time series are detached because of the problem of low frequency noise. Fig. 11(c) shows that despite all the problems mentioned above, QP-DTW done an almost perfect reconstruction, to the point that it is difficult to distinguish between the original and the reconstructed time series. Fig. 11(d) shows the misalignment of X and Y done by DTW because of the problem of quasi periodicity and low frequency noise of the time series. The numerical results presented in Table 2 confirm this state with a very low error rate (PRD) and a very high correlation in favor of QP-DTW. In contrary they indicate a high error rate (PRD) for DTW and SEA, an average correlation for SEA and a low correlation for DTW.

Fig. 12 shows the case of two plots of the same record with 1,000 samples of the time series rec.215 for X and 2000 samples of the same time series with a shift of 35 seconds for Y. Fig. 12(a) presents the original time series. The X signal has been taken at the beginning of the recording and the Y signal has been taken at the end of the recording to illustrate the phase shift problem. Fig. 12(b) shows the alignment performed by SEA. We see that SEA method fails in face of the problem of low frequency noise which is presented in the Y signal. Fig. 12(c) shows the alignment performed by QP-DTW. Fig. 12(d) presents the bad alignment done by DTW. We see that our method resolve efficiently the problems of phase shift and noise. The factors of similarity (Corr) and of dissimilarity (PRD) clearly indicate the superiority of our method in comparison with DTW and SEA. The correlation of QP-DTW is higher than those of DTW and SEA and its PRD is the lowest. It represents the half of the value of PRD of DTW.

Fig. 13 shows the case of two plots of the same record with 1,000 samples of the time series rec.104 and 2,000 samples of the same time series with a shift of 20 seconds for Y. Fig. 13(a) presents the original time series. Each series is composed of different number of periods which are phase shifted. The Y signal presents also the problem of noise. The alignment performed by the SEA method is presented in Fig. 13(b). We see that SEA fails facing the problems of different amplitude scales and phase shift. Fig. 13(c) presents the alignment done by QP-DTW. It shows that our method resolve all the problems previously cited. The alignment done by DTW is presented in Fig. 13(d). We see that DTW fails again facing the problems of phase shift and noise. The numerical results indicate a high correlation and a low PRD for QP-DTW, a very low correlation and a high PRD for SEA and an average PRD and correlation for DTW.

6.2 Comparison of Similar Traces of the PTB Diagnostic ECG Database

Fig. 14 shows the case of two plots of the same record with 1,000 samples of the time series “s0287lrem” from the PTB Diagnostic ECG Database [ 18 ] for X and 1,200 samples of the same time series. The time series are phase shifted. The visual inspection and the numerical results indicate that the alignment done by QP-DTW is much better than the alignment done by SEA and DTW. Specifically, it can be noticed in this particular case that the SEA method deals weakly when we have one cycle in series X and two cycles in series Y, whereas the proposed QP-DTW deals much better with this complex case.

Fig. 15 shows the case of two plots of the same record with 2,000 samples of the time series “s0273lrem” from the PTB Diagnostic ECG Database for X and 3,000 samples of the same time series for Y. The visual inspection of the Fig. 15 shows that QP-DTW has done a good alignment, contrary to DTW which fails completely and to SEA which shows some weakness. In Table 3, the numerical results confirm this fact.

6.3 Comparison of Dissimilar Time Series

Fig. 16 shows the case of two plots from two different records with 2,000 samples of the time series rec.103 for X and 2,000 samples of the time series rec.123 for Y and a shift of 40 seconds for Y. The visual inspection of the figure shows that the original time series and the reconstructed time series by QP-DTW are detached. The numerical results in Table 4 indicate a very low correlation and a very high PRD in favor of QP-DTW. This proves that our method is perfectly capable of differentiating dissimilar time series.

Fig. 17 shows two plots from two different records with 1,000 samples of the time series rec.100 for X and 2,000 samples of the time series rec.112 for Y and a shift of 50 seconds for Y. The visual inspection and the numerical results indicate that QP-DTW done the best misalignment.

Figs. 18 and 19 show respectively the changes in the correlation and in the PRD of the three methods in relation to the size of time series. Fig. 18 indicates that the correlation of QP-DTW is the best and that it is always close to 1. Fig. 19 indicates that the PRD of QP-DTW is always the lowest despite increasing data size.

7. Conclusion

In this work, we have proposed a novel alignment method for quasi-periodic time series. The proposed QP-DTW can be seen as an upgrade of the classical DTW that handles alignment of very complex time series, more effectively than the existing SEA method, quantitatively and qualitatively. Therefore, the proposed method would be a good alternative for time series applications, such as data mining, pattern recognition, search/retrieval, motif discovery and classification.